基于改进RRT算法的无人机三维避障规划

李克玉，陆永耕，鲍世通，徐培真

(上海电机学院电气学院上海 200240)

1 引言

无人机的避障规划是指在未知障碍物的环境中，无人机能够借助信息的反馈，在一些约束条件(如时间最短、距离最短和能耗最低等)下，自主分析环境信息并规划出一条从起始状态到目标状态的无碰撞路径[1，2]。国内外很多学者对无人机的路径规划避障算法进行了研究，而且提出了很多优化的算法。其中启发式算法有遗传模拟退火算法[3]、蚁群算法[4]、遗传算法[5]、A*算法[6，7]等。数学优化算法主要有人工势场法[8]、快速扩展随机树(RRT)法[9]等。

RRT算法由于其无需对系统进行建模，无需对搜索区域进行几何划分，搜索的范围广等众多优势[10]，其在避障规划上的运用受到了很多学者的青睐，改进方法也层出不穷。RRT*算法以新增节点半径r的邻域内随机树上所有的节点为备选节点，很好的解决RRT算法生成避障路径非最优问题[11]；RRT-Connect算法通过在起始点和目标点并行生成两棵随机树的方式来提高寻找避障路径的速度[12]，将其与桥梁检测(Bride Test)算法融合，很好的解决了RRT-connect算法在窄道内采样难的问题[13]；在RRT算法中引入人工势场法，很好的利用了势场函数法能够携带障碍物和目标点等优点，使扩展树搜索更具有方向性的同时还提高了障碍物搜索效率[14]。

由此可以看出，在二维空间内，目前国内外对RRT算法的避障路径快速生成[15]和优化窄道局部采样[16]等方面做了很好的改进，使得改进后的RRT算法在避障能力和搜索效率等方面都有很大的提高。……