余艳碧

（重庆师范大学数学科学学院，重庆 401331）

0 引言

近几年来，路径规划算法在移动机器人领域得到广泛的研究，大量经典的路径规划算法被国内外学者提出。包括基于构建虚拟势场的人工势场法［1］，基于计算智能的蚁群算法［2］、遗传算法［3］、基于图搜索的A*算法［4］，等。然而，上述算法在解决复杂多障碍环境下或高维状态空间下的路径规划问题时，搜索效率都明显降低。

基于采样的路径规划算法被提出，目的是提高算法在复杂多障碍物环境或高维状态空间下搜索能力。快速扩展随机树（RRT）［5］是当前应用最广泛的基于采样的算法，作为概率完备的快速搜索算法，RRT可以弥补上述算法搜索速度慢等缺陷。然而，由于传统的RRT算法是均匀采样的，引导信息不足，从而算法在复杂多障碍物环境下搜索的路径复杂曲折，且耗费时间较长［6］。为了解决基本RRT算法的缺陷，国内外学者提出了许多改进算法。LaValle和Kuffner通过从起始点和目标点两个方向同时向对方扩展形成两棵随机树，提出了Bi-RRT算法［5］，之后在此基础上增加贪婪策略，提出了RRT-connect算法［7］，提高了节点扩展效率。

由于RRT的最大缺陷是没有考虑可行解的成本，没办法搜索出最优路径。Karaman和Frazoli在2011年提出了渐进最优的RRT*算法［8］，该算法在RRT扩展树节点的基础上根据最优标准来调整随机树中的节点。虽然确保了近似最优性，但是该算法仍需对所有状态空间进行采样来搜索路径，增加了不必要的内存和计算。为了提高RRT*的搜索效率……