基于B-RRT^(*)FND算法的移动机器人路径规划  

Path planning of AGV based on B-RRT^(*)FND algorithm

作　　者：张腾龙 李擎[1] ZHANG Teng-long;LI Qing(School of Automation,Beijing Information Science and Technology University,Beijing 100085,China)

机构地区：[1]北京信息科技大学自动化学院,北京100085

出　　处：《控制与决策》2023年第11期3121-3127,共7页Control and Decision

基　　金：国家自然科学基金项目(61971048);国家重点研发计划项目(2020YFC1511702)。

摘　　要：针对RRT^(*)FN算法获取路径解的速度慢,且无法应用于动态环境等问题,提出固定节点数的动态双向渐近最优快速随机扩展树算法(bidrectional RRT^(*)fix-node dynamic,B-RRT^(*)FND),用于解决移动机器人在二维空间内快速实时获取无碰撞路径的问题.所提出算法基于RRT^(*)FN算法,采用双向贪婪搜索方法加快路径搜索速度,解决单向RRT算法由于随机采样的盲目性造成的搜索速度慢、在狭窄环境下难以搜索到解的问题;利用固定节点算法在规划过程中不占用过多计算量的特点,在路径迭代优化过程中,实时更新地图信息,并对被破坏的原始路径进行修复重连,以完成算法的动态规划.将所提出算法与RRT、RRT^(*)FN等算法在3种环境下进行对比仿真,验证结果表明,所提出算法在规划速度、路径解长度以及动态规划性能方面具有较好效果.Aiming at the problems of the RRT^(*)FN algorithm about its slow speed to obtain the path solutions and unable to applied in dynamic environment,a dynamic bidirectional RRT^(*)algorithm with fixed nodes(B-RRT^(*)FND)is proposed,which is used to solve the problem of how to obtain collision-free paths in 2D space quickly in real-time with a robot.The algorithm is based on the RRT^(*)FN algorithm,using the bidirectional greedy search method to speed up the searching and solve the problems of the unidirectional RRT algorithm about its slow searching speed as well as the difficulty of solving in the narrow environment caused by blindly random sampling.Meanwhile,taking the advantage of the fact that fixed nodes do not occupy too much computation in planning,in the process of path iterative optimization,the algorithm updates the map information in real-time,and repairs the broken original path to complete the dynamic path planning.Compared with the RRT,the RRT^(*)FN and other algorithms in three environments,the B-RRT^(*)FND algorithm is superior in planning speed,length of path and dynamic programming performance.

关 键 词：移动机器人 RRT^(*)FN算法 动态路径规划 双向贪婪搜索 渐近最优 路径修复 

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]