一种面向非结构化环境的改进跳点搜索路径规划算法

An Improved Jump Point Search Path-planning Algorithm for Unstructured Environment

为解决非结构化复杂场景下基于搜索的寻路算法中存在的计算时间长、路径非最优等问题,在跳点搜索(jump point search,JPS)算法的基础上,提出一种带权重的跳点搜索(weighted jump point search,WJPS)算法。WJPS算法改进了启发式函数,同时采用非传统的距离表达,最终实现了在保证全局路径最短的同时,降低了计算时间。为了验证WJPS算法的有效性,设计了多种非结构化复杂场景地图,对A、JPS算法和WJPS算法在寻路时间、扩展点数和路径长度3方面进行了对比。实验结果显示,相比A算法和JPS算法,WJPS算法在复杂环境中能保证生成路径是最短的,同时利用JPS跳点算法中寻找拓展点的策略,能够实现毫秒级别的规划,且算法效率能够满足智能体对路径规划层的要求。另外,WJPS算法采用微分平坦法对生成的路径点作曲线拟合,使智能体的运动轨迹更加平滑。

To solve the problems of long computation time and non-optimal path in the path-planning algorithms based on search in unstructured and complex scenarios,a weighted jump point search algorithm was proposed based on jump point search algorithm(JPS).The proposed algorithm,called weighted jump point search WJPS,improved heuristic function and adopted the unconventional distance expression policy.To verify the effectiveness of WJPS algorithm,a variety of unstructured complex scenarios were designed,and A,JPS,and WJPS were compared in three aspects:path-finding time,expansion points,and path length.The experimental results show that the proposed algorithm can guarantee the optimal path generation in complex environments,and the millisecond planning efficiency can meet the requirements of the path planning layer.In addition,the differential flat method is used to perform curve-fitting for to the path points generated by WJPS algorithm.Finally,the experimental results show that the trajectory after curve fitting is smoother and suitable for direct control by intelligent agents.