多目標群多基地多無人機協(xié)同任務規(guī)劃*

劉 暢，謝文俊，張 鵬，郭 慶

(空軍工程大學裝備管理與無人機工程學院， 西安 710051)

0 引言

無人機任務規(guī)劃的目的是找出一條從基地到目標點并且滿足某種性能指標的最佳飛行航線[1-2]，在眾多約束條件下完成各項任務。任務分配[3-4]和航跡規(guī)劃[5-6]是任務規(guī)劃中的核心問題。無人機任務規(guī)劃問題可由智能優(yōu)化領域的許多方法進行求解，目前研究的方法有蟻群(ACO)算法、遺傳算法(GA)等。GA作為群智能算法的典型代表，已廣泛用于無人機任務規(guī)劃領域。文獻[7]在求解過程中由于其搜索的隨機性，產(chǎn)生許多劣質(zhì)搜索過程，導致求解效率和精度不高。文獻[8]中運用ACO算法很好地實現(xiàn)了多無人機協(xié)同任務規(guī)劃，ACO算法威力的發(fā)揮取決于數(shù)學問題的規(guī)模。

文中針對多目標群多基地多無人機協(xié)同任務規(guī)劃問題，同時考慮任務分配和航跡規(guī)劃，將共同分配策略引入任務規(guī)劃中來，同時提出“雙重優(yōu)化”思想，運用貪心算法對群內(nèi)路徑進行第一重優(yōu)化，對構建的基地和目標群中心位置坐標的中心無向圖用PFSGA進行第二重優(yōu)化。為提高搜索速度和解的精度，PFSGA通過引入最優(yōu)搜索算子對種群進行快速搜索，尋找最優(yōu)解。

1 問題描述

某無人機作戰(zhàn)部隊有4個無人機基地且每個基地均裝備2架R系列無人機，主要遂行偵察任務，需要完成10個目標群的偵察任務，每個目標群包含數(shù)量不等的地面目標，巡航飛行速度為200 km/h，最長巡航時間為10 h。

為了使問題簡化，文中作如下假設：

1)每架無人機都在固定的巡航高度飛行，從而無人機之間沒有沖突；

2)飛行空間沒有任何限制、燃油充足；

3)所有目標的優(yōu)先級都是一樣的，即沒有執(zhí)行次序的差別；

4)無人機經(jīng)過目標，任務即完成。

基于以上假設可把無人機任務規(guī)劃問題簡化為二維平面上的旅行商問題進行求解，即無人機偵察時需遍歷各目標群和各目標群內(nèi)的節(jié)點。各目標群中心位置坐標和各無人機基地坐標如圖1所示，黑色實心原點為各目標群中心位置坐標，方塊為各無人機基地坐標。

圖1 基地和目標群中心位置坐標

2 多目標群多基地多無人機任務規(guī)劃數(shù)學模型

2.1 各目標群內(nèi)任務規(guī)劃數(shù)學模型

Dantzing等人在1959年提出TSP問題，并將其用數(shù)學方法進行描述[9]。TSP問題描述的是某旅行者由起點出發(fā)，遍歷各需求點之后，最后再回到起點的最低代價[10]。文中在求解中，需從某點出發(fā)，遍歷所有目標群中的節(jié)點，但不需回到原點，因為無人機完成一個目標群的偵察將會立即前往下一個目標群進行偵察。即在給定圖G=(V,E,W)中，其中V為頂點集合，V=n，n為各目標群含有的目標數(shù)目，E為邊集合，W為邊權函數(shù)，求集合{1,2，…，n}的一個全排列使得下式最小。

(1)

TSP問題求解有多種方法，如蟻群算法[11]、模擬退火算法[12]、PSO算法[13]等。文中采用貪心算法求解。首先構造距離矩陣，任意節(jié)點到自身節(jié)點的距離為無窮大，借助距離矩陣將TSP問題求解簡化，在第一行找到最小項a[1][j]，從而跳到第j行；再跳到第j行最小值a[j][k]，再跳到第k行進行查找，以此類推。然后構造各行、各列允許數(shù)組，即row[n]={1,…,1}，column[n]={0,1,…,1}，其中1表示允許訪問，即該節(jié)點未被訪問；0表示不允許訪問，即該節(jié)點已被訪問，如果該行該列不允許訪問，則跳過該節(jié)點訪問下一節(jié)點。

由于已有TSP問題的求解算法不能在多項式時間內(nèi)得到最優(yōu)解，已經(jīng)被證明是一個典型的NP-hard問題[14]。故無需證明其貪心選擇性質(zhì)，只需找到近似解，并在多項式時間內(nèi)結(jié)束。由于目標群中目標點的個數(shù)較少，因此求解速度較快，并且能得到最優(yōu)解，即初步的最佳路線。

由于無人機在偵察時有一定的偵察范圍，實際上只需要初步的最佳路線所包含的目標點在有效偵察區(qū)域即可。此外，為減少無人機轉(zhuǎn)彎次數(shù)，需要對路線做相應的平滑處理以滿足實際需要。根據(jù)偵察機有效偵察范圍，做出某一目標群中各個目標的有效偵察區(qū)域，如圖2所示。

圖2 各個目標的有效偵察區(qū)域圖

為偵察到所有目標，只需要以一定的角度到達有效偵察范圍即可。故此問題的優(yōu)化轉(zhuǎn)換為求經(jīng)過所有圓域的最少線段數(shù)。采用下述算法對初始路線進行優(yōu)化。

①根據(jù)TSP問題得到的解，從初始點到終點，依次選取3個點A、B、C，通過3個點構建三角形ABC；

②判斷B與AC的距離是否在有效偵察范圍內(nèi)，如果在有效范圍內(nèi)，則去掉B點，如果不在，則整體往下推移一個點；

③如此反復，直到最后無法縮減；

④最后沒有被去掉的點，即為優(yōu)化后的路線。

對于飛機轉(zhuǎn)彎所多花的時間，根據(jù)文獻[15]提出的Ω形轉(zhuǎn)彎方法，計算額外時間花銷，每個轉(zhuǎn)彎多出3.2 km，換算出一個轉(zhuǎn)彎補償?shù)臅r間為0.016 h。按照上述算法，無人機在偵察完所有目標需要轉(zhuǎn)彎的次數(shù)為6次，則轉(zhuǎn)彎補償?shù)臅r間為0.144 h。根據(jù)各自的路線解算得出偵察各目標群所花的時間(h)如表1所示。

2.2 目標群間無人機任務規(guī)劃數(shù)學模型

2.2.1 任務共同分配策略

共同分配是將共同分發(fā)任務策略引入到任務規(guī)劃中來，指具有指揮權的大型無人機基地主導的協(xié)作型任務分配，即由具有指揮權的大型無人機基地統(tǒng)一集中任務，再將任務分配給參與合作的無人機基地，它們共同協(xié)作完成任務。共同分配策略具有如下優(yōu)勢：①任務由多基地配合完成，可減少一個基地需完成任務的數(shù)量，確保所有任務順利完成；②可實現(xiàn)戰(zhàn)場態(tài)勢的共享與快速反饋，更好的適應未來戰(zhàn)場需求。

2.2.2 目標函數(shù)及數(shù)學模型

無人機在執(zhí)行偵察任務時，需保證無人機滯留防御方雷達有效探測范圍內(nèi)的時間總和最小[16]，才能提高無人機的生存概率，即無人機從基地起飛到回到基地的總時間最少，由于R系列無人機全程勻速飛行，時間與路程成正比，故可以令無人機的飛行路徑總長最短。目標函數(shù)的優(yōu)化包括總路徑代價和多基地協(xié)調(diào)調(diào)度合理化代價。

假設4個基地向N個目標群(編號為i=1,2,…,N)分配R系列無人機，在第i個目標群的滯留時間為qi，目標群的中心位置坐標為(xi,yi)；4個基地的坐標分別為(x11,y11)、(x12,y12)、(x13,y13)、(x14,y14)，無人機每千米飛行消耗的代價為pck，每架無人機的固定代價為wk。

1)出動無人機的總路徑代價

無人機的固定代價和變動代價共同組成出動無人機的總路徑代價。無人機固定代價一般包括地面站操控員工資、無人機折舊費用、無人機制造成本等代價，為了使代價函數(shù)簡化，文中的固定代價特指出動無人機所需承擔的固定代價。假設基地擁有K架無人機，記第k架無人機的固定代價為wk(k=1,2,…,K)，則出動無人機架次的總固定代價為：

(2)

式中:sk為0-1決策變量。若sk=1，表示基地的第k架無人機出動，否則sk=0。

對于出動無人機的變動代價方面，包括無人機的維修保養(yǎng)、航油油耗等代價，為了使問題簡化，文中只計算航油油耗代價，此代價大致上同無人機所飛行的路徑長度成正比，其變動代價可以表示為：

(3)

式中:xijk為0-1決策變量。xijk=1表示目標群i和j節(jié)點之間有飛行計劃，否則xijk=0。dijk為目標群i和j節(jié)點之間的航路長度。

2)多基地協(xié)調(diào)調(diào)度合理化代價

在多無人機任務規(guī)劃時，還要充分考慮偵察無人機等存儲資源和基地設施的不確定性，主要是由執(zhí)行任務的無人機、地面站操控人員的不確定性引起的。為解決此問題，按照“少出動架次”原則合理運用基地無人機架次。特別是在無人機架次非常少、調(diào)度合理化與出動代價有一定關系的情況下，應最大程度上減少出動架次以充分利用無人機的偵察載荷資源。

在基地無人機架次比較緊張的情況下，合理進行任務規(guī)劃和優(yōu)化調(diào)度，對各基地出動架次和降低無人機執(zhí)行任務的代價是極其重要的。

如圖3所示，基地到目標群1和目標群2的距離分別為400 km和500 km，目標群1和目標群2之間的距離為900 km，目標群1和目標群2需要偵察載荷量均為0.5 t?；赜袃杉軣o人機可供使用，偵察載荷量均為1 t。若不考慮調(diào)度合理化代價，則可行的偵察方案有兩種，分別為：①由兩架無人機分別偵察兩個目標群；②由一架無人機偵察，一次性偵察兩個目標群。

比較這兩種方案，雖然無人機總的航行距離是一致的，均為1 800 km，但是當基地無人機數(shù)量有限時，若采用方案①，則該基地可繼續(xù)出動的無人機為0架；若采用方案②，則該基地可繼續(xù)出動的無人機為1架。雖然只有一架的差別，但是在實際作戰(zhàn)中考慮調(diào)度合理化是十分必要的。

因此文中在構建目標群間任務規(guī)劃數(shù)學模型上引入“調(diào)度合理化代價”，其可表示為：

(4)

式中:c為調(diào)度代價系數(shù)；λ為放大因子；qi為偵察每個目標群需要的載荷量;Lk為無人機的固有載荷量。

綜上所述，多目標群間無人機任務規(guī)劃目標函數(shù)的數(shù)學模型為：

(5)

3 周期性快速搜索遺傳算法

3.1 GA

GA是從一個問題的解集(種群)開始搜索的，解集中的每個解是由基因經(jīng)特定編碼構成的個體，由一定數(shù)目的個體組成種群[17]。GA的計算流程如下：①編碼。編碼方法是GA的關鍵步驟，既決定了染色體排列形式，又決定了個體的解碼方法。②生成初始種群。③適應度值計算。個體的優(yōu)劣性通過適應度函數(shù)值大小來表示，通常情況下，把目標函數(shù)的倒數(shù)作為適應度函數(shù)。④選擇、交叉與變異。通過選擇算子、交叉算子和變異算子執(zhí)行此操作。如今，對GA的改進研究很多，如何有效配合使用選擇、交叉和變異操作是當前的重要研究內(nèi)容[18]。⑤終止。算法的終止條件為種群適應度不再上升或迭代次數(shù)已達到預設次數(shù)。⑥解碼。最優(yōu)個體經(jīng)解碼得到解決實際問題的方案。

3.2 PFSGA思想

仿照自然界生物進化的“突變學說”思想，地球每經(jīng)過一次災難，原有生物會發(fā)生退化，爾后新的物種會出現(xiàn)，如此循環(huán)往復，生物的種類、復雜性會有所增加[19-20]。PFSGA的設計思想模擬自然界周期性往復“進化-退化”的特點。為了能夠保證算法朝著適應度函數(shù)值增加的方向進化。文中將GA中的選擇算子進行改進，設計了最優(yōu)算子，包括最優(yōu)逆轉(zhuǎn)序列算子和最優(yōu)插入點算子，如圖4所示。對于最優(yōu)逆轉(zhuǎn)序列算子，隨機選取兩個最優(yōu)逆轉(zhuǎn)點，如果將兩點之間的序列反序能使種群適應度增加，則將其逆轉(zhuǎn)，同時修改適應度值，否則相當于復制操作；對于最優(yōu)插入點算子，隨機選取兩個最優(yōu)插入點，如果將一個點插入到另一個點的前邊能使適應度增加，則執(zhí)行此操作，同時修改適應度值，否則相當于復制操作。目的是使種群適應值增加或不變，即保持種群進化。在種群進行重組的過程中始終保留適應值最大的個體，再通過自適應交叉、變異算子以一定的概率對種群進行演化，使種群發(fā)生暫時的退化，如此循環(huán)往復進行進化，即為PFSGA的一個進化周期，經(jīng)過若干個這樣的周期，最后可求得最優(yōu)解。

3.3 PFSGA計算流程

首先要確定所研究問題的種群規(guī)模N，其次隨機生成一定數(shù)量的由基因編碼構成的個體組成初始種群，最后計算初始種群中每個個體的適應度函數(shù)值，保留初始種群中適應度函數(shù)值最高的個體，為在一個進化周期里重組種群使用，同時給定滿足實際問題的進化周期數(shù)和一個進化周期所包含的進化代數(shù)。若進化周期數(shù)不滿足設定的次數(shù)，并且一個周期所包含的進化代數(shù)也不滿足給定的次數(shù)，使用文中設計的最優(yōu)算子對初始種群進行選擇操作，使種群發(fā)生暫時的進化，經(jīng)過若干進化代數(shù)重新組成了新的初始種群；若重新組成的種群中個體的適應度函數(shù)值優(yōu)于先前保留的個體，則將其替換，保留適應度函數(shù)值更高的個體。為了在下一進化周期前重組種群，由于種群的規(guī)模為N，按照錦標賽選擇策略(競賽度為2)從初始種群中繼續(xù)選擇N-1個個體組成新的種群，最后為了使種群發(fā)生暫時的退化，通過交叉、變異算子以一定的概率執(zhí)行遺傳操作重組種群，從而進入下一進化周期。周而復始，經(jīng)過若干個這樣的進化周期，就可以得到最優(yōu)個體，經(jīng)解碼即可得出滿足實際問題的最優(yōu)解。PFSGA計算流程圖如圖5所示。

圖5 PFSGA計算流程圖

4 仿真算例

4.1 PFSGA的算例分析

10個目標群均配屬雷達，一旦無人機進入某一目標群雷達探測范圍，10個目標群的配屬雷達均開機對空警戒和搜索目標，并采取相應對策，可能對無人機發(fā)射導彈予以摧毀，故無人機滯留目標群雷達探測范圍內(nèi)時間越長，被摧毀的可能性就越大。現(xiàn)需為R系列無人機完成10個目標群，共68個目標的偵察任務擬制最佳的路線和無人機調(diào)度策略，以保證無人機滯留雷達有效探測范圍內(nèi)的時間總和最小。

PFSGA的進化周期數(shù)設為150，種群規(guī)模設為100，一個進化周期所包含的進化代數(shù)為10。10個目標群分別對應編號(1,2,3,4,5,6,7,8,9,10)，4個無人機基地對應編號為(11,12,13,14)，運行該算法得到最優(yōu)解為(4,5,9,3,1,10,8,7,6,2)，對應的出動無人機架次最優(yōu)調(diào)度方案為(1,1,1,2,2,3,3,4,4,5)，1對應的無人機基地為11，2對應的無人機基地為12，3對應的無人機基地為13，4對應的無人機基地為14，5對應的無人機基地為11，4個基地派遣5架無人機即可完成偵察。經(jīng)過解算可得任務規(guī)劃方案如圖6所示。任務規(guī)劃結(jié)果如表2所示。PFSGA得到的種群適應度最優(yōu)值、平均值和最小值的進化圖如圖7所示。

圖6 任務規(guī)劃方案圖

路徑距離/km耗時/h11-4-5-9-11840.784.2012-3-1-121 126.105.6313-10-8-13989.974.9514-7-6-14822.324.1111-2-11658.063.29

從仿真結(jié)果可以看出，PFSGA求解任務規(guī)劃問題時，各基地無人機被分配的任務數(shù)量比較均衡，路徑規(guī)劃合理，各基地資源被充分利用，可以滿足實際戰(zhàn)場協(xié)同偵察的需要，驗證了模型的有效性和算法的合理性。

圖7 PFSGA適應度函數(shù)值進化圖

4.2 PFSGA與GA、單親遺傳算法的比較

文中首先對同一算例采取GA對其進行求解，最大迭代次數(shù)設為1 500，種群規(guī)模設為100，分別將變異概率、交叉概率設為0.05和0.8，運行該算法得到最優(yōu)解為(4,7,8,9,2,5,3,1,6,10)，對應出動無人機的架次為(1,1,2,2,3,3,4,5,5,6)，1對應的無人機基地為11，2對應的無人機基地為12，3對應的無人機基地為13，4對應的無人機基地為14，5對應的無人機基地為11，6對應的無人機基地為12，4個基地派遣6架無人機才能完成任務。相比于PFSGA多出動了一架無人機。其次運用文獻[20]中提出的單親遺傳算法(SPGA)對此算例進行求解，最大迭代次數(shù)為1 500次，變異概率、交叉概率分別設為0.15和0.6，種群規(guī)模設為100，運行該算法可知，4個基地也需要出動5架無人機，但飛行的總路徑卻比PFSGA飛行的路徑多208.71 km，同時偵察完所有目標的耗時也比PFSGA多花費1.04 h。將PFSGA、GA和SPGA分別運行6次，其適應度函數(shù)值的比較如表3所示。

表3 PFSGA、GA和SPGA適應度的比較

從表3中可知，參數(shù)設置大體相同的情況下，PFSGA所得到適應值更接近最優(yōu)解，由于設計的最優(yōu)算子指向性較強，搜索能力強，算法能夠快速收斂，易于求得模型的最優(yōu)解。

5 結(jié)論

文中構建了多目標群多基地多無人機協(xié)同偵察的任務規(guī)劃數(shù)學模型，基于文中所做的假設可將其簡化為TSP問題，同時在求解該問題時做了“雙重優(yōu)化”，第一重優(yōu)化是運用貪心算法對各目標群群內(nèi)的目標進行航路規(guī)劃，第二重優(yōu)化是運用PFSGA對各目標間的目標進行任務規(guī)劃。通過仿真算例驗證了任務規(guī)劃數(shù)學模型的有效性和算法的合理性，同時通過與GA和SPGA進行比較，可知PFSGA中的最優(yōu)算子具有較強的搜索能力，該算法收斂性較好，求解效率、精度高，易于求得最優(yōu)解。在實際中執(zhí)行偵察時，還應考慮隨時出現(xiàn)的各種不確定威脅及已知威脅和地形限制，構建在不確定環(huán)境的任務規(guī)劃決策數(shù)學模型。汲取當下人工智能的精華，搭建基于人機混合認知的任務規(guī)劃系統(tǒng)，提升無人機作戰(zhàn)效能。今后要在這兩方面進行深入研究。