面向越野路径规划的多层次六角格网通行模型

doi:10.11947/j.AGCS.2023.20220159

测绘学报 ›› 2023, Vol. 52 ›› Issue (9): 1562-1573.doi: 10.11947/j.AGCS.2023.20220159

面向越野路径规划的多层次六角格网通行模型

陈占龙^1,2,3, 吴贝贝², 王润⁴, 戴薇薇⁵, 徐道柱^6,7, 马超^6,7

1. 中国地质大学(武汉)计算机学院, 湖北武汉 430078;
2. 国家地理信息系统工程技术研究中心, 湖北武汉 430078;
3. 中国地质大学(武汉)地质探测与评估教育部重点实验室, 湖北武汉 430074;
4. 湖北省地质环境总站, 湖北武汉 430034;
5. 中国地质大学(武汉)地理与信息工程学院, 湖北武汉 430078;
6. 西安测绘研究所, 陕西西安 710054;
7. 地理信息工程国家重点实验室, 陕西西安 710054

收稿日期:2022-03-01 修回日期:2023-01-31 发布日期:2023-10-12
通讯作者: 吴贝贝 E-mail:cug_wbb@cug.edu.cn
作者简介:陈占龙(1980-),男,博士,教授,研究方向为空间分析算法、空间推理、地理信息系统软件开发与应用。E-mail:chenzl@cug.edu.cn
基金资助:
国家自然科学基金(41871305);地质探测与评估教育部重点实验室主任基金和中央高校基本科研业务费(GLAB2022ZR06)

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

CHEN Zhanlong^1,2,3, WU Beibei², WANG Run⁴, DAI Weiwei⁵, XU Daozhu^6,7, MA Chao^6,7

1. School of Computer Science, China University of Geoscience, Wuhan 430078, China;
2. National Engineering Research Center of Geographic Information System, Wuhan 430078, China;
3. Key Laboratory of Geological Survey and Evaluation of Ministry of Education, China University of Geosciences, Wuhan 430074, China;
4. Geological Environmental Center of Hubei Province, Wuhan 430034, China;
5. School of Geography and Information Engineering, China University of Geoscience, Wuhan 430078, China;
6. Xi'an Research Institute of Surveying and Mapping, Xi'an 710054, China;
7. State Key Laboratory of Geo-Information Engineering, Xi'an 710054, China

Received:2022-03-01 Revised:2023-01-31 Published:2023-10-12
Supported by:
The National Natural Science Foundation of China (No. 41871305);The Opening Fund of Key Laboratory of Geological Survey and Evaluation of Ministry of Education and the Fundamental Research Funds for the Central Universities (No. GLAB2022ZR06)

摘要/Abstract

摘要： 针对大规模越野环境中规划路径效率低下的问题,本文提出了一种面向越野路径规划的多层次六角格网通行模型,该模型能在缩减格网数据规模、保持规划路径合理性的同时,提升路径规划算法的执行效率。本文首先以六角格网单元为基础,设计通行能力量化规则,赋予每个格网相应的通行能力,构建普通六角格网通行模型;然后,建立多层次格网压缩规则,对通行模型中通行能力相似的邻接格网进行合并及重构格网邻接关系,生成含有不同层次格网的通行模型;最后,针对本文提出的多层次六角格网通行模型,设计了考虑坡度和地表覆盖要素的启发函数,进一步对A^*路径规划算法进行了优化。试验表明,本文提出的多层次六角格网通行模型相较于普通六角格网通行模型,格网数量缩减了53.75%,路径规划所需时间降低了57%。

关键词: 越野路径规划, 最短路径, 六角格网, 多层次, A^*算法, 通行模型

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

中图分类号:

P208

陈占龙, 吴贝贝, 王润, 戴薇薇, 徐道柱, 马超. 面向越野路径规划的多层次六角格网通行模型[J]. 测绘学报, 2023, 52(9): 1562-1573.

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.

参考文献

[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.

面向越野路径规划的多层次六角格网通行模型

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 7

编辑推荐

Metrics

本文评价

[1]	叶鹏, 张雪英, 张春菊. 基于微博文本的灾害事件信息时空过程聚合方法[J]. 测绘学报, 2023, 52(3): 490-500.
[2]	禹文豪, 魏铖, 陈佳鑫. 面向不平衡POI类别分布的电子地图多层次标签预测模型[J]. 测绘学报, 2023, 52(2): 318-328.
[3]	刘呈熠, 武芳, 巩现勇, 行瑞星, 罗登瀚. 规则池塘群的复杂直线模式识别[J]. 测绘学报, 2020, 49(2): 256-266.
[4]	张志然, 刘纪平, 仇阿根, 钱新林, 张福浩. 面向大规模道路网的最短路径近似算法[J]. 测绘学报, 2019, 48(1): 86-94.
[5]	刘铭崴, 朱庆, 朱军, 冯斌, 李赟, 张骏骁, 付萧, 张鹏程, 杨卫军, 宁新稳, 徐婉妍. 多模态时空数据多层次可视化任务模型[J]. 测绘学报, 2018, 47(8): 1098-1104.
[6]	刘小凤吴艳兰胡海. 面状要素的多层次骨架线提取[J]. , 2013, 42(4): 0-0.
[7]	王美玲,程林. 浮动车地图匹配算法研究[J]. 测绘学报, 2012, 41(1): 133-0.