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.