The EBS-A* algorithm: An improved A* algorithm for path planning

PLoS One. 2022 Feb 17;17(2):e0263841. doi: 10.1371/journal.pone.0263841. eCollection 2022.

Abstract

Path planning plays an essential role in mobile robot navigation, and the A* algorithm is one of the best-known path planning algorithms. However, the traditional A* algorithm has some limitations, such as slow planning speed, close to obstacles. In this paper, we propose an improved A*-based algorithm, called the EBS-A* algorithm, that introduces expansion distance, bidirectional search, and smoothing into path planning. The expansion distance means keeping an extra space from obstacles to improve path reliability by avoiding collisions. Bidirectional search is a strategy searching path from the start node and the goal node simultaneously. Smoothing improves path robustness by reducing the number of right-angle turns. In addition, simulation tests for the EBS-A* algorithm are performed, and the effectiveness of the proposed algorithm is verified by transferring it to a robot operating system (ROS). The experimental results show that compared with the traditional A* algorithm, the proposed algorithm improves the path planning efficiency by 278% and reduces the number of critical nodes by 91.89% and the number of right-angle turns by 100%.

MeSH terms

  • Algorithms*
  • Artificial Intelligence*
  • Computer Simulation*
  • Computer Systems
  • Humans
  • Robotics / methods*

Grants and funding

The author(s) received no specific funding for this work.