Improved JPS algorithm based on greedy strategy

To address the problem of the JPS (Jump Point Search) algorithm lacking goal orientation in the pathfinding process, resulting in the presence of many redundant nodes along the explored path and affecting search efficiency, particularly difficult to meet the real-time requirements of high-speed movement for MAV, this paper proposes a JPS algorithm with a backtracking greedy strategy (BG-JPS) based on the greedy approach. Firstly, the type of nodes added to the priority queue during the search process is optimized. Secondly, the goal orientation of the jump point search process is enhanced by estimating the cost value to the destination. Then, through backtracking update the priority of the exploration direction of nodes between two adjacent exploration processes. Finally, simulation experiments are conducted on two-dimensional grid maps of different sizes and complexities. Simulation results show that compared to the JPS algorithm, the BG-JPS algorithm reduces the number of expanded nodes by 30% to 68% and shortens the search time by 16% to 53% across various types of maps, while maintaining similar path lengths. The improved BG-JPS algorithm can effectively addresses the problem of low search efficiency in large-scale scenarios due to the lack of goal orientation in the JPS algorithm.