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.

Key words: path planning, improved A* algorithm, key point extraction, mobile robot