移动机器人路径规划综述

(西安工业大学 电子信息工程学院，西安 710021)

0 引言

路径规划是机器人研究的核心内容之一，近年来在很多领域都具有广泛的应用，如室内服务机器人的自主运动[1]；无人机的避障突防飞行[2]；物流管理中的车辆问题[3]及类似的资源管理、资源配置问题。机器人的路径规划按照“感知-建模-规划-执行”的过程依次进行。首先机器人用自身携带的传感器感知环境，对环境形成两类信息，一类是静态的长期信息反映环境中静态障碍物的分布，另一类是动态的短期信息反映环境中动态障碍物的分布。然后选择合适的建模方法对整个工作空间建立一个便于计算机进行路径规划的环境模型，即将实际的物理空间抽象成算法能够处理的抽象空间[4]。接下来根据已有的长期信息和在运动过程中感知到的动态障碍物，依据最低耗损原则规划出最优化路线，使预定的性能函数获得最优值。最后执行系统执行该条线路，使得机器人无碰撞的安全到达目标点[5-9]。

本文重点对全局路径规划和局部路径规划进行了总结与评价，全局路径规划注重寻求最优解，局部路径规划注重避障，同时介绍了基于仿生学的算法，最后对移动机器人路径规划的未来发展趋势进行了展望。

1 全局路径规划方法

1.1 栅格法

栅格法将工作空间解耦为多个简单的区域，建立一个便于计算机进行路径规划的环境模型，即将实际的物理空间抽象成算法能够处理的抽象空间，实现相互间的映射。每个栅格点或者在自由空间中，用“0”表示，或者在障碍物空间中，用“1”表示，通过搜索栅格图找到一条从起始栅格到目标栅格的最短路径[10-12]。若栅格较小，环境信息将会非常清晰，但会需要存储较多的信息，规划速度降低，实时性得不到保证；若栅格较大，信息存储量将会少，规划速度加快，但环境信息划分会变得模糊，不利于有效路径的规划，所以需要在地图网格分辨率与路径规划实时性上寻求平衡。

栅格法是公认的最成熟的算法，也是安全系数最高的算法，直观明了，常与其他方法集成使用，但方法受制于传感器，消耗过多运算资源。郑秀敏[13]等人采用栅格法表示环境，局部路径规划基于模拟退火法，用模拟退火法摆脱局部极小值，达到全局最优，同时也对模拟退火法进行了改进；于红斌[14]等人在栅格法的基础上，在结点中加入记忆力，修改两个结点之间的关联程度，形成正反馈机制，最终得到一条最优路径，该算法在静态路径规划中切实可行，并且搜索效率高于遗传算法，但参数是依据经验值确定的，普遍性不高；朱磊[15]等人针对发生矿难的井下环境，采用栅格法建模，改进的负反馈遗传算法规划全局路径，并以全局规划的结果为基础，设计了基于自由栅格和障碍栅格的相互转换的局部避障方法，该方法具有较强鲁棒性；王曙光[16]等人提出实时栅格法将其应用于多机器人协作建立空间地图，通过机器人的编队在探索环境中直接完成环境建模，不再局限于单个机器人各自划分一个小区域，栅格也不再局限于正方形，实时栅格法检测障碍计算简单，不需要进行局部地图的拼接，但在实际情况下，由于地形起伏的环境因素，队形会出现偏差，造成栅格位置的误差，影响检测结果。

1.2 A*算法

A*算法是一种在工作空间中求解最短路径搜索方法，它将启发式函数BFS和常规方法Dijkstra算法结合在一起[17-20]，在进行启发式搜索提高效率的同时，可以保证找到一条最优路径。代价函数定义为f(m)=g(m)+h(m)。其中f(m)是从初始点S经由中间点M到目标点E的代价估计，g(m)是初始点S到达中间点M的实际距离，h(m)是是中间点M到目标点E的估计距离，它是一种启发式函数，评估任意结点到目标点的代价，快速地导向目标结点，省略大量无效的搜索节点。

A*算法能快速实现移动机器人的无碰最短路径规划，主要的计算量在于对节点状态的检测和最小代价的选择[21]。Dan[22]等将A*算法用于对随机语法进行解析，通过与各种算法的比较，可以看出A*算法大大减少了找到解析所需的时间，并且能给出最佳的、准确的解析；Kagan[23]等将A*算法用于在离散空间中在线搜寻特定信息，启发函数定义为搜索空间上信息距离，该算法具有较强的收敛性，获得的结果可以用于弥补信息理论搜索过程的不足；由于算法本身原理的限制，规划出的路径折线多、转折次数多、累积转折角度大，王红卫[24]等人提出平滑A*算法，取出相邻的3个节点，当某一节点前后节点连线上无障碍物时，删除中间节点，该算法优化了路径，减少了路径长度，降低了转折次数；A*算法规划出的路径曲率非连续，导致在转折点处运动参量发生跳变，王殿君[25]在平滑A*算法基础上加入了在拐点处调整自身位姿，更好实现自主定位功能，但两者需要在A*算法规划好的基础上平滑路径，增加了运行时间，实时性不高，寻路效率不高；规划的场景较大时，往往由于庞大的计算量导致运行时间过长、内存占用严重，赵晓[26]等人在A*算法的基础上，结合跳点搜索算法将添加到OpenList和ClosedList的不必要节点用跳点代替，减少了算法的覆盖面，大大加快了寻路速度，但规划出来的路径转折点较多，不利于机器人直接执行；王小红[27]等人提出对邻域进行扩展，将8邻域扩展到24邻域，使得机器人可以小角度行进，从而轨迹更加平滑，并且将启发式函数不再单一的选择曼哈顿距或者欧几里得距离，将其进行融合以适应具体环境，使得A*算法更加灵活，规划出来的转折点少，同时全局路径更加平滑。

2 局部路径规划算法

2.1 人工势场法

人工势场是抽象的人造受力场，其中目标点产生“引力”，障碍物产生“斥力”，最后通过求合力来控制移动机器人的运动[28-30]。人工势场法主要用于局部环境中躲避动态避障物，此时的引力极是局部环境中的中间目标，斥力极则是局部环境中的障碍物。该方法结构简单，便于底层的实时控制。但其存在局部极值点，易在狭窄的通道中摆动，当临近目标点的地方存在障碍物时不能发现路径等问题[31-32]。

Borenstein[33]等人提出了基于向量场直方图方法的VFH算法，对人工势场方法进行了改进，机器人可在多障碍物环境或狭窄通道中找出局部较优的路径，且运行轨迹合理。但是，此方法将机器人理想化为一个点，没有考虑机器人的尺寸、动力学和运动学特性，这使得机器人很难按照VFH算法计算出来的预定轨线移动；Iwan[34]等人充分考虑机器人的尺寸、轨迹和运动学性能，提出了改进的VFH+方法，但只是一种纯局部避障算法，容易在多个障碍物中迷失方向；之后他们加入了接下来几个周期机器人的位置和周围环境的关系的预测，在几个可能方向角之间进行优化选择，提出了VFH*[35]算法，使得机器人能够选择一个局部较优的方向，但本质上仍然是局部避障算法，没有考虑到周围障碍物的速度，选择出的运动方向有可能不是最优的，章苏书[36]提出可VFH#算法，考虑了障碍物的速度，并预测了机器人沿某方向前进会遇到的环境，使得机器人能找到最优最安全的运动方向；S.S.Ge[37]等首次提出人工势场法在临近目标点存在障碍物不可达问题，然后将机器人与目标点的距离考虑到斥势场函数中，保证目标点为全局最小点；唐志荣[38]等人将道路边界势能场考虑在内引入道路边界斥力场模型，利用椭圆化距离代替传统斥力势场中的实际距离，从而在较小车道空间获得汽车避障局部路径，保证汽车在避障过程中具有良好的稳定性和舒适性。

2.2 动态窗口法DWA

动态窗口法DWA是在曲率速度法[39]的基础上提出的，将机器人的位置控制转化为速度控制，将避障问题描述为速度空间带约束的优化问题。该算法在速度空间中采样多组速度，将有限的速度和加速度的运动约束考虑到动态窗的设计中，模拟这些速度在一定时间内的运动轨迹，再通过一个评价函数对这些轨迹打分，选择出最优的速度。充分考虑了机器人的物理限制、环境约束以及当前速度等因素，得到的路径安全可靠，适用于局部路径规划[40-43]。

Piyapat[44]等提出field Dynamic Window Approach,将动态窗口法中只涉及了机器人轨迹上的障碍物改变为不仅考虑了轨迹上的障碍物，也考虑了临近轨迹的障碍物，以避免机器人可能会撞到一些靠近轨迹但不在轨迹上的障碍物。该算法具有较好的鲁棒性，经验证在涉及近轨迹障碍物时可以更安全地行进；Pablo[45]等提出了一种称为共享控制动态窗口方法的共享控制方法。它通过控制界面接受用户命令，提供最合适的、动态可行的轨迹，并提供导航辅助，在非结构化环境中以及动态约束发挥重要作用的其他场景中驾驶车辆；程传奇等[46]将动态窗口法和改进A*算法进行融合，构造一种顾及全局最优路径的评价函数，可实时避障，路径更加平滑，曲率变化的连续性及可输出的运动控制参数更符合机器人的动力学控制；在障碍物较稠密区域，动态窗口法在穿越稠密障碍物时，存在绕行于稠密障碍物区域外侧，造成总长度增加且速度和安全性不能兼顾的问题。

3 智能方法

3.1 遗传算法

遗传算法是一种模拟自然界进化过程，搜索最优解的算法，在进化过程中进行遗传操作，如选择、交叉、变异[47-50]。选择的目的是把优化的个体直接遗传到下一代，使适应度值较好的路径具有较大的生存机会；交叉的目的是通过配对交叉产生新的路径个体，在遇到障碍物时多一种选择；变异有增加一个点，减少一个点，移动一个点以及替换一段路径，具有不确定性。

遗传算法可以同时处理多个个体，具有内在的隐并行性，且具有较高的自组织性、自适应性和自学习性。但是针对复杂环境设计相应的遗传算子存在着较大困难，经常会产生非法个体，Vincent[51]等在自主无人机上将遗传算法与粒子群算法相融合去处理在三维环境下复杂问题，产生的路径由线段，圆弧和垂直螺旋组成，通过使用“单程序，多数据”并行编程缩短执行时间，并在现成多核CPU上实现了实时性能，可以实现无人机的实时路径规划，此外遗传算法可以为粒子群算法产生出色的轨迹；陈刚等[52]设计了有效的路径遗传因子，提出了用翻越障碍物的能力替代穿越障碍物的长度的新适应度计算方法，且充分运用背景知识进行启发式变异，避免变异的盲目性，该算法有很强的鲁棒性，适合于复杂环境下的路径规划；在三维空间中随着维数的增加，传统避障方法会出现计算量的加剧增加和实时性的大幅度降低问题，陈志军等[53]采用基于模糊神经网络和遗传算法建立机器人三维路径规划，模糊神经网络建立了三维路径的五层结构，遗传算法来优化模糊神经网络，优化后的网络输出结果和期望输出结果高度吻合，具有较高的适应性。

3.2 蚁群算法

蚁群算法就是模拟蚁群觅食行为的优化算法[54-57]。蚂蚁在觅食过程中会在所经过的路径上留下信息素，并且在觅食过程中感知信息素的存在以及强度以此指导运动方向，某一路径越短，选择该路径的蚂蚁数量就越多，留下的信息素越强，被选择的机率也就越高，因此大量蚂蚁组成的集体觅食行为便表现出一种信息正反馈现象。

该算法具有分布式并行计算能力，可在全局的多点同时进行解的搜索，在求解非线性问题方面，具有高度的鲁棒性。但是目前对于有约束的函数优化问题，缺乏数学理论基础，尚无相应算法。Vahid[58]等将蚁群算法和模拟退火算法的融合，解决了无等待流水车间调度问题，改进了信息素路径更新的方式，检查搜索空间的一些不同区域并选择最佳解决方案，蚁群算法中局部搜索的新方法对于解决无等待流水车间问题是有效的；王辉[59]等引入新的距离启发函数因子于状态转移概率，并修改信息素更新规则局部更新和全局更新相结合，将此改进蚁群算法应用于泊车系统自动导引车路径规划，规划出的路径长度短，收敛迭代次数少，具有较强的全局搜索能力和较好的收敛性能；在复杂环境下蚁群算法表现出收敛速度慢，容易陷入局部最优，李龙澍等[60]通过优化初始信息素的分布解决算法初期的盲目性，在信息素的挥发中注意保留优秀路径的优势同时避免过多影响后续蚂蚁的选择，算法陷入局部最优，并通过优化概率转移规则来增加解的多样性，强化全局搜索能力；彭凡彬[61]等在群机器人路径搜索时，产生个别蚂蚁开辟的新道路，给出算法跳出局部最优解的一种可能，明显改变了传统算法的局部性调整，提高了传统蚁群的搜索能力，规划出的路径更加圆滑，方便机器人的快速行走。

3.3 粒子群算法

粒子群算法是模拟鸟群飞行的仿生算法[62-66]。鸟群在随机搜寻食物时，尽快找到食物的有效方法就是搜寻目前离食物最近的同伴位置，同伴位置在粒子群系统中为备选解，被称为一个粒子，每个粒子根据自身的经验和相邻粒子群的最佳经验向更好的位置飞行，不断迭代寻找全局最优解。

该算法为群体智能优化算法，对目标函数的性质没有要求，易于实现，鲁棒性好，在各类多维连续空间优化问题均取得良好效果，但存在过早收敛的问题，搜索性能对参数的依赖性过也过大，易于陷入局部极小值。Yilmaz[67]等采用改进粒子群优化算法来解决混合模型双侧装配线平衡问题，提出了组合选择机制和解码的新过程，增强了算法在解空间中搜索不同点的有效性；翁理国等[68]针对算法陷入局部最优时较差的搜索能力和较差的收敛速度，提出了一种改进型多目标粒子群算法，该算法引入环境选择和配对选择策略于适应度值计算方法，根据此来选择种群的个体历史最优值位置和全局历史最优值位置，采用自适应原理改变对速度权重的计算方法，以此来平衡算法的全局搜索能力与局部搜索能力，使种群粒子快速地收敛于帕累托最优边界。王学武[69]在离散粒子群算法中加入莱维飞行，增加种群多样性，很好地解决粒子群算法早熟的缺点，提高算法的寻优能力，优化效果稳定。

4 展望

4.1 多机器人协同

多机器人协同是机器人的一个必然发展趋势，不仅可以发挥个体功能，而且可以根据环境和任务的变化灵活、高效、快捷的组织多个机器人协同完成任务。在路径规划中对于未知区域地图的建立，可以让多个机器人并行的完成不同的子任务，成员之间相互交换信息，更有效和更精确地进行定位，且若单个机器人的定位错误时，不会对全局任务产生很大的影响，群体化智能使得系统的容错能力更强，可靠性更高，目前研究的热点是在火灾、地震、矿难、巡检等复杂环境中，多机器人协同搜索。

4.2 空中机器人与水下机器人研究

移动机器人现如今大多是针对地面，如扫地机器人、足球机器人，针对空中和水下机器人则比较少。空中机器人在搜寻目标、航拍摄影、农业植保方面，水下机器人在探测海底资源，搜救被困人员、维护水下管线方面都有很大的发展空间，所以这将是未来的一个热点及难点。所面临的外部环境非常恶劣，且很难利用现有的传感器获知环境信息，不确定性更大。因此，路径规划与避障更加困难和迫切。

5 结论

机器人路径规划是机器人应用中的一项重要技术，采用良好的机器人路径规划技术可以节省机器人作业时间，同时节约人力资源，减少资金投入，为机器人在多个行业的应用奠定良好的基础。将全局路径规划和局部路径规划相结合，可以在注重全局的情况下，提高机器人路径规划的避障精度，加快规划速度，满足实际应用的需要。同时多机器人协同、空中机器人与水下机器人的研究也将是研究的热点及难点问题。