移动机器人路径规划方法

顾冬雷 李晓格 王硕

（1 南京模拟技术研究所，南京，210016; 2中国科学院自动化研究所，北京，100190）

0 引言

近年来，勘察、目标获取、搜索与援救、监督、环境监测等方面广泛的应用需求使移动机器人技术得到快速发展。其中，导航技术是移动机器人研究的核心技术之一，而路径规划是导航的基本环节。

机器人路径规划的基本思想是依据某种性能指标（如时间最短、能量最少、路径最短等），寻找一条从起始点到目标点的无碰撞最优或近似最优的路径[1]。本文从全局规划和局部规划两个方面对一些路径规划常用算法进行介绍。

1 全局路径规划方法

全局路径规划是在作业环境中，基于先验模型规划从起始点到目标点的路径，也称为静态路径规划，主要包括可视图法、栅格解耦法、概率路径图法、拓扑法、神经网络法等。

1.1 可视图法

可视图法利用机器人的最短路径是擦着多边形障碍物的顶点的思想，将机器人看成一个点，把起始点、目标点和多边形障碍物的所有顶点用线段连接起来，同时删除穿过障碍物的线组成可视图，再搜索最短路径[2]。该方法应用于二维路径规划问题中，则是能在O(N2)的时间内完成最短路径搜索，其中N为障碍物的数量（下同）。

可视图法没有考虑到机器人本身的形状、大小，易造成与障碍物的碰撞，同时随着障碍物的增多，或障碍物的不规则性而导致图中的顶点集过大，计算复杂性增加，搜索时间长。可视图法最初由斯坦福大学的Nilsson提出，Kuwata和How[3]将该方法推广到三维情形，障碍物用多面体表示，得到的路径不一定是最优的。

1.2 Voronoi图法

Voronoi图法的基本思想是首先产生与障碍物多边形所有的边等距离的Voronoi边，并将所有Voronoi边的交点组成顶点集；再通过与可视图类似的搜索最短路径边的方法来规划路径。

Voronoi图法的时间复杂度为O(NlogN)，能够保证机器人以最大的安全度到达目标，但却导致机器人到目标位置的路径增长，从而不是最优的路径。这是一个二维算法，肖秦琨等研究了三维空间Voronoi图法[4]，Choset 和Burdick将其推广到多维空间并进行了改进[5]。

1.3 栅格解耦法

栅格解耦法是目前应用最广泛的路径规划方法。该方法将环境空间解耦成一系列相互连接但不重叠的网格单元，从而得到一个连通图，每个栅格都被赋予一个累积值，用来描述该栅格中存在障碍物的可信度，累积值越高则存在障碍物的可能性越大，最后通过优化算法来搜索栅格中的最短连通路径。

栅格划分的方法可以分为精确栅格解耦法和近似栅格解耦法[6]。精确栅格解耦法将自由空间划分成小的凸多边形或凸多面体，得到的环境空间与原环境空间精确相等。常见的精确栅格解耦法有梯形栅格解耦法，时间复杂性为O(NlogN)，不是最优解；临界曲线栅格解耦法，时间复杂度为O(N2logN)，得到的也不是最优解。近似栅格解耦法有矩形栅格解耦法和2m叉树栅格解耦法 （四叉树、八叉树[7]）等。栅格法在三维路径规划中也有应用[8-9]，小波变换法、多分辨率方法等常用于栅格算法的改进[10-11]。

可视图法、Voronoi图法和栅格解耦法都是把区域划分成不同的网格空间，找到机器人可达的网格（节点）以及网格间联系（边），构成满足一定拓扑结构的图[10]，因此，A*算法[11]、Dijkstra算法、宽度优先、深度优先搜索算法等常用于解决图搜索问题，且算法的效率与存储图的数据结构存在一定的关系。

1.4 概率路径图法（PRM）

概率路径图法最初由Kavraki等[12]提出，是一种基于采样的规划方法，与传统方法的不同，它以某种概率来构建图。PRM算法概率完备并且收敛，但不是近似最优，与空间维数和复杂度无关。Karaman和Frazzoli系统地分析并改善了基于采样的PRM算法[13]。此外，Bohlin和Kavraki解决了狭长通道内PRM算法不易收敛的问题[14]。

1.5 拓扑法

拓扑法基本思想是将环境空间分割成若干个具有拓扑特征的子空间，并根据子空间的联通性建立拓扑网络。在此拓扑网络上，机器人搜索到目标位置的拓扑路径，再通过拓扑路径来计算几何路径，完成路径规划的任务。

拓扑法主要使用降维法，将高维空间中的求路径问题转化为低维拓扑空间的连通性判别问题。拓扑法的优势是利用拓扑特征缩小搜索空间，提高了搜索效率。但算法中空间划分及拓扑网络建立的复杂程度随障碍物的数目增多而增大。对于结构简单的拓扑网络，一般可采用宽度优先、深度优先算法，复杂网络则多采用A*算法、S*算法等。

1.6 神经网络法

神经网络方法应用于机器人路径规划中，通过定义整条路径的总能量函数，利用网络结构设计和模拟退火方法等产生移动路径点，使其朝着能量减少的方向运动，最终获得总能量最小的路径。神经网络方法比较灵活，可以解决可视图法不能解决的圆形障碍物问题[12]。其中，生物启发神经网络的实时性较好，大多数的神经网络由于存在学习样本难以获取的问题而存在滞后性。

2 局部路径规划方法及其他规划方法

局部规划是在作业环境中，基于对周围环境的感知进行路径规划。主要算法有人工势场法、快速扩展随机搜索树法（RRT）、模糊逻辑算法等，其他规划算法还有遗传算法、蚁群算法、粒子群算法等。

2.1 人工势场法

人工势场法最初由Khatib和Mampey[15]提出，基本思想是用一个势函数来描述机器人环境空间，机器人作为一个粒子受到势力，目标点有最低势能对机器人产生吸引力，同时障碍物对机器人产生排斥力。

人工势场法结构简单，便于底层实时控制，在实时避障和平滑的轨迹控制方面得到了广泛应用，其不足在于存在局部最优解，容易产生死锁现象，因而可能使移动机器人在到达目标点之前就停留在局部最优点。

Koren和Borenstein[16]指出虚拟力场法存在局部极小陷阱区域、在相近障碍物间找不到路径等不足。针对这些不足，出现了利用图搜索办法、调和函数及启发函数等方法[17]。

2.2 快速扩展随机搜索树法（RRT）

快速扩展随机搜索树法最初由LaValle[18]提出，先对供参考用的主题框架进行随机搜索，再扩展到通过随机采样得到的构造空间。这是一种基于采样的方法，利用了单查询机制，用于当机器人从一个环境移动到另一个环境的情形。

RRT算法可以解决环境模型的先验知识未知或者建模困难问题，可用于实时在线规划。但该方法只应用在完整约束问题中，没有考虑到动力学约束问题。

2.3 遗传算法

遗传算法是以自然遗传机制和自然选择等生物进化理论为基础的一类随机优化搜索算法。通过模拟生物进化过程中的选择、交叉和变异等机制进行搜索，可以并行执行，适用于全局搜索。

遗传算法由于是一种多点搜索算法，所以有可能搜索到全局最优解，缺点是运算速度不快，存储空间和运算时间较多。

2.4 粒子群算法

粒子群是由Kennedy[19]从鸟类捕食行为中受到启发而提出的一种基于群体的智能随机优化算法。粒子群算法具有收敛速度快、参数设置简单、算法简单、容易编程实现和鲁棒性强等特点，但是容易陷入局部极值点，而且对参数设置依赖性比较高。

2.5 模糊逻辑算法

模糊逻辑是二值逻辑的推广，是对经典的二值逻辑的模糊化。利用模糊逻辑进行路径规划，能够一定程度上处理局部极小问题，同时通过对环境信息的模糊化，可降低对移动机器人定位精度的要求。

由于模糊逻辑算法依据的是经验，但经验不一定准确，这是该方法的缺陷。此外，模糊隶属度函数、控制规则的设计也是其中需要重点考虑的问题。

2.6 蚁群算法

Colorni, Dorigo等[20]提出了一种可并行计算、鲁棒的模拟进化算法——蚁群算法，该方法具有较好的最优解发现能力，在路径规划中有一定的应用。但是，蚁群算法用于机器人路径规划时，存在算法耗时、容易出现停滞现象、收敛慢等问题。

2.7 其他算法

除了上面提到的方法，还有很多其他规划方法，如模型预测方法或滚动优化法（RHC）和线性规划方法等基于数学优化的方法、启发式算法、基于反应式规划的方法、慎思规划、全局与局部路径规划相结合的方法、针对不确定性动态环境的路径规划方法等。

3 总结

随着智能移动机器人应用的快速增长，移动机器人导航技术中的路径规划方法也越来越多被关注，并获得应用。本文对机器人路径规划的主要方法进行了归纳介绍。

在规划方法的实际应用中，全局规划和局部规划相结合是一个比较合理的策略。规划方法的选取应依据机器人的实际计算能力、实时性要求、外部环境等因素综合考虑，以满足实际应用需求。

至谢

感谢国家科技支撑计划（No.2013BAK03B00）对本项目的资助。

[1]Li L, Ye T, Tan M, et al. Present State and Future Development of Mobile Robot Technology Research[J]. Robot, 2002, 24(5): 475-480.

[2]Goerzen C, Kong Z, Mettler B. A Survey of Motion Planning Algorithms from the Perspective of Autonomous UAV Guidance[J]. Journal of Intelligent and Robotic Systems, 2010, 57(1-4): 65-100.

[3]Kuwata Y, How J. Three Dimensional Receding Horizon Control for UAVs[C]. AIAA Guidance, Navigation, and Control Conference and Exhibit. 2004: 2100-2113.

[4]肖秦琨, 高晓光. 基于空间改进型 Voronoi 图的路径规划研究[J]. 自然科学进展, 2006, 16(2): 232-237.

[5]Choset H, Burdick J. Sensor-based Exploration: The Hierarchical Generalized Voronoi Graph[J]. The International Journal of Robotics Research, 2000, 19(2): 96-125.

[6]Cai C, Ferrari S. Information-driven Sensor Path Planning by Approximate Cell Decomposition[J]. IEEE Transactions on Systems, Man, and Cybernetics - Part B: Cybernetics, 2009, 39(3): 672-689.

[7]Cocaud C, Jnifene A, Kim B. Environment Mapping Using Hybrid Octree Knowledge for UAV Trajectory Planning[J]. Canadian Journal of Remote Sensing, 2008, 34(4): 405-417.

[8]Williams M, Jones D I. A Rapid Method for Planning Paths in Three Dimensions for a Small Aerial Robot[J]. Robotica, 2001, 19(2): 125-135.

[9]Tsenkov P, Howlett J K, Whalley M, et al. A System for 3d Autonomous Rotorcraft Navigation in Urban Environments[C]. AIAA Guidance, Navigation and Control Conference and Exhibit, Honolulu, HI. 2008.

[10]LaValle S M. Robot Motion Planning: A Game-theoretic Foundation[J]. Algorithmica, 2000, 26(3-4): 430-465.

[11]Dechter R, Pearl J. Generalized best-1st Search Strategies and the Optimality of A*[J]. Journal of the ACM, 1985, 32(3): 505-536.

[12]Kavraki L E, Svestka P, Latombe J C, et al. Probabilistic Roadmaps for Path Planning in High-dimensional Configuration Spaces[J]. IEEE Transactions on Robotics and Automation , 1996, 12(4): 566-580.

[13]Karaman S, Frazzoli E. Sampling-based Algorithms for Optimal Motion Planning[J]. The International Journal of Robotics Research, 2011, 30(7): 846-894.

[14]Bohlin R, Kavraki E E. Path planning using lazy PRM[C]. IEEE International Conference on Robotics and Automation, 2000: 521-528.

[15]Khatib O, Mampey L M. Fonction D é cision-Commande d'un Robot Manipulateur [R]. DERA-CERT, Toulouse, France, 1978, 2(7): 156.

[16]Koren Y, Borenstein J. Potential Field Methods and Their Inherent Limitations for Mobile Robot Navigation[C]. IEEE International Conference on Robotics and Automation, 1991: 1398-1404.

[17]Zelek J S. Dynamic Path Planning[C]. IEEE International Conference on Systems, Man and Cybernetics, 1995: 1285-1290.

[18]LaValle S M. Rapidly-Exploring Random Trees: A New Tool for Path Planning[R]. Technical Report TR 98-11, Computer Science Deptartment, Iowa State University, 1998.

[19]Poli R, Kennedy J, Blackwell T. Particle Swarm Optimization[J]. Swarm Intelligence, 2007, 1(1): 33-57.

[20]Colorni A, Dorigo M, Maniezzo V. Distributed Optimization by Ant Colonies[C]. Proceedings of the First European Conference on Artificial Life, 1991: 134-142.