楊晨 張少卿 孟光磊

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

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

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

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

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

1.1.1 內(nèi)容與目的

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

1.1.2 規(guī)劃原則

1)基本原則

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

2)優(yōu)先級

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

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

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

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

④選取無人機數(shù)量最少;

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

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

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

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

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

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

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

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

5)方案效能評估模塊:對規(guī)劃方案進行收益和代價評估,供決策者參考;

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

7)內(nèi)部數(shù)據(jù)管理模塊:無人機的知識庫、數(shù)據(jù)庫,接收、存儲、發(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))由一個中央處理器控制全局,可以是由長機或者地面控制中心,這樣的好處在于使全局收益最高.但是,計算量大、計算時間長且對服務(wù)器性能要求也高,更重要的是無人機在突發(fā)狀況下不具備自治能力,就大大降低了無人機的安全系數(shù).

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

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

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

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

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

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

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

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

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

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

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

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

1.4.2 在線實時規(guī)劃

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

1.5 小結(jié)

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

2 任務(wù)分配

2.1 工作任務(wù)分配

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

2.2 編隊級目標(biāo)分配

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

2.2.1 聚類分析

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

2.2.2 K均值算法

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

K均值聚類算法的運算步驟[40]:

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

2)然后計算每組的中心,修改聚點,確定各組新聚點;

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

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

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

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

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

2.3.1 常見的問題模型

1)多旅行商問題模型

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

2)車輛路徑問題模型

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

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

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

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

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

2.3.2 常見的求解算法

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

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

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

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

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

2.4 小結(jié)

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

3 航跡規(guī)劃

3.1 路徑規(guī)劃

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

1)路標(biāo)圖法

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

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

2)單元分解

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

3)人工勢場法

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

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

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

3.2 航跡修正

3.2.1 平滑處理

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

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

3.2.2 安全距離

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

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

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

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

3.3 小結(jié)

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

4 總結(jié)與展望

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

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

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

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

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