孙丰财， 张亚楠， 史旭华

(宁波大学 信息科学与工程学院,浙江 宁波 315000)

改进的快速扩展随机树路径规划算法*

孙丰财， 张亚楠， 史旭华

(宁波大学 信息科学与工程学院,浙江 宁波 315000)

针对快速扩展随机树(RRT)路径规划算法缺乏稳定性和偏离最优解的问题，提出了一基于RRT的偏向性路径搜索算法(m-RRT)。m-RRT采用生成随机点向量组的形式对随机点选取策略进行了优化，改善快速扩展随机树的不确定性，减少不必要的扩展，而加快向目标位置搜索的速度，且得到的路径优于RRT算法的结果。通过其在二维平面路径规划和三维机械臂路径规划的测试,表明其具有一定的应用价值。

路径规划； 机械臂； 快速扩展随机树算法； 避障； 机器人操作系统

0 引 言

机器人路径规划即通过某些性能(如时间、距离、能量)指标来规划出一条从初始位置到目标位置的最优或者较优的线路。目前，机械臂路径规划方法主要有细胞分解法、人工势场法、随机路标法(probabilistic roadmap，PRM)和快速扩展随机树(rapidly-exploring random tree，RRT)法等[1～3]。

针对传统RRT算法的缺陷，Burget F，Bennewitz M等人[4]采用双向随机搜索树(Bi2RRT) 搜索算法，提高了搜索效率，由于该算法较原始RRT算法有更好的收敛性，因此，在目前路径规划中很常见。Melchior N A[5]提出的粒子RRT算法考虑了地形的不确定性，保证了在不确定性环境下随机搜索树的扩展。Kuffner J J等人[6]提出了RRT2connect算法，使得节点的扩展效率大大提高；同时王道威等人[7]采用动态步长改善了RRT的不确定性，冯林等人[8]通过对比优化的方法使得在复杂环境下的规划稳定性增强，宋金泽等人[9]通过添加非完整性约束及双向多步扩展方式提高了搜索效率。……