Improved A-Star Algorithm for Long-Distance Off-Road Path Planning Using Terrain Data Map

To overcome the limitation of poor processing times for long-distance off-road path planning, an improved A-Star algorithm based on terrain data is proposed in this study. The improved A-Star algorithm for long-distance off-road path planning tasks was developed to identify a feasible path between t...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Zhonghua Hong, Pengfei Sun, Xiaohua Tong, Haiyan Pan, Ruyan Zhou, Yun Zhang, Yanling Han, Jing Wang, Shuhu Yang, Lijun Xu
Formato:	article
Lenguaje:	EN
Publicado:	MDPI AG 2021
Materias:	path planning long distance terrain data map A-Star algorithm efficiency Geography (General) G1-922
Acceso en línea:	https://doaj.org/article/a34b2d9ba69044148e2981ba350b7fb8
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:a34b2d9ba69044148e2981ba350b7fb8
record_format	dspace
spelling	oai:doaj.org-article:a34b2d9ba69044148e2981ba350b7fb82021-11-25T17:53:15ZImproved A-Star Algorithm for Long-Distance Off-Road Path Planning Using Terrain Data Map10.3390/ijgi101107852220-9964https://doaj.org/article/a34b2d9ba69044148e2981ba350b7fb82021-11-01T00:00:00Zhttps://www.mdpi.com/2220-9964/10/11/785https://doaj.org/toc/2220-9964To overcome the limitation of poor processing times for long-distance off-road path planning, an improved A-Star algorithm based on terrain data is proposed in this study. The improved A-Star algorithm for long-distance off-road path planning tasks was developed to identify a feasible path between the start and destination based on a terrain data map generated using a digital elevation model. This study optimised the algorithm in two aspects: data structure, retrieval strategy. First, a hybrid data structure of the minimum heap and 2D array greatly reduces the time complexity of the algorithm. Second, an optimised search strategy was designed that does not check whether the destination is reached in the initial stage of searching for the global optimal path, thus improving execution efficiency. To evaluate the efficiency of the proposed algorithm, three different off-road path planning tasks were examined for short-, medium-, and long-distance path planning tasks. Each group of tasks corresponded to three different off-road vehicles, and nine groups of experiments were conducted. The experimental results show that the processing efficiency of the proposed algorithm is significantly better than that of the conventional A-Star algorithm. Compared with the conventional A-Star algorithm, the path planning efficiency of the improved A-Star algorithm was accelerated by at least 4.6 times, and the maximum acceleration reached was 550 times for long-distance off-road path planning. The simulation results show that the efficiency of long-distance off-road path planning was greatly improved by using the improved algorithm.Zhonghua HongPengfei SunXiaohua TongHaiyan PanRuyan ZhouYun ZhangYanling HanJing WangShuhu YangLijun XuMDPI AGarticlepath planninglong distanceterrain data mapA-Star algorithmefficiencyGeography (General)G1-922ENISPRS International Journal of Geo-Information, Vol 10, Iss 785, p 785 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	path planning long distance terrain data map A-Star algorithm efficiency Geography (General) G1-922
spellingShingle	path planning long distance terrain data map A-Star algorithm efficiency Geography (General) G1-922 Zhonghua Hong Pengfei Sun Xiaohua Tong Haiyan Pan Ruyan Zhou Yun Zhang Yanling Han Jing Wang Shuhu Yang Lijun Xu Improved A-Star Algorithm for Long-Distance Off-Road Path Planning Using Terrain Data Map
description	To overcome the limitation of poor processing times for long-distance off-road path planning, an improved A-Star algorithm based on terrain data is proposed in this study. The improved A-Star algorithm for long-distance off-road path planning tasks was developed to identify a feasible path between the start and destination based on a terrain data map generated using a digital elevation model. This study optimised the algorithm in two aspects: data structure, retrieval strategy. First, a hybrid data structure of the minimum heap and 2D array greatly reduces the time complexity of the algorithm. Second, an optimised search strategy was designed that does not check whether the destination is reached in the initial stage of searching for the global optimal path, thus improving execution efficiency. To evaluate the efficiency of the proposed algorithm, three different off-road path planning tasks were examined for short-, medium-, and long-distance path planning tasks. Each group of tasks corresponded to three different off-road vehicles, and nine groups of experiments were conducted. The experimental results show that the processing efficiency of the proposed algorithm is significantly better than that of the conventional A-Star algorithm. Compared with the conventional A-Star algorithm, the path planning efficiency of the improved A-Star algorithm was accelerated by at least 4.6 times, and the maximum acceleration reached was 550 times for long-distance off-road path planning. The simulation results show that the efficiency of long-distance off-road path planning was greatly improved by using the improved algorithm.
format	article
author	Zhonghua Hong Pengfei Sun Xiaohua Tong Haiyan Pan Ruyan Zhou Yun Zhang Yanling Han Jing Wang Shuhu Yang Lijun Xu
author_facet	Zhonghua Hong Pengfei Sun Xiaohua Tong Haiyan Pan Ruyan Zhou Yun Zhang Yanling Han Jing Wang Shuhu Yang Lijun Xu
author_sort	Zhonghua Hong
title	Improved A-Star Algorithm for Long-Distance Off-Road Path Planning Using Terrain Data Map
title_short	Improved A-Star Algorithm for Long-Distance Off-Road Path Planning Using Terrain Data Map
title_full	Improved A-Star Algorithm for Long-Distance Off-Road Path Planning Using Terrain Data Map
title_fullStr	Improved A-Star Algorithm for Long-Distance Off-Road Path Planning Using Terrain Data Map
title_full_unstemmed	Improved A-Star Algorithm for Long-Distance Off-Road Path Planning Using Terrain Data Map
title_sort	improved a-star algorithm for long-distance off-road path planning using terrain data map
publisher	MDPI AG
publishDate	2021
url	https://doaj.org/article/a34b2d9ba69044148e2981ba350b7fb8
work_keys_str_mv	AT zhonghuahong improvedastaralgorithmforlongdistanceoffroadpathplanningusingterraindatamap AT pengfeisun improvedastaralgorithmforlongdistanceoffroadpathplanningusingterraindatamap AT xiaohuatong improvedastaralgorithmforlongdistanceoffroadpathplanningusingterraindatamap AT haiyanpan improvedastaralgorithmforlongdistanceoffroadpathplanningusingterraindatamap AT ruyanzhou improvedastaralgorithmforlongdistanceoffroadpathplanningusingterraindatamap AT yunzhang improvedastaralgorithmforlongdistanceoffroadpathplanningusingterraindatamap AT yanlinghan improvedastaralgorithmforlongdistanceoffroadpathplanningusingterraindatamap AT jingwang improvedastaralgorithmforlongdistanceoffroadpathplanningusingterraindatamap AT shuhuyang improvedastaralgorithmforlongdistanceoffroadpathplanningusingterraindatamap AT lijunxu improvedastaralgorithmforlongdistanceoffroadpathplanningusingterraindatamap
_version_	1718411877024792576

Improved A-Star Algorithm for Long-Distance Off-Road Path Planning Using Terrain Data Map

Ejemplares similares