基于并行-交替式双向JPS算法的机器人路径规划

Robot Path Planning Based on Parallel Alternate Bidirectional JPS Algorithm

摘要:

针对跳点搜索（Jump Point Search，JPS）算法在障碍物位置随机的栅格地图中路径规划时间较长的问题，提出了并行-交替式双向跳点搜索（Parallel Alternate Bidirectional Jump Point Search，PA-BJPS）算法。首先，在起始点与目标点间确定一个中心热点区域；其次，采用改进了预计代价函数的并行式双向跳点搜索算法，分别规划从起始点抵达中心热点区域以及目标点抵达中心热点区域的路径；然后，采用交替式双向跳点搜索算法，规划中心热点区域内部的路径；最后，提出迭代式路径修正方法来改良危险路径，并采用3次B-样条曲线替代拐角来平滑路径。仿真结果表明，并行-交替式双向跳点搜索算法有效地缩短了路径规划时间，同时提高了路径的安全性和平滑性。

Abstract:

Aiming at the problem of long path planning time of traditional jump point search(JPS) algorithm in grid map with random obstacle location, a parallel alternate bidirectional jump point search algorithm(PA-BJPS) is proposed. Firstly, a central hot spot area is determined between the starting point and the target point; Secondly, the parallel bidirectional jump point search algorithm with improved estimated cost function is used to plan the paths from the starting point and the target point to the central hot spot area respectively; Then, the alternate bidirectional jump point search algorithm is used to plan the path inside the central hot spot area; Finally, an iterative path correction method is proposed to improve the dangerous path, and the cubic B-spline curve is used to replace the corners to smooth the path. The simulation results show that PA-BJPS algorithm effectively shortens the path planning time and improves the security and smoothness of the planned path.