基于人工免疫克隆选择算法的无人机三维航迹规划

武 健, 舒健生, 李亚雄, 苏国华, 何艳萍

(1. 火箭军工程大学作战规划教研室, 陕西 西安 710025; 2. 火箭军装备研究院三所, 北京 100094)

0 引 言

无人机(unmanned aerial vehicle,UAV)在军事战略中起着越来越重要的作用,作为任务规划系统的核心之一,航迹规划技术大大提高了UAV的作战效能。如何为UAV规划出一条参考飞行航迹是一项重要而又复杂的工作。

UAV航迹规划属于非确定性多项式(non-deterministic polynomial, NP)问题,国内外学者围绕该问题展开了大量的研究,航迹规划算法大致包括:①动态规划法、A*算法、Voronoi算法等确定型算法[1-5];②模拟退火、神经网络算法、遗传算法、蚁群算法和粒子群优化算法及其改进算法等随机型航迹规划[6-18]。目前的算法研究一般基于一定的假设条件,使得算法在工程应用有一定的局限性。

工程中UAV航迹规划分两步完成:第一,平时进行预处理工作,并储存预处理结果;第二,基于预处理结果,采用人工方法进行航迹规划。工程中的航迹分步规划方法能够借助人较强的跳跃性思维能力快速地处理多要素、多约束、时变性的优化问题,但该方法在规划时间和规划精度上都有很大的改进空间。

本文将工程中的航迹分步规划方法与人工免疫克隆选择(artificial immune clone selection, AICS)算法相结合,提出了基于AICS的航迹自动规划方法。由于UAV的水平航迹和纵向航迹有一定的独立性,在航迹规划中分两步进行:第一,对于给定的可行水平航迹,寻找与其对应的最优纵向航迹;第二,利用AICS寻找一条水平航迹,以确保与其相对应的飞行航迹为最优。本文方法能够充分发挥计算机速度快的特点,进一步提高航迹规划结果的精度,更好地满足UAV控制要求;同时,能进一步降低航迹规划的工作时间,更好地满足实际工作时间要求。

1 水平航迹描述及约束条件分析

1.1 水平航迹控制变量

UAV水平航迹是其飞行航迹在水平面内的投影,水平航迹的运动形式分为水平直飞和水平转弯。在水平转弯半径Rsp给定的情况下,水平航迹由一组有序排列的线段连接而成,航迹可以用各折点的直角坐标(xi,yi)描述,给定折点坐标,则航迹确定,也可以采用极坐标(ri,θi)的形式,取一组有序连接有向线段的各个有向线段的起点、长度和方向所构成的集合。

由于起点(x0,y0)、终点(xn,yn)已知,因此水平航迹控制变量可以取为一组有序连接的n-1个局部极坐标:(ri,θi),i=1,2,…,n。

其中,ri为第i个有向线段的长度;θi为第i个有向线段前进方向相对于第i-1个有向线段前进方向的夹角,定义θi方位角逆时针为正,顺时针为负,取第1个有向线段的前进方向变化量θ1以起点的正东方向为基准。

1.2 水平航迹变化规律

对于直飞段,只要确定出直飞段的起点和终点即可;对于转弯段,除了确定出转弯段的起点和终点,还必须给出起点到终点的转动方向,由两个相邻直飞方向的方向变化θi+1和水平转弯半径Rsp确定,如图1所示。

图1 航迹转弯段示意图Fig.1 Sketch map of route curve section

(1)

(2)

(3)

1.3 飞行环境分析

UAV一般采用组合导航方案,其主要特点表现为惯性导航为主,地形匹配、景象匹配、GPS制导、气压高度修正等为辅。以地形匹配区为例,开展UAV飞行环境分析,航迹约束条件分析及航迹规划研究。

地形匹配系统是利用UAV飞行航迹地面投影点的地形高程起伏特性对其实时定位的一种非连续定位系统。UAV在飞越地形匹配区时,弹上的高度系统(气压高度表、雷达高度表)测量出UAV下方地形剖面的起伏变化,然后与预先存储在计算机存储器中的基准地形匹配区进行相关计算,找出最佳匹配的基准地形剖面,并计算出UAV位置,从而修正由于惯性导航所带来的实际偏差。

地形匹配的时机和地形匹配区面积是根据惯性导航的误差散布及可匹配的地形决定的。原则上,当惯性导航的位置误差积累达到一定值时,应根据地形的具体情况安排一次地形匹配定位,从而及时修正惯性导航的位置误差和速度误差。如果在飞行中,有一段航程内没有合适的地形匹配区,可以再增加航程并根据惯导误差散布的实际情况,安排较大面积的地形匹配搜索区,即UAV飞行一定距离后就需要一个具备一定长度跟宽度的地形匹配区。

1.4 水平航迹约束条件分析

在UAV航迹规划中,除考虑自身技术性能的约束外,还必须充分考虑地形匹配约束,因此影响水平航迹的约束条件主要有:

(1) 水平转弯角度θi的约束:θi≤θmax;

(2) 各水平直飞段航程ri的约束:ri≥rmax;

(3) 水平航迹总航程S的约束:S≤Smax;

2 水平航迹可行时纵向航迹优化模型

2.1 纵向航迹控制变量

UAV纵向航迹是其飞行航迹在纵平面的投影,其控制变量就是一组能够确定纵向航迹的变量,纵向航迹控制变量可以取为各个水平转弯、地形匹配等特定平飞段的飞行高度Hi(i=1,2,…)。

2.2 纵向航迹约束条件分析

2.2.1 水平转弯段的平飞高度取值范围

其中,Hmax为UAV最大升限。

2.2.2 地形匹配段的平飞高度取值范围

在给定地形及UAV爬坡、下滑等相关参数,水平航迹的条件下,可以根据约束快速确定纵向航迹[19]。

3 基于AICS的航迹规划模型

3.1 基于AICS的航迹规划流程

基于上述分析,在给定水平航迹的基础上,可以确定一条满足约束的最优纵向航迹,航迹规划问题转换成了寻找一条水平航迹的过程。

取水平航迹控制变量(ri,θi)为优化变量,其维数是可变的,AICS不涉及交叉问题,比较适合于该问题的求解,同时AICS在收敛速度和多样性保持方面也取得了较好的效果。本文在确定编码方式、克隆操作、免疫基因操作及克隆选择操作的基础上,建立了基于AICS的航迹规划模型。

(1) 编码方式

在本文中,参考航迹优化是取水平航迹控制变量为优化变量的,因此构建抗体为d(可变)维向量[(r1,θ1),(r2,θ2),…,(rd,θd)],采用实数编码的方式。

(2) 群体规模

人工免疫算法中常将群体规模设定为个体编码长度最大值的一个线性倍数,如取为N2和2N2之间的确定数,而N=max(dk)。群体规模按m=int[1.5N2]确定,其中m为群体规模;int[]为取整函数。

初始种群采用随机的方式产生,因为随机选取可保证初始解分布的均匀性。抗体[(r1,θ1),(r2,θ2),…,(rd,θd)]中ri、θi按式(4)产生。

i=1,2,…,d

(4)

式中,(ri_min,ri_max)、(θi_min,θi_max)为UAV水平直飞距离的最小值/最大值边界、水平转弯角度的最小值/最大值边界;rand()为0～1的随机数。

(3) 适应度计算

仿真中适应度取UAV平均飞行高度。

(4) 克隆操作

采用整体克隆的方式,即对任意一个抗体采用相同的克隆比例R。

(5) 免疫基因操作

免疫基因操作主要包括克隆重组操作和克隆变异操作,免疫学认为亲和度成熟和抗体多样性的产生主要是依靠抗体的高频变异,而非交叉或重组,因此采取均匀变异的克隆变异操作,即对抗体[(r1,θ1),(r2,θ2),…,(rd,θd)]的随机位i选择变异,变异后的取值如式(5)所示。

(5)

(6) 克隆选择操作

在实施克隆操作之前,根据抗体适应度进行选择操作。

3.2 仿真计算及结果分析

3.2.1 仿真条件

仿真地形有多种典型生成方法,本文采用经典的中点位移法生成地形[20],具有4个地形匹配区,其顶点坐标如表1所示。

表1 地形匹配区数据

发射点坐标(0,0,0.02),目标点坐标(600,600,0.75),单位为km。

人工免疫算法参数:群体规模m=20,克隆比例R=1.5,变异概率pm=0.4,最大迭代次数Imax=50。

3.2.2 仿真结果

基于上述条件进行仿真,仿真流程如图2所示,仿真结果如图3～图8所示,穿越匹配区结果如表2所示。

图2 航迹规划流程图Fig.2 Flow diagram of route planning

图3 航迹规划结果Fig.3 Result of route planning

图4 三维航迹Fig.4 Three-dimensional route planning

图5 航迹水平投影图Fig.5 Horizontal projection of route

图6 穿越地形匹配区示意图Fig.6 Sketch map of passing the terrain matching area

图7 指标优化曲线Fig.7 Index optimization curve

图8 纵向航迹示意图Fig.8 Sketch map of vertical route

3.2.3 仿真结果分析

从仿真结果中可以看出,在给定相关参数,以高度为优化指标,得到了一条靠近山谷的飞行航迹,符合预期,验证了模型的可靠性。因此,在水平航迹变化规律、状态特征计算、可行性判定及纵向航迹优化的基础上,采用AICS算法可以实现UAV航迹规划。同时,AICS算法表现了较好的收敛性。

4 结 论

本文提出了一种基于AICS的UAV航迹规划方法,克服了传统方法工程化过程中假设条件较多的缺点,优点如下:

(1) 采用了分步规划策略,将复杂的航迹规划问题分解为水平航迹规划规划和纵向航迹规划;

(2) 提出了易于计算机描述的水平航迹控制变量(ri,θi)和纵向航迹控制变量Hi;

(3) 设计了基于AICS的UAV航迹规划方法,仿真结果验证了方法的可行性和有效性,同时该方法能充分发挥计算机容量大、速度快的优点,对传统的人工航迹规划方法进行一定程度上的改进。

[1] PEHLIVANOGLU Y V. A new vibrational genetic algorithm enhanced with a Voronoi diagram for path planning of autonomous UAV[J].Aerospace Science and Technology,2012,16(1):47-55.

[2] CHEN X, CHEN X M. The UAV dynamic path planning algorithm research based on Voronoi diagram[C]∥Proc.of the 26th Chinese Control and Decision Conference, 2014: 1069-1071.

[3] WANG Z, LIU L, LONG T. Enhanced sparseA*search for UAV path planning using Dubins path estimation[C]∥Proc.of the 33rd Chinese Control Conference, 2014:738-742.

[4] JENNINGS A L, ORDONEZ R, CECCARELLI N. Dynamic programming applied to UAV way point path planning in wind[C]∥Proc.of the IEEE International Symposium on Computer-aided Control System Design, 2008: 215-220.

[5] 符小卫, 高晓光. 基于贝叶斯优化的三维飞行航迹规划[J]. 兵工学报, 2007, 28(11): 1340-1346.

FU X W, GAO X G. 3D flight path planning based on Bayesian optimization algorithm[J]. Acta Armamentarii, 2007, 28(11): 1340-1346.

[6] 倪天权, 王建东, 刘以安. 交叉粒群算法在无人机航路规划中的应用[J]. 系统工程与电子技术, 2011, 33(4): 806-810.

NI T Q, WANG J D, LIU Y A. Application of particle swarm algorithm in route planning of UAV[J]. Systems Engineering and Electronics, 2011, 33(4): 806-810.

[7] 苏菲,彭辉,沈林成.基于协进化多子群蚁群算法的多无人作战飞机协同航迹规划研究[J].兵工学报,2009,30(11):1562-1567.

SU F, PENG H, SHEN L C. Research on multi-UCAV cooperative route planning based on coevolutionary multi-ant-colony algorithm[J]. Acta Armamentarii, 2009, 30(11): 1562-1567.

[8] 傅阳光, 周成平, 胡汉平. 无人飞行器海上航迹规划差分进化算法研究[J]. 兵工学报, 2012, 33(3): 295-301.

FU Y G, ZHOU C P, HU H P. Research on differential evolution algorithm for path planning for unmanned aerial vehicle in ocean environment[J]. Acta Armamentarii, 2012, 33(3): 295-301.

[9] AL-SABBAN W H, GONZALEZ L F, SMITH R N. Wind-energy based path planning for electric unmanned aerial vehicles using markov decision processes[C]∥Proc.of the IEEE International Conference on Robotics and Automation, 2013: 784-789.

[10] BAEK S S, KWON H, YODER J A, et al. Optimal path planning of a target following fixed-wing UAV using sequential decision processes[C]∥Proc.of the IEEE/RSJ International Conference on Intelligent Robots and System, 2013: 2955-2962.

[11] DONG Z N, ZHANG R L, CHEN Z J, et al. Study on UAV path planning approach based on fuzzy virtual force[J]. Chinese Journal of Aeronautics, 2010, 23(3): 341-350.

[12] WANG Q, CHANG A, SUN H Y. MPC and SADE for UAV real-time path planning in 3D environment[C]∥Proc.of the IEEE International Conference on Security, 2014: 130-133.

[13] 齐乃明, 孙小雷, 董程, 等. 航迹预测的多无人机任务规划方法[J]. 哈尔滨工业大学学报, 2016, 48(4): 32-35.

QI N M, SUN X L, DONG C, et al. Mission planning based on path prediction for multiple UAVs[J]. Journal of Harbin Institute of Technology, 2016, 48(4): 32-35.

[14] 高颖, 陈旭, 周士军, 等. 基于改进蚁群算法的多批次协同三维航迹规划[J]. 西北工业大学学报, 2016, 34(1): 41-45.

GAO Y, CHEN X, ZHOU S J, et al. Planning based on improved ant colony algorithm multiple batches collaborative three-dimensional track[J]. Journal of Northwestern Polytechnical University, 2016, 34(1): 41-45.

[15] BELLINI A C, LU W, NALDI R, et al. Information driven path planning and control for collaborative aerial robotic sensors using artificial potential functions[C]∥Proc.of the American Control Conference, 2014:590-597.

[16] OZALP N, SAHINGOZ O K. Optimal UAV path planning in a 3D threat environment by using parallel evolutionary algorithms[C]∥Proc.of the IEEE International Conference on Unmanned Aircraft Systems, 2013: 308-317.

[17] FU Y G, DING M Y, ZHOU C P. Routing planning for unmanned aerial vehicle (UAV) on the sea using hybrid differential evolution and quantum-behaved particle swarm optimization[J]. IEEE Trans.on Systems,Man,and Cybernetic: System,2013,43(6):1451-1465.

[18] ZAZA T, RICHARDS A. Ant colony optimization for routing and tasking problems for teams of UAVs[C]∥Proc.of the UKACC International Conference on Control, 2014: 652-655.

[19] 向明思, 刘新学, 郝辉. 相邻特定平飞段之间纵向航迹的快速规划算法研究[J]. 四川兵工学报, 2013, 34(1): 97-100.

XIANG M S, LIU X X, HAO H. Fast planning algorithm of vertical track between adjacent specific level flight segments[J]. Acta Armamentarii of Sichuan, 2013, 34(1): 97-100.

[20] 梁俊,王琪,刘坤良,等.基于随机中点位移法的三维地形模拟[J].计算机仿真,2005,22(1):213-215.

LIANG J, WANG Q, LIU K L, et al. 3D terrain simulation based on the method of random mid-point displacement[J]. Computer Simulation, 2005, 22(1): 213-215.