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

近年来,跳点搜索(Jump Point Search, JPS)算法在移动机器人的全局路径规划中得到广泛运用,但其本身存在计算量较大、用时较长等问题。因而有人又提出了通过地图预处理提高效率的JPS+算法,但仍然在计算量和用时上有改进空间。针对业界存在的现实问题,首先介绍了JPS+的主要工作,并对JPS+算法进行了详尽分析,继而阐明了本文提出的两点改进策略。一是引入了一种基于密度的判断障碍物角点规则,进而减少主要跳点的数量；二是在进行最短路径求解过程中对目标跳点的判定规则进行了修改,从而实现了减少计算量、缩短计算时长的目标。为验证所提改进型JPS+算法的有效性,将JPS+算法在不同类型地图中与改进型JPS+算法进行了比较。仿真结果表明,改进型JPS+算法在多种地图中均能有效提高搜索速度,路径规划也十分合理,由此证明所提改进型JPS+算法对于全局路径规划具有实用价值和推广意义。

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.