基于双重A*算法的移动机器人动态环境路径规划

陈伟华，林 颖，文宗明，缪丹云

(华南理工大学广州学院 机械工程学院，广州 510800)

0 引言

移动机器人路径规划是导航中的关键技术之一，是机器人技术领域研究的重点和热点。移动机器人路径规划是指在有障碍物的环境中为机器人规划出一条从起始点到目标点的最优或者次优安全无碰撞路径[1-6]。路径规划问题通常存在环境信息量大、障碍物多等约束，其已被证明是非确定性多项式困难问题[7]。路径规划问题一直以来都是移动机器人研究的热点和难点[8-9]。

A*算法在机器人全局路径寻优和规划方面应用非常广泛。A*算法是一种经典的启发式搜索算法，并广泛应用于路径搜索问题中。A*算法是一类适用于全局环境信息已知的路径规划方法，同时也适用于路径的二次规划[6]。但是在动态环境中，移动机器人运动过程会遇到障碍物，则其运动路径需要重新规划。重新规划的算法很多，比如遗传算法、蚁群算法、增强学习算法等，每个算法都有其优缺点，其中实时性是算法的缺点之一。为解决环境信息局部变动情况下路径规划问题，并且减少路径规划时间，提高移动机器人运动的实时性，提出了基于双重A*算法的路径规划方法，即采用A*算法分别进行全局路径规划和局部路径规划。首先在移动机器人运动前，在全局环境信息已知的条件下进行全局最优路径规划；接着，机器人沿着全局规划的路径运动，当在前进的路径上出现障碍物，则再一次采用A*算法进行局部路径规划，局部区域比全局区域小很多，能减小路径规划时间，提高机器人运动的实时性，使移动机器人的运动路径全局最优和局部最优兼并，并使机器人能在动态环境中安全无碰撞运动。

1 基于双重A*算法的路径规划

1.1 A*算法原理

A*算法在人工智能中是一种典型的启发式搜索算法(Heuristic Search Algorithm)，是一种静态路径规划求解最短路径最有效的方法，其基本公式如下[10]：

f(n) =g(n) +h(n)

(1)

其中，f(n)为节点n的估价函数，g(n)为在状态空间中从初始节点到n节点的实际代价，h(n)为从n节点到目标节点最优路径的估计代价。

图1 A*算法进行全局路径规划的路径

估价函数的正确选取将直接关系到A*算法的成功与否，而函数的确定却与实际情形有着密切的关系。所以选择的估价函数好坏是很重要的，一个不恰当的启发式函数反而会减慢A*算法，导致其产生出不好的路径[10]。本文取两节点间的曼哈顿距离作为估价值，即h(n)=abs(dx-sx)+abs(dy-sy)，(sx，sy)为当前节点坐标，(dx，dy)为目标节点的坐标。g(n)表示沿路径从初始节点到当前节点n的移动消耗成本，令水平和垂直移动的消耗成本为1，对角线方向的消耗成本为1.4。见图1，已知全局环境的栅格地图(27行×26列格子)，机器人或障碍物在栅格地图中的位置用它们所占格子在栅格地图中的行号和列号表示，即(行号，列号)表示位置坐标(x，y)，则图片的左上角的第一个格子位置为(1，1)，右下角的最后一个格子的位置为(27，26)。设机器人的初始点位置为(4，22)，目标点位置为(18，2)，如图1所示，采用A*算法进行全局路径规划，得到如图1中所示的路径。移动机器人沿着路径从初始点运动到目标点消耗的成本为26.8。

1．2 基于双重A*算法的路径规划原理

图2 基于双重A*算法的路径规划流程图

双重A*算法指的是全局A*算法和局部A*算法相结合。移动机器人路径规划中，当已知运动环境的栅格地图、移动机器人运动的起点和目标点位置，则可采用A*算法进行全局最优的路径规划(见图1)。但在运动过程中，移动机器人会碰到一些静止或动态的障碍物，这时需要进行局部路径规划，局部路径规划中再一次采用A*算法。基于双重A*算法的路径规划流程图如图2所示。

基于双重A*算法的路径规划步骤如下：

(1)已知运动环境的栅格地图，移动机器人运动起点位置，需要到达的目标点位置，运动前先采用A*算法规划出全局的运动路径(见图1)。

(2)移动机器人按第(1)步规划出的全局运动路径开始运动，当在运动路径中出现障碍物时，移动机器人则进行局部规划：当障碍物为静止时则转到第(3)步，当障碍物为动态时则转到第(4)步。

(3)当移动机器人前面运动路径上出现静止障碍物时，则移动机器人在局部范围内采用A*算法进行路径规划。如图3所示，静止障碍物在地图上占有四个格子，位置为(9，16)、(9，17)、(10，16)和(10，17)，局部规划区域为图中方框的范围，局部路径规划的局部起点为移动机器人当前点其位置为(8，18)，局部目标点为越过障碍物沿着靠近全局目标点方向的全局运动路径上的一点其位置为(11，15)，在局部区域采用A*算法规划出来的局部路径为(8，18)-(8，17)-(8，16)-(8，15)-(9，15)-(10，15)-(11，15)。全局路径与局部路径混合则可以得到机器人运动的路径。

图3 障碍物为静止物体的规划路径

(4)当移动机器人前面运动路径上出现动态障碍物时，根据动态障碍物运动方向进行不同的路径规划：①当动态障碍物运动方向与移动机器人运动方向相同，则机器人慢速与障碍物保持一定距离进行跟随运动。②当动态障碍物运动方向相对移动机器人运动方向是侧向穿越，则机器人减速运动到离障碍物一定安全距离的地方停止，等待障碍物穿越完成机器人再继续向前运动。③当动态障碍物(如图4(1)中(19，12)，图4(2)中(17，12)，图4(3)中(16，12)，图4(4)中(14，12)，图4(5)中(12，12)，图4(6)中(3，12)的位置)运动方向与移动机器人运动方向相反，则移动机器人实时进行局部路径规划，直至障碍物消失在移动机器人前进的局部路径范围内或者障碍物不在机器人前进运动路径上，如图4运动顺序图所示。图4中位置(15，12)为局部路径规划的局部起点，位置(17，11)为局部目标点，局部路径为(15，12)-(15，13)-(16，13)-(17，13)-(17，12)-(17，11)。

图4 障碍物为运动物体的规划路径

1.3 局部规划区域的确定

当移动机器人运动过程中遇到障碍物时需要进行局部路径规划，局部规划区域的确定如下：当移动机器人运动的下一步有障碍物时，记下移动机器人当前点的位置，检测障碍物占有前进运动路径的格子数n(如图3中n=2)，设s=n+6，如果s为偶数，则s=n+7。①当下一步的障碍物所占格子(如图5中黑色格子)在机器人当前点(如图5a中第8行第4列格子)所占格子的正上方，则局部规划区域格子数为(s+1)*s，如图5a的第2行到第9行的方框所示。②当下一步的障碍物所占格子在机器人当前点(如图5b中第3行第4列的格子)所占格子的正下方，则局部规划区域格子数为(s+1)*s，如图5b的第2行到第9行的方框所示。③当下一步的障碍物所占格子在机器人当前点(如图5c中第6行第9列的格子)所占格子的左方，则局部规划区域格子数为s*(s+1)，如图5c的第2行到第10行的方框所示。④当下一步的障碍物所占格子在机器人当前点(如图5d中第6行第2列的格子)所占格子的右方，则局部规划区域格子数为s*(s+1)，如图5d的第3行到第9行的方框所示。图5中除了表示机器人当前点的另一个灰色格子为局部规划区域内的目标点位置，它也是全局路径中的一点。

图5 局部规划区域

2 仿真分析

为了验证本文所提出的方法可行，对机器人在动态环境中运动过程遇到的几种情况(静止的障碍物，同向运动的障碍物，侧向穿过的障碍物，反向运动的障碍物)进行仿真。仿真软件为Matlab2013b，仿真的环境为(27×0.5)m×(26×0.5)m的长方形栅格地图，每小格的尺寸为0.5 m ×0.5 m，一共27×26个格子，如图6所示。设机器人的初始位置为(4，22)，目标点为(26，13)，坐标以格子位置的行号和列号表示，如初始位置(4，22)为在第4行第22列格子的位置，本文下面的坐标表示一样。当没有障碍物时，机器人从起点到达目标点，使用A*算法得到如图7所示的运动路径。当在运动过程中分别遇到四个障碍物：①静止的障碍物((9，16)、(9，17)、(10，16)和(10，17)四个格子表示)；②同向运动的障碍物(图8(1)中(16，13)所示)；③侧向穿过的障碍物(图8(2)中(19，12)所示)；④反向运动的障碍物(图8(3)中(18，13)所示)。使用本文提出的方法则机器人的运动路径顺序图如图8所示。

图6 仿真环境的栅格地图

图7 没障碍物情况的运动路径

图8 机器人的运动路径顺序图

从图8可知，当移动机器人遇到第一个障碍物(静止的障碍物)时，机器人将进行局部路径规划，局部规划区域如图5c所示，为9×10个格子范围；当遇到第二个障碍物(同向运动的障碍物)时，机器人将进行跟随运动；当遇到第三个障碍物(侧向穿过的障碍物)时，机器人等待障碍物穿越完成再继续运动；当遇到第四个障碍物(反向运动的障碍物)时，机器人将进行局部路径规划，局部规划区域如图5b所示，为8×7个格子范围。从仿真结果可知：①移动机器人在动态环境中能安全避障。②移动机器人运动前进行了一次A*算法全局路径规划和运动过程中进行了两次A*算法局部路径规划，局部规划区域分别为9×10个格子范围和8×7个格子范围，它们与全局规划区域(27×26个格子范围)相比，局部规划区域小很多，则可以说明局部规划时间比全局规划时间小。③局部规划时间减小可以提高移动机器人运动的实时性。

3 结论

基于双重A*算法的移动机器人路径规划方法能让移动机器人在动态环境中安全无碰撞运动，并且在环境信息局部变动情况下重新规划运动路径的时间减小，提高机器人运动的实时性。本文提出的方法是采用A*算法分别进行全局路径规划和局部路径规划。全局路径规划为机器人运动前根据已知起点位置，目标点位置和全局运动环境的栅格地图，采用A*算法进行全局路径最优规划。局部路径规划为移动机器人在运动过程中遇到障碍物时，首先根据障碍物的运动特点，确定局部规划区域，局部规划的起点位置和目标点位置，然后采用A*算法在局部规划区域进行局部最优路径规划。全局路径与局部路径混合则为移动机器人的运动路径，该路径能让移动机器人在动态环境中安全无碰撞并且全局最优和局部最优兼并。并且，由于局部路径规划范围比全局路径规划范围小，则局部路径规划时间小，能减小总体的路径规划时间，提高机器人运动的实时性。

[参考文献]

[1] 陆新华，张桂林．室内服务机器人导航方法研究[J]．机器人，2003，25(1)：80-87．

[2] 黄玉清，梁靓．机器人导航系统中的路径规划算法[J]．微计算机信息，2006，22(7)：259-261.

[3] 黄健生．移动机器人的路径规划研究[D]．杭州：浙江大学，2008．

[4] 王殿君. 基于改进A*算法的室内移动机器人路径规划[J]. 清华大学学报(自然科学版)，2012，52(8)：1085-1089.

[5] 王红卫，马勇，谢勇，等. 基于平滑A*算法的移动机器人路径规划[J]. 同济大学学报(自然科学版)，2010， 38(11): 1647-1650.

[6] 秦玉鑫，王红旗，杜翠杰. 基于双层A*算法的移动机器人路径规划[J]. 制造业自动化，2014，36(12)：21-25.

[7] HUNAG Biao, Kadali R. Dynamic modeling, predictive control and performance monitoring (a data-driven subspace approach) [M]. London: Springer, 2008.

[8] 曲道奎，杜振军，徐殿国，等.移动机器人路径规划方法研究[J].机器人，2008，30(2)：97-101，106.

[9] 邬再新, 李艳宏, 刘涛, 等. 动态环境中多移动机器人路径规划的一种新方法[J]. 组合机床与自动化加工技术，2008(3)：25-27.

[10]王殿君，魏洪兴，任福君. 移动机器人自主定位技术[M]. 北京：机械工业出版社，2013.

(编辑李秀敏)