改进双向动态JPS算法的移动机器人全局路径规划  

Improved bidirectional dynamic JPS algorithm forglobal path planning of mobile robot

作　　者：刘荣华 王欣[1] 吴迪[2] 谢春圆 Liu Ronghua;Wang Xin;Wu Di;Xie Chunyuan(School of Mechanical Engineering,Dalian University of Technology,Dalian Liaoning 116024,China;School of Computer Science&Technology,Dalian University of Technology,Dalian Liaoning 116024,China)

机构地区：[1]大连理工大学机械工程学院,辽宁大连116024 [2]大连理工大学计算机科学与技术学院,辽宁大连116024

出　　处：《计算机应用研究》2024年第4期1117-1122,共6页Application Research of Computers

基　　金：中央高校基本科研业务费资助项目(DUT22LAB507)。

摘　　要：针对跳点搜索(jump point search,JPS)算法在寻路过程中所存在的路径拐点多、中间搜索跳点数多、寻找跳点的过程中扩展节点数多和寻路时间较长等问题,提出改进双向动态JPS算法。改进算法动态定义正、反扩展方向上的目标点,动态定义启发函数,并利用动态约束椭圆对算法的扩展区域加以限制,以区分椭圆内、外区域的扩展优先级。在算法从起点和目标点两个方向上分别向对方进行扩展的过程中,以寻找到的新的代价最小点为新椭圆的焦点,椭圆的方位和约束区域也随之动态调整。仿真结果表明,经过优化改进的双向动态JPS算法在一般地图中有一定的表现,在障碍物较少且目标点距离起点较近的室内环境地图中表现尤为良好。In order to address the issues with the jump point search algorithm in the process of pathfinding,such as numerous path inflection points,numerous intermediate search hop points,numerous extended nodes,and lengthy pathfinding time in the process of finding jump points,this paper proposed the improved bidirectional dynamic JPS algorithm.The improved algorithm dynamically defined the target points in the forward and reverse expansion directions,dynamically defined the heuristic function,and used the dynamic constraint ellipse to restrict the expansion region of the algorithm to distinguish the expansion priorities of the inner and outer regions of the ellipse.The new cost minimum point served as the focus of the new ellipse,and the orientation and constraint region were dynamically changed as the extension from the starting point and goal point to each other.The simulation results show that the optimized bidirectional dynamic JPS algorithm has a certain performance in general maps,especially in indoor environment maps with fewer obstacles and the target point is close to the starting point.

关 键 词：路径规划 跳点搜索 双向动态搜索 移动机器人 

分 类 号：TP242.6[自动化与计算机技术—检测技术与自动化装置]