无人机多目标侦察航迹规划方法

2018-08-17刘志阳

电光与控制 2018年8期

刘志阳，江涛

(1.空军工程大学航空机务士官学校，河南信阳 464000； 2.陆军工程大学石家庄校区，石家庄 050003)

0 引言

无人机航迹规划是任务规划的重要内容，可以有效地提升无人机的作战效能。侦察型无人机执行任务时通常不会针对单一目标，往往是单次任务包含多个目标，这就涉及到任务分配问题中的多目标时序分配问题[1]。

一般任务分配问题可以转化为典型的组合优化问题模型，然后利用与之相关的理论求解。目前典型的任务分配模型有：旅行商问题(TSP)模型[2]、车辆路由问题(VRP)模型[3]、混合整数线性规划(MILP)模型[4]、动态网络流优化(DNFO)模型[5]等。

本文的研究背景选定为侦察型无人机在任务区域对多类型的多个目标进行侦察,因此选择TSP模型。

目前用于无人机航迹规划的寻优方法有很多，本文选择的航迹规划方法为改进智能单粒子优化(ISPO)算法，该算法在笔者前一阶段的研究中已充分论证了其可靠性和优越性。在本文中对航迹初始化方法和航迹编码方式进行了调整和优化，并通过Matlab仿真实验比较了改进ISPO算法、带动态变化惯性权系数的PSO算法及具备反向学习和局部学习能力的粒子群(RLPSO)算法[6]的性能。结果表明，3种算法能有效完成航迹规划的寻优计算，规划结果的质量、稳定性和计算效率由高到低的顺序为改进ISPO算法、RLPSO算法和带动态变化惯性权系数的PSO算法。在后文中提到的PSO算法都是带动态变化惯性权系数的PSO算法。

针对TSP问题，文献[7]提出了一种改进帝国竞争算法(ICA)，该算法在求解TSP问题时有较高的求解质量和效率。本文参考该文献采用改进ICA算法求解，并在帝国增强阶段加入了帝国合并策略，并以与航迹长度和航迹复杂程度有关的函数为目标函数。

针对本文的研究背景，把目标划分为点目标、线目标和面目标，在任务区域中可以把相对比较集中的点目标转化为线目标或者面目标，因此，在有界的区域中目标个数不会很多，所以本文研究的是小规模的TSP问题。通过Matlab分别计算了所有5个、6个和7个目标的航迹，对比ICA算法和离散型萤火虫群优化(DGSO)算法[8]计算的航迹，发现ICA算法能够有效地完成无人机任务区域航迹规划任务并准确找到最优解，其计算结果优于DGSO算法的计算结果。

1 TSP模型

在本文中采用的侦察手段为照相侦察，使用的侦察设备为可见光照相机。研究中，假设目标处在拍摄范围内即可完成侦察，因而将目标分为点目标、线目标和面目标。

点目标的尺寸需小于照相机在地面的拍摄范围。假设照相机的拍摄范围为l0×l0。为保证侦察效果，需要无人机在目标进入拍摄范围到离开拍摄范围期间保持平飞直飞。考虑到无人机机动的需要，假设无人机的最小转弯半径为rmin，因此直飞的距离为2L0。

(1)

图1所示为点目标的侦察模式示意图。

图1 点目标的侦察模式示意图Fig.1 Reconnaissance mode to point target

线目标和面目标的尺寸通常大于照相机的拍摄范围，需要采用广域搜索模式[9]。线目标侦察模式如图2所示，和点目标一样进入前后各增加L0的飞行距离，无人机沿线目标方向飞行。面目标侦察模式如图3所示，面目标可以用一个矩形来表示，同理，进入前后各增加L0的飞行距离。

图2 线目标的侦察模式示意图Fig.2 Reconnaissance mode to linear target

图3 面目标的侦察模式示意图Fig.3 Reconnaissance mode to area target

对有n个目标的TSP问题，本文采取如下的编码方式：每种可能的编码都是从1～n的全排列序列(a1,…,ai,…,an)，其中，ai为[1,n]之间的整数，表示目标的序号，i表示ai在序列中的位置，每一个序列在ICA中表示一个国家。

2 改进ISPO航迹算法

2.1 航迹编码和初始化

在基于改进ISPO算法的航迹规划方法中，没有种群的概念，整个迭代过程只有一个粒子，也就是只对一条航迹进行优化。在传统的TSP问题中，点与点之间的路径通常以连接前后两点的直线表示。但是，这样的路径并不能满足无人机的侦察和机动性能的要求。因此，在目标与下一个目标之间加入一个航迹点，对点目标的侦察可以从任意方向进入，也可以在允许的范围内偏离点目标。改进ISPO算法中的粒子向量为

X=[x1,…,xn,y1,…,yn,θ1,…,θnp,ll1,…,llnp]

式中：[x1,…,xn]为目标与目标之间航迹点的横坐标；[y1,…,yn]为其纵坐标；n为目标个数；[θ1,…,θnp]为点目标的进入方向；[ll1,…,llnp]为偏离点目标的距离；np为点目标个数。

航迹初始化分为航迹点初始化和点目标初始化。航迹点初始化时，航迹点位于连接前一目标和后一目标的航迹的中点；点目标初始化时，采用在允许的范围内取随机值的方法。图4为航迹初始化示意图，图中红色部分为目标。

图4 航迹初始化Fig.4 Route initialization

2.2 航迹代价函数

航迹代价函数所求得的航迹代价是评判航迹优劣的标准，在本文的研究中只考虑时效性和机动性限制。

时效性取决于航迹的长度，侦察每个目标的航迹长度是一定的，所以可不予考虑，只需要考虑目标以外的航迹长度，计算可得

(2)

式中：L表示总的时效性指标；kL为一常数；n为航迹点的个数，与目标点的个数相同；l1i表示第i个航迹点与前一个目标侦察结束点的航迹段长度；l2i表示第i个航迹点与后一个目标侦察开始点的航迹段长度。

在本文中，机动性主要考虑无人机的机动性能约束，在目标前后分别增加一个最小转弯半径的直飞距离，可以保证无人机在侦察完毕后或者开始前进行充分的机动。机动性指标为

(3)

本文所采用的无人机机动性能限制方法为：把半径为无人机最小转弯半径的圆放入前一个拐角的凹侧并与该拐角的两条航迹段相切，计算下一条航迹与该圆相切时的角度θ2imax。因采用arccos(·)函数求夹角，所以不论向量相对前一向量的方向向左或者向右偏，所求得的结果都相同。如图5所示，如果l2i向左偏，θ2i超过θ2imax，那么l1i的长度将满足不了飞行器机动的需求。

图5 无人机机动性能限制Fig.5 UAV maneuverability limit

综上所述，航迹代价函数可由以上两个指标加权求和得到

J(X)=w1L+w2D

(4)

式中：J为航迹代价；X为一条完整的航迹；w1，w2为两个权系数，分别表示其所对应的指标的重要程度，在本文中假设它们同等重要，w1=w2=0.5。

改进ISPO算法这里就不做过多的介绍。通过改进ISPO算法计算最终得到的最优航迹代价可以计算ICA中的每个国家的权力。

社会医疗保险作为社会保障制度的一个子系统，要减少慢性病患者的疾病经济风险，离不开其他贫困资助政策、养老保险、大病保险等社会保障制度的支持。国家卫计委已于2017年再启动实施“三个一批”行动计划(按大病集中救治一批、慢病签约服务管理一批、重病兜底保障一批)，截止到2017年5月已分类救治贫困患者260多万人[22]。当然，对低收入患者的托底政策需进一步制度化。

3 改进ICA

文献[10]于2007年提出了一种社会政治进化算法，并将其命名为帝国竞争算法(ICA)，该算法是对人类帝国的殖民与竞争过程的模拟。

3.1 改进ICA算法流程

1) 建立初始帝国。按照前文中提到的TSP问题的编码方式随机生成Npop个初始国家，并选择权力由大到小排列的前Nimp个国家作为殖民国家，其余Ncol个国家作为殖民地。同时根据殖民国家权力的大小按比例分配殖民地个数，殖民国家和其所属的殖民地国家共同构成了一个帝国。

2) 殖民地同化。根据一定的同化规则，殖民国家对其所属的殖民地国家进行同化，使殖民地国家逐渐趋同于殖民国家。

3) 殖民地革命。以一定的概率对殖民地进行革命操作，革命操作会随机改变原殖民地国家的编码序列，这样可以增强殖民地国家的多样性。在同化和革命完成后，计算帝国内所有国家的权力，选择权力最大的国家作为帝国的殖民国家。

4) 帝国增强。按照一定的规则对每个帝国的殖民国家进行帝国增强操作,这样可以增强殖民国家的多样性，避免算法早熟收敛。

5) 殖民竞争。该步骤是算法收敛的关键。在完成上述步骤以后，每个帝国的结构都有了改变，按照一定的规则计算整个帝国的权力,并以这个权力为标准，把权力最小的帝国中的最小权力殖民地重新分配给权力最大的帝国。如果某个帝国中没有殖民地国家，那么这个帝国将会消失。

改进ICA算法的流程就是不断循环步骤2)～5)，直到满足迭代次数要求或者仅剩一个帝国。算法的详细内容可参考文献[7]，本文不做过多描述。

3.2 算法改进

因此，本文提出了帝国合并的策略。在帝国增强完成后，把殖民国家相同的帝国进行合并，新帝国的殖民国家不变，所有相同殖民国家的殖民地归于新帝国。这样的操作不会影响原来的运算步骤，还大大加强了算法收敛的速率。实验结果表明，算法改进后计算耗时大大缩短,同时，两种算法所得到的最优结果一致。

4 算法实验与分析

本文仿真计算是在Intel(R)Core(TM)i7- 6700 CPU@3.40 GHz,8 GB内存的计算机上进行的，计算机系统为Windows7，仿真计算软件为Matlab R2014b。目标区域设定为以(185 km,185 km)为顶点的15 km×15 km的方形区域。

4.1 改进ISPO算法实验

本实验所涉及的一系列参数：无人机的最小转弯半径rmin=1 km，l0=500 m；PSO算法中，最大惯性权系数ωmax为1.4，最小惯性权系数ωmin为0.8；学习因子c1=c2=2；在RLPSO算法中，反向学习因子c3=0.7，c4=0.3；反向学习代数s0=10；反向学习种群规模m=28；扰动系数初始值d0=40；反向学习条件为种群最优解连续10代没有变化；在改进ISPO算法中，当确定多样性因子时，A为[15，15，0.5]；下降因子p为1.55；收缩因子s为4；加速度因子b为2；kG取0.3；飞行的起点为(185 km,200 km)。

综合考虑航迹计算精度与航迹表示精度，通过大量的实验，设定PSO算法和RLPSO算法的种群数量N为40，目标点数量为5，最大迭代次数为50。改进ISPO算法的航迹迭代次数Nx为15，航迹点迭代次数为10。每种算法进行200次运算。实验数据如表1所示。

表1 3种算法的航迹代价比较

模型1的航迹规划结果如图6所示，航迹代价变化如图7所示。

图6 模型1的航迹规划结果Fig.6 The result of route planning of Model 1

图7 航迹代价变化曲线Fig.7 The curve of route cost

改进ISPO算法、RLPSO算法和PSO算法平均总耗时分别为0.65 s，1.22 s和0.85 s。

4.2 改进ICA算法实验

为了验证改进ICA算法针对本文的研究背景所设定的问题的有效性，设计了5种本文研究背景可能涉及到的TSP模型进行算法验证，分别为5个目标的1种、6个目标和7个目标各2种，同目标个数的不同情况之间目标类型与位置不同。

本文实验所涉及的一系列参数：改进ICA算法初始国家个数与DGSO算法初始种群数量均设置为50，迭代次数均为250。帝国个数约占国家总数的10%～20%时,改进ICA算法的求解质量较为理想，因此帝国个数取15。其余参数的选择均与原文献中算法的参数一致。为了客观比较算法的优劣性，每种情况的每条航迹采用相同的航迹代价，该航迹代价采用改进ISPO算法进行3次重复的计算，取最小值。表2为5种不同的情况2种算法实验结果的对比，每种模型的最优解是通过计算所有可能的情况得到的。