基于改進蟻群算法的無人機協(xié)同航跡規(guī)劃研究

吳 蕊， 趙 敏， 李可現(xiàn)

(南京航空航天大學(xué)自動化學(xué)院，南京 210016)

0 引言

無人機多機協(xié)同作戰(zhàn)越來越受到廣泛關(guān)注，將具有不同功能的無人機組成網(wǎng)絡(luò)化無人機群能大大提高其作戰(zhàn)能力。無人機網(wǎng)絡(luò)的管理模式、作戰(zhàn)方式以及如何根據(jù)瞬息萬變的戰(zhàn)場環(huán)境任務(wù)調(diào)度直接決定了作戰(zhàn)效率和生存能力［1］。在多機協(xié)同作戰(zhàn)模式方面，文獻［2］提出了一種無人機任務(wù)分配的通用模型，該模型能對無人機執(zhí)行復(fù)雜作戰(zhàn)任務(wù)間的時序約束關(guān)系進行有效建模，但該方法未考慮到某個作戰(zhàn)任務(wù)需要多架無人機共同完成的情況，并且該方法信息傳遞量大，耦合性強，實用性不高。文獻［3］采用了分層規(guī)劃的思想，將整個動態(tài)、大規(guī)模、強耦合的優(yōu)化問題化解為3個層次:航跡規(guī)劃層、協(xié)同規(guī)劃層和航線平滑層。這種方法可把高維、強耦合的優(yōu)化問題分解成低維、計算量少、信息交流少的問題［4］，因此降低了規(guī)劃的難度。其中，航跡規(guī)劃層作為協(xié)同任務(wù)規(guī)劃的關(guān)鍵技術(shù)，受到國內(nèi)外學(xué)者的廣泛關(guān)注。

基于Voronoi圖方法在無人機航跡規(guī)劃方面有著廣泛的應(yīng)用，文獻［5］中通過構(gòu)建作戰(zhàn)環(huán)境的V圖模型，采用遺傳算法求解UAV航跡。這種方法能夠在空間規(guī)模較大的情況下進行，但也存在著效率不高的缺陷。蟻群算法是Dorigo M等人于1991年首次提出，并應(yīng)用于TSP問題，它是對自然界中真實蟻群覓食機制的模擬，通過引入啟發(fā)信息和基于正反饋機制的信息素更新機制，提高算法的求解效率［6－7］。由于 TSP問題和無人機航跡規(guī)劃具有一定的相似性，相比于進化算法，采用蟻群算法求解時不用編碼、求解效率高、易于計算機實現(xiàn)。

在研究已有的無人機協(xié)同航跡規(guī)劃方法的基礎(chǔ)上，采用層次分解策略，利用Voronoi圖構(gòu)造無人機作戰(zhàn)空間模型，根據(jù)問題特點對算法要素進行設(shè)計和改進。在蟻群算法的基礎(chǔ)上，一方面提出帶有方向性引導(dǎo)性的信息素更新策略，使其對人工螞蟻的搜索行為具有更強的引導(dǎo)作用，以提高算法效率;另一方面減少迷失螞蟻對算法收斂性的影響，有效地提高了算法的尋優(yōu)能力，以此來對多無人機的協(xié)同航跡規(guī)劃問題進行了研究。

1 基于Voronoi圖的威脅環(huán)境建模

壓制敵防空火力(SEAD)任務(wù)是研究多機協(xié)同航跡規(guī)劃的典型作戰(zhàn)任務(wù)，如圖1所示，其中一個重要目標就是避開威脅。采用Voronoi圖來處理多無人機的航跡規(guī)劃問題，主要因為Voronoi圖在計算最佳航跡各方法中是最簡單的，其最大優(yōu)點在于它將航跡規(guī)劃從無限維搜索問題縮減為有限的圖形搜索問題［8］，大大降低了計算量，能夠滿足多機協(xié)同問題的實時性要求。

圖1 無人機航跡規(guī)劃模型Fig.1 UAV path-planning model

若威脅場中存在N個雷達和導(dǎo)彈，則Voronoi圖將威脅場分成N個凸多邊形。每個凸多邊形中僅包含一個威脅，多邊形內(nèi)的任一點到相應(yīng)雷達站的距離最近。由于是在二維上規(guī)劃航跡，無人機沿著Voronoi圖邊飛行時，只考慮兩方面代價:一是無人機的燃料限制;二是雷達、導(dǎo)彈等對無人機的威脅代價。

對于第一方面的代價，可以假定無人機以恒速在同一高度飛行，燃料限制與路徑長度相關(guān)，則第i條路線的燃料代價表示為 wlength，i。

對于第二方面的代價，若假設(shè)各威脅對航路的影響因子相同，則各威脅的Voronoi圖的第i條邊作用效果為無人機到各威脅距離的四次方分之一。威脅模型表示為式中:lr，s是邊 L(r，s)的長度;dr，j、ds，j、d1/2，j分別是第 j個威脅距該路徑端點r、s和1/2處的距離。

由此，第i條路徑的廣義航跡代價表示為

其中，系數(shù)k表示威脅代價的權(quán)重，它反映了航跡規(guī)劃時決策人的傾向性選擇。這樣，就得到了一個賦權(quán)有向網(wǎng)絡(luò)圖［9－10］。無人機航跡規(guī)劃的目標就是在滿足式(2)的兩方面代價的前提下求解多無人機的多條初始航跡，且使得求得的航跡的廣義航跡代價最小化。

2 基于改進蟻群算法的多無人機航跡規(guī)劃算法設(shè)計

2.1 算法描述

將蟻群算法用于多無人機航跡規(guī)劃時，首先將m只螞蟻放在起始點處，開始沿著由n個威脅構(gòu)成的Voronoi圖邊從起始點出發(fā)尋找到達目標點的最優(yōu)主航跡和兩條輔航跡。假設(shè)迭代NC_max次，在每次迭代的一步轉(zhuǎn)移中，根據(jù)Voronoi圖的特點，該螞蟻從當前節(jié)點出發(fā)，最多有3個下一步可選節(jié)點，首先計算每一節(jié)點的轉(zhuǎn)移概率，然后用輪盤賭法選擇下一節(jié)點，這樣依次計算選擇直到到達目標點，完成一次候選航跡。

由于在每一步的待選點集中，可能存在無窮大節(jié)點，或是已經(jīng)走過的節(jié)點，因此螞蟻很可能在兩點之間徘徊無法前進，造成算法停滯，甚至無法得到滿足條件的多條初始航跡。為此定義迷失螞蟻，并令該螞蟻的本次廣義航跡代價為無窮大，即:

當所有螞蟻完成一次迭代后，首先選出本次迭代的前三優(yōu)航跡記錄保存，再根據(jù)目標點信息強度修改規(guī)則更新每一節(jié)點的生物信息強度，這一過程使得更多的信息素分配到具有更小航跡代價的節(jié)點上，有利于螞蟻更快地尋找到最好的航跡。

2.2 算法實現(xiàn)

1)算法的方向性引導(dǎo)。為了保證在一次迭代中有盡可能多的螞蟻到達目標點，在目標點處放置一生物信息素源，每時每刻都散發(fā)出生物信息激素，吸引螞蟻向目標點移動。假設(shè)目標點散布的生物激素隨距離的增加而減弱，且呈倒數(shù)變化關(guān)系，則可定義目標點信息強度為

式中:A為目標點處生物信息激素源的強度;Rr和Rs分別為節(jié)點r和節(jié)點s距目標點的距離;lr，s為邊L(r，s)的長度，如圖1所示。

為了將蟻群算法用于Voronoi圖的航跡規(guī)劃，方便計算各個點的參數(shù)值，定義生物信息強度矩陣Τn×5和節(jié)點可見性矩陣Ηn×5，其中第r行的Τr和Ηr可表示為

式中:xr，yr為可選節(jié)點 r的 x 和 y 方向的坐標;τs1，τs2，τs3為與點 r相連的 s1，s2，s3點的目標點信息強度;ws1，ws2，ws3為與點 r相連的 s1，s2，s3點的廣義航跡代價。

2)狀態(tài)轉(zhuǎn)移規(guī)則。第k只螞蟻按照輪盤賭選擇規(guī)則，來決定下一步移向哪一個航跡點，如果螞蟻當前位于航跡點r，下一步可行的航跡點的集合為J(r)，則從航跡點r到航跡點s的轉(zhuǎn)移概率為

式中:τ(r，s)與 η(r，s)分別表示兩航跡點的信息強度和啟發(fā)式信息值;α與β兩個常數(shù)，分別決定了信息強度和啟發(fā)式信息的相對影響力，α表示距目標點的相對重要性，β表示能見度的相對重要性。

3)目標點信息強度修改規(guī)則。當所有螞蟻完成一次航跡選擇后，必須對各點上的目標點信息強度作一次全面的修正，修正規(guī)則為

其中:m為螞蟻的數(shù)量;0＜ρ＜1為信息揮發(fā)參數(shù);Δτk(r，s)表示螞蟻 k 經(jīng)過邊 L(r，s)后的信息強度增量;Q值用來控制信息素的強度;Wk為螞蟻k本次廣義航跡代價。

4)時空上的協(xié)同。在協(xié)同任務(wù)中，各UAV抵達目標執(zhí)行任務(wù)的時間有一定的時間窗要求。若在該時間窗內(nèi)各無人機都能夠到達目標位置，即認為可以完成該協(xié)同任務(wù)。這里，假設(shè)無人機的速度范圍為［vmin，vmax］，則無人機到達給定目標點的時間為［tmin，tmax］。那么通過調(diào)整無人機的飛行速度即可滿足時間協(xié)同。同時，由于無人機是依次到達目標點，任意時刻各無人機所處的位置不同，這樣既避免了無人機的碰撞，保證了一定的安全距離。

3 算法仿真實例

在Voronoi圖上應(yīng)用改進的蟻群算法求解多無人機的協(xié)同規(guī)劃的初始多條航線，如圖1所示敵方陣地大小為70 km×70 km，菱形代表無人機的起始位置，五角星表示目標點，圓點代表雷達、導(dǎo)彈等威脅。在仿真實驗中(算法流程見圖2)，算法的參數(shù)設(shè)置如下:NC_max=100，m=30，ρ=0.3，K=0.5，Q=2，A=50。我方出動4架UAV(編號1～4)，分兩隊分別執(zhí)行任務(wù)1和任務(wù)2，各UAV的飛行速度取值范圍為［4，6］。測試樣本如表1所示。

圖2 算法流程圖Fig.2 Flow chart of the algorithm

表1 無人機樣本參數(shù)Table 1 The UAV parameters

圖3和圖4表示為了完成任務(wù)1需要位于不同起始點的UAV1和UAV2出發(fā)到達目標點(45，65)執(zhí)行任務(wù)的情況。由于考慮到兩架飛機協(xié)同的需要，初始情況下應(yīng)給出3條航跡供無人機選擇。其中，圖3a為滿足約束條件下利用蟻群算法得到各無人機的最優(yōu)主航跡，圖3b和圖3c為兩條輔航跡。同樣地，圖5和圖6是另一任務(wù)下的UAV3和UAV4航跡結(jié)果。

表2 各UAV抵達任務(wù)目標的時間Table 2 The arrival time of UAVs

圖3 任務(wù)1中UAV1的最佳3條航跡表示Fig.3 The three optimum paths for UAV1 in task 1

圖4 任務(wù)1中UAV2的最佳3條航跡表示Fig.4 The three optimum paths for UAV2 in task 1

圖5 任務(wù)2中UAV3的最佳3條航跡表示Fig.5 The three optimum paths for UAV3 in task 2

圖6 任務(wù)2中UAV4的最佳3條航跡表示Fig.6 The three optimum paths for UAV4 in task 2

表2為各UAV在［4，6］速度范圍內(nèi)保持一固定速度不變時抵達目標的時間，根據(jù)計算結(jié)果，在滿足最小時間窗下從待選航跡中選擇合適的航跡飛抵各自的目標，如圖7和圖8所示。

圖7 任務(wù)1中UAV1和UAV2的協(xié)同航跡結(jié)果Fig.7 The planned cooperative paths for task 1

圖8 任務(wù)2中UAV3和UAV4的協(xié)同航跡結(jié)果Fig.8 The planned cooperative paths for task 2

從圖中可以看出，一方面各無人機從同一時刻出發(fā)，在協(xié)同容許的時間范圍內(nèi)到達目標，這樣即可滿足多機時間協(xié)同需要。另一方面在空間協(xié)同方面，保證初始時航跡的多樣性，圖7和圖8的航跡雖然存在局部段重合的情況，但由于經(jīng)過該段的時間不同，故任意時刻各UAV所處位置始終滿足空域協(xié)同約束。從仿真結(jié)果可以看出，引入方向性引導(dǎo)策略的蟻群算法適合多無人機多航跡規(guī)劃的需求。

4 結(jié)論

本文所述將Voronoi圖和改進蟻群算法結(jié)合起來求解多無人機協(xié)同多條航線的方法，發(fā)揮了它們各自的優(yōu)點。仿真實驗表明，一方面利用Voronoi圖構(gòu)造的航線集合，可以保證UAV能夠回避各種威脅，順利地飛抵目標點;另一方面說明引入方向性引導(dǎo)的蟻群算法，提高了算法的優(yōu)化能力，確保利用層次分解策略開始多機多任務(wù)規(guī)劃時，快速找到多條可行航線，完成多任務(wù)下的多機協(xié)同，并為進一步優(yōu)化規(guī)劃結(jié)果奠定了基礎(chǔ)。

［1］ 馮琦，周德云.軍用無人機發(fā)展趨勢［J］.電光與控制，2003，10(1):9-13.

［2］ SHIMA T，RASMUSSEN S J，SPARKS A G.Multiple task assignments for cooperating uninhabited aerial vehicles using genetic algorithms［J］.Computers ＆ Operations Research，2006，33(11):3252-3269.

［3］ MCLAIN T W，CHANDLER P R，PACHTER M.A decomposition strategy for optimal coordination of unmanned air vehicles［C］//Proceedings of American Control Conference，2000:369-373.

［4］ 宋紹梅，張克，關(guān)世義.基于層次分解策略的無人機多機協(xié)同航線規(guī)劃方法研究［J］.戰(zhàn)術(shù)導(dǎo)彈技術(shù)，2004，1(1):44-48.

［5］ 賀濤，謝軍，王文娟，等.基于遺傳算法的無人偵察機航跡規(guī)劃［J］.彈箭與制導(dǎo)學(xué)報，2010，30(3):210-212.

［6］ DORIGO M.Special section on ant colony optimization［J］.IEEE Trans on Evolutionary Computation，2002，6(4):317-319.

［7］ 金飛虎，洪炳熔，高慶吉.基于蟻群算法的自由飛行空間機器人路徑規(guī)劃［J］.機器人，2003，24(6):526-529.

［8］ MCLAIN T，BEARD R.Trajectory planning for coordinated rendevousofunmanned airvehicles［C］//The Proceedings of the AIAA Guidance，Navigation，and Control Conference.Clearwater，F(xiàn)lorida:AIAA，2000:1247-1254.

［9］ 何艷萍，張安，劉海燕.基于Voronoi圖與蟻群算法的UCAV 航路規(guī)劃［J］.電光與控制，2009，16(11):22-23.

［10］ 葉媛媛，閔春平.基于Voronoi圖的無人機空域任務(wù)規(guī)劃方法研究［J］.系統(tǒng)仿真學(xué)報，2005(6):1353-1355.