基于粒子群算法的无人机航迹规划问题

摘要:文章首先将无人机航迹问题转换为多目标的TSP问题数学模型,建立了航迹规划问题的数学模型。然后将轨迹规划问题转换成一个求最短路径的单目标的有约束的优化问题,针对这类问题的求解,采用了一种新的粒子群算法并利用软件编程求解。最后验证了结果的可行性,同时讨论了结果的稳定性和收敛性。

关键词:多目标TSP问题;粒子群算法;航迹规划;无人机

中图分类号:TP309文献标识码:A文章编号:1009-2374(2010)04-0011-02

粒子群算法是一种基于生物种群中的个体生物对种群和个体本身的不同依赖程度而设计的智能优化算法,又简称PSO。粒子群算法通过鸟群飞行规律的模拟,并以此为理论基础形成了一种最新的算法。

无人机航迹规划的能力是无人机所必须具有的能力,轨迹规划是无人机自主飞行任务的核心,一般是指在起点,目标点和一些目标节点确定后的轨迹规划问题。

粒子群算法最早是由J•Kennedy和R•Eberhart在1995年提出的,该算法通过对鸟群调整自我飞行速度和方向的研究,将鸟群中的个体抽象为一个多维复杂空间的粒子,粒子在运动过程中不断更新自己的速度和方向,以达到局部和整体的平衡得到最优结果。传统的粒子群的早期运用主要集中在连续函数的优化问题上,粒子群算法还被应用于混合整数非线性优化问题、整数规划问题、带约束函数优化等问题的求解。本文针对无人机航迹规划问题,将问题利用图论知识将多目标的航迹规划问题转换为单目标有约束的TSP问题,同时利用粒子群算法求解得到最佳航迹,并在此问题的基础上进行了结果分析和仿真。

一、无人机轨迹规划问题

(一)无人机轨迹规划问题简介

无人机自主飞行的航迹规划问题有下列要求:

1.能够尽量避开敌方雷达的探测区域和敌方威胁的攻击,同时要避开地形险恶,天气恶劣等不利因素,以保证无人机受到最小的威胁值。

2.当临时出现天气、地形等突况影响正常飞行时能够规划出新的飞行航迹,完成规定的目标任务,即有一定的重规划能力。要求无人机避开雷区且要求威胁值尽量小的基础上找到一条最短路径。

(二)将多目标转化为单目标的轨迹规划模型

已知飞行需要到达的目标点的个数为n,用集合V={v1,v2,…,vn}表示,D=[dij]m×n(i,j=1,2,3,…,n)为两顶点之间的距离矩阵。因此无人机的轨迹规划问题转化为求解一条最优闭合回路的问题,这条闭合回路可以用集合x={va(1),va(2),…,va(n)}表示,即是以为va(1),va(2),…,va(n)顶点的一条路径,这条闭合回路的解集为R={x:{a(1),a(2),…,a(n)｝={1,2,…,n}｝。

如果x={va(1),va(2),…,va(n)}∈R,则令f(x)表示x这条路径的总长度,这样就将问题的重点转换为求解f(x)的最小值。同时以x={va(1),va(2),…,va(n)}∈R表示的一条路径的威胁值尽量小作为约束条件,利用软件编程寻找一条最优路径。

多目标的求解是一个很复杂的过程,上述模型中将威胁值最小这个目标转换为一个约束条件,通过上面的建模将多目标的TSP问题转换为一个单目标问题,经过这样的转换处理后将模型简化,同时为利用粒子群算法对模型求解建立了基础。

二、粒子群算法的定义及其具体形式

(一)粒子群算法的定义

利用粒子群算法求解优化问题是将多个可行解的一个集合定义为一个群,群中的一个可行解看成一个粒子,粒子的个数称为粒子群的规模,每个粒子都有自己的位置和速度,在优化问题的适应度的范围内,追寻粒子的个体最优位置,同时在整个群集合中寻找一个较好解,在每次的迭代过程中粒子并不是随机的任意搜索,而是依据一定的约束条件且与整体最优值不断靠近,粒子通过对自身最优值和全局最优值之间的一个平衡来寻找最优解。

(二)粒子群算法

定义表示第i个粒子的位置为x,V表示第i个粒子的速度,每个粒子自身经历的最好解及个体最优值记作pid,即每个粒子目前搜索到的自己的位置。整个粒子群搜索到的最优值及整体目前的最优值记作pgd,即搜索到的最优解,定义粒子群算法定义如下:

1.粒子通过个体最优和全局最优调整自身速度的表达式

Vid(t+1)=wVid(t)+c1(pid(t)xid(t))rand()+c2(pgd(t)xid(t))rand()

2.粒子位置的更新公式

xid(t+1)=xid(t)+Vid(t+1)

在上述表达式中w是惯性系数防止粒子过早的停止搜索。c1、c2是加速系数又称为学习因子,调节个体最优值和全局最优值对粒子运动影响的大小c1和c2的和等于1,rand()为随机生成数的函数。

(三)利用粒子群算法的TSP问题链表表示

在无人机自主飞行航迹规划的一类TSP问题的求解过程中首先要有一个储存路径的数组,但利用数组存储时的空间冗余度过高且编码和替换过程复杂,本文利用已有的链表法储存路径,其具体表述如下:

X={x1,x2,…,xi,…,xn},1≤i≤n,1≤xi≤n

上述式子中的n表示目标任务点个数,对于第i维数据xi表示一条边(i,xi),即在访问城市i后访问城市后访问后继续访问城市xi,整个访问序列构成一个循环单链表。

(四)无人机航迹规划问题利用粒子群算法的求解步骤

1.对粒子群进行初始化,即产生n个粒子的位置和速度。

2.计算每个粒子的适应度值。

3.比较每个粒子i的适应度值和它所经历过的最好位置pid的适应度值,如果更好,更新pid。

4.比较每个粒子的适应度值和群体的全局最好位置pgd的适应度值,如果更好,更新pgd。

5.如果达到结束条件(足够好的位置或最大迭代次数)则结束程序;否则转到步骤2)。

三、实验结果和分析

利用参考文献的数据,其20个目标任务点的TSP坐标,见表1:

利用粒子群算法思想计算20个目标点的无人机航迹规划仿真结果如下:

利用PSO计算出的最优路程之和为23.1240,其路径为:

1516561484312121320111071819915

通过粒子群算法找到了这条最优路径,这条路径的路程相对于其它算法很短。同时计算结果收敛性很好,到最后基本达到平衡且稳定性很好。说明粒子群算法对无人机航迹规划问题一类的多目标问题的求解是可行的。

四、结语

本文针对无人机自主飞行的航迹规划问题建立了一个多目标的TSP模型,虽然目前的一些算法能够很好地解决航迹规划问题,但不是最优结果,针对这个问题本文提出了一种新的算法,即粒子群算法。通过利用粒子群算法进行求解,得到的一个相对更优的结果,同时本算法的思想还可以推广到更多的求解最优路径的TSP问题的求解中。

参考文献

[1]钟一文,杨建刚,宁正元.求解TSP问题的离散粒子群优化算法[J].系统工程理论与实践,2006,(6).

[2]赵文婷,彭俊毅.基于VORONOI图的无人机轨迹规划[J].系统仿真学报,2006,18(2).

[3]Keedny J,Eberhart R C.Particle swarm optimization[A].Proceedings of the IEEE International Conference on Neural Networks[C].Perth,Australia:IEEE Press,1995.

[4]李智勇,王永,孙星明.一种进化粒子群算法及其在TSP问题中的应用[J].计算机工程与应用,2008,44(28).

[5]孙亮,胡晓磊,于雷.基于遗传算法的航迹规划的TSP问题研究[J].导弹与制造学报,2005,(2).

基金项目:四川省教育厅青年项目(项目编号:07ZB043)。

作者简介:彭文敏(1987-),女,四川万源人,内江师范学院数学与信息科学学院2007级学生,研究方向:粒子群优化算法;胡书(1990-),女,四川达州人,内江师范学院数学与信息科学学院2007级学生;张莉(1988-),女,四川南充人,内江师范学院数学与信息科学学院2007级学生;谭周田(1987-),男,四川达州人,安徽理工大学理学院2007级学生。