2. 西北工业大学 航空学院, 陕西 西安 710072
小型无人驾驶飞行器(unmanned aerial vehicle,UAV)凭借其自身成本低、重量轻、体积小、操作灵活等诸多优点,在军事以及民用领域有着越来越广泛的运用。然而,由于单个小型无人机的能力有限,使其难以满足日益复杂的应用要求,因此,多小型无人机通常采用协同编队飞行的方式完成所设计的任务,例如灾后进行区域内的协同搜索[1],森林的火灾巡逻、预警[2]等。在多无人机系统中,为减轻地面站的负担,降低操作成本,增加系统的灵活性、可靠性、可扩展性以及鲁棒性,通常将无人机设计为协同合作的智能体自主地完成机上的各种操作,而无须时刻接收地面站发送的指令。在众多自主操作中,编队飞行的协同轨迹规划是多无人机系统完成设计任务的前提[3]。
目前文献中的研究主要是针对单个UAV的航迹规划[4]、多个UAV的集中式编队飞行航迹规划[3]以及多个UAV的混合式编队飞行航迹规划[2]。其中,集中式编队飞行规划是指编队中的某一UAV先接收系统中所有UAV的信息,然后运行规划算法,最后将生成的结果发送给其他UAV;而分布式协同规划需要系统中所有UAV都承担部分规划计算任务,且计算过程中只需要其邻居UAV的相关信息;混合式协同编队规划则介于集中式与分布式规划之间。综上所述,集中式编队飞行规划对UAV间的通信拓扑结构有严格的要求(需要多点对单点的通信结构),存在着单点脆弱性、扩展性差的缺点,不适于数目较多的多UAV系统(因为规划问题的复杂度随着UAV个数的增多而显著增加,计算量也因此加大)。虽然混合式编队规划算法部分弥补了集中式算法的不足,但它依然要求多点对单点的通信结构,且存在单点脆弱性。
对于小型UAV,其通信能力会受到平台大小的制约,因此需要开发仅需要相邻UAV信息的分布式算法。本文基于对偶分解原理,提出了一种新的分布式算法以实现多智能体编队飞行的协同航迹规划,给出了规划的优化模型,进行了对偶分解的详细推导,分析了所设计方法的最优性和收敛性,并完成了以5个智能体进行V字形协同编队飞行的仿真验证。
1 多智能体协同编队飞行的优化模型在本文的研究中,假设协同编队飞行中的每个智能体都受到线性动力学的约束;在航迹规划中,它们既要完成各自任务也要完成系统的全局任务。在本文提出的协同编队飞行的优化模型中,首先将线性动力学约束转化为关于决策变量的线性等式约束,然后使用目标函数描述智能体的独立任务以及系统的全局任务。
1.1 线性动力学约束假设协同编队飞行中有n个智能体,且每个智能体的动力学模型表示为:
(3)式建立了智能体i各个时刻的状态变量与其控制变量之间的线性关系。在协同编队飞行中,通常希望智能体在某时刻能够实现特定的状态目标;借助于(3)式,该状态目标即可转化为关于Ui的表达式。
1.2 智能体的独立目标为方便起见,记ziT=XiTUiT 。在协同编队飞行中,每个智能体需要完成的各自独立目标可由关于zi的线性方程Pizi=bi描述[6]。例如,当Pi=0I(I为对应维数的单位矩阵)且bi=0时,每个智能体需要完成的各自独立目标为燃料消耗最小,即Ui=0;当Pi=I0且bi=xid时,每个智能体需要完成的各自独立目标变为跟踪参考轨迹,即CXi=xid(C为对应维数的矩阵,用以提取Xi中的位置状态,xid为参考轨迹向量)。这些独立目标的完成情况可由以下的偏差衡量:
在本文的研究中,协同编队飞行系统的全局目标主要包括所有智能体的燃料消耗总和最小以及相邻智能体位置之间保持特定的队形。燃料消耗总和最小可以表示为:
结合(3)式~(6)式,受线性动力学约束的协同编队飞行可以建模为以下的优化问题:
在优化问题(7)中,目标函数包括智能体各自独立的目标以及系统的全局目标,约束则由智能体的线性动力学约束构成。由于目标函数是二次型多项式且约束为线性等式约束,因此优化问题(7)是一个凸优化问题[7]。
2 对偶分解运用对偶分解分布式地求解优化问题(7)就是要将原来包含所有智能体变量的大型、非线性问题分解成一系列较小的问题进行求解;且每个小问题只与一个独立智能体相关,并只包含这个智能体的变量。因此,原问题便可以被分配到每个智能体上求解,这就构成了分布式算法。然而,优化问题(7)的目标函数不具备可分解的形式,首先需要对其进行解耦操作。
2.1 解耦目标函数优化问题(7)的目标函数中,第1个求和符号里的求和项是解耦的,但第2个求和符号中的Xi会出现在不同的非线性求和项中,因此求和项之间是耦合的,需要进行解耦操作。解耦的目的即建立一个与问题(7)等价的新问题,且在求和符号中的不同非线性求和项中不存在相同的优化变量,从而便于进行对偶分解。为此,为每个智能体引入松弛变量i,将问题(7)转化为:
为设计分布式算法,需要将优化问题(8)分解为一系列可由智能体独立求解的小问题。然而,优化问题(8)的原始形式不便于分解。但由于优化问题(8)是凸优化问题,具备强对偶性,因此它的解可以通过求解其对偶问题获得。经过下面的推导,可以看出优化问题(8)的对偶问题具备可分解的形式。然而,为求得优化问题(8)的对偶问题,首先要推导出它的拉格朗日函数,接着再求出它的对偶函数。
优化问题(8)的部分拉格朗日函数为:
当智能体的独立目标为跟踪参考轨迹,而系统的全局目标包含总燃料消耗最小时,可以根据L1i的最小值推导出最优控制和最优轨迹的表达式。将(3)式代入L1i得到:
由(14)式可以求得最优控制Ui*为
将Ui*代入(3)式则得到使L1i最小的最优轨迹:
L2i关于i以及Xij的最小值推导如下。首先,L2i相对于i以及Xij的偏导数应满足:
将(24)式和(25)式代入(10)式,优化问题(8)式的对偶函数变为一个关于编队飞行队形品质的函数:
至此,优化问题(8)式的对偶问题可描述为:
在本文的研究中,运用次梯度方法求解对偶问题(7)[8]。由于次梯度方法只适用于求解函数的最小值,故将对偶问题(7)转化为求解-g(ξ)的最小值。函数-g(ξ)相对于ξij的一个次梯度可表示为:
一般情况下,迭代步长αk有5种选取准则[8]。①定步长,即αk=α,α为正常数。②定间隔,即每次迭代中ξij前后差值的模为常数。例如,αk=γ/‖s(k)‖2,式中γ为正常数。③步长平方可加但步长不可加,例如αk=a/(b+k),式中a为正数,b为非负数。④步长不可加而步长递减,例如αk=a/k,式中a为正数。⑤间隔不可加而间隔递减,例如αk=a/(k·‖s(k)‖2)。前2种步长选取准则只能保证次梯度算法收敛到最优值的某个邻域,而后3种准则能确保次梯度算法收敛于最优值。
3 分布式协同算法 3.1 算法的描述在上一节推导的基础上,可以设计出适用于多智能体协同编队飞行的分布式算法。该算法总结如下。
算法的输入为:Aic、Bic、xi(0)、xid、δij、Ni和ξij(0),i=1,2,…,n,j∈Ni。在算法进行迭代之前,每个智能体先根据(2)式和(3)式计算出Gi和Hi,然后进行以下的迭代直至满足预设的精度。
1) 智能体i向它的邻居j,j∈Ni,发送它当前的编队飞行品质ξij(k),并接收由智能体j发送的ξji(k);
2) 智能体i根据(3)式计算νij(k)和νji(k),并根据(20)式计算μi(k);
3) 智能体i根据(15)式计算当前的最优控制Ui* (k),再根据(16)式计算当前的最优轨迹Xi* (k);
4) 智能体i向它的邻居j,j∈Ni,发送它当前的最优轨迹Xi* (k),并接收由智能体j发送的Xj* (k);
5) 智能体i根据(9)式计算ξji(k+1)以更新编队飞行品质。
当编队飞行品质ξij收敛时,以上的迭代过程结束。算法的输出为Ui* 和Xi*。
以上的分布式算法可以有如下直观的解释。首先,每个智能体先忽略系统的全局目标,只基于各自的局部目标计算最优轨迹。接着,每个智能体将自己的最优轨迹信息发送给那些与它在全局目标中相关联的智能体;与此同时,也接收来自于这些智能体的最优轨迹信息。在交换轨迹信息之后,每个智能体开始计算它与全局目标的偏离量,再基于偏移量计算出新的最优轨迹。重复以上过程直至与全局目标的偏离量收敛。
在本文设计的分布式算法中,一共存在两次信息交互的过程。第一次是交互编队飞行品质信息;第二次是交互最优轨迹信息。两次信息的交互都只发生在相邻的智能体之间,因此对系统的通信拓扑结构没有苛刻的要求。
3.2 算法的最优性本文提出的分布式算法采用次梯度方法求解优化问题(8)的对偶问题(27)。由于优化问题(8)是一个凸优化问题,对于有可行解的协同编队飞行问题(意味着满足Slater条件),根据凸优化理论,优化问题(8)具有强对偶性[7]。因此,由对偶问题(27)的最优解能得到优化问题(8)的最优解;又由于最优问题(8)和问题(7)等价,故分布式算法能给出协同编队飞行问题的最优解。
3.3 算法的收敛性[8]分布式算法的收敛性取决于运用次梯度方法求解对偶问题(27)的收敛性。令f(ξ)=-g(ξ),则要说明次梯度方法的收敛性就是要比较迭代值f(ξk)(ξk为第k次迭代时向量ξ的值)与最优值f(ξ*)(ξ*为f(ξ)取得最优值时向量ξ的值)之间的关系。首先,根据迭代公式,有以下关系式成立:
根据次梯度的定义有[8]:
将不等(32)式代入(31)式中,得到:
重复运用不等关系式(33),得到:
令‖ξ0-ξ*‖2≤R,即初始值ξ0选取在ξ的有界值域内,则有:
令fbest是迭代过程中使得f(ξi)-f(ξ*),i=0,1,…,k,最小的函数值,则:
由(26)式可以看出:f(ξ)是一个关于ξ的二次函数,因此满足Lipschitz条件,即
如果迭代步长的选取准则为步长平方可加但步长不可加,即
为验证上述分布式算法的可行性、最优性以及收敛性,这里以5个智能体的V字形协同编队飞行为例进行仿真分析。V字形协同编队飞行如图 1所示:图 1中也给出了Ni,i=1,2,…,5的定义。V字形协同编队飞行可以由两智能体间的距离以及夹角θ描述。在仿真中,将相邻智能体之间的距离设置为等距200 m,且θ=60°。
编队中每个智能体的系统矩阵和输出矩阵都分别设置为:
对于以上设定的仿真场景,本文先设计了集中算法对其进行求解,即对问题(7)直接求解。由于问题(7)是凸优化问题,可以用开源的凸优化求解器进行求解。本文使用的是CVX求解器[9, 10]。在求解问题(7)的过程中,需要将所有智能体的状态信息发送给进行计算的智能体,因此是集中式算法。集中式算法的结果由图 2中的“+”标记。最终集中式算法给出的目标函数最小值为14.346 4。将集中式算法的结果作为分布式算法的参照。分布式算法给出的优化轨迹如图 2中“o”标记的点所示,其结果与集中式算法给出的结果一致。最终时刻协同编队飞行的构型如图 3所示。
这里需要说明的是:由于在目标函数中同时考虑了智能体各自独立的目标以及系统的全局目标,最终时刻每个智能体的轨迹并没有完全跟踪参考轨迹,而最终构型也不是预先设定的V字形编队。这是因为仿真的最优结果是智能体各自独立目标与系统全局目标之间的一个妥协。
分布式算法中目标函数值的迭代结果如图 4所示(本文的迭代步长选为αk=1/k)。在图 4中,目标函数的值先增大再减小,最终收敛于最优值。从图 4可以看出,次梯度方法并不像传统的梯度下降法那样使目标函数值一直减小。在本文的仿真设定下,分布式算法只需迭代14次便收敛于最优值14.346 4。
5 结 论为了解决通信能力受限情况下的协同编队规划问题,文中提出了一种基于对偶分解方法的分布式算法,不仅能快速地收敛于全局最优值,而且只需较少的通信信息。在设计的分布式算法中,每一次迭代过程仅需相邻智能体间进行两次通信,且通信量较小(仅包括编队飞行品质和当前的最优轨迹)。文中将协同编队飞行建模为受动力学约束的优化问题,且在目标函数中考虑智能体各自独立的目标和系统的全局目标;这种建模方法有利于推导出对偶分解的基本形式。除此之外,将对偶分解和次梯度方法结合求解协同编队飞行规划问题,能够充分利用凸优化已有的理论结果对设计的分布式算法进行最优性以及收敛性证明。未来将考虑更为复杂的动力学约束和控制约束进行协同编队飞行的分布式路径规划。
[1] | 彭辉, 沈林成, 朱华勇. 基于分布式模型预测控制的多UAV协同区域搜索[J]. 航空学报,2010, 31(3): 593-601 Peng Hui, Shen Lincheng, Zhu Huayong. Multiple UAV Cooperative Area Search Based on Distributed Model Predictive Control[J]. Acta Aeronautica et Astronautica Sinica, 2010, 31(3): 593-601 (in Chinese) |
Cited By in Cnki (23) | Click to display the text | |
[2] | 李远. 多UAV协同任务资源分配与编队轨迹优化方法研究[D]. 长沙:国防科技大学, 2011 Li Yuan. Research on Resources Allocation and Formation Trajectories Optimization for Multiple UAVs Cooperation Mission[D]. Changsha, National University of Defense Technology, 2011 (in Chinese) |
Cited By in Cnki (11) | |
[3] | 白瑞光,孙鑫,陈秋双,等. 基于Gauss伪谱法的多UAV协同航迹规划[J]. 宇航学报,2014, 35(9): 1022-1029 Bai Ruiguang, Sun Xin, Chen Qiushuang, et al. Multiple UAV Cooperative Trajectory Planning Based on Gauss Pseudospectral Method[J]. Journal of Astronautics, 2014, 35(9): 1022-1029 (in Chinese) |
Cited By in Cnki (2) | |
[4] | 傅阳光,周成平,王长青,等. 考虑时间约束的无人飞行器航迹规划[J]. 宇航学报,2011, 32(4): 749-755 Fu Yangguang, Zhou Chengping, Wang Changqing, et al. Path Planning for UAV Considering Time Constraint[J]. Journal of Astronautics, 2011, 32(4): 749-755 (in Chinese) |
Cited By in Cnki (9) | Click to display the text | |
[5] | 郑大钟.线性系统理论[M].北京:清华大学出版社,2005 Zheng Dazhong. Theory of Linear Systems[M]. Beijing, Tsinghua Press, 2005 (in Chinese) |
[6] | Raffard R L, Tomlin C J, Boyd S P. Distributed Optimization for Cooperative Agents: Application to Formation Flight[C]//43rd IEEE Conference on Decision and Control, 2004: 2453-2459 |
[7] | Boyd S, Vandenberghe L. Convex optimization[M]. London, Cambridge University Press, 2004 |
[8] | Michael C, Stephen P. Graph Implementations for Nonsmooth Convex Programs[J]. Recent Advances in Learning and Control, 2008, 371: 95-110 |
Click to display the text |
2. College of Aeronautics, Northwestern Polytechnical University, Xi'an 710072, China