EN中文

Journal of Geo-information Science >

2023 , Vol. 25 >Issue 1: 90 - 101

DOI: https://doi.org/10.12082/dqxxkx.2023.220535

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

  • WU Yuefei , 1, 2 ,
  • LI Jianwei , 1, 2, * ,
  • BI Sheng 1, 2 ,
  • ZHU Xin 1, 2 ,
  • WANG Qianfeng 3
Expand
  • 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
*LI Jianwei, Email:

Received date: 2022-07-21

  Revised date: 2022-09-19

  Online published: 2023-03-25

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)

Fold

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)

Cite this article

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

1 引言

近年来，游客被困在山林、原始森林火灾等野外事故时有发生[1-2]，当遇到山区尚未修建道路或路网稀疏的情况时，游客与消防员无法及时获取科学的路线，严重危害生命财产安全，合理设计野外山地徒步路径对于应急救援具有重要意义[3]。
基于网络分析的城市交通路径规划研究相对成熟[4-5]，广泛应用于二维地图导航系统，但其依赖于精确路网数据，不适用于无路网或路网稀疏的野外山地环境。针对无路网路径规划问题，常用的路径搜索算法包括传统算法与智能算法，主要有Dijkstra、A*、遗传算法(Genetic Algorithm, GA)、蚁群优化算法(Ant colony optimization, ACO)、麻雀搜索算法(Sparrow Search Algorithm, SSA)等[6⇓⇓⇓-10]，除了使用上述单一算法求解问题，还有混合算法的研究[11-12]。近年来国内外学者逐渐将目光转向三维，天空、海洋、地表等三维环境的路径规划研究越来越多，在三维路径规划研究中，智能算法应用更加广泛[13⇓⇓⇓⇓-18]。关于智能优化算法在三维地表环境的路径规划研究，贺娇等[19]针对三维地形路径规划问题提出一种结合视野范围与遗传算法的方法，以此搜索避开地形的可行路径，降低算法复杂度，但未规定研究对象，仍以路径长度最短为寻优目标；胡平志等[20]为解决机器人在复杂山地环境的路径规划问题，采用改进的蚁群算法结合等高线分层规划路线，以坡度为约束条件求解路径长度最短的路线；Wang等[21]采用改进禁忌表的蚁群算法求解越野车三维路径规划研究，基于土壤类型与坡度对越野车的影响建立目标函数，通过实验展示其良好的性能；Wang等[22]根据地形特征建立三维地形模型，并使用改进的蚁群算法求解地面机器人的三维地形路径规划。
上述研究以机器为主要研究对象，但机器并无法完美应对真实山区的复杂性，研究应参考人类的行动方式。现实山地环境属于复杂的三维地表环境，移动路径被约束在三维表面上，因此山地徒步路径规划需考虑地形起伏与地表环境因素产生的影响，而不仅仅是以固定坡度为约束条件。以蚁群算法为代表的智能搜索算法在三维地表路径规划的研究多为粗粒度研究，大多采用少量的网格环境作为模拟环境，缺乏实用性。
考虑到山地地表环境的复杂性，为贴合实际工作，尽可能地使用更精细的地理信息数据，且算法搜索时间不宜过长。本研究侧重考虑细粒度野外山地环境，参考人类的移动方式，研究改进的定向范围视野蚁群算法求解三维山地徒步路径规划问题，通过实验证明了算法的良好性能。

2 山地徒步路径规划方法设计

2.1 山地徒步通行性分析

山地徒步应急救援路线规划的目标是搜索用户位置和目标地点之间通过时间最短的路径。通常情况下，山区徒步路径最好避免陡峭的山坡、密集的植被、不平坦的地面，但这些描述过于主观，因此本文通过定量公式进行研究，确保规划结果更客观。根据Campbell等[23]关于制定野外消防员逃生路线的研究，在影响山区行进速度的众多因素中，坡度、灌木密度和地表粗糙度等景观条件的影响尤其大，并且通过实验确定了消防人员逃生路线中行进速度与各个因素之间的定量关系。但其研究通过LiDAR计算特殊的地表粗糙度[24]，该数据不易获取，故不考虑地表粗糙度，结合文献[23]可得野外行进速度公式，见式(1)。
V = 1.662 - 1.076 × d e n s i t y - ( 5.191 × 10 - 3 ) × s l o p e - ( 1.127 × 10 - 3 ) × s l o p e 2
式中：V是消防员行进速度/(m/s)；density是灌木密度/%，代表网格的平均灌木密度；slope是坡度/ °。
从文献[23]可知，在灌木密度与坡度的双重影响下，行进速度可能会降到0 m/s及以下。本研究因缺少地理类型数据，不考虑无法通行区域，如悬崖、壕沟、荆棘丛、湖泊等，因此通过行进速度判别路线能否通行，规定速度小于0 m/s的路线行进速度为接近0的极小值，经过不可通行路线的情况会在算法迭代中被优化。

2.2 定向范围视野

本研究区域为无路网信息的三维山地，基础地理信息均为栅格数据形式，因此选择栅格法作为环境建模方法。将DEM网格中心点作为移动节点，为确保路线贴合地形，假设4个相邻网格的中心点在同一平面，即在单位移动网格中的任意移动轨迹均为直线。
本研究针对细粒度网格环境，基础网格数较大。传统栅格法路径规划使用八连通和禁忌表的方法确定下一位置集合，计算量过高，用时太长，更适用于布满障碍物的二维粗粒度环境。因此，本研究采取定向范围视野的搜索方式，首先确定路径规划的主方向、前进的固定长度，再将横向方向限制在左右各2个网格，最后确定下一步选择的位置网格。定向范围视野方式舍弃了全局网格的搜索空间，简化了搜索过程。定向范围视野方式的搜索示意图如图1，即对于每个点都拥有5个方向的选择。
图1 网格搜索方式

Fig.1 Grid search method

2.3 改进蚁群算法

2.3.1 网格选择

蚁群优化算法通过模拟蚂蚁合作觅食的行为，采用遗留信息素的方式逐代寻优。蚁群算法中每只蚂蚁都会根据残留的信息素和启发式函数选择下一位置点，假设蚂蚁的当前位置网格为( i 1 , j 1)，下一步选择的相邻位置网格( i 2 , j 2)的概率为 P ( i 2 , j 2 )。传统蚁群算法通过轮盘赌法利用相邻网格的选择概率确定蚂蚁下一步将要移动的网格，全局随机挑选会导致收敛变慢。所以，本文采用自适应伪随机轮盘赌方法确定下一步网格，方法通过式(2)选择。
F X = m a x { τ ( i 2 , j 2 ) α × Q ( i 2 , j 2 ) β × G ( i 2 , j 2 ) γ } p x > r a n d R o u l e t t e p x ≤ r a n d ( i 2 , j 2 ) ∈ N ( i , j )
p x = ( M / 25 f i t g b e s t ) m a x ( i t e r ) / i t e r f i t g b e s t < f i t g r e e d y p x 0 其 他
P ( i 2 , j 2 ) = τ ( i 2 , j 2 ) α × Q ( i 2 , j 2 ) β × G ( i 2 , j 2 ) γ ∑ τ ( i 2 , j 2 ) α × Q ( i 2 , j 2 ) β × G ( i 2 , j 2 ) γ 0 其 他 ( i 2 , j 2 ) ∈ N ( i , j )
式中： τ ( i 2 , j 2 )是网格 ( i 2 , j 2 )的信息素浓度； Q ( i 2 , j 2 )是网格 ( i 2 , j 2 )的启发式函数； G ( i 2 , j 2 )是隔离信息素浓度， α、 β和 γ分别是常规信息素浓度、启发式函数和隔离信息素浓度的相对重要因子； N ( i , j )是下一步可选择的位置集合， p x是自适应随机选择概率；Roulete表示轮盘赌法；M为网格数； f i t g b e s t为迄今全局最佳适应度值； f i t g r e e d y为贪婪算法求解最佳初始适应度；iter为迭代次数； p x 0为初始随机概率。

2.3.2 启发函数与适应度函数设计

根据式(1)可知，无任何阻碍的情况下徒步速度为1.662 m/s，因此山地行走距离 d m与无任何阻碍情况下行走距离 d r的关系如式(5)所示， θ代表等效比例系数； v 0表示无任何阻碍的情况下的徒步速度；v表示山地徒步速度。
θ = d r d m = v 0 t v t = 1.662 / ( 1.662 - 1.076 × d e n s i t y - ( 5.191 × 10 - 3 ) × s l o p e - ( 1.127 × 10 - 3 ) × s l o p e 2 )
由于行进速度公式中的坡度区分上坡与下坡且本文坡度计算分为2种情况（图2）：
图2 贴地运动路线

Fig.2 Ground movement route

第1种情况是行进路线在同一地形网格上（ | j 1 - j 2 | < 2），此时，行进坡度路线坡度值slope用式（6）计算：
s l o p e = 180 ° π × t a n - 1 | H ( i 1 , j 1 ) - H ( i 2 , j 2 ) | 12.5 × 1 + ( j 1 - j 2 ) 2
第2种情况是行进路线跨越2个地形网格（ | j 1 - j 2 | = 2），分为2个坡度值，对应图2中前路段和后路段，分别用式（7）计算。
s l o p e = 180 ° π × t a n - 1 H m - H ( i 1 , j 1 ) 12.5 × 1 + ( 1 / 2 ) 2 前 路 段 180 ° π × t a n - 1 H ( i 2 , j 2 ) - H m 12.5 × 1 + ( 1 / 2 ) 2 后 路 段
H m = ( H ( i 1 , j 1 + j 2 2 ) + H ( i 2 , j 1 + j 2 2 ) ) / 2
式中： H ( i , j )为网格(i,j)对应地形高度。 H m是两点地表中心点。
灌木密度density的计算公式同样分2种情况，以路线经过网格的平均灌木密度为准。第1种情况是行进路线在同一地形网格上（ | j 1 - j 2 | < 2），此时的灌木盖度density用式（9）计算：
d e n s i t y = ( d e n ( i 1 , j 1 ) + d e n ( i 2 , j 2 ) ) / 2
第2种情况是行进路线跨越2个地形网格（ | j 1 - j 2 | = 2），分为2个平均灌木密度，采用式（10）计算。
d e n s i t y = d e n ( i 1 , j 1 ) + d e n i 1 , j 1 + j 2 2 2 前 路 段 d e n i 2 , j 1 + j 2 2 + d e n ( i 2 , j 2 ) 2 后 路 段
式中：den(i, j)是网格(i,j)的灌木密度。
为了使算法迭代过程中确保蚂蚁定向运动，蚁群算法引入启发式函数结合信息素机制寻找路径。启发式函数需要考虑两点之间的通行性和下一点到终点的直线距离，见式(11)。当两点之间存在行进速度为极小值的情况时， d取值会极大，导致选择概率也会变小。
Q ( i 2 , j 2 ) = 1 ω f × ( d × D )
式中： ω f是分配给d与D的启发函数权重值； d是两点之间的等效无障碍距离，见式(11)； D是空间直线距离，如式(13)所示。
d = 12 . 5 2 + ( 12.5 × ( j 1 - j 2 ) ) 2 + ( H ( i 1 , j 1 ) - H ( i 2 , j 2 ) ) 2 × θ , | j 1 - j 2 | < 2 12 . 5 2 + ( 12.5 2 ) 2 + ( H m - H ( i 1 , j 1 ) ) 2 × θ 1 + 12 . 5 2 + ( 12.5 2 ) 2 + ( H m - H ( i 2 , j 2 ) ) 2 × θ 2 , | j 1 - j 2 | = 2
式中： d的计算公式同样分为2种情况； θ根据式(5)使用对应的坡度slope与灌木覆盖度density计算。
由于算法初期地图尺度较大且蚂蚁离终点较远，下一步网格与终点网格之间的距离差异很小，路线选择存在很大的随机性，因此采用等式(13)减少随机情况的发生。
D = d 12 + d 2 E - d 1 E
式中：D表示下一点与终点的距离关系； d 12是当前点( i 1, j 1)与下一点( i 2, j 2)的直线距离，见式(14)； d 1 E是当前点( i 1, j 1)与终点( i E, j E)的直线距离，见式(15)； d 2 E是下一点( i 2, j 2)与终点( i E, j E)的直线距离，见式(16)； H ( i , j )为网格(i, j)对应地形高度。
d 12 = ( 12.5 × ( i 2 - i 1 ) ) 2 + ( 12.5 × ( j 2 - j 1 ) ) 2 + ( H ( i 2 , j 2 ) - H ( i 1 , j 1 ) ) 2
d 1 E = ( 12.5 × ( i E - i 1 ) ) 2 + ( 12.5 × ( j E - j 1 ) ) 2 + ( H ( i E , j E ) - H ( i 1 , j 1 ) ) 2
d 2 E = ( 12.5 × ( i E - i 2 ) ) 2 + ( 12.5 × ( j E - j 2 ) ) 2 + ( H ( i E , j E ) - H ( i 2 , j 2 ) ) 2
本研究以等效无障碍距离d作为山地徒步应急救援路径规划算法的目标函数值fit，见式(17)，即各段等效距离总和。
f i t = s u m ( d )

2.3.3 信息素更新

蚁群算法的行为很大程度上受信息素的影响，初始信息素的合理分布有利于改善初期算法盲目搜索的情况，而初始信息素的确定方法本身需要极短的搜索时间。本文采用定向范围视野结合启发函数的贪心算法确定初始路径，信息素分布通过拉普拉斯分布(Laplace distribution)调整，见式(18)。
i n i p h e r o m o n e = e x p ( - 2 × | Δ d | M / 4 )
式中： i n i p h e r o m o n e表示初始信息素； M是网格数； Δ d是网格离初始路径的网格差，即初始信息素以初始路径的信息素浓度最高并向两端快速降低的情况分布。
蚁群算法中的信息素用于吸引蚂蚁寻找路径，信息素更新包括局部信息素更新和全局信息素更新，局部信息素更新相关公式见式(19)， τ ( i , j )是信息素， μ是信息素衰减系数。
τ ( i , j ) = ( 1 - μ ) × τ ( i , j )
由于局部信息素更新过程中存在信息素自动衰减机制，较多的蚂蚁会导致某些网格信息素逐步衰减至无限接近0的值，会导致算法陷入局部最优的情况，因此需要利用上下界限制信息素，本文以最大最小信息素的方法限制信息素，具体公式如式(20)。
τ ( i , j ) = τ m a x τ ( i , j ) > τ m a x τ ( i , j ) o t h e r s τ m i n τ ( i , j ) < τ m i n
式中： τ ( i , j )是信息素浓度； τ m i n是最小信息素浓度； τ m a x是最大信息素浓度。
在蚂蚁搜索过程中，到达某个无法寻找下一网格的位置（死路）时会触发隔离信息素的变化，从而避免后续蚂蚁重蹈覆辙。
G ( i , j ) = G i n i 未 出 现 尽 量 隔 离 的 网 格 G m i n 出 现 尽 量 隔 离 的 网 格
式中： G ( i , j )表示隔离信息素浓度； G i n i表示初始隔离信息素浓度； G m i n是最小隔离信息素浓度。
当所有蚂蚁完成路径搜索时，需在下一次迭代前进行全局信息素更新。算法的全局信息素更新机制仅更新当前迭代中的最佳路径，可能导致算法局部最优。因此，全局信息素更新机制修改为将蚂蚁分为超越组与普通组，超越组即找到全局最佳路径的蚂蚁，其余蚂蚁均归为普通组。当未出现超越组时，只更新普通组前5的蚂蚁的信息素，全局信息素更新见式(22)。
τ ( i , j ) = ( 1 - ρ ) × τ ( i , j ) + Δ τ ( i , j ) t r a + Δ τ ( i , j ) b e s t
Δ τ ( i , j ) = C f i t ( k )
式中： ρ是信息素挥发系数； Δ τ ( i , j ) t r a是超越组路径网格增强信息素； Δ τ ( i , j ) b e s t是普通组路径网格增强信息素，由对应适应度值确定；C是一个正常数； f i t ( k )是对应蚂蚁经过路线的评价值。

2.3.4 路径交叉变异

当蚁群算法在一轮迭代搜索结束后得到若干路径，再引用遗传算法的选择、交叉和变异算子优化已有路径。① 选择算子。根据蚁群算法搜索的路径，获取前5位及其适应度值，再根据轮盘赌法选择路径。② 交叉算子。按照交叉概率将路径两两配对，若两条路径存在3个以上相同节点，则随机选取一个节点单点交叉，得到2条新路径。③ 变异算子。按照变异概率随机选择部分序列变异，生成新路径。
将遗传操作后的路径适应度值与原路径、全局最佳路径比较，选择当代局部最佳路径和全局最佳路径，再进入下一次迭代。

2.3.5 算法流程

本文算法涉及6个步骤：① 环境建模与初始化参数，改变网格选择策略，确定启发函数与适应度函数；② 采用定向范围视野结合贪心算法搜索初始路径，并以拉普拉斯分布调整初始信息素；③ 蚂蚁从起点出发，按照随机轮盘赌方法选择下一步网格并更新局部信息素，直到蚂蚁到达终点；④ 若此蚂蚁发现死路，则启动隔离信息素，限制后续蚂蚁的路径寻优；⑤ 所有蚂蚁均寻优完成后，取排序前五的路径，基于遗传算子进行路径融合变异，记录当代最佳路径和全局最佳路径；⑥ 按适应度值分组并更新全局信息素，开启下一次迭代。总算法流程如图3所示。
图3 算法流程

Fig.3 Algorithm flow

3 实验与分析

3.1 实验环境概况

实验场景分为小范围环境与大范围环境，小范围环境包括环境1与环境2，是徒步应急救援较常见的环境。环境1的中心点经纬度为（117°01′48″ E， 24°57′36″N），山区面积25 km2，海拔高度为456~1269 m，地形呈现中部高东西低的特征；环境2的中心点经纬度为（116°41′00″E， 24°52'31″N），占地面积156.25 km2，海拔高度为209~1386 m，地形呈现东北高西南低的特征。大范围环境包括环境3与环境4，是展示方法性能的场景。环境3的中心点经纬度是（117°04′03″E， 25°12′25″N），海拔高度为174~1806 m，地形起伏明显。环境4的中心点经纬度是（117°04′49″E， 25°14′43″N），海拔高度2~1806 m，地形起伏明显。
根据式(1)可知，实验数据包括坡度与灌木盖度。根据式(6)、式（7）可知，坡度计算存在不同情况，需采用DEM信息实时计算。DEM数据来源于ALOS PALSAR DEM（https://earthdata.nasa.gov/），灌木盖度网格数据由MOD44B（https://modis.gsfc.nasa.gov）和相关林业调查数据插值计算。4种环境的地理数据精度一致，均为12.5 m。地理数据网格数分别为400 ×400、1000 ×1000、5000 ×5000、10 000 ×10 000。山地环境数据如图4所示，由DEM网格实时计算的坡度与灌木盖度网格决定路线。
图4 山地环境数据(以环境1为例)

注:上层为灌木盖度网格数据,下层是地形网格数据。

Fig.4 Mountain environment data (Take environment1 as an example)

3.2 算法参数设置

本文算法初始参数如下，蚂蚁数量设置为100，随机选择概率为0.9，信息素重要因子为1，启发式函数重要因子为1，信息素衰减系数为0.3，信息素限制为0.001~1，初始信息素挥发系数为0.2，启发式函数因子权重为(0.5，0.5)，信息素初始值为1，正常数C为200，迭代次数为100，交叉概率为0.8，变异概率为0.2。所有蚁群算法的共同参数保持一致，独有参数参考其文献。

3.3 网格选择方式对比测试

为了验证定向范围视野的有效性，本节在保持初始参数不变的前提下，采用单步邻近八连通搜索结合禁忌表的蚁群算法与定向范围视野方式的蚁群算法，分别在不同网格数的山地环境中重复20次实验，实验结果如表1所示。
表1 改变网格选择方式前后对比

Tab.1 Comparision of two grid search methods

环境 单步邻近八连通搜索和禁忌表结合 定向范围视野
平均适应度/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
根据实验结果可知，在野外山地场景中，定向范围视野的搜索方式缩短了蚁群搜索的时间，在20 ×20的山地环境中搜索时间降低了90%。随着环境网格数的增加，2种搜索方式的耗时差距逐渐变大。尽管定向范围视野舍弃了一些搜索空间，在布满障碍物的极复杂环境下不占优势，但更适用于细粒度野外三维山地环境。考虑到该搜索方式在野外山地环境中良好的时间性能，因此本文采用定向范围视野的搜索方式。

3.4 算法对比测试

本研究使用Matlab2020a编写算法，并在配备Intel(R) Core (TM) i5-6500 CPU、3.2 GHz和8.00 GB 内存的电脑上运行。山地徒步应急救援路径规划研究采用改进的蚁群算法搜索路径，并与伪随机比例规则的蚁群系统算法(PRACS)、文献[9]、[22]算法对比。由于研究对象与网格搜索方式的不同，只采用了文献中蚁群算法部分，启发函数、适应度函数与网格搜索方式参考本文。为了避免偶发情况，所有实验均在相同环境与参数情况下独立运行20次。本研究以解决方案的质量、运行时间、算法收敛性为指标，对于每次运行结果，记录下对应的评估指标值。

3.4.1 小范围网格环境测试

为验证本文算法的优越性，本节在环境1和环境2中进行实验，实验场景数据取自原始山区，代表一般研究的应用场景。
表2展示小范围环境下各算法评估结果。通过分析表2结果可知，本文算法的平均适应度与标准差较其他算法更好，表明其具有良好的寻优能力和算法稳定性；从运行时间指标来看，本文算法的搜索时间比文献[22]算法略长，比其他2种算法更短；本文算法的平均收敛次数最小，表明算法具有良好的收敛性。各算法在2种环境中求解的最佳路径情况如图5和图6所示，本文算法在环境1的最佳路径与其他算法的最佳路径有较大差异，在环境2中与文献[22]的路径相近，路线总体地形趋势更平缓；图5(d)为各蚁群算法的最佳路径迭代收敛曲线，由图5可知本文算法具有更好的寻优能力，避免了初期搜索的盲目性，即在初次搜索时得到的路径适应度最小，说明本文初始信息素分布规律较合理。
表2 小范围环境各算法评估

Tab.2 Evaluation of each algorithm in small scale environment

环境 环境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

注：表中加粗字体表示各评价指标的较优值。

图5 实验结果对比（环境1）

Fig.5 Experiment result comparison (Environment1)

图6 实验结果对比（环境2）

Fig.6 Experiment result comparison(Environment2)

3.4.2 大范围网格环境测试

为了展示方法性能，本节在环境3与环境4中测试算法，该场景数据取自较大面积地区，代表提高算法基础计算量的实验场景。
各算法在环境3中测试结果如图7所示，各蚁群算法均能搜索到有效路径，各路径在初始路段有较大差异，后程路段差异较小。从算法收敛曲线图7可知，文献[22]的最佳路径质量明显次于其他算法，其他3种算法的差距较小。从算法评价指标图可以看出，本文算法的平均适应度为95.5623 km，相比其他算法求解的最佳路径适应度分别减少了2.26 %、2.41 %与13.11 %；本文算法的标准差为0.2732 km，比其他3种算法更低，文献[22]算法的标准差最大；从耗时性能指标来看，文献[22]算法耗时75.4767 s，耗时性能最优，其次是本文算法耗时110.8290 s；本文算法的迭代次数为94次，其次是PRACS算法和文献[9]算法的98次迭代，最后是文献[22]算法。综上所述，本文算法在环境3中的耗时性能弱于文献[22]算法，其他指标均更优。
图7 实验结果对比（环境3）

Fig.7 Experiment result comparison(Environment3)

各算法在环境4中的实验结果如图8所示，随着环境网格数达到10 000 ×10 000，各算法仍能搜索到有效路径，表明本文方法中搜索方式与启发函数的有效性。从算法收敛曲线图可知，文献[22]的最佳路径质量次于其他算法，本文算法的最佳路径质量更好。从算法评价指标图可以看出，本文算法的平均适应度为179.7500 km，相比其他算法求解的最佳路径适应度减少了3.84%~9.16%；从平均耗时指标来看，文献[22]算法耗时162.0678 s，耗时性能依然最优，其次是本文算法耗时234.7271 s；各算法标准差分别为1.0958、0.780 、1.3622与0.7996 km，说明文献[9]算法的稳定性更好，其次是本文算法；本文算法的迭代次数更优，文献[22]算法的收敛性较差。综上所述，结合定向范围视野的搜索方式与本文启发函数的各蚁群算法在较大网格数的环境中仍能搜索有效路径，且搜索时间在容忍范围的前提下，本文算法的寻优能力更好。
图 8 实验结果对比（环境4）

Fig.8 Experiment result comparison (Environment4)

4 结论与讨论

智能优化算法相比于传统搜索算法具有更好的寻优能力，但规划时间往往更长，导致许多相关研究采用粗粒度的野外三维山地环境，缺乏实用性。智能优化算法在三维地形路径规划中的研究，更多地以机器人或越野车为研究对象，很少参考人类行走方式。因此，本研究采用定向范围视野方式缩短规划时间，确保智能优化算法在大型野外山地环境的路径规划研究中具有实际应用意义。通过已有野外山地徒步路径速度定量公式作为通行性限制，为消防员或徒步旅行爱好者提供可在大型野外三维山地环境中移动的路径。
本研究根据野外山地徒步的特点，提出一种适用于细粒度野外山地环境的改进蚁群算法，以不同网格数的环境为例进行可行性验证与性能评估，得到下述结论：
（1）基于传统智能路径寻优方法，采用定向范围视野的方式限制搜索空间，降低算法规划时间。通过3组不同野外山地环境下的实验，结果表明该搜索方式比传统搜索方式更适用于细粒度野外山地环境，平均耗时降低90%以上。
（2）根据野外山地徒步速度的已有研究，将速度公式作为路径通行性限制，并根据速度公式转化为等效距离，以此规划等效距离最短的路径。同时，为了减少蚂蚁迂回问题，通过当前点、下一点与终点相互之间的空间距离差值提升终点引导作用，减少大范围环境下难以找到终点的情况发生。经过四组实验，采用上述搜索方式与启发函数的各蚁群算法均能搜索到可行路径，验证了该方法在大型野外山地环境中的有效性。
（3）针对蚁群算法存在容易陷入局部最优解的问题，本文基于蚁群系统算法，结合初始信息素拉普拉斯分布、添加隔离信息素、分组更新全局信息素、混合遗传算子等方法进行改进。与其他蚁群算法相比，改进后的蚁群算法在四组实验中表现出更好的寻优性，平均适应度分别提高了0.52%~4.95%、4.71%~5.39%、2.26%~13.11%、3.84%~9.16%，且具有较短的搜索时间和较好的稳定性。
本研究能在野外山区救援、远足旅行、野外灾害疏散、越野运动、规划公共山路等方面提供一定参考。本文算法在4种不同环境下均能搜索到可行路径，算法鲁棒性较强，但案例数量仍较少，存在障碍物拦截、地形高度差异大等问题导致算法寻优效果不佳。实际野外山地环境中，可能存在类似荆棘丛、湖泊等障碍物，但相关数据较难获取，因此本研究未考虑复杂障碍物的场景，后续研究需要完善。面对实际景观条件动态变化的情况，后续需要进行实时读取周边环境与动态修改路径规划的研究。

References

Publishing order | Descend order by publishing year | Descend order by cited within
[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

[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

[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

[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

[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

[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

[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

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

[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

[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

[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

[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

[15]
李逸斐, 陈静. 基于改进RRT*算法的城市低空路径规划方法研究[J]. 地球信息科学学报, 2022, 24(3):448-457.

DOI

[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

[16]
徐晨晨, 廖小罕, 岳焕印, 等. 基于改进蚁群算法的无人机低空公共航路构建方法[J]. 地球信息科学学报, 2019, 21(4):570-579.

DOI

[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

[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

[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

[19]
贺娇, 谭代伦. 基于视野范围和遗传算法的三维地形路径规划[J]. 计算机工程与应用, 2021, 57(15):279-285.

DOI

[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

[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

[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

[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

[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

Options
Outlines

/

〈 〉