動基地多無人機協同偵察問題研究*

王 晨，謝文俊，趙曉林，李兵飛

（1.空軍工程大學航空航天工程學院，西安 710038；2.航空電子系統綜合技術重點實驗室，上海 200233）

0 引言

無人機是一種具備自主飛行和獨立執行任務能力的新型作戰平臺［1］，利用無人機執行空基偵察任務是UAV的重要應用方向之一［2］，實時獲取偵察目標的動態信息能更有效地掌握戰場情況，對戰爭結果的走向起著至關重要的作用。

目前，國內外對于無人機航路規劃的研究成果多是基于無人機發射回收基地是固定不變的［2-3］。楊遵等［4］采用粒子群算法研究了多架無人機遍歷多個目標點的航路規劃問題；吳文超等［5］針對不確定環境下多無人機協同搜索航路規劃，提出了一種滿足無人機機動限制和適應數據通信延遲的協同路徑決策算法；喻蓉、林林等［6-8］研究了保證多無人機到達同一目標地的時空協同航路規劃問題，在多機協同航路規劃中考慮戰術思想和通信約束方面也進行了有益嘗試；馬純超［9］在無人機任務分配模型中設計了任務時間窗和平臺特性為約束條件的遺傳算子，改進了遺傳算法求解任務分配問題。國外對于多機協同航路規劃的研究，除了經典的Voronoi圖、混合整數規劃、動態規劃等方法外，達里奧·博索等［10］在無人機之間可以共享位置和航向前提下，提出了神經動態規劃方法；尼古勞斯等［11］采用了進化計算方法；菲利普瓊斯等［12］研究了監視任務中多機航路規劃，以保證對監視區域的全覆蓋和提高重訪率。

隨著無人機艦載起降技術的成熟，無人機由艦載平臺搭載完成偵察任務逐漸成為一種重要的樣式。本文針對艦載無人機的偵察特點，建立了動基地的多無人機協同偵察問題模型。

多無人機協同偵察通過選擇無人機的數量、配置任務載荷、確定偵察目標、規劃航跡，使得偵察效能大大優于以往的單機偵察模式，且總代價最小。實際作戰中為了及時獲取關鍵的軍事情報信息，在一次偵察任務中通常會派出數架UAV對若干可疑目標進行偵察，多無人機協同偵察規劃已經成為UAV的一個重要應用方式，是國內外相關研究領域研究的一個重點問題。

在文獻［13］中，已經建立了考慮目標偵察需要的多UAV協同偵察優化模型，并提出了一個有效算法對其進行解決，隨著無人機作戰運用技術的發展，無人機可以在艦載平臺上起降遂行偵察任務，不再是要對單一固定基地的UAV進行調度和任務規劃。隨著各國軍備技術的發展和戰爭形勢的變化，基于移動基地的多無人機目標偵察問題研究越來越有必要，這在以往的研究尚未涉及。本文首次研究基于移動基地的多無人機協同偵察任務規劃問題，針對多目標、多無人機、移動基地、硬時間窗口建立了偵察規劃模型，采用改進的周期進化遺傳算法，通過MATLAB進行了仿真驗證分析。仿真結果表明，可以得到高品質的協同偵察方案，本文提出的動基地多無人機協同偵察問題模型，更符合艦載無人機遂行偵察任務特點。

1 M-MUCRPTW模型

1.1 問題描述

艦載無人機偵察使用有其自身特點，例如無人機可以在艦載平臺起飛降落，這樣在執行任務過程中，隨著艦載平臺的移動，無人機的起飛著陸基地不再是固定不變的了。

根據艦載無人機執行任務的特點，動基地的多UAV協同偵察問題簡化為如下問題：

1）動基地沿固定路線移動有4個無人機回收點（回收點1是起點），如圖1所示。

圖1 動基地回收點示意圖

2）每個目標點僅被偵察一次，每個目標點都被偵察到。

3）航母在每個回收點的停留時間為t1小時，兩兩相鄰的回收點之間的航行時間為t2小時。

4）偵察無人機滯留防御方雷達探測范圍內時間越長，被其摧毀的可能性就越大。每個目標點都有最大的安全偵察時間，為保證盡可能多地獲取信息，無人機在目標點的偵察時間等于其最大安全時間。

1.2 M-MUCRPTW模型建立

目標函數為出行UAV的運輸成本，記為Z，記第k架無人機的固定成本為fk，則調用無人機的總固定成本為，任一sk=1，表示基地的第k架無人機被調用，否則sk=0。

無人機的變動成本按油耗計算，大致上和無人機所行駛的里程數呈正比。其總運輸成本可以表示為：。

xijk為決策0-1變量，標識i和j節點之間是否有通路，dijk為i和j節點之間的路徑長度，行駛每公里消耗費用為pck。則動基地多無人機協同偵察問題模型為：

約束條件為：

若 xijk=1，則：

式（2）表示每個目標被偵察且僅被偵察一次，式（3）表示每架飛機從起始點出發，式（4）表示每架飛機在回收點被回收，式（5）表示每架飛機偵察的目標點不超過總的目標點數，式（6）表示回收點的停靠時間窗約束，式（7）表示單架UAV的總飛行時間不能超過其最長允許飛行時間。

2 M-MUCRP模型求解

針對M-MUCRPTW問題，本文采用周期進化遺傳算法求解。算法流程如圖2所示。

2.1 算法設計思想

生物進化的“災變學說”認為，在歷史上，地球表面曾經發生過多次災變，其中有些是世界性的，如洪水泛濫、星球撞擊等。每經一次災變，原有生物即發生大幅度退化，甚至有些物種被毀滅，災難過后，新的物種重新被創造出來，如此循環往復［15］。

圖2 算法流程圖

本文算法對一個進化周期的設計思想是：首先將組合算子加入到遺傳操作中，然后根據指定的代數對種群進化（種群的適應度平均值單調不減），接著在保留歷史最優個體的情況下對種群進行重組，最后按照自適應選擇的交叉概率和變異概率對種群中的個體進行一代演化，使種群發生暫時的退化（種群的適應度平均值降低），再轉入下一個進化周期，通過若干個這樣的進化周期，最后求得最優解。

組合算子是為周期進化遺傳算法新設計的一種算子，按如下4步進行操作［16］：假設父代為F。

Step1：從父代F中隨機選取兩個目標點e和f；

Step2：如果將e和f間的目標點（含e和f）反序能使F的適應度值增加，則將e和f間的目標反序，同時修改F的適應度值；

Step3：先后選取兩個客戶點e和f；

Step4：如果將e插入到f的前面能使F的適應度值增加，則將e插入到f的前面，同時修改F的適應度值。

組合算子執行完畢，同時也計算出生成的子個體的適應度值。該算子使種群保持進化趨勢主要體現在：1）該算子作用后，所得后代的適應度值大于等于父代的適應度值；2）如果Step2和Step4中的條件都不滿足，組合算子相當于復制操作，反之則是變異操作。

2.2 解的編碼

采用多個由各無人機起始點、偵察目標、回收點的全排列組成的數據結構表示協同偵察方案，也就是模型的解，稱為解染色體。

解染色體為一個ka+1位的數據結構，其中ka=m，k表示第k架UAV。1到a存儲第i架UAV的偵察目標點排序，a+1到2a存儲第j架UAV的偵察目標點排序，以此類推，第ka+1位為標識位。另外設置一個起標識作用有ka+1位數據結構的染色體，由1，2，…，k組成，例如a+1到2a全為2表示該段基因為第2架UAV的偵察目標排序。

2.3 初始解的生成

隨機選取能實現所有狀態的遍歷，因此，初始解由MATLAB函數隨機生成。初始解是一個二維數組，橫向表示的是目標點和艦載無人機的代碼，包含了每架UAV偵察目標的順序及其停靠回收點的信息，縱向代表了初始種群中的每一個個體。

2.4 確定適應度函數及適應度計算

在遺傳算法中，適應度是用來區分種群中個體好壞的標準，是算法進化過程的驅動力。本文取個體的適應度為其評價值的倒數，即f=1/Z。首先解碼種群中的每一個染色體，求出對應的可行解，然后按照動基地多無人機協同偵察數學模型根據式（1）計算出目標函數值Zn（n=1，2，…，N），令染色體的適應度函數為 fn=1/Zn［17-19］。

2.5 種群進化策略

將每代種群的n個染色體按fn值的大小進行排序，把從大到小的前n/2個染色體進行復制，直接進入下一代。下一代種群中剩余的n/2個染色體由MATLAB函數隨機產生。

對產生的新種群，按照交叉概率pc，采用PMX交叉法則，進行交叉重組。

染色體按照變異概率pm進行變異操作。變異算子采用的策略如下：隨機產生變異點jm，將染色體循環左移jm個基因。例如，染色體：1 2 7 8 11 16 14 10 3 5 4 9 6 12；jm=3，經變異操作后，產生的染色體為：8 11 16 14 10 3 5 4 9 6 12 1 2 7。

3 仿真實驗

仿真實驗中，任務背景為某海域上航母艦載無人機對陸地目標點遂行偵察任務。航母沿著固定路線勻速航行，在航行路線上有4個UAV回收點（包括起始點），每個回收點的停靠時間固定為2 h，偵察目標為一個12個點的集合，派出3架UAV遂行偵察任務。UAV在每個偵察目標點有不同的最大安全偵察時間，為保證盡量獲取更多的偵察信息，UAV的偵察時間設為等于最大安全偵察時間。設置種群規模為100，進化代數為150。

計算得到最優解如表1所示。

2號和1號UAV在回收點2被回收，3號UAV在回收點3被回收。1、2、3號UAV的偵察路徑分別為 2 9 8；7 6 4 10 1 3 11；5 12 。

表1 第150代的最優解

最終方案中的所有無人機的偵察路徑總圖如圖3所示。

圖3 最終方案中的所有無人機的偵察路徑總圖

種群適應度值隨著進化的進行變化情況如圖4所示。從圖中可以看出，隨著進化的進行，每一代中最優解的適應度越來越好，接近100代的時候適應度的最大值開始保持不變，此時的進化已經基本達到最優。

圖4 適應度值進化情況圖

4 結論

1）首次建立了動基地多無人機協同偵察問題的研究模型，該模型充分考慮了不同偵察目標的威脅情況和航母回收UAV的時間窗約束，以最小化UAV執行任務的偵察代價為目標，符合現階段及未來一段時間內的實際作戰情況需求。

2）采用周期進化的遺傳算法對模型進行求解，保留了標準遺傳算法思想中的交叉和變異設計，并且對交叉概率和變異概率加以控制，避免了插入算子對好的基因片段可能造成的破壞。且該算法具有很好的全局搜索能力，更易于取得最優解。

UAV在執行偵察任務過程中，受到動態復雜多變戰場環境的影響，某些偵察目標的位置、時間窗約束以及UAV的自身狀態均有可能發生變化。因此，在后續工作中，將對動態的多UAV協同偵察問題展開進一步的研究。