面向山地徒步应急救援路径规划的改进蚁群算法研究

doi:10.12082/dqxxkx.2023.220535

地球信息科学学报 ›› 2023, Vol. 25 ›› Issue (1): 90-101.doi: 10.12082/dqxxkx.2023.220535

• 地球信息科学理论与方法 • 上一篇下一篇

面向山地徒步应急救援路径规划的改进蚁群算法研究

伍跃飞¹^,²(), 李建微¹^,²^,^*(), 毕胜¹^,², 朱馨¹^,², 王前锋³

1.福州大学物理信息与工程学院，福州 350000
2.福州大学数字中国研究院（福建），福州 350000
3.福州大学环境与安全工程学院，福州 350000

收稿日期:2022-07-21 修回日期:2022-09-19 出版日期:2023-01-25 发布日期:2023-03-25
通讯作者: *李建微（1979— ），男，福建龙岩人，副研究员，主要从事森林火灾蔓延模型和智能优化算法研究。 Email: lwticq@163.com
作者简介:伍跃飞（1997— ），男，浙江金华人，硕士生，主要从事智能优化算法和三维虚拟地球技术研究。Email: 1620584767@qq.com
基金资助:
国家自然科学基金项目(32071776);国家自然科学基金项目(41571490);国家重点研发计划项目(2022YFC3003000);福建省自然科学基金项目(2020J01465)

Research on Improved Ant Colony Algorithm for Mountain Hiking Emergency Rescue Path Planning

WU Yuefei¹^,²(), LI Jianwei¹^,²^,^*(), BI Sheng¹^,², ZHU Xin¹^,², WANG Qianfeng³

1. College of Physics and Information Engineering,Fuzhou University, Fuzhou 350000, China
2. The Academy of Digital China(Fujian), Fuzhou University, Fuzhou 350000, China
3. College of Environment and Safety Engineering, Fuzhou University,Fuzhou 350000, China

Received:2022-07-21 Revised:2022-09-19 Online:2023-01-25 Published:2023-03-25
Contact: LI Jianwei
Supported by:
National Natural Science Foundation of China(32071776);National Natural Science Foundation of China(41571490);National Key Research and Development Programe of China(2022YFC3003000);Natural Science Foundation of Fujian Province, China(2020J01465)

摘要/Abstract

摘要：

当消防事故发生在无明显道路或道路稀疏的野外复杂山区时，如何在复杂山地环境中规划安全、快速通过的路线至关重要。针对蚁群算法在复杂山地路径规划中容易陷入局部最优以及搜索时间较长的问题，本文提出一种适用于细粒度野外山地环境的徒步应急救援路径规划算法。本文首先根据已有文献分析地表信息与人类运动速度之间的关系，综合地表灌木盖度与地形坡度因素设计寻优算法的目标函数和启发函数；接着采用定向范围视野的蚂蚁搜索方式，决定蚁群算法寻优过程中每一步的网格选择；最后采用拉普拉斯分布调整初始信息素、添加隔离信息素、融合遗传算子与分组更新常规信息素的方法改进蚁群算法。将算法应用到400 $×$ 400、1000 $×$ 1000、5000 $×$ 5000、10 000 $×$ 10 000网格数的野外山地环境进行实验对比，实验结果表明，采用定向范围视野与优化启发函数的各蚁群算法在四组实验中均能得到可行路径，验证了方法的有效性；本文算法求解的路径质量优于另外三种算法，在四组实验中分别提高了0.52%~4.95%、4.71%~5.39%、2.26%~13.11%、3.84%~9.16%；此外，在野外三维山地环境中，定向范围视野的搜索方式缩减了搜索空间，有效提高算法的计算效率，搜索速度比八连通结合禁忌表的搜索方式更快，平均耗时降低了90%以上。该算法适用于大型三维山地场景的徒步路径规划研究，降低规划时间，提高路径质量，为无路网三维山地徒步路径寻优工作提供技术支撑。

关键词: 三维山地环境, 野外应急救援, DEM, 栅格法, 徒步路径规划, 山地徒步可通行性, 蚁群算法, 遗传算法

Abstract:

When a firefighting incident occurs in a wild complex mountain with no obvious roads or sparse roads, it is crucial to plan a safe and fast route through the complex mountain environment. Aiming at the problem that Ant Colony Optimization (ACO) is easy to fall into local optimum and the search time is long for complex mountain path planning, our study proposes an ACO algorithm for hiking emergency rescue path planning, which is suitable for fine-grained wild mountain environments. Firstly, our study analyzed the relationship between surface information and human movement speed based on existing literature and designed the objective function and heuristic function of the optimization algorithm considering two factors: surface shrub cover and terrain slope. Then, we used a combination of plane and field of view ant search combined with heuristic function and pheromone concentration to determine the next grid to be selected in the optimization process of the improved algorithm. Finally, the improved algorithm used a Laplace distribution to adjust the initial pheromone to improve the quality of the algorithm's initial solution. For the deadlock problem, the improved algorithm added isolated pheromones to prevent the next ant from falling into a deadlock dilemma. The improved algorithm used a genetic operator with grouping to update the global regular pheromone to avoid the ant colony from falling into a local optimum dilemma. In our study, we applied four ACO to the wild mountain environment of 400×400 grids, 1000 grids×1000 grids, 5000 grids×5000 grids, and 10 000 grids×10 000 grids for comparison, and set different starting and ending points for each environment. The experimental results show that each ACO using a combined planar and visual field search approach can obtain feasible paths in all four experiments, which verified the feasibility of the method. The quality of the paths using the improved algorithms was better than the other three algorithms, with improvements of 0.52%~4.95%, 4.71%~5.39%, 2.26%~13.11%, and 3.84%~9.16% in the four experiments, respectively, and the improved algorithm had shorter search time and convergence time. In addition, the combined planar and visual field search approach reduced the search space and improved the computational efficiency of the algorithm in the field 3D mountain environment. This search method was faster than the 8-connected method and reduced the average time consumption by more than 90%. Our algorithm is suitable for hiking path planning research in large 3D mountain scenes, with reduced planning time and improved path quality, providing technical support for the work of finding the best 3D mountain hiking paths without road networks.

Key words: 3D mountain environment, field emergency rescue, DEM, grid method, hiking path planning, mountain hiking accessibility, Ant Colony Optimization(ACO), Genetic Algorithm(GA)

伍跃飞, 李建微, 毕胜, 朱馨, 王前锋. 面向山地徒步应急救援路径规划的改进蚁群算法研究[J]. 地球信息科学学报, 2023, 25(1): 90-101.DOI:10.12082/dqxxkx.2023.220535

WU Yuefei, LI Jianwei, BI Sheng, ZHU Xin, WANG Qianfeng. Research on Improved Ant Colony Algorithm for Mountain Hiking Emergency Rescue Path Planning[J]. Journal of Geo-information Science, 2023, 25(1): 90-101.DOI:10.12082/dqxxkx.2023.220535

图/表 10

图1

图2

图3

图4

表1

表2

图5

图6

图7

图 8

参考文献 24

[1]	王帅辉, 耿松涛. 全域旅游营销策略与品牌策略规划[J]. 价格月刊, 2018(3):57-60.
	[Wang S H, Geng S T. Marketing strategy and brand strategy planning of region-based tourism[J]. Prices Monthly, 2018(3):57-60. ] DOI:10.14076/j.issn.1006-2025.2018.03.11 doi: 10.14076/j.issn.1006-2025.2018.03.11
[2]	覃先林, 李晓彤, 刘树超, 等. 中国林火卫星遥感预警监测技术研究进展[J]. 遥感学报, 2020, 24(5):511-520.
	[Qin X L, Li X T, Liu S C, et al. Forest fire early warning and monitoring techniques using satellite remote sensing in China[J]. Journal of Remote Sensing, 2020, 24(5):511-520. ]
[3]	Li J W, Li X W, Chen C C, et al. Three-dimensional dynamic simulation system for forest surface fire spreading prediction[J]. International Journal of Pattern Recognition and Artificial Intelligence, 2018, 32(8):1850026. DOI:10.1142/S021800141850026X doi: 10.1142/S021800141850026X
[4]	Guo C, Li D M, Zhang G L, et al. Real-time path planning in urban area via VANET-assisted traffic information sharing[J]. IEEE Transactions on Vehicular Technology, 2018, 67(7):5635-5649. DOI:10.1109/TVT.2018.2806979 doi: 10.1109/TVT.2018.2806979
[5]	Jeong D, Kim M, Song K, et al. Planning a green infrastructure network to integrate potential evacuation routes and the urban green space in a coastal city: The case study of haeundae district, Busan, south Korea[J]. The Science of the Total Environment, 2021, 761:143179. DOI:10.1016/j.scitotenv.2020.143179 doi: 10.1016/j.scitotenv.2020.143179
[6]	Yang B W, Ding Z M, Yuan L, et al. A novel urban emergency path planning method based on vector grid map[J]. IEEE Access, 8:154338-154353. DOI:10.1109/ACCESS.2020.3018729 doi: 10.1109/ACCESS.2020.3018729
[7]	Cai Z, Cui X R, Su X, et al. A novel vector-based dynamic path planning method in urban road network[J]. IEEE Access, 8:9046-9060. DOI:10.1109/ACCESS.2019.2962392 doi: 10.1109/ACCESS.2019.2962392
[8]	Elhoseny M, Tharwat A, Hassanien A E. Bezier curve based path planning in a dynamic field using modified genetic algorithm[J]. Journal of Computational Science, 2018, 25:339-350. DOI:10.1016/j.jocs.2017.08.004 doi: 10.1016/j.jocs.2017.08.004
[9]	Luo Q, Wang H B, Zheng Y, et al. Research on path planning of mobile robot based on improved ant colony algorithm[J]. Neural Computing and Applications, 2020, 32(6):1555-1566. DOI:10.1007/s00521-019-04172-2 doi: 10.1007/s00521-019-04172-2
[10]	Zhang Z, He R, Yang K. A bioinspired path planning approach for mobile robots based on improved sparrow search algorithm[J]. Advances in Manufacturing, 2022, 10(1):114-130. DOI:10.1007/s40436-021-00366-x doi: 10.1007/s40436-021-00366-x
[11]	Chen X, Dai Y. Research on an improved ant colony algorithm fusion with genetic algorithm for route planning[C]. In 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference (ITNEC), 2020, 1:1273-1278. DOI:10.1109/ITNEC48623.2020.9084730 doi: 10.1109/ITNEC48623.2020.9084730
[12]	Chen Y L, Bai G Q, Zhan Y, et al. Path planning and obstacle avoiding of the USV based on improved ACO-APF hybrid algorithm with adaptive early-warning[J]. IEEE Access, 9:40728-40742. DOI:10.1109/ACCESS.2021.3062375 doi: 10.1109/ACCESS.2021.3062375
[13]	Liu G Y, Shu C, Liang Z W, et al. A modified sparrow search algorithm with application in 3d route planning for UAV[J]. Sensors (Basel, Switzerland), 2021, 21(4):1224. DOI:10.3390/s21041224 doi: 10.3390/s21041224
[14]	Ma Y N, Gong Y J, Xiao C F, et al. Path planning for autonomous underwater vehicles: An ant colony algorithm incorporating alarm pheromone[J]. IEEE Transactions on Vehicular Technology, 2019, 68(1):141-154. DOI:10.1109/TVT.2018.2882130 doi: 10.1109/TVT.2018.2882130
[15]	李逸斐, 陈静. 基于改进RRT*算法的城市低空路径规划方法研究[J]. 地球信息科学学报, 2022, 24(3):448-457. doi: 10.12082/dqxxkx.2022.210413
	[Li Y F, Chen J. Research on urban low-altitude path planning method based on improved RRT*Algorithm[J]. Journal of Geo-Information Science, 2022, 24(3):448-457. ] DOI:10.12082/dqxxkx.2022.210413 doi: 10.12082/dqxxkx.2022.210413
[16]	徐晨晨, 廖小罕, 岳焕印, 等. 基于改进蚁群算法的无人机低空公共航路构建方法[J]. 地球信息科学学报, 2019, 21(4):570-579. doi: 10.12082/dqxxkx.2019.180392
	[Xu C C, Liao X H, Yue H Y, et al. Construction of a UAV low-altitude public air route based on an improved ant colony algorithm[J]. Journal of Geo-information Science, 2019, 21(4):570-579. ] DOI:10.12082/dqxxkx.2019.180392 doi: 10.12082/dqxxkx.2019.180392
[17]	Zhang B, Li G B, Zheng Q X, et al. Path planning for wheeled mobile robot in partially known uneven terrain[J]. Sensors (Basel, Switzerland), 2022, 22(14):5217. DOI:10.3390/s22145217 doi: 10.3390/s22145217
[18]	Pu X C, Xiong C W, Ji L H, et al. 3D path planning for a robot based on improved ant colony algorithm[J]. Evolutionary Intelligence, 2020:1-11. DOI:10.1007/s12065-02 0-00397-6 doi: 10.1007/s12065-02 0-00397-6
[19]	贺娇, 谭代伦. 基于视野范围和遗传算法的三维地形路径规划[J]. 计算机工程与应用, 2021, 57(15):279-285. doi: 10.3778/j.issn.1002-8331.2103-0071
	[He J, Tan D L. Three-dimensional terrain path planning based on sight range and genetic algorithm[J]. Computer Engineering and Applications, 2021, 57(15):279-285. ] doi: 10.3778/j.issn.1002-8331.2103-0071
[20]	胡平志, 杨小柳, 李泽滔. 复杂山地环境下的机器人路径规划[J]. 计算机仿真, 2021, 38(3):286-291.
	[Hu P Z, Yang X L, Li Z T. PathPlanning of robots in complex terrain[J]. Computer Simulation, 2021, 38(3):286-291. ]
[21]	Wang H, Zhang H J, Wang K, et al. Off-road path planning based on improved ant colony algorithm[J]. Wireless Personal Communications, 2018, 102(2):1705-1721. DOI:10.1007/s11277-017-5229-5 doi: 10.1007/s11277-017-5229-5
[22]	Wang L F, Kan J M, Guo J, et al. 3D path planning for the ground robot with improved ant colony optimization[J]. Sensors (Basel, Switzerland), 2019, 19(4):815. DOI:10.3390/s19040815 doi: 10.3390/s19040815
[23]	Campbell M J, Dennison P E, Butler B W. A LiDAR-based analysis of the effects of slope, vegetation density, and ground surface roughness on travel rates for wildland firefighter escape route mapping[J]. International Journal of Wildland Fire, 2017, 26(10):884. DOI:10.1071/wf17031 doi: 10.1071/wf17031
[24]	Glenn N F, Streutker D R, Chadwick D J, et al. Analysis of LiDAR-derived topographic information for characterizing and differentiating landslide morphology and activity[J]. Geomorphology, 2006, 73(1/2):131-148. DOI:10.1016/j.geomorph.2005.07.006 doi: 10.1016/j.geomorph.2005.07.006

环境	单步邻近八连通搜索和禁忌表结合		定向范围视野
环境	平均适应度/km	平均运行时间/s	平均适应度/km	平均运行时间/s
20×20	0.3753	3.4994	0.3708	0.3493
40×40	0.6841	14.3852	0.6714	0.7202
100×100	1.7444	168.4040	1.6707	2.3325

环境	环境1				环境2
环境	平均适应度/km	标准差/km	平均运行时间/s	平均收敛次数/次	平均适应度/km	标准差/km	平均运行时间/s	平均收敛次数/次
PRACS	8.3304	0.1136	7.8916	95	20.1837	0.1248	19.5329	93
文献[9]	8.3443	0.1405	7.3538	85	20.1466	0.1548	14.9997	95
文献[22]	8.7185	0.1324	4.6301	97	20.0394	0.2996	11.4807	98
本文算法	8.2868	0.0828	7.4948	84	19.6965	0.0883	14.0772	82

面向山地徒步应急救援路径规划的改进蚁群算法研究

Research on Improved Ant Colony Algorithm for Mountain Hiking Emergency Rescue Path Planning

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 24

相关文章 15

Metrics

本文评价

推荐阅读 0

[1]	董勇, 周亮, 高鸿, 王宝. 黄土高原地形破碎化探测及空间异质性分析[J]. 地球信息科学学报, 2023, 25(8): 1625-1636.
[2]	戚梦, 陈楠, 林偲蔚, 周千千. 引入集水区复杂网络的中国地貌识别研究[J]. 地球信息科学学报, 2023, 25(5): 909-923.
[3]	谢静, 陈楠, 林偲蔚. 基于地形音乐的地形定量分析与空间分异研究—以陕北黄土高原为例[J]. 地球信息科学学报, 2023, 25(5): 924-934.
[4]	焦怀瑾, 陈崇成, 黄洪宇. 结合ICESat-2和GEDI的中国东南丘陵地区ASTER GDEM高程精度评价与修正[J]. 地球信息科学学报, 2023, 25(2): 409-420.
[5]	朱佳波, 王益, 张拾斤, 陈家亮, 杨璐. 基于路径模拟和空间句法的封闭式非门禁居住小区犯罪人逃逸行为研究[J]. 地球信息科学学报, 2023, 25(11): 2178-2190.
[6]	师长兴. 地形扫描数据TIN模型生成DEM的误差计算方法[J]. 地球信息科学学报, 2023, 25(1): 40-48.
[7]	张晗, 邬群勇. 基于LDA和优化蚁群的OD流向时空语义聚类算法[J]. 地球信息科学学报, 2022, 24(5): 837-850.
[8]	肖坤, 艾廷华, 王璐. 正六边形格网DEM下的等高线生成算法及质量评价[J]. 地球信息科学学报, 2022, 24(4): 643-656.
[9]	林偲蔚, 陈楠, 刘奇祺, 贺卓文. 基于DEM小流域复杂网络的黄土高原地貌自动识别研究[J]. 地球信息科学学报, 2022, 24(4): 657-672.
[10]	代文, 陈凯, 王春, 李敏, 陶宇. 顾及DEM误差空间自相关的地形变化检测方法[J]. 地球信息科学学报, 2022, 24(12): 2297-2308.
[11]	扈常钰, 徐月雪, 宋词, 朱红春. DEM起伏纹理的视觉认知内涵与多变量消隐方法[J]. 地球信息科学学报, 2022, 24(11): 2115-2127.
[12]	马子钦, 陈崇成, 黄正睿. 融合用户特征与群体智慧的多目标旅游线路推荐方法[J]. 地球信息科学学报, 2022, 24(10): 2033-2044.
[13]	戴云哲, 杨建新, 龚健, 叶菁, 李靖业, 李云. AutoPaCA:耦合过程-模式的城镇空间增长模拟模型[J]. 地球信息科学学报, 2022, 24(1): 87-99.
[14]	杨练兵, 陈春波, 郑宏伟, 罗格平, 尚白军, Olaf Hellwich. 基于优化随机森林回归模型的土壤盐渍化反演[J]. 地球信息科学学报, 2021, 23(9): 1662-1674.
[15]	张菊, 房世波, 刘汉湖. 基于微波数据与光学数据集成的机器学习技术在作物产量估算中的应用[J]. 地球信息科学学报, 2021, 23(6): 1082-1091.