VNS-BA*: An Improved Bidirectional A* Path Planning Algorithm Based on Variable Neighborhood Search
Sensors · 29.10.2024 · 24 (21) · 6929
DOI: 10.3390/s24216929 ↗Kurz gefasst
Fachartikel in der Zeitschrift Sensors, online erschienen am 29.10.2024. Verfasst von Peng Li und 2 weiteren Autor:innen. Beteiligte Einrichtung: School of Electronic and Information Engineering, Nanjing University of Information Science and Technology, Nanjing 210044, China. Die Arbeit wurde bisher 13-mal zitiert (Crossref) und nennt 29 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Natural Science Foundation of the Higher Education Institutions of Jiangsu Province.
Abstract (Originalsprache)
The A* algorithm is an effective method for path planning; however, it has certain drawbacks, such as a high number of turns, low planning efficiency, and redundant searches. To address these issues, this paper proposes an improved bidirectional A* global path planning algorithm based on a variable neighborhood search strategy, named VNS-BA*. The new algorithm first employs an 8-11-13 neighborhood search method for node expansion. Then, the bidirectional search strategy is optimized by using the current nodes of the opposite path and the global target point, enabling the two paths to meet in the middle of the map. Finally, redundant turns are removed from the path, and cubic spline interpolation is applied to achieve local smoothing at the turns. The effectiveness of the improved algorithm was validated on different maps and compared with A* and its three derived improved versions. The simulation results indicate that VNS-BA* shows significant improvements in terms of the number of path turns, turn angles, and planning efficiency.
Schlagwörter
Stichwörter der Autor:innen
Autor:innen und Institutionen
- School of Electronic and Information Engineering, Nanjing University of Information Science and Technology, Nanjing 210044, China.
- School of Automation, Wuxi University, Wuxi 214105, China.
ORCID-Profile: Ying Li
Förderung
- Natural Science Foundation of the Higher Education Institutions of Jiangsu Province
Zitieren
APA
Li, P., Li, Y., & Dai, X. (2024). VNS-BA*: An Improved Bidirectional A* Path Planning Algorithm Based on Variable Neighborhood Search. Sensors, 24(21), 6929. https://doi.org/10.3390/s24216929
Vancouver
Li P, Li Y, Dai X. VNS-BA*: An Improved Bidirectional A* Path Planning Algorithm Based on Variable Neighborhood Search. Sensors. 2024;24(21):6929. doi:10.3390/s24216929
BibTeX
@article{Li2024,
author = {Li, Peng and Li, Ying and Dai, Xuesong},
title = {VNS-BA*: An Improved Bidirectional A* Path Planning Algorithm Based on Variable Neighborhood Search},
journal = {Sensors},
year = {2024},
volume = {24},
number = {21},
pages = {6929},
doi = {10.3390/s24216929}
}
EUVIMED