基于四叉树和分层地图的路径规划算法  

Path planning algorithm based on quadtree and hierarchical map

作　　者：邢立宁 黄振华 马超[3] XING Lining;HUANG Zhenhua;MA Chao(Hangzhou Research Institute,Xidian University,Hangzhou,Zhejiang,China 311231;School of Mechanical and Electrical Engineering and Automation,Foshan University of Science and Technology,Foshan,Guangdong,China 528225;School of Digital Media,Shenzhen Institute of Information Technology,Shenzhen,Guangdong,China 518172)

机构地区：[1]西安电子科技大学杭州研究院,浙江杭州311231 [2]佛山大学机电工程与自动化学院,广东佛山528225 [3]深圳信息职业技术学院数字媒体学院,广东深圳518172

出　　处：《深圳信息职业技术学院学报》2024年第5期42-52,共11页Journal of Shenzhen Institute of Information Technology

基　　金：陕西省科技创新团队项目(项目编号:2023-CX-TD-07);广东高校重点领域专项项目(项目编号:2021ZDZX1019);广东省普通高校创新团队及特色创新项目(项目编号:2020KCXTD040,2020KTSCX302)。

摘　　要：在路径规划领域,尽管Dijkstra和A^(*)等传统图搜索算法能确保找到最佳路径,但在处理大规模地图时,这些算法的搜索时间会显著增加。因此,结合地图分解和分层地图技术的新型图搜索路径规划方法提出了更加优化的QH-A^(*)算法。QH-A^(*)算法在离线阶段通过地图分解预处理并标记关键节点,在线阶段利用针对层级地图优化的搜索策略,有效减少了复杂场景下的搜索空间。实验结果显示,QH-A^(*)算法在寻找最短路径方面表现出色,其搜索空间比传统A^(*)算法减少了超过60%,在提高搜索效率的同时,显著优化了搜索范围。其不仅改善了性能,而且为需要处理大规模且复杂的工业自动化仓库、智能交通系统和城市搜救任务等复杂的路径规划提供了一种高效的解决方案。In the field of path planning,although traditional graph search algorithms like Dijkstra and A^(*)ensure the identification of the optimal path,their search time significantly increases when dealing with large-scale maps.To address this issue,this paper introduces the QH-A^(*)algorithm,a novel graph search path planning method that combines map decomposition and hierarchical mapping techniques.In the offline phase,the QH-A^(*)algorithm preprocesses the map decomposition and marks key nodes,while in the online phase,it utilizes a search strategy optimized for hierarchical maps,effectively reducing the search space in complex scenarios.Experimental results demonstrate that the QH-A^(*)algorithm excels in finding the shortest path,reducing the search space by over 60%compared to the traditional A^(*)algorithm,significantly optimizing the search range while enhancing search efficiency.This method not only improves performance,but also provides an efficient solution for handling complex path planning tasks such as large-scale and complex industrial automated warehouses,intelligent transportation systems,and urban search and rescue missions.

关 键 词：路径规划 地图分解 层级地图 移动机器人 QH-A^(*) 

分 类 号：TP242[自动化与计算机技术—检测技术与自动化装置] TP18[自动化与计算机技术—控制科学与工程]