王 芳，李昆鹏

(1．西安航空学院 航空工程系，陕西 西安710077； 2．长安大学 机械学院，陕西 西安710064)

1 引言

航路规划( Path Planning)是指在目标点与起始点之间，为运动物体寻找满足某种性能指标和某些约束的线路、路径[1]。随着雷达探测跟踪能力的不断增强以及地面防空系统日益完善，无人机面临的战场环境也不断变化，因此在有限时间内规划全局最优路径，使无人机能够顺利地往返可疑目标点( 有时是多个目标点) ，是保障无人机安全性和作战效率的关键所在，也是目前航路规划有待解决的问题。

目前，国内外常用的无人机航路规划算法大致可分为两类：确定型(或启发式)搜索算法和随机型(或智能优化)搜索算法。相对于确定型搜索算法，随机型算法在求解复杂航路规划问题上具有明显优势[2]。智能优化算法是随机型搜索算法中的一个大类，由于其思想简单，易于操作，且对优化函数没有特殊要求，因此近年来被广泛应用于航路规划，常用的有遗传算法[3]、粒子群算法[4]和蚁群算法(AOC)[5]等。上述仿生规划算法虽然可以获得较高精度的可行路径，但是通常算法存在易于陷入局部最优和收敛速度慢等问题，难以满足航路规划实时性的要求。

为了解决上述问题，本文提出一种改进的AOC航路规划算法，通过采用人工势场法优化AOC，可以很好地改善AOC算法搜索中的盲目性以及收敛速度慢等问题。

2 航路规划问题描述

无人机在巡航阶段，一般仅考虑其横侧向运动，故可将三维航路规划问题转换成在某一高度下二维平面航路规划。在航路规划问题中，通常障碍、火力威胁区域、探测威胁区域是已知的，故可对飞行任务空间构建栅格环境模型。

无人机全局航路规划不仅要依据预先获得的威胁信息寻找安全的飞行轨迹，而且还要做到从起点到目标点所用燃油最小。本文采用如下方程来定义航路性能指标[6]：

对于每段航路的威胁代价，采用加权平均的办法，威胁代价定义为：

上式中，N为无人机当前飞行位置探测到的威胁个数，Kj为第j个威胁的强度；Rij为该段航路上的点到第j个威胁中心的距离。

3 算法设计

蚂蚁尽管个体行为比较简单，但是由这些简单个体所组成的群体却表现出极其复杂的行为特征。考察无人机航路规划问题，受自然界中蚂蚁路径搜索启发而产生的蚁群算法，与航路规划问题有着自然的联系，因此结合无人机航路规划特点，本文采用改进蚁群算法，搜索通往目标点的最优航路。

3.1 基于AOC的航路规划

在路径选择阶段，蚂蚁会根据路径上的信息素来选择运动方向，t时刻蚂蚁k从节点i转移到节点j的概率按如下式计算[7]：

式中，τij(t)t时刻节点i和j之间残留的信息素；α信息素启发因子；ηij(t)t时刻节点i和j之间的期望启发函数；β期望启发因子；allowedk=(Tabuk)蚂蚁下一步允许选择的节点，Tabuk为禁忌表，记录蚂蚁k所走过的节点。

期望启发函数定义为节点i和j之间的距离dij的倒数，即，

(2)

蚂蚁走过的路径上会留下信息素，同时为了避免路径上因残留信息素过多而造成启发信息被淹没，信息素会随着时间的流逝而挥发，设ρ为信息素挥发系数且(0≤ρ<1)，t+Δt时刻节点i和j上的信息素更新规则为[7]：

τij(t+Δt)=(1-ρ)·τij(t) +Δτij(t)

(3)

(4)

式中，Q信息素强度；Lk蚂蚁k在本次循环中所走过路径的总长度；pk(begin,end)蚂蚁k在本次循环中从起点到终点所走过的路径。

在蚁群航路规划算法中，初始解的产生带有随机性，不利于路径的快速搜索；同时，由于蚁群算法的正反馈机制，使得质量不高的初始解可能使算法收敛于次优解，即陷入局部极值点。因此，高效地获得较高质量的初始解，同时改善蚁群路径搜索中的盲目性对提高算法性能具有重要意义。

3.2 基于人工势场优化的AOC航路规划

人工势场路径规划因其模型简单、计算量小和实时性好等优点，在实时避障中得到了广泛的应用，但由于其中没有涉及到优化过程，所以得到的路径虽然是安全的，但是并非最优。考虑到蚁群算法在航路规划中存在的问题，有效地融合人工势场法和蚁群算法的优点来实现最优路径的搜索，必然会改善单一规划算法的规划效果。

人工势场法中采用与位置有关的势函数来进行路径规划控制，其基本思想是：首先在机器人运行空间构建虚拟力场，包括引力场和斥力场，引力场随机器人与目标的距离减小而递减，方向指向目标，斥力场随机器人与障碍物的距离减小而增大，方向由障碍物指向机器人，且在障碍物处有一个极大值，整个势场的合力是引力和斥力的叠加，则机器人在环境中的运动可视为在虚拟力场作用下的运动。引力场、斥力场和合力场的数学描述如下：

引力场函数为：

Uatt(q)=0.5ξρm(qr,qgoal)

(6)

式中，ξ为引力位置场正增益系数；qr为机器人在空间中的位置；qgoal为目标点在空间中的位置；ρ为机器人qr和目标qgoal之间的欧式距离；m为引力位置场阶次，通常取吸引力场为抛物线形状，即m=2。

斥力场函数为：

式中，η为斥力位置场正增益系数；ρ为机器人qr和障碍物qobst之间的欧式距离；ρ0为障碍物影响范围。ρmin为机器人与障碍物之间所允许的最小距离，增加的ρn(qr,qgoal)项为机器人到目标点的最短距离，n为优化参数，这样，当机器人向目标运动，到达目标点时，对应的斥力为零，从而可以保证机器人在目标点处达到全局最小。

分别对引力场和斥力场函数按照相对位置的负梯度方向求导得到引力和斥力：

Fatt(q) =-(Uatt)

=-0.5mξρ(qr,qgoal)m-1ρ(qr,qgoal)

=-0.5mξρ(qr,qgoal)m-1nrg

(8)

Frep(q) =-(∑Urep)

(9)

式中，nro为机器人指向障碍物的单位矢量；nrg为机器人指向目标点的单位矢量。

将人工势场法得到的规划结果作为蚁群算法较高质量的初始解，对初始到达的栅格进行邻域栅格信息素的初始化，从而可以大大提高路径搜索的效率，算法具体计算过程如下：

步骤1 初始化算法参数：包括蚂蚁数m，最大循环次数Tmax，α、β、l及人工势场法中的相关参数；

步骤2 初始化规划任务，确定是否初次到达的栅格；

步骤3 利用势场法，计算蚂蚁在该栅格时受到的引力和斥力，并计算基于势场法的转移角度；

步骤4 计算势场法转移角度与蚂蚁相邻八个栅格转移角度的差，如图1所示；

步骤5 对上述角度差进行排序，角度差越小说明越接近势场法转移方向，此时对相应的转移方向赋予较大的信息素，而其余七个方向，按照由小到大，分别赋予较小的初始信息素。

图中，合力与方向7的角度差最小，则方向7即为蚂蚁转移的最佳栅格方向，因此将该栅格信息素赋予最大权值，势必提高蚂蚁的转移概率，其余按照夹角由小到大分别赋予较小的权值，由于采用轮盘赌的选择方法，因此大的权值，也就是信息素强度高的栅格被选中的机会较大，同时，信息素强度低的栅格也存在被选择的可能性。

图1 最佳栅格方向计算

步骤6 经过路径信息素强度初始化之后，采用蚁群算法进行路径搜索，蚂蚁在相邻的位置间转移，按照公式(1)定义的转移概率进行，而当蚂蚁到达目标，完成一次搜索后，按照式(3)进行信息素的更新，完成一次群体优化，不断重复此过程，最终完成最佳路径的搜索。

4 仿真结果

为了验证文中算法的有效性，针对不同环境给出了算法的仿真实验测试。本文提供了如图2所示两种环境，环境一相对比较简单，障碍物较少。环境二比较复杂，且存在明显的局部极小。针对两种环境，分别对基本蚁群算法，基于势场法优化的蚁群算法进行规划对比测试，结果如图3所示。考虑到算法的随机性，仿真中，每种环境进行了50次独立随机测试。算法中的具体参数设置分别为：最大循环次数为Tmax=50，每次出动的蚂蚁数为m=15，α=1，β=2，ρ=0.2。

图3(a)(b)分别为环境一中两种规划算法的蚂蚁信息素演化曲线。图5(a)为两种算法最优规划结果。从结果可见，在环境简单时，两种方法基本上都能得到最优路径。从信息素演化图可见ACA算法(图3(a))在路径搜索过程中带有一定随机性，而APFOA方法则减少了盲目搜索，因而最优路径的规划效率也较高。

图4(a)(b)为环境二中两种规划算法的蚂蚁信息素演化曲线。图5(b)为两种算法最优规划结果。和环境一相比，环境二更为复杂，且存在明显局部极小，虽然两种方法最终都能收敛到各自的最优路径，但从蚁群信息素演化图可见，在人工势场作用下，蚂蚁的路径搜索更趋理性，减少了对明显非最优路径的尝试，体现了较强的规划能力。

(a)环境一(b)环境二(a)ACA (b)APFOA

图2仿真测试环境图3环境一信息素演化曲线

(a)ACA (b)APFOA (a)环境一最优路径(b)环境二最优路径

图4环境二信息素演化曲线图5最优路线

5 结语

蚁群算法是一种仿生学随机搜索全局寻优算法，具有正反馈、并行性等特点，但在搜索初期具有盲目性和随机性。人工势场法搜索效率高，导向性强，具有良好的局部搜索性能。本文针对复杂环境中无人机航路规划问题，融合蚁群全局航路规划算法和人工势场局部规划各自优点，提出一种势场法优化的蚁群算法，不但可以避免局部优化算法容易陷入局部极值的问题，而且可以改善蚂蚁路径搜索的盲目性，从而显著提高收敛速度。仿真实验测试表明，在收敛速度及最优规划方面，经过势场法优化的蚁群算法整体上要明显好于蚁群算法和人工势场法。

[1] 庄夏，戴敏，贺元骅.基于改进AOC算法的无人作战飞机航路规划设计[J].计算机测量与控制，2014，22(1)：270-272.

[2] 刘钢，老松杨，谭东风，等. 反潜导弹航路规划问题的研究现状与发展[J].自动化学报，2013，39(4)：347-359.

[3] 郑锐,冯振明,陆明泉.基于遗传算法的无人机航路规划优化研究[J].计算机仿真，2011， 28(6)：88-91.

[4] Jung L F,Jared S K,James H O,et al.Three-dimensional multi-objective path planning of unmanned aerial vehicles using particle swarm optimization[C] // In: Proceedings of the 48th AIAA/ASME/ASCE/AHS Structures, Structural Dynamics, and Materials Conference. Hawaii: AIAA, 2007:1881-1890.

[5] 刘振峰，谢洪森，危水根.基于蚁群遗传算法的三维飞行器航路规划[J].计算机仿真，2013, 30(9)：121-125.

[6] 税薇，葛艳，韩玉，等.基于混合蚁群算法的无人机航路规划[J].系统仿真学报，2011，23(3)：574-576.

[7] 袁明新，王孙安，李昆鹏，等.基于势场法优化的蚁群免疫网络路径规划研究[J].系统仿真学报，2009，21(15)：4686-4690.