多策略蚁群算法求解诱导维修路径规划*

饶楚锋，韩华亭，瞿 珏，王 崴，彭勃宇

（空军工程大学防空反导学院，西安 710051）

多策略蚁群算法求解诱导维修路径规划*

饶楚锋，韩华亭，瞿 珏*，王 崴，彭勃宇

（空军工程大学防空反导学院，西安 710051）

在诱导维修过程中，为了帮助维修者快速找到维修对象，提供高效安全的行走路径，需要对复杂的维修环境进行路径规划。传统的蚁群算法收敛速度慢、易陷入局部最优。为了提高寻优效率，对基本蚁群算法进行改进。提出了对α、β的自适应调整，改变信息素增量的更新方式，以及引入双向搜索策略，有效地提高了算法的收敛速度和全局搜索能力。仿真结果表明，改进的蚁群算法效率高，收敛速度快，能够为处在复杂维修环境中的维修人员提供高效的行进路线。

诱导维修，路径规划，蚁群算法，自适应，双向搜索

0 引言

随着我军装备不断向大型复杂、技术密集的方向发展，在提升武器性能的同时还增大了维修的难度，提高了对维修人员的要求。诱导维修［1-3］是运用增强现实技术将虚实叠加的显示方式呈现在维修人员的市场中，在维修人员注意力集中的“维修区域”叠加显示各类图形文字信息，以辅助和引导维修人员进行维修作业，诱导维修系统能够一步步地指导毫无经验的用户完成复杂的任务。

在进行大型装备的维修时，维修者所处环境较为复杂，加之佩戴头盔式显示设备的维修者视野受限，若不对其加以引导，很难快速找到和到达指定区域并将视角对准维修目标。此外，若人员在复杂维修空间内随意走动，可能引起人员受伤或设备损坏等安全事故。因此，根据维修环境和维修任务，研究一种符合实际地形环境的维修路径规划方法是很有必要的。

蚁群算法［4］是由意大利学者M.Dorigo等人提出的，并最早成功应用于解决旅行商问题。蚁群算法具有正反馈性、并行性以及较强的鲁棒性和较强的全局搜索能力［5］，广泛应用于航迹规划、车辆路径规划、机器人路径规划等问题。

针对蚁群算法的路径规划方面的研究，文献［6］分析了蚁群算法的主要参数对规划路径的长度和效率的影响。文献［7］提出了根据目标点自适应调整启发函数，有效提高了算法的收敛速度；还根据狼群分配原则对信息素进行更新，避免陷入局部最优。文献［8］将蚂蚁当前位置与目标位置的距离信息反馈到系统中作为航迹规划的控制信息，提高了算法的效率。

然而在维修环境下基于蚁群算法的路径规划研究却不多见。本文根据复杂维修环境可通行的难易程度划分了4种不同的区域，并考虑了时间代价和体能代价作为规划的指标，构建了性能指标函数。针对传统蚁群算法的缺点，设计了自适应的概率转移规则和双向搜索策略，改进了传统的蚁群算法，并通过实验验证了改进蚁群算法的优越性。

1 诱导维修路径规划的数学模型

1.1 问题假定及地图构建

为求维修人员最优行进路线，首先要对维修环境进行建模，以生成用于路径规划的地图模型，本文在此提出了一种为复杂维修环境构建地图模型的方法。将维修环境的可通行情况分为4类：无障碍区域、1类有障碍区域、2类有障碍区域、不可通行区域。其中，维修人员可以较快的速度通过无障碍区域并消耗较少的体力，此类区域通常为室外平地或机舱内较宽的通道等；通过有障碍区域时，需要消耗较长时间和较多体力，2类有障碍区域比1类有障碍区域通过难度更高，此类区域通常为机舱内狭小的过道或可通过的管道等；不可通行区域为不能够通过或进入的区域，此类区域通常为舱壁阻隔、摆放大型设备或危险区域等。

根据事先存储好的维修环境的三维CAD模型、危险区域位置等信息，利用栅格法［9］建立维修环境的二维地图。本文将20 m×20 m的维修环境划分40×40的网格空间。此处作如下假设：维修人员在地图上的投影看作是一个网格，可朝与其相邻的8个方向前进；将地图中的网格分为4种颜色，用于对应上述不同通行情况维修区域，图1为将某型装备方舱内部简化得到的维修环境二维地图；4种区域对应不同的通行速度和体力消耗强度，具体设置见表1，可根据不同维修环境的实际情况进行修改。由于所求最优路径应是能使维修者以尽量少的体力消耗和尽快到达目标区域的行进路线。因此，这里认为人员在同一类型区域内为匀速行进，体力消耗代表人员行进单位距离所消耗的体力，在此使用无量纲量p对其进行度量，并设定体力消耗上限为50 p。此处的“匀速运动”和“体力消耗”是本文对实际维修情况的一种模拟，是为了配合后面的性能指标函数选取一条相对最优的路径，并不具备实际度量功能。

图1 构建虚拟环境地图

表1 地图各区域通过指标

网格序号i按照从左到右，从下到上的顺序依次增加，其与网格坐标（x，y）的转换关系由式（1）确定：

其中，mod（·）为取余操作，int（·）为取整操作，Nh为每行的栅格数。

地图以一个二维数组map（x，y）的形式存储在计算机中：

1.2 路径规划性能指标选取

考虑以时间代价和体能代价作为规划的指标，构造性能指标函数式（3）：

其中，Jt和Js分别为该段路径的时间代价和体能代价；k为权系数

时间代价由各区域内路程和通行速度决定：

体能代价由各区域内路程和体力消耗决定：

式（4）、式（5）中的 L0、L1、L2分别代表该次规划中通过无障碍区域、1类障碍区域、2类障碍区域的路径长度。

2 算法改进

2.1 基本蚁群算法

蚂蚁在觅食过程中会在所经过的路径上留下一种被称为信息素的化学物质，而蚂蚁们能感受到这种信息素的存在并倾向于向着信息素浓度高的区域移动，信息素会随时间挥发以达到更新的目的。因此，当路径上的信息素浓度越高时，其被蚂蚁选中的概率就越大，反过来也促进这条路径上信息素浓度增加。蚂蚁之间就这样依靠信息素进行交流并找到最优路径。

真实自然环境中信息素会随着时间推移而挥发，蚂蚁的经过会带来新的信息素，因此，每循环一次后都要对各小段路径上的信息素浓度进行更新。本文根据式（7）对网格i到j上的信息素进行更新。

针对蚁群算法在路径规划问题中存在的不足归纳如下：①随机性强，搜索的准确性不高；②全局搜索能力不强，容易陷入局部最优；③蚂蚁之间的协作性不强；④收敛速度低，搜索速度慢［10］。

2.2 自适应调整策略

2.2.1 参数α、β的动态调整

传统蚁群算法中α和β为常数，然而在算法初始运行时信息素基本不起作用，将α，β设为常数显然不合理，因此，本文将其设为随迭代次数动态调整，在第N次前α由小增大，此时β值较大，启发因子对转移概率起主导作用；在第N次后β逐渐减小，α维持不变，此时信息素浓度为主导，α，β变化可由式（8）和式（9）表示：

2.2.2 改变信息素增量的更新方式

由于每个蚂蚁寻求到的解的质量会有所不同，有的蚂蚁找到的解跟最优解很接近，有的蚂蚁找到的解却背离最优解，然而它们释放的信息素却是相同的，这似乎对于它们很不“公平”。我们总是希望找到优质解的蚂蚁在其所经过的路径上释放的信息素要多一些。为此，本文引入信息素增量调节因子ω，根据不同蚂蚁找到的不同路径性能指标值，对所经过的路径上的信息素自适应地更新。

其中，信息素增量调节因子ω可由下式求得

其中，Jk为第k只蚂蚁得到路径的性能指标值，Jave为蚂蚁在本次循环得到的路径平均性能指标值。

通过引入信息素增量调节因子，可以使找到较优解的蚂蚁能够释放更多的信息素，从而可以增大较好路径和较差路径之间的差距，促使蚂蚁能够更快地找到最优路径，提高了收敛的速度，缩短了搜索时间。

2.3 双向路径搜索策略

本文通过设计双向路径搜索策略提高算法效率，即将同样数量蚂蚁放在起点和终点，从两边进行搜索并引入相遇机制增强蚁群个体间的信息交流。具体方法是，将蚂蚁分为2只一组，先由起点释放一只蚂蚁，当蚂蚁找到目标或进入“不可用点”时销毁蚂蚁；然后在终点释放一只蚂蚁，遇到下列情况销毁该蚂蚁：①该蚂蚁路径与上一只蚂蚁路径在非起点和终点处产生交点；②该蚂蚁进入“不可用点”；③路径搜索成功。

当两只蚂蚁都成功到达起点和终点时会产生两条路径，此时选择代价小的一条作为最终路径；当两只蚂蚁都遇到“不可用点”时则此次搜索未找到路径；以上情况除外，可将达到路径合并为一条连通起点和目标点的路径。其中“不可用点”是指当前网格周围8个网格均属于不可通行区域或已经过的网格。将同组由起点和终点释放的蚂蚁分别记为蚂蚁A和蚂蚁B，A、B所经过的路径用LA，LB表示，L′A代表LA中路径交点处到终点的部分，Lk表示本次搜索得到的路径，上述路径的代价由式（3）求得，用 JA、JB、L′A、Lk表示。用图 2 描述双向搜索策略的流程。

图2 搜索策略流程图

2.4 改进蚁群算法步骤

利用改进蚁群算法进行维修路径规划的具体步骤如下：

①在离线状态下，根据维修环境三维CAD模型和危险区域位置等信息人工划定各类区域，并建立地图 map（x，y）；

②根据当前维修人员位置和目标任务设定路径规划的起点（xstart，ystart）和终点（xend，yend），初始化并令n=1；

③将m只蚂蚁两等份，并将相同数量蚂蚁置于起点和目标点处，开始第n次迭代；

④第k组的两只蚂蚁进行双向搜索，若成功获取路径Lk则记录下来，并对信息素值进行更新。

⑥判断近十次迭代得到的最优路径是否一致，若是则输出第n次迭代的最优路径并结束，否则转下一步；

⑦判断n＜Nmax是否成立，若是则n=n+1并跳转③，否则输出第n次迭代的最优路径并结束。

3 仿真与结果分析

表2 算法各指标对比

两次规划的最优路径如图3所示，性能指标随迭代次数的收敛情况如下页图4所示。

图3 路径搜索结果

由上述实验结果可知，本文的改进蚁群算法和基本蚁群算法都能够找到同一条最优行进路线。由于本文算法引入了自适应调整策略、双向匹配策略，使得其和基本蚁群算法相比有更快的收敛速度，能以较少的迭代次数找到最优路径。在两次规划中，本文算法所消耗的时间分别比传统蚁群算法要少34.2%和29.6%。本文所提出的改进蚁群算法能够快速有效地为处在复杂维修环境中的维修人员提供高效的行进路线。

图4 算法收敛情况对比

4 结论

本文以栅格地图上的诱导维修路径规划为研究背景，在分析不同维修区域对维修者通行的综合影响后，通过设计自适应调整策略和双向搜索策略，提出了多策略蚁群算法。为了增加路径搜索的有效性，将α、β设为随迭代次数增加而改变的自适应函数，提高了搜索的精度；改变信息素增量的更新方式，可以促使蚂蚁更好地区分较好路径和较差路径，提高了收敛速度，缩短了搜索时间。引入双向搜索策略，增强了蚂蚁之间的协作能力，路径搜索的成功率更高，也使得迭代次数优于基本的蚁群算法。仿真结果表明，改进的蚁群算法效率高，收敛速度快，能够为处在复杂维修环境中的维修人员提供高效的行进路线。

［1］赵新灿，左洪福，徐兴民.增强现实维修诱导系统关键技术研究［J］.中国机械工程，2008，19（6）:678-681.

［2］靳冬冬，王崴，刘晓卫，等.增强现实诱导维修在外军的发展现状和趋势［J］.现代防御技术，2014，42（6）：134-139.

［3］赵守伟.增强现实辅助维修技术研究进展［J］.图形学报，2014，35（4）：648-653.

［4］DORIGO M，MANIEZZO V，COLORNI A.Ant system：optimization by a colony of cooperating agent［J］.IEEE Transactions on Systems，Man， and Cybernetics，1996，26（1）：29-41.

［5］康冰，王曦辉，刘富.基于改进蚁群算法的搜索机器人路径规划 ［J］. 吉林大学学报 （工学版），2014，44（4）：1062-1068.

［6］史恩秀，陈敏敏，李俊，等.基于蚁群算法的移动机器人全局路径规划方法研究［J］.农业机械学报，2014，45（6）：53-57.

［7］柳长安，鄢小虎，刘春阳，等.基于改进蚁群算法的移动机器人动态路径规划方法［J］. 电子学报，2011，39（5）：1220-1223.

［8］牛治永，李炎，李晓岚.基于改进蚁群算法的机器人路径规划［J］.控制理论与应用，2011，3（7）：1-4.

［9］温如春等.改进蚁群算法在迷宫路径寻优中的应用研究［J］.自动化仪表，2010，31（11）：8-10.

［10］吴天羿，许继恒.多策略蚁群算法求解越野路径规划［J］.解放军理工大学学报（自然科学版），2014，15（2）：158-164.

Route Planning of Induced Maintenance Based on Improved ant Colony Algorithm

RAO Chu-feng，HAN Hua-ting，QU Jue*，WANG Wei，PENG Bo-yu
（School of Air-Defense and Anti-Missile，Air Force Engineering University，Xi’an 710051，China）

In the process of inducing maintenance，in order to help the maintenance person to find the maintenance of the image quickly，and to provide a safe and efficient way to walk，there is a need to make a maintenance path planning for its complex maintenance environment.The traditional ant colony algorithm is slow convergence and easy to fall into local optimum.In order to improve the optimization efficiency，the basic ant colony algorithm is improved.The adaptive adjustment of α、β，pheromone increment adjustment factor and the bidirectional search strategy are introduced to improve the basic ant colony algorithm，which improve the solution effciency of the algorithm greatly.The simulation results shows that the improved ant colony algorithm has high efficiency and fast convergence speed and is able to provide efficient route for the maintenance personnel in complex maintenance environment.

inducing maintenance，path planning，ant colony algorithm，self-adaptation，bidirectional search strategy

1002-0640（2017）10-0082-05

TP301

A

10.3969/j.issn.1002-0640.2017.10.018

2016-08-12

2016-10-27

国家自然科学基金资助项目（51405505）

饶楚锋（1993- ），男，湖北黄冈人，硕士研究生。研究方向：增强现实诱导维修。

*通信作者：瞿 珏（1985- ），男，湖南汨罗人，副教授，在读博士。研究方向：虚拟维修，人机工程和机器视觉。