| 面向山地徒步应急救援路径规划的改进蚁群算法研究 |
| |
| 引用本文： | 伍跃飞,李建微,毕胜,朱馨,王前锋.面向山地徒步应急救援路径规划的改进蚁群算法研究[J].地球信息科学,2023,25(1):90-101. |
| |
| 作者姓名： | 伍跃飞 李建微 毕胜 朱馨 王前锋 |
| |
| 作者单位： | 1.福州大学物理信息与工程学院，福州 3500002.福州大学数字中国研究院（福建），福州 3500003.福州大学环境与安全工程学院，福州 350000 |
| |
| 基金项目： | 国家自然科学基金项目(32071776);国家自然科学基金项目(41571490);国家重点研发计划项目(2022YFC3003000);福建省自然科学基金项目(2020J01465) |
| |
| 摘 要： | 当消防事故发生在无明显道路或道路稀疏的野外复杂山区时，如何在复杂山地环境中规划安全、快速通过的路线至关重要。针对蚁群算法在复杂山地路径规划中容易陷入局部最优以及搜索时间较长的问题，本文提出一种适用于细粒度野外山地环境的徒步应急救援路径规划算法。本文首先根据已有文献分析地表信息与人类运动速度之间的关系，综合地表灌木盖度与地形坡度因素设计寻优算法的目标函数和启发函数；接着采用定向范围视野的蚂蚁搜索方式，决定蚁群算法寻优过程中每一步的网格选择；最后采用拉普拉斯分布调整初始信息素、添加隔离信息素、融合遗传算子与分组更新常规信息素的方法改进蚁群算法。将算法应用到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%；此外，在野外三维山地环境中，定向范围视野的搜索方式缩减了搜索...
|
| 关 键 词： | 三维山地环境 野外应急救援 DEM 栅格法 徒步路径规划 山地徒步可通行性 蚁群算法 遗传算法 |
| 收稿时间： | 2022-07-21 |
Research on Improved Ant Colony Algorithm for Mountain Hiking Emergency Rescue Path Planning |
| |
| WU Yuefei,LI Jianwei,BI Sheng,ZHU Xin,WANG Qianfeng.Research on Improved Ant Colony Algorithm for Mountain Hiking Emergency Rescue Path Planning[J].Geo-information Science,2023,25(1):90-101. |
| |
| Authors: | WU Yuefei LI Jianwei BI Sheng ZHU Xin WANG Qianfeng |
| |
| Institution: | 1. College of Physics and Information Engineering,Fuzhou University, Fuzhou 350000, China2. The Academy of Digital China(Fujian), Fuzhou University, Fuzhou 350000, China3. College of Environment and Safety Engineering, Fuzhou University,Fuzhou 350000, China |
| |
| 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. |
| |
| Keywords: | 3D mountain environment field emergency rescue DEM grid method hiking path planning mountain hiking accessibility Ant Colony Optimization(ACO) Genetic Algorithm(GA) |
|
| 点击此处可从《地球信息科学》浏览原始摘要信息 |
| 点击此处可从《地球信息科学》下载免费的PDF全文 |
|
