关键词: 路径规划, JPS算法, 跳点, 碰撞危险度

Abstract:

The path planned by JPS（Jump Point Search） algorithm is often too close to the obstacle, which affects the quality of the path. Therefore, an improved JPS algorithm based on path collision hazard is proposed. By using the risk assessment function to evaluate the traditional jump points, the jump points with high risk in the same corner of the obstacle are combined to form a new type of jump points. At the same time, the obstacle is puffed up to keep a certain distance between the jump point and the obstacle, so as to improve the search range of each iteration of the algorithm. Finally, the non-direct jump point is deleted to reduce the path length of the improved algorithm and improve the performance of the algorithm. Simulation results show that the improved JPS algorithm increases the average search speed by 58.9%, reduces the average path length by 2.7%, and reduces the average collision risk by 41.3% in the complex environment.

Key words: path planning, Jump Point Search（JPS） algorithm, jump point, collision risk