Robot path planning based on improved A* algorithm

摘要

Abstract To address the issues of excessive polyline paths and the increased number of search nodes in the A* algorithm, a weighted WA* algorithm is proposed based on the A* algorithm. Firstly, a new distance function is introduced to reduce computational resource usage and improve search efficiency. Then, the heuristic function is improved by searching all feasible paths to find the shortest path. When the lengths of feasible paths are very similar, an additional value is added to the heuristic function along with weights to minimize frequent searches. Lastly, Bezier curves are introduced to enhance the smoothness of the global path. Simulation results show that the improved WA* algorithm reduces the number of turns, time consumption, search space, and turning angles by 25.0%, 65.4%, 53.5%, and 18.7%, respectively, compared to the A* algorithm. Compared to the bidirectional A* algorithm, these reductions are 7.6%, 34.4%, 43.5%, and 7.1%, respectively. In addition, the WA* algorithm uses Bezier curves to curve-fit the generated path points, making the path trajectory smoother.