一种基于航迹片段的多蚁群协同规划算法

刘慧娟,蔡 超,孙希霞

(华中科技大学自动化学院多谱信息处理技术国防科技重点实验室,武汉430074)

一种基于航迹片段的多蚁群协同规划算法

刘慧娟,蔡 超,孙希霞

(华中科技大学自动化学院多谱信息处理技术国防科技重点实验室,武汉430074)

在协同航迹规划过程中,针对传统蚁群算法存在的收敛速度慢、航迹易冲突等问题,结合由航迹片段构成的网络图特点,提出一种基于多蚁群的飞行器协同航迹规划算法。将蚁群算法中的人工蚁群划分为与飞行器数量相对应的蚂蚁子群,通过引入异质信息素实现子群之间的竞争,采取基准长度协同进化的方法引导子群规划出满足时间协同要求的航迹,利用迷失蚂蚁信息素更新策略加快算法收敛速度。实验结果表明,针对不同规划任务,在多种复杂规划环境中,该算法都能生成满足时间和空间约束的协同飞行航迹。与传统蚁群算法相比,该算法能够将规划速度提高2倍～3倍,所规划出的航迹具有更好的时空协同性能。

协同航迹规划;网络图;多子群;蚁群算法;异质信息素

1 概述

协同航迹规划技术是提高无人飞行器协同作战效能,保证无人飞行器协同作战顺利实施的关键技术之一［1］。其目标是在飞行器性能允许的范围内,为多架飞行器设计从起点到目标的飞行航迹,要求在尽可能降低多飞行器执行飞行任务代价的同时满足多飞行器执行任务的协同要求,是一个 NP难题［2］。

针对多飞行器协同规划问题中存在的搜索空间大、规划速度慢等问题,本文采用基于航迹片段图(航迹网络图［3］)的方法进行规划,将航迹规划问题转化为一个图搜索问题,以减少搜索空间、加快搜索速度。航迹片段图是一种类似于Voronoi［4］图或路线图［5］的图结构,图的边由一系列满足飞行约束条件的航迹片段构成,节点是一系列的导航控制点。常用的图搜索算法有Dijkstra算法［6］、遗传算法［7］、蚁群算法［8］、A*算法［9］等。蚁群算法作为一种新兴的演化计算技术,由于其灵活性和自我组织等特点,近年来成为研究热点,并被用于解决多飞行器协同规划问题［10］。

蚁群算法相比于其他进化算法,在求解协同航迹规划问题时,具备无需编码、求解效率高等优点［11］。但是一般的蚁群算法只考虑了同一种群内部信息素的影响,在解决多任务问题时无法很好地满足协同约束。文献［12］提出一种多蚁群协作模式,解决了约束条件复杂的组合优化问题。

本文针对协同航迹规划存在的问题,设计了多蚁群协同规划算法,将人工蚁群划分为与飞行器对应的蚂蚁子群,同一子群内部通过信息素引导个体趋向最优路径,采用异质信息素互斥策略降低航迹冲突概率,增加迷失蚂蚁信息素更新策略提高规划速度。

2 规划空间及协同问题描述

2.1 协同航迹规划问题描述

本文的规划空间为构造完毕的航迹网络图,其局部示意图如图1所示,其中椭圆形区域为禁飞区。航迹网络图表示为图G=(V,E),其中,V为图中节点集合;E为航迹片段(图G中的边)的集合,节点位置为(x,y,z)。

图1 航迹网络的局部示意图

设V={Vi,i=1,2,…,Nv}为执行协同规划任务的无人飞行器集合,S={Si,i=1,2,…,Ns}和T= {Ti,i=1,2,…,Nt}分别为与各无人飞行器相对应的起始点和目标点所构成的集合,F={Fi,i=1,2,…,Nf}为禁飞区集合,规划空间为在R行C列(R和C为常数)的网格环境下构造出的航迹网络图。Vi的航迹Ri由一系列航迹片段{Ei,i=1,2,…,Ne}构成,航迹片段由一系列导航点{Pk=(xk,yk,zk),k=1, 2,…,N}表示。

假设所有飞行器以速度v匀速飞行,本文中的协同规划问题为:在给定的航迹网络图上为飞行器集合V规划出从起始点到目标点的代价最小且满足协同约束的协同航迹组。

2.2 协同约束分析

多飞行器协同航迹规划除了要满足飞行器自身飞行约束外,还必须满足多机协同约束,包括空间协同约束和时间协同约束。

(1)空间协同约束

多架飞行器协同执行任务过程中,任意时刻各飞行器之间必须满足一定的空间安全间隔ds,设Pi(t)为Vi在t时刻的位置,即要求任意时刻两飞行期间的欧氏距离大于等于间隔ds:

(2)时间协同约束

在协同规划问题中,飞行器到达目标的时间往往存在一定的时间窗［0,T］限制,即对协同规划任务中飞行器最早抵达目标和最晚抵达目标的时间间隔有一定的要求。任务时间约束可表达如下:

其中,Tmax,Tmin分别为飞行器集合V中最早抵达目标点和最晚抵达目标点的时间。

2.3 协同航迹代价函数设定

对于多飞行器协同航迹规划问题,一方面应考虑单航迹本身的代价,另一方面还应考虑航迹的协同性能。

(1)单航迹代价

飞行器的航迹Ri由起始点到目标点之间相互连接的航迹片段构成,因此单航迹的代价为构成该航迹的片段代价之和。每段航迹片段上都存储了相应的航迹长度代价、威胁代价、转弯次数代价等信息,由此可以得到航迹Ri的单航迹代价:

其中,nr为构成航迹Ri的航迹片段数目;Fl(Ek),Ft(Ek)和Fz(Ek)分别为航迹Ri上第k条航迹片段的航迹长度代价、威胁代价和转弯次数代价;a,b和c分别为对应代价的加权系数,三者之和为1。

(2)多航迹协同代价

对于多航迹的协同性能,不能仅考虑多条航迹的代价之和,还需考虑时间协同性能。定义协同系数λ来衡量协同航迹对时间协同约束的满足程度:

显然,时间约束要求λ不大于1,λ越接近于0,时间协同性能越好(发射段和攻击段避碰问题另行考虑)。

综合单航迹代价、协同系数以及协同约束可得航迹组的协同评价指标:

其中,F为综合航迹代价;N为协同航迹数目。2个不等式分别代表时间和空间协同约束。协同航迹规划目标为:在满足时间和空间协同的情况下,尽可能地减小F的取值。

3 多蚁群协同规划算法

多飞行器协同航迹规划问题包含多类协同约束,本文基于协同进化思想,设计了多子群蚁群算法。

3.1 多子群蚁群协同进化机制

多无人飞行器协同航迹规划中,每架飞行器对应不同的任务,因此可将蚁群算法中的人工蚁群划分为与飞行器对应的蚂蚁子群。同一个子群中的蚂蚁个体之间相互合作,不同子群之间存在竞争关系,如图2所示。

图2 多子群蚁群的协同进化

在图2中,黑色原点代表蚂蚁,ACi对应于Vi的蚂蚁子群,Antij为第i个子群中的第j只蚂蚁个体,m为子群的规模。蚂蚁子群之间通过信息素进行通信。每个蚂蚁子群散发不同种类的信息素,并维护各自的信息素结构。蚁群算法采用信息素更新策略引导蚂蚁个体选择优化路径,蚂蚁个体根据备选航迹片段上的信息素浓度及启发信息大小计算转移概率,依据状态转移规则选择相应的航迹片段。

为实现各任务的时间协同,依据基准长度协同进化思想,使所有子群都规划出最接近基准长度的航迹。一次规划结束后,若规划次数达到最大迭代次数或者综合协同代价与上次规划结果的差值小于最小基准值ΔF,则停止迭代,否则对基准长度进行调整,调整方法为:

其中,Ls为该次协同规划过程中的基准航迹长度;Lmax为所有起始点到目标点直线距离中最大的值;i为迭代次数;MAX为最大迭代次数;Lave为上一代航迹组的平均长度;α为基准长度进化系数;ΔL为上一代规划产生的航迹与标准航迹长度的最大差值。

本文在状态转移概率计算公式中加入异质信息素,在子群间引入竞争机制,减少了不同子群的蚂蚁挑选到同一航迹片段的概率,避免产生冲突,实现空间协同。同时考虑到未成功找出路径的蚂蚁个体(迷失蚂蚁)的经验信息,在带精英策略蚁群算法［13］信息素更新策略基础上,加入迷失蚂蚁信息素更新以减少其他蚂蚁的迷失概率,加快算法的收敛速度。

3.2 基于异质信息素互斥的状态转移

子群i中的蚂蚁按照轮盘赌选择规则,决定下一步移向哪个节点,这个过程称为状态转移。与传统的图搜索问题不同,本文搜索的航迹网络图中,2个节点之间可能存在多条航迹片段(边)。因此本文将传统的蚁群算法进行图搜索中的节点选择问题转化为航迹片段选择问题,即通过选择航迹片段来确定到达的节点。为避免航迹冲突,引入异质信息素互斥的概念,在进行状态转移时不仅考虑本子群的信息素,同时考虑其他子群信息素浓度对航迹片段选择的影响。如果蚂蚁当前位于航迹片段Er,下一步可选航迹片段的集合为E(r),从航迹片段Es到集合E(r)中的Es片段的转移概率为:

其中,Pi(r,s)为子群i中位于航迹片段Er上的蚂蚁挑选航迹片段Es的概率值;τis和F(Es)分别为子群i在航迹片段Es上留下的信息素值和片段Es的代价值;~τis为引入的异质信息素,其值为除子群i外的其他蚂蚁子群在航迹片段Es上留下的信息素的最大值;α,β和γ分别为信息素系数、启发信息系数和异质信息素系数。

3.3 信息素更新

蚁群算法通过信息素的更新对蚂蚁起到引导作用。当蚂蚁子群中所有个体完成了当前迭代过程中的路径搜索后,如下原因会造成部分蚂蚁没有能够成功规划出路径:(1)可能的航迹片段搜索完毕没能到达目标;(2)经过的路径长度超过了长度约束; (3)因机动性能约束或目标进入方向约束使得不能到达目标。这类蚂蚁个体即前文定义的迷失蚂蚁,这些蚂蚁应该对后续蚂蚁起到警示作用。因此,本文对规划出的路径上的片段采用带精英策略蚂蚁系统的更新策略,同时对迷失蚂蚁所经路径上的片段采用迷失蚂蚁信息素更新策略进行更新,减少后续蚂蚁迷失的概率。

(1)带精英策略的信息素更新

子群i完成一次迭代后,从规划出的路径中找出与标准航迹长度值最接近的航迹作为最优航迹,找出这条航迹的蚂蚁被称为精英蚂蚁。假设所有成功规划出路径的蚂蚁所经过的片段集合为E(S),对集合中片段Es上的信息素按照下式更新:其中,τis(n)和τis(n-1)分别为迭代前后片段Es的信息素值;ρ为信息素挥发因子(0＜ρ＜1);Δ表示第k只蚂蚁在本次迭代中留在片段Es上的信息素量;mk为子群k中成功规划出路径的蚂蚁数量;Δτis表示本次迭代中片段Es的信息素的增加量;Δτ*is表示精英蚂蚁引起的片段Es上的信息素增量;Q为信息素常量;mσ为精英蚂蚁数量;ΔLk和ΔL*分别为第k只蚂蚁构造的航迹和最优航迹与标准航迹的长度差值。

(2)迷失蚂蚁的信息素更新

假设子群i本次迭代中迷失蚂蚁所经路径上的片段集合为E(F),其片段Es上的信息素的更新策略如下:

其中,mj为子群i第n次迭代中的迷失蚂蚁数目;为第j只迷失蚂蚁在片段Es上产生的衰减系数;Lj为蚂蚁j所经路径的总长度;Ljs为蚂蚁j到达片段Es时所经路径的长度。

迷失蚂蚁信息更新机制的作用主要表现在:对迷失蚂蚁所经路径上的信息素进行按比例衰减,从而对后续蚂蚁个体产生引导作用,减少后续蚂蚁迷失的概率。

3.4 算法步骤

本文算法首先将蚁群算法中的人工蚁群分为多个与飞行器对应的蚂蚁子群,每个子群采用上文提出的状态转移规则和信息素更新策略为对应飞行器构造与标准航迹长度最接近的航迹,并通过航迹综合代价值判断是否需要动态调整标准航迹值,以构造出符合协同约束的协同航迹组,具体算法步骤如下:

步骤1 初始化蚂蚁子群及相关参数。

步骤2 对所有的蚂蚁子群均执行步骤3～步骤5。

步骤3 子群中的蚂蚁个体按照状态转移规则为对应飞行器构造航迹。

步骤4 一次迭代完毕后,根据构造的航迹结果对信息素结构进行更新。

步骤5 迭代次数达到子蚁群算法上限或构造出的最优航迹与上次迭代相近,则停止迭代,否则跳转到步骤3。

步骤6 在所有子群都完成上述过程后,若达到群体最大迭代次数或者规划出的综合航迹代价与上一次的差值小于标准差值,则停止迭代,否则更改标准航迹长度,并跳转到步骤2。

4 实验结果及分析

在CPU为CoreE7200 2.53 GHz、内存为2.0 GB的PC机上,对算法进行了验证。PC机的操作系统为Windows XP,程序开发环境为Visual Studio 2005。实验中使用在分辨率为90 m的3 000×3 000像素的数字地形高程图上生成的航迹网络图,网络图由3 680条航迹片段构成。

本文对异质信息素和迷失蚂蚁信息素更新的效果、算法对不同任务的适应度以及算法对不同环境的适应度进行了实验。每个子群中蚂蚁个体的总数是一个恒量,蚂蚁数量太多容易导致次优路线的快速增长且计算量增大,然而,蚂蚁数量太少时又会由于信息素的挥发和通信的减少而导致蚂蚁间的协作行为减弱,通过多次测试实验,本文将子群规模定为80只,子群最大迭代次数定为40代。由于信息素随着时间的推移可能会累加到一个比较大的量,而片段上的代价值则是一个定值,为了避免信息素作用太强而过早陷入局部最优,将α,β,γ,ρ等参数取值分别定为0.8,0.6,0.7和0.3,动态调整标准航迹最大迭代次数为5次。

实验1 为了验证异质信息素和迷失蚂蚁信息素的效果,在规划环境、协同任务一致的情况下进行2组对比实验。

(1)为验证迷失蚂蚁信息素的作用,对多蚁群协同算法和未采用迷失蚂蚁信息素更新的蚁群算法进行对比实验,图3给出了规划时间曲线。可以看出,在相同任务和规划环境条件下,采用多蚁群协同算法规划的时间均比无迷失蚂蚁更新策略的算法短,说明迷失蚂蚁信息素更新策略能加快算法收敛,提高规划速度。

图3 规划时间对比

(2)为验证异质信息素的作用,对多蚁群协同算法和未加入异质信息素的蚁群算法进行对比实验。在10次实验中,采用无异质信息素蚁群算法的规划结果中有2次出现了碰撞的情况,而多蚁群协同算法规划结果均满足空间协同,说明基于异质信息素的状态转移策略能够降低碰撞概率,提高空间协同能力。图4为其中一次对比实验结果和三维仿真截图。

图4 对比实验结果和三维仿真

实验2 为了验证多蚁群协同算法对不同任务的适应度,在相同环境下对不同规划任务进行实验,图5给出了部分实验结果图,表1给出相应的实验数据。

图5 不同任务的规划结果

表1 不同任务的规划结果数据

实验结果均满足空间协同,且从表1可以看出,每个任务的协同系数均小于1,说明算法能够为不同任务规划出符合时间和空间协同的航迹。

实验3 为验证多蚁群协同算法对不同环境的适应度,对同一任务在不同环境下进行实验,图6给出部分实验结果,表2给出了相应的实验数据。

图6 不同规划环境下的规划结果

表2 不同规划环境下的规划结果数据

表2中的数据和实验结果验证了本文算法能够在不同的规划环境下规划出满足时间和空间协同的协同航迹。

5 结束语

多无人机协同规划问题是一个复杂的大规模优化问题,本文针对该问题提出了一种基于航迹片段的多蚁群协同规划算法。该算法在蚁群之间引入竞争机制,并在信息素更新机制中引入迷失蚂蚁信息素更新策略。实验结果表明,该算法能够在不同环境下为不同任务规划出可行的协同飞行航迹,并且在规划速度上优于传统蚁群算法,同时能够降低飞行器的碰撞概率,更好地满足协同规划的空间协同约束。由于蚁群算法是一种随机进化算法,因此对于如何平衡航迹的优化质量和时间消耗需要进一步研究。

［1］ 郑昌文,严 平,丁明跃,等.飞行器航迹规划研究现状与趋势［J］.宇航学报,2007,28(6):1441-1446.

［2］ 唐 强,张翔伦,左 玲.无人机航迹规划算法的初步研究［J］.航空计算技术,2003,33(1):125-128.

［3］ Li Shidong,Ding Mingyue,Cai Chao.A Novel Path Planning Method Based On Path Network［C］// Proceedings ofthe6th InternationalSymposium on Multispectral Image Processing and Pattern Recognition. Wuhan,China:［s.n.］,2009.

［4］ McLain T,Beard R.Trajectory Planning for Coordinated Rendezvous of Unmanned Air Vehicles［C］//Proceedings of AIAA Guidance Navigation and Control Conference.Clearwater,USA:AIAA Press,2000:1247-1254.

［5］ 严 平,丁明跃,周成平.航迹规划的一种路线图方法［J］.计算机工程与应用,2004,40(17):218-221.

［6］ Dijkstra E W.A Note on Two Problems in Connexion with Graphs［J］.Numerische Mathematik,1959,1(1):269-271.

［7］ 王银年.遗传算法的研究与应用［D］.无锡:江南大学,2009.

［8］ Colorni A,Dorigo M,Maniezzo V,et al.Distributed Optimization by Ant Colonies［C］//Proceedings of the 1st European Conference on Artificial Life.France,Paris: Elsevier Publishing,1991:134-142.

［9］ 李 季,孙秀霞.基于改进A-star算法的无人机航迹规划算法研究［J］.兵工学报,2008,29(7):788-792.

［10］ Shtovba S D.Ant Algorithms:Theory and Applications［J］.Programming and Computer Software,2005,31(4): 167-168.

［11］ Dorigo M,Gambardella L M.Ant Colony System:A Cooperative Learning Approach to the Travelling Salesman Problem［J］.IEEE Transactions on Evolutionary Computation,1997,1(1):53-66.

［12］ Nowé A,Verbeeck K,Vrancx P.Multi-type Ant Colony: The Edge Disjoint Paths Problem［M］//Dorigo M, Birattari M,Blum C,et al.Ant Colony Optimization and Swarm Intelligence.Berlin,Germany:Springer,2004: 978-982.

［13］ Dorigo M,Maniezzo V,ColorniA.AntSystem: Optimization By a Colony of Cooperating Agents［J］.IEEE Transactions on Systems,Man and Cybernetics, 1996,26(1):29-41.

编辑 陆燕菲

A Multiple Ant Colony Collaborative Planning Algorithm Based on Trajectory Segment

LIU Huijuan,CAI Chao,SUN Xixia
(State Key Laboratory for Multi-spectral Information Processing Technologies, School of Automation,Huazhong University of Science and Technology,Wuhan 430074,China)

To solve the problem that the traditional ant colony algorithm is slow to converge and easy to conflict in the collaborative trajectory planning,considering the features of network graph consist of trajectory segments,a aircraft collaborative trajectory planning algorithm is proposed based on multi-subgroup ant colony coevolution.It divides the ant colony into subgroups with the same number of the aircrafts.Heterogeneous pheromone is introduced to simulate the competition among subgroups,reference length coevolution is adopted to guide the subgroups generating trajectory satisfying the temporal constraints,and the strategy of lost ants pheromone update is added to accelerate the convergence speed.Experimental results demonstrate that this algorithm can generate collaborative flight trajectorys satisfying the constraints of time and space in complex environments for different planning tasks.Compared with the traditional ant colony algorithm,it can generate better collaborative trajectorys,while the planning speed can be improved by 2～3 times.

collaborative trajectory planning;network graph;multi-subgroup;ant colony algorithm;heterogeneous pheromone

10.3969/j.issn.1000-3428.2014.11.029

1000-3428(2014)11-0143-06

A

TJ760

国家部委基金资助项目。

刘慧娟(1989-),女,硕士,主研方向:飞行器路径规划,计算机视觉;蔡 超,副教授、博士;孙希霞,博士研究生。

2013-12-19

2014-01-10E-mail:805577846@qq.com

中文引用格式:刘慧娟,蔡 超,孙希霞.一种基于航迹片段的多蚁群协同规划算法［J］.计算机工程,2014, 40(11):143-148.

英文引用格式:Liu Huijuan,Cai Chao,Sun Xixia.A Multiple Ant Colony Collaborative Planning Algorithm Based on Trajectory Segment［J］.Computer Engineering,2014,40(11):143-148.