基于正六边形栅格JPS算法的智能体路径规划

通过构建正六边形栅格地图, 并修改传统跳点搜索(jump point search, JPS)算法的邻居剪枝、强制邻居判断的规则和JPS策略, 提出一种新的正六边形栅格JPS算法, 并且利用该算法解决智能体在环境地图存在障碍物时的路径规划问题。利用Pycharm平台进行仿真研究, 并与传统正方形栅格A^*算法和JPS算法进行路径规划仿真比较, 结果表明正六边形栅格JPS算法可更好地实现路径规划, 所规划出的路径可避免穿越墙角的不安全行为、减少转向次数, 且该算法可减少路径规划时间, 提高了路径规划的质量和效率。

Agent path planning based on regular hexagon grid JPS algorithm

By constructing a regular hexagon grid map and modifying the rules of neighbors pruning, forced neighbors judgment and jump point search (JPS) strategy of the traditional JPS algorithm, a new regular hexagon grid JPS algorithm is proposed, which is used to solve the path planning problem of the agent on the environment map with obstacles. The path planning simulations and the simulation comparisons with the traditional square grid A^* algorithm and JPS algorithm are carried out on Pycharm platform. The simulation results show that the regular hexagon grid JPS algorithm can plan paths better, avoiding the unsafely crossing corner behaviors, reducing the number of turnings and the time of path planning, thus the algorithm improves the quality and efficiency of path planning.