改进的蚁群算法在无人机航路规划中的应用

2013-01-14郝延军陈治平何佑明孙彦飞

无线电工程 2013年6期

郝延军，罗军，陈治平，何佑明，孙彦飞

(解放军陆军军官学院，安徽合肥230031)

0 引言

航路规划(Path Planning)［1，2］是指在目标点与起始点之间，为运动物体寻找满足某种性能指标和某些约束的线路、路径。在制定无人机部(分)队作战计划时，首先要进行合理的航路规划，以期在种种约束条件之下无人机能够顺利地往返可疑目标点(有时是多个目标点)，并能对目标点发挥无人机最大的作战效能。

1 无人机航路规划的基本步骤

1.1 确定航路规划的主要指标

航路规划时选择的主要指标包括:有效飞行时间、目标价值指数和航路总长等。

有效飞行时间Teffective是无人机作用目标的时间。若无人机等速飞行，则无人机的有效飞行时间也就可以转变为有效飞行距离，可记为Leffective。

目标价值指数是指目标的重要程度。在对不同的目标执行任务时，对于价值较高的目标通常需要有效作用的时间长，而对于价值相对较低的目标，则可以压缩作用时间。

航路总长是指在遂行了一定的任务之后，总的航路长度，这里指路程，而不是位移。

1.2 确定目标位置

目标对无人机的吸引程度由目标的军事价值、无人机性能和任务决定。敌方的目标一般以点目标较多，但当目标为明显的面目标时，则选择其中心点作为目标点位置。

1.3 确定主要威胁位置

敌方对无人机的主要威胁有:敌方雷达阵地和敌方防空武器阵地等。在航路规划时，在不影响作用效果或者影响效果不大的情况下尽可能远离或规避这些区域。

1.4 选择无人机发射回收阵地

在尽可能安全的前提下，无人机尽量抵近第一个目标点发射，以保证在航程一定的情况下能经过尽可能多的目标点。回收通常与发射是同一阵地，有时为增强抗毁性也可分开。

1.5 优化航路

航路的获得是通过计算机按一定选优算法仿真实现的，具体地说:首先构建目标点及威胁点的坐标系。将上述各目标点及威胁点用坐标系来表示，将主要威胁点换算到平面直角坐标系中。然后有针对性地规划多条航路，这些航路不是最终航路，需要最优化处理，本文采用改进的蚁群算法和MATLAB二维仿真运算实现寻优过程。

1.6 后期处理航路

航路的后期处理通常是指航路的光顺。该过程包括:初始航路的离散化、链路动力学处理和最佳通过点附近的修正。

2 蚁群算法的基本原理

航路优化方法［3-11］有很多，蚁群算法在这些方法中具有较好的鲁棒性，在蚂蚁数量不多时收敛速度快，无人机航路优化尤其适合用蚁群算法来求解。

蚁群算法(Ant Colony Algorithm)［12，13］是一种仿真蚁群觅食过程的新型概率搜索算法。其原理在于，一只蚂蚁在行动中感知其他蚂蚁留下的气味，并在路网中散布自己的生物信息激素，而后到者会受前者信息激素影响，并很可能会对原有的信息激素进行加强，如此循环下去。这样，经过蚂蚁越多的路径，被后到蚂蚁选中的可能性就越大。通常越短的路径会被越多的蚂蚁访问，因而积累的信息激素也就越多，在下一个时间内被其他蚂蚁选中的可能性也就越大。这个过程会一直持续到几乎所有的蚂蚁都走最短的那一条路径为止，那么这条路径也就是蚁群选择的距离最短的(有时是能量消耗最小的)最优路径。

3 改进的蚁群算法

3.1 原蚁群算法的不足

上述蚁群算法运用于无人机航路规划时有其不足之处:

①蚁群在寻找食源时，它们的目标是不定的，而无人机的作战目标是预先确定的。

②算法不满足无人机航路选择的要求。无人机对航路选择要求有2点:航路尽可能安全(主要防敌打击和电磁干扰);航路尽量短(为减少路途飞行时间，增加执行任务时间，有时也为减少油耗)。在这2个要求需要同时抉择时，应该首先满足前者。但蚁群算法解决后者比较理想，解决前者却略显不足。

③第一只蚂蚁对蚁群路径选择影响大，容易消耗蚁群正确选择路径的时间。如开始时第一只蚂蚁在探索路径中(假设是较次的路径)散布自己的生物信息激素，而后到者会受这只蚂蚁信息激素影响，并很可能会加强信息激素，如此恶性循环下去，则这只蚂蚁会极大地消耗正确选择路径的时间，在仿真实现中会占用计算机资源。

④无人机的路径选择过程对信息内容要求较严，因为蚁群选择路径时一般是静态的，需要考虑的因素少，而无人机选择路径是动态的，要随战场变化实时调整的。

3.2 改进的蚁群算法

通过分析上述算法不足，本文提出新的改进算法。首先，在算法中设定具体目标和可能经过的威胁点;其次，在信息激素中除了有距离信息还需要增加威胁度信息，并将威胁度设为权重较高的参数指标;再次，在航路规划仿真开始阶段，同时发送多个探路人工蚁。探路人工蚁是专门探路的专职人工蚁，其探路行动各自独立，也可以按人工预定线路探路，到达目标返回后，报告所行路径的安全度和行程距离。探路人工蚁的数量可根据计算机处理能力设定，一般至少5个。由探路人工蚁探测出通往目标的可能路径和相关指标后，再根据要求初选出几条较好路径，然后再由人工蚁群算法确定最优路径。最后，信息激素中的信息是随时更新，以便于适应战场动态变化。

在新算法使用中，有些时候探路人工蚁可能得不出无人机通往目标的航路路径，这很可能因为威胁点过多，或有的威胁度过高，此时，可以通过改变一个或几个威胁点的危险度，再由算法得出可能的航路。这为我部队通过战法或其他手段，降低其威胁度提供依据。当目标本身威胁度很高时，则合理采用无人机战法来解决，如采用“复眼”和“蜂群”战法［14］，这里与航路规划无关，不详细讨论。

3.2.1 改进的蚁群算法的基本假设

改进的蚁群算法基于以下基本假设:

①在航路规划仿真开始阶段。探路人工蚁按制约条件独自向目标方向行动，返回后，报告其所行路径的安全度和行程距离，给出初选的几条航路。

②蚁群选优仿真阶段。第一，人工蚁之间通过环境进行通信。通信内容具有安全信息，这样使安全度高的路径与信息激素高的路径趋于一致。第二，每只人工蚁仅根据其周围的局部环境做出反应，也仅对其周围的局部环境产生影响。人工蚁之间通过激素相互影响，并趋向于选择信息激素浓度高的方向。人工蚁对环境的反应由其内部模式决定。第三，在个体水平上，每只人工蚁仅根据环境做出独立选择。在群体水平上，单只人工蚁的行为是随机的，但蚁群通过自组织过程形成高度有序的群体行为。

以上基本假设构成了改进蚁群算法，基于以上基本假设的蚂蚁系统，实际上是一类多主体系统。在人工蚂蚁系统中，人工蚁设计成反应型主体，它包括一个感知器、一个反应器和一个内部执行系统。感知器收集环境信息如收集其他人工蚁的信息、纪录当地威胁度信息及所行航程;内部执行系统具有分析收集的环境信息，选择下一步路径(选择人工蚁较多的路径);反应器则在执行系统处理后，散布自身信息。反应型主体的执行系统是一组“条件—处理—动作”规则，将主体的感知器与效应器连接起来。

3.2.2 编程实现探路人工蚁对航路的初选

因为航路初选不是简单的类旅行商(TSP)问题，更不是简单的寻求最短路径的行为，因此在编程时，必须考虑约束条件。蚂蚁系统的主体——环境模型如图1所示。

图1 蚂蚁系统的主体——环境模型

威胁量不能超过指挥员的许可范围，即无人机的被毁歼概率不能超过某一特定的数值。无人机的总路径长度不能超过无人机的航程。一旦两者不能达成，则程序需要跳出循环，提示要求的任务是无法完成的。

由于该优化不便于用传统的优化论的方法求解，因此需要采取一定的人工智能求解最优路线，进而得出最优的目标函数值。

4 案例分析

假设无人机的作战目标是M1、M2和M3，发射回收阵地在X市，途经威胁点有M地、J地和W地，目标附近威胁点有T地、H地和Z地。利用MATLAB仿真运算，得出最优航路如图2所示，图中坐标系为虚拟平面直角坐标系，单位为km，每小格为20 km×20 km。

图2 蚁群算法改进前后对比

图2中单线是改进前航路，双线是改进后航路。由图2可见，改进前蚁群算法规划的航路虽然路程少但经过的威胁点多;而改进后的航路，尽量避开了威胁点，虽然路程远，但在无人机航程内，这损失与取得的战果相比是值得的。而且在仿真过程中由于采用探路人工蚁，改进后的算法在选择最优航路过程中需要的时间远远小于改进前时间。