多機(jī)協(xié)同航路規(guī)劃的數(shù)學(xué)模型與求解方法

王記豐　李崢　葉文

【摘 要】應(yīng)用層次分解方法和小生境克隆選擇算法相結(jié)合，通過引入?yún)f(xié)同變量和協(xié)同函數(shù)，解決了多機(jī)協(xié)同規(guī)劃航路的時(shí)間協(xié)同問題。

【關(guān)鍵詞】多機(jī)協(xié)同；航路規(guī)劃；層次分解策略

無人機(jī)作戰(zhàn)的主要模式是多機(jī)協(xié)同作戰(zhàn)，而多機(jī)協(xié)同航路規(guī)劃是提高無人機(jī)作戰(zhàn)效能的有效手段。多機(jī)協(xié)同航路規(guī)劃就是在考慮無人機(jī)機(jī)動(dòng)能力和導(dǎo)航精度限制的條件下，為每架無人機(jī)規(guī)劃出飛行航路，使其滿足團(tuán)隊(duì)協(xié)同的要求，并且整體具有最大的生存概率。

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

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

多機(jī)協(xié)同航路規(guī)劃是在盡量提高無人機(jī)的生存概率的條件下，為每架無人機(jī)規(guī)劃出一條航路，并且滿足一定的協(xié)同要求[1-2]。最終每架無人機(jī)規(guī)劃得的航路，對(duì)無人機(jī)自身來說不一定是最優(yōu)的，然而針對(duì)無人機(jī)編隊(duì)來說，卻一定是最優(yōu)或接近最優(yōu)的。

假設(shè)多架無人機(jī)對(duì)一個(gè)目標(biāo)進(jìn)行攻擊時(shí)，要求多架無人機(jī)從不同的起飛點(diǎn)同時(shí)到達(dá)預(yù)先指定的目標(biāo)位置，進(jìn)行協(xié)同攻擊，提高攻擊的有效性。戰(zhàn)場(chǎng)態(tài)勢(shì)如圖1所示，要求兩架無人機(jī)同時(shí)到達(dá)目標(biāo)點(diǎn)對(duì)目標(biāo)進(jìn)行攻擊。根據(jù)同時(shí)達(dá)到要求，預(yù)先規(guī)劃出的協(xié)同航路（如圖中虛線所示），滿足同時(shí)到達(dá)要求，即具有相同的估計(jì)到達(dá)時(shí)間（ETA）。

在無人機(jī)根據(jù)預(yù)先規(guī)劃航路向目標(biāo)飛行過程中，突然出現(xiàn)預(yù)先沒有探測(cè)到的新威脅，并且新威脅還影響無人機(jī)2的安全，無人機(jī)2可能被擊毀。此時(shí)，就需要重新規(guī)劃航路，并且需要重新計(jì)算一個(gè)編隊(duì)協(xié)同飛行時(shí)間ETA。根據(jù)新的ETA，新生成的航路如圖中實(shí)現(xiàn)所示。顯然對(duì)于無人機(jī)1來說新航路不是最優(yōu)的，但對(duì)于整個(gè)無人機(jī)編隊(duì)來說，新航路是最安全，并且能夠同時(shí)到達(dá)目標(biāo)點(diǎn)。

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

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

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

多機(jī)協(xié)同航路規(guī)劃還需要滿足一定的約束條件，包括單機(jī)的物理性能和單架無人機(jī)的任務(wù)需求，而且還要滿足多機(jī)同時(shí)達(dá)到目標(biāo)約束和無人機(jī)之間最小安全距離約束等。具體約束如下：

禁飛區(qū)：無人機(jī)飛行航路必須避開政治人文性禁/避飛區(qū)，以及極度惡劣的天氣區(qū)域。

最大作戰(zhàn)半徑：無人機(jī)受所攜帶燃料量的限制，其規(guī)劃的飛行航路不能超過其最大飛行航程。

最小轉(zhuǎn)彎半徑：無人機(jī)受飛機(jī)性能限制，其規(guī)劃的飛行航路轉(zhuǎn)彎半徑不能小于無人機(jī)的最小轉(zhuǎn)彎半徑

空域協(xié)同：規(guī)劃得到的協(xié)同航路要保證無人機(jī)之間不發(fā)生碰撞，機(jī)間距離大于規(guī)定的最小距離。

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

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

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

空域協(xié)同和時(shí)域協(xié)同是多機(jī)協(xié)同航路規(guī)劃所要解決的重點(diǎn)問題。其中，時(shí)域協(xié)同主要是確保飛機(jī)按照一定的時(shí)間要求到達(dá)各自的目標(biāo)點(diǎn)。時(shí)域協(xié)同一般分為以下三種情況[3]：

（1）同時(shí)到達(dá)：編隊(duì)的所有飛機(jī)在相同的時(shí)間點(diǎn)同時(shí)到達(dá)各自所要攻擊目標(biāo)的攻擊點(diǎn)，對(duì)同一目標(biāo)或者不同目標(biāo)實(shí)施同時(shí)攻擊。

（2）嚴(yán)格依次順序到達(dá)：編隊(duì)的所有飛機(jī)按照一定的先后順序依次到達(dá)所要攻擊目標(biāo)的攻擊點(diǎn)，并且各個(gè)飛機(jī)到達(dá)的時(shí)間節(jié)點(diǎn)有嚴(yán)格精確的要求，即一架飛機(jī)到達(dá)攻擊點(diǎn)后，t時(shí)間后下一架飛機(jī)必須到達(dá)攻擊點(diǎn)，不能提前也不能推遲。

（3）松散依次順序到達(dá)：編隊(duì)的所有飛機(jī)按照一定的先后順序依次到達(dá)所要攻擊目標(biāo)的攻擊點(diǎn)，并且各個(gè)飛機(jī)到達(dá)攻擊點(diǎn)之間的時(shí)間間隔有范圍要求，即一架飛機(jī)到達(dá)攻擊點(diǎn)后，下一架飛機(jī)必須在[tmin，tmax]時(shí)間范圍內(nèi)到達(dá)攻擊點(diǎn)，不能超出這個(gè)可接受的范圍。

目前，要求同時(shí)到達(dá)是多機(jī)協(xié)同航路規(guī)劃中最常見的情況。一般，采用層次分解的思想來進(jìn)行同時(shí)到達(dá)情況的求解，即分解為航路規(guī)劃層、協(xié)同規(guī)劃層、航路平滑層三個(gè)層次，如圖2所示。

航路規(guī)劃層首先為每架飛機(jī)規(guī)劃出Num條備選航路，這樣如果有N架無人機(jī)，則就有N×Num條航路，形成備選航路集合；協(xié)同規(guī)劃層根據(jù)協(xié)同函數(shù)和協(xié)同變量，為每架飛機(jī)從其Num條備選航路中選擇一條合適的航路，組成協(xié)同航路，使得選出的航路既能滿足編隊(duì)同時(shí)到達(dá)的要求，又確保編隊(duì)航路的整體代價(jià)最?。ù涡。?；航路平滑層主要是對(duì)航路進(jìn)行平滑處理，使其滿足最小轉(zhuǎn)彎半徑約束，并不改變其航程，確保同時(shí)（依次）到達(dá)目標(biāo)。

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

航路規(guī)劃層要求能夠獨(dú)立規(guī)劃出各自飛機(jī)的Num條備選航路，并且這些備選航路應(yīng)該為全局最優(yōu)航路、全局次優(yōu)航路或者有意義的局部最優(yōu)航路，以便在協(xié)同規(guī)劃層根據(jù)不同需要決定選擇合適的飛行航路[4-5]。

在層次分解策略下，首先采用小生境克隆選擇算法為每架無人機(jī)生成了Num條備選航路[6-7]，下一步就是要根據(jù)航路的協(xié)同要求，在每架無人機(jī)的Num條備選航路中選擇一條航路。那么各架無人機(jī)之間通過什么樣的信息交流，才能使選擇出來的航路滿足多機(jī)之間的協(xié)同要求，并且盡量使規(guī)劃得到的協(xié)同航路對(duì)整個(gè)團(tuán)隊(duì)而言是最優(yōu)的。因此，為了實(shí)現(xiàn)同時(shí)到達(dá)的時(shí)間協(xié)同目的，選擇航路的估計(jì)到達(dá)時(shí)間（Estimated Time of Arrival， ETA）來對(duì)每架無人機(jī)的航路進(jìn)行協(xié)同[9]。

假設(shè)v∈[vmin，vmax]為飛機(jī)的速度區(qū)間，那么對(duì)于飛機(jī)i規(guī)劃得到的航路Li，則其預(yù)計(jì)到達(dá)時(shí)間為Ti∈[Li/vmax，Li/vmin]。這樣，對(duì)于飛機(jī)i的Num條備選航路，其預(yù)計(jì)到達(dá)時(shí)間則是Num個(gè)時(shí)間范圍的并集Si。

假設(shè)編隊(duì)由N架飛機(jī)組成，若時(shí)間交集S=S1∩S2∩…∩SN，如果S不為空集，即存在Ta∈S，則說明對(duì)于估計(jì)到達(dá)時(shí)間Ta來說，在每架飛機(jī)的Num條備選航路中都能找到一條估計(jì)到達(dá)時(shí)間為的Ta航路。因此，如果每架飛機(jī)都選擇估計(jì)到達(dá)時(shí)間為Ta的航路飛行，那么飛機(jī)編隊(duì)就能滿足同時(shí)到達(dá)要求，這里的Ta就稱為協(xié)同變量。

由于時(shí)間交集S是一個(gè)集合，而不是一個(gè)數(shù)，因此估計(jì)到達(dá)時(shí)間Ta不唯一，即可能存在多條可選擇的航路，那么怎樣選值來確定協(xié)同變量的值呢？這里，通過構(gòu)建協(xié)同函數(shù)Jxt來確定對(duì)協(xié)同變量值。

其中k1、k2為系數(shù)，Ji為具體航路的代價(jià)，對(duì)于確定的一條航路，Ji是一定的，Ji=kJthreat+（1-k）Jfuel。因此，對(duì)于每一條航路的Jxt.i都是估計(jì)到達(dá)時(shí)間Ti的函數(shù)。無人機(jī)編隊(duì)的總體代價(jià)為：

其中N是飛機(jī)的數(shù)目。

根據(jù)代價(jià)函數(shù)，飛行時(shí)間不同，每一條航路的代價(jià)Jxt也隨著變化，代價(jià)Jxt與協(xié)同變量Ta的關(guān)系如圖3所示。因?yàn)樗捎谕ㄟ^Jxt能夠表現(xiàn)協(xié)同變量Ta的變化對(duì)飛機(jī)的生存、安全性的影響，因此，將Jxt稱為協(xié)同函數(shù)。

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

在協(xié)同規(guī)劃層中，首先建立協(xié)同函數(shù)Jxt，根據(jù)飛機(jī)的協(xié)同函數(shù)之和最小的原則，選擇確定合適的協(xié)同變量Ta。然后根據(jù)選定的協(xié)同變量Ta，在每架無人機(jī)Num條備選航路中選擇相對(duì)應(yīng)的一條航路，最終得到多機(jī)的協(xié)同航路。

3 結(jié)論

將層次分解策略與小生境克隆選擇算法相結(jié)合，針對(duì)多機(jī)協(xié)同航路規(guī)劃問題的實(shí)質(zhì)，提出了一種基于層次分解策略和小生境克隆選擇算法的多機(jī)協(xié)同航路規(guī)劃方法，有效解決了多機(jī)協(xié)同航路規(guī)劃問題。

【參考文獻(xiàn)】

[1]葉媛媛.多UCAV協(xié)同任務(wù)規(guī)劃方法研究[博士學(xué)位論文]長沙：國防科學(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. IEEE Transactions on Aerospace and Electronic System.2000.36（3）：869-878.

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

[6]韓昕鋒，葉文，陳海生.多UCAV協(xié)同航路規(guī)劃算法[J].海軍航空工程學(xué)院學(xué)報(bào).2010.16（5）：10-13.

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

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

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

[責(zé)任編輯：朱麗娜]