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

Agent path planning based on regular hexagon grid JPS algorithm

作　　者：王文明 杜佳璐 WANG Wenming;DU Jialu(School of Marine Engineering,Dalian Maritime University,Dalian 116000,China;School of Marine Electrical Engineering,Dalian Maritime University,Dalian 116000,China)

机构地区：[1]大连海事大学轮机工程学院,辽宁大连116026 [2]大连海事大学船舶电气工程学院,辽宁大连116026

出　　处：《系统工程与电子技术》2021年第12期3635-3642,共8页Systems Engineering and Electronics

基　　金：国家自然科学基金(51079013);大连市科技创新基金(2020JJ26GX020)资助课题。

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

关 键 词：正六边形 栅格地图 JPS算法 路径规划 

分 类 号：N945[自然科学总论—系统科学]