過娟，褚晶，閆杰

（1.西北工業(yè)大學航天學院，陜西西安 710072；2.西北工業(yè)大學航空學院，陜西西安 710072）

基于對偶分解的分布式協(xié)同編隊飛行研究

過娟1，褚晶2，閆杰1

（1.西北工業(yè)大學航天學院，陜西西安 710072；2.西北工業(yè)大學航空學院，陜西西安 710072）

針對多智能體編隊飛行問題，提出一種新的基于對偶分解的分布式算法，以實現(xiàn)協(xié)同航跡規(guī)劃。首先，將編隊飛行問題建模為受線性動力學約束的優(yōu)化問題，其目標函數(shù)中包括智能體各自的獨立目標（例如跟蹤參考軌跡）以及系統(tǒng)的全局目標（例如總?cè)剂舷?、編隊隊形等）。其次，為了分布式地求解該?yōu)化問題，將其對偶問題分解，把大計算量的原問題轉(zhuǎn)化為多個小的子問題。最后，設(shè)計了協(xié)同分布式規(guī)劃算法，并對其收斂性和最優(yōu)性進行了理論證明。由于該算法只需相鄰智能體間的通信，因此具有很強的可擴展性，并能適用于通信能力受限情況下的編隊飛行。仿真結(jié)果表明，提出的分布式算法能有效地進行協(xié)同編隊飛行規(guī)劃；同時通過與集中式方法的比較，其最優(yōu)性和收斂性得到了驗證。

分布式優(yōu)化；對偶分解；編隊飛行；協(xié)同智能體

小型無人駕駛飛行器（unmanned aerial vehicle，UAV）憑借其自身成本低、重量輕、體積小、操作靈活等諸多優(yōu)點，在軍事以及民用領(lǐng)域有著越來越廣泛的運用。然而，由于單個小型無人機的能力有限，使其難以滿足日益復雜的應用要求，因此，多小型無人機通常采用協(xié)同編隊飛行的方式完成所設(shè)計的任務(wù)，例如災后進行區(qū)域內(nèi)的協(xié)同搜索［1］，森林的火災巡邏、預警［2］等。在多無人機系統(tǒng)中，為減輕地面站的負擔，降低操作成本，增加系統(tǒng)的靈活性、可靠性、可擴展性以及魯棒性，通常將無人機設(shè)計為協(xié)同合作的智能體自主地完成機上的各種操作，而無須時刻接收地面站發(fā)送的指令。在眾多自主操作中，編隊飛行的協(xié)同軌跡規(guī)劃是多無人機系統(tǒng)完成設(shè)計任務(wù)的前提［3］。

目前文獻中的研究主要是針對單個UAV的航跡規(guī)劃［4］、多個UAV的集中式編隊飛行航跡規(guī)劃［3］以及多個UAV的混合式編隊飛行航跡規(guī)劃［2］。其中，集中式編隊飛行規(guī)劃是指編隊中的某一UAV先接收系統(tǒng)中所有UAV的信息，然后運行規(guī)劃算法，最后將生成的結(jié)果發(fā)送給其他UAV；而分布式協(xié)同規(guī)劃需要系統(tǒng)中所有UAV都承擔部分規(guī)劃計算任務(wù)，且計算過程中只需要其鄰居UAV的相關(guān)信息；混合式協(xié)同編隊規(guī)劃則介于集中式與分布式規(guī)劃之間。綜上所述，集中式編隊飛行規(guī)劃對UAV間的通信拓撲結(jié)構(gòu)有嚴格的要求（需要多點對單點的通信結(jié)構(gòu)），存在著單點脆弱性、擴展性差的缺點，不適于數(shù)目較多的多UAV系統(tǒng)（因為規(guī)劃問題的復雜度隨著UAV個數(shù)的增多而顯著增加，計算量也因此加大）。雖然混合式編隊規(guī)劃算法部分彌補了集中式算法的不足，但它依然要求多點對單點的通信結(jié)構(gòu)，且存在單點脆弱性。

對于小型UAV，其通信能力會受到平臺大小的制約，因此需要開發(fā)僅需要相鄰UAV信息的分布式算法。本文基于對偶分解原理，提出了一種新的分布式算法以實現(xiàn)多智能體編隊飛行的協(xié)同航跡規(guī)劃，給出了規(guī)劃的優(yōu)化模型，進行了對偶分解的詳細推導，分析了所設(shè)計方法的最優(yōu)性和收斂性，并完成了以5個智能體進行V字形協(xié)同編隊飛行的仿真驗證。

1　多智能體協(xié)同編隊飛行的優(yōu)化模型

在本文的研究中，假設(shè)協(xié)同編隊飛行中的每個智能體都受到線性動力學的約束；在航跡規(guī)劃中，它們既要完成各自任務(wù)也要完成系統(tǒng)的全局任務(wù)。在本文提出的協(xié)同編隊飛行的優(yōu)化模型中，首先將線性動力學約束轉(zhuǎn)化為關(guān)于決策變量的線性等式約束，然后使用目標函數(shù)描述智能體的獨立任務(wù)以及系統(tǒng)的全局任務(wù)。

1.1線性動力學約束

假設(shè)協(xié)同編隊飛行中有n個智能體，且每個智能體的動力學模型表示為：

式中，xi為第i個智能體的狀態(tài)變量，ui為其控制輸入，Aic和Bic分別是其系統(tǒng)矩陣和輸入矩陣。對于線性動力學系統(tǒng)，可以使用離散化的方法對其進行求解［5］：

式中

（3）式建立了智能體i各個時刻的狀態(tài)變量與其控制變量之間的線性關(guān)系。在協(xié)同編隊飛行中，通常希望智能體在某時刻能夠?qū)崿F(xiàn)特定的狀態(tài)目標；借助于（3）式，該狀態(tài)目標即可轉(zhuǎn)化為關(guān)于Ui的表達式。

1.2智能體的獨立目標

式中，‖·‖表示向量的2范數(shù)。每個智能體的獨立目標就是要最小化Ji。

1.3系統(tǒng)的全局目標

在本文的研究中，協(xié)同編隊飛行系統(tǒng)的全局目標主要包括所有智能體的燃料消耗總和最小以及相鄰智能體位置之間保持特定的隊形。燃料消耗總和最小可以表示為：

相鄰智能體之間的位置保持特定隊形可以表示為：

式中，Ni為與智能體i相鄰的智能體集合，δij為智能體i和j之間設(shè)定的位置隊形。

1.4優(yōu)化模型

結(jié)合（3）式～（6）式，受線性動力學約束的協(xié)同編隊飛行可以建模為以下的優(yōu)化問題：

subject to Xi=GiUi+Hixi（0），i=1，…，n優(yōu)化問題（7）的優(yōu)化變量為zi，i=1，2，…，n。

在優(yōu)化問題（7）中，目標函數(shù)包括智能體各自獨立的目標以及系統(tǒng)的全局目標，約束則由智能體的線性動力學約束構(gòu)成。由于目標函數(shù)是二次型多項式且約束為線性等式約束，因此優(yōu)化問題（7）是一個凸優(yōu)化問題［7］。

2　對偶分解

運用對偶分解分布式地求解優(yōu)化問題（7）就是要將原來包含所有智能體變量的大型、非線性問題分解成一系列較小的問題進行求解；且每個小問題只與一個獨立智能體相關(guān)，并只包含這個智能體的變量。因此，原問題便可以被分配到每個智能體上求解，這就構(gòu)成了分布式算法。然而，優(yōu)化問題（7）的目標函數(shù)不具備可分解的形式，首先需要對其進行解耦操作。

2.1解耦目標函數(shù)

優(yōu)化問題（7）的目標函數(shù)中，第1個求和符號里的求和項是解耦的，但第2個求和符號中的Xi會出現(xiàn)在不同的非線性求和項中，因此求和項之間是耦合的，需要進行解耦操作。解耦的目的即建立一個與問題（7）等價的新問題，且在求和符號中的不同非線性求和項中不存在相同的優(yōu)化變量，從而便于進行對偶分解。為此，為每個智能體引入松弛變量，將問題（7）轉(zhuǎn)化為：引入松弛變量后，優(yōu)化問題（8）的目標函數(shù)是解耦的。顯而易見，優(yōu)化問題（8）與問題（7）等價，也是凸優(yōu)化問題。問題（8）中的可以理解為智能體Xij獲得的相鄰智能體j的狀態(tài)信息。

2.2具備可分解形式的對偶問題

為設(shè)計分布式算法，需要將優(yōu)化問題（8）分解為一系列可由智能體獨立求解的小問題。然而，優(yōu)化問題（8）的原始形式不便于分解。但由于優(yōu)化問題（8）是凸優(yōu)化問題，具備強對偶性，因此它的解可以通過求解其對偶問題獲得。經(jīng)過下面的推導，可以看出優(yōu)化問題（8）的對偶問題具備可分解的形式。然而，為求得優(yōu)化問題（8）的對偶問題，首先要推導出它的拉格朗日函數(shù)，接著再求出它的對偶函數(shù)。

優(yōu)化問題（8）的部分拉格朗日函數(shù)為：

式中，μi是與等式約束對應的拉格朗日乘子向量，而vij是與等式約束對應的拉格朗日乘子向量。由（9）式可以看出，引入松弛變量后，優(yōu)化問題（8）的部分拉格朗日函數(shù)L是解耦的。因此，相關(guān)的對偶函數(shù)也是解耦的。優(yōu)化問題（8）的對偶函數(shù)為：

式中，μ是由所有μi（i=1，2，…，n）構(gòu)成的向量，v是由所有構(gòu)成的向量，L1i=且

當智能體的獨立目標為跟蹤參考軌跡，而系統(tǒng)的全局目標包含總?cè)剂舷淖钚r，可以根據(jù)L1i的最小值推導出最優(yōu)控制和最優(yōu)軌跡的表達式。將（3）式代入L1i得到：

式中

為求L1i的最小值，應使下式成立：

結(jié)合（15）式和（16）式，L1i的最小值為

L2i關(guān)于以及Xij的最小值推導如下。首先，L2i相對于以及Xij的偏導數(shù)應滿足：

以及

聯(lián)立（18）式和（19）式可以得到如下重要的關(guān)系式：

將（20）式代入（11）式有：

由（21）式可知，L2i是關(guān)于的一個二次函數(shù)，其最小值為：

將（23）式代入（22）式，L2i的最小值變?yōu)?/p>

結(jié)合（23）式和（20）式，L1i的最小值也可由編隊飛行的隊形品質(zhì)ξij表示：

將（24）式和（25）式代入（10）式，優(yōu)化問題（8）式的對偶函數(shù)變?yōu)橐粋€關(guān)于編隊飛行隊形品質(zhì)的函數(shù)：

式中，ξ是由所有ξij（i=1，2，…，n，j∈Ni）構(gòu)成的向量。

至此，優(yōu)化問題（8）式的對偶問題可描述為：

顯而易見，結(jié)合（26）式，對偶問題（27）式相對于ξij具備可分解的形式。因此，分布式地求解問題（27）式便可以獲得優(yōu)化問題（8）式的解。

2.3對偶問題的求解

在本文的研究中，運用次梯度方法求解對偶問題（7）［8］。由于次梯度方法只適用于求解函數(shù)的最小值，故將對偶問題（7）轉(zhuǎn)化為求解-g（ξ）的最小值。函數(shù)-g（ξ）相對于ξij的一個次梯度可表示為：

運用次梯度方法，ξij的迭代公式如下：

式中，ξij（k）為ξij第k次迭代時的值，αk為第k次迭代時的迭代步長，s（k）為第k次迭代時次梯度的值，即：

一般情況下，迭代步長αk有5種選取準則［8］。①定步長，即αk=α，α為正常數(shù)。②定間隔，即每次迭代中ξij前后差值的模為常數(shù)。例如，αk= γ/‖s（k）‖2，式中γ為正常數(shù)。③步長平方可加但步長不可加，例如αk=a/（b+k），式中a為正數(shù)，b為非負數(shù)。④步長不可加而步長遞減，例如αk=a/，式中a為正數(shù)。⑤間隔不可加而間隔遞減，例如。前2種步長選取準則只能保證次梯度算法收斂到最優(yōu)值的某個鄰域，而后3種準則能確保次梯度算法收斂于最優(yōu)值。

3　分布式協(xié)同算法

3.1算法的描述

在上一節(jié)推導的基礎(chǔ)上，可以設(shè)計出適用于多智能體協(xié)同編隊飛行的分布式算法。該算法總結(jié)如下。

2）智能體i根據(jù)（3）式計算νij（k）和νji（k），并根據(jù)（20）式計算μi（k）；

5）智能體i根據(jù)（9）式計算ξji（k+1）以更新編隊飛行品質(zhì)。

以上的分布式算法可以有如下直觀的解釋。首先，每個智能體先忽略系統(tǒng)的全局目標，只基于各自的局部目標計算最優(yōu)軌跡。接著，每個智能體將自己的最優(yōu)軌跡信息發(fā)送給那些與它在全局目標中相關(guān)聯(lián)的智能體；與此同時，也接收來自于這些智能體的最優(yōu)軌跡信息。在交換軌跡信息之后，每個智能體開始計算它與全局目標的偏離量，再基于偏移量計算出新的最優(yōu)軌跡。重復以上過程直至與全局目標的偏離量收斂。

在本文設(shè)計的分布式算法中，一共存在兩次信息交互的過程。第一次是交互編隊飛行品質(zhì)信息；第二次是交互最優(yōu)軌跡信息。兩次信息的交互都只發(fā)生在相鄰的智能體之間，因此對系統(tǒng)的通信拓撲結(jié)構(gòu)沒有苛刻的要求。

3.2算法的最優(yōu)性

本文提出的分布式算法采用次梯度方法求解優(yōu)化問題（8）的對偶問題（27）。由于優(yōu)化問題（8）是一個凸優(yōu)化問題，對于有可行解的協(xié)同編隊飛行問題（意味著滿足Slater條件），根據(jù)凸優(yōu)化理論，優(yōu)化問題（8）具有強對偶性［7］。因此，由對偶問題（27）的最優(yōu)解能得到優(yōu)化問題（8）的最優(yōu)解；又由于最優(yōu)問題（8）和問題（7）等價，故分布式算法能給出協(xié)同編隊飛行問題的最優(yōu)解。

3.3算法的收斂性［8］

分布式算法的收斂性取決于運用次梯度方法求解對偶問題（27）的收斂性。令f（ξ）=-g（ξ），則要說明次梯度方法的收斂性就是要比較迭代值f（ξk）（ξk為第k次迭代時向量ξ的值）與最優(yōu)值f（ξ?）（ξ?為f（ξ）取得最優(yōu)值時向量ξ的值）之間的關(guān)系。首先，根據(jù)迭代公式，有以下關(guān)系式成立：

根據(jù)次梯度的定義有［8］：

將不等（32）式代入（31）式中，得到：

重復運用不等關(guān)系式（33），得到：

令‖ξ0-ξ?‖2≤R，即初始值ξ0選取在ξ的有界值域內(nèi)，則有：

令fbest是迭代過程中使得f（ξi）-f（ξ?），i=0，1，…，k，最小的函數(shù)值，則：

由（26）式可以看出：f（ξ）是一個關(guān)于ξ的二次函數(shù)，因此滿足Lipschitz條件，即

結(jié)合不等（37）式、（32）和（36）式，有

如果迭代步長的選取準則為步長平方可加但步長不可加，即

4　仿真與分析

為驗證上述分布式算法的可行性、最優(yōu)性以及收斂性，這里以5個智能體的V字形協(xié)同編隊飛行為例進行仿真分析。V字形協(xié)同編隊飛行如圖1所示：圖1中也給出了的定義。V字形協(xié)同編隊飛行可以由兩智能體間的距離以及夾角θ描述。在仿真中，將相鄰智能體之間的距離設(shè)置為等距200 m，且θ=60°。

圖1　包含5個智能體的V字形協(xié)同編隊飛行

編隊中每個智能體的系統(tǒng)矩陣和輸出矩陣都分別設(shè)置為：

在后面的仿真算例中，將λ設(shè)為0。智能體的初始狀態(tài)為（位置單位為km，速度單位為km/s）：

即初始時刻5個智能體兩兩相距100 m一字排開。每個智能體跟蹤的參考軌跡相同：該參考軌跡為三次曲線y=x3，且x∈［-2 km，2 km］，如圖2中虛線所示。在仿真中，初始時刻設(shè)為0時刻，編隊飛行的總時間為50 s，離散化步長為1 s。而在分布式算法的初始輸入中，都設(shè)為0向量。

對于以上設(shè)定的仿真場景，本文先設(shè)計了集中算法對其進行求解，即對問題（7）直接求解。由于問題（7）是凸優(yōu)化問題，可以用開源的凸優(yōu)化求解器進行求解。本文使用的是CVX求解器［9-10］。在求解問題（7）的過程中，需要將所有智能體的狀態(tài)信息發(fā)送給進行計算的智能體，因此是集中式算法。集中式算法的結(jié)果由圖2中的“+”標記。最終集中式算法給出的目標函數(shù)最小值為14.346 4。將集中式算法的結(jié)果作為分布式算法的參照。分布式算法給出的優(yōu)化軌跡如圖2中“o”標記的點所示，其結(jié)果與集中式算法給出的結(jié)果一致。最終時刻協(xié)同編隊飛行的構(gòu)型如圖3所示。

圖2　協(xié)同編隊飛行軌跡優(yōu)化仿真結(jié)果 圖3　編隊飛行50秒時刻的構(gòu)型 圖4　分布式算法中目標函數(shù)值的迭代結(jié)果

這里需要說明的是：由于在目標函數(shù)中同時考慮了智能體各自獨立的目標以及系統(tǒng)的全局目標，最終時刻每個智能體的軌跡并沒有完全跟蹤參考軌跡，而最終構(gòu)型也不是預先設(shè)定的V字形編隊。這是因為仿真的最優(yōu)結(jié)果是智能體各自獨立目標與系統(tǒng)全局目標之間的一個妥協(xié)。

分布式算法中目標函數(shù)值的迭代結(jié)果如圖4所示（本文的迭代步長選為αk=1/k）。在圖4中，目標函數(shù)的值先增大再減小，最終收斂于最優(yōu)值。從圖4可以看出，次梯度方法并不像傳統(tǒng)的梯度下降法那樣使目標函數(shù)值一直減小。在本文的仿真設(shè)定下，分布式算法只需迭代14次便收斂于最優(yōu)值14.346 4。

5　結(jié) 論

為了解決通信能力受限情況下的協(xié)同編隊規(guī)劃問題，文中提出了一種基于對偶分解方法的分布式算法，不僅能快速地收斂于全局最優(yōu)值，而且只需較少的通信信息。在設(shè)計的分布式算法中，每一次迭代過程僅需相鄰智能體間進行兩次通信，且通信量較小（僅包括編隊飛行品質(zhì)和當前的最優(yōu)軌跡）。文中將協(xié)同編隊飛行建模為受動力學約束的優(yōu)化問題，且在目標函數(shù)中考慮智能體各自獨立的目標和系統(tǒng)的全局目標；這種建模方法有利于推導出對偶分解的基本形式。除此之外，將對偶分解和次梯度方法結(jié)合求解協(xié)同編隊飛行規(guī)劃問題，能夠充分利用凸優(yōu)化已有的理論結(jié)果對設(shè)計的分布式算法進行最優(yōu)性以及收斂性證明。未來將考慮更為復雜的動力學約束和控制約束進行協(xié)同編隊飛行的分布式路徑規(guī)劃。

［1］ 彭輝，沈林成，朱華勇.基于分布式模型預測控制的多UAV協(xié)同區(qū)域搜索［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）

［2］ 李遠.多UAV協(xié)同任務(wù)資源分配與編隊軌跡優(yōu)化方法研究［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）

［3］ 白瑞光，孫鑫，陳秋雙，等.基于Gauss偽譜法的多UAV協(xié)同航跡規(guī)劃［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）

［4］ 傅陽光，周成平，王長青，等.考慮時間約束的無人飛行器航跡規(guī)劃［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）

［5］ 鄭大鐘.線性系統(tǒng)理論［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

Distributed Cooperative Planning of Formation Flying Based on Dual Decomposition

Guo Juan1，Chu Jing2，Yan Jie1
1.College of Astronautics，Northwestern Polytechnical University，Xi′an 710072，China 2.College of Aeronautics，Northwestern Polytechnical University，Xi′an 710072，China

This paper presents a distributed algorithm to address the cooperative planning of multiple agents flying in formation.First，the cooperative trajectory planning subject to linear dynamics constraints is formulated as an optimization problem，where the objective includes not only private（such as tracking reference trajectories）but also common（such as overall fuel consumption，formation and so on）goals for all agents.Second，in order to solve the optimization problem in a distributed fashion，the dual decomposition technique is employed to replace the original complex problem of very high computational load by multiple smaller sub-problems，which are then distributed over agents.Last but not least，a distributed algorithm is developed to solve the dual problem and thus the original cooperative planning problem because there is no duality gap due to the convexity of the problem.Since the algorithm only requires neighbors′information，it is scalable and applicable when the communication capabilities are limited. Simulation results show the efficiency and efficacy of the algorithm when applied to the cooperative planning of formation flying.Meanwhile，as compared with the centralized method，the optimality and convergence of the algorithm are demonstrated as well.

algorithms，computer simulation，convergence of numerical methods，convex optimization，dynamics，efficiency，fuel consumption，matrix algebra，optimization，scalability，trajectories，vectors；cooperative agents，distributed optimization，dual decomposition，formation flying

TP391

A

1000-2758（2015）06-0892-08

2015-04-01

過娟（1986—），女，西北工業(yè)大學博士研究生，主要從事分布式優(yōu)化及制導技術(shù)的研究。