無人機集群任務規劃方法研究綜述

賈高偉, 王建峰

(國防科技大學空天科學學院, 湖南 長沙 410073)

0 引 言

任務規劃是指在任務執行過程中對個體工作狀態及使用方法或步驟的規劃及安排,遍布于社會生活諸多領域,幾乎所有社會系統的運作都必須明確什么樣的任務該由什么樣的成員來完成。任務規劃理論是多類領域特殊任務規劃問題求解發展的結果。鑒于任務規劃之于群體運行的重要意義,長時間的研究使得該方面成果豐富。理論上講,任務規劃是一類多約束條件下的優化問題,從任務規劃理論的發展歷程看,20世紀60年代以前,主要的理論模型包括線性規劃問題及單純形方法[1]、指派問題[2]及匈牙利法[3]、整數規劃問題[4]及分支定界方法[5]等經典的任務分配理論。隨后受分布式系統發展的影響,任務規劃理論得到快速的發展,隨之而來的關鍵成果包括典型的0-1規劃模型[6]、圖論模型[7]、負載平衡模型[8]。20世紀80年代后,分布式智能任務規劃方法開始出現,該類算法對數學模型的依賴很小,借鑒生物習性,逐步形成一類優化方法。

無人機具有低成本、無人員傷亡、操作方便簡單、靈活可靠等優點,近年來發展迅速,各式各樣的無人機層出不窮。結合日益發展的網絡信息技術,促使了無人機集群的出現和高速發展。無人機集群技術已經演化為航空工業的核心技術之一,表現出巨大的應用潛力,尤其在軍事應用領域。類似于其他社會系統,無人機集群的任務規劃為無人機集群應用的核心技術,是指根據無人機集群的數量、要完成的任務及任務載荷情況的不同,對無人機集群所需完成的具體任務進行預先設定與統籌管理,決定著無人機集群的應用效能。因此,相關研究在全世界范圍內得到了廣泛持續的關注。從復雜程度上講,無人機集群是由多無人機進一步提升發展而來,無人機集群是多無人機的高階形式,二者的區別可以由表1來概括。

表1 無人機集群與多無人機的對比

無人機集群的靈活組織與運用,離不開科學的體系架構設計,不同的架構設計又牽引著不同的技術路線和方向,影響著無人機集群的任務規劃、協同決策與實際效益。概括來講,適合于無人機集群的控制架構包括集中式、分布式、集散式等多類[9]。

(1) 集中式:該體系的確立源自“單無人機-多無人機-無人機集群”的發展思路,是當前最直接、最成熟的集群架構模式,無人機集群接受單個或多個中心控制。該體系架構對無人機數據鏈帶寬、速率、功率以及可靠性提出了很高要求。

(2) 分布式:該體系類似于自然界生物集群,無人機之間地位平等,通過彼此信息交互,協同完成任務。該體系是一種朝“完全自主”方向發展的任務構型,對無人機機間協同能力要求很高。分布式體系下各無人機單元之間的通信信息量較大.

(3) 集散式:該體系結合了集中式和分布式的優點,利用分布式自治與集中式協作相結合的方式,來解決全局控制問題。該體系符合現階段集群技術發展現狀,在可預見的今后一段時間,可能成為常態的實用化體系架構。

鑒于任務規劃理論的多樣性以及無人機任務樣式的復雜性,截止目前,關于多無人機任務規劃技術的研究成果豐富[10],而無人機集群是多無人機的高階形式,對應的任務規劃技術將呈現更為復雜的技術特征,本文擬針對近幾年無人機集群的研究現狀,從兩個角度歸納無人機集群任務規劃技術的發展特點和關鍵方向。

1 基于邏輯與規則的多無人機任務規劃典型方法

基于人類知識所建立起來的邏輯與規則,是實現多無人機任務規劃的重要渠道,沿襲了分層遞階的思想[10],從頂層規劃到分層逐步實施,降低了問題的復雜性。該思路符合人類社會管理的一般規律,易于理解,成果豐富。典型的任務規劃方法也秉承了這一思想。

概括地講,多無人機任務規劃的內涵十分寬泛,可以包括但不限于任務目標分配、航跡規劃、任務載荷規劃、數據鏈路規劃、應急處置規劃等等。一般地,任務載荷規劃、數據鏈路規劃以及應急處置規劃等功能相對獨立,對無人機集群屬性的依賴度不夠強,比如有專用的傳感器使用規劃、鏈路配置規劃系統等。常見的做法是在無人機集群的任務分配與航跡規劃中將任務載荷、鏈路設置、安全飛行等因素作為規劃的約束條件。

因此,本文對多無人機(乃至無人機集群)任務規劃技術的介紹,主要從任務分配和航跡規劃兩個層次展開。任務分配與航跡規劃是無人機集群任務規劃中的關鍵環節,決定了無人機集群執行任務的時序關系,多無人機與多目標之間的映射關系,單架無人機的可執行航線等,確保無人機能夠安全適時地抵達任務區域并最大效能地完成任務。任務分配和航跡規劃共同奠定了無人機集群執行任務的基本能力基礎。

1.1 典型多無人機任務分配方法分類

無人機任務分配用于建立無人機與任務之間的關聯和映射關系,是多約束條件下的離散空間組合優化問題,其實施的關鍵是建立可數學表達的目標函數并有效地處理各項約束。本節從集中式任務分配和分布式任務分配兩個方面簡要地歸納相應的典型方法。

1.1.1 集中式任務分配典型方法

適合于多無人機集中式任務分配的數學模型主要包括:多旅行商問題(multiple traveling salesman problem, MTSP)[11],車輛路徑問題(vehicle routing problem, VRP)[12],多選擇背包問題(multiple choice knapsack problem, MCKP)[13],混合整數線性規劃(mixed integer linear programming, MILP)問題[14], 動態網絡流優化(dynamic network flow optimization, DNFO)模型[15],多處理器資源分配(multiple processors resource allocation, CMTAP)模型[16]等。這些模型一般可以推廣應用于無人機集群,但隨著無人機數量和任務類型增多,分配問題的描述將變得愈加復雜。

集中式任務分配求解方法又可以分為最優化方法和啟發式方法。其中,典型的最優化方法如圖1所示。整數規劃(integer programming, IP)法通過建立目標函數和約束條件的方法進行求解,矩陣作業法[17]、單純型法、匈牙利法、分支定界法等是常見的IP法,這一方法也演變出一類混合整數線性規劃算法[13]。約束規劃(constraint programming, CP)法由變量集和約束集兩者組成,變量集內的所有變量都有自己對應的值域,是求解組合優化問題的常用方法。圖論法通過圖示的方法把目標和接收任務的對象特征表征出來[7],利用圖論法在任務和系統成員之間建立匹配,網絡流模型和偶圖匹配模型是經典的圖論任務分配模型。一般而言,最優化算法具有描述簡潔、直接等特點,可以靈活調整約束條件來求解實際問題,具有理論最優解,但規模不宜過大,一般可用于無人機集群離線式任務分配。

圖1 部分最優化方法分類

啟發式方法的基本思想是在算法時間和求解結果之間進行調節,在能夠接受的時間內求得局部最優解或滿意解,具體分類如圖2所示。

圖2 啟發式方法分類

在啟發式方法中,列表算法基于優先權函數對任務處理次序進行排列,隨后分發給各成員[18];聚類算法將任務作為一個簇進行聚類,通過滿足任務簇與系統成員數達到一致[19]實現分配,兩者都有一定應用。智能類算法的應用相對比較普遍,尤其以遺傳算法、粒子群優化(particle swarm optimization, PSO)算法、蟻群算法為多。這幾類算法通常具有較強的穩定性,適合分布式計算機制、也能夠與多類其他算法結合,但缺乏嚴謹的數學基礎,沒有對應的深刻的、具有普遍意義的理論分析,對其機理的數學解釋薄弱,也缺乏規范化的、針對算法優化性能的評價準則。盡管如此,這些方法及其改進算法依然廣泛應用于無人機任務分配。

1.1.2 分布式任務分配典型方法

分布式任務分配的典型模型主要包括多智能體決策理論、類市場機制(合同/競拍)、分布式馬爾可夫、分布式約束等。多Agent理論[20]廣泛應用于機器人領域,其中一致性問題是多智能體協同控制的根本問題。隨著應用樣式的多樣化,多Agent理論衍生了很多分支,并取得了諸多成果,具體如圖3所示。

圖3 分布式任務分配模型及方法

針對智能體與不確定因素之間的矛盾,已有的常用算法包括博弈論方法[21]、分布式馬爾可夫法[22]、分布式貝葉斯方法[23]等。分布式約束可以形式化為一個約束網,網中變量有各自離散值域,且各自約束相互聯系,求解過程即是求出變量的某個組合使得所有約束值相加獲得極值[24]。分布式約束也可以看作是多Agent理論的分支應用。

類市場機制的方法是多無人機任務分配中應用廣泛的一種分布式方法,其核心處理是防止沖突,對每個問題的求解采用通信協商的方式解決。合同網方法[25]由發布者和競標者兩個角色,由“招標-投標-中標-確認”4個交互階段組成。而拍賣法[26]則是將要拍賣的物品用公開競價的方式轉賣給應價最高者。一個拍賣主要由參與方、拍賣品、收益函數和應價策略等要素組成。拍賣算法的演化算法也逐漸引起廣泛重視,如一致性包算法(consensus-based bundle algorithm, CBBA)[27]。

1.2 無人機航跡規劃的典型方法

1.2.1 單機航跡規劃方法

航跡規劃的作用在于為每架無人機執行所分配的任務建立可執行的航跡安排,其本質上是連續空間的路徑尋優問題,是任務規劃分層遞階策略的底層實現。從航跡規劃的發展歷程看,已有的典型規劃方法可以分為基于路標圖形的航跡規劃和基于格柵的航跡規劃等,此處進行簡要概括,具體如圖4所示。

圖4 部分適合于單無人機航跡規劃的典型方法

最優控制法[28-29]是將航跡規劃問題看作非線性、帶有狀態約束和控制約束的控制問題,進而求解得到符合實際飛行要求的規劃路徑。又可分為間接法和直接法,后者的應用更廣,其利用數值化將最優控制問題轉化為非線性規劃問題,典型代表有偽譜法[30]。

路標圖形法本質上是對規劃環境的采樣,是對規劃空間的一種壓縮處理[31-32];可以結合目標與規劃空間的威脅等因素構建多類型圖形,如Voronoi圖,概率路標圖(probabilistic road map, PRM)[33],可視圖和快速擴展隨機樹(rapidly exploring random tree, RERT)等[32],最后通過搜索算法得到合理路徑[34]。

柵格處理同樣是對連續規劃空間的離散化,由于現代數字地圖都是柵格化處理得到,因此基于柵格的航跡規劃方法發展迅速。A*算法是啟發式搜索算法,將搜索空間表示為網絡的形式,以網絡的中心點或頂點作為航跡點,搜索鄰域內代價函數值最小的航跡點,從起始點逐步搜索至目標點,最后逆向回溯當前節點的父節點完成航跡生成[35]。

利用優化求解方法獲得航跡規劃方面,人工勢場法算法簡明、實時性好、規劃速度快,在局部規劃和實時規劃領域應用廣泛[36],但主要問題是在復雜環境中容易產生局部極小值,在障礙物附近抖動或頻繁擺動。智能類優化法的優點是算法求解對初始解狀態依賴較小,能夠漸近收斂于全局最優解[37]。

在實際應用中,上述多類算法也可互相借鑒與融合應用,解決航跡規劃速度問題、動態性問題、航跡與載荷使用耦合問題等[38],例如Haider等人針對多無人機搜索與營救任務,采用Dijkstra算法和人工勢場算法結合的方法,完成靜態和動態規劃[39]。

1.2.2 多無人機協同航跡規劃

多無人機航跡規劃協同性的體現,大多針對特定的目標或者具體任務。例如,龐強偉[40]圍繞多無人機對多目標的協同偵察,依據K-means聚類算法完成目標集合的聚類,求解偵察序列,由偵察序列對應生成各無人機的任務航跡。胡超芳[41]針對多無人機協同追蹤地面移動目標的問題,基于分布式預測控制架構,引入多無人機之間避碰約束,求解有限時域內每架無人機的局部航跡。周德云[42]針對多無人機區域內協同打擊任務,強調“同時抵達”的時間和空間強約束環境,建立了基于多目標優化的航跡規劃方法。王道波等人[43]針對地面移動目標,考慮了傳感器安裝姿態及有效觀測模型約束,建立了基于化學反應優化理論框架的啟發式多無人機航跡優化策略,得到了具有更長的目標檢測時間的規劃方案。Shah[44]考慮無人機間觀測區域必須重疊、所有無人機同時抵達、無人機間滿足通信條件等約束,基于Pythagorean曲線完成了有障礙環境內的多無人機航跡規劃。Ema[45]針對市區環境內協同避障,通過無人機間的信息交互為其他無人機在線提供障礙信息,得到了一種基于人工勢場和全局規劃策略結合的多無人機航跡規劃策略。概括來看,多無人機航跡協同是由于所執行任務之間的耦合性牽引多機之間的時空協同。

2 多機任務規劃方法向無人機集群的拓展應用

2.1 無人機集群任務分配方法新發展

隨著無人機集群數量和任務樣式的增多以及協同性要求的提高,第1節闡述的多無人機任務分配典型方法適用性受限。無人機集群相對于多無人機,在任務分配上面臨的新的重要挑戰包括:模型的合理性與應用適應性需進一步拓展、任務分配的求解速度與動態可塑性要求進一步提升、亟需適應信息的不完整與不確定性。上述3個主要挑戰對應的科學問題如下。

2.1.1 分配模型的完善與復雜度之間的均衡

無人機集群數量規模的增大,要求求解算法的效率大為提升,這是分配模型需要完善的重要驅動力。進化類算法對數學模型依賴小,因而得到了持續研究和發展,對智能類算法的初始化、粒子編碼的改進是常見的應對思想。王婷[46]通過設計新的遺傳算子,對適應度值進行標定,避免了傳統遺傳算法在最優解附近擺動的現象。沈林成[47]根據PSO算法離散化映射方式,將離散PSO(discrete PSO, DPSO)分為基于連續空間的DPSO和基于離散空間的DPSO兩類模型,能夠用于求解集群高維復雜離散優化問題。朱德法[48]設計新的粒子群位置和速度更新過程。國博[49]對粒子分群處理與合并優化。Hoang[50]對無人機航向角進行粒子編碼等策略,都促使粒子群算法分配模型針對性優化以能夠適應大規模集群,加速了粒子收斂速度。此外,Vincent[51]和Ugur[52]結合硬件設備特點,實現了遺傳算法、PSO算法以及蟻群算法的并行化處理,也提升了進化速度。

無人機集群任務樣式的多樣性和特殊性,要求分配模型進行針對性與適應性拓展,結合任務屬性增加模型約束條件并維持求解復雜度是常見的處理思想。張耀中[53]針對不同偵察能力的無人機集群多任務區協同偵察,將達到時間作為強約束,結合分布式拓展一致性束算法,在多項式時間復雜度的層面實現了遍歷偵察任務規劃。林君燦[54]針對偵察/控制/打擊/評估一體化無人機集群作戰應用,在分配模型中增加時間窗約束,并利用混合整數線性規劃算法實現了集群離線式任務分配。嚴飛[55]針對多無人機協同搜索和同時攻擊的任務約束,引入協同粒子群、協同函數、協同變量,并結合合同網模型實現任務分配。羅德林[56]針對大規模無人機集群對抗任務,引入了規避不利目標、支援處于劣勢友機的功能約束,結合分布式博弈決策模型,實現了群對群對抗中的目標分配。Khaled[57]針對森林著火點監視與探測,引入無人機間沖突規避約束,以及無人機控制參量化、時間離散化等建模策略,豐富對無人機單機控制模型的描述,實現著火點目標的分配。

2.1.2 求解空間劇增條件下的快速收斂優化

滿足多目標條件下的共同優化是應對協同等級提高的新需求,無人機集群多目標任務分配使得求解空間大幅擴增。以智能類優化算法為例,加速進化進程和結構化減小解空間是常見的快速收斂優化思想。Farid[58]針對無人機群對群對抗,在減少視場區域和滿足規避動作的約束下,對比了多目標PSO算法、改進非劣分層多目標遺傳算法(non-dominated sorting genetic algorithm version 2, NSGA2)[59]、強度Pareto算法(strength pareto evolutionary algorithm version 2， SPEA2)、多目標進化算法(multi-objective evolutionary algorithm, MOEA)等的任務規劃性能。施展[60]基于量子粒子群算法,通過將粒子高斯變異改為混沌變異,增加粒子群的遍歷性和隨機性,提升了多目標分配收斂速度。王建峰[61]在量子粒子群算法中設計了多層編碼策略和約束調度方法,通過非支配解評估引導算法進化,兼顧了收斂性和分布性。韓博文[62]基于量子粒子群算法,通過佳點集構造產生初值解,基于量子變異和混沌因子拓展遍歷解空間,設置動態慣性引導前期全局搜索、后期局部精細搜索,最終實現在保證遍歷性的基礎上加速進化搜索。

實戰或者對抗背景下無人機集群的動態調整導致求解空間增加,并迫切需要分配算法的快速收斂性。集群任務分配算法應對動態調整的直接思路是在原有任務方案基礎上對局部任務進行重分配調整,當前主要的處理思想是約束動態重置對任務分配解空間產生非線性劇增。具體算法方面,Carlos[63]提出了一種通用的包括全局任務規劃和單智能體任務規劃的動態分配架構,以全局規劃-局部調整的策略支持實時在線的任務調整。史豪斌[64]提出了基于迭代自組織數據分析技術算法(iterative self-organizing data analysis techniques algorithm, ISODATA)約束聚類的多無人機動態任務分配方法,ISODATA是無監督分類機器學習方法的一種,克服了K-means聚類方法需要人為設定K數值的不足,能夠動態地進行類的合并與分裂,最后得到滿足動態性要求的任務方案。一致性競拍算法(consensus-based auction algorithm, CBAA)和CBBA是基于市場競拍策略的分布式任務分配算法[65],Noam[66]針對分布式時間敏感任務,將CBBA與部分重規劃策略結合,通過改變任務重規劃過程中重置任務數,在收斂速度和協調規模之間折衷,針對性重置最少的競拍任務,使得任務分配解空間同重置任務數和集群規模保持線性復雜度關系,在滿足任務約束的情況下大幅降低了運算量。

2.1.3 信息不完整條件下的模糊度量和優化分配

無人機集群的實戰對抗要求任務分配算法能夠在不確定因素(如態勢不明確、信息被阻滯、欺騙和干擾)存在的情況下完成高效的方案規劃。而集群數量規模的增大以及協同等級的提升,也放大了不確定因素的影響。該問題的關鍵處理思想是不確定度的建模與量化。陳俠[67]以目標價值收益、毀傷代價以及航程代價的不確定信息為依據,采用主觀賦值與客觀賦值相結合的方法確定指標綜合權重,利用區間數表示不確定因素,建立了不確定多因素下多屬性任務分配模型,將離散粒子群算法與區間數排序方法相結合,適應了不確定環境下的任務分配問題。任佳[68]提出了一種基于變結構離散動態貝葉斯網絡的決策模型,利用貝葉斯推理量化不確定度,得到當前時刻的任務決策。Le[69]將無人機集群動態環境下的非線性任務規劃問題轉換為差分凸函數規劃問題,并利用差分凸函數算法進行求解。Alqahtani[70]針對多無人機偵察任務,利用四叉樹表述不確定性,建立基于四叉樹和K部圖結合的分配架構,能夠在通信受限情況下完成任務分配。

2.2 無人機集群對航跡規劃的新要求

結合第1.2.2節多無人機航跡協同技術現狀的論述可知,在充分的協同任務分配基礎上,任務規劃對于無人機集群航跡層面的邏輯協同要求降低。無人機集群任務對航跡規劃的核心要求體現為:精確的時間協同與空間沖突消解。精確的時間協同是任務協同分配方案得以實施的關鍵保障,而沖突消解則是無人機集群安全可靠應用的基礎。需要說明的是,高精度的時間協同和空間沖突消解的應用范圍不僅限于無人機集群,因此下文的闡述,著重于對兩類技術的現狀總結。

2.2.1 航跡的高精度時間協同

高精度時間協同條件下的航跡規劃演變為有時間約束的路徑規劃,即4D路徑優化問題。相關研究分為離散4D航跡規劃和連續4D航跡規劃。前者是以一系列離散的航路點來控制航跡形狀并為航路點設置到達時間,后者以位置和時間為變量,并采用連續數學表達式表述4D航跡時空關系。

離散4D航跡規劃方面,Chaimatanan[71]將航跡規劃轉換為混合元啟發式優化問題,優化航線和設定出發時間,實現了4D航跡設計。Antonio[72]通過對航路點設置時間屬性,基于調整飛機速度策略滿足時間要求。丁強[73]在Tau-H運動策略基礎上,利用PSO算法形成全局航跡預測,隨后利用采樣間隔與沖突判斷雙驅動的滾動優化方法,實現航跡不斷更新。周青[74]將到達時間偏差引入到A*算法中的估價函數中,不斷擴展偏差最小的節點,同時加入速度調整策略進一步縮小時間誤差,滿足了到達時間要求。整體而言,離散4D航跡規劃方法具有直接、簡便、規劃效率高的優點,但是忽略了航跡點之間速度變化的過渡過程,通常會導致航路規劃的靈活性及航線精度降低。

連續4D航跡規劃方面,Goerzen[75]運用勾股速端曲線(pythagorean hodograph,PH)進行航跡規劃,基于可變參數的矢量場中參數的調整,實現向終點的收斂以達到期望的4D協同。Antonio[76]和Bousson[77]基于3次至5次樣條曲線近似的方法,提出了搜索兩個連續航點之間最短軌跡的算法,在區域監視的框架下實現了無人機的4D航跡規劃。概括地講,連續4D航跡規劃保證了時域的可微性和連續性,能夠提供更為光滑的航跡,且提供連續的速度和加速度,但通常航跡的表達式參數較多、形式復雜。

2.2.2 空間沖突消解

無人機集群飛行面臨空間沖突,盡管空間沖突的規避不完全由航跡規劃克服(控制層面也可發揮重要作用),但全面、有預案的無人機集群航跡規劃能夠大幅減小空間沖突概率。

在傳統的多機航跡規劃中,通常采用以安全飛行距離為半徑的“管道”來包圍航跡,保證多UAV之間不發生碰撞。這一處理思路同樣可以應用到空間位置較為松散的無人機集群。無人機間沖突消解流程一般包括沖突的預判/檢測和基于規則的規避。在預判/檢測方面,可以分為基于幾何形狀的確定性方法和基于預測的概率性方法兩類,判決標準分別對應于有其他物體進入無人機安全保護區或者飛行器間沖突概率超過一定閾值[78-79]。沖突消解的典型策略可以分為基于航線、基于勢場、和模型轉化等3類,如圖5所示。

圖5 部分空間沖突消解典型方法

航線法沖突消解簡單、直接,一般可以在時間維度消解,即調整無人機到達沖突位置時間;但在飛行器數量多、航線密集條件下應用受限[80]。勢場法中定義無人機目標為引力、空間沖突物為斥力,兩者合力作為無人機安全飛行方向,具有含義清晰、易于處理的特點,但應避免陷入局部極值。模型轉化類方法較為靈活、應用廣泛,將沖突消解問題轉化為在線預測控制問題或博弈問題。魏瑞軒[81]提出了基于差分進化(differential evolution,DE)算法和分布式模型預測控制(distributed model dictive control, DMPC)相結合的防碰撞控制策略,將編隊問題轉化為滾動在線優化問題,將碰撞約束納入代價函數。Kurik[82]將沖突消解轉化為基于一致性編隊控制問題。茹常劍[83]提出將無人機碰撞規避問題轉化為兩方博弈問題,建立了無人機間運動學模型,實現了基于認知博弈制導的防碰撞方法[84]。Senthil[85]在無人機集群協同偵察應用方面,將沖突消解轉化為速度空間的速度障礙問題,在保證偵察覆蓋范圍的條件下實現了無人機間動態避障,其前提是假定無人機能夠在很大的范圍內安全調整速度。

2.2.3 無人機集群航跡規劃的難點

整體來看,當前有時間約束的路徑規劃以及多機間沖突消解方法的技術現狀尚不完全適應于無人機集群。其一,無人機集群數量大、編隊密集等約束對連續4D航跡規劃的精確度和實時性提出了挑戰。其二,無人機集群數量大,以安全距離(區域)為約束的分割會限制集群的密集程度,基于概率的沖突檢測處理也面臨巨大計算壓力。其三,從時間維度看,無人機集群航跡可以存在交疊,當任務類型或協同要求更復雜時,基于局部調整的沖突消解容易引入新的沖突。滿足無人機集群應用的航跡規劃問題仍需要持續關注和深入研究。

3 基于集群智能涌現機理的任務規劃方法

與秉承“自上而下”的思路研究集群技術相對應,“自下而上”思路研究集群技術也逐漸引起研究學者的廣泛興趣,該類技術的突出特點是對無人機集群的數量不敏感,而這一優勢是“自上而下”式集群技術所缺乏的。

從生物、數學、計算機、控制、機器人等領域看,集群的出現和研究已經歷時很久,對集群的關注重點包括自然界中的鴿群、魚群、蜂群、狼群等群居動物[86],并不斷探索集群現象產生的原因及其衍生的工程應用[87-88]。研究發現,動物集群一般具有臨近交互性、群體穩定性、環境適應性。動物行為學表明可以通過個體間簡單行為規則的合作產生復雜有序的集體行為。無人機集群技術的另一重要研究思路,即是基于生物集群行為的模仿,逐步向群體決策和認知理論發展,最終實現飛行的智能、決策的智能,以及集群的智能。無人機飛行的智能化是實現無人機決策智能和集群智能的基礎,而集群協同智能化的終極目標是無人機集群的完全自主[89]。

3.1 生物集群行為的描述與建模

Boid模型[90]、Vicsek模型[91-92]以及Couzin模型[93]是描述集群行為最為常見的3種模型。Boid模型于1986年由美國科學家Reynolds提出,基于靠近、對齊和避碰3條規則,假設每只鳥只能觀察到其周圍固定范圍內的個體,就可以在計算機中復現出自然界中鳥類等動物的集群現象、模擬其群體運動。Vicsek模型于1995年由匈牙利物理學家Vicsek及其合作者從統計力學的角度提出,通過改變群體密度以及噪聲強度,對集群行為進行定量分析。Conzin模型將個體的感知區域由內而外分為排斥區域、對齊區域和吸引區域,3個區域互不重疊,分別對應群體中分離、速度一致和聚集規則。這3類模型構成了現有集群行為理論研究的重要基石,為后續集群研究提供必要的理論架構、分析工具和方法支撐。近年來Jadbabaie[94], Tanner[95], Olfati-Saber[96]以及Levine[97]也提出了新的群集模型。

共識主動性是生物群體中的一個核心概念:代表生物個體自治的信息協調機制,個體之間間接協調,無需任何集中規劃以及直接通信即能完成復雜智能活動。典型的例子是:螞蟻的大腦或基因中并沒有巢穴建造的計劃、組織和控制機制,個體間也沒有直接的交流,但是螞蟻個體通過識別其他螞蟻留下的信息素,達成共識,共同完成了復雜和精致的蟻巢建造[98]。

在集群行為模擬與驗證方面,Mataric[99]研制的The Nerd Herd系統被應用在多機器人學習、群體行為、協調與協作等方面。James[100]基于“在多機器人上進行并行算法運算的復雜性度量項目”研制的多移動機器人系統,能夠開展大量多機器人行為協調算法設計以及性能預測研究。此外,典型系統還包括Kube[101]研制的 Collective Robotics系統以及Dorigo[102]開發的SWARM-BOTS系統。

實際的無人機集群系統方面,近年來引起廣泛關注的包括美國國防部高級研究計劃局(Defense Advanced Research Projects Agency, DARPA)支持的“小精靈”項目、美國海軍支持的“郊狼(LOCUST)”計劃、美國海軍參與研制的“山鶉”項目等[103],但這些項目的技術體制和方案細節并未公布。所見報道的其他無人機集群系統包括:匈牙利羅蘭大學Vicsek團隊于2014年實現10架四旋翼飛機在室外的自主集群飛行[104-105],該項目在任務決策層利用了生物集群行為機制,四旋翼飛機與臨近個體之間進行信息交互,實現了在全球定位系統(global positioning system, GPS)噪聲、通信延遲環境下的自主決策和穩定飛行,包括區域內碰撞規避、聚集、隊形保持和集群目標跟蹤。Chung團隊在2015年實現了一人控制50架固定翼飛機的集群飛行,無人機按照主從模式飛行,其工作重點是無人機操控權的轉移以及無人機自主飛行和決策[106]。

3.2 基于集群智能涌現的規劃決策

生物群體在去中心化、鄰近個體信息交互、整體自組織等方面的特點與無人機集群追求目標一致,因此仿生研究是無人機集群任務規劃決策的重要研究方向之一[107-108]。對應地,基于集群智能的無人機集群任務規劃的內容包括但不限于威脅的判斷、目標優先權的排序、任務的動態分配與調度、飛機航跡的規劃與任務載荷的協調等[109],且需要重點考慮多機之間邏輯與行為沖突消解?；诩褐悄苡楷F的無人機集群任務規劃的一般過程可以表述為:無人機個體收集并處理外界信息進而更新個體知識以適應環境,再同集群內其他個體交互,完成經驗交互和社會學習,實現共同進化,并執行復雜有序的集體行為[110]。而智能涌現在任務規劃方面的表征體現在3個層面:單機、群集以及任務,分別對應于無人機單機對環境的學習與適應,無人機集群群集行為的形成,以及無人機集群對復雜多樣化任務的完成。

具體進展方面,Su[111]提出一種具有多個變速度虛擬領導者的多智能體蜂擁控制算法,從理論上證明了該方法可以準確跟蹤對應的虛擬領導者。周子為[112]分析研究了雁群長途遷徙過程中的編隊飛行機制,并設計實現了一種仿雁群行為機制的多無人機緊密編隊控制與編隊變拓撲重構方法。段海濱[113]提出一種基于注意力機制的群集模型,能夠通過刺激單一或者多個個體影響群體快速一致性反應。王訓[21]提出基于合作博弈的智能自主聚集策略,以實現群體聚集為“合作目標”,以降低自身消耗為“競爭目標”開展博弈,最終引導群體系統出現聚集行為。段海濱團隊[98,114]結合狼群的等級特性與社會組織,建立狼群合作狩獵運動模型,提出一種基于狼群行為機制的自主編隊控制方法,設計了基于狼群層級行為機制的編隊保持控制器。此外,該團隊[115]針對鳥群運動中拓撲交互、策略切換等群集行為機制,映射建立了具有動態環境適應性的無人機集群協調決策控制模型。

除了模擬群體行為建立映射決策模型,研究學者的另一種思路是試圖提出通用的自組織集群模型架構,例如美國空軍試驗室的Nowak面向戰場環境中集群任務的動態性、部分可觀性提出了基于集群行為激勵的通用控制等級模型[116],如圖6所示。

圖6 基于自組織涌現的通用控制等級

Antonio[117]針對分布式目標定位,提出了，群集激勵進化(flocking, stigmergy, and evolution, FSE)算法,基于共識主動性用潛在目標吸引無人機,基于聚集特性保證成員間協調觀測,基于進化特性來適應動態環境,如圖7所示。其他應用場景方面,Wallar[118]基于集群行為建模,設計實現了無人機集群對某敏感危險區域的監視。Howden[119]基于聚集和共識主動性,在無人機局部通信的約束下,實現了無人機集群對森林火場的自主監視。

圖7 FSE算法結構圖

總的來看,受當前研究水平限制,基于生物集群行為學習與映射的集群任務規劃決策更適合于組織較為松散的簡單反應型任務,是否能夠滿足高端無人機在行為更為嚴格受限條件下的任務執行,還有待深入研究和驗證。但這是一個充滿挑戰與希望的領域,有潛力產生涌現式的集群智能,發揮不可替代的作用,值得持續深入的研究。

3.3 與基于邏輯規則類任務規劃的區別

上文分析了基于邏輯規則與集群智能涌現的兩類不同的無人機集群任務規劃方法,為便于對比,在表2中列出了二者的區別。

表2 兩類方法特性對比

4 無人機集群任務規劃技術的發展方向

從第2節和第3節的內容看,無人機集群任務規劃的方式方法多樣,集群任務規劃技術的研究既有廣泛化、理論化等優勢方面,也存在重復化和低端化的不足。以無人機集群實際能力建設為牽引,圍繞無人機集群系統的應用前景,梳理無人機集群任務規劃技術的發展方向如下。

4.1 多約束下的集群系統群智涌現式規劃理論

無人機集群任務規劃需要考慮單個無人機的動力學和運動學約束、輸入飽和及狀態有界約束、模型非線性及不確定性約束,此外還需要滿足多無人機到達目的地的時間和空間協同約束,以及數據鏈系統連通性方面的網絡拓撲約束等?；谶壿嬇c規則的任務規劃模型在集群數量劇增的情況下很難以較低的復雜度準確描述多約束條件以及協作機理,迫切需要研究多約束條件下基于集群智能涌現的系統建模和分布式協同控制機理。

4.2 基于深度學習和分布式優化的任務規劃技術

在面臨時變任務和突發威脅條件下,無人機集群的實時協同規劃與決策在當前和未來一段時間內將是集群任務規劃的難點。不確定、動態環境下的任務規劃機理上依賴于推理判斷與優化求解,鑒于深度學習方法在推理的其他應用方面展現出極大優勢,將深度學習與分布式優化相結合,在提升無人機集群任務協同分配和航跡規劃的實時性和最優性方面具有巨大潛力。

4.3 局部信息反饋條件下的自組織航跡協同技術

無人機集群航跡規劃與調整要能夠滿足既定分配任務,又要能夠自主防碰撞(由控制層面進行的規避技術不在本文闡述范圍內),而分布式控制下的無人機集群個體僅同局部臨近節點進行信息交換和反饋,要兼顧集群系統的任務使命和智能個體的多約束條件,迫切需要研究局部信息反饋條件下的自組織航跡協同技術,能夠應對突發威脅并具備一定的容錯和自愈能力。

4.4 通信受限時邏輯與群集行為結合的規劃技術

邏輯規則與集群智能涌現相結合的規劃決策模式能夠增強無人機集群在通信受限環境下的適應能力,在群間自組織通信正常情況下可采用基于邏輯/規則指派或動態調整任務規劃方案,在電磁干擾導致通信受阻,可以結合集群個體間底層協調,保持穩定的隊形及功能,增強集群魯棒性。

4.5 無人機集群系統總體設計技術

作為“先進的任務規劃技術能夠更好地發揮無人機集群能力”的逆問題,設計滿足一定功能的無人機集群系統具有重要現實意義,無論是基于邏輯與規則,還是基于集群智能涌現,均需建立個體能力與集群整體效能的關系模型,形成個體能力與集體狀態之間的量化聯系。并根據系統的性能指標要求,完成個體設計、結合(改善)個體間驅動與激勵模式組織應用,形成實用的無人機集群系統。

4.6 無人機集群任務規劃方案的量化評估技術

對于基于邏輯與規則的無人機集群任務規劃,目標函數是評價任務方案優良與否的基石,全面的目標函數能夠度量任務方案的最優性,但目標函數復雜度的提升將大幅擴增優化解空間,影響求解效率,甚至無法求解。而基于集群智能涌現的任務規劃決策是開放式的架構,缺乏量化的能力評價。迫切需要開展無人機集群任務規劃方案的應用效能評估技術[120-121],在無人機集群執行任務前形成規劃閉環。

5 結 論

基于邏輯與規則的集群任務規劃技術的研究成果豐富,可以直接應用于現有無人機集群系統;對應的研究大多是多無人機系統任務規劃技術針對無人機集群系統的拓展和適應性調整,尚不能滿足在信息不完全、環境不確定、高動態調整等對抗環境下的集群任務規劃要求,以無人機集群為對象的任務規劃建模與理論方面缺乏足夠創新。此外,基于集群智能涌現的任務規劃決策受當前研究水平限制,尚不能靈活、機動、高效、可控地完成復雜性耦合性強的集群任務。無人機集群任務規劃技術仍需要持續深入地研究與發展。

本文總結了無人機集群任務規劃技術潛在發展方向，對于全面了解無人機集群任務規劃研究現狀具有良好的參考意義。