中国指挥与控制学会会刊 
在城市巡逻防控路径规划问题中,既要提升装甲装备的机动性,又要结合实际合理规划巡逻防控路径。蚁群算法广泛应用于路径规划问题,不仅满足城市巡逻防控的特殊要求,而且在算法性能和时间复杂度方面具有优势。张松灿等人[1]从蚁群算法的理论研究、算法融合、多蚁群算法研究等方面,展望了蚁群算法在战时路径规划中的未来研究方向和热点。赵天亮等人[2]为了改善传统蚁群算法进行路径规划时出现的距离障碍物过近、冗余节点多、收敛速度慢等问题,提出改进融合蚁群算法。陆缘缘等人[3]针对前期信息素匮乏导致搜索速度较慢、最优路径计算迭代次数过多的问题,提出了一种改进蚁群算法。郑娟毅等人[4]针对现有路径动态规划算法在交通问题规模增大时性能急剧下降的问题,提出了一种改进的混合遗传蚁群算法。雷超帆等人[5]针对蚁群算法在进行路径规划时存在收敛速度慢、寻优结果差、搜索不全面等问题,提出了一种融合粒子群与蚁群算法的路径规划算法,改变按经验选取参数的惯常模式,利用粒子群算法优化蚁群算法的参数。
1 模型构建
1.1 约束条件
为了解决某城市重点区域巡逻防控任务中的复杂路径规划问题,本文综合考虑多因素的巡逻防控路径规划方法,分析影响装甲装备巡逻路线的各类因素。通常,影响行进路线的因素有以下3种。
1.1.1 距离因素
距离因素是路径规划问题重要因素之一,各目的地与出发地之间的距离是确定的,当节点之间没有行驶路径时用0表示。由于装甲装备巡逻防控路径值较大,使用具体数值会影响其他约束条件的影响度,从而影响整体效果,因此我们要统一具体参数,将装甲装备巡逻防控路径的具体距离值限制在(0,1)之间,具体转换表达式如下:
式中,d为此路径实际距离,dmax为巡逻任务的最大距离。
1.1.2 天气因素
在装甲装备巡逻防控过程中,行军速度受天气的影响。但因天气因素影响较为复杂,考虑天气的影响,所以本文将天气影响具体数值化划分:极端天气影响巨大(影响值为1);风雨交加路段,导致路面道路受损(影响值为0.6);能见度低的雾霾天气对装甲装备巡逻防控有影响但不太大(影响值为0.3);正常天气无影响(影响值为0)。在场景导入过程中,我们要考虑不同时间段、不同路段、天气因素对装甲装备巡逻防控的实际影响情况,当影响值x为1时,即极端天气下,在路径规划时要尽可能地避开此路段。
1.1.3 恐怖分子袭击骚扰因素
本文尽可能模拟真实环境,考虑恐怖分子会对我方装甲装备巡逻防控进行火力骚扰,甚至炸毁城市中重要的路段,以此影响我方行动轨迹,假设当前损毁程度为n,路线上最大承受能力为m。当y=n/m为1时,表示该路段完全损毁,无法正常通行,在路径规划时要避开此路段。
在路径规划任务中,依照不同影响因素的影响程度,本文对其进行加权处理,当xi≠1,yi≠1时:
$g(c)=\min \left[\sum_{i=1}^{j}\left(0.6 \frac{d_{i}}{d_{\max }}+0.2 x_{i}+0.4 \frac{n_{i}}{m_{i}}\right)\right]$
式中,g(c)为路径点,di/dmax 为加权后距离约束条件,xi 为天气约束条件,ni/mi 为道路损毁的约束条件。当xi=1或者yi=1时,此线路无法通行。
1.2 巡逻防控点确定
巡逻防控点的确定尤为重要。在对一个城市的巡逻防控中,不可能做到对每条道路进行遍历,这不仅浪费人力物力,而且对装甲装备的机动性能也提出了较高要求。因此在设计巡逻点位时,我们需要综合考虑,通常设置在人口密集区、重要办公场所、大型地标建筑等重点区域,如大型商场、政府机构、医院等。
2 最优路径规划
2.1 蚁群算法原理
蚁群算法是仿生蚂蚁觅食的过程,蚂蚁主要通过分泌或嗅觉带有本蚁群气味的物质,即信息素来进行分析判断,以此完成群体对觅食工作的分工,如图1所示。
在约束条件下,本文采取蚁群算法,对装甲装备巡逻防控多路径模型进行求解,实现对装甲装备巡逻防控路径问题的合理规划。
蚁群在各路径之间的移动方式的表达式为
$W_{m l}(y+1)=\left\{\begin{array}{l}\frac{\left[o_{m l}(y)\right]^{\varepsilon} \cdot\left[z_{m l}(y)\right]^{\delta}}{\sum_{\text {r∈allows }_{z}}\left[o_{m l}(y)\right]^{\varepsilon} \cdot\left[z_{m l}(y)\right]^{\delta}} \\{ { l } { ∈allowsd }_{z}}^{\delta} \\0, \text { otherwise }\end{array}\right.$
式中,oml (y)为时刻y节点的信息浓度,ε为信息素的相对重要程度,δ为启发信息的相对重要程度。
对蚁群移动路径进行更新,其移动方式为
当ϑ为1时,即表示此条路径重要程度最高,蚁群选择的下一条路径不发生变化。当ϑ不为0时,蚁群算法中的蚁群可以根据实时不同路况信息释放的信息素,反馈路径状态,当某一路径发生异常时,蚁群可以迅速选择下一条最优路径。对于已经经过的路径,加入禁忌搜索表,避免重复行进。具体蚁群算法的流程如图2所示。
2.2 步骤设计
Step1.根据装甲装备巡逻防控路径中的多重干扰建立路径规划模型,明确在路径规划问题中蚁群的约束条件;
Step2.模拟生成平面地图,设定目标函数;
Step3.蚁群的起点设置在创建模型中多条路径的中心点,同时开始移动;
Step4.当蚁群移动到下一个更新节点的路径上时,每一个种群内的个体都会释放信息素,释放的信息素浓度不同,以达到对经过路径的标记;
Step5.完成所有路径后,就能按照信息素标记出最优路径,完成对装甲装备巡逻防控最优路径的规划;
Step6.在最优路径规划过程中,时间信息素差距直接影响着蚁群的更新速度,差距越大,更新速度越快,完成路径的优化速度越快。
3 实验分析
3.1 实验一
为验证多因素条件下的巡逻防控路径规划问题,本文需要进行模拟实验,模拟某省某市数据地图进行测试,巡逻防控起点、终点设置在同一位置,巡逻防控路径中包含必要巡逻防控点:飞机场、工业园区、中心花园、政府大楼、中学。本文利用Matlab绘制城市平面地图,如图3所示,黑色区域为居民楼、蓝色区域为河流、橙色区域为桥梁、绿色区域为山脉、黄色区域为必要巡逻防控点,具体场所名称已在图上标明。
表1 实验一参数设计表Tab.1 Parameter design for experiment 1 |
| 实验组 | 矩阵区域 | 巡逻点数 | 蚂蚁个数 | 迭代次数 |
|---|---|---|---|---|
| 1 | 20*20 | 5 | 15 | 100 |
| 2 | 20*20 | 5 | 30 | 100 |
| 3 | 20*20 | 5 | 45 | 100 |
| 4 | 20*20 | 5 | 60 | 100 |
实验结果如图4所示,选取45个蚂蚁收敛速度最快,效果最好,在35次即完成收敛。
最终模拟生成的战时装甲装备巡逻防控路径规划图如图5所示,最终巡逻防控路线为黑色线段,其满足对5个重要区域的巡逻防控需求,并且是最短最优路径。
通过模拟战时环境,恐怖分子对我城市进行恐怖袭击,炸毁一处桥梁和三处居民楼,如图6所示,红色区域即为受到攻击区域。
由于重要桥梁被攻击炸毁,我方需要重新规划装甲装备巡逻防控路线。更新后的规划路线如图7所示,我们可以看出重新规划的路径在确保选取最短路径的前提下,避开了被毁桥梁。
3.2 实验二
为验证算法的可行性,本文扩大模拟生成的T岛地图面积至40*40的区域,增加重点巡逻防控点数为12个,模拟生成地图如图8所示,其中黄色区域为重点巡逻点。
通过实验我们发现,随着地图面积的扩大,选取蚂蚁个数至少为60个,才能找到路径,因此蚂蚁的数量分别设置3组对比实验。具体实验参数如表2所示。
表2 实验二参数设计表Tab.2 Parameter design for experiment 2 |
| 实验组 | 矩阵区域 | 巡逻点数 | 蚂蚁个数 | 迭代次数 |
|---|---|---|---|---|
| 1 | 40*40 | 12 | 60 | 200 |
| 2 | 40*40 | 12 | 80 | 200 |
| 3 | 40*40 | 12 | 100 | 200 |
实验结果收敛情况如图9所示,在100次迭代时并不能够完全收敛,继续实验,我们发现最优实验结果大约在130次左右完成收敛。
实验最终生成路径规划图如图10所示,图中可见模拟生成的装甲装备巡逻防控路径,即图中蓝色线段,不但能够包括重点巡逻点,而且为最短路径,即证明蚁群算法能够很好地解决此问题。
3.3 对比实验
表3 不同路径规划方法的时间代价Tab.3 Time cost of different path planning methods |
| 迭代 次数 | 本文消耗 时间/s | FSA消耗 时间/s | PSO消耗 时间/s | GA消耗 时间/s |
|---|---|---|---|---|
| 100 | — | — | — | — |
| 150 | 26 | — | 90 | 1 500 |
| 200 | 32 | 450 | 96 | 2 323 |
在不考虑时间成本的情况下,我们记录不同算法找到最优解并完成收敛所需要的次数。表4即为实验结果。
表4 不同路径规划方法寻找最优解迭代次数Tab.4 Iteration counts for optimal solution search by different path planning methods |
| 实验 | 本文迭代 次数 | FSA迭代 次数 | PSO迭代 次数 | GA迭代 次数 |
|---|---|---|---|---|
| 实验1 | 130 | 1 120 | 144 | 123 |
| 实验2 | 126 | 1 132 | 144 | 133 |
| 实验3 | 131 | 1 150 | 145 | 112 |
由上表结果可以看出,人工鱼群的表现最差,大约在1 130次迭代才能完成收敛。其余算法大约稳定在120~150次迭代完成收敛。综合考虑时间因素,我们得出结论蚁群算法是最适用于解决此问题的算法。
4 结束语
本文研究城市巡逻防控问题,基于蚁群算法实现装甲装备路径规划,算法实现过程中,综合考虑距离、天气、恐怖袭击威胁等因素,可高效生成巡逻路线,并能根据场景变化实时更新路径。实验表明,蚁群算法规划的巡逻路径可显著节省人力物力,支持突发事件模拟,提升应急处置效率,从而维护社会稳定。