基于無監督學習離散鴿群優化的多無人機偵察任務分配

龍 泓,魏 晨,段海濱

(北京航空航天大學自動化科學與電氣工程學院,北京,100083)

無人機正在智能搜索、區域監測、環境檢測和營救任務[1]等軍事和民用領域扮演著越來越重要的角色。然而,受限于其自身的大小和能力,單獨的無人機很難完成一些復雜的任務,因此多無人機協同完成任務已經成為研究熱點。

相關多無人機集群協同規劃執行偵察任務分配問題,可以分為任務分配的原則、模型以及算法3方面。任務分配的原則主要有路徑合理、路徑最優、算法完備以及高效及時等等[3-5]。常用的任務分配模型有混合整數線性規劃(mixed integer linear programing,MILP)[6]、多旅行商(multiple traveling salesman problem,MTSP)[7]、多車輛路由(multiple vehicle routing problem,MVRP)[8]、協同任務分配(cooperative multiple task assignment problem,CMTAP)[9]等模型,主要根據具體問題進行針對性的構建。在算法求解方面,常采用集中式和分布式2類算法。文獻[10]采用改進的多目標蟻群優化算法解決多機協同任務分配問題,注重決策代價的復雜性和算法的優越性,通過質點模型降低了分配代價的復雜性,減弱了實際無人機飛行軌跡的適用性。文獻[11]將任務分配問題描述為MILP問題,考慮無人機燃料約束和地形約束等情況,提出一種高效的啟發式結構方法生成可行解,雖然MILP模型具有較強的可擴展性,但此模型適合解決小規模問題。文獻[12]分析了許多能描述成簡單的MTSP模型的問題,考慮資源約束和任務序列限制,提出一種改進的兩部分狼群搜索算法,在時間和任務完成度上有較好的優勢和效果,但是在經典的MTSP問題中,路徑的長度表示兩個點之間的最短歐式距離,因此并沒有考慮到無人機自身的運動學約束和機載傳感器的偵察范圍對目標的偵察情況[13]。文獻[14]基于相鄰局部通信的分布式拍賣算法,實現了多無人機協同任務分配問題的優化求解,但是每架無人機使用基于貪婪策略或局部通信的任務分配方法獨立選擇偵察路徑,常常面臨信息一致性和任務一致性的挑戰,無人機群之間的沖突也會隨著數量的增加而導致協作效率降低。以上研究主要考慮了多種分配模型下基于集中式和分布式兩類算法的無人機偵察任務分配問題。分配模型過于簡化,現有分配算法對處理規模較大的任務分配問題會造成任務負載不平衡,因此建立符合多無人機實際運動學約束的任務分配模型以及采用能夠消解任務負載沖突的求解算法尤為重要。

本文針對上述問題,以偵察目標數量和位置在一定時間內保持不變的確定性環境為任務分配背景。為了考慮無人機的運動學約束,引入了Dubins曲線模型[15-16],這種問題模型可以描述為多Dubins旅行商問題(multiple Dubins travelling salesman problem,MDTSP)[17]。考慮執行偵察目標和無人機集群規模較大的協同偵察任務,偵察點的拓撲圖會很大,邊很多,并且在偵察過程中,不同無人機之間所偵察的目標點數目差距過大也會造成相應的負載不平衡,從而導致無人機集群偵察的工作效率低下,本文提出一種引入無監督學習的柔性分組策略的離散鴿群優化方法,仿真對比實驗和三維態勢仿真平臺實驗證明,所提出的算法在計算成本和沖突消解方面更具優勢。

1 多無人機偵察任務分配問題模型設計

1.1 基于Dubins曲線設計無人機模型

以二維戰場環境為背景研究多無人機協同偵察任務分配問題,主要在無人機群頂層的決策層面,而且考慮復雜的六自由度無人機模型將使該任務分配問題難以求解,因此將Dubins曲線模型引入到無人機模型當中。該模型在許多協同任務分配研究中取得了較好的應用效果,但是仍需要對無人機的運動學約束和載荷約束做出以下假設：

1)在執行任務的過程中,無人機群與靜止偵察目標之間不存在戰場對抗的過程,僅僅考慮無人機群的偵察過程,不會發生無人機戰損和丟失的情況。

2)無人機群執行任務時已處在一個較穩定的狀態,即其工作時飛行速度和海拔高度趨于恒定。

3)機群中各架無人機在偵察過程中飛行在不同且恒定的海拔高度,內部不會發生機間碰撞。

4)假設無人機攜帶了足夠的載荷儲備,且飛行時間足夠滿足完成分配的偵察任務。

根據以上假設首先建立無人機群集合U={U1,U2,…,Un},將無人機簡化為3個狀態量(x,y,ψ)表示,對于第i架無人機Ui,其運動學模型可以表示為：

式中：x與y為無人機的位置;ψ為無人機的偏航角;v為無人機的速度,在此為常值;ρmin為無人機的最小轉彎半徑;c為控制輸入,|c|≤1。c>0時,表示無人機逆時針轉彎;c<0時,表示無人機順時針轉彎;當c=0時,表示無人機沿著原來的方向直行。

在無人機通過2個目標點之間的路徑時,在Dubins模型限制下,可以得到所有可能的最佳運動方式集合：

D={LSL,RSR,RSL,LSR,RLR,LRL}

(2)

式中：D表示無人機可以選擇的運動方式集合。如圖1所示,L表示逆時針轉彎,R表示順時針轉彎,S表示沿著原來的方向直行。

(a)RSR

1.2 偵察目標與傳感器模型

偵察目標為靜止的點目標T={T1,T2,…,Tm},例如典型的待偵察的建筑物和地面車輛等[17]。因為無人機群在恒定高度飛行,且與地面平行,所以假設其傳感器偵察范圍為一穩定的圓形范圍,視場半徑為R。當無人機穿過該目標點時,意味著已對其執行了偵察過程。具體的概念模型見圖2。

(a)傳感器模型

1.3 基于無監督學習的無人機群柔性分組模型

從無人機模型和目標模型已知,有n架無人機,集合為U,m個待偵察的目標點,集合為T。在集合T中包含的m個對象,每個都會有h個維度的特征。為了降低航跡重疊度以及減少迭代時間,并且有效地應用于從一個中心起始位置出發的無人機群,采用K-means余弦相似度聚類的策略進行柔性分組[18],以下是具體過程,如圖3所示。

圖3 無人機群柔性分組模型示意圖

1)首先隨機產生數據大小在范圍內的n個對象作為初始的類簇中心點C={C1,C2,…,Cn}。

2)將m個對象根據對象之間的余弦相似度聚集到指定的n個類簇中,并且每個對象只能存在于被指定的n個類簇中的一個。

3)然后通過式(3)計算每個對象Ti到每個聚類中心Ck的余弦值。

由于在二維戰場對靜態目標點的偵察背景下,每個對象僅有2個維度的特征,因此式(3)又可簡化為式(4)：

cos(Ti,Ck)=

4)通過比較式(4)計算出的余弦相似度,得到余弦相似度類似的新的k個類簇S={S1,S2,…,Sk},通過式(5)重新求得每個類簇中的類簇中心。

(5)

式中：Ck為新的類簇中心;Ti為屬于類簇Sk的第i個對象;n(Sk)為類簇Sk的元素個數。

5)不斷重新迭代分配數據樣本和類簇中心,直到總迭代次數達到一定值或者類簇中心的位置變化趨于穩定,此時輸出各組的目標點。

1.4 偵察任務性能指標設計

在執行偵察任務的過程中,為了能夠均衡分組,優化各無人機任務之間的負載差異,最小化分組代價,實現偵察目標點的均衡劃分,得到無人機偵察的最優覆蓋占位,從而在最大效費比的情況下對目標點進行偵察。采用偵察路徑的總長度和各無人機之間的路徑標準差來評價該任務完成的效果。

在每個柔性分組的集合Sk中無人機執行任務都需要滿足任務分配模型約束：

(7)

每個分組Sl中的代價函數通過無人機偵察其中所有的目標點的Dubins航程來決定,假設分組中有p個目標點：

(8)

式中：Jl為無人機偵察完所有在分組Sl中的目標點所需要的代價;D0,1為無人機從起始點到第一個目標點的Dubins距離;Dp,0為無人機從最后一個目標點到起始點的Dubins距離。據此可以得到整個偵察任務的代價函數：

(9)

針對偵察目標點數目較多,無人機集群之間對所分組的目標點數目以及總航程差異太大會造成無人機之間的工作負載不平衡,時間上的不協同問題從而降低工作效率。因此采用方差和時間差來評價無人機集群之間的負載平衡和多機協同情況：

(10)

(11)

2 基于改進離散鴿群優化的任務分配算法

鴿群優化算法是模擬鴿子歸巢行為設計的智能優化算法,通過地磁場信息、太陽高度信息和地標信息3個導引工具使得鴿子更易歸巢[20-22],可以有效解決參數優化和數值設計等一系列問題,通常在函數極值問題等連續性優化問題上具有一定的優勢。但是對于復雜的組合優化問題,例如本文中的MDTSP問題,鴿群優化算法的連續性限制了它的使用范圍。針對以上的問題,采用全局編碼交叉與變異的方法將指南針算子和地標算子離散化引入多無人機偵察任務分配的組合優化問題中。

基于改進離散鴿群優化的任務分配算法具體實施步驟如下：

式中：xj≠xk表示需要保證無人機對偵察目標不會重復偵察;x1,x2,…,xp表示偵察目標點的一段排序,表示無人機將從x1點依次偵察直到xp點。

Step2基于全局編碼交叉與變異的地圖和指南針算子的設計,連續型的地圖指南針算子的迭代公式為：

(12)

Step3基于全局編碼交叉與變異的地標算子設計,連續型的地標算子的迭代公式為：

(14)

Nt=ceil(N(t-1)/2)

(15)

3.2 無監督學習離散鴿群優化多機任務分配實現流程

根據前文搭建的多無人機Dubins模型、點目標模型以及傳感器模型,然后隨機產生一系列待偵察的目標點數據集T,并且進行無監督學習的柔性分區,主要過程包括先從數據集T中隨機選擇n個樣本作為類簇中心,通過計算所有的目標點與類簇中心的余弦相似度進行分區歸類,在此過程中不斷的進行重復計算類簇中心直到迭代次數達到Nmax或者類簇中心位置基本穩定,則輸出分組集合S以及類簇中心集合C,如圖4所示。

圖4 基于無監督學習離散鴿群優化的多機偵察任務分配算法流程

3 仿真實驗分析

3.1 實驗設計

為驗證本文所提出的無監督學習離散鴿群優化算法的有效性,設計仿真實驗場景為10架無人機和50個待偵察的目標點,在200 m×200 m的范圍內進行偵察,并且與傳統用于任務分配任務的遺傳算法進行仿真實驗對比。給定無人機的初始航向角均為0°,速度恒為10 m/s,最小轉彎半徑為6 m,初始位置均在原點,表1與表2分別表示本文算法和文獻[17]遺傳算法參數設置。

表1 無監督學習離散鴿群優化算法參數設置

表2 遺傳算法參數設置

本文算法和遺傳算法的無人機集群協同偵察任務分配單次運行結果如圖5和6所示,圖中不同顏色的軌跡代表著每一架無人機的飛行航路,圖中,通過無監督學習的柔性分區策略的引入,將不同航跡下的分區目標點用與航跡相同的顏色標出,性能指標如表3所示。由仿真結果可以發現,兩種算法已經全部完成了對目標的偵察任務,并且在本文算法中因為考慮了柔性分區策略,在航跡重合度、負載沖突以及工作效率上更具優勢。

表3 2種算法單次運行在性能指標參數對比

(a)二維視圖

多機偵察任務分配在三維態勢仿真平臺上進行實驗驗證如圖7所示,圖7中紅色的軌跡曲線是無人機的航跡,綠色的部分代表著無人機攜帶的簡化傳感器模型,通過觀察在線仿真的執行情況,無人機群通過各自的航跡完成所有目標后回到起始點,執行完全部任務,滿足無人機飛行的整體態勢要求。

(a)本文算法

如圖8所示,基于無監督學習離散鴿群優化算法在每架無人機的航跡長度上均優于遺傳算法計算的航跡長度,并且考慮負載不匹配問題,100次迭代過程后計算兩種算法下各種性能指標的值如表4所示。在任務完成率都達到100%時,本文的算法無論是在航程平均值、航程方差、航程最大值以及所用時間上都不同程度的優于遺傳算法。特別是在所用時間上,引入柔性分組策略和采用改進的鴿群算法相結合能夠在一定程度上比傳統方法極大地提高工作效率。

表4 2種算法運行100次在性能指標參數對比

圖8 2種算法運行100次時各無人機的航程距離對比

4 結語

面向多無人機協同偵察任務分配的任務場景,本文首先分析研究了多機協同偵察任務分配模型、適用于無人機的Dubins模型、傳感器模型以及目標模型,提出了一種無監督學習策略的離散鴿群優化算法,以解決無人機集群協同偵察任務負載不匹配、工作效率低下等問題。三維態勢視景仿真平臺對比仿真實驗結果證明,文中方法與傳統方法相比,在計算成本、航程距離和沖突消解方面均具有一定的優勢、可行性和有效性。