Journal of System Simulation
Abstract
Abstract: To address the limitations of the traditional A* algorithm in large and complex scenes, including traversing a large number of nodes, long computation times, and susceptibility to U-shaped traps, this paper proposes an improved A* algorithm incorporating the jump point search (JPS) concept and image processing techniques to extract key points from the global map. The proposed method preprocesses the global map to identify corner points located one grid diagonally from obstacles, constructs a key point list, and replaces the nodes traditionally traversed by the A* algorithm with these global key points, significantly reducing computational overhead. The neighbor nodes are redefined using the Bresenham line algorithm, enabling the algorithm to search for paths efficiently while avoiding unnecessary nodes. The improved A* algorithm was validated through simulations and obstacle scenarios in MATLAB. The results demonstrate that the proposed method achieves faster pathfinding, shorter path lengths, fewer turning points, and effectively addresses the U-shaped trap problem.
Recommended Citation
Lin, Guijuan; Li, Zihan; and Wang, Yu
(2025)
"Research on Improved A* Algorithm Path Planning Based on Global Key Point Extraction,"
Journal of System Simulation: Vol. 37:
Iss.
3, Article 10.
DOI: 10.16182/j.issn1004731x.joss.23-1375
Available at:
https://dc-china-simulation.researchcommons.org/journal/vol37/iss3/10
First Page
667
Last Page
678
CLC
TP391.9
Recommended Citation
Lin Guijuan, Li Zihan, Wang Yu. Research on Improved A* Algorithm Path Planning Based on Global Key Point Extraction[J]. Journal of System Simulation, 2025, 37(3): 667-678.
DOI
10.16182/j.issn1004731x.joss.23-1375
Included in
Artificial Intelligence and Robotics Commons, Computer Engineering Commons, Numerical Analysis and Scientific Computing Commons, Operations Research, Systems Engineering and Industrial Engineering Commons, Systems Science Commons