An Efficient and Robust 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 conventional A* algorithm and the subsequent improved algorithms still have some limitations in terms of robustness and efficiency. These limitations...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Huanwei Wang, Xuyan Qi, Shangjie Lou, Jing Jing, Hongqi He, Wei Liu
Formato:	article
Lenguaje:	EN
Publicado:	MDPI AG 2021
Materias:	path planning A* algorithm expansion distance bidirectional search heuristic function smoothing Mathematics QA1-939
Acceso en línea:	https://doaj.org/article/a6fcd992fb7b47e9b7c1fe229ff9a767
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:a6fcd992fb7b47e9b7c1fe229ff9a767
record_format	dspace
spelling	oai:doaj.org-article:a6fcd992fb7b47e9b7c1fe229ff9a7672021-11-25T19:07:38ZAn Efficient and Robust Improved A* Algorithm for Path Planning10.3390/sym131122132073-8994https://doaj.org/article/a6fcd992fb7b47e9b7c1fe229ff9a7672021-11-01T00:00:00Zhttps://www.mdpi.com/2073-8994/13/11/2213https://doaj.org/toc/2073-8994Path planning plays an essential role in mobile robot navigation, and the A* algorithm is one of the best-known path planning algorithms. However, the conventional A* algorithm and the subsequent improved algorithms still have some limitations in terms of robustness and efficiency. These limitations include slow algorithm efficiency, weak robustness, and collisions when robots are traversing. In this paper, we propose an improved A-based algorithm called EBHSA algorithm. The EBHSA* algorithm introduces the expansion distance, bidirectional search, heuristic function optimization and smoothing into path planning. The expansion distance extends a certain distance from obstacles to improve path robustness by avoiding collisions. Bidirectional search is a strategy that searches for a path from the start node and from the goal node at the same time. Heuristic function optimization designs a new heuristic function to replace the traditional heuristic function. Smoothing improves path robustness by reducing the number of right-angle turns. Moreover, we carry out simulation tests with the EBHSA* algorithm, and the test results show that the EBHSA* algorithm has excellent performance in terms of robustness and efficiency. In addition, we transplant the EBHSA* algorithm to a robot to verify its effectiveness in the real world.Huanwei WangXuyan QiShangjie LouJing JingHongqi HeWei LiuMDPI AGarticlepath planningA* algorithmexpansion distancebidirectional searchheuristic functionsmoothingMathematicsQA1-939ENSymmetry, Vol 13, Iss 2213, p 2213 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	path planning A* algorithm expansion distance bidirectional search heuristic function smoothing Mathematics QA1-939
spellingShingle	path planning A* algorithm expansion distance bidirectional search heuristic function smoothing Mathematics QA1-939 Huanwei Wang Xuyan Qi Shangjie Lou Jing Jing Hongqi He Wei Liu An Efficient and Robust Improved A* Algorithm for Path Planning
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 conventional A* algorithm and the subsequent improved algorithms still have some limitations in terms of robustness and efficiency. These limitations include slow algorithm efficiency, weak robustness, and collisions when robots are traversing. In this paper, we propose an improved A-based algorithm called EBHSA algorithm. The EBHSA* algorithm introduces the expansion distance, bidirectional search, heuristic function optimization and smoothing into path planning. The expansion distance extends a certain distance from obstacles to improve path robustness by avoiding collisions. Bidirectional search is a strategy that searches for a path from the start node and from the goal node at the same time. Heuristic function optimization designs a new heuristic function to replace the traditional heuristic function. Smoothing improves path robustness by reducing the number of right-angle turns. Moreover, we carry out simulation tests with the EBHSA* algorithm, and the test results show that the EBHSA* algorithm has excellent performance in terms of robustness and efficiency. In addition, we transplant the EBHSA* algorithm to a robot to verify its effectiveness in the real world.
format	article
author	Huanwei Wang Xuyan Qi Shangjie Lou Jing Jing Hongqi He Wei Liu
author_facet	Huanwei Wang Xuyan Qi Shangjie Lou Jing Jing Hongqi He Wei Liu
author_sort	Huanwei Wang
title	An Efficient and Robust Improved A* Algorithm for Path Planning
title_short	An Efficient and Robust Improved A* Algorithm for Path Planning
title_full	An Efficient and Robust Improved A* Algorithm for Path Planning
title_fullStr	An Efficient and Robust Improved A* Algorithm for Path Planning
title_full_unstemmed	An Efficient and Robust Improved A* Algorithm for Path Planning
title_sort	efficient and robust improved a* algorithm for path planning
publisher	MDPI AG
publishDate	2021
url	https://doaj.org/article/a6fcd992fb7b47e9b7c1fe229ff9a767
work_keys_str_mv	AT huanweiwang anefficientandrobustimprovedaalgorithmforpathplanning AT xuyanqi anefficientandrobustimprovedaalgorithmforpathplanning AT shangjielou anefficientandrobustimprovedaalgorithmforpathplanning AT jingjing anefficientandrobustimprovedaalgorithmforpathplanning AT hongqihe anefficientandrobustimprovedaalgorithmforpathplanning AT weiliu anefficientandrobustimprovedaalgorithmforpathplanning AT huanweiwang efficientandrobustimprovedaalgorithmforpathplanning AT xuyanqi efficientandrobustimprovedaalgorithmforpathplanning AT shangjielou efficientandrobustimprovedaalgorithmforpathplanning AT jingjing efficientandrobustimprovedaalgorithmforpathplanning AT hongqihe efficientandrobustimprovedaalgorithmforpathplanning AT weiliu efficientandrobustimprovedaalgorithmforpathplanning
_version_	1718410296592171008

An Efficient and Robust Improved A* Algorithm for Path Planning

Ejemplares similares