基于交错式栅格粒度地图的非平坦地形环境下无人车辆路径规划

doi:10.3901/JME.260057

摘要/Abstract

摘要： 针对非平坦地形环境下无人车辆路径规划问题，提出一种交错式栅格粒度地图模型，并基于该地图模型建立一种改进的A^*路径规划算法，即交错式栅格粒度A^*（Interleaved granularity A^*,IGA^*）算法。首先，建立一种交错式栅格粒度地图模型，通过两幅子地图交错的方式，存储相关环境信息，生成对应的陡峭度地图，完成对环境信息的理论描述；然后，基于传统A^*算法并结合交错式栅格粒度地图模型，从地形坡度、地面阶跃高度、地形陡峭度三个方面对路径节点进行通过性评估，建立新的代价函数，引导算法避开不适宜通过的地形路径点；最后，建立IGA^*路径规划算法策略。在四种不同的地图环境下对所提出的IGA^*算法进行了测试评价，并与传统A^*算法、文献改进A^*算法进行了对比分析。结果表明，所提出的IGA^*算法能够兼顾算法效率和路径规划质量，相较于传统A^*算法，规划时间、单位路径高程变化、单位路径地面陡峭度变化分别平均可减少65.5%、61.2%、73.2%，与文献改进A^*算法相比，IGA^*算法在平均减少87.3%规划时间的同时，单位路径高程变化、单位路径地面陡峭度变化还可以分别平均减少18.2%、38.1%，能够实现更高效、更安全的路径规划。

关键词: 无人车辆, 路径规划, 非平坦地形, A^*算法, 数字高程模型

Abstract: For the unmanned vehicle path planning problem in uneven terrain environment, an interleaved granularity map model is proposed, and then a path planning algorithm named Interleaved granularity A^*(IGA^*) algorithm is established. First, an interleaved granularity map model is established to store relevant environmental information by interleaving two sub-maps to generate the corresponding steepness map and complete the theoretical description of environmental information. Then, based on the traditional A^* algorithm, combined with the interleaved granularity map model, the path nodes are evaluated in terms of terrain slope, ground step height, and terrain steepness for passability, and a new cost function is established to guide the algorithm to avoid terrain path points that are not suitable for passing, and the IGA^* algorithm path planning strategy is established finally. The proposed IGA^* algorithm is tested and evaluated in four different map conditions and compared with the traditional A^* algorithm and the improved A^* algorithm reported in literature. The results reveal that the proposed IGA^* algorithm can well balance the algorithm efficiency and the path quality, and the planning time can be reduced by 65.5% on average, the change of unit path elevation can be reduced by 61.2% on average, and the change of unit path ground steepness can be reduced by 73.2% on average. Compared with the improved A^* algorithm reported in literatures,the planning time can be reduced by 87.3% on average, the change of unit path elevation can be reduced by 18.2% on average, and the change of unit path ground steepness can be reduced by 38.1% on average,and thus more efficient and safer path planning can be achieved.

Key words: unmanned vehicle, path planning, uneven terrain, A^* algorithm, digital elevation model

中图分类号:

U471
TP242

杨秀建, 袁志豪. 基于交错式栅格粒度地图的非平坦地形环境下无人车辆路径规划[J]. 机械工程学报, 2026, 62(2): 313-328.

YANG Xiujian, YUAN Zhihao. Path Planning for Unmanned Vehicle in Uneven Terrain Environment Based on the Interleaved Granularity Map Method[J]. Journal of Mechanical Engineering, 2026, 62(2): 313-328.

参考文献

[1] 中华人民共和国科学技术部.科技部关于支持建设新一代人工智能示范应用场景的通知[EB/OL].(2022-08-15)[2023-11-05]. https://www.most.gov.cn/xxgk/xinxifenlei/fdzdgknr/qtwj/qtwj2022/202208/t20220815_181874.html.Ministry of Science and Technology of the People’s Republic of China. Circular of the ministry of science and technology on supporting the construction of newgeneration artificial intelligence demonstration application scenarios[EB/OL].(2022-08-15)[2023-11-05]. https://www.most.gov.cn/xxgk/xinxifenlei/fdzdgknr/qtwj/qtwj2022/202208/t20220815_181874.html.
[2] WANG L,LEI T,SI J G,et al. Speed consensus control for a parallel six-wheel-legged robot on uneven terrain[J].ISA Transactions,2021,129:628-641.
[3] ALGFOOR Z A,SUNAR M S,ABDULLAH A. A new weighted pathfinding algorithms to reduce the search time on grid maps[J]. Expert Systems with Applications,2017,71:319-331.
[4] SARANYA C,UNNIKRISHNAN M,ALI S A,et al.Terrain based D*algorithm for path planning[J]. IFAC PapersOnLine,2016,49(1):178-182.
[5] JONES D,HOLLINGER G. Planning energy-efficient trajectories in strong disturbances[J]. IEEE Robotics&Automation Letters,2017,2(4):2080-2087.
[6] KIM H,KIM B K. Online minimum-energy trajectory planning and control on a straight-line path for three-wheeled omnidirectional mobile robots[J]. IEEE Transactions on Industrial Electronics,2014,61(9):4771-4779.
[7] SAEED R A,RECUPERO D R,REMAGNINO P. A boundary node method for path planning of mobile robots[J]. Robotics and Autonomous Systems,2020,123:103320.
[8] 张浩杰,龚建伟,姜岩,等.基于变维度状态空间的增量启发式路径规划方法研究[J].自动化学报,2013,39(10):1602-1610.ZHANG Haojie,GONG Jianwei,JIANG Yan,et al.Research on incremental heuristic path planning method based on variable dimensional state space[J]. Journal of Automation,2013,39(10):1602-1610.
[9] BELTER D,WIETRZYKOWSKI J,SKRZYPCZYŃSKI P. Employing natural terrain semantics in motion planning for a multi-legged robot[J]. Journal of Intelligent&Robotic Systems,2019,93(3-4):723-743.
[10] 闫飞,庄严,白明,等.基于拓扑高程模型的室外三维环境建模与路径规划[J].自动化学报,2010,36(11):1493-1501.YAN Fei,ZHUANG Yan,BAI Ming,et al. Outdoor 3D environment modeling and path planning based on topological elevation model[J]. Journal of Automation,2010,36(11):1493-1501.
[11] 黄志清,李鼎鑫,王庆文.非平坦地形下移动机器人安全路径规划[J].控制与决策,2022,37(2):323-330.HUANG Zhiqing,LI Dingxin,WANG Qingwen. Safe path planning for mobile robots in non-flat terrain[J].Control and Decision,2022,37(2):323-330.
[12] SAAD M, SALAMEH A I, ABDALLAH S.Energy-efficient shortest path planning on uneven terrains:A composite routing metric approach[C] //2019IEEE International Symposium on Signal Processing and Information Technology(ISSPIT). Ajman. New York:IEEE,2019:1-6.
[13] 殷建军,董文龙,梁利华,等.复杂环境下农业机器人路径规划优化方法[J].农业机械学报,2019,50(5):17-22.YIN Jianjun,DONG Wenlong,LIANG Lihua,et al.Optimization method for path planning of agricultural robots in complex environment[J]. Journal of Agricultural Machinery,2019,50(5):17-22.
[14] GANGANATH N, CHENG C T, TSE C K. A constraint-aware heuristic path planner for finding energy-efficient paths on uneven terrains[J]. IEEE Transactions on Industrial Informatics,2015,11(3):601-611.
[15] LIU Q H,ZHAO L J,TAN Z B,et al. Global path planning for autonomous vehicles in off-road environment via an A-star algorithm[J]. International Journal of Vehicle Autonomous Systems,2017,13(4):330-339.
[16] 张慧,荣学文,李贻斌,等.四足机器人地形识别与路径规划算法[J].机器人,2015,37(5):546-556.ZHANG Hui,RONG Xuewen,LI Yibin,et al. Algorithm for terrain recognition and path planning of quadruped robot[J]. Robot,2015,37(5):546-556.
[17] 冯世盛,徐青,朱新铭,等.基于地形数据的长距离越野路径快速规划方法研究[J].地球信息科学学报,2022,24(9):1742-1754.FENG Shisheng,XU Qing,ZHU Xinming,et al. Research on fast planning method for long-distance cross-country paths based on terrain data[J]. Journal of Geo-Information Science,2022,24(9):1742-1754.
[18] ZHANG B,LI G,ZHENG Q,et al. Path planning for wheeled mobile robot in partially known uneven terrain[J].Sensors,2022,22(14):5217.
[19] 徐鹏,丁亮,高海波,等.考虑足地作用的足式机器人环境表征与路径规划[J].机械工程学报,2020,56(23):21-33.XU Peng,DING Liang,GAO Haibo,et al. Environmental characterization and path planning for footed robots considering foot-ground effects[J]. Journal of Mechanical Engineering,2020,56(23):21-33.
[20] HART P E,NILSSON N J,RAPHAEL B. A formal basis for the heuristic determination of minimum cost paths[J].IEEE Transactions on Systems Science&Cybernetics,1972,4(2):28-29.
[21] NASA JPL. NASADEM MERGED DEM Global 1 arc second V001[DB/OL].(2000-02-21)[2023-11-05].https://doi.org/10.5067/MEaSUREs/NASADEM/NASADEM_HGT.001.