魏武 韩进 李艳杰 高天啸

(华南理工大学 自动化科学与工程学院，广东 广州 510640)

近几十年来，路径规划问题的研究在机器人领域兴起并成为研究的热点[1- 2]。路径规划问题就是在环境完全已知或部分已知的前提下寻找一条与障碍物无碰撞的路径。环境完全已知的路径规划问题为全局路径规划，环境部分已知的路径规划问题为局部路径规划。路径规划算法主要包括基于采样的方法[3- 4]、人工势场法[5]、可视图法[6]、生物智能算法[7- 9]和基于深度学习的方法[10]，其中基于采样的方法以概率路图法(PRM)[3]和快速扩展随机树(RRT)[4]为代表，生物智能算法的典型代表为遗传算法[7]和蚁群算法[8- 9]。

基于采样的路径规划方法具有强大的搜索能力，将规划算法从几何学模型中分离[2]，在探索高维空间方面具有突出的表现。因此，众多学者展开了相关研究，其中RRT算法[4]引起了高度关注并得到了较为广泛的应用[10- 12]。RRT算法虽然具有概率完备性[13]和计算量小的优点，但RRT算法本身不考虑所获得的路径代价，故无法保证路径的质量[14]，即不具备渐进最优性的特性，而这一特性对于实际应用尤为重要。

为了加快RRT算法寻找路径的速度，文献[13]提出了双向RRT算法，与基本的RRT算法最大的不同在于，双向RRT算法同时存储从起点、终点处生成的两棵随机树而不是仅有一棵树。在计算资源充足的前提下，双向RRT算法的多树思想为加快收敛速度提供了一个新的思路。针对RRT算法不具备渐进最优性的缺点，大量学者基于RRT算法提出了相应的改进算法。……