Improved A∗ Algorithm for AGV Path Planning Based on Obstacle Density Prioritization Strategy
摘要
An improved A∗ algorithm was proposed to address the problems of excessive path turning points, redundant nodes, and susceptibility to local optimum in AGV path planning when the traditional A∗ algorithm was applied in obstacle-dense scenarios. The environment model was constructed using the grid method. Firstly, an obstacle density function K(n) was introduced into the heuristic function to improve the cost function, enabling a more accurate estimation of the actual cost from the current node to the target node. Secondly, a dynamic neighborhood search strategy was adopted to enhance the search efficiency and operational performance of the algorithm. Finally, a redundant node processing strategy was implemented to reduce path turning points and remove redundant nodes, yielding a path that contained only the starting point, turning points, and the endpoint. Simulation experiments were conducted on grid maps with varying sizes and complexities. The results demonstrated that, compared to the traditional A∗ algorithm and other improved A∗ algorithm, the proposed algorithm achieved path length reductions of 4.71% and 2.07%, turning point reductions of 45.45% and 20.54%, and node reductions of 84.24% and 62.45%, respectively.