基于JPS策略的改进RRT^(*)移动机器人全局路径规划算法

An improved RRT^(*) path planning algorithm based on JPS strategyfor mobile robot

针对渐进最优快速扩展随机树(RRT^(*))算法在移动机器人路径规划中存在的收敛速度慢、消耗资源大、路径平滑度较低等问题,提出一种基于跳点搜索(JPS)策略的RRT^(*)算法。该算法在随机树扩展初期构建新的路径规划区域,查询是否存在一条目标点路径;在随机树扩展过程中,利用JPS搜索策略减少算法寻路过程中计算节点的数量。利用不同规格的栅格地图进行的仿真实验结果表明,相比于RRT^(*)算法,改进的RRT^(*)算法寻路效率更高、路径质量更优。最后,将两种算法在相同环境下进行路径规划实验。结果证明,改进的RRT*算法是一种有效、可行的改进算法,且寻路效率提升20%以上。

Aiming at the problems of slow convergence speed,large resource consumption and low path smoothness in the mobile robot path planning of rapidly-exploring random tree^(*)(RRT^(*))algorithm,an improved RRT^(*)algorithm based on jump point search(JPS)strategy is proposed.The algorithm constructs a new path planning region at the initial stage of random tree expansion and queries whether there is an entry punctuation path.In the process of random tree expansion,the number of nodes is reduced by using JPS strategy.The simulation experiment results by using grid maps of different specifications show that the improved RRT^(*)algorithm is more efficient and has better path quality than the RRT^(*)algorithm.Finally,the two algorithms are carried out in the same environment,and the results show that the improved RRT^(*)algorithm is an effective and feasible improved algorithm,and the path-finding efficiency is improved by more than 20%.