多無(wú)人機(jī)協(xié)同任務(wù)規(guī)劃研究

楊晨 張少卿 孟光磊

無(wú)人機(jī)作戰(zhàn)相比于有人機(jī)具有:體積小、重量輕、續(xù)航時(shí)間長(zhǎng)、載荷能力強(qiáng)、生存能力強(qiáng)、費(fèi)用低廉、自主控制能力強(qiáng)、無(wú)人員傷亡、可在高風(fēng)險(xiǎn)空域飛行等優(yōu)勢(shì),且在第四次中東戰(zhàn)爭(zhēng)、海灣戰(zhàn)爭(zhēng)、科索沃戰(zhàn)爭(zhēng)中和后來(lái)的伊拉克戰(zhàn)爭(zhēng)中無(wú)人機(jī)完成了中低空偵察、長(zhǎng)時(shí)間戰(zhàn)場(chǎng)監(jiān)視、電子對(duì)抗、戰(zhàn)況評(píng)估、目標(biāo)定位和收集氣象資料等任務(wù)[1?2].由于軍事戰(zhàn)場(chǎng)收益是面向全局,單架無(wú)人機(jī)所能發(fā)揮的作用效能十分有限,由此提出多機(jī)協(xié)同作戰(zhàn),同時(shí)完成不同任務(wù),壓制敵軍,贏得戰(zhàn)斗.

2016年,美國(guó)針對(duì)無(wú)人機(jī)不同功能、尺寸及作戰(zhàn)需求,研究與無(wú)人機(jī)相關(guān)的各種協(xié)同作戰(zhàn)方式,在以“忠誠(chéng)僚機(jī)”為代表的有/無(wú)人協(xié)同和小精靈項(xiàng)目為代表的集群協(xié)同作戰(zhàn)方面進(jìn)行了大量探索[3].2018～2022年,美國(guó)計(jì)劃繼續(xù)致力于研究無(wú)人機(jī)作為“忠誠(chéng)的僚機(jī)”的有/無(wú)人機(jī)混編協(xié)同作戰(zhàn)系統(tǒng)的研究,且計(jì)劃將無(wú)人機(jī)編隊(duì)分配給前線F-35、F-22和最新轟炸機(jī)“B-21”[4].可見(jiàn),無(wú)人機(jī)集群協(xié)同作戰(zhàn)必將是無(wú)人機(jī)未來(lái)發(fā)展的必然趨勢(shì).文獻(xiàn)[5]分析了現(xiàn)階段智能無(wú)人機(jī)集群發(fā)展的四大關(guān)鍵技術(shù):環(huán)境感知與認(rèn)識(shí)、多機(jī)協(xié)同任務(wù)規(guī)劃、信息交互與自主控制、人機(jī)智能融合與自適應(yīng)學(xué)習(xí)技術(shù).在集群技術(shù)中,多機(jī)協(xié)同任務(wù)規(guī)劃技術(shù)尤為重要,既要使機(jī)群的安全指數(shù)最大化,同時(shí)要求在最短的時(shí)間內(nèi)完成情報(bào)、監(jiān)視、偵察以及多目標(biāo)攻擊等任務(wù).合理、高效的協(xié)同任務(wù)規(guī)劃方案能極大提高任務(wù)執(zhí)行成功率和效率、降低風(fēng)險(xiǎn)和成本是任務(wù)執(zhí)行的基礎(chǔ)[6].

目前,各國(guó)研究者們對(duì)多無(wú)人機(jī)協(xié)同任務(wù)規(guī)劃技術(shù)還在大力研究中,部分問(wèn)題已得到有效的解決方法.如解決多目標(biāo)優(yōu)化問(wèn)題的傳統(tǒng)數(shù)學(xué)規(guī)劃法、基于市場(chǎng)機(jī)制的方法、基于圖論的方法、和現(xiàn)代智能優(yōu)化算法如蟻群算法、遺傳算法、禁忌搜索算法等;但現(xiàn)階段多數(shù)算法在時(shí)間上、全局最優(yōu)上、在大規(guī)模復(fù)雜的優(yōu)化組合問(wèn)題上,仍未達(dá)到令人滿(mǎn)意的效果.以及飛行過(guò)程中威脅源突現(xiàn),單機(jī)需具備在線航跡重規(guī)劃的自治能力或在線多機(jī)航跡重規(guī)劃的協(xié)調(diào)能力依舊是我們的難點(diǎn)問(wèn)題.

1 多無(wú)人機(jī)任務(wù)規(guī)劃系統(tǒng)

1.1 任務(wù)規(guī)劃的內(nèi)容、目的及原則

1.1.1 內(nèi)容與目的

對(duì)多無(wú)人機(jī)協(xié)同任務(wù)規(guī)劃的研究是基于對(duì)單無(wú)人機(jī)的發(fā)展而來(lái),所以依舊具備單無(wú)人機(jī)任務(wù)的規(guī)劃特性:1)明確任務(wù),包括任務(wù)類(lèi)型、任務(wù)區(qū)域、完成時(shí)間等;2)戰(zhàn)場(chǎng)狀態(tài)分析,包括環(huán)境威脅、目標(biāo)威脅、效能評(píng)估、態(tài)勢(shì)預(yù)測(cè);3)任務(wù)規(guī)劃;根據(jù)既定任務(wù)設(shè)定約束條件并結(jié)合評(píng)估數(shù)據(jù),計(jì)算無(wú)人機(jī)團(tuán)隊(duì)以最小的代價(jià)完成最大收益的分配方案和飛行路線.此外,多無(wú)人機(jī)本質(zhì)上不同于單機(jī)在于具有協(xié)同、協(xié)調(diào)能力[7],規(guī)劃時(shí)需考慮時(shí)間上的“協(xié)同”、空間上的“協(xié)調(diào)”,為無(wú)人機(jī)團(tuán)隊(duì)建立“互幫互助”的關(guān)系,所以規(guī)劃上的復(fù)雜度和計(jì)算量都大大增加[8?9].

1.1.2 規(guī)劃原則

1)基本原則

多機(jī)任務(wù)規(guī)劃的原則不僅要考慮各單機(jī)的物理性能和任務(wù)需求,還需考慮機(jī)群間協(xié)同關(guān)系和協(xié)調(diào)關(guān)系.從功能上任務(wù)規(guī)劃由任務(wù)分配和航跡規(guī)劃兩部分組成,在任務(wù)分配方面需具備以下3個(gè)基本原則[10?12]:委派與無(wú)人機(jī)性能相適合的目標(biāo);多無(wú)人機(jī)共同執(zhí)行任務(wù)時(shí),在時(shí)間上協(xié)調(diào);不同任務(wù)要求下,規(guī)劃全局最優(yōu)的多目標(biāo)分配方案.航跡規(guī)劃也具備3個(gè)基本原則[11?14]:避開(kāi)航路威脅,氣象威脅、地形威脅、編隊(duì)碰撞、威脅源(雷達(dá)探測(cè)威脅、電磁干擾威脅、防空火炮威脅等);滿(mǎn)足飛行約束條件,最小航跡段長(zhǎng)度、最大爬升/俯沖角、最大轉(zhuǎn)彎角、最大航跡長(zhǎng)度、最低飛行高度等自身特性;飛行路徑最優(yōu)化,路徑最優(yōu)化的選擇不但是選擇出飛行的路徑最短,更得滿(mǎn)足所規(guī)劃出的航路必須能夠經(jīng)過(guò)偵查區(qū)域或打擊目標(biāo)所在區(qū)域,且盡可能以較低概率被敵方雷達(dá)發(fā)現(xiàn),最好結(jié)果是不被發(fā)現(xiàn),這對(duì)規(guī)劃航路的質(zhì)量有較高的要求.

2)優(yōu)先級(jí)

多無(wú)人機(jī)任務(wù)規(guī)劃過(guò)程中會(huì)出現(xiàn)多任務(wù)多目標(biāo)情況,軍事指揮員基于不同環(huán)境、不同作戰(zhàn)方式下達(dá)不同的作戰(zhàn)要求,這不僅需要任務(wù)規(guī)劃的結(jié)果是飛行的航路無(wú)威脅、滿(mǎn)足飛機(jī)性能約束以及飛行路徑最優(yōu)等各類(lèi)基本條件,還需任務(wù)規(guī)劃系統(tǒng)能夠以任務(wù)的優(yōu)先級(jí)進(jìn)行選取達(dá)到上層下達(dá)的作戰(zhàn)要求[12,15?16].由此任務(wù)規(guī)劃應(yīng)具備這4種原則:

①優(yōu)先選擇價(jià)值高的目標(biāo);

②優(yōu)先選擇距離近的目標(biāo);

③優(yōu)先執(zhí)行任務(wù)時(shí)間最短;

④選取無(wú)人機(jī)數(shù)量最少;

這4種任務(wù)規(guī)劃原則的優(yōu)先級(jí)不等.在空對(duì)空、空對(duì)地等許多情況下,目標(biāo)價(jià)值常常是作為任務(wù)規(guī)劃的關(guān)鍵參考因素,建立選取價(jià)值高的目標(biāo)為最高優(yōu)先級(jí)的原則,保證了無(wú)人機(jī)的安全且得到的收益最大.但在完成一些特殊任務(wù)時(shí),目標(biāo)價(jià)值對(duì)規(guī)劃要求來(lái)說(shuō)優(yōu)先級(jí)并不是最高的(指不是最重要的)如在完成偵察、監(jiān)視、探測(cè)類(lèi)任務(wù)時(shí),由于無(wú)人機(jī)數(shù)量越多越容易暴露,針對(duì)這一類(lèi)任務(wù)應(yīng)當(dāng)考慮用最少數(shù)量的無(wú)人機(jī)協(xié)同完成最多、最復(fù)雜的任務(wù),由此選取最少無(wú)人機(jī)數(shù)量原則的優(yōu)先級(jí)最高.

1.2 任務(wù)規(guī)劃系統(tǒng)的功能模塊

最早的無(wú)人機(jī)任務(wù)規(guī)劃系統(tǒng)[15],是由控制站完成任務(wù)規(guī)劃,再將任務(wù)命令下達(dá)給無(wú)人機(jī),無(wú)人機(jī)只需完成對(duì)航跡的規(guī)劃,如:文獻(xiàn)[17]基于偵察機(jī)接受偵察戰(zhàn)場(chǎng)狀況的任務(wù)命令,建立了單無(wú)人機(jī)任務(wù)規(guī)劃系統(tǒng),系統(tǒng)只生成具體的飛行軌跡引導(dǎo)飛機(jī)到達(dá)預(yù)定目標(biāo)完成任務(wù),卻沒(méi)考慮在載荷等條件滿(mǎn)足的情況下,單機(jī)任務(wù)規(guī)劃系統(tǒng)需建立對(duì)目標(biāo)的時(shí)序排列;文獻(xiàn)[18]單機(jī)任務(wù)規(guī)劃系統(tǒng)中建立比較全面、基本的系統(tǒng)模塊包括任務(wù)分配、航跡規(guī)劃、控制模塊、數(shù)據(jù)管理模塊等,但系統(tǒng)的組成還是過(guò)于簡(jiǎn)單;文獻(xiàn)[19]的規(guī)劃系統(tǒng)中除具有任務(wù)分配模塊外,添加了系統(tǒng)保障模塊,當(dāng)航路戰(zhàn)術(shù)決策裝訂好后發(fā)送到指揮系統(tǒng)內(nèi),在指揮系統(tǒng)接收到的航路戰(zhàn)術(shù)決策的同時(shí)航路戰(zhàn)術(shù)決策上傳到保障系統(tǒng),確保無(wú)人機(jī)出現(xiàn)意外指揮系統(tǒng)失控時(shí),保障系統(tǒng)作為指揮系統(tǒng)繼續(xù)完成任務(wù),且保障系統(tǒng)還存入其他重要信息如:無(wú)人機(jī)所經(jīng)過(guò)地形地貌的地圖信息.單機(jī)任務(wù)規(guī)劃系統(tǒng)是不能滿(mǎn)足多機(jī)協(xié)同、協(xié)調(diào)的能力.基于協(xié)同能力的要求,多無(wú)人機(jī)任務(wù)規(guī)劃系統(tǒng)需具備[15]:協(xié)同通信系統(tǒng)、協(xié)同控制系統(tǒng)以及協(xié)同任務(wù)調(diào)配系統(tǒng)等,使各無(wú)人機(jī)可以相互配合,減少威脅,一起行動(dòng),提高效率.文獻(xiàn)[20?21]提出將系統(tǒng)從功能上進(jìn)行層次結(jié)構(gòu)的劃分:決策層和執(zhí)行層;決策層由多機(jī)任務(wù)分配、多機(jī)航跡規(guī)劃、信息協(xié)調(diào)組成,執(zhí)行層則是單機(jī)路徑規(guī)劃,由此完成了從多機(jī)到單機(jī)、從任務(wù)分配到航跡規(guī)劃整個(gè)多無(wú)人機(jī)的任務(wù)規(guī)劃.多無(wú)人機(jī)協(xié)同對(duì)控制技術(shù)、系統(tǒng)設(shè)置以及通信技術(shù)等都有很高的要求,研究者們就提出有人機(jī)控制無(wú)人機(jī)的方式完成協(xié)同作戰(zhàn);文獻(xiàn)[22]在有/無(wú)人機(jī)協(xié)同作戰(zhàn)下,提出采用語(yǔ)音控制法,完成協(xié)同控制下包括人機(jī)交互接口、鏈路通信接口、任務(wù)管理和調(diào)度以及實(shí)時(shí)路徑?jīng)Q策和航路規(guī)劃模塊的任務(wù)規(guī)劃系統(tǒng);文獻(xiàn)[23]在文獻(xiàn)[19]的基礎(chǔ)上設(shè)置了評(píng)估模塊、目標(biāo)分析模塊,同時(shí)還將航跡規(guī)劃分為了預(yù)規(guī)劃和航路規(guī)劃,實(shí)現(xiàn)了在飛行過(guò)程中對(duì)目標(biāo)實(shí)時(shí)分析、判定威脅,無(wú)人機(jī)自主進(jìn)行在線航跡規(guī)劃,并具有評(píng)估能力,遇危自治,基本完成多無(wú)人機(jī)下的單機(jī)任務(wù)規(guī)劃系統(tǒng)[23](圖1(a));文獻(xiàn)[24]基于對(duì)多UAV協(xié)同偵察任務(wù)決策問(wèn)題繼續(xù)深入,采用從局部到總體的研究思路建立如圖1(b)的多無(wú)人機(jī)任務(wù)規(guī)劃系統(tǒng)[24].

由此分析,多無(wú)人機(jī)任務(wù)規(guī)劃系統(tǒng)需具備以下基本模塊,其組成的基本架構(gòu)如圖2所示.

1)檢測(cè)管理模塊:跟蹤各模塊實(shí)時(shí)狀態(tài)、調(diào)度各模塊信息、控制各模塊發(fā)生沖突;

2)態(tài)勢(shì)/威脅評(píng)估模塊:感知環(huán)境、目標(biāo)等態(tài)勢(shì)信息,建立綜合評(píng)估指標(biāo)體系圖;

3)任務(wù)分配模塊:根據(jù)任務(wù)要求,確定任務(wù)目的,完成任務(wù)(目標(biāo))分配.但由于不同機(jī)型的任務(wù)分配系統(tǒng)需要完成的規(guī)劃不一樣,偵察機(jī)就只需根據(jù)任務(wù)要求,完成支配各個(gè)傳感器對(duì)目標(biāo)、環(huán)境等信息的搜集;對(duì)于“偵察–打擊”為一體的無(wú)人機(jī),不但需要完成偵察任務(wù)還需要對(duì)目標(biāo)評(píng)估,將目標(biāo)進(jìn)行合理安排保證目標(biāo)收益最大化,最后完成目標(biāo)打擊.

4)航跡規(guī)劃模塊:根據(jù)目標(biāo)位置,確定起飛點(diǎn)、作戰(zhàn)點(diǎn)、作戰(zhàn)區(qū)域,完成從起飛點(diǎn)到作戰(zhàn)點(diǎn)的路線規(guī)劃,選取最優(yōu)路線,并做平滑處理滿(mǎn)足飛機(jī)性能約束;

5)方案效能評(píng)估模塊:對(duì)規(guī)劃方案進(jìn)行收益和代價(jià)評(píng)估,供決策者參考;

6)協(xié)調(diào)模塊:解除預(yù)規(guī)劃路徑與新障物、與各UAVS的沖突;

7)內(nèi)部數(shù)據(jù)管理模塊:無(wú)人機(jī)的知識(shí)庫(kù)、數(shù)據(jù)庫(kù),接收、存儲(chǔ)、發(fā)送有關(guān)任務(wù)規(guī)劃的所有信息與數(shù)據(jù),更新任務(wù)規(guī)劃的中間結(jié)果,接受任務(wù)規(guī)劃的最終結(jié)果.

1.3 任務(wù)規(guī)劃系統(tǒng)的控制方式

1.3.1 集中式控制系統(tǒng)

集中式控制系統(tǒng)[20,25?27](圖3(a))由一個(gè)中央處理器控制全局,可以是由長(zhǎng)機(jī)或者地面控制中心,這樣的好處在于使全局收益最高.但是,計(jì)算量大、計(jì)算時(shí)間長(zhǎng)且對(duì)服務(wù)器性能要求也高,更重要的是無(wú)人機(jī)在突發(fā)狀況下不具備自治能力,就大大降低了無(wú)人機(jī)的安全系數(shù).

1.3.2 完全分布式控制系統(tǒng)

完全分布式控制系統(tǒng)[17,23,25?26,28](圖3(b))與集中式完全相反,各無(wú)人機(jī)地位平等,以相互協(xié)商、相互協(xié)調(diào)的方式完成任務(wù)分配.每架無(wú)人機(jī)從自身利益出發(fā),容易陷入局部最優(yōu),且當(dāng)無(wú)人機(jī)對(duì)任務(wù)都同時(shí)具有相同收益時(shí),便無(wú)法抉擇,相互之間產(chǎn)生競(jìng)爭(zhēng).

1.3.3 部分分布式控制系統(tǒng)

部分分布式控制系統(tǒng)即集散式控制系統(tǒng)[17,28?31](圖3(c)),也稱(chēng)分層次式.結(jié)合集中式和分布式的優(yōu)缺點(diǎn),由長(zhǎng)機(jī)或者地面控制站將任務(wù)分解成小任務(wù)包,分配給無(wú)人機(jī),無(wú)人機(jī)對(duì)小包任務(wù)進(jìn)行規(guī)劃并相互協(xié)調(diào),規(guī)劃完成后將自己的收益、損失等數(shù)據(jù)反饋給長(zhǎng)機(jī)或者地面控制站,從全局收益出發(fā)對(duì)各機(jī)下達(dá)任務(wù)命令.集散式控制方式既消除了集中式計(jì)算量大的問(wèn)題,又大大提高了作戰(zhàn)效率,滿(mǎn)足全局利益最大化且無(wú)人機(jī)還具備自治能力.

1.3.4 基于多智能體分布式控制系統(tǒng)

多智能體系統(tǒng)(Multi-agent system,MAS)是指由不同的單個(gè)智能體(Agent)為完成某一特定任務(wù)組合而成的多智能體系統(tǒng)[32?33].在多無(wú)人機(jī)任務(wù)規(guī)劃系統(tǒng)由規(guī)劃Agent,分配Agent和協(xié)調(diào)Agent等組成(圖3(d)).

由于Agent不但具有能迅速對(duì)環(huán)境進(jìn)行認(rèn)識(shí)、學(xué)習(xí)的能力,對(duì)問(wèn)題進(jìn)行判斷、推理、求解的能力,且還具備很好的協(xié)調(diào)能力、協(xié)作能力,解決與其他Agent的矛盾和沖突,規(guī)劃自身行為,并做出最終決策.而多Agent除了具有單Agent的自主性、交互性、主動(dòng)性、社會(huì)性等基本特性外,由于其動(dòng)態(tài)復(fù)雜,還具有以下特點(diǎn):群體性,多Agent系統(tǒng)是由多個(gè)Agent為了實(shí)現(xiàn)各自的或群體的整體目標(biāo),通過(guò)扮演群體中的角色,并以角色關(guān)系相互連接而構(gòu)成的.一個(gè)Agent可以承擔(dān)多個(gè)角色,也可能由多個(gè)Agent組成的組來(lái)共同承擔(dān)某一個(gè)角色;協(xié)作與協(xié)調(diào),具有不同目標(biāo)的各個(gè)Agent必須相互工作、協(xié)作、協(xié)商來(lái)完成問(wèn)題的求解,從而實(shí)現(xiàn)整體任務(wù).

通過(guò)MAS技術(shù)對(duì)多無(wú)人機(jī)任務(wù)規(guī)劃系統(tǒng)的控制功能進(jìn)行子功能劃分,實(shí)現(xiàn)了智能體間、系統(tǒng)模塊間共同參與、相互協(xié)商的作用,包括:集中式、分布式、分散式和混合式的多Agent系統(tǒng)架構(gòu).但目前國(guó)際上研究的熱點(diǎn)問(wèn)題主要在基于MAS技術(shù)的分布式控制系統(tǒng),不同的是完全分布式任務(wù)規(guī)劃系統(tǒng)[17,32,34]是將各智能體之間的交互關(guān)系平級(jí)化,而基于分層的部分分布式任務(wù)規(guī)劃系統(tǒng)[33,35]是以集中式控制區(qū)和分布式控制區(qū)建立集散式控制方式明確各智能體之間的交互關(guān)系.

1.4 任務(wù)規(guī)劃的基本流程

圖4為多無(wú)人機(jī)任務(wù)規(guī)劃的基本流程,由此流程圖我們將任務(wù)規(guī)劃過(guò)程分為離線預(yù)規(guī)劃和在線實(shí)時(shí)規(guī)劃.為了更好地展現(xiàn)出任務(wù)規(guī)劃的流程,圖4中將態(tài)勢(shì)與威脅評(píng)估、航跡規(guī)劃的工作過(guò)程分步分開(kāi)表示.

1.4.1 離線預(yù)規(guī)劃

離線預(yù)規(guī)劃:起飛前,根據(jù)任務(wù)指令在完成態(tài)勢(shì)評(píng)估系統(tǒng)同時(shí)完成:任務(wù)分析,建立任務(wù)優(yōu)先級(jí)和對(duì)已知信息的態(tài)勢(shì)分析與態(tài)勢(shì)估計(jì),建立目標(biāo)的威脅評(píng)估并結(jié)合我機(jī)情況完成目標(biāo)代價(jià)收益評(píng)估.然后,根據(jù)各類(lèi)評(píng)估數(shù)據(jù)基于任務(wù)要求建立的優(yōu)先級(jí)原則,完成目標(biāo)的分配、路徑規(guī)劃和航跡修正,預(yù)規(guī)劃完成.

1.4.2 在線實(shí)時(shí)規(guī)劃

在線實(shí)時(shí)規(guī)劃:執(zhí)飛后,當(dāng)在飛行過(guò)程中出現(xiàn)不明物或者與其他飛機(jī)交匯的問(wèn)題,由機(jī)載傳感器提供數(shù)據(jù)信息進(jìn)行分析、評(píng)估,分步判斷目標(biāo)對(duì)無(wú)人機(jī)是否有威脅、對(duì)任務(wù)的執(zhí)行是否有影響:是,協(xié)調(diào)修改;否,則執(zhí)行原計(jì)劃.由此確定是否具有更改預(yù)規(guī)劃的必要性,使無(wú)人機(jī)在動(dòng)態(tài)環(huán)境下縮短任務(wù)執(zhí)行的時(shí)間并提高了自身的自治能力.

1.5 小結(jié)

本節(jié)由分析多無(wú)人機(jī)任務(wù)規(guī)劃的規(guī)劃內(nèi)容、目的以及原則,討論了無(wú)人機(jī)任務(wù)規(guī)劃的體系結(jié)構(gòu),系統(tǒng)至少包含7個(gè)模塊,具備任務(wù)分配、航跡規(guī)劃、協(xié)調(diào)處理等功能,分析了多無(wú)人機(jī)控制系統(tǒng)的結(jié)構(gòu),將無(wú)人機(jī)任務(wù)規(guī)劃分為集中式任務(wù)規(guī)劃、部分分布式任務(wù)規(guī)劃和完全分布式任務(wù)規(guī)劃和基于多智能體的分布式控制系統(tǒng).最后闡述了任務(wù)規(guī)劃的基本流程,理論上實(shí)現(xiàn)了任務(wù)規(guī)劃過(guò)程中的離線預(yù)規(guī)劃和在線實(shí)時(shí)規(guī)劃.

2 任務(wù)分配

2.1 工作任務(wù)分配

任務(wù)分配包含了工作任務(wù)分配和工作目標(biāo)分配.工作任務(wù)分配是指對(duì)偵察監(jiān)視、目標(biāo)指示、電子干擾、火力打擊、效果評(píng)估等任務(wù),在一定的場(chǎng)景、戰(zhàn)況、任務(wù)下完全自主的智能式完成作戰(zhàn)任務(wù)步驟的分配,工作任務(wù)分配與工作目標(biāo)分配兩者求解的問(wèn)題模型以及解決問(wèn)題方法大同小異,分配本質(zhì)是一樣的,都是一個(gè)優(yōu)化組合NP問(wèn)題,有關(guān)工作任務(wù)分配問(wèn)題可見(jiàn)文獻(xiàn)[26,36]對(duì)多機(jī)協(xié)同作戰(zhàn),完成了偵察、評(píng)估、打擊3種任務(wù)的分配,建立了偵察—評(píng)估—打擊—評(píng)估的任務(wù)執(zhí)行順序.國(guó)內(nèi)外對(duì)工作任務(wù)分配研究相對(duì)較少,本章以工作目標(biāo)分配問(wèn)題(目標(biāo)分配)為闡述對(duì)象.

2.2 編隊(duì)級(jí)目標(biāo)分配

在高動(dòng)態(tài)實(shí)時(shí)戰(zhàn)場(chǎng)下,無(wú)人機(jī)面對(duì)的目標(biāo)數(shù)量眾多且相對(duì)分散,為提高求解速度,研究者們將聚類(lèi)思想用于目標(biāo)分配— 目標(biāo)群劃分技術(shù),由目標(biāo)聚類(lèi)分析建立目標(biāo)簇,將此目標(biāo)群分給某組無(wú)人機(jī)編隊(duì)[28,31,37?38].文獻(xiàn)[39]提出兩階段目標(biāo)分配,第一階段對(duì)分散的多目標(biāo)聚類(lèi)求解得若干目標(biāo)簇,再將目標(biāo)簇分配給不同的無(wú)人機(jī)編隊(duì),建立編隊(duì)級(jí)目標(biāo)分配,如圖5所示[39].最后編隊(duì)內(nèi)的各無(wú)人機(jī)進(jìn)行隊(duì)內(nèi)目標(biāo)分配,完成編隊(duì)內(nèi)目標(biāo)分配,如圖6所示[39].

2.2.1 聚類(lèi)分析

聚類(lèi)分析是指使用數(shù)學(xué)的方法研究和處理對(duì)給定對(duì)象分類(lèi).可劃分為:系統(tǒng)聚類(lèi)法、有序樣品聚類(lèi)法、動(dòng)態(tài)聚類(lèi)法、模糊聚法、圖論聚類(lèi)法、聚類(lèi)預(yù)報(bào)法等.聚類(lèi)分析的算法可以分為:1)劃分法(如:K-means算法、K-medoids算法、CLARANS算法等)在給定一個(gè)有N個(gè)元組或者記錄的數(shù)據(jù)集,通過(guò)反復(fù)迭代的方法改變分組,使得每一次改進(jìn)之后的分組方案都較前一次好,分裂法將構(gòu)造K個(gè)分組,每一個(gè)分組就代表一個(gè)聚類(lèi),其中K

2.2.2 K均值算法

近10年,K均值算法(也稱(chēng)K-means算法)是無(wú)人機(jī)目標(biāo)聚類(lèi)分析使用最多、最常用的一種動(dòng)態(tài)聚類(lèi)、一種基于劃分的迭代算法.通過(guò)反復(fù)修改分類(lèi)來(lái)達(dá)到最滿(mǎn)意的聚類(lèi)結(jié)果.其基本思想:先以一些初始點(diǎn)為聚類(lèi)中心,對(duì)樣本集進(jìn)行初始分類(lèi),判定分類(lèi)結(jié)果是否能使一個(gè)確定的準(zhǔn)則函數(shù)取得極值:能,聚類(lèi)算法結(jié)束;不能,改變聚類(lèi)中心,重新進(jìn)行分類(lèi),并重復(fù)判定所使用的準(zhǔn)則.設(shè)有k個(gè)分類(lèi),每個(gè)分類(lèi)域中心為m,(j=l,2,···,k),常用的準(zhǔn)則函數(shù)是使得每個(gè)類(lèi)中的各樣本到該類(lèi)中心的距離的平方和取得極小值,即:

K均值聚類(lèi)算法的運(yùn)算步驟[40]:

1)確定初始聚點(diǎn),根據(jù)聚點(diǎn)全部對(duì)象劃分為兩組,完成初始劃分;

2)然后計(jì)算每組的中心,修改聚點(diǎn),確定各組新聚點(diǎn);

2)最后由新的中心將對(duì)象重新劃分.

通過(guò)這樣確定中心點(diǎn)建立目標(biāo)簇完成編隊(duì)級(jí)目標(biāo)分配,就可將最近的目標(biāo)簇分配給該無(wú)人機(jī)編隊(duì),可簡(jiǎn)化了多無(wú)人機(jī)—多目標(biāo)分配問(wèn)題,從整體上提高了目標(biāo)分配求解效率.但是,傳統(tǒng)K均值聚類(lèi)算法由于產(chǎn)生類(lèi)的大小相差不會(huì)很大,且對(duì)臟數(shù)據(jù)很敏感.許多研究者以改變初始聚點(diǎn)或修改聚點(diǎn)等對(duì)傳統(tǒng)K均值聚類(lèi)算法進(jìn)行改進(jìn),如:K-means改進(jìn)的K-medoids算法[39],K-means是以當(dāng)前Cluster中所有數(shù)據(jù)點(diǎn)的平均值為中心點(diǎn),而K-medoids以當(dāng)前Cluster內(nèi)滿(mǎn)足到其他所有點(diǎn)的距離之和最小為中心點(diǎn);此外文獻(xiàn)[40]是以所有數(shù)據(jù)成員到聚類(lèi)中心的距離與聚類(lèi)的半徑閾值對(duì)比判定中心點(diǎn)的辦法改進(jìn)傳統(tǒng)K均值方法,當(dāng)出現(xiàn)距離大于設(shè)定的聚類(lèi)的半徑閾值時(shí),該點(diǎn)為新的中心點(diǎn).再依次檢測(cè)所有數(shù)據(jù)成員到聚類(lèi)中心的距離是否小于等于聚類(lèi)的半徑閾值,若都小于等于則該點(diǎn)為聚類(lèi)中心.以60個(gè)目標(biāo)仿真后得到改進(jìn)后K均值方法在求解預(yù)攻擊目標(biāo)聚類(lèi)問(wèn)題優(yōu)于傳統(tǒng)K均值方法,但是這樣計(jì)算量增大且計(jì)算的時(shí)間相對(duì)變長(zhǎng).

聚類(lèi)分析法還可用于航跡規(guī)劃,文獻(xiàn)[41]作者發(fā)現(xiàn)用遺傳算法完成路徑規(guī)劃后常常會(huì)產(chǎn)生多條可行航路,這些航路在空間中的分布有些相對(duì)分散而有些相對(duì)集中.由此提出是否可將聚類(lèi)分析使用到空間中較為分散的航路,計(jì)算航路的相對(duì)方向,對(duì)航路進(jìn)行聚類(lèi).作者在文中還分析到由于不同的航路其節(jié)點(diǎn)數(shù)一般不同,因此,不能用航路節(jié)點(diǎn)作為特征對(duì)航路進(jìn)行聚類(lèi),選擇航路個(gè)體的適應(yīng)度值和相對(duì)方向作為聚類(lèi)的數(shù)據(jù)對(duì)象,將K均值聚類(lèi)算法與基于遺傳算法的航路規(guī)劃方法結(jié)合起來(lái),通過(guò)將航路個(gè)體進(jìn)行聚類(lèi),生成K個(gè)子種群的航跡規(guī)劃算法,這樣就可提高規(guī)劃航路的時(shí)間,更快生成可飛行路徑.

2.3 編隊(duì)內(nèi)目標(biāo)分配

多目標(biāo)分配(圖6)根據(jù)環(huán)境知識(shí)、任務(wù)需求、目標(biāo)威脅強(qiáng)度及自身攻擊能力等信息下,既考慮到飛行器的數(shù)量、是否異構(gòu)、任務(wù)的類(lèi)別和權(quán)重、飛行的環(huán)境等因素,又考慮可行的航程代價(jià)、合理的分配算法、各種協(xié)同約束條件等[10],使完成最大數(shù)量任務(wù)的同時(shí)也滿(mǎn)足多機(jī)系統(tǒng)整體效率和資源配比達(dá)到最優(yōu)的分配問(wèn)題,是求解組合優(yōu)化的NP問(wèn)題[42].下面接介紹有關(guān)NP問(wèn)題的幾種常見(jiàn)模型以及解決NP問(wèn)題的常見(jiàn)算法,并類(lèi)比了這些算法在目標(biāo)分配問(wèn)題的上的適應(yīng)性.

2.3.1 常見(jiàn)的問(wèn)題模型

1)多旅行商問(wèn)題模型

旅行商問(wèn)題(TSP)是NP類(lèi)問(wèn)題的經(jīng)典模型,問(wèn)題是指有N個(gè)城市,要求旅行商到達(dá)每個(gè)城市各一次且僅一次,并回到起點(diǎn)且要求旅行路線最短.多旅行商問(wèn)題(MTSP)是指多個(gè)旅行商從同一個(gè)城市或不同城市出發(fā),分別走一條旅行路線,使得每個(gè)城市有且僅有一個(gè)旅行商經(jīng)過(guò)(出發(fā)城市除外),且總路程最短等有關(guān)問(wèn)題的研究.國(guó)內(nèi)對(duì)TSP和MTSP問(wèn)題求解進(jìn)行嘗試并改進(jìn)各種算法使計(jì)算范圍更大、結(jié)果更優(yōu)化.文獻(xiàn)[43]采用蟻群算法解決了無(wú)人機(jī)滯留防御方雷達(dá)探測(cè)范圍內(nèi)時(shí)間總和最小的航線優(yōu)化問(wèn)題;文獻(xiàn)[44?45]提出改進(jìn)的蟻群算法對(duì)多目標(biāo)情況下的航路規(guī)劃問(wèn)題求解;文獻(xiàn)[46]基于多目標(biāo)多旅行商問(wèn)題模型,將旅行商的個(gè)數(shù)和多旅行商的最長(zhǎng)訪問(wèn)路徑作為優(yōu)化目標(biāo),采用改進(jìn)的多目標(biāo)模擬退火算法和多目標(biāo)遺傳算法分別對(duì)30個(gè)城市的旅行商問(wèn)題進(jìn)行了測(cè)試,發(fā)現(xiàn)改進(jìn)的多目標(biāo)模擬退火算法比多目標(biāo)遺傳算法計(jì)算復(fù)雜度低、能有較好的最優(yōu)解且算法性能更優(yōu),此外文獻(xiàn)[20]發(fā)現(xiàn)受時(shí)序優(yōu)先級(jí)約束的協(xié)同多任務(wù)規(guī)劃過(guò)程中會(huì)出現(xiàn)不可避免的死鎖問(wèn)題,基于圖論提出了一整套方法進(jìn)行處理,指出在多無(wú)人機(jī)路徑協(xié)調(diào)過(guò)程中,沿著解的拓?fù)湫蛄?順序協(xié)調(diào)飛行路徑,可獲得最佳的協(xié)調(diào)效果.

2)車(chē)輛路徑問(wèn)題模型

多車(chē)輛路徑問(wèn)題(MDVRP)是車(chē)輛路徑問(wèn)題的一種擴(kuò)展.根據(jù)車(chē)輛的型號(hào)是否相同,可將車(chē)輛路徑問(wèn)題分為單車(chē)型問(wèn)題(VRP)和多車(chē)型題(HVRP).單車(chē)型問(wèn)題假定車(chē)輛的型號(hào)相同,即具有相同的最大載重量、最大行駛距離、固定成本與變動(dòng)成本,而多車(chē)型問(wèn)題則不同,通常各車(chē)型的最大載重、使用成本等都各不同.目前國(guó)內(nèi)對(duì)多車(chē)場(chǎng)車(chē)輛問(wèn)題研究注重結(jié)合實(shí)際運(yùn)行情況,從傳統(tǒng)的啟發(fā)式算法的應(yīng)用到現(xiàn)在集中于現(xiàn)代啟發(fā)式算法的應(yīng)用,并對(duì)多車(chē)場(chǎng)問(wèn)題進(jìn)行擴(kuò)充.而MDVRP,在多車(chē)輛路徑問(wèn)題上增加了多停車(chē)場(chǎng)情況,符合車(chē)輛的調(diào)度問(wèn)題.國(guó)內(nèi)2011年王征等人,對(duì)多車(chē)場(chǎng)帶時(shí)間窗車(chē)輛路徑問(wèn)題的變鄰域搜索算法進(jìn)行了研究[47];2017年顏瑞等人,考慮二維裝箱約束的多車(chē)場(chǎng)帶時(shí)間窗的車(chē)輛路徑問(wèn)題模型及算法研究[48].多車(chē)場(chǎng)、多車(chē)型車(chē)輛路徑問(wèn)題(MDMTVRP),是對(duì)基本車(chē)輛路徑問(wèn)題的擴(kuò)展,更是對(duì)多車(chē)場(chǎng)車(chē)輛路徑問(wèn)題和多車(chē)型車(chē)輛路徑問(wèn)題的組合,它的求解必然更加復(fù)雜.目前國(guó)內(nèi)外還沒(méi)有一個(gè)相對(duì)成熟的解決辦法,這也是目前研究的熱點(diǎn)問(wèn)題和難點(diǎn)問(wèn)題.國(guó)內(nèi)學(xué)者對(duì)此問(wèn)題已開(kāi)始進(jìn)行初步的研究探索,馬建華等[49]以最快完成為目的求解MDMTVRP,對(duì)給定的顧客順序劃分車(chē)輛和指派車(chē)場(chǎng),把該問(wèn)題轉(zhuǎn)化為尋找最優(yōu)顧客順序問(wèn)題進(jìn)行求解.然而,這種方法劃分了路線,對(duì)每條路線取最優(yōu),達(dá)到了局部最優(yōu),但對(duì)于全局而言并不一定是收益最大的,即:不一定是全局最優(yōu)解;2018年陳呈頻等[50],對(duì)多車(chē)場(chǎng)與多車(chē)型車(chē)輛路徑問(wèn)題的多染色體遺傳算法的研究,雖然全局上得到了最優(yōu)解,但是計(jì)算量很大、且是集中計(jì)算,對(duì)服務(wù)器要求很高,花費(fèi)時(shí)間很長(zhǎng).

3)混合整數(shù)線性規(guī)劃模型

混合整數(shù)線性規(guī)劃(MILP)的研究己有相當(dāng)長(zhǎng)的歷史.1974年,G.Dantzig提出了線性規(guī)劃單純形間算法,并在應(yīng)用中取得了很大的成功.但現(xiàn)實(shí)生活中機(jī)器臺(tái)數(shù)、工作人數(shù)這類(lèi)變化要求必須是整數(shù),如果在線性規(guī)劃的模型中添加一些整數(shù)約束,那么該模型將有更廣闊的應(yīng)用空間,由此產(chǎn)成了MILP.目前求解MILP的方法主要有分支定界法和巧平面法.用混合整數(shù)規(guī)劃技術(shù)求解規(guī)劃問(wèn)題具有一些優(yōu)點(diǎn)[51]:模型描述簡(jiǎn)潔、直接,很容易表示涉及到數(shù)值的全局約束,有助于提高無(wú)人機(jī)任務(wù)執(zhí)行效率和生存能力,達(dá)到了任務(wù)分配的目的和初衷,且當(dāng)無(wú)法求得最優(yōu)解時(shí),可以較快求出次優(yōu)解.文獻(xiàn)[52]采用混合整數(shù)線性規(guī)劃技術(shù)對(duì)無(wú)人機(jī)最優(yōu)搜索任務(wù)方法的研究,仿真結(jié)果表明如果有可能降低優(yōu)化問(wèn)題的復(fù)雜度,則可以減少計(jì)算時(shí)間.但是模型規(guī)模不能過(guò)大,問(wèn)題規(guī)模過(guò)大將導(dǎo)致計(jì)算量指數(shù)型增長(zhǎng),任務(wù)分配的實(shí)時(shí)性得不到保證.

4)網(wǎng)絡(luò)流模型

網(wǎng)絡(luò)流模型(NFM)網(wǎng)絡(luò)流是一種類(lèi)比水流的解決問(wèn)題方法,與線性規(guī)劃密切相關(guān).其優(yōu)化特性是對(duì)于已知攻擊目標(biāo)、行為的數(shù)據(jù)集進(jìn)行學(xué)習(xí),以及對(duì)人為選定的攻擊組合特征進(jìn)行優(yōu)化,使之更能反映該攻擊行為的特點(diǎn).網(wǎng)絡(luò)流量分配模型是基于網(wǎng)絡(luò)流量特征向量分層劃分的思想,具備基本特征和優(yōu)化特性?xún)蓚€(gè)特點(diǎn).文獻(xiàn)[53]中將網(wǎng)絡(luò)流量分配劃分為:平衡配流[54]和非平衡配流.在一定供給和需求水平條件下,如何確定網(wǎng)絡(luò)中具體弧段上的流量,用于模擬當(dāng)前整個(gè)運(yùn)輸網(wǎng)絡(luò)的狀態(tài),評(píng)估其性能從而為決策者制定政策及網(wǎng)絡(luò)發(fā)展規(guī)劃提供依據(jù).文獻(xiàn)[55]介紹了網(wǎng)絡(luò)流量分配模型的基本概念和移動(dòng)云計(jì)算環(huán)境下可以有效解決發(fā)展中遇到的移動(dòng)設(shè)備差異化和網(wǎng)絡(luò)環(huán)境復(fù)雜帶來(lái)的資源浪費(fèi)、網(wǎng)絡(luò)開(kāi)銷(xiāo)大等問(wèn)題,使移動(dòng)端和云端各盡其能,大大提高程序運(yùn)行的效率.

2.3.2 常見(jiàn)的求解算法

1)打擊式目標(biāo)分配

2.3.1節(jié)中幾種NP問(wèn)題模型現(xiàn)已有許多解決算法:傳統(tǒng)的匈牙利算法,用于分布式系統(tǒng)的合同網(wǎng)法以及目前正蓬勃發(fā)展的智能優(yōu)化算法.經(jīng)過(guò)對(duì)這些算法學(xué)習(xí)、研究,通過(guò)它們各自的特性、適用性等不同,建立如表1所示的目標(biāo)分配算法的類(lèi)比.雖然這些算法能解決一些約束少、優(yōu)化目標(biāo)少、規(guī)模小的目標(biāo)分配問(wèn)題,而為能解決在現(xiàn)實(shí)環(huán)境中的復(fù)雜問(wèn)題,研者們嘗試對(duì)已有的算法進(jìn)行改進(jìn)與優(yōu)化,并得到不錯(cuò)的效果.國(guó)內(nèi)學(xué)者,文獻(xiàn)[56]基于同構(gòu)多機(jī)協(xié)同空對(duì)地,建立了目標(biāo)分配模型,根據(jù)戰(zhàn)術(shù)任務(wù)和戰(zhàn)術(shù)目標(biāo)提出相關(guān)約束,減小搜索范圍提高攻擊效率.同時(shí)引入滿(mǎn)意決策理論,根據(jù)攻擊滿(mǎn)意集來(lái)搜索目標(biāo)分配最優(yōu)解,大大提升了搜索效率;文獻(xiàn)[29]對(duì)3個(gè)有人作戰(zhàn)智能體控制的不同數(shù)量的異構(gòu)無(wú)人作戰(zhàn)智能體進(jìn)行多目標(biāo)分配,分別采用集中式遺傳算法、傳統(tǒng)合同網(wǎng)算法和擴(kuò)展后的合同網(wǎng)算法(CNP)的分布式分配法,發(fā)現(xiàn)在集中式遺傳算法可得到優(yōu)于全局的分配方案,但通信量和計(jì)算時(shí)間上都高于其余兩種,若目標(biāo)新增則需重新求解;而采用分布式擴(kuò)展后的CNP具有更好的尋優(yōu)質(zhì)量,通信量小于傳統(tǒng)的合同網(wǎng),但由于擴(kuò)展后CNP在招標(biāo)、投標(biāo)和中標(biāo)策略比傳統(tǒng)CNP的復(fù)雜度大,在計(jì)算時(shí)間上,需要更多的計(jì)算時(shí)間,以犧牲少量計(jì)算時(shí)間為代價(jià)得到了較高質(zhì)量的解和較少的通信量;文獻(xiàn)[57]采用模擬退火遺傳算法進(jìn)行目標(biāo)攻擊分配方案的尋優(yōu),對(duì)算法中的非常規(guī)編碼、變異以及模擬退火平衡條件和凍結(jié)條件進(jìn)行了設(shè)計(jì),結(jié)合最優(yōu)導(dǎo)彈目標(biāo)攻擊分配方案,得出相應(yīng)的最佳協(xié)同多目標(biāo)攻擊決策解.

2)對(duì)抗式目標(biāo)分配

目前大多數(shù)研究都是單次(一次性)靜/動(dòng)態(tài)打擊式目標(biāo)分配,但由于未來(lái)無(wú)人機(jī)自主作戰(zhàn)過(guò)程中不可能是單次目標(biāo)分配,而是敵我雙方動(dòng)態(tài)(多階段多次)對(duì)抗式目標(biāo)分配,國(guó)內(nèi)學(xué)者哈爾濱工業(yè)大學(xué)教授韓松臣1996年提出[58]可基于馬爾可夫動(dòng)態(tài)系統(tǒng)通過(guò)隨機(jī)服務(wù)系統(tǒng)輸入過(guò)程的最優(yōu)控制建立目標(biāo)分配決策模型的方法,考慮實(shí)戰(zhàn)中不同類(lèi)型目標(biāo)(如核武器、重型轟炸機(jī)、誘餌彈等)的威脅程度相差很大利用這種方法得到的決策結(jié)果能有效地減少重點(diǎn)目標(biāo)突防的概率,得到攻防對(duì)抗式目標(biāo)分配決策.北京航空航天研究者姜?dú)g、陳萬(wàn)春2007年[59]對(duì)動(dòng)靜態(tài)結(jié)合的武器目標(biāo)分配方法求取最大化的攔截效能其基本依據(jù)馬爾可夫決策過(guò)程和隨機(jī)服務(wù)系統(tǒng)輸入過(guò)程最優(yōu)化問(wèn)題.采用馬爾可夫決策用于目標(biāo)分配通過(guò)策略迭代算法得到最優(yōu)分配策略從而實(shí)現(xiàn)系統(tǒng)效益的最大化.2012年黃長(zhǎng)強(qiáng)等[60]研究了基于博弈論建立在納什平衡(在雙方都為最優(yōu)策略)下的對(duì)抗策略,并仿真完成了動(dòng)態(tài)下的多次武器目標(biāo)分配.但不足之處是當(dāng)打破這一平衡,整個(gè)過(guò)程便不會(huì)具有動(dòng)態(tài)特性.

對(duì)抗式動(dòng)態(tài)目標(biāo)多次分配問(wèn)題的研究仍然處于起步階段,目前沒(méi)有系統(tǒng)的理論能夠解決這一問(wèn)題.

2.4 小結(jié)

在第2節(jié)中我們以編隊(duì)級(jí)、編隊(duì)內(nèi)目標(biāo)分配這兩階段著手分析研究,介紹了編隊(duì)級(jí)目標(biāo)分配解決問(wèn)題的一般步驟和K均值算法.例舉了編隊(duì)內(nèi)目標(biāo)分配的幾種常見(jiàn)的分配模型,再將目標(biāo)分配算法從作戰(zhàn)方式上分為:打擊式與對(duì)抗式,例舉了打擊式靜、動(dòng)態(tài)目標(biāo)分配的算法并分析了其特性及適用性和研究者們對(duì)對(duì)抗式目標(biāo)分配提出的一些可用方法.

3 航跡規(guī)劃

3.1 路徑規(guī)劃

3.1.1 基于環(huán)境建模的方法

1)路標(biāo)圖法

路標(biāo)圖法包括可視圖法、Voronoi圖法和概率路圖法.可視圖法、Voronoi圖法通過(guò)對(duì)環(huán)境空間的釆樣處理,把環(huán)境空間轉(zhuǎn)換為避開(kāi)路徑中(起點(diǎn)到終點(diǎn))所有約束區(qū)由若干線段組成的二維網(wǎng)絡(luò).而不同之處在于,可視圖法是將障礙物設(shè)置成一個(gè)多邊形,其余空間為自由區(qū),由各多邊形上的頂點(diǎn)連接而成的可視直線,是最早的路徑規(guī)劃方法之一;Voronoi圖法[16]是將地圖規(guī)劃成圍繞障礙物的多個(gè)共邊的多邊形連接圖,從這些多邊形的節(jié)點(diǎn)經(jīng)過(guò)公共邊到下一個(gè)節(jié)點(diǎn)直到非完整性規(guī)劃和運(yùn)動(dòng)動(dòng)力學(xué)規(guī)劃中,其優(yōu)點(diǎn)根植于它不需要連接任何一對(duì)位姿點(diǎn)或狀態(tài)點(diǎn),完成從起點(diǎn)到終點(diǎn)的路線,是目前使用較多路徑規(guī)劃方法之一.文獻(xiàn)[16]葉媛媛等人對(duì)想定的已知靜態(tài)配置的威脅和突現(xiàn)威脅通過(guò)Voronoi圖法對(duì)無(wú)人機(jī)任務(wù)規(guī)劃建模,確定此方法作為初始可選航路可行.概率法是隨機(jī)選取相鄰點(diǎn)使其滿(mǎn)足一定的優(yōu)化準(zhǔn)則,如最短距離,此時(shí)概率法稱(chēng)為隨機(jī)概率路圖法.在概率法基礎(chǔ)之上,1996年Kavraki等以分隔單元內(nèi)的搜索的方式研究得到概率路圖法.1998年Lavalle,2001年Cheng等通過(guò)現(xiàn)有樹(shù)中最近點(diǎn)相連得到下一步軌跡的方式研究得到快速擴(kuò)展隨機(jī)樹(shù)法,文獻(xiàn)[61]提出快速擴(kuò)展隨機(jī)樹(shù)法優(yōu)點(diǎn)在于無(wú)需啟發(fā)式函數(shù),以隨機(jī)性作為最有力的參數(shù);應(yīng)用于航跡規(guī)劃的隨機(jī)數(shù)據(jù)結(jié)構(gòu),針對(duì)不確定環(huán)境下的航跡規(guī)劃問(wèn)題,并能直接應(yīng)用于非完整性約束下的環(huán)境,而概率路標(biāo)算法則需要上萬(wàn)個(gè)這樣的連接.

表1 目標(biāo)分配算法

2)單元分解

單元分解法是將環(huán)境劃分為若干個(gè)正四邊形或正六邊形柵格,有障礙物、威脅、禁飛等區(qū)域視為不疊加的陰影區(qū),其余為自由區(qū),在空間區(qū)域內(nèi)連通柵格構(gòu)造(從起點(diǎn)到目標(biāo)點(diǎn))代價(jià)最小的航行路徑,但即使這樣,相比其他方法可選的空間環(huán)境變小,路徑相對(duì)變長(zhǎng),且柵格的大小也對(duì)路徑規(guī)劃有很大的影響:當(dāng)柵格較大時(shí),其存儲(chǔ)信息量小,航路質(zhì)量低;當(dāng)柵格較小時(shí),存儲(chǔ)信息量大,相比之下航路的質(zhì)量高.

3)人工勢(shì)場(chǎng)法

人工勢(shì)場(chǎng)法[62?63]是將整個(gè)空間區(qū)域建勢(shì)場(chǎng)模,基于“同性相吸、異性相斥”的原理,在目標(biāo)吸引力場(chǎng)與障礙物排斥力場(chǎng)共同作用的勢(shì)能場(chǎng)下,沿著勢(shì)函數(shù)下降的方向運(yùn)動(dòng),結(jié)合搜索算法選擇最優(yōu)路徑.其優(yōu)點(diǎn)在于與障礙物相排斥規(guī)劃出的路徑相對(duì)安全,實(shí)時(shí)性極強(qiáng)可用于在線避障且規(guī)劃出的路徑相對(duì)平滑.缺點(diǎn)在于勢(shì)場(chǎng)對(duì)一些約束條件不好處理,且障礙物如“C”型易陷入局部極小的陷阱區(qū)域問(wèn)題.此方法通過(guò)求合力控制移動(dòng)飛行器的運(yùn)動(dòng),當(dāng)障礙物過(guò)密過(guò)多,在狹窄的路徑中可能會(huì)造成斥力大等于引力,無(wú)人機(jī)無(wú)法飛往目標(biāo)或者出現(xiàn)抖動(dòng)問(wèn)題[64].所以適用于障礙物數(shù)量不多的環(huán)境中,且僅用于單無(wú)人機(jī).

3.1.2 路徑的優(yōu)化組合

路徑優(yōu)化問(wèn)題是指在飛機(jī)性能、自然環(huán)境、任務(wù)要求等約束條件下,從全局出發(fā),合理安排各無(wú)人機(jī)有序完成任務(wù),達(dá)到路程最短、費(fèi)用最少、耗時(shí)最少、毀傷程度最少等目標(biāo)的調(diào)度技術(shù)[65].也可以看成復(fù)雜的優(yōu)化組合NP問(wèn)題,目前解決路徑優(yōu)化[45,66?67]的方法可分為:精確算法(分支定界法、動(dòng)態(tài)規(guī)劃法、網(wǎng)絡(luò)流算法)、傳統(tǒng)啟發(fā)式算法(掃描法、數(shù)學(xué)規(guī)劃法)、智能優(yōu)化算法(禁忌搜索法、模擬退火法、蟻群算法、遺傳算法[17]等),其特性及適用性分析見(jiàn)表2.和聲搜索算法[68]是近幾年新提出來(lái)的一種智能算法,一種啟發(fā)式全局搜索算法,通過(guò)反復(fù)調(diào)整記憶庫(kù)中的解變量,使函數(shù)值隨著迭代次數(shù)的增加不斷收斂,從而來(lái)完成優(yōu)化.算法概念簡(jiǎn)單、可調(diào)參數(shù)少、容易實(shí)現(xiàn).除此之外,董喬月、李洪雙等[69]2016年在解決桁架結(jié)構(gòu)優(yōu)化設(shè)計(jì)和機(jī)翼翼盒結(jié)構(gòu)優(yōu)化問(wèn)題時(shí)使用了增廣拉格朗日子集模擬優(yōu)化方法.增廣拉格朗日子集模擬優(yōu)化方法是一種基于增廣拉朗日約束處理方法和子集模擬優(yōu)化方法發(fā)展的優(yōu)化設(shè)計(jì)方法.利用拉格朗日乘子法處理多重約束條件,再利用子集模擬優(yōu)化方法對(duì)轉(zhuǎn)化后的無(wú)約束優(yōu)化問(wèn)題進(jìn)行求解;對(duì)罰函數(shù)因子的更新方法進(jìn)行改進(jìn),以保證收斂過(guò)程的穩(wěn)定性.作者將其與其他著名優(yōu)化算法進(jìn)行對(duì)比,發(fā)現(xiàn)相比于遺傳算法、蟻群算法、粒子群優(yōu)化算法更具有很好的尋優(yōu)準(zhǔn)確性,相比于和聲搜索算法具有不超越最大約束限制.由此我們可對(duì)此方法繼續(xù)深入研究是否能用于求解任務(wù)規(guī)劃的優(yōu)化組合問(wèn)題.此外用于解決單機(jī)快速路徑規(guī)劃有A*算法、D*算法和Dijkstra算法.A*算法是一種經(jīng)典的最優(yōu)啟發(fā)搜索算法,以柵格為基礎(chǔ),以柵格中心點(diǎn)為子節(jié)點(diǎn)進(jìn)行擴(kuò)展,可過(guò)濾掉不必要的節(jié)點(diǎn)(不同問(wèn)題的具體約束結(jié)合)削減了搜索的空間.同時(shí)A*算法是智能搜索算法,搜索效率高,但最優(yōu)程度取決于啟發(fā)函數(shù)的表達(dá)式且當(dāng)搜索空間很大時(shí),計(jì)算量也大,主用于路徑預(yù)規(guī)劃.文獻(xiàn)[70?72]研究了基于A*算法在路徑規(guī)劃和圖搜索的工程應(yīng)用,文獻(xiàn)[73]對(duì)A*算法改進(jìn)為稀疏A*算法,將節(jié)點(diǎn)帶約束的選擇性擴(kuò)展,減少了搜索的空間.A*算法與Dijkstra算法只適用于靜態(tài)環(huán)境,D*是動(dòng)態(tài)的A*,D*算法是A*算法與Dijkstra算法的結(jié)合在動(dòng)態(tài)環(huán)境中尋路非常有效,向目標(biāo)點(diǎn)移動(dòng)中,只檢查最短路徑上下一節(jié)點(diǎn)或臨近節(jié)點(diǎn)的變化情況.其他的還有文獻(xiàn)[41]利用元胞自動(dòng)機(jī)算法解決航跡規(guī)劃問(wèn)題,將航跡規(guī)劃問(wèn)題分為多層次問(wèn)題,對(duì)每一層的問(wèn)題,分別提出了解決的方法,再將各層次問(wèn)題綜合得到最終的航跡優(yōu)化結(jié)果.

3.2 航跡修正

3.2.1 平滑處理

平滑處理是航跡規(guī)劃技術(shù)中重要組成之一,是解決路徑初規(guī)劃后使路徑滿(mǎn)足無(wú)人機(jī)飛行性能約束的問(wèn)題.路徑初規(guī)劃是由許多最短直線首尾連接而成的折線,具有一定的角度,而無(wú)人機(jī)受飛行性能約束,轉(zhuǎn)角有限不能都達(dá)到.研究者們對(duì)此問(wèn)題提出路徑修正:軌跡曲線規(guī)化法即平滑處理,將不滿(mǎn)足飛行性能約束的路徑,計(jì)算修正為滿(mǎn)足飛行約束的曲線,建立參數(shù)控制,使無(wú)人機(jī)沿滿(mǎn)足飛行性能約束的曲線航跡飛到終點(diǎn)到目前為止,文獻(xiàn)[61]在航跡平滑層中引入k航跡平滑算法奠定了基礎(chǔ).文獻(xiàn)[67]航跡平滑過(guò)程基于B-spline方法,對(duì)平面移動(dòng)和高度變化被分別考慮,算法通過(guò)對(duì)控制點(diǎn)的修整,使生成的航跡滿(mǎn)足場(chǎng)景及UAV的約束;文獻(xiàn)[74]采用CR樣條曲線是Bezier曲線的一種改進(jìn)形式,一種插值樣條曲線,參數(shù)方簡(jiǎn)單,計(jì)算速度快,具有C1連續(xù)性(切線連續(xù)),且修改其中某一控制點(diǎn)只會(huì)修改相鄰的曲線變化,不會(huì)影響距該點(diǎn)較遠(yuǎn)的曲線形狀,當(dāng)要對(duì)某些航跡段調(diào)整時(shí),僅需要對(duì)部分航跡做出改變即可.文獻(xiàn)[75]基于Clothoid螺旋曲線的復(fù)合路徑,采用一種新的算法與基于微分幾何的迭代算法相比能夠在任意起止點(diǎn)位置和方向下得到更短的曲率連續(xù)的Clothoid復(fù)合路徑且算法迭代簡(jiǎn)單.曲線規(guī)劃法包含的種類(lèi)眾多,但它們適用性并不相同,表3簡(jiǎn)單介紹了幾種常用的曲線,分析了各自的適用性.

表2 路徑規(guī)劃算法

3.2.2 安全距離

目前,國(guó)內(nèi)外對(duì)曲線規(guī)劃法的研究已不只在路徑的平滑處理.多無(wú)人機(jī)協(xié)同攻擊時(shí)存在兩機(jī)或多機(jī)交匯問(wèn)題,為避免無(wú)人機(jī)交匯碰撞將無(wú)人機(jī)建立軌道安全距離,如果不滿(mǎn)足安全約束,需通過(guò)改變曲率或添加中間航路點(diǎn)等方法,通過(guò)K航跡平滑處理法、Dubins曲線、Clothoid螺旋曲線、PH螺旋曲線等對(duì)路徑修正,如文獻(xiàn)[76]仿真得到PH路徑隨切線向量長(zhǎng)度k變化,如圖7所示[76].文獻(xiàn)[77]在城市環(huán)境和山區(qū)環(huán)境下提出使用PH曲線和和聲搜索算法調(diào)整飛行路徑以滿(mǎn)足空間需求,滿(mǎn)足無(wú)人機(jī)的運(yùn)動(dòng)和動(dòng)態(tài)約束,保證任何兩輛車(chē)之間都大于等于安全距離,不存在碰撞路線以及障礙物.此外有的研究者將躲避新障礙物問(wèn)題也看做航跡安全距離問(wèn)題.由于人工勢(shì)場(chǎng)法常用于躲避障礙物,并可以得到較平滑的路徑,但由于它只適用于障礙物數(shù)量不多的環(huán)境下,文獻(xiàn)[64]指出傳統(tǒng)的人工勢(shì)場(chǎng)僅限于單個(gè)無(wú)人機(jī)軌跡規(guī)劃,為了克服這一挑戰(zhàn),提出了一種利用距離因子和跳躍策略來(lái)解決不可達(dá)目標(biāo)等常見(jiàn)問(wèn)題的方法,并確保無(wú)人機(jī)不會(huì)碰到任何障礙物.此外,使用動(dòng)態(tài)步長(zhǎng)調(diào)整方法解決抖動(dòng)問(wèn)題.已在定量測(cè)試仿真模型中得到驗(yàn)證,并且在模擬城市環(huán)境中獲得滿(mǎn)意的結(jié)果.國(guó)內(nèi)外研究者們對(duì)航跡修正(避障)還研究出其他可行方法:文獻(xiàn)[67]采用啟發(fā)式A*搜索算法和B樣條曲線對(duì)1)無(wú)人機(jī)探測(cè)半徑的航跡修正、2)不規(guī)則障礙物的航跡修正、3)突發(fā)情況的航跡修正、4)目標(biāo)位置改變的航跡修正、5)目標(biāo)變異的航跡修正,這5種情況下由于威脅的突發(fā)性對(duì)航跡在線修正,并得到了較好的實(shí)驗(yàn)結(jié)果.也有其他研究者用蟻群、遺傳等智能搜索算法代替A*算法雖然可以滿(mǎn)足多架無(wú)人機(jī)協(xié)同規(guī)劃問(wèn)題,但這樣的搜索算法計(jì)算時(shí)間過(guò)長(zhǎng),對(duì)躲避動(dòng)態(tài)障礙物在線實(shí)時(shí)路徑修正的實(shí)用性不大.由此研究者們將曲線規(guī)劃法直接用于避障技術(shù)上,將障礙物所處的路徑位置看作不滿(mǎn)足飛行約束的路徑,對(duì)路徑進(jìn)行曲線修正避開(kāi)障礙物.文獻(xiàn)[78]一書(shū)中詳細(xì)介紹了Dubins曲線、PH曲線、Clothoid曲線用于已知障礙物的路徑修正問(wèn)題和結(jié)合安全圓算法或中間航點(diǎn)算法解決未知障礙物的避障路徑修正.國(guó)內(nèi)楊秀霞、張毅、周皚皚等人2015年采用PH曲線用于航跡修正法、分布估計(jì)算法解決路徑優(yōu)化問(wèn)題、速度障礙法在線勘測(cè)障礙物這3種算法完成了在線避障航跡規(guī)劃,PH曲線在此可由不同初始條件和終止切向量長(zhǎng)度,滿(mǎn)足曲率約束的初始和終止偏航角[79];2016年對(duì)現(xiàn)有避障算法忽略重規(guī)劃路徑侵犯威脅障礙物安線路徑規(guī)劃為例,基于速度障礙圓弧法給出了速度障礙圓弧法,并在此基礎(chǔ)全圓的問(wèn)題上提出一種基于PH螺線修正避障重規(guī)劃路徑的方法[80];2017年結(jié)合PH曲線路徑規(guī)劃提出了一種動(dòng)態(tài)不確定環(huán)境下UAV自主避障算法[81].

3.2.3 多機(jī)協(xié)同優(yōu)化

目前國(guó)內(nèi)外對(duì)無(wú)人機(jī)在突發(fā)威脅后,采用曲線規(guī)劃法對(duì)路徑修正避開(kāi)障礙物,可看作小范圍的航跡重規(guī)劃.此法不但簡(jiǎn)化了系統(tǒng)的復(fù)雜結(jié)構(gòu),更可縮短計(jì)算時(shí)間.采用曲線規(guī)劃法優(yōu)化飛行路徑,使多機(jī)協(xié)同大致建立在兩種思想上:1)使得平滑后的航跡與平滑之前的航跡長(zhǎng)度相等,以滿(mǎn)足多機(jī)協(xié)同規(guī)劃時(shí)確定的預(yù)計(jì)到達(dá)時(shí)間不變;2)基于各無(wú)人機(jī)都能達(dá)到的約束條件下或性能相同的情況下,使多架無(wú)人機(jī)從起點(diǎn)到達(dá)終點(diǎn)修正后所產(chǎn)生的路徑長(zhǎng)度相等,也可滿(mǎn)足來(lái)多無(wú)人機(jī)路徑規(guī)劃的協(xié)同性.文獻(xiàn)[61]基于第1種思想提出一種分級(jí)分解的方法,將優(yōu)化分解成3步,將協(xié)同航跡產(chǎn)生器分解為航跡生成層、航跡協(xié)同層和航跡平滑層.在航跡生成層中引入了快速擴(kuò)展隨機(jī)隨算法,并通過(guò)對(duì)隨機(jī)擴(kuò)展函數(shù)進(jìn)行改進(jìn)以及采用Dijkstra算法對(duì)冗余節(jié)點(diǎn)進(jìn)行處理,提高了算法的效率;在航跡協(xié)同層中以編隊(duì)代價(jià)函數(shù)最小為約束,確定了各機(jī)的航跡以及同時(shí)到達(dá)時(shí)間(ETA)并確定了各自的速度;在航跡平滑層中引入k航跡平滑算法對(duì)航跡拐點(diǎn)處進(jìn)行處理并通過(guò)對(duì)參數(shù)k的取值使得平滑后的航跡與平滑之前的航跡長(zhǎng)度相等,以滿(mǎn)足多機(jī)協(xié)同規(guī)劃時(shí)確定的ETA不變.而國(guó)外研究者們基于第2種思想,設(shè)定多無(wú)人機(jī)為一組勻速飛行的無(wú)人機(jī),將多無(wú)人機(jī)路徑規(guī)劃同時(shí)到達(dá)問(wèn)題分為了3個(gè)階段:產(chǎn)生可飛行路徑、產(chǎn)生可行路徑(采用Dubins曲線、Clothoid曲線、PH曲線用于二維和三維的可飛行路徑規(guī)劃建立無(wú)人機(jī)之間的安全距離)和產(chǎn)生等長(zhǎng)度路徑(改變曲率的方法調(diào)整路徑的長(zhǎng)度),成功應(yīng)用在二維和三維空間內(nèi)多機(jī)協(xié)同達(dá)到的Dubins路徑和PH路徑中[78].

表3 路徑規(guī)劃算法

3.3 小結(jié)

第3節(jié)主要敘述了航跡規(guī)劃中基于環(huán)境建模的3種方法,常用于路徑優(yōu)化的算法其特性及適用性的分析,闡述了平滑處理中采用曲線規(guī)劃法修正了不滿(mǎn)足無(wú)人機(jī)自身特性的規(guī)劃路徑,分析了6種不同曲線其特性和適用范圍.最后介紹了改變曲率或添加中間航路點(diǎn)的數(shù)目可處理兩機(jī)之間的安全距離問(wèn)題和多機(jī)協(xié)同的問(wèn)題.

4 總結(jié)與展望

多無(wú)人機(jī)協(xié)同任務(wù)規(guī)劃技術(shù)是一個(gè)綜合性研究課題.本文圍繞系統(tǒng)架構(gòu)、目標(biāo)分配、航跡規(guī)劃等方面進(jìn)行總結(jié),并根據(jù)目前的研究現(xiàn)狀,淺談對(duì)多無(wú)人機(jī)任務(wù)規(guī)劃技術(shù)的展望:

1)以分析多無(wú)人機(jī)任務(wù)規(guī)劃的規(guī)劃內(nèi)容、目的以及原則,無(wú)人機(jī)任務(wù)規(guī)劃的體系架構(gòu)至少包含7個(gè)模塊,具備任務(wù)分配、航跡規(guī)劃、協(xié)調(diào)處理等功能,發(fā)現(xiàn)基于多智能體任務(wù)規(guī)劃系統(tǒng)的控制架構(gòu),相比于其他控制架構(gòu),其魯棒性好,具備良好的協(xié)同能力和自治能力,可減少無(wú)人機(jī)的反應(yīng)時(shí)間,提高作戰(zhàn)能力.但軟件的程序上所涉及層次增多,設(shè)計(jì)更為復(fù)雜.基于離線預(yù)規(guī)劃上并可在線實(shí)時(shí)規(guī)劃完成方案重規(guī)劃,雖然在理論上可實(shí)現(xiàn),但是在實(shí)際應(yīng)用中,系統(tǒng)計(jì)算程序的設(shè)定以及發(fā)現(xiàn)沖突后,對(duì)已有方案部分修改的判定以及如何修改還需要深入研究.

2)目標(biāo)分配以編隊(duì)級(jí)、編隊(duì)內(nèi)這兩個(gè)階段著手,目前這兩個(gè)階段的分配問(wèn)題都有可行方法.但國(guó)內(nèi)外在任務(wù)分配技術(shù)上的發(fā)展尚未成熟,目前對(duì)靜態(tài)目標(biāo)分配已形成了一套研究方法和步驟,對(duì)動(dòng)態(tài)分配的分配技術(shù)也有不少研究者提出了解決的辦法,但對(duì)于目標(biāo)—武器的多階段的綜合性分配問(wèn)題,雖已有采用博弈論的辦法可解決,但需基于納什平衡下才能完成分配,這一問(wèn)題目前任然是我們無(wú)法突破的難題.此外工作任務(wù)分配技術(shù)與工作目標(biāo)分配技術(shù)的結(jié)合問(wèn)題,形成“OODA”一個(gè)完整的任務(wù)分配過(guò)程,這將是解決目標(biāo)分配問(wèn)題后的下一個(gè)關(guān)鍵點(diǎn).

3)航跡規(guī)劃中研究者們已從環(huán)境建模、路徑優(yōu)化、航跡修正這3個(gè)方面完成了無(wú)人機(jī)航跡規(guī)劃的研究.并可通過(guò)改變曲率或添加中間航路點(diǎn)的數(shù)目來(lái)處理兩機(jī)之間的安全距離問(wèn)題和解決多機(jī)協(xié)同問(wèn)題.但無(wú)人機(jī)飛行時(shí)飛行環(huán)境復(fù)雜、攀爬動(dòng)力有限、轉(zhuǎn)彎角度受限且要求工作效率高,不同的實(shí)時(shí)任務(wù)要求下,對(duì)選擇適合的曲線路徑、中間航路點(diǎn)數(shù),控制適合的轉(zhuǎn)彎曲率尤為重要.無(wú)人機(jī)航跡規(guī)劃系統(tǒng)應(yīng)為決策者(決策系統(tǒng))分析、預(yù)測(cè)航跡的變化趨勢(shì),提供航跡在線代價(jià)評(píng)估,從航跡規(guī)劃上提高作戰(zhàn)效率.這也是亟待解決的問(wèn)題之一.

通過(guò)對(duì)多無(wú)人機(jī)協(xié)同任務(wù)規(guī)劃技術(shù)研究、分析,發(fā)現(xiàn)各類(lèi)問(wèn)題雖已有許多行之有效的解決方法,但任存在諸多不足.由于不同的無(wú)人機(jī)具有不同的特性、適應(yīng)性,由此下一步我們將嘗試在設(shè)定的場(chǎng)景下,對(duì)比各種模型及算法,選擇適合無(wú)人機(jī)的工作特性方法,并基于某一理論找出最優(yōu)辦法進(jìn)行優(yōu)化,縮短計(jì)算的時(shí)間,提高工作效率,使之在任務(wù)規(guī)劃問(wèn)題內(nèi)充分發(fā)揮自身優(yōu)勢(shì).