多架無(wú)人機(jī)協(xié)同航路規(guī)劃問題研究

漆云海　葉文

【摘 要】針對(duì)同時(shí)到達(dá)的多機(jī)協(xié)同航路規(guī)劃問題，采用層次分解的方法，應(yīng)用小生境克隆選擇算法能夠?yàn)闊o(wú)人機(jī)生成多條不同的滿足實(shí)際需求的可選航路，同時(shí)引入?yún)f(xié)同變量和協(xié)同函數(shù)的概念，解決規(guī)劃航路的時(shí)間協(xié)同問題。仿真結(jié)果表明，該方法能夠有效地解決多機(jī)協(xié)同航路規(guī)劃問題，實(shí)現(xiàn)多機(jī)協(xié)同航路規(guī)劃的協(xié)同控制。

【關(guān)鍵詞】多機(jī)協(xié)同；航路規(guī)劃；層次分解策略；小生境克隆選擇算法

無(wú)人機(jī)多機(jī)協(xié)同航路規(guī)劃是多架無(wú)人機(jī)協(xié)同作戰(zhàn)任務(wù)規(guī)劃系統(tǒng)中的關(guān)鍵技術(shù)。它是根據(jù)戰(zhàn)場(chǎng)環(huán)境信息，綜合考慮無(wú)人機(jī)導(dǎo)航精度和機(jī)動(dòng)能力的限制，為無(wú)人機(jī)設(shè)計(jì)出既滿足團(tuán)隊(duì)協(xié)同的要求，又使整體生存概率最大的飛行航路。在防空技術(shù)日益先進(jìn)、防空體系日益完善的現(xiàn)代戰(zhàn)爭(zhēng)中，利用航路規(guī)劃可以有效地提高無(wú)人機(jī)完成任務(wù)的成功率。

1 多機(jī)協(xié)同航路規(guī)劃的數(shù)學(xué)模型

1.1 多機(jī)協(xié)同航路規(guī)劃的問題描述

多機(jī)協(xié)同航路規(guī)劃的目的就是為每架無(wú)人機(jī)生成一條航路，保證無(wú)人機(jī)能夠同時(shí)或者按照一定的時(shí)間間隔到達(dá)各自的目標(biāo)點(diǎn)，并且盡量提高無(wú)人機(jī)的生存概率[1-2]。這樣生成的航路對(duì)于每個(gè)單一的無(wú)人機(jī)來(lái)說(shuō)，不一定是最優(yōu)的，但對(duì)于整個(gè)無(wú)人機(jī)編隊(duì)來(lái)說(shuō)，卻必須是最優(yōu)或是近似最優(yōu)的。

作戰(zhàn)想定：為了提高攻擊的有效性，同步攻擊時(shí)，讓多架無(wú)人機(jī)同時(shí)到達(dá)預(yù)先指定的目標(biāo)位置。圖1顯示了由兩架無(wú)人機(jī)組成的編隊(duì)執(zhí)行飛行任務(wù)的情形，圖中虛線為預(yù)先規(guī)劃好的航路，保證整個(gè)無(wú)人機(jī)編隊(duì)有相同的估計(jì)到達(dá)時(shí)間（Estimated Time of Arrival， ETA），使得UCAV同時(shí)到達(dá)目標(biāo)點(diǎn)。兩無(wú)人機(jī)沿各自的航路飛行，當(dāng)無(wú)人機(jī)2探測(cè)到新的威脅時(shí)，當(dāng)前的航路不再是最優(yōu)的（無(wú)人機(jī)2可能被擊毀），此時(shí)，整個(gè)編隊(duì)有必要重新計(jì)算一個(gè)編隊(duì)協(xié)同飛行時(shí)間ETA。相應(yīng)地，需要重新規(guī)劃路徑。圖中的實(shí)線為新生成的航路，它們保證整個(gè)無(wú)人機(jī)編隊(duì)具有新的ETA。顯然新路徑對(duì)于無(wú)人機(jī)1來(lái)說(shuō)是次優(yōu)的，但對(duì)于整個(gè)編隊(duì)來(lái)說(shuō)，新路徑使得整個(gè)編隊(duì)都能安全、同時(shí)到達(dá)目標(biāo)點(diǎn)。因此，多無(wú)人機(jī)協(xié)同航路規(guī)劃的關(guān)鍵問題是確定同時(shí)到達(dá)目標(biāo)點(diǎn)的協(xié)同時(shí)間，然后就可以根據(jù)協(xié)同時(shí)間進(jìn)行編隊(duì)中各架無(wú)人機(jī)飛行航路的規(guī)劃。

圖1 多無(wú)人機(jī)協(xié)同航路規(guī)劃

1.2 多機(jī)協(xié)同航路規(guī)劃的性能指標(biāo)

性能指標(biāo)主要包括完成規(guī)定任務(wù)的安全性能指標(biāo)和燃油性能指標(biāo)，即威脅代價(jià)最小性能指標(biāo)和燃油代價(jià)最小性能指標(biāo)。

威脅代價(jià)最小性能指標(biāo)為：

燃油代價(jià)最小性能指標(biāo)為：

則多UCAV協(xié)同航路規(guī)劃的總性能指標(biāo)為：

式中的k為權(quán)衡系數(shù)，取威脅和燃油之間一個(gè)折衷的數(shù)，加權(quán)的大小取決于權(quán)項(xiàng)的重要性和可行性的綜合指標(biāo)。

1.3 多機(jī)協(xié)同航路規(guī)劃的約束條件

多架無(wú)人機(jī)協(xié)同航路規(guī)劃的約束條件不僅僅考慮單機(jī)的物理性能和單架無(wú)人機(jī)的任務(wù)需求，而且要將各無(wú)人機(jī)間的協(xié)同與合作關(guān)系考慮進(jìn)來(lái)，其中包括同時(shí)達(dá)到目標(biāo)約束和無(wú)人機(jī)間的最小安全距離約束等。下面我們分別加以描述：

最大作戰(zhàn)半徑約束：這限制了航路的長(zhǎng)度必須小于或等于一個(gè)預(yù)先設(shè)置的最大距離。它取決于無(wú)人機(jī)所攜帶的燃料以及到達(dá)目標(biāo)所允許的飛行時(shí)間。

最小轉(zhuǎn)彎半徑約束：它限制了生成的航路轉(zhuǎn)彎半徑必須大于無(wú)人機(jī)的最小轉(zhuǎn)彎半徑。該約束條件取決于無(wú)人機(jī)的性能和飛行任務(wù)。

禁飛區(qū)約束：由于政治人文因素，存在一些政治人文性禁/避飛區(qū)；由于天氣等自然條件的影響使得無(wú)人機(jī)必須避開極度惡劣的天氣區(qū)域。

時(shí)域協(xié)同約束：保證無(wú)人機(jī)能夠同時(shí)或者按照一定的時(shí)間間隔到達(dá)各自的目標(biāo)點(diǎn)。

空域協(xié)同約束：保證飛行過程中無(wú)人機(jī)之間不發(fā)生碰撞，限制無(wú)人機(jī)與其他無(wú)人機(jī)之間距離大于規(guī)定的最小距離。

2 多機(jī)協(xié)同航路規(guī)劃問題的求解

2.1 多機(jī)協(xié)同航路規(guī)劃問題的求解方法

多機(jī)協(xié)同航路規(guī)劃所要解決的協(xié)同問題主要是時(shí)域協(xié)同，時(shí)域協(xié)同是要保證飛機(jī)能夠同時(shí)或者按照一定的時(shí)間間隔到達(dá)各自的目標(biāo)點(diǎn)。

目前，多機(jī)協(xié)同航路規(guī)劃研究的時(shí)間協(xié)同問題主要還是同時(shí)到達(dá)情況。為了滿足多機(jī)同時(shí)到達(dá)的任務(wù)需求，通常采用層次分解的思想將多機(jī)的協(xié)同航路規(guī)劃分解為三個(gè)層次，即航路規(guī)劃層、協(xié)同規(guī)劃層、航路平滑層，如圖2所示。航路規(guī)劃層獨(dú)立規(guī)劃出各自飛機(jī)的Num條備選航路，N架無(wú)人機(jī)就有N×Num條航路組成備選航路集合；協(xié)同規(guī)劃層引入?yún)f(xié)同變量和協(xié)同函數(shù)，在備選航路集合中為每架飛機(jī)選出既能滿足編隊(duì)同時(shí)到達(dá)的要求，又使編隊(duì)代價(jià)最小（次?。┑暮铰泛惋w行速度；最后一步是由每架飛機(jī)的航路平滑層對(duì)協(xié)同規(guī)劃層選出的航路進(jìn)行平滑處理，滿足飛機(jī)的力學(xué)約束，并不改變其幾何長(zhǎng)度，以保證同時(shí)（依次）到達(dá)目標(biāo)。

圖2 多機(jī)協(xié)同航路規(guī)劃層次結(jié)構(gòu)

2.2 單機(jī)多航路規(guī)劃

航路規(guī)劃層要求能夠獨(dú)立規(guī)劃出各自飛機(jī)的Num條備選航路，以便在協(xié)同規(guī)劃層根據(jù)不同需要決定選擇合適的飛行航路。因此，在應(yīng)用層次分解策略求解多機(jī)協(xié)同航路規(guī)劃問題時(shí)，必須對(duì)單機(jī)多航路規(guī)劃技術(shù)進(jìn)行研究。根據(jù)單機(jī)多航路規(guī)劃的實(shí)際需求，航路規(guī)劃算法不僅能夠在可行域內(nèi)尋找全局最優(yōu)航路，而且還能夠搜索多個(gè)全局最優(yōu)航路和有意義的局部最優(yōu)航路，從而為決策者提供多種選擇或多方面的信息[4-5]。

免疫系統(tǒng)作為一種分布式自學(xué)習(xí)系統(tǒng)，通過進(jìn)化地處理不同抗體，在有效識(shí)別抗原的同時(shí)，能夠?qū)崿F(xiàn)各種抗體并存，具有良好的優(yōu)化和多樣化保持功能。免疫系統(tǒng)通過B細(xì)胞的高變異克隆可以維持多種小生境，因而有利于保存多種模式；同時(shí)，由于存在模式補(bǔ)充機(jī)制，能夠克服初始模式不完備的缺陷；加上所采用的遞減式變異方式類似于梯度尋優(yōu)，搜索能力較強(qiáng)，因而更適合于求解單機(jī)多航路規(guī)劃問題[6-7]。

本文在傳統(tǒng)的小生境遺傳算法求解多模態(tài)函數(shù)優(yōu)化問題的基礎(chǔ)上，針對(duì)免疫系統(tǒng)中克隆選擇算法的不足，運(yùn)用小生境、記憶算子、抑制算子和重組算子等技術(shù)對(duì)算法進(jìn)行改造，并且應(yīng)用小生境克隆選擇算法來(lái)求解單機(jī)多航路規(guī)劃問題。

單機(jī)多航路規(guī)劃算法的實(shí)現(xiàn)流程為：

（1）根據(jù)編碼，應(yīng)用隨機(jī)數(shù)函數(shù)隨機(jī)產(chǎn)生群體的初始抗體Ab；

（2）針對(duì)每一抗體，形成相應(yīng)的航路，并計(jì)算相應(yīng)抗體的抗體-抗原親和度函數(shù)值；

（3）進(jìn)行記憶操作，將抗體的函數(shù)評(píng)價(jià)值大于記憶閥值δm的抗體通過記憶算子添加到記憶庫(kù)中，并對(duì)其進(jìn)行抑制算子操作，比較記憶庫(kù)中是否有其相似性抗體，如果有，則刪除其中函數(shù)評(píng)價(jià)值小的抗體；

（4）應(yīng)用小生境適應(yīng)值共享函數(shù)對(duì)抗體的抗體-抗原親和度進(jìn)行調(diào)整；

（5）對(duì)Ab中的抗體按照調(diào)整后的親和度由大至小按降序排列，再將這個(gè)抗體按照克隆擴(kuò)增操作公式進(jìn)行克隆擴(kuò)增，得到規(guī)模為Nc的抗體群Ab′，由初始抗體群中N個(gè)抗體分別對(duì)應(yīng)的N個(gè)子抗體群組成；

（6）對(duì)Ab′中的抗體進(jìn)行抗體變異和抗體重組操作，得到規(guī)模為Nc的新抗體群Abm；

（7）計(jì)算抗體群Abm的每個(gè)抗體親和度；

（8）根據(jù)抗體的親和度，從每個(gè)子抗體群中選出一個(gè)親和度最高的抗體組成抗體群Abx，注意是從每個(gè)子抗體群中選出一個(gè)最高的，而不是在所有抗體中進(jìn)行選擇；

（9）隨機(jī)產(chǎn)生規(guī)模為Nr的抗體群Abr，選出親和度最高的Ns個(gè)抗體組成抗體群Abs；

（10）用Abs代替Abx中親和度最低的Ns個(gè)抗體，形成規(guī)模為N的抗體群Ab；

（11）判斷是否滿足終止條件，不滿足則轉(zhuǎn)至步驟（2）繼續(xù)執(zhí)行，滿足則結(jié)束計(jì)算。記憶庫(kù)中的抗體即為要搜索的峰值抗體。

基于小生境克隆選擇算法的單機(jī)多航路規(guī)劃的具體實(shí)現(xiàn)見參考文獻(xiàn)[8]。

2.3 協(xié)同變量與協(xié)同函數(shù)

對(duì)于協(xié)同問題，分層的目的是把一個(gè)復(fù)雜的優(yōu)化問題分解為小的可直接優(yōu)化的問題，并且允許分布在各個(gè)無(wú)人機(jī)中進(jìn)行計(jì)算，無(wú)人機(jī)之間不需要太多的通信，同時(shí)考慮了威脅和各個(gè)無(wú)人機(jī)的代價(jià)問題。這樣引出問題的關(guān)鍵：需要決定每架無(wú)人機(jī)之間交流什么樣的信息，才能使整個(gè)無(wú)人機(jī)的編隊(duì)進(jìn)行有效的配合協(xié)同，從而規(guī)劃出對(duì)整個(gè)團(tuán)隊(duì)而言是最優(yōu)的協(xié)同航路。為了實(shí)現(xiàn)會(huì)聚目的，系統(tǒng)選擇一個(gè)估計(jì)的會(huì)聚時(shí)ETA（Estimated Time of Arrival）來(lái)對(duì)每架無(wú)人機(jī)的航路進(jìn)行協(xié)同[9]。

假設(shè)飛機(jī)的速度v∈[vmin，vmax]，則對(duì)于某架飛機(jī)i航路規(guī)劃層規(guī)劃得到的某條航路Lj，其預(yù)計(jì)到達(dá)目標(biāo)的時(shí)間為Tj∈[Lj/vmax，Lj/vmin]。對(duì)于某架飛機(jī)i的Num條航路，其預(yù)計(jì)到達(dá)目標(biāo)的時(shí)間則是Num個(gè)時(shí)間范圍的并集Si。

對(duì)于N架飛機(jī)組成的編隊(duì)，則有一個(gè)時(shí)間交集S=S1∩S2∩…∩SN。如果S不為空集，假設(shè)Ta∈S，則每架飛機(jī)都存在對(duì)應(yīng)于到達(dá)時(shí)間為Ta的航路，因此每架飛機(jī)選擇此航路飛行，則可滿足同時(shí)到達(dá)要求，這里Ta就為協(xié)同變量。

由于時(shí)間交集S是一個(gè)集合，那么怎樣來(lái)選取其中一個(gè)元素作為協(xié)同變量的值呢？這里，通過構(gòu)建一個(gè)協(xié)同函數(shù)Jxt來(lái)實(shí)現(xiàn)對(duì)協(xié)同變量值的確定。

其中k1、k2是系數(shù)，Jj是在航線規(guī)劃層得到的某條航線的代價(jià)，只與航路有關(guān)。對(duì)于固定的一條航路，代價(jià)Jj是一定的，Jj=kJthreat+（1-k）Jfuel。

這樣每一條航路的代價(jià)Jxt，j都是到達(dá)時(shí)間Tj的函數(shù)。編隊(duì)的總體代價(jià)為：

式中N為飛機(jī)的數(shù)目。

對(duì)于每一條航路，其飛行時(shí)間不同，代價(jià)Jxt也隨著變化，圖3示意了代價(jià)Jxt與協(xié)同變量Ta的關(guān)系。稱Jxt為協(xié)同函數(shù)，因?yàn)樗軌蝮w現(xiàn)協(xié)同變量Ta的變化如何影響飛機(jī)的生存、安全性，即代價(jià)。

圖3 最優(yōu)ETA決策

因此，協(xié)同規(guī)劃層根據(jù)協(xié)同函數(shù)Jxt，來(lái)確定選擇合適的協(xié)同變量Ta，使飛機(jī)的協(xié)同函數(shù)之和最小，還要保證選擇的Ta滿足每架飛機(jī)的威脅和燃料約束。根據(jù)協(xié)同變量Ta，就能為每一架飛機(jī)確定航路，最終得到多機(jī)的協(xié)同航路。

3 仿真驗(yàn)證與分析

設(shè)定任務(wù)需要3架無(wú)人機(jī)協(xié)同來(lái)完成任務(wù)，設(shè)定UAV1的出發(fā)點(diǎn)為（-10，40）、目標(biāo)點(diǎn)為（90，-70），UAV2的出發(fā)點(diǎn)為（20，60）、目標(biāo)點(diǎn)為（120，-60），UAV3的出發(fā)點(diǎn)為（70，70）、目標(biāo)點(diǎn)為（130，-40），設(shè)3架無(wú)人機(jī)的速度范圍均為40-60m/s。通過單機(jī)多航路規(guī)劃算法分別規(guī)劃得到UAV1、UAV2、UAV3的各自三條分散的最優(yōu)及次優(yōu)航路。飛機(jī)編隊(duì)估計(jì)到達(dá)時(shí)間ETA的最優(yōu)決策如圖4所示。協(xié)同時(shí)間ETA取2805s時(shí)，即保證3架無(wú)人機(jī)同時(shí)到達(dá)目標(biāo)點(diǎn)。最終得到的協(xié)同航路如圖5所示。表1為規(guī)劃結(jié)果統(tǒng)計(jì)。

圖4 ETA的最優(yōu)決策圖

圖5 多機(jī)協(xié)同規(guī)劃的結(jié)果

表1 協(xié)同航路信息

4 結(jié)論

根據(jù)多機(jī)協(xié)同航路規(guī)劃問題的特點(diǎn)，將層次分解策略與小生境克隆選擇算法相結(jié)合，提出了一種基于層次分解策略和小生境克隆選擇算法的多機(jī)協(xié)同航路規(guī)劃方法。采用層次分解策略將一個(gè)單一龐大的優(yōu)化問題分解為多個(gè)小的、更具可操作性的優(yōu)化問題。多機(jī)協(xié)同航路規(guī)劃過程被分解到編隊(duì)中的各飛機(jī)間進(jìn)行，讓每一架飛機(jī)根據(jù)任務(wù)要求采用小生境克隆選擇算法自主地計(jì)算自己的最優(yōu)飛行航路和備選的次優(yōu)航路，最終通過協(xié)同變量和協(xié)同函數(shù)，確定編隊(duì)的協(xié)同航路，解決復(fù)雜戰(zhàn)場(chǎng)環(huán)境下多機(jī)協(xié)同航路規(guī)劃問題，為復(fù)雜環(huán)境下的協(xié)同航路規(guī)劃問題求解提供一種新的有效方法。

【參考文獻(xiàn)】

[1]葉媛媛.多UCAV協(xié)同任務(wù)規(guī)劃方法研究[J].長(zhǎng)沙：國(guó)防科學(xué)技術(shù)大學(xué)，2005.

[2]Dario Bauso， Laura Giarre and Raffaele Pesenti. Multiple UAV Cooperative Path Planning via Neuro-Dynamic Programming[J]. 43rd IEEE Conference on Decision and Control.2004：1087-1092.

[3]Timothy W. McLain ，Randal W. Beard. Coordination Variables， Coordination Functions， and Cooperative Timing Missions[J]. Journal of Guidance，Control and Dynamics. 2005. Vol. 28， No. 1：150-161.

[4]R.J.Szczerba， P.Galkowski， I.S.Glickstein. Robust Algorithm for Real-time Route Planning[J]. IEEE Transactions on Aerospace and Electronic System. 2000，36（3）：869-878.

[5]鄭昌文.飛行器航跡規(guī)劃方法研究[D].華中科技大學(xué)，2003：84-90.

[6]Leandro N de Castro，Jonathan Tinunis. Artifieial Immune Systems： a New Computational Intelligence Approach[M]. British：SPringerPress. 2002：77-88.

[7]王曉蘭，李恒杰.多模態(tài)函數(shù)優(yōu)化的小生境克隆選擇算法[J].甘肅科學(xué)學(xué)報(bào)，2006，18（3）：64-69.

[8]葉文，朱明，李海軍，鞠傳文.基于小生境克隆選擇算法的單UCAV多航路規(guī)劃[C]//2010中國(guó)制導(dǎo)、導(dǎo)航與控制學(xué)術(shù)會(huì)議，2010，10：1062-1069.

[責(zé)任編輯：湯靜]

單機(jī)多航路規(guī)劃算法的實(shí)現(xiàn)流程為：

（1）根據(jù)編碼，應(yīng)用隨機(jī)數(shù)函數(shù)隨機(jī)產(chǎn)生群體的初始抗體Ab；

（2）針對(duì)每一抗體，形成相應(yīng)的航路，并計(jì)算相應(yīng)抗體的抗體-抗原親和度函數(shù)值；

（3）進(jìn)行記憶操作，將抗體的函數(shù)評(píng)價(jià)值大于記憶閥值δm的抗體通過記憶算子添加到記憶庫(kù)中，并對(duì)其進(jìn)行抑制算子操作，比較記憶庫(kù)中是否有其相似性抗體，如果有，則刪除其中函數(shù)評(píng)價(jià)值小的抗體；

（4）應(yīng)用小生境適應(yīng)值共享函數(shù)對(duì)抗體的抗體-抗原親和度進(jìn)行調(diào)整；

（5）對(duì)Ab中的抗體按照調(diào)整后的親和度由大至小按降序排列，再將這個(gè)抗體按照克隆擴(kuò)增操作公式進(jìn)行克隆擴(kuò)增，得到規(guī)模為Nc的抗體群Ab′，由初始抗體群中N個(gè)抗體分別對(duì)應(yīng)的N個(gè)子抗體群組成；

（6）對(duì)Ab′中的抗體進(jìn)行抗體變異和抗體重組操作，得到規(guī)模為Nc的新抗體群Abm；

（7）計(jì)算抗體群Abm的每個(gè)抗體親和度；

（8）根據(jù)抗體的親和度，從每個(gè)子抗體群中選出一個(gè)親和度最高的抗體組成抗體群Abx，注意是從每個(gè)子抗體群中選出一個(gè)最高的，而不是在所有抗體中進(jìn)行選擇；

（9）隨機(jī)產(chǎn)生規(guī)模為Nr的抗體群Abr，選出親和度最高的Ns個(gè)抗體組成抗體群Abs；

（10）用Abs代替Abx中親和度最低的Ns個(gè)抗體，形成規(guī)模為N的抗體群Ab；

（11）判斷是否滿足終止條件，不滿足則轉(zhuǎn)至步驟（2）繼續(xù)執(zhí)行，滿足則結(jié)束計(jì)算。記憶庫(kù)中的抗體即為要搜索的峰值抗體。

基于小生境克隆選擇算法的單機(jī)多航路規(guī)劃的具體實(shí)現(xiàn)見參考文獻(xiàn)[8]。

2.3 協(xié)同變量與協(xié)同函數(shù)

對(duì)于協(xié)同問題，分層的目的是把一個(gè)復(fù)雜的優(yōu)化問題分解為小的可直接優(yōu)化的問題，并且允許分布在各個(gè)無(wú)人機(jī)中進(jìn)行計(jì)算，無(wú)人機(jī)之間不需要太多的通信，同時(shí)考慮了威脅和各個(gè)無(wú)人機(jī)的代價(jià)問題。這樣引出問題的關(guān)鍵：需要決定每架無(wú)人機(jī)之間交流什么樣的信息，才能使整個(gè)無(wú)人機(jī)的編隊(duì)進(jìn)行有效的配合協(xié)同，從而規(guī)劃出對(duì)整個(gè)團(tuán)隊(duì)而言是最優(yōu)的協(xié)同航路。為了實(shí)現(xiàn)會(huì)聚目的，系統(tǒng)選擇一個(gè)估計(jì)的會(huì)聚時(shí)ETA（Estimated Time of Arrival）來(lái)對(duì)每架無(wú)人機(jī)的航路進(jìn)行協(xié)同[9]。

假設(shè)飛機(jī)的速度v∈[vmin，vmax]，則對(duì)于某架飛機(jī)i航路規(guī)劃層規(guī)劃得到的某條航路Lj，其預(yù)計(jì)到達(dá)目標(biāo)的時(shí)間為Tj∈[Lj/vmax，Lj/vmin]。對(duì)于某架飛機(jī)i的Num條航路，其預(yù)計(jì)到達(dá)目標(biāo)的時(shí)間則是Num個(gè)時(shí)間范圍的并集Si。

對(duì)于N架飛機(jī)組成的編隊(duì)，則有一個(gè)時(shí)間交集S=S1∩S2∩…∩SN。如果S不為空集，假設(shè)Ta∈S，則每架飛機(jī)都存在對(duì)應(yīng)于到達(dá)時(shí)間為Ta的航路，因此每架飛機(jī)選擇此航路飛行，則可滿足同時(shí)到達(dá)要求，這里Ta就為協(xié)同變量。

由于時(shí)間交集S是一個(gè)集合，那么怎樣來(lái)選取其中一個(gè)元素作為協(xié)同變量的值呢？這里，通過構(gòu)建一個(gè)協(xié)同函數(shù)Jxt來(lái)實(shí)現(xiàn)對(duì)協(xié)同變量值的確定。

其中k1、k2是系數(shù)，Jj是在航線規(guī)劃層得到的某條航線的代價(jià)，只與航路有關(guān)。對(duì)于固定的一條航路，代價(jià)Jj是一定的，Jj=kJthreat+（1-k）Jfuel。

這樣每一條航路的代價(jià)Jxt，j都是到達(dá)時(shí)間Tj的函數(shù)。編隊(duì)的總體代價(jià)為：

式中N為飛機(jī)的數(shù)目。

對(duì)于每一條航路，其飛行時(shí)間不同，代價(jià)Jxt也隨著變化，圖3示意了代價(jià)Jxt與協(xié)同變量Ta的關(guān)系。稱Jxt為協(xié)同函數(shù)，因?yàn)樗軌蝮w現(xiàn)協(xié)同變量Ta的變化如何影響飛機(jī)的生存、安全性，即代價(jià)。

圖3 最優(yōu)ETA決策

因此，協(xié)同規(guī)劃層根據(jù)協(xié)同函數(shù)Jxt，來(lái)確定選擇合適的協(xié)同變量Ta，使飛機(jī)的協(xié)同函數(shù)之和最小，還要保證選擇的Ta滿足每架飛機(jī)的威脅和燃料約束。根據(jù)協(xié)同變量Ta，就能為每一架飛機(jī)確定航路，最終得到多機(jī)的協(xié)同航路。

3 仿真驗(yàn)證與分析

設(shè)定任務(wù)需要3架無(wú)人機(jī)協(xié)同來(lái)完成任務(wù)，設(shè)定UAV1的出發(fā)點(diǎn)為（-10，40）、目標(biāo)點(diǎn)為（90，-70），UAV2的出發(fā)點(diǎn)為（20，60）、目標(biāo)點(diǎn)為（120，-60），UAV3的出發(fā)點(diǎn)為（70，70）、目標(biāo)點(diǎn)為（130，-40），設(shè)3架無(wú)人機(jī)的速度范圍均為40-60m/s。通過單機(jī)多航路規(guī)劃算法分別規(guī)劃得到UAV1、UAV2、UAV3的各自三條分散的最優(yōu)及次優(yōu)航路。飛機(jī)編隊(duì)估計(jì)到達(dá)時(shí)間ETA的最優(yōu)決策如圖4所示。協(xié)同時(shí)間ETA取2805s時(shí)，即保證3架無(wú)人機(jī)同時(shí)到達(dá)目標(biāo)點(diǎn)。最終得到的協(xié)同航路如圖5所示。表1為規(guī)劃結(jié)果統(tǒng)計(jì)。

圖4 ETA的最優(yōu)決策圖

圖5 多機(jī)協(xié)同規(guī)劃的結(jié)果

表1 協(xié)同航路信息

4 結(jié)論

根據(jù)多機(jī)協(xié)同航路規(guī)劃問題的特點(diǎn)，將層次分解策略與小生境克隆選擇算法相結(jié)合，提出了一種基于層次分解策略和小生境克隆選擇算法的多機(jī)協(xié)同航路規(guī)劃方法。采用層次分解策略將一個(gè)單一龐大的優(yōu)化問題分解為多個(gè)小的、更具可操作性的優(yōu)化問題。多機(jī)協(xié)同航路規(guī)劃過程被分解到編隊(duì)中的各飛機(jī)間進(jìn)行，讓每一架飛機(jī)根據(jù)任務(wù)要求采用小生境克隆選擇算法自主地計(jì)算自己的最優(yōu)飛行航路和備選的次優(yōu)航路，最終通過協(xié)同變量和協(xié)同函數(shù)，確定編隊(duì)的協(xié)同航路，解決復(fù)雜戰(zhàn)場(chǎng)環(huán)境下多機(jī)協(xié)同航路規(guī)劃問題，為復(fù)雜環(huán)境下的協(xié)同航路規(guī)劃問題求解提供一種新的有效方法。

【參考文獻(xiàn)】

[1]葉媛媛.多UCAV協(xié)同任務(wù)規(guī)劃方法研究[J].長(zhǎng)沙：國(guó)防科學(xué)技術(shù)大學(xué)，2005.

[2]Dario Bauso， Laura Giarre and Raffaele Pesenti. Multiple UAV Cooperative Path Planning via Neuro-Dynamic Programming[J]. 43rd IEEE Conference on Decision and Control.2004：1087-1092.

[3]Timothy W. McLain ，Randal W. Beard. Coordination Variables， Coordination Functions， and Cooperative Timing Missions[J]. Journal of Guidance，Control and Dynamics. 2005. Vol. 28， No. 1：150-161.

[4]R.J.Szczerba， P.Galkowski， I.S.Glickstein. Robust Algorithm for Real-time Route Planning[J]. IEEE Transactions on Aerospace and Electronic System. 2000，36（3）：869-878.

[5]鄭昌文.飛行器航跡規(guī)劃方法研究[D].華中科技大學(xué)，2003：84-90.

[6]Leandro N de Castro，Jonathan Tinunis. Artifieial Immune Systems： a New Computational Intelligence Approach[M]. British：SPringerPress. 2002：77-88.

[7]王曉蘭，李恒杰.多模態(tài)函數(shù)優(yōu)化的小生境克隆選擇算法[J].甘肅科學(xué)學(xué)報(bào)，2006，18（3）：64-69.

[8]葉文，朱明，李海軍，鞠傳文.基于小生境克隆選擇算法的單UCAV多航路規(guī)劃[C]//2010中國(guó)制導(dǎo)、導(dǎo)航與控制學(xué)術(shù)會(huì)議，2010，10：1062-1069.

[責(zé)任編輯：湯靜]

單機(jī)多航路規(guī)劃算法的實(shí)現(xiàn)流程為：

（1）根據(jù)編碼，應(yīng)用隨機(jī)數(shù)函數(shù)隨機(jī)產(chǎn)生群體的初始抗體Ab；

（2）針對(duì)每一抗體，形成相應(yīng)的航路，并計(jì)算相應(yīng)抗體的抗體-抗原親和度函數(shù)值；

（3）進(jìn)行記憶操作，將抗體的函數(shù)評(píng)價(jià)值大于記憶閥值δm的抗體通過記憶算子添加到記憶庫(kù)中，并對(duì)其進(jìn)行抑制算子操作，比較記憶庫(kù)中是否有其相似性抗體，如果有，則刪除其中函數(shù)評(píng)價(jià)值小的抗體；

（4）應(yīng)用小生境適應(yīng)值共享函數(shù)對(duì)抗體的抗體-抗原親和度進(jìn)行調(diào)整；

（5）對(duì)Ab中的抗體按照調(diào)整后的親和度由大至小按降序排列，再將這個(gè)抗體按照克隆擴(kuò)增操作公式進(jìn)行克隆擴(kuò)增，得到規(guī)模為Nc的抗體群Ab′，由初始抗體群中N個(gè)抗體分別對(duì)應(yīng)的N個(gè)子抗體群組成；

（6）對(duì)Ab′中的抗體進(jìn)行抗體變異和抗體重組操作，得到規(guī)模為Nc的新抗體群Abm；

（7）計(jì)算抗體群Abm的每個(gè)抗體親和度；

（8）根據(jù)抗體的親和度，從每個(gè)子抗體群中選出一個(gè)親和度最高的抗體組成抗體群Abx，注意是從每個(gè)子抗體群中選出一個(gè)最高的，而不是在所有抗體中進(jìn)行選擇；

（9）隨機(jī)產(chǎn)生規(guī)模為Nr的抗體群Abr，選出親和度最高的Ns個(gè)抗體組成抗體群Abs；

（10）用Abs代替Abx中親和度最低的Ns個(gè)抗體，形成規(guī)模為N的抗體群Ab；

（11）判斷是否滿足終止條件，不滿足則轉(zhuǎn)至步驟（2）繼續(xù)執(zhí)行，滿足則結(jié)束計(jì)算。記憶庫(kù)中的抗體即為要搜索的峰值抗體。

基于小生境克隆選擇算法的單機(jī)多航路規(guī)劃的具體實(shí)現(xiàn)見參考文獻(xiàn)[8]。

2.3 協(xié)同變量與協(xié)同函數(shù)

對(duì)于協(xié)同問題，分層的目的是把一個(gè)復(fù)雜的優(yōu)化問題分解為小的可直接優(yōu)化的問題，并且允許分布在各個(gè)無(wú)人機(jī)中進(jìn)行計(jì)算，無(wú)人機(jī)之間不需要太多的通信，同時(shí)考慮了威脅和各個(gè)無(wú)人機(jī)的代價(jià)問題。這樣引出問題的關(guān)鍵：需要決定每架無(wú)人機(jī)之間交流什么樣的信息，才能使整個(gè)無(wú)人機(jī)的編隊(duì)進(jìn)行有效的配合協(xié)同，從而規(guī)劃出對(duì)整個(gè)團(tuán)隊(duì)而言是最優(yōu)的協(xié)同航路。為了實(shí)現(xiàn)會(huì)聚目的，系統(tǒng)選擇一個(gè)估計(jì)的會(huì)聚時(shí)ETA（Estimated Time of Arrival）來(lái)對(duì)每架無(wú)人機(jī)的航路進(jìn)行協(xié)同[9]。

假設(shè)飛機(jī)的速度v∈[vmin，vmax]，則對(duì)于某架飛機(jī)i航路規(guī)劃層規(guī)劃得到的某條航路Lj，其預(yù)計(jì)到達(dá)目標(biāo)的時(shí)間為Tj∈[Lj/vmax，Lj/vmin]。對(duì)于某架飛機(jī)i的Num條航路，其預(yù)計(jì)到達(dá)目標(biāo)的時(shí)間則是Num個(gè)時(shí)間范圍的并集Si。

對(duì)于N架飛機(jī)組成的編隊(duì)，則有一個(gè)時(shí)間交集S=S1∩S2∩…∩SN。如果S不為空集，假設(shè)Ta∈S，則每架飛機(jī)都存在對(duì)應(yīng)于到達(dá)時(shí)間為Ta的航路，因此每架飛機(jī)選擇此航路飛行，則可滿足同時(shí)到達(dá)要求，這里Ta就為協(xié)同變量。

由于時(shí)間交集S是一個(gè)集合，那么怎樣來(lái)選取其中一個(gè)元素作為協(xié)同變量的值呢？這里，通過構(gòu)建一個(gè)協(xié)同函數(shù)Jxt來(lái)實(shí)現(xiàn)對(duì)協(xié)同變量值的確定。

其中k1、k2是系數(shù)，Jj是在航線規(guī)劃層得到的某條航線的代價(jià)，只與航路有關(guān)。對(duì)于固定的一條航路，代價(jià)Jj是一定的，Jj=kJthreat+（1-k）Jfuel。

這樣每一條航路的代價(jià)Jxt，j都是到達(dá)時(shí)間Tj的函數(shù)。編隊(duì)的總體代價(jià)為：

式中N為飛機(jī)的數(shù)目。

對(duì)于每一條航路，其飛行時(shí)間不同，代價(jià)Jxt也隨著變化，圖3示意了代價(jià)Jxt與協(xié)同變量Ta的關(guān)系。稱Jxt為協(xié)同函數(shù)，因?yàn)樗軌蝮w現(xiàn)協(xié)同變量Ta的變化如何影響飛機(jī)的生存、安全性，即代價(jià)。

圖3 最優(yōu)ETA決策

因此，協(xié)同規(guī)劃層根據(jù)協(xié)同函數(shù)Jxt，來(lái)確定選擇合適的協(xié)同變量Ta，使飛機(jī)的協(xié)同函數(shù)之和最小，還要保證選擇的Ta滿足每架飛機(jī)的威脅和燃料約束。根據(jù)協(xié)同變量Ta，就能為每一架飛機(jī)確定航路，最終得到多機(jī)的協(xié)同航路。

3 仿真驗(yàn)證與分析

設(shè)定任務(wù)需要3架無(wú)人機(jī)協(xié)同來(lái)完成任務(wù)，設(shè)定UAV1的出發(fā)點(diǎn)為（-10，40）、目標(biāo)點(diǎn)為（90，-70），UAV2的出發(fā)點(diǎn)為（20，60）、目標(biāo)點(diǎn)為（120，-60），UAV3的出發(fā)點(diǎn)為（70，70）、目標(biāo)點(diǎn)為（130，-40），設(shè)3架無(wú)人機(jī)的速度范圍均為40-60m/s。通過單機(jī)多航路規(guī)劃算法分別規(guī)劃得到UAV1、UAV2、UAV3的各自三條分散的最優(yōu)及次優(yōu)航路。飛機(jī)編隊(duì)估計(jì)到達(dá)時(shí)間ETA的最優(yōu)決策如圖4所示。協(xié)同時(shí)間ETA取2805s時(shí)，即保證3架無(wú)人機(jī)同時(shí)到達(dá)目標(biāo)點(diǎn)。最終得到的協(xié)同航路如圖5所示。表1為規(guī)劃結(jié)果統(tǒng)計(jì)。

圖4 ETA的最優(yōu)決策圖

圖5 多機(jī)協(xié)同規(guī)劃的結(jié)果

表1 協(xié)同航路信息

4 結(jié)論

根據(jù)多機(jī)協(xié)同航路規(guī)劃問題的特點(diǎn)，將層次分解策略與小生境克隆選擇算法相結(jié)合，提出了一種基于層次分解策略和小生境克隆選擇算法的多機(jī)協(xié)同航路規(guī)劃方法。采用層次分解策略將一個(gè)單一龐大的優(yōu)化問題分解為多個(gè)小的、更具可操作性的優(yōu)化問題。多機(jī)協(xié)同航路規(guī)劃過程被分解到編隊(duì)中的各飛機(jī)間進(jìn)行，讓每一架飛機(jī)根據(jù)任務(wù)要求采用小生境克隆選擇算法自主地計(jì)算自己的最優(yōu)飛行航路和備選的次優(yōu)航路，最終通過協(xié)同變量和協(xié)同函數(shù)，確定編隊(duì)的協(xié)同航路，解決復(fù)雜戰(zhàn)場(chǎng)環(huán)境下多機(jī)協(xié)同航路規(guī)劃問題，為復(fù)雜環(huán)境下的協(xié)同航路規(guī)劃問題求解提供一種新的有效方法。

【參考文獻(xiàn)】

[1]葉媛媛.多UCAV協(xié)同任務(wù)規(guī)劃方法研究[J].長(zhǎng)沙：國(guó)防科學(xué)技術(shù)大學(xué)，2005.

[2]Dario Bauso， Laura Giarre and Raffaele Pesenti. Multiple UAV Cooperative Path Planning via Neuro-Dynamic Programming[J]. 43rd IEEE Conference on Decision and Control.2004：1087-1092.

[3]Timothy W. McLain ，Randal W. Beard. Coordination Variables， Coordination Functions， and Cooperative Timing Missions[J]. Journal of Guidance，Control and Dynamics. 2005. Vol. 28， No. 1：150-161.

[4]R.J.Szczerba， P.Galkowski， I.S.Glickstein. Robust Algorithm for Real-time Route Planning[J]. IEEE Transactions on Aerospace and Electronic System. 2000，36（3）：869-878.

[5]鄭昌文.飛行器航跡規(guī)劃方法研究[D].華中科技大學(xué)，2003：84-90.

[6]Leandro N de Castro，Jonathan Tinunis. Artifieial Immune Systems： a New Computational Intelligence Approach[M]. British：SPringerPress. 2002：77-88.

[7]王曉蘭，李恒杰.多模態(tài)函數(shù)優(yōu)化的小生境克隆選擇算法[J].甘肅科學(xué)學(xué)報(bào)，2006，18（3）：64-69.

[8]葉文，朱明，李海軍，鞠傳文.基于小生境克隆選擇算法的單UCAV多航路規(guī)劃[C]//2010中國(guó)制導(dǎo)、導(dǎo)航與控制學(xué)術(shù)會(huì)議，2010，10：1062-1069.

[責(zé)任編輯：湯靜]