2. 西北工业大学 无人机特种技术国防重点实验室, 陕西 西安 710065;
3. 光电控制技术重点实验室, 河南 洛阳 471009
航迹规划是提高无人机作战效能,实施精确打击的有效手段,是无人机自主航行的关键[1]。当前研究主要集中在确定环境中的单任务航迹规划问题,而战场上无人飞行器主要面临多种威胁且通常作战任务是由多个无人机共同完成,所以无人机要具备多批次协同航迹规划能力。而蚁群算法是近年来发展起来具有反馈、分布式计算和启发式搜索的方法。为了提高无人无人机的作战效能,提出了基于改进蚁群算法的航迹优化方法。
目前无人机航迹规划方法中,文献[2]虽然对蚁群算法进行改进,并且可以有效规划出最优的飞行航迹,但是该航迹规划仅限于二维平面的航迹规划,无法满足解决在实际应用中三维空间的航迹规划问题。文献[3]解决单批次静态威胁下的三维航迹规划,无法解决多批次协同三维航迹规划。文献[4]解决了动态实时情况下的航迹规划问题,但是该算法是二维平面下单批次的航迹规划,无法解决三维空间下多批次航迹规划。文献[5]解决了三维空间下的航迹规划,但是该算法无法解决多批次协同情况下的航迹规划。文献[6]针对多飞行器的协调航迹规划问题展开研究,提出了一种基于协同进化的多飞行器协调航迹规划方法,但是该算法解决的是静态威胁条件下的航迹规划,而且算法在寻找最优路径时容易陷入局部最优。文献[7]建立了基于协同系数的协同航迹性能评价指标,在此基础上,通过引入蚂蚁子群间的协同进化策略,设计并实现了基于协进化多子群蚁群算法的协同航迹规划算法,但是该基本蚁群算法的收敛速度过慢,降低算法的运算速度。目前,无人机航迹规划的算法虽然较多,但是针对多无人机协同三维航迹规划,现有航迹规划算法存在不足,本文提出基于改进蚁群算法的多批次协同三维航迹规划算法,该算法通过加权排序的信息素更新规则扩大各优劣蚂蚁的差异,提高了算法收敛速度,并采用自适应挥发系数调节来确保收敛速度的同时使算法具有全局寻优,解决了基本蚁群算法容易过早陷入局部最优缺点,然后运用改进蚁群算法,引入蚂蚁子群间多约束条件下的协同进化策略,解决了多批次协同三维航迹规划。
1 航迹规划建模1)建立数字地图。原始地图模型采用如下公式
将飞行区域的火力威胁等效成山峰加载到数字地图,采用模型如下:
将原始随机地形和山峰等效融合从成飞行区域中的数字地形图,融合算法如下:
2) 建立最小威胁曲面。在建立数字地图时,将静态的火力威胁等效成山峰威胁,由于威胁对数字地图的抬升,所以威胁曲面是地形高程抬高hc所构成的曲面。无人机在这个曲面上进行飞行所受的威胁最小,所以无人机的飞行航迹必须在这个曲面之上。所以最小威胁曲面为
3) 同时到达目标约束。同时到达目标是多飞行器航迹规划需要解决的主要问题。由于多个飞行器同时到达敌方上空,敌方防空火力很难在短时间内将其全部摧毁,因此,未被摧毁的无人机可以对目标实时打击,从而增加目标摧毁的概率。由于无人机本身性能的约束和作战任务的要求,无人机飞行速度范围为[vmin,vmax],所以要使无人机在时间范围[tmin,tmax]到达目标上空。
4) 基于水平投影面的模型转换算法。由于航迹规划是规划威胁最小的航迹,所以最优航迹一定在该威胁曲面之上,威胁曲面之上任何连接飞行起点到飞行终点的曲线都有可能成为无人机的飞行航迹,这些曲线在水平面的投影也是曲线,如果搜索到水平面的最优航迹,然后根据投影映射成三维航迹,这条航迹就是最优的三维航迹。
5) 水平投影的航迹代价函数。将空间最小威胁曲面进行投影之后,三维航迹规划简化成二维航迹规划,所以航迹规划的代价函数式为
蚁群算法是根据自然界中蚁群寻找食物的过程中,蚂蚁通过生物信息素向后传递信息影响后来者的行为。从数学的角度看,就是蚂蚁寻找从起点到终点的最优路径。蚁群算法的简要步骤是:首先对搜索区域网格上的所有节点给出合适的初始值,形成初始信息素矩阵,再将所有蚂蚁放在起点位置,同时向目标方向前进,每只蚂蚁在前进的过程中根据状态转移规则选择相邻且满足约束条件的节点,直到所有蚂蚁到达终点,即完成一次循环。循环过后依据每只蚂蚁经过的路径对全局信息素进行更新,对无蚂蚁经过的节点进行信息素挥发,重复这个过程,直到求出最优路径。
2.1 基本原理蚁群算法主要包括状态转换规则和信息素更新规则。状态转换规则:蚂蚁k(k=1,2,…,m)在路径搜索过程中根各个路径上的信息强度和下一个节点的代价,在可行集合中决定下一个节点的选择概率。从当前节点i到下一个节点j的转移概率为
生物信息素更新准则:只有生成阶段最优解的蚂蚁才能进行全局调整,m只蚂蚁搜索完成一次后在m条路径中确定最优的一条路径,加大其信息强化量,以提高收敛速度。全局调整准则见(7)式
在一次循环中可行性节点增加的信息总量为
在基本蚁群算法的应用中发现,该算法容易陷入局部最优以及收敛速度慢等缺陷。为了克服这些缺陷,提高蚁群算法的搜索速度和全局寻优能力是改进蚁群算法的主要目标。 2.2.1 待选航迹节点间的转移规则
蚂蚁按照公式(10)和(11)的转移方法从一个节点转移到下一个节点
为了解决基本蚁群算法收敛速度慢的缺陷,将遗传算法中的排序扩展到蚁群算法中,利用排序改进算法的收敛速度,即排序加权的信息素更新规则。
该算法的思想是:对于每次迭代完成之后生成的路径按照长短依次排序为(L1≤L2≤…≤Lm),每只蚂蚁对信息素更新由其在循环中生成路径的长短决定,路径越短信息素越大,每只蚂蚁对应信息素更新的加权系数为λk(0<λ<1,0 <k <m),该数列为等比数列,使得各个蚂蚁的优劣表现在更新的过程中加大,从而提高对较优蚂蚁的选择概率,降低较差蚂蚁的选择概率。
基于排序加权的全局信息素更新规则如下:
在蚁群路径搜索的过程中,由于挥发系数ρ的存在,那些较少被搜索到甚至从未被搜索到的解上的信息素会减小接近与0。或者ρ过大时,随着信息素增大,该路径被选择的可能性过大,都会降低该算法的全局搜索能力和解的多样性。若ρ减小,算法的全局搜索能力会提高,但是收敛性能变差,所以采取自适应的挥发系数调节。ρ的初始值取较大的值来保证收敛速度,但是随着迭代次数的增大,ρ减小,为确保算法的全局寻优,同时设定挥发系数的下限ρmin来确保算法的收敛性。
改进后的蚁群算法如图 1所示。
3 多飞行器协同航迹规划算法在多飞行器协同航迹规划中,飞行器集合为V={V1,V2,…,VNv},Nv为飞行器的数量,飞行器起点和终点分别为S={S1,S2,…,SNv},T={T1,T2,…,TNv},航迹规划的代价函数为:
多机协同航迹规划算法步骤如下:
1) 初始化参数,每个无人机Vj对应一个蚁群Antj,共Nv个种群,每个种群的信息素结构保持;
2) 对于无人机Vj,j=1开始一个循环过程;
3) 用本文改进的蚁群算法让蚁群Antj开始寻找最优路径,求解Vj的飞行航迹;
4) 如果j=Nv,则j=j+1,然后转到步骤3),否则转到步骤5);
5) 如果算法达到规定的迭代次数,则循环结束,否则转到步骤2)。
4 仿真结果 4.1 改进蚁群算法和基本蚁群算法对比该仿真的主要目的是验证本文提出的改进蚁群算优于基本蚁群算法。
蚁群算法的基本参数为:Nant=20,Q=4,α=2,β=6,Nc=100,ρmin=0.2,ρmax=0.85,q=0.2,λ=0.5,μ=0.5,k=0.5。地形参数为[a,b,c,d,e,f,g]=[10,0.2,0.1,0.6,0.1,0.1,0.1],飞行区域等效威胁的参数为X0=[10,0.2,0.1,0.6,0.1,0.1,0.1]。
通过2种方法的仿真对比结果显示,改进蚁群算法在计算效率明显优于基本蚁群算法,而且能够搜索出更优的三维航迹。从收敛曲线中可以得到,改进蚁群算法的收敛性明显优于基本蚁群算法。
4.2 改进蚁群算法的多批次协同航迹规划蚁群算法的参数和等效地形参数与算例4.1中的仿真参数相同。同时在仿真中对动态多批次威胁进行仿真。本文采样3架飞机从不同起点飞往不同的终点进行协同作战的航迹规划。多批次协同航迹规划仿真如图 6所示。
5 结 论本文提出了基于改进蚁群算法的多批次无人机协同航迹规划算法。该算法采用基于加权排序的信息素更新规则和信息素挥发系数自适应调节方法,通过加权排序来扩大蚂蚁的优劣排序从而提高算法的收敛速度,通过挥发系数的自适应调节在确保收敛速度的同时避免因信息素挥发过快使解陷入局部最优,从而使蚁群全局寻优。同时用该改进的蚁群算法进行多批次无人机的航迹规划,通过多个蚂蚁子群协同进化实现多批次的协同航迹规划。最后的仿真结果表明,改进的蚁群算在搜索效率和最优路径的规划方面都优于基本蚁群算法。而且该改进算法运用于多批次无人机协同航迹规划,能够对多批次无人机航迹规划问题进行有效求解。
[1] | Cao H Y, Cao Y C, Chen Y Q. Autopilots for Small Unmanned Aerial Vehicles: a Survey[J]. International Journal of Control Automation and Systems, 2010,8(1):36-44 |
Click to display the text | |
[2] | 唐必伟, 方群, 朱战霞, 等. 基于改进蚁群算法的无人飞行器二维航迹规划[J]. 西北工业大学学报, 2013,31(5):683-688 Tangy Biwei, Fang Qun, Zhu Zhanxia, et al. Effective 2D Route Planning of UAV Based on Improved Ant Colony Algorithm[J]. Journal of Northwestern Polytechnical University, 2013,31(5):683-688 (in Chinese) |
Cited By in Cnki (5) | |
[3] | 刘莉, 于成龙, 王祝,等. 小型无人机快速三维航迹规划方法[J]. 系统工程与电子技术, 2013,35(12):2521-2526 Liu Li, Yu Chenglong, Wang Zhu, et al. Fast 3D Route Planning Method for Small UAV[J]. Systems Engineering and Electronics, 2013, 35(12): 2521-2526 (in Chinese) |
Cited By in Cnki (6) | |
[4] | 李士波,孙秀霞,王栋,等. 无人机动态环境实时航迹规划[J]. 系统工程与电子技术, 2007,29(3):399-401 Li Shibo, Sun Xiuxia, Wang Dong, et al. Real-Time Route Planning Algorithm for Unmanned Aerial Vehicles in Dynamic Environment[J]. Systems Engineering and Electronics, 2007, 29(3): 399-401 (in Chinese) |
Cited By in Cnki (20) | |
[5] | 韩攀, 陈谋, 陈哨东,等. 基于改进蚁群算法的无人机航迹规划[J]. 吉林大学学报, 2013,31(1):66-72 Han Pan, Chen Mou, Chen Shaodong, et al. Path Planning for UAVs Based on Improved Ant Colony Algorithm[J]. Journal of Jilin University, 2013,31(1):66-72 (in Chinese) |
Cited By in Cnki (9) | |
[6] | 郑昌文, 丁明, 周成平,等. 多飞行器协调航迹规划方法[J]. 宇航学报, 2003, 24(2): 115-120 Zheng Changwen, Ding Ming, Zhou Chengping, et al. Clobber Probability of Pilotless Aircraft Based on Error Stochastic Process[J]. Journal of Astronautics, 2003, 24(2): 115-120 (in Chinese) |
Cited By in Cnki (44) | |
[7] | 苏菲,彭辉,沈林成. 基于协进化多子群蚁群算法的多无人作战飞机协同航迹规划研究[J]. 兵工学报, 2009,30(11): 1562-1567 Su Fei, Peng Hui, Shen Lincheng. Research on Multi-UCAV Cooperative Route Planning Based on Coevolutionary Multi-Ant Colony Algorithm[J]. Acta Armamentarii, 2009,30(11): 1562-1567 (in Chinese) |
Cited By in Cnki (17) |
2. Science and Technology on UAV Laboratory at Northwestern Polytechnical University, Xi'an 710065, China;
3. Science and Technology on Electro-Optic Control Laboratory, Luoyang 471009, China