一种改进的跳点搜索移动机器人路径规划算法

An Improved Jump Point Search Algorithm for Mobile Robots Path Planning

  • 摘要: 针对跳点搜索(jump point search,JPS)算法路径存在斜向穿越障碍物、搜索过程中存在较多冗余跳点、路径拐点多且靠近障碍物的问题,提出一种安全快速的跳点搜索(safe fast jump point search,SFJPS)算法。该算法重新定义跳点判断规则,使生成的跳点均为安全跳点,解决了路径中斜向穿越障碍物的情况;加入基于角度的搜索方向优先级判断,有效减少了搜索过程中的冗余节点,加快了搜索速度;基于Bresenham算法对路径上的跳点进行关键跳点筛选,关键跳点生成的路径拐点明显减少,贴近障碍物的路径长度大幅减小,整体路径长度也有所减小。结果表明在不同场景下本文算法相较于A*算法和JPS算法,路径长度分别最大减小了5.42%和4.48%,搜索时间分别最大缩短了98.33%和67.83%,搜索节点数最大减少了99.08%和56.72%,路径拐点数分别最大减少了90.91%和83.33%。相较于Theta*算法路径长度增加了1.17%,搜索时间缩短了91.07%,搜索节点数减少了98.9%。仿真试验证明本文算法规划速度快,路径安全且拐点更少,更加适用于移动机器人路径规划问题。

     

    Abstract: To address the limitations of the jump point search (JPS) algorithm, such as path crossing obstacles obliquely, excessive redundant jump points in the search process, numerous turning points in the path, and proximity to obstacles, we propose a safe fast jump point search (SFJPS) algorithm. This new algorithm redefines jump point judgment criteria to ensure all generated jump points are safe, thus eliminating oblique obstacle crossings. By incorporating angle-based search direction priority judgment, the algorithm effectively reduces redundant nodes and speeds up the search process. Employing the Bresenham algorithm, key jump points are identified, significantly reducing the number of turning points and shortening paths close to obstacles. In different scenarios, SFJPS reduces path length by up to 5.42% compared with the A* algorithm and 4.48% compared with the JPS algorithm. It also shortens the search time by up to 98.33% and 67.83%, respectively, and decreases the number of search nodes by up to 99.08% and 56.72%, respectively. The number of path turning points is reduced by up to 90.91% and 83.33%, respectively. Although the path length increases by 1.17% compared with the Theta* algorithm, SFJPS shortens search time by 91.07% and reduces the number of search nodes by 98.9%. Simulation experiments show that the proposed algorithm offers fast planning speed, safe paths, and fewer turning points, making it more suitable for mobile robot path planning problems.

     

/

返回文章
返回