基于GAPSO-TS 的多基地無人機航路-時間協(xié)同規(guī)劃*

楊川力，寧 芊*，陳炳才，雷印杰

（1.四川大學(xué)電子信息學(xué)院，成都 610065；2.大連理工大學(xué)計算機科學(xué)與技術(shù)學(xué)院，遼寧 大連 116024）

0 引言

由于軍事偵察任務(wù)的復(fù)雜性越來越高，偵察方法朝著多無人機合作的方向逐漸發(fā)展［1］，因此，多無人機協(xié)同規(guī)劃十分重要。并且多種無人機協(xié)作作戰(zhàn)是無人機在戰(zhàn)場上作戰(zhàn)的主要形式［2］，多無人機要綜合考慮任務(wù)點分配，無人機通信，編隊保持，碰撞避免，雷達威脅，以及時間等問題。因此，多無人機的航路規(guī)劃比單無人機航路規(guī)劃更加復(fù)雜和困難。時間協(xié)同對于多無人機執(zhí)行搜索，攻擊等任務(wù)是極其重要的，可以有效提高任務(wù)完成率［3］。

目前，很多研究都是關(guān)于單無人機的航路規(guī)劃，如某些經(jīng)典算法細胞分解法（CD）、人工勢場法（APF）等算法［4］。還有一些智能反應(yīng)算法，如遺傳算法（GA）、粒子群優(yōu)化算法（PSO）［5］。遺傳算法是由Holland 于20 世紀70 年代初提出，目前，該算法已經(jīng)在各個領(lǐng)域得到應(yīng)用［6］。文獻［7］把遺傳算法和概率自動結(jié)合，解決無人機在未知空域中路徑規(guī)劃實時性和適用性不足的問題。文獻［8］混合了A*算法和遺傳算法，提高了基本遺傳算法的穩(wěn)定性和效率。粒子群算法（PSO）是一種基于自然現(xiàn)象的啟發(fā)式算法，采用了魚群和鳥群等生物的社會行為，粒子群算法結(jié)構(gòu)簡單，便于實現(xiàn)，但收斂速度慢，容易陷入局部最優(yōu)［9］。文獻［10］引入QPSO 算法，對基本PSO 算法進行改進，提高了全局搜索能力。遺傳粒子群算法（GAPSO）混合了遺傳算法和粒子群優(yōu)化算法，該算法首先計算適應(yīng)度函數(shù)值，對群體中的個體按適應(yīng)度函數(shù)值的大小進行排序，再采用PSO 算法對群體中的優(yōu)秀個體進行提高，提高以后的個體被保留并進入下一代，其他適應(yīng)度函數(shù)值差的個體則被淘汰。對已經(jīng)提高的優(yōu)秀個體再通過選擇交叉和變異步驟得到剩下的個體［11］。

本文同時考慮航路規(guī)劃和時間協(xié)同規(guī)劃，引入了禁忌搜索算法（Tabu-Search）到GAPSO 中，提出一種遺傳粒子群算法和禁忌搜索算法組合的GAPSO-TS 算法，由于GAPSO 算法是基于群體的優(yōu)化算法，而禁忌搜索算法是基于個體的［12］，組合算法保證了搜索的多樣性和全局性。

由于各個無人機距任務(wù)點距離不同，不能保證所有的無人機都能在協(xié)同時間內(nèi)到達目的地，所以，需要對不滿足條件的無人機重新規(guī)劃航路。目前主要有兩個方面來解決此問題，一是以變步長來調(diào)整無人機的協(xié)同時間；二是以延長航路來達到時間協(xié)同［13］。本文對于不滿足協(xié)同時間的無人機，設(shè)計了以協(xié)同時間或協(xié)同航程為約束的適應(yīng)度函數(shù)，重新規(guī)劃航路，以此保證所有無人機都能在最短時間內(nèi)同時到達目標點。

1 無人機航路規(guī)劃問題建模

1.1 問題描述

面對多基地多無人機最短時間同時到達目標點的任務(wù)需求，本文研究多無人機時間協(xié)同規(guī)劃問題。單無人機在執(zhí)行任務(wù)的過程，會碰到很多威脅，包括雷達、地形障礙、防空火炮等。如圖1 所示，仿真實驗中設(shè)定的場景包括了威脅區(qū)域、起點、任務(wù)點、地形。多無人機規(guī)劃是在單無人機規(guī)劃的基礎(chǔ)上建立的。

圖1 無人機飛行環(huán)境

威脅區(qū)域用定義為藍色半球體，威脅區(qū)域的中心坐標為（x，y，z），第i 個威脅區(qū)域的半徑為Ri。地形由山丘和平原組成。

1.2 航行代價評估

式（1）為單無人機航跡規(guī)劃時的適應(yīng)度函數(shù)，式（2）為多無人機協(xié)同規(guī)劃時，對無法協(xié)同的無人機設(shè)計的新適應(yīng)度函數(shù)。

1）油耗代價：w1×S

w1是油耗的權(quán)重，S 是該航路的實際長度。

2）高度代價：w2×H

w2是高度代價的權(quán)重，H=∑Hi，表示所有航路點的高度代價的總和，Hi表示航路點i 的高度代價，用式（3）來計算，Hmax、Hmin為最高和最低飛行高度，h是當前航路點的高度，Cdestory是懲罰因子。

3）威脅代價：w3×S×V

w3是威脅代價的權(quán)重，S 是實際航路的長度，V 是所有航路點的威脅系數(shù)，Vij是第k 段航路中第i 個點到第j 個威脅區(qū)域的威脅系數(shù)?？偟耐{系數(shù)是每段航路k 上的各點的威脅系數(shù)取平均值，再對所有航路的威脅系數(shù)進行求和，用式（4）計算。

vij用式（5）計算，其中，Dij是點Pk，m到威脅j 的直線距離，Rj是威脅j 的半徑，如下頁圖2 所示。

圖2 航跡威脅圖

4）重新規(guī)劃航路代價：w4×|S-P|

w4航路約束代價的權(quán)重，S 是實際規(guī)劃航路的長度，P 是根據(jù)最短協(xié)同時間設(shè)計的航路約束計算方式，tc是協(xié)同時間，Vmax是無人機最大運行速度，cs是航路約束系數(shù)。

2 基于GAPSO-TS 的航路規(guī)劃模型

GAPSO 算法是把GA 和PSO 算法結(jié)合起來，利用PSO 粒子間的相互聯(lián)系可以快速成熟的特點和GA 交叉、變異的特點，提高算法的收斂速度和精度［11］。在多無人機規(guī)劃中，需要進一步提高算法的收斂速度和精度，本文在GAPSO 算法的基礎(chǔ)上引入了禁忌搜索算法（Tabu-Search）。

禁忌搜索算法是對個體進行優(yōu)化，通過搜索個體的鄰域來獲取最優(yōu)解，并將已經(jīng)訪問過的鄰居放入禁忌表，防止重復(fù)訪問導(dǎo)致其陷入搜索循環(huán)，同時，會特赦禁忌表中的優(yōu)良狀態(tài)來保證搜索的多樣性與全局性［14］。

2.1 狀態(tài)空間模型

本文通過無人機在第i 個航路點的航偏角αi、俯仰角βi和飛行時間Ti建立極坐標系（α，β，T）與三維坐標系（x，y，z）的狀態(tài)空間模型，極坐標轉(zhuǎn)換為三維坐標用式（7）計算。

（xk+1，yk+1，zk+1）表示三維空間中第k+1 段航路的坐標點，αk+1、yk+1、Tk+1分別是第k+1 段航路的航偏角和俯仰角以及每一段航路的運行時間，v 是無人機的平均飛行速度，（xk，yk，zk）是第k 段航路的三維坐標。使用極坐標初始化航路可以保證轉(zhuǎn)角滿足約束和航路平滑。

2.2 基本PSO 模型

假設(shè)一個粒子有D 維搜索空間，總共有n 個粒子，第i 個粒子的狀態(tài)空間描述用向量Pi=

2.3 交叉和變異操作

采用浮點數(shù)交叉和變異［15］。設(shè)P1、P2是待交叉的粒子，交叉因子為Cp，子代為S1、S2，設(shè)α={αi1，…，αiD}，β={βi1，…，βiD}，T={Ti1，…，TiD}。則P1、P2的交叉操作為式（10），其中，x 是α、β、T 基因中的任意一個，S1（x）表示編號為1 的子代中的x 基因，P1（x）表示編號為1 的父代中的x 基因，S2（x）、P2（x）同上。

設(shè)變異因子為Cm，隨機數(shù)r，變異操作用式（11）來計算變異后的結(jié)果。其中，xmax為基因x 的最大值，xmin為基因x 的最小值，S（x）為子代染色體的x 基因。

2.4 GAPSO-TS 算法步驟

1）初始化種群數(shù)為NP，粒子維數(shù)D，最大迭代次數(shù)tmax，隨機初始化粒子的速度和狀態(tài)。

2）根據(jù)式（1）計算粒子的適應(yīng)度值，并更新歷史最優(yōu)和全局最優(yōu)。

3）對全局最優(yōu)引入TS 算法進行優(yōu)化。

4）按適應(yīng)度對所有粒子排序，保留前NP/2 的粒子，舍棄后NP/2 的粒子。

5）對前NP/2 的粒子進行交叉和變異操作。

6）判斷是否滿足迭代終止條件，滿足，則輸出最優(yōu)解；否則，返回第2）步，算法流程如下頁圖3 所示。

圖3 GAPSO-TS 算法流程圖

3 多無人機協(xié)同規(guī)劃

3.1 多無人機協(xié)同規(guī)劃模型

多無人機協(xié)同規(guī)劃采用分層規(guī)劃的模型，先對多個無人機用GAPSO-TS 算法進行航跡預(yù)規(guī)劃，再進行協(xié)同規(guī)劃，如圖4 所示。

圖4 是無人機協(xié)同規(guī)劃模型，分為頂層協(xié)同規(guī)劃層和底層無人機航跡規(guī)劃層，先對每架無人機用GAPSO-TS 算法進行預(yù)規(guī)劃，然后根據(jù)無人機飛行速度范圍，把［Tmin，Tmax］時間窗口傳遞給協(xié)同規(guī)劃層。

圖4 多無人機協(xié)同規(guī)劃模型

協(xié)同規(guī)劃層根據(jù)各個無人機的時間集來計算協(xié)同時間，取協(xié)同時間為時間交集的下界，再把協(xié)同時間傳遞給各個無人機進行速度調(diào)整。若沒有協(xié)同時間，則根據(jù)最短時間到達目的地原則，選取最長航路的無人機最短規(guī)劃時間作為協(xié)同時間，對無法滿足協(xié)同時間的無人機以協(xié)同時間為約束，變換適應(yīng)度函數(shù)，進行航跡重規(guī)劃。

3.2 多無人機協(xié)同規(guī)劃算法

4 單機航路規(guī)劃和多機航路規(guī)劃仿真

4.1 仿真環(huán)境

在IntelCorei5（TM）-7500@3.4 GHz，8 G 內(nèi)存的硬件，Matlab 仿真軟件環(huán)境下進行仿真實驗。場景參數(shù)由下頁表1 所示。

表1 場景參數(shù)表

4.2 單無人機三維空間仿真結(jié)果與分析

把GAPSO-TS 算法、標準PSO 與GAPSO 算法作對比，仿真結(jié)果如圖6～圖8 所示。

圖5 多基地無人機協(xié)同規(guī)劃流程圖

從圖8 分析，GAPSO 算法由于收斂很快，導(dǎo)致局部最優(yōu)，PSO 算法收斂速度次于GAPSO 因此，種群多樣性豐富，隨著迭代次數(shù)增加，適應(yīng)度精度比GAPSO 高，GAPSO-TS 算法繼承了GAPSO 收斂快的特點以及禁忌搜索的多樣性，在收斂速度和精度上都有所提高。從圖6、圖7 中3 組算法運行的結(jié)果看，PSO 算法運行的航跡通過爬高繞過威脅，GAPSO 和GAPSO-TS 算法的航跡相似，也避開了威脅，但GAPSO-TS 算法的航跡高度更低，說明GAPSO-TS 的全局尋優(yōu)能力高于GAPSO。

圖6 GAPSO-TS，PSO，GAPSO 算法航跡比較俯視圖

圖7 GAPSO-TS，PSO，GAPSO 算法航跡比較側(cè)視圖

圖8 GAPSO-TS，PSO，GAPSO 適應(yīng)度比較圖

表2 實驗參數(shù)表

表3 是 做10 次 實 驗 的 結(jié) 果，PSO、GAPSO、GAPSO-TS 算法的適應(yīng)度都用式（1）來計算，標準差公式用式（11）來計算，其中，σ 為標準差，n 設(shè)為10，fi是第i 次實驗的適應(yīng)度值，f 是平均適應(yīng)度值，收斂速度定義為f（i）與f（tmax）之間的誤差為10%時的最小迭代次數(shù)的倒數(shù)。GAPSO-TS 算法在精度上比PSO 算法提升了14%，比GAPSO 算法提高了25%，從標準差來看，GAPSO-TS 算法的穩(wěn)定性要優(yōu)于PSO 和GAPSO 算法。

表3 航跡規(guī)劃適應(yīng)度比較

4.3 多無人機三維空間協(xié)同規(guī)劃仿真參數(shù)設(shè)置

為了驗證多無人機協(xié)同算法的性能，假設(shè)4 架無人機從不同位置出發(fā)，到達相同目的地。地形、雷達參數(shù)如表1 所示，多無人機協(xié)同規(guī)劃模型參數(shù)見下頁表4。

表4 無人機參數(shù)

4.4 多無人機協(xié)同規(guī)劃仿真結(jié)果與分析

4.4.1 多無人機協(xié)同規(guī)劃仿真實驗

通過下頁圖9、圖10 可以看出，各個無人機從起點到目標點完成了航路規(guī)劃，從圖11 和表5 的實驗結(jié)果中看到，協(xié)同時間為86.058 07 s，UAV3 的最大飛行時間為69.978 27 s，不滿足時間協(xié)同的要求，所以要重新規(guī)劃，UAV3 重新規(guī)劃的適應(yīng)度函數(shù)設(shè)為式（2），式（2）中航路約束系數(shù)cs用來限制航路長度，通過設(shè)置不同大小的cs作對比來驗證式（2）的有效性。

表5 各無人機航跡規(guī)劃時間

圖9 多基地無人機協(xié)同規(guī)劃航跡側(cè)視圖

圖10 多基地無人機協(xié)同規(guī)劃航跡俯視圖

圖11 多基地無人機時間窗口

4.4.2 cs=1 時的無人機協(xié)同規(guī)劃仿真

UAV3 重新規(guī)劃的軌跡如圖13 中的黑色虛線所示所示，從圖中可以看出UAV3 的航跡延長了，從圖12 來看，UAV3 的航跡沿著地形航行來增加航路距離，結(jié)合表6 和圖14 來看，根據(jù)最長航跡最短時間設(shè)為協(xié)同時間的原則，協(xié)同時間設(shè)為86.05 s，而UAV3 重新規(guī)劃的最大飛行時間是86.06 s，大于協(xié)同時間，驗證了協(xié)同規(guī)劃的有效性。

圖12 UAV3 重規(guī)劃側(cè)視圖

圖13 UAV3 重規(guī)劃俯視圖

圖14 重規(guī)劃多基地無人機時間窗口

表6 各無人機航跡規(guī)劃時間

4.4.3 cs=1.02 時的無人機協(xié)同規(guī)劃仿真

當cs=1.02，UAV3 重新規(guī)劃的航路是圖16 中的綠色虛線所示，從圖15 中的綠色虛線看出，UAV3重新規(guī)劃的航路跟隨了地形的同時并延長了航路，根據(jù)表6 和表7 對比發(fā)現(xiàn)，cs=1 時，UAV3 航路長度為16.351 66 km，cs=1.02 的UAV3 航路長度為16.681 12 km，在航路長度上略有增加，從圖15 容易看到UAV3 的時間窗口相對于圖14 右移了一點，增加了裕量，這樣可以保證協(xié)同到達的穩(wěn)定性。對比實驗的結(jié)果驗證了式（2）的有效性。

圖15 UAV3 重規(guī)劃側(cè)視圖

圖16 UAV3 重規(guī)劃俯視圖

圖17 重規(guī)劃多基地無人機時間窗口

表7 重規(guī)劃后的各無人機規(guī)劃時間

5 結(jié)論

本文通過引入禁忌搜索算法，提升了GAPSO算法的收斂速度和精度，通過對比實驗，驗證了GAPSO-TS 算法的有效性。

通過建立多無人機分層模型，設(shè)計了新的適應(yīng)度函數(shù)，對不滿足時間協(xié)同的無人機進行重規(guī)劃，能夠?qū)崿F(xiàn)多基地無人機目的地集結(jié)的時間同步，證明了多無人機時間協(xié)同規(guī)劃算法的有效性。復(fù)雜環(huán)境中的多機規(guī)劃是一個多變量、多狀態(tài)、多約束、多目標的復(fù)雜系統(tǒng)規(guī)劃問題，本文還存在不足，可以在本文的基礎(chǔ)上運用馬爾科夫鏈等隨機過程模型，進一步將生存狀態(tài)模型與評估、威脅模型與評估等與航路-任務(wù)規(guī)劃相結(jié)合。