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

過娟，褚晶，閆杰

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

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

過娟1，褚晶2，閆杰1

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

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

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

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

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

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

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

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

1.1線性動(dòng)力學(xué)約束

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

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

式中

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

1.2智能體的獨(dú)立目標(biāo)

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

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

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

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

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

1.4優(yōu)化模型

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

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

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

2　對(duì)偶分解

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

2.1解耦目標(biāo)函數(shù)

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

2.2具備可分解形式的對(duì)偶問題

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

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

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

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

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

式中

為求L1i的最小值，應(yīng)使下式成立：

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

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

以及

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

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

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

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

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

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

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

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

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

2.3對(duì)偶問題的求解

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

運(yùn)用次梯度方法，ξij的迭代公式如下：

式中，ξij（k）為ξij第k次迭代時(shí)的值，αk為第k次迭代時(shí)的迭代步長(zhǎng)，s（k）為第k次迭代時(shí)次梯度的值，即：

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

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

3.1算法的描述

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

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

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

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

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

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

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

3.3算法的收斂性［8］

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

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

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

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

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

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

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

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

如果迭代步長(zhǎng)的選取準(zhǔn)則為步長(zhǎng)平方可加但步長(zhǎng)不可加，即

4　仿真與分析

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

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

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

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

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

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

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

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

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

5　結(jié) 論

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

［1］ 彭輝，沈林成，朱華勇.基于分布式模型預(yù)測(cè)控制的多UAV協(xié)同區(qū)域搜索［J］.航空學(xué)報(bào)，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］ 李遠(yuǎn).多UAV協(xié)同任務(wù)資源分配與編隊(duì)軌跡優(yōu)化方法研究［D］.長(zhǎng)沙：國(guó)防科技大學(xué)，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］.宇航學(xué)報(bào)，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］ 傅陽(yáng)光，周成平，王長(zhǎng)青，等.考慮時(shí)間約束的無人飛行器航跡規(guī)劃［J］.宇航學(xué)報(bào)，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］.北京：清華大學(xué)出版社，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è)大學(xué)博士研究生，主要從事分布式優(yōu)化及制導(dǎo)技術(shù)的研究。