黄壹凡，胡立坤，薛文超

（广西大学 电气工程学院，南宁 530004）

0 概述

机器人学聚集了多种学科最先进的研究成果，一直以来都是科学技术领域的研究热点。路径规划算法作为移动机器人的重要组成部分，是移动机器人运行研究的重点问题［1］。

路径规划的基本任务是找到一条从起始位置到目标位置的无碰撞路径［2］，并且使得这条路径能够具有距离短、用时少等优点。在传统路径规划方法中：A*算法［3-4］和D*算法［5］在实时规划或者局部规划中都有较好的性能，但两种算法需要的计算量较大，特别在三维空间中计算量剧增；人工势场法［6］易于实现的优点使其能被广泛应用，但容易陷入局部极小值；蚁群算法［7］可以获得全局最优解且有较强鲁棒性，但计算量大、收敛时间长。

快速扩展随机树（Rapidly exploring Random Tree，RRT）算法采用随机采样方法搜索［8］，具有很强的搜索性，但是该算法的随机性也导致其搜索效率较低。为提高RRT 算法的搜索效率，偏 向RRT［9］、RRT-Connect［10］、双 向RRT［11］等改进算法被相继提出，这些算法通过目标偏向、双树拓展等改进加快了收敛算法速度，但仍存在较大转折、绕远等问题。为得到最优路径，一些算法相继提出：RRT*［12-13］采用渐进优化思想改进了由基本RRT 产生的并非概率最优解问题；Bi-RRT*［14］采用双树拓展同时结合RRT-Connect 和启发式思想，在保证渐进最优的同时加快了收敛速度；Quick-RRT*［15］在重选父节点时扩大潜在父节点选择范围，以此减少路径不必要的拐弯来缩短路径长度；文献［16］通过重选父节点的方法改进RRT 算法来缩短规划路径；……