The EBS-A* algorithm: An improved A* algorithm for path planning
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 algori...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Public Library of Science (PLoS)
2022-01-01
|
| Series: | PLoS ONE |
| Online Access: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8853577/?tool=EBI |
| _version_ | 1819279816843591680 |
|---|---|
| author | Huanwei Wang Shangjie Lou Jing Jing Yisen Wang Wei Liu Tieming Liu |
| author_facet | Huanwei Wang Shangjie Lou Jing Jing Yisen Wang Wei Liu Tieming Liu |
| author_sort | Huanwei Wang |
| collection | DOAJ |
| description | 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%. |
| first_indexed | 2024-12-24T00:33:55Z |
| format | Article |
| id | doaj.art-580a8b95222d444dbca4b247ae8a7238 |
| institution | Directory Open Access Journal |
| issn | 1932-6203 |
| language | English |
| last_indexed | 2024-12-24T00:33:55Z |
| publishDate | 2022-01-01 |
| publisher | Public Library of Science (PLoS) |
| record_format | Article |
| series | PLoS ONE |
| spelling | doaj.art-580a8b95222d444dbca4b247ae8a72382022-12-21T17:24:10ZengPublic Library of Science (PLoS)PLoS ONE1932-62032022-01-01172The EBS-A* algorithm: An improved A* algorithm for path planningHuanwei WangShangjie LouJing JingYisen WangWei LiuTieming LiuPath 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%.https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8853577/?tool=EBI |
| spellingShingle | Huanwei Wang Shangjie Lou Jing Jing Yisen Wang Wei Liu Tieming Liu The EBS-A* algorithm: An improved A* algorithm for path planning PLoS ONE |
| title | The EBS-A* algorithm: An improved A* algorithm for path planning |
| title_full | The EBS-A* algorithm: An improved A* algorithm for path planning |
| title_fullStr | The EBS-A* algorithm: An improved A* algorithm for path planning |
| title_full_unstemmed | The EBS-A* algorithm: An improved A* algorithm for path planning |
| title_short | The EBS-A* algorithm: An improved A* algorithm for path planning |
| title_sort | ebs a algorithm an improved a algorithm for path planning |
| url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8853577/?tool=EBI |
| work_keys_str_mv | AT huanweiwang theebsaalgorithmanimprovedaalgorithmforpathplanning AT shangjielou theebsaalgorithmanimprovedaalgorithmforpathplanning AT jingjing theebsaalgorithmanimprovedaalgorithmforpathplanning AT yisenwang theebsaalgorithmanimprovedaalgorithmforpathplanning AT weiliu theebsaalgorithmanimprovedaalgorithmforpathplanning AT tiemingliu theebsaalgorithmanimprovedaalgorithmforpathplanning AT huanweiwang ebsaalgorithmanimprovedaalgorithmforpathplanning AT shangjielou ebsaalgorithmanimprovedaalgorithmforpathplanning AT jingjing ebsaalgorithmanimprovedaalgorithmforpathplanning AT yisenwang ebsaalgorithmanimprovedaalgorithmforpathplanning AT weiliu ebsaalgorithmanimprovedaalgorithmforpathplanning AT tiemingliu ebsaalgorithmanimprovedaalgorithmforpathplanning |