移动机器人路径规划中的图方法应用综述

A Survey of Mobile Robots Path Planning Using Geometric Methods

近40年中,涌现出很多移动机器人路径规划算法,其中大部分算法将环境信息几何化,转换成图的问题,利用图的方法解决。这些算法可分成三类:具有较好完备性适用于低维姿态空间的几何构造的方法、完备性较差或只具有概率完备但适用高维姿态空间的随机规划方法,以及常用的图搜索算法。对这些算法进行了归纳总结,评价了各算法的性能差异和优缺点。最后,探讨了移动机器人路径规划的发展趋势,给出图方法在路径规划中未来的应用展望。

In recent forty years, a lot of path planning algorithms for mobile robot have been proposed. Majority of them translates environment geometric information into graph and then solve the problems using graph theory. They are classified into three categories： geometry construction methods in 2D and 3D configuration space with good completeness, randomized planning methods, and graph search algorithms. This survey tries to summarize these planning algorithms and point out the advantages and disadvantages of them. Finally, the future of mobile robot path planning is discussed.