{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T22:29:28Z","timestamp":1780525768291,"version":"3.54.1"},"reference-count":21,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2024,7,12]],"date-time":"2024-07-12T00:00:00Z","timestamp":1720742400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100012166","name":"National Key R&amp;D Program of China","doi-asserted-by":"publisher","award":["2023YFB3907103"],"award-info":[{"award-number":["2023YFB3907103"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>Pathfinding for autonomous vehicles in large-scale complex terrain environments is difficult when aiming to balance efficiency and quality. To solve the problem, this paper proposes Hierarchical Path-Finding A* based on Multi-Scale Rectangle, called RHA*, which achieves efficient pathfinding and high path quality for large-scale unequal-weighted maps. Firstly, the original map grid cells were aggregated into fixed-size clusters. Then, an abstract map was constructed by aggregating equal-weighted clusters into rectangular regions of different sizes and calculating the nodes and edges of the regions in advance. Finally, real-time pathfinding was performed based on the abstract map. The experiment showed that the computation time of real-time pathfinding was reduced by 96.64% compared to A* and 20.38% compared to HPA*. The total cost of the generated path deviated no more than 0.05% compared to A*. The deviation value is reduced by 99.2% compared to HPA*. The generated path can be used for autonomous vehicle traveling in off-road environments.<\/jats:p>","DOI":"10.3390\/ijgi13070251","type":"journal-article","created":{"date-parts":[[2024,7,12]],"date-time":"2024-07-12T16:23:41Z","timestamp":1720801421000},"page":"251","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["A Pathfinding Algorithm for Large-Scale Complex Terrain Environments in the Field"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-6661-9930","authenticated-orcid":false,"given":"Luchao","family":"Kui","sequence":"first","affiliation":[{"name":"School of Transportation, Southeast University, Nanjing 211109, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xianwen","family":"Yu","sequence":"additional","affiliation":[{"name":"School of Transportation, Southeast University, Nanjing 211109, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2024,7,12]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"611","DOI":"10.1017\/S0263574713000738","article-title":"A global path planning method for mobile robot based on a three-dimensional-like map","volume":"32","author":"Wang","year":"2014","journal-title":"Robotica"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1565","DOI":"10.1177\/0278364910369715","article-title":"Learning from demonstration for autonomous navigation in complex unstructured terrain","volume":"29","author":"Silver","year":"2010","journal-title":"Int. J. Robot. Res."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1109\/MRA.2010.936946","article-title":"Learning for Autonomous Navigation","volume":"17","author":"Bagnell","year":"2010","journal-title":"IEEE Robot. Autom. Mag."},{"key":"ref_4","first-page":"253","article-title":"Stereo-vision-based terrain mapping for off-road autonomous navigation","volume":"Volume 7332","author":"Rankin","year":"2009","journal-title":"Unmanned Systems Technology XI"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Huertas, A., Matthies, L., and Rankin, A. (2005, January 5\u20137). Stereo-based tree traversability analysis for autonomous off-road navigation. Proceedings of the Seventh IEEE Workshops on Application of Computer Vision, Washington, DC, USA.","DOI":"10.1109\/ACVMOT.2005.111"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Carsten, J., Ferguson, D., and Stentz, A. (2006, January 9\u201315). 3D Field D*: Improved path planning and replanning through three dimensions. Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems, Beijing, China.","DOI":"10.1109\/IROS.2006.282516"},{"key":"ref_7","unstructured":"Lacaze, A., Murphy, K., and DelGiono, M. (2002, January 8\u201312). Autonomous mobility for the Demo III experimental unmanned vehicles. Proceedings of the AUVSI Conference, Orlando, FL, USA."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1177\/0278364906065543","article-title":"Toward reliable off road autonomous vehicles operating in challenging environments","volume":"25","author":"Kelly","year":"2006","journal-title":"Int. J. Robot. Res."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1109\/70.508439","article-title":"Probabilistic roadmaps for path planning in high-dimensional configuration spaces","volume":"12","author":"Kavraki","year":"2006","journal-title":"IEEE Trans. Robot. Autom."},{"key":"ref_10","unstructured":"LaValle, S.M. (1998, January 16\u201320). Rapidly-Exploring Random Tree: A New Tool for Path Planning. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Leuven, Belgium."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Karaman, S., and Frazzoli, E. (2011). Incremental sampling-based algorithms for optimal motion planning. arXiv, 1105\u20131186.","DOI":"10.15607\/RSS.2010.VI.034"},{"key":"ref_12","unstructured":"Jordan, M., and Perez, A. (2024, April 26). Optimal Bidirectional Rapidly-Exploring Random Trees. Computer Science and Artificial Intelligence Laboratory Technical Report 2013. Available online: https:\/\/dspace.mit.edu\/handle\/1721.1\/79884."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1177\/0278364919830554","article-title":"Matrix completion as a post-processing technique for probabilistic roadmaps","volume":"38","author":"Esposito","year":"2019","journal-title":"Int. J. Robot. Res."},{"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":"2829","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","unstructured":"Harabor, D., and Grastien, A. (2011, January 7\u201311). Online graph pruning for pathfinding on grid maps. Proceedings of the AAAI Conference on Artificial Intelligence, San Francisco, CA, USA.","DOI":"10.1609\/aaai.v25i1.7994"},{"key":"ref_17","unstructured":"Deloura, M. (2000). A* Speed Optimizations. Game Programming Gems, Charles River Media."},{"key":"ref_18","unstructured":"Holte, R.C., Perez, M.B., Zimmer, R.M., and MacDonald, A.J. (1996, January 4\u20138). Hierarchical A*: Searching abstraction hierarchies efficiently. Proceedings of the AAAI Conference on Artificial Intelligence, Portland, OR, USA. Available online: https:\/\/aaai.org\/papers\/079-aaai96-079-hierarchical-a-searching-abstraction-hierarchies-efficiently."},{"key":"ref_19","first-page":"1","article-title":"Near-Optimal Hierarchical Pathfinding","volume":"1","author":"Botea","year":"2004","journal-title":"J. Game Dev."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/978-3-642-83539-1_2","article-title":"An Overview of Quadtrees, Octrees, and Related Hierarchical Data Structures","volume":"F40","author":"Samet","year":"1988","journal-title":"Theor. Found. Comput. Graph. CAD"},{"key":"ref_21","unstructured":"Yahja, A., Stentz, A., Singh, S., and Brumitt, B.L. (1998, January 16\u201320). Framed-quadtree path planning for mobile robots operating in sparse environments. Proceedings of the 1998 IEEE International Conference on Robotics and Automation, Leuven, Belgium."}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/13\/7\/251\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T15:16:05Z","timestamp":1760109365000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/13\/7\/251"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,12]]},"references-count":21,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2024,7]]}},"alternative-id":["ijgi13070251"],"URL":"https:\/\/doi.org\/10.3390\/ijgi13070251","relation":{},"ISSN":["2220-9964"],"issn-type":[{"value":"2220-9964","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,7,12]]}}}