Gene

Robot

Algorithm

Engineering

Smoothing

Motion planning

Node (physics)

Robustness (evolution)

Biochemistry

Any-angle path planning

Computer science

Mathematical optimization

Path length

Computer network

Mathematics

Path (computing)

Artificial intelligence

Structural engineering

Chemistry

Programming language

Fast path

Computer vision

A* search algorithm

PLoS ONE

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%.

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