Статья

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

Zhonghua HongThe College of Information Technology, Shanghai Ocean University, 999 Huchenghuan Road, Pudong New District, Shanghai 201306, ChinaPengfei SunThe College of Information Technology, Shanghai Ocean University, 999 Huchenghuan Road, Pudong New District, Shanghai 201306, ChinaXiaohua TongCollege of Surveying and Geo-Informatics, Tongji University, 1239 Siping Road, Shanghai 200092, ChinaHaiyan PanThe College of Information Technology, Shanghai Ocean University, 999 Huchenghuan Road, Pudong New District, Shanghai 201306, ChinaRuyan ZhouThe College of Information Technology, Shanghai Ocean University, 999 Huchenghuan Road, Pudong New District, Shanghai 201306, ChinaYun ZhangThe College of Information Technology, Shanghai Ocean University, 999 Huchenghuan Road, Pudong New District, Shanghai 201306, ChinaYanling HanThe College of Information Technology, Shanghai Ocean University, 999 Huchenghuan Road, Pudong New District, Shanghai 201306, ChinaJing WangThe College of Information Technology, Shanghai Ocean University, 999 Huchenghuan Road, Pudong New District, Shanghai 201306, ChinaShuhu YangThe College of Information Technology, Shanghai Ocean University, 999 Huchenghuan Road, Pudong New District, Shanghai 201306, ChinaLijun XuThe College of Information Technology, Shanghai Ocean University, 999 Huchenghuan Road, Pudong New District, Shanghai 201306, China

2021en

ABI

Аннотация

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.

Перевод пока недоступен

Идентификаторы

DOI: 10.3390/ijgi10110785

Цитирования и источники

Цитирований: 2Использованных источников: 0

Показатели — AkademScholar