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

Area of Science:

• Robotics
• Artificial Intelligence
• Computer Science

Background:

• The A* algorithm is crucial for robot global path planning.
• Existing A* methods struggle with redundant nodes and large search spaces.

Purpose of the Study:

• To introduce the Obstacle Density-based Dynamic Exponential A* (ODDEA*) algorithm.
• To enhance robot path planning efficiency by addressing A* limitations.

Main Methods:

• The ODDEA* algorithm dynamically adjusts heuristic function weights based on surrounding obstacle density.
• A local dynamic penalty is incorporated to guide robots toward low-obstacle-density areas.
• Computational experiments compare ODDEA* against Theta*, A*, and BA* on various grid map sizes.

Main Results:

• ODDEA* significantly reduces expanded nodes and planning time compared to Theta*, A*, and BA*.
• On fixed grid maps, ODDEA* achieved 46.96% of the planning time and 20.33% of the search space compared to A*.
• Experiments included small (20x20), medium (40x40), large (60x60) grid maps, and 50 random medium maps.

Conclusions:

• The ODDEA* algorithm offers superior performance in robot path planning.
• ODDEA* effectively minimizes computational resources by optimizing search space and reducing planning time.
• This algorithm presents a promising advancement for efficient robotic navigation in complex environments.