基于密度分类的JPS+移动机器人全局路径规划算法

针对传统全局路径规划中扩展节点多、寻路时间长等问题，提出一种基于JPS+(jump point search plus)算法的全局路径规划算法，旨在提高机器人在复杂环境的智能性、高效性的要求。首先引入了一种基于密度的判断障碍物角点规则，实现对于主要跳点的识别数目，减少搜索路径过程中的可扩展节点，同时在路径求解过程中对目标跳点的判定规则进行了修改，最终实现了减少计算量、缩短计算时长的目标。为验证所提改进型JPS+算法的有效性，将A~*、JPS+算法在不同类型地图中与改进型JPS+算法进行了比较。仿真结果表明，改进型JPS+算法与A~*算法相比，在路径长度、寻路时间和扩展节点数量上都有明显改进；在生成相同路径的基础上，与传统JPS+算法相比，在障碍物占比33.25%的地图中搜索时间降低了7.58%,节点扩展数量减少了9.38%,能够满足移动机器人快速全局路径规划的要求。

JPS+ Global Path-planning Algorithm for Mobile Robots Based on Density Classification

Recently, the Jump Point Search(JPS) algorithm has been widely used in mobile robot path planning. However, it has problems such as much calculation and a long time. Therefore, the JPS+ algorithm is proposed to improve the efficiency through map preprocessing. However, there is still space to develop in computation and time. This paper introduces the main work of JPS+ algorithm in detail and puts forward modifications in two points. Firstly, it introduces a density-based rule for judging obstacle corner points, thereby reducing the number of main jump points; on the other hand, the logic of Target Jump Points work is altered to reduce the amount of calculation and shorten the time in solving the shortest path. To verify the effectiveness of the improved JPS+ algorithm, the algorithm is compared with the A* algorithm and the JPS+ algorithm in different maps. The simulation results show that the improved JPS+ algorithm can effectively increase the search speed in various maps, and the path planning is also very reasonable. As a result, the improved JPS+ algorithm has practical value and promotion significance for global path planning.