Self-adaptive search algorithm for path planning based on the A* algorithm

Abstract

The A* algorithm plays an important role in global path planning for robots, but it faces challenges such as redundant nodes and large search spaces. This paper proposes the Obstacle Density-based Dynamic Exponential A* (ODDEA*) algorithm. The ODDEA* algorithm adjusts the weights of the heuristic function based on the density of the surrounding obstacles. It uses the improved heuristic function to guide the robot toward areas with low obstacle density, employing a local dynamic penalty. The computational experiments compare the proposed ODDEA* algorithm with the Theta*, A*, and BA* algorithms, involving small-size (20×20), medium-size (40×40), and large-size (60×60) grid maps, as well as 50 random medium-size maps. The proposed ODDEA* algorithm uses fewer expanded nodes and less planning time than the other algorithms. Compared with the A* algorithm, it achieves 46.96% of the planning time and 20.33% of the search space on the three fixed grid maps.