在自主车辆路径规划中逆向D*算法的应用

雷雨能，赖文娟，曾 刊

(中国兵器工业第五八研究所 军品部，四川 绵阳 621000)

自主车辆研究是当今的1 个热点，路径规划作为自主车辆完成行驶任务的安全保障，是其智能化程度的重要标志。所谓路径规划，是指在具有障碍物的环境中，机器人按照某一特定性能指标(如距离、时间等)搜索1 条从起始状态到目标状态的最优或次优路径的过程。由于自主车辆运行在户外复杂环境中，因此对路径规划的仿真研究非常必要。传统的路径规划算法主要有人工势场法、可视图法，而目前比较流行的路径规划算法主要有A*、D*、神经网络、遗传以及蚁群等等算法［1］。其中，文献［2］采用的D*算法比较适合在小规模、部分已知的环境中进行路径规划，而在较大规模复杂环境中，直接规划起点到终点的计算代价往往很大。

针对上述问题，本文对逆向D*算法进行了分析和验证。对自主车辆装备的各种传感器所探测到的前方路面环境建立局部栅格地图。在局部栅格地图中采用A*方法［3］搜索中间节点，并规划得出车辆当前位置到中间节点的局部路径。在行驶到中间节点后，自主车辆再重新搜索下1 个中间节点，并规划下1 条局部路径，自主车辆沿着下1 条局部路径行驶。依此循环后，直到到达最终目的地。通过实验验证，该算法克服了D*算法在大规模环境下计算量较大的缺点，提高了路径规划算法的效率。

1 逆向D* 算法

1.1 基本思想

在部分信息未知的复杂环境中，机器人路径规划有以下3 个特点［4］:①环境信息的改变大多是在机器人周围相当近的1 个区域当中进行的，这主要是因为机器人一般装备的各种传感器都只具有一定的观察范围。这意味着路径规划过程不一定非要在整个全局环境内进行。②机器人的行进过程中，如果大多数的障碍物很小，那么简单的路径改变就足以表达，这样就可以避免很高的计算代价。③在机器人行进过程中的1 个节点上，在大多数情况之下只有剩下的一部分路径需要重新规划。那么，根据第2 个特点，重新规划的这部分路径就可以变得更短，D*算法正是针对部分信息已知的环境中路径规划问题提出的。

D*算法在小规模环境区域规划中比较有效，但在较大规模环境下直接规划起点到终点的路径，往往造成很大的计算代价。为了不再计算初始的目标距离势场，通过定义“机器人距离”的方法来建立机器人当前位置中心的局部区域势场，并且通过搜索距离目标估计代价最小的中间目标节点，来满足机器人滚动优化［5］的需要，提出了逆向D*算法。

1.2 设计流程

逆向D*算法的设计流程如下:

1)采用栅格环境建模法对机器人行进中传感器所感知到的前方信息建立局部环境地图，对障碍物栅格进行预膨胀，以保证机器人和障碍物有一定的安全膨胀距离。通过膨胀后，机器人可以被看成是以其参考点为中心的“点”机器人。

2)设置机器人从起点S(xs，ys)到目标点G(xg，yg)运动过程中所经历的目标势能最小值Emin。假设自由栅格坐标点I(xi，yi)的势能为，则在滚动优化过程中，机器人要以其当前位置R 为中心，向外寻找目标势能小于Emin-ε(ε ＞0，为常数项)的中间栅格节点I。而此栅格节点I 应该满足

3)在搜索中间栅格节点I 过程中，以A*方法建立确定搜索优先度的估计函数f(i)。其中，被搜索点I 的估价函数f(i)=g(i)+h(i)。而与D*算法不同的是，g(i)是从机器人当前位置R 到搜索栅格节点I 的实际代价，即机器人距离，h(i)是搜索栅格节点I 到目标节点G 的估计代价。

4)在被搜索的区域里，机器人距离g(i)被记录在栅格位图中，当搜索到满足上述条件的I 节点后，从节点I 出发，按照机器人距离g(i)减少的梯度方向，回溯到当前机器人位置R，而该回溯的逆向过程就是从机器人当前位置R 到达中间目标I 的路径。

5)机器人从起点出发，通过不断地采用A*方法搜索中间目标I 来实现滚动的动态路径规划。

2 环境地图的表示

无论采用哪种路径规划算法，都需要知道机器人所在的自身环境，包括机器人自身的位置、障碍物的位置、路标以及目标的位置等，这样机器人才能搜索到达目的地位置的行走路径，以便更好地完成任务。而如何对环境建立模型，就成了路径规划的基本前提。目前，建立环境模型的方法主要有几何建模法、拓扑建模法以及栅格地图建模法［1］。针对不同的路径规划需要不同的建模方法，由于栅格地图很容易创建和维护，故本文所述的逆向D*算法所采用的环境表示方法是栅格地图环境建模法。

栅格地图就是将整个工作环境分为若干相同大小的栅格，对于每个栅格指出其是否存在障碍物。机器人所了解的每个栅格的信息直接与环境中某区域对应，环境被表示成离散栅格，栅格“0”表示为可通行的栅格，栅格“1”表示为障碍物栅格。本文所建立的环境地图如图1 所示。栅格范围为20 ×20 方格，栅格单元尺寸为0.5 m，黑色方格为膨胀后的障碍物栅格，空白栅格为可通行栅格。

图1 环境栅格地图

3 算法流程

本文所设计的自主车辆路径规划仿真流程如图2 所示。

4 实验结果与结论

为了说明逆向D*算法在自主车辆路径规划中应用的可行性及有效性，采用图1 所示的环境栅格地图，以最短距离和最短计算量作为路径规划的优化性能指标，利用matlab 进行自主车辆逆向D*算法的实验仿真。为了说明逆向D*算法的优越性，还与D*算法的仿真结果进行了比较和分析。实验的硬件配置:处理器为Pentium(R)Dual-Core CPU E5500 2.8 GHz;内存为2 GB。

本实验中，自主车辆从起始点S(3，3)出发，预计行驶到目标点G(18，18)，以完成路径规划任务。起始点和目标点在栅格地图中的位置如图3 所示。实验中还设定自主车辆传感器所能探测到的局部环境栅格地图范围为6 ×6 方格，而估价函数中的机器人距离g(i)为欧几里德距离。

图2 算法流程

图3 起始点和目标点位置示意图

逆向D*算法的仿真结果如图4 ～图6 所示。自主车辆在行进过程中，总共搜索到2 个中间节点，分别是L1和L2，图4 ～图6 分别表示起始点S 到中间节点L1、中间节点L1到中间节点L2、中间节点L2到目标点G 的规划结果，栅格位图中的数字表示机器人距离g(i)。同等实验条件下，D*算法的仿真结果如图5 所示。

图4 逆向D* 算法路径规划(1)

图5 逆向D* 算法路径规划(2)

图6 逆向D* 算法路径规划(3)

图7 D* 算法路径规划

以上实验结果说明，逆向D*算法与D*算法规划出的路径一样，都是最短的安全行驶路径，但逆向D*算法在路径规划过程中，3 次累计需要计算的机器人距离g(i)次数比D*算法需要计算的机器人距离g(i)次数要少3 倍以上，这样大大减少了计算量，提高路径规划执行的效率。

5 结束语

本文讨论了自主车辆的路径规划，分析了逆向D*路径规划算法的原理以及基本流程，利用仿真实验验证了其有效性，并与D*路径规划算法做分析比较，验证了该算法能大大提高路径规划的执行效率。

［1］朱大奇，颜明重. 移动机器人路径规划技术研究概述［J］.控制与决策，2010，25(7):962-967.

［2］刘亮.自主移动机器人的路径规划与避障研究［D］.武汉:武汉京理工大学，2007.

［3］刘进. 自主式移动机器人控制系统与路径规划研究［D］.青岛:青岛大学，2009.

［4］张毅，罗元，郑太雄.移动机器人技术及其应用［M］.北京:电子工业出版社，2007.

［5］张纯刚，席裕庚.全局环境未知时基于滚动窗口的机器人路径规划［J］.中国科学(E 辑)，2001，31(2):51-57.

［6］黄鹤.部分环境信息已知的智能机器人路径规划方法研究［D］.南京:南京理工大学，2005.

［7］张亮，周继宝. 基于遗传算法的后勤运输车路径规划［J］.四川兵工学报，2012(2):81-83.