多目標群多基地多無人機協同任務規劃*

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

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

0 引言

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

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

1 問題描述

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

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

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

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

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

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

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

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

2 多目標群多基地多無人機任務規劃數學模型

2.1 各目標群內任務規劃數學模型

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

(1)

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

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

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

圖2 各個目標的有效偵察區域圖

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

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

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

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

④最后沒有被去掉的點，即為優化后的路線。

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

2.2 目標群間無人機任務規劃數學模型

2.2.1 任務共同分配策略

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

2.2.2 目標函數及數學模型

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

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

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

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

(2)

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

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

(3)

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

2)多基地協調調度合理化代價

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

在基地無人機架次比較緊張的情況下，合理進行任務規劃和優化調度，對各基地出動架次和降低無人機執行任務的代價是極其重要的。

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

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

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

(4)

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

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

(5)

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

3.1 GA

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

3.2 PFSGA思想

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

3.3 PFSGA計算流程

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

圖5 PFSGA計算流程圖

4 仿真算例

4.1 PFSGA的算例分析

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

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

圖6 任務規劃方案圖

路徑距離/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

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

圖7 PFSGA適應度函數值進化圖

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

文中首先對同一算例采取GA對其進行求解，最大迭代次數設為1 500，種群規模設為100，分別將變異概率、交叉概率設為0.05和0.8，運行該算法得到最優解為(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)對此算例進行求解，最大迭代次數為1 500次，變異概率、交叉概率分別設為0.15和0.6，種群規模設為100，運行該算法可知，4個基地也需要出動5架無人機，但飛行的總路徑卻比PFSGA飛行的路徑多208.71 km，同時偵察完所有目標的耗時也比PFSGA多花費1.04 h。將PFSGA、GA和SPGA分別運行6次，其適應度函數值的比較如表3所示。

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

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

5 結論

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