刘建宇，范平清

上海工程技术大学 机械与汽车工程学院，上海 201620

随着时代的飞速发展，高度自主化的机器人在人类社会中的地位与作用越来越大。而机械臂作为机器人的一个最主要操作部件，其运动规划问题，例如准确抓取物体，在运动中躲避障碍物等，是现在研究的热点，对其运动规划的不断深入研究是非常必要的。

机械臂的运动规划主要在高维空间中进行。RRT（Rapidly-exploring Random Tree）算法[1]基于随机采样的规划方式，无需对构型空间的障碍物进行精确描述，同时不需要预处理，因此在高维空间被广为使用。

近些年人们对于RRT 算法的研究很多，2000 年Kuffner 等提出 RRT-connect 算法[2]，通过在起点与终点同时生成两棵随机树，加快了算法的收敛速度，但存在搜索路径步长较长的情况。2002 年Bruce 等提出了ERRT（Extend RRT）算法[3]。2006年Ferguson等提出DRRT（Dynamic RRT）算法[4]。2011 年 Karaman 和 Frazzoli 提出改进的RRT*算法[5]，在继承传统RRT 算法概率完备性的基础上，同时具备了渐进最优性，保证路径较优，但是会增加搜索时间。2012 年Islam 等提出快速收敛的RRT*-smart 算法[6]，利用智能采样和路径优化来迫近最优解，但是路径采样点较少，使得路径棱角较大，不利于实际运用。2013 年Jordan 等通过将RRT*算法进行双向搜索，提出B-RRT*算法[7]，加快了搜索速度。同年Salzman 等提出在下界树LBT-RRT 中连续插值的渐进优化算法[8]。2015 年Qureshi 等提出在B-RRT*算法中插入智能函数提高搜索速度的IB-RRT*算法[9]。同年Klemm等结合RRT*的渐进最优和RRT-connect的双向搜索，提出使搜索路径朝理论最优解收敛的RRT*-connect算法[10]。2016年王道威等提出动态步长的RRT算法[11]，但是只考虑简单障碍物环境。……