Multi-hierarchy hexagonal grid traffic model for off-road path planning

doi:10.11947/j.AGCS.2023.20220159

Abstract

Abstract: Aiming at the low efficiency of path planning in a large-scale off-road environment, this paper proposes a multi-hierarchy hexagonal grid traffic model for off-road path planning. The model can improve the execution efficiency of the path planning algorithm while reducing the grid data scale and maintaining the rationality of the planned path. Based on the hexagonal grid unit, this paper designs the quantification rule of traffic capacity gives each grid the corresponding traffic capacity, constructs the traffic model of ordinary hexagonal grid, and then establishes the multi-hierarchy grid compression rules. The adjacent grids are merged, and the adjacent grid relationship is reconstructed to generate a traffic model containing different hierarchy of grids. Finally, according to the multi-hierarchy hexagonal grid traffic model proposed in this paper, a heuristic function considering the elements of slope and ground cover is designed, and the A^* path planning algorithm is further optimized. Experiments show that the multi-hierarchy hexagonal grid traffic model proposed in this paper reduces the number of grids by 53.75% and the time required for path planning by 57% compared with the ordinary hexagonal grid traffic model.

Key words: off-road path planning, shortest path, hexagonal grid, multi-hierarchy, A^* algorithm, traffic model

CLC Number:

P208

CHEN Zhanlong, WU Beibei, WANG Run, DAI Weiwei, XU Daozhu, MA Chao. Multi-hierarchy hexagonal grid traffic model for off-road path planning[J]. Acta Geodaetica et Cartographica Sinica, 2023, 52(9): 1562-1573.

References

[1] 王文刚, 张秀丽, 王曦鸣. 基于模糊化环境建模的无人车路径规划研究[J]. 国防制造技术, 2009(3): 53-56. WANG Wengang, ZHANG Xiuli, WANG Ximing. Path planning for unmanned ground vehicle based on fuzzy obstacles environment model[J]. Defense Manufacturing Technology, 2009(3): 53-56.
[2] KUNDRA H, SOOD M. Cross-country path finding using hybrid approach of PSO and BBO[J]. International Journal of Computer Applications, 2010, 7(6): 15-19.
[3] 王书勤, 黄茜. 军事定向越野路径优化问题建模及混合蚁群算法求解[J]. 运筹与管理, 2018, 27(4): 105-111. WANG Shuqin, HUANG Qian. Route optimization model of military orienteering and its solution to a hybrid ant colony algorithm[J]. Operations Research and Management Science, 2018, 27(4): 105-111.
[4] 陈长林,孙迈,宋顺达.基于扩展Voronoi图的兵力机动路线决策[J].指挥控制与仿真,2010,32(3):24-27. CHEN Changlin, SEN Mai, SONG Shunda. Decision-making of forces maneuver path based-on extended Voronoi diagram [J]. Command Control & Simulation, 2010,32(3):24-27.
[5] 张欣, 李培宁, 顾明强. 计算机兵棋中越野机动路径网络分析[J]. 地理空间信息, 2017, 15(3): 14-16. ZHANG Xin, LI Peining,GU Mingqiang. Cross-country maneuver path network analysis of the computer wargame[J]. Geospatial Information, 2017, 15(3): 14-16.
[6] ZHUO Qunlong. Dynamic path planning of mobile robot based on ant colony algorithm[J]. International Journal of Reasoning-based Intelligent Systems, 2018, 10(2): 122-127.
[7] HUSSEIN A, MARÍN-PLAZA P, MARTÍN D, et al. Autonomous off-road navigation using stereo-vision and laser-rangefinder fusion for outdoor obstacles detection[C]//Proceedings of 2016 IEEE Intelligent Vehicles Symposium (IV). New York: ACM Press, 2016: 104-109.
[8] NEDJATI A, IZBIRAK G, VIZVARI B, et al. Complete coverage path planning for a multi-UAV response system in post-earthquake assessment[J]. Robotics, 2016, 5(4): 26.
[9] DENG Lizheng, YUAN Hongyong, HUANG Lida, et al. Post-earthquake search via an autonomous UAV: hybrid algorithm and 3D path planning[C]// Proceedings of the 14th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery. Huangshan: IEEE, 2018: 1329-1334.
[10] KUMAR DEBNATH S, OMAR R, ABDUL LATIP N B, et al. A review on graph search algorithms for optimal energy efficient path planning for an unmanned air vehicle[J]. Indonesian Journal of Electrical Engineering and Computer Science, 2019, 15(2): 743-749.
[11] 王艳萍, 刘文堂, 赵宜宾, 等. 多发点情况下地震救援路径的优选算法[J]. 世界地震工程, 2010, 26(1): 121-124. WANG Yanping, LIU Wentang, ZHAO Yibin, et al. Optimization algorithm of earthquake rescue routes for multi-start conditions[J]. World Earthquake Engineering, 2010, 26(1): 121-124.
[12] 孙玉泽. 无人轮式车辆越野路面全局路径规划与轨迹跟踪[D]. 长春: 吉林大学, 2020. SUN Yuze. Global path planning and trajectory tracking of unmanned wheeled vehicles on terrains[D]. Changchun: Jilin University, 2020.
[13] 汪永红, 崔铁军, 吴正升. 嵌入式GIS中最优路径规划算法研究与实现[J]. 测绘科学, 2010, 35(2): 147-149. WANG Yonghong, CUI Tiejun, WU Zhengsheng. Research and implementation of the optimal route planning algorithm in embedded GIS[J]. Science of Surveying and Mapping, 2010, 35(2): 147-149.
[14] PAPADAKIS P. Terrain traversability analysis methods for unmanned ground vehicles: a survey[J]. Engineering Applications of Artificial Intelligence, 2013, 26(4): 1373-1385.
[15] 蒋键. 智能车辆越野环境路径规划[D]. 北京: 北京理工大学, 2016. JIANG Jian. Path planning of intelligent vehicles on uneven terrain[D]. Beijing: Beijing Institute of Technology, 2016.
[16] 林辉, 彭长辉. 地理信息系统中栅格单元大小和形状的选择[J]. 遥感信息, 2001, 16(1): 21-23. LIN Hui, PENG Changhui. The role of raster pixel size and shape in geographic information system[J]. Remote Sensing Information, 2001, 16(1): 21-23.
[17] 王维才, 艾廷华, 晏雄锋, 等. 多约束条件下的正六边形格网室内路径规划[J]. 武汉大学学报(信息科学版), 2020, 45(1): 111-118. WANG Weicai, AI Tinghua, YAN Xiongfeng, et al. Indoor route planning under regular hexagonal grid considering multi-constraints[J]. Geomatics and Information Science of Wuhan University, 2020, 45(1): 111-118.
[18] 范林林, 华一新. 一种基于六角格的越野通行方法[J]. 测绘通报, 2017(2): 25-29, 59. FAN Linlin, HUA Yixin. A method of cross-country access based on hexagonal grid[J]. Bulletin of Surveying and Mapping, 2017(2): 25-29, 59.
[19] 翁敏, 毋河海, 李林燕. 层次空间推理的机制及其在路径寻找方面的应用[J]. 测绘科学, 2006, 31(5): 119-121. WENG Min, WU Hehai, LI Linyan. Hierarchical spatial reasoning and its application to wayfinding[J]. Science of Surveying and Mapping, 2006, 31(5): 119-121.
[20] 张志然, 刘纪平, 仇阿根, 等. 面向大规模道路网的最短路径近似算法[J]. 测绘学报, 2019, 48(1): 86-94. DOI: 10.11947/j.AGCS.2019.20180007. ZHANG Zhiran, LIU Jiping, QIU Agen, et al. The shortest path approximation algorithm for large scale road network[J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(1): 86-94.DOI: 10.11947/j.AGCS.2019.20180007.
[21] 汪永红. 多尺度道路网路径规划关键技术及应用研究[D]. 郑州:信息工程大学, 2011. WANG Yonghong. Study of key technique and application of the optimal route based on multi-scale road network[D]. Zhengzhou: Information Engineering University,2011.
[22] DELLING D, SANDERS P, SCHULTES D, et al. Engineering route planning algorithms[M]//Algorithmics of Large and Complex Networks. Berlin: Springer, 2009: 117-139.
[23] XU Qing, FENG Shisheng, SUN Qun, et al. A method of planning disaster emergency rescue paths in road-free environment[EB/OL].[2022-03-01]. http://www.hindawi.com/journals/cin/2022/2987852/.
[24] 吴天羿, 许继恒, 刘建永, 等. 基于改进A^*算法的越野路径规划研究[J]. 计算机应用研究, 2013, 30(6): 1724-1726. WU Tianyi, XU Jiheng, LIU Jianyong, et al. Research of cross-country path planning based on improved A^* algorithm[J]. Application Research of Computers, 2013, 30(6): 1724-1726.
[25] LIU Qinghe, ZHAO Lijun, TAN Zhibin, 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.
[26] 武丽丽, 华一新, 徐青. 基于六角格的陆地边界环境模型构建方法研究[J]. 测绘与空间地理信息, 2013, 36(2): 22-26. WU Lili, HUA Yixin, XU Qing. Study on hexagon-based land boundary environment model[J]. Geomatics & Spatial Information Technology, 2013, 36(2): 22-26.
[27] 周成军, 张锦明, 范嘉宾, 等. 训练模拟系统中地形量化模型的探讨[J]. 测绘科学技术学报, 2010, 27(2): 149-152. ZHOU Chengjun, ZHANG Jinming, FAN Jiabin, et al. Research terrain measured model applied in the training simulation system[J]. Journal of Geomatics Science and Technology, 2010, 27(2): 149-152.
[28] BRODSKY I. H3: hexagonal hierarchical geospatial indexing system[EB/OL].[2022-03-01]. http://www.uber.com/blog/h3/.
[29] RIEDEL S L, PITZ G F. Utilization-oriented evaluation of decision support systems[J]. IEEE Transactions on Systems, Man and Cybernetics, 1986, 16(6): 980-996.
[30] MUSIAKA Ƚ, NALEJ M. Application of GIS tools in the measurement analysis of urban spatial layouts using the square grid method[J]. ISPRS International Journal of Geo-Information, 2021, 10(8): 558
[31] 范林林. 基于六角格网的越野路径规划技术方法研究[D]. 郑州:信息工程大学, 2017. FAN Linlin. Research on cross-country path planning technology based on hexagonal grid[D]. Zhengzhou: Information Engineering University, 2017.
[32] 李坤伟, 游雄, 张欣, 等. 基于多源数据的土壤越野通行性评估[J]. 测绘科学技术学报, 2018, 35(2): 206-210. LI Kunwei, YOU Xiong, ZHANG Xin, et al. Evaluation of soil trafficability based on multi-source data[J]. Journal of Geomatics Science and Technology, 2018, 35(2): 206-210.
[33] RYBANSKY M. Soil trafficability analysis[C]//Proceedings of 2015 International Conference on Military Technologies. Brno: IEEE, 2015: 1-5.
[34] HART P, NILSSON N, RAPHAEL B. A formal basis for the heuristic determination of minimum cost paths[J]. IEEE Transactions on Systems Science and Cybernetics, 1968, 4(2): 100-107.
[35] BOMERS A, SCHIELEN R J, HULSCHER S H. The influence of grid shape and grid size on hydraulic river modelling performance[J]. Environmental Fluid Mechanics, 2019, 19(5): 1273-1294.