{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,25]],"date-time":"2026-06-25T16:03:59Z","timestamp":1782403439171,"version":"3.54.5"},"reference-count":30,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2021,11,17]],"date-time":"2021-11-17T00:00:00Z","timestamp":1637107200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Key R&amp;D Program of China","award":["2018YFB0505400"],"award-info":[{"award-number":["2018YFB0505400"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["41871325"],"award-info":[{"award-number":["41871325"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.3390\/ijgi10110785","type":"journal-article","created":{"date-parts":[[2021,11,17]],"date-time":"2021-11-17T21:32:07Z","timestamp":1637184727000},"page":"785","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":96,"title":["Improved A-Star Algorithm for Long-Distance Off-Road Path Planning Using Terrain Data Map"],"prefix":"10.3390","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0045-1066","authenticated-orcid":false,"given":"Zhonghua","family":"Hong","sequence":"first","affiliation":[{"name":"The College of Information Technology, Shanghai Ocean University, 999 Huchenghuan Road, Pudong New District, Shanghai 201306, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pengfei","family":"Sun","sequence":"additional","affiliation":[{"name":"The College of Information Technology, Shanghai Ocean University, 999 Huchenghuan Road, Pudong New District, Shanghai 201306, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaohua","family":"Tong","sequence":"additional","affiliation":[{"name":"College of Surveying and Geo-Informatics, Tongji University, 1239 Siping Road, Shanghai 200092, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Haiyan","family":"Pan","sequence":"additional","affiliation":[{"name":"The College of Information Technology, Shanghai Ocean University, 999 Huchenghuan Road, Pudong New District, Shanghai 201306, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ruyan","family":"Zhou","sequence":"additional","affiliation":[{"name":"The College of Information Technology, Shanghai Ocean University, 999 Huchenghuan Road, Pudong New District, Shanghai 201306, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yun","family":"Zhang","sequence":"additional","affiliation":[{"name":"The College of Information Technology, Shanghai Ocean University, 999 Huchenghuan Road, Pudong New District, Shanghai 201306, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0682-9157","authenticated-orcid":false,"given":"Yanling","family":"Han","sequence":"additional","affiliation":[{"name":"The College of Information Technology, Shanghai Ocean University, 999 Huchenghuan Road, Pudong New District, Shanghai 201306, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jing","family":"Wang","sequence":"additional","affiliation":[{"name":"The College of Information Technology, Shanghai Ocean University, 999 Huchenghuan Road, Pudong New District, Shanghai 201306, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9967-7756","authenticated-orcid":false,"given":"Shuhu","family":"Yang","sequence":"additional","affiliation":[{"name":"The College of Information Technology, Shanghai Ocean University, 999 Huchenghuan Road, Pudong New District, Shanghai 201306, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lijun","family":"Xu","sequence":"additional","affiliation":[{"name":"The College of Information Technology, Shanghai Ocean University, 999 Huchenghuan Road, Pudong New District, Shanghai 201306, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2021,11,17]]},"reference":[{"key":"ref_1","first-page":"15","article-title":"Cross-country path finding using hybrid approach of PSO and BBO","volume":"7","author":"Kundra","year":"2010","journal-title":"Int. J. Comput. Appl. Technol."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Liang, H., Bai, H., Sun, R., Sun, R., and Li, C. (2017, January 26\u201328). Three-dimensional path planning based on DEM. Proceedings of the 36th Chinese Control Conference (CCC), Dalian, China.","DOI":"10.23919\/ChiCC.2017.8028307"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Korkmaz, M., and Durdu, A. (2018, January 1). Comparison of optimal path planning algorithms. Proceedings of the 2018 14th International Conference on Advanced Trends in Radioelecrtronics, Telecommunications and Computer Engineering (TCSET), Lviv-Slavske, Ukraine.","DOI":"10.1109\/TCSET.2018.8336197"},{"key":"ref_4","unstructured":"Dalton, A.J. (2008). Autonomous Vehicle Path Planning with Remote Sensing Data. [Master Thesis, Virginia Polytechnic Institute and State University]."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1016\/j.neucom.2017.12.015","article-title":"Car-like mobile robot path planning in rough terrain using multi-objective particle swarm optimization algorithm","volume":"282","author":"Wang","year":"2018","journal-title":"Neurocomputing"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"7459","DOI":"10.1109\/TII.2020.2974252","article-title":"Accurate and Efficient Indoor Pathfinding Based on Building Information Modeling Data","volume":"16","author":"Zhou","year":"2020","journal-title":"IEEE Trans. Ind. Inform."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1111\/phor.12309","article-title":"A precise visual localisation method for the Chinese Chang\u2019e-4 Yutu-2 rover","volume":"35","author":"Ma","year":"2020","journal-title":"Photogramm. Rec."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1016\/j.procs.2018.01.054","article-title":"Grid path planning with deep reinforcement learning: Preliminary results","volume":"123","author":"Panov","year":"2018","journal-title":"Procedia Comput. Sci."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1105","DOI":"10.1007\/s42405-020-00262-x","article-title":"Global Path Planning of Lunar Rover Under Static and Dynamic Constraints","volume":"21","author":"Bai","year":"2020","journal-title":"Int. J. Aeronaut. Space Sci."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1504\/IJVAS.2017.087148","article-title":"Global path planning for autonomous vehicles in off-road environment via an A-star algorithm","volume":"13","author":"Liu","year":"2017","journal-title":"Int. J. Veh. Auton. Syst."},{"key":"ref_11","first-page":"97","article-title":"Optimal path planning using RRT * based approaches: A survey and future directions","volume":"7","author":"Noreen","year":"2016","journal-title":"Int. J. Adv. Comput. Sci. Appl."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1109\/3477.484436","article-title":"Ant system: Optimization by a colony of cooperating agents","volume":"26","author":"Dorigo","year":"1996","journal-title":"IEEE Trans. Syst. Man Cybern. Part B Cybern."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/s00500-006-0068-4","article-title":"Multiple objective genetic algorithms for path-planning optimization in autonomous mobile robots","volume":"11","author":"Castillo","year":"2007","journal-title":"Soft Comput."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connexion with graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","article-title":"A formal basis for the heuristic determination of minimum cost paths","volume":"4","author":"Hart","year":"1968","journal-title":"IEEE Trans. Syst. Sci. Cybern."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/j.apor.2018.12.001","article-title":"Smoothed A * algorithm for practical unmanned surface vehicle path planning","volume":"83","author":"Song","year":"2019","journal-title":"Appl. Ocean Res."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/j.proeng.2014.12.098","article-title":"Path planning with modified a star algorithm for a mobile robot","volume":"96","author":"Babinec","year":"2014","journal-title":"Procedia Eng."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Zhang, Y., Li, L.L., Lin, H.C., Ma, Z., and Zhao, J. (2017, January 20\u201322). Development of path planning approach based on improved A-star algorithm in AGV system. Proceedings of the International Conference on Internet of Things as a Service, Taichung, Taiwan, China.","DOI":"10.1007\/978-3-030-00410-1_32"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Shang, E., Dai, B., Nie, Y., Zhu, Q., Xiao, L., and Zhao, D. (2020, January 24). A Guide-line and Key-point based A-star Path Planning Algorithm For Autonomous Land Vehicles. Proceedings of the 23rd International Conference on Intelligent Transportation Systems (ITSC), Rhodes, Greece.","DOI":"10.1109\/ITSC45102.2020.9294336"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Wang, C., Wang, L., and Qin, J. (2015, January \u201310). Path planning of automated guided vehicles based on improved A-Star algorithm. Proceedings of the International Conference on Information and Automation (ICIA), Lijiang, China.","DOI":"10.1109\/ICInfA.2015.7279630"},{"key":"ref_21","first-page":"903","article-title":"Mobile Robot Path Planning Based on an Improved A * Algorithm","volume":"40","author":"Zhao","year":"2018","journal-title":"Robot"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Zambrano-Martinez, J.L., Calafate, C.T., Soler, D., Lemus-Z\u00fa\u00f1iga, L.G., Cano, J.C., Manzoni, P., and Gayraud, T. (2019). A centralized route-management solution for autonomous vehicles in urban areas. Electronics, 8.","DOI":"10.3390\/electronics8070722"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Xu, P.F., Ding, Y.X., and Luo, J.C. (2021). Complete Coverage Path Planning of an Unmanned Surface Vehicle Based on a Complete Coverage Neural Network Algorithm. J. Mar. Sci. Eng., 9.","DOI":"10.3390\/jmse9111163"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Borkowski, P., Pietrzykowski, Z., and Magaj, J. (2021). The Algorithm of Determining an Anti-Collision Manoeuvre Trajectory Based on the Interpolation of Ship\u2019s State Vector. Sensors, 21.","DOI":"10.3390\/s21165332"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Wang, H., Zhou, J., Zheng, G., and Yun, L. (2014, January 28\u201330). HAS: Hierarchical A-Star Algorithm for Big Map Navigation in Special Areas. Proceedings of the International Conference on Digital Home (ICDH), Guangzhou, China.","DOI":"10.1109\/ICDH.2014.49"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Al Zoubi, O., and Awad, M. (2018, January 18\u201319). Dynamic Area Search with Shared Memory: A Meta-Framework to Improve Pathfinding Algorithms. Proceedings of the International Conference on Innovations in Information Technology (IIT), Al Ain, United Arab Emirates.","DOI":"10.1109\/INNOVATIONS.2018.8606025"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0004-3702(89)90069-6","article-title":"BS\u2217: An admissible bidirectional staged heuristic search algorithm","volume":"38","author":"Kwa","year":"1989","journal-title":"Artif. Intell."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"749","DOI":"10.1109\/TPEL.2006.872374","article-title":"Parametric design of the traction motor and energy storage for series hybrid off-road and military vehicles","volume":"21","author":"Gao","year":"2006","journal-title":"IEEE Trans. Power Electron."},{"key":"ref_29","first-page":"3592902","article-title":"Research on Characteristics of Tracked Vehicle Steering on Slope","volume":"2021","author":"Zhang","year":"2021","journal-title":"Math. Probl. Eng."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/j.jterra.2008.09.002","article-title":"Design and mobility evaluation of tracked lunar vehicle","volume":"46","author":"Wakabayashi","year":"2009","journal-title":"J. Terramechanics"}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/10\/11\/785\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:31:47Z","timestamp":1760167907000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/10\/11\/785"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,17]]},"references-count":30,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2021,11]]}},"alternative-id":["ijgi10110785"],"URL":"https:\/\/doi.org\/10.3390\/ijgi10110785","relation":{},"ISSN":["2220-9964"],"issn-type":[{"value":"2220-9964","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,17]]}}}