多无人机编队自主重构的内点算法

王建宏, 朱永红, 许 莺, 熊朝华

(1.景德镇陶瓷学院机电系, 江西 景德镇 333403;2.中国电子科技集团公司第二十八研究所,南京 210007)

多无人机编队自主重构的内点算法

王建宏1, 朱永红1, 许 莺2, 熊朝华2

(1.景德镇陶瓷学院机电系, 江西 景德镇 333403;2.中国电子科技集团公司第二十八研究所,南京 210007)

多无人机编队； 自主重构； 内点算法； 多目标优化

0 引言

多无人机编队控制是无人机执行任务的基础和前提，其目的是根据各无人机的具体任务为每架无人机规划出从初始点到目标点的可行飞行航迹，协调处理各架无人机航迹之间的相互关系，使其在指定的性能指标下达到最优或次优，以适应平台性能、战场环境、战术任务等要求。当编队任务或者战场环境发生变化时，整个多无人机编队需要进行调整即重构。在调整重构过程中，需要重新调节每架无人机在新编队几何构型中的位置，并规划出从原初始位置到新终端位置的航迹。由此所规划的航迹必须确保每架无人机的安全性，同时考虑无人机的非线性动力学特性，各种编队重构的无人机代价函数，以及各类约束条件。多无人机编队自主重构的过程可设计成一个数学优化问题，其中的优化决策变量是每架无人机的控制输入序列；代价函数包括侦察无人机代价函数、导弹干扰无人机代价函数、雷达干扰无人机代价函数；系统的约束条件包括雷达威胁约束、导弹威胁约束、高炮阵地威胁约束、编队防碰撞约束。

现有的研究重心集中在多无人机编队控制轨迹规划，文献[1]概要地介绍多无人机编队控制轨迹设计在多基地多无人机协同侦察过程中的辅助作用；文献[2]在多无人机编队建模中引入一种智能化多Agent系统的通信结构；文献[3]介绍无人机路径规划的各种方法，如蚁群算法、遗传算法、粒子群算法、单元分解法、人工势能场法、路标图法和概率图法等；文献[4]从灰色系统理论来调整智能算法中的权重值；文献[5]从信息融合的角度分析怎样对多无人机上的多个传感信息进行融合得到状态融合估计值；文献[6]将粒子滤波算法应用于非高斯条件下的路径跟踪；文献[7]提出一种改进的交互式多模型粒子滤波算法，并将此新算法应用于无人机的目标跟踪；文献[8]考虑多目标优化的蚁群算法；文献[9]利用一致设计的遗传算法来求解多目标优化问题；对于多无人机编队自主重构问题，文献[10]运用多目标多人博弈理论将原最优化问题转化为纳什谈判过程；文献[11]考虑通信延迟的存在，设计了基于信息滤波算法的信息补偿。

本文将内点算法应用于多无人机编队自主重构的轨迹优化。在文献[10]所建立的多无人机编队自主重构的优化模型中，建立3类不同的代价函数，将各架无人机的动力学方程作为等式约束，联合雷达威胁、导弹威胁、高炮阵地威胁和编队防碰撞作为4类不等式约束，构成一个带有等式和不等式约束条件的多目标优化问题。对此,复杂的多目标优化问题求解可得到航迹规划过程中所需要的控制输入向量。整篇思路在于如何从经典的运筹学优化理论角度分析多目标优化问题的求解。对于此多目标优化问题，利用加权和策略将多目标优化转化为单一的目标优化，从理论上证明加权和策略的可行性。为将原始的最优化问题改写成标准的非线性优化形式，可将各架无人机的动力学等式方程作拓展，采用某些形式来描述状态变量集和控制输入集。对于改进的标准非线性优化形式，详细给出改进内点算法的求解过程。

1 多无人机编队自主重构的建模

多无人机编队自主重构指的是在初始考虑时刻，多无人机以一种编队模式飞行。当编队执行任务或周围的战场环境发生改变时，此时无人机群能够自主地改变之前正在飞行的编队模式，而应重新选择新的编队模式[12]。在两种编队模式重构过程中，每架无人机在新编队模式中的位置需要重新规划设计，从而生成一条新的飞行轨迹。此新飞行轨迹的设计需要考虑各架无人机的动力学特性、飞行代价函数及约束条件等。多无人机编队在执行任务中的自主重构过程如图1所示。

设有n架无人机在编队中飞行，且整个自主重构过程完成时所需的时间长度为N。记第i架无人机在整个编队自主重构任务过程中的状态向量为xi=(xi(1)xi(2)…xi(N))T，对应的控制输入向量为

图1 多无人机编队自主重构过程Fig.1 Multi-UAV formation autono-mous reconfiguration process

第i架无人机的时不变离散状态方程为

xi(k+1)=fi(xi(k),ui(k))

xi∈Ξi,ui(k)∈Θi

(1)

式中:fi为一个非线性映射，其联合k时刻的状态向量xi(k)和控制向量ui(k)映射到k+1时刻的状态变量;Ξi和Θi是第i架无人机的可行状态集和控制输入约束集。当无人机编队飞跃战场环境时，设k时刻领航的虚拟长机位置为pl(k)=(xl(k)yl(k))T。第i架执行侦察任务的无人机vi的位置为:pi(k)=(xi(k)yi(k))T。

在执行任务过程中侦察无人机vi的代价函数为

(2)

(3)

(4)

式中：代价函数F2i(xi,ui)是以导弹干扰第i架无人机的当前位置pi与其理想位置pa1间的距离差构造的，pa1为理想的导弹干扰位置。而式(4)中的代价函数F3i(xi,ui)是在为实现对编队飞行通道最大保护下，以雷达干扰无人机当前位置pi与其理想位置pa2间的距离差构造的。

在共有n架无人机位于多无人机编队的几何构型中，联合式(2)～式(4)可得需考虑的代价函数为

(5)

式(5)的代价函数矢量中共有3n项元素需要取最小化运算，要能保证同时使所有的3n项元素都最小化的最小解u是不存在的，只能在其中寻找一个折中解，此解即为多目标优化理论中的有效解[14]。

‖pi(k)-prj(k)‖2≤0 。

(6)

设导弹mj的位置为pmj=(xmjymj)T，导弹mj受干扰后的安全距离和安全角度余弦分别为dmj和csmj(k)，则无人机vi的导弹威胁约束为

(7)

设高炮阵地的辐射半径不受干扰影响，设定其为常值，阵地nj的位置和辐射半径分别为pnj=(xnjynj)T和Rnj(k)，则无人机vi的高炮阵地威胁约束为

(8)

设编队无人机间的最小安全距离为dmin，则无人机vi的编队防碰撞威胁约束为

‖pi(k)-pj(k)‖2≤0 。

(9)

联合以上关于无人机的多目标代价函数式(5)、无人机的非线性动力学方程式(1)、4类不等式约束式(6)～式(9)，可得到多无人机编队自主重构的建模为一个非线性的多目标优化问题

(10)

s.t.xi(k+1)=fi(xi(k),ui(k))

xi∈Ξi,ui(k)∈Θii=1,2,…,n,

k=1,2,…,N

将式(10)中所有的不等式合并成矢量形式为

(11)

其中的状态变量和控制输入矢量为

(12)

类似有无人机的非线性动力学方程也可合并为

f(x(k),u(k)) 。

(13)

利用式(11)～ 式(13)的矢量化，式(10)所示的非线性多目标优化问题可简化为

(14)

s.t.x(k+1)=f(x(k),u(k))

xi∈Ξi,ui(k)∈Θii=1,2,…,n,

g(x,u)≤0 。

对式(14)利用内点算法之前，需将其中的多目标最小转化为单目标优化，将其转化为标准的带等式和不等式约束的非线性优化问题。

2 模型的规范化

对于式(14)中的多目标代价函数矢量

(15)

可采用加权和策略来将其改写为单目标优化问题

(16)

λ1i>0,λ2i>0,λ3i>0 。

(17)

对于最小化问题式(15)与式(16)之间的等价性分析可知在式(17)成立的正加权值条件下，若式(16)所示的单目标优化问题存在一个最优解，该最优解必为式(15)多目标优化问题的一个有效解。

对于式(14)中的无人机非线性动力学方程可改为

5.问题诱导。一篇文章要提的问题可能很多，但符合语文学科特征的、重点的问题，可能只有几个，对这些问题，多问几个为什么，可以增强学生对周围实际现象的兴趣，发展他们看出多种事物和现象之间的相互关系的能力，获取知识和技能。如教学《落花生》一课的重点段，可提问：花生的可贵之处是什么？父亲这样赞美花生，实际上是在表达一种希望，他希望什么？你认为做人要做怎样的人？一连串的问题，把学生思维引向深入，把对课文的理解引向深入。

k=1,2,…,N-1 。

(18)

式(18)中的第一个等式表示初始状态，其在优化设计过程中可根据实验测取。对于可行状态集Ξi和控制输入约束集Θi可定义如下对应的约束

(19)

(20)

s.t.G(u)=

对于式(16)所示的标准非线性优化问题可采用运筹学中的内点算法来继续求解。

3 内点算法

内点算法的目的是生成一组迭代序列uj，此时上标uj是为了和k时刻的控制输入值u(k)相区别。该组序列将紧紧地位于控制输入集合内。在每次生成序列的迭代过程中，将使用到不等式约束H(u)的每一个元素分量，利用松弛变量s可将这些不等式约束转化为等式约束。将式(20)改写为

(21)

s.t.G(u)=0,H(u)+s=0,s≥0

式(21)中的松弛变量s应该为一个选择适当维数的矢量，其每一元素都应非负。此时式(21)对应的拉格朗日函数构造为

L(u,s,v,w)=F(u)-vTG(u)-
wT(H(u)+s)。

(22)

根据最优性必要条件可知，在最小值处等式H(u)+s=0必成立，对式(21)应用广义KKT最优充要条件可得

(23)

为增强式(23)的最优条件，采用内点算法求解式(21)，对式(21)引进障碍函数以消除非负条件s≥0得

(24)

s.t.G(u)=0,H(u)+s=0

(25)

对式(25)应用牛顿增量步骤可得系统方程为

(26)

当计算出增量(ΔuΔsΔvΔw)后，新的递推迭代值可计算如下

(27)

(28)

式中,τ∈(0,1)，常取τ=0.995。为保证式(26)的第2个块矩阵具有满行秩，以使得内点算法并非病态，不会表现出奇异性现象，可将式(26)修改为

(29)

(30)

即在式(30)的第1个矩阵中增加规范参数γ>0。因迭代式(27)在有限时间段内不会终止，故可施加一个误差准则函数来判断是否需要终止整个迭代循环算法。

E(u,s,v,w)=max{‖▽F(u)-

▽GT(u)v-▽HT(u)w‖,‖Sw-

μe‖,‖G(u)‖,‖H(u)+s‖}。

(31)

利用此误差准则函数作为判断终止迭代算法，可得改进内点算法的基本步骤为：

1) 假设给定初始值(u0,s0)，令j=0；

2) 计算拉格朗日乘子v0和w0，定义参数μ0>0,σ,τ∈(0,1);

3) 检验误差准则函数是否成立:E(uj,sj,vj,wj)≥ε,ε为一个非常小的正数；若不成立则算法可终止，此时的迭代优化变量(uj,sj,vj,wj)即可作为非线性优化变量的最优解；

6) 利用迭代式(27)求解新的迭代值；

7) 令μj+1=μj,k=k+1；

8) 转回步骤3)。

改进的内点算法应用于多无人机编队自主重构，弥补传统内点算法的秩亏损，保证能够得到原非线性优化问题的最优解。

对于迭代式(27)的收敛性和一致性，理论式的推导是严格利用优化过程的最优性KKT充要条件，而工程实用采用的是迭代求解形式。根据最优性充要条件可得关于未知权值在理论上的收敛性。

定理1若u*是式(21)非线性规划问题满足式(23)最优性充要条件的一个解，此时该解对应的拉格朗日乘子分别为v和w，式(26)左边的矩阵是正半定的，则u*必是非线性规划问题的最优解。该定理是关于改进内点算法的一致性和收敛性，其证明过程见文献[12]。

4 两优化问题间的等价性

在求解多目标优化问题时，第3章利用加权和策略将其转化为单目标优化问题，以说明当正加权标量值满足式(17)条件下，两优化问题间存在等价性。因式(15)中共有3n项元素，将式(15)改写为

(32)

类似式(16)可改写为

(33)

式(32)与式(33)虽然在形式上与式(15)、式(16)不同，但实质上是相同的。只需将式(15)中的3n项元素按照顺序全列举出来，再从头开始排序，并用式(32)中的符号重新表示，则式(32)与式(33)间等价性的条件归纳为如下命题。

(34)

(35)

(36)

(37)

(38)

5 仿真算例

考虑编队由3架无人机组成，包括1架雷达干扰无人机、1架导弹干扰无人机以及一架侦察无人机。3架无人机的初始位置都位于起点坐标(0 m,0 m)处，要执行飞行任务的终点位置为(700 m,700 m)，且各自的飞行最大速度、最小速度和速度偏差构成矢量(80 m/s15 m/s±5 m/s)，周围的战场环境中包含有雷达威胁、导弹威胁和高炮阵地威胁，其中，雷达威胁的部署坐标为(300 m,300 m)，导弹威胁的部署坐标为(250 m,200 m)，高炮阵地威胁的区域位于高度为300 m，宽度为300 m的矩形范围之内，此范围对无人机属于禁飞区。

利用内点算法作用于多无人机编队自主重构优化模型，各无人机的加权系数Qi=diag(10,10)，代价函数中的加权矩阵Ri=diag(1,10)。离散采样周期取ΔT=0.05s，时间段长度N=500 s，无人机架次为3，算法的初始估计值选择为(u0,s0)=(0.01 0.01 0.01 0.01)T,摄动参数μ0=0.05，正数ε=0.01，规范参数γ=0.5，标量值δ=1.5。利用内点算法来设计编队自主重构的仿真轨迹见图2所示。战场环境中威胁的坐标为(296 m,746 m)和(229 m,173 m)，作用半径为100 m。设威胁区域内的威胁为无穷大。由于在威胁附近区域规划路径时路径的变化较为复杂,为了增加路径的可飞性，在威胁附近采样航点的密度可以比没有威胁的区域高。图2为多无人机编队自主重构轨迹。该3架无人机所组成的编队共经历了2次编队的自主重构过程，第1次重构发生在位置(200 m,100 m)处，第2次重构发生在位置(280 m,280 m)处。在经过这2次编队的重构后，该3架无人机恰好能绕开这些威胁从初始位置飞行到终点位置。

图2 多无人机编队自主重构轨迹Fig.2 Multi-UAV formation auto-nomous reconfiguration trajectory

图3给出3架无人机各自代价函数的迭代收敛曲线图。

图3 各架无人机代价函数的收敛曲线Fig.3 Convergence curves of each UAV cost function

此时各自的代价函数是采用式(16)的形式，其中所有正加权标量值λ=1/9，由图3中的各个图形可见，随着内点算法的循环迭代运行，将最终计算出来的最优控制输入解u代入对应的加权和代价函数中，可使得代价函数随着迭代次数的增加而逐渐趋于接近0的小数。

6 结语

建立多无人机编队自主重构的非线性多目标优化模型，利用加权和策略及其合并某些等式和不等式，将非线性多目标优化问题转化为标准的单目标非线性优化问题。进而采用内点算法来求解，并在内点算法的实现上提出若干改进措施，以保证得到原非线性优化问题的最优解。

[1] KARIMODDINI A.Hybrid three dimensional formation control for unmanned helicopters[J].Automatica,2013,49(2):424-433.

[2] INNOCENTI M.Management of communication failures in formation control with communication relays[J].Journal of Aerospace Computing Information and Communication,2004, 11(1):19-35.

[3] REZAEC H.Motion synchonization in unmanned aircrafts formation control with communication relays[J].Commun Nonlinear Science Number Simulate,2013,38(18):744-756.

[4] TRIPLET B I.Cooperative estimation for coordinate target tracking in a clustered environment[J].Mobile Networkand Application,2009,14(3): 336-349.

[5] LI S Y.Nash-optimization enhanced distributed model predictive control applied to the shell benchmark pro- blem[J].Information Sciences,2005, 17(2):329-349.

[6] SCHOERLING D.Experimental test of a robust formation controller for marine unmanned surface vessels[J].Autonomous Robots,2010,28(2):213-230.

[7] SUN H B.Distributed cooperation target tracking for heterogeneous multi-UAV under communication and measurement constrains[J].Acta Aeronautica et Astronautica Sinica,2011,32(2):299-310.

[8] ZHANG X Q.Research on improved leader following formation method[J].Computer Engineering and De-

sign,2010,31(11):2547-2549.

[9] GUILIETTI F.Autonomous formation flight[J].IEEE Controls System Magazine,2000,20(6):34-44.

[10] GIANLUIGI P,FRANCESCO D, CHEN T S,et al.Kernal methods in system identification,machine learnning and function estimation:a survey[J].Automatica,2014, 50(3):657-682.

[11] MELANIE N Z,DAVIDE M R, ALEXANDER D,et al.On real time robust model predictive control[J].Automatica,2014,50(3):683-694.

[12] 王建宏.基于先进辨识的控制策略研究及其应用[D].南京:南京航空航天大学,2011.

[13] YOSI B A.Distributed decision and control for cooperative UAVs using ad hoc communication[J].IEEE Transaction on Control Systems Technology,2008,16(3):511-516.

[14] CHEN W H.Nonlinear disturbance observer enhanced dynamic inversion control of missiles[J].Guidance Control and Dynamics,2003, 26(1):161-166.

[15] FABRIZIO G.Dynamics and control of different aircraft formation structures[J].Aeronautical,2004,108(10):117-124.

[16] FABRIZIO G.Dynamics and control issures of formation flight[J].Aerospace Science and Technology, 2005,36(9):65-71.

InteriorPointAlgorithminMulti-UAVFormationAutonomousReconfiguration

The problem of how to design the multi-UAV formation autonomous reconfiguration is studied. Based on three kinds of cost functions,the nonlinear dynamic equations of UAVs and four inequality constrain conditions,a nonlinear multi-objective optimization model is constructed. After applying weighted sum method and separating all equality constraints from inequality constraints,the former nonlinear multi-objective optimization model is converted into a standard nonlinear single-objective optimization model. Then the interior point algorithm from operations research is used to solve the optimization problem. To avoid rank deficiency,some improvements are made in realizing the interior point algorithm. The equivalence property between multi-objective optimization through weighted sum method and single-objective optimization is proved. Finally,the efficiency of the proposed strategy is confirmed by the simulation results.

multi-UAV formation; autonomous reconfiguration; interior point algorithm; multi-objective optimization

王建宏

王建宏(1980-)，男，江西吉安人，景德镇陶瓷学院机械电子工程学院教授，原中国电子科技集团公司第二十八研究所研究员。2011年毕业于南京航空航天大学,获博士学位，2013年中国电子科技集团第二十八研究所博士后，2014年赴瑞士苏黎世理工大学信息技术与电子工程学院自动控制系作访问教授，2015年赴意大利米兰理工大学电气与信息工程学院自动控制系作访问教授。主要研究方向为系统辨识、预测控制、数据驱动控制、多无人机编队协同指挥控制和稳定跟踪转台高精度伺服控制。主持和参与了多无人机编队协同目标跟踪模拟设计、舰载无人直升机起降控制系统设计、精密伺服跟踪转台的控制及仿真，且多为国防预研和重点基金、国家自然科学基金、航空基金项目。发表论文80篇，其中50余篇被三大检索收录，出版专著2部。

考虑多无人机编队自主重构的优化设计问题，联合编队过程中的3类代价函数、无人机的非线性动力学方程以及4类不等式约束条件，构成一个非线性多目标优化模型。采用加权和策略并将所有的等式和不等式约束分别组合，将非线性多目标优化模型转化为一个标准的非线性单目标优化模型。采用运筹学中的内点算法来求解最优解，并在算法的实现过程中做了某些改进，以避免出现矩阵的秩亏损。从理论上证明多目标优化在加权和策略下与单目标优化间的等价性。最后用仿真算例验证了算法的有效性。

TP273

1671-637X(2017)03-0001-06

国家自然科学基金(61563022);江西省重大科技项目(20152ACB20009)