張耀中，李寄瑋，胡 波，張建東

（西北工業(yè)大學電子信息學院，西安 710129）

基于改進ACO算法的多UAV協(xié)同航路規(guī)劃*

張耀中，李寄瑋，胡 波，張建東

（西北工業(yè)大學電子信息學院，西安 710129）

針對無人機（Unmanned Aerial Vehicle，UAV）在執(zhí)行任務過程中遇到的諸如敵方防空火力、地形障礙及惡略天氣等各類威脅源，采用威脅源概率分布的方法進行威脅的量化處理，構建任務空間的威脅概率密度分布圖，有效消除了威脅源的差異性。根據(jù)UAV在任務飛行過程中的性能約束與時、空協(xié)同約束，同時考慮任務過程中UAV的損毀概率最小、任務航程最短，構建了相應的綜合任務航路代價最優(yōu)化目標函數(shù)。結合傳統(tǒng)蟻群優(yōu)化算法（Ant Colony Optimization，ACO）在解決此類問題中的不足，給出了相應的改進策略，提出采用協(xié)同多種群ACO進化策略來實現(xiàn)多UAV在滿足時、空協(xié)同約束下的協(xié)同航路規(guī)劃。通過相應的仿真計算表明，改進后的ACO協(xié)同多種群進化策略算法更適用于多UAV協(xié)同任務航路規(guī)劃問題，具有一定的實用性。從而為多UAV協(xié)同任務航路規(guī)劃問題的求解提供了科學的決策依據(jù)。

航路規(guī)劃，無人機，蟻群算法，協(xié)同進化

0 引言

多無人飛行器（Unmanned Aerial Vehicle，UAV）協(xié)同攻擊任務規(guī)劃系統(tǒng)是實現(xiàn)UAV功能互補、發(fā)揮多UAV集群作戰(zhàn)優(yōu)勢、降低任務之間的復雜耦合程度以及提升UAV執(zhí)行任務效率的保障，也是多UAV協(xié)同攻擊所需要解決的關鍵技術［1-2］。航路規(guī)劃作為UAV執(zhí)行任務的基礎，能夠為UAV提供一條最優(yōu)航跡，提高UAV的作戰(zhàn)效能。合理地規(guī)劃由起點到終點的任務航路，可使UAV快速有效地完成預定任務。近些年來，隨著戰(zhàn)場環(huán)境、任務難度的變化，多UAV協(xié)同航路規(guī)劃越來越受到重視［3-6］。多UAV航路規(guī)劃就是在滿足UAV性能、戰(zhàn)場環(huán)境、任務協(xié)同等約束條件下，為每架UAV制定從初始點到任務點的飛行軌跡使其任務效能指標達到最優(yōu)。

目前在航路規(guī)劃問題的研究上，主要集中在基于單元分解法的UAV航路規(guī)劃方法，在該方法中具有代表性的求解方法如A*算法、蟻群算法（Ant Colony Optimization，ACO）、元胞自動機方法等搜索方法；基于電磁場理論的人工勢場法；路標圖法，在該方法中具有代表性的是基于Voronoi圖的方法和概率路標圖法兩種。國外對多UAV協(xié)同航路規(guī)劃的研究主要集中在航路規(guī)劃方法和航路協(xié)調(diào)方法方面。如文獻［1］提出通過調(diào)節(jié)各UAV的飛行速度使多UAV在規(guī)定的時間范圍內(nèi)到達任務區(qū)域，并且使多UAV協(xié)同完成信息收集任務的時間最短。文獻［3］主要針對任務區(qū)中存在突發(fā)威脅與固定障礙環(huán)境，提出采用模型預測的方法在UAV機動能力下動態(tài)規(guī)劃出最優(yōu)任務航路。文獻［4］針對任務區(qū)中存在規(guī)避區(qū)時的信息收集最大化問題，提出了一種改進的遺傳算法來求解任務航路。文獻［5］提出了一種基于引力搜素算法與離散粒子群算法混合的最優(yōu)任務路徑規(guī)劃方法，來解決多移動機器人的最優(yōu)化路徑規(guī)劃問題。文獻［6］針對多UAV協(xié)同資源分配最優(yōu)化問題，提出了一種基于Pythagorean Hodgraphs曲線的幾何方法的多UAV協(xié)同航路規(guī)劃算法，取得了較好的效果。文獻［7］提出了將基于角度量編碼的小生境偽并行自適應遺傳算法和人有限干預情況下的智能決策結合起來UAV低空突防航跡規(guī)劃技術。文獻［8］對基本ACO算法采用精靈策略保留每次迭代最優(yōu)解的基礎上，提出了一種適用于航路規(guī)劃的MAX-MIN自適應ACO算法，在UCAV航路規(guī)劃中取得了較好的效果。文獻［9］以自主駕駛車輛為應用背景，將非完整性約束條件與雙向多步擴展RRT搜索算法相結合，提出了一種改進的RRT路徑規(guī)劃算法。文獻［10］提出了一種基于Pythagorean Hodgraph曲線的UAV在線航跡生成算法，并給出了高動態(tài)環(huán)境下多UAV的實時動態(tài)避碰規(guī)劃算法。

通過大量的文獻分析可以看出目前相關文獻針對航跡規(guī)劃問題采用了多種改進智能算法，取得了一定的效果［11-15］。本文結合航路規(guī)劃問題的特點，對基本ACO算法進行了系列改進，并對其進行了仿真驗證，仿真結果表明改進后的ACO算法更適用于多UAV協(xié)同任務航路規(guī)劃問題。

1 問題描述

在軍事應用中，任務空間中分布著已知或未知的敵方威脅以及地形、障礙和天氣等諸多因素，影響著UAV的任務執(zhí)行過程。因此，UAV航路規(guī)劃問題不僅需要考慮敵方威脅的變化，還需要考慮戰(zhàn)區(qū)環(huán)境的變化，并將這些信息及時地存儲和更新。航路規(guī)劃的目的是制定UAV的任務路徑使其能夠更加高效地完成預定任務，可以表示為任務空間中的一系列航路點，相鄰航路點之間可以用直線段連接，表示為如下的形式：

其中S表示起始點，G表示終點，Pi表示中間航路點，每一個航路點Pi需要預先知道該點的位置坐標（xi，yi）、航路代價等相關信息。

通常在對抗作戰(zhàn)環(huán)境中，敵方的防空火力以及地形等因素都會造成UAV的損毀，為了便于分析，本文中采用概率的方法進行威脅的量化處理，將任務空間（x，y）處的威脅定義為UAV被地形障礙或防空火力等因素摧毀的概率。在威脅環(huán)境下UAV損壞的概率與地形、威脅分布、威脅強度有著密切的關系［12］。任務區(qū)中的威脅源是UAV在任務飛行過程中應當盡量避免進入的區(qū)域，假定位于（x，y）處的威脅源Wi在其作用范圍內(nèi)使UAV損毀的概率為fi（x，y），則威脅源可以表示為：

其中pi（x，y）表示威脅源Wi在其作用范圍內(nèi)的威脅分布概率密度函數(shù)。

式（2）將威脅源進行了量化，假設各威脅源相互獨立，則空間（x，y）處受到n個威脅源作用的威脅值表示為：

式中n表示障礙與威脅源的總數(shù)，fi（x，y）與威脅源（或障礙）的特性有關。

式（3）構造了空間的威脅概率分布圖（Probabilistic Threat Exposure Map，PTEM），從而消除了威脅的差異性。在PTEM中，將威脅值高于某閾值fr的區(qū)域看作UAV的禁飛區(qū)，則UAV的禁飛區(qū)表示為：

2 UAV航路規(guī)劃問題建模

2.1 航路代價的表示方法

在UAV航路規(guī)劃問題中，航路代價是反映航路規(guī)劃結果優(yōu)劣的指標，定義UAV在航路中兩相鄰航路節(jié)點的綜合航路代價包括威脅代價和航程代價兩個部分：

①威脅代價是指UAV在通過航路段時，由于威脅源的存在而損壞的概率，表示為：

式中f（x，y）為威脅源的分布概率密度。

②航程代價是UAV在通過該航路段時的飛行距離，表示為：

定義UAV在航路P中相鄰兩航路節(jié)點上的綜合航路代價表示為：

由于UAV在任務執(zhí)行過程中并不是總能避開全部威脅的，在特定情況下有時候也需要穿越威脅源，在此引入威脅因子δ，表示UAV對威脅的最大承受能力，δ越大表示UAV能承受的威脅值越高。在考慮威脅承受能力的情況下，UAV的綜合航路代價可以表示為：

由此可以給出在綜合考慮威脅代價和航程代價時的航路規(guī)劃目標函數(shù)為：

多UAV協(xié)同航路規(guī)劃是在UAV航路規(guī)劃的基礎上，綜合考慮時間協(xié)同和空間協(xié)同等約束，使部分UAV能夠在允許的時間范圍內(nèi)到達任務區(qū)域，且各UAV之間不發(fā)生碰撞。對n架UAV進行協(xié)同航路規(guī)劃，使UAV整體的航路代價最小，則根據(jù)式（10）有：

2.2 約束條件分析

UAV協(xié)同航路規(guī)劃需要考慮UAV自身性能約束以及多UAV間的協(xié)同約束，其中自身性能約束主要包括速度約束、航程約束以及最大轉(zhuǎn)彎角約束，協(xié)同約束主要包括時間協(xié)同約束和空間協(xié)同約束。

2.2.1 速度約束

速度約束限制UAV在任務飛行過程中的速度保持在其最小最大速度之間，表示為：

2.2.2 最大航程約束

最大航程約束限制UAV在執(zhí)行任務過程中可飛行的最遠距離（Lmax），表示為：

2.2.3 最大轉(zhuǎn)彎角約束

最大轉(zhuǎn)彎角約束體現(xiàn)了UAV的轉(zhuǎn)彎機動性能。設UAV在t時刻位于時刻位于，其中△t表示時間步長。設最大轉(zhuǎn)彎角為θmax，則當前時刻位置、下一時刻位置、最大轉(zhuǎn)彎角之間有如下關系：

2.2.4 時間協(xié)同約束

對多UAV協(xié)同航路規(guī)劃，時間協(xié)同約束要求執(zhí)行同一個任務的多個UAV都必須在允許的時間范圍內(nèi)到達任務區(qū)域，表示為：

2.2.5 空間協(xié)同約束

空間協(xié)同約束限制了UAV之間的距離，保證UAV之間的距離保持在安全范圍之外，避免UAV之間在任務過程中發(fā)生碰撞。假設UAV的安全距離為Rs，任兩架UAV的飛行位置為，則在全任務飛行過程中要求：

3 蟻群算法原理

蟻群優(yōu)化算法（Ant Colony Optimization，ACO）是Dorigo于1991年根據(jù)螞蟻覓食行為提出的一種智能優(yōu)化算法［8，11，18-20］。

式中：

tabuk為螞蟻Ak已走過的節(jié)點；

經(jīng)過n個時刻，螞蟻完成一次搜索，各路徑上的信息素更新公式為：

3.1 蟻群算法的改進策略

通過國內(nèi)外研究表明，基本蟻群算法具有計算時間長、收斂速度慢、容易陷入局部最優(yōu)等缺點，為了有效克服這些缺點，本文給出蟻群算法的改進策略如下：

3.1.1 精英保留策略

在每一次迭代中保存當前的最優(yōu)值，有效保證下一次迭代的結果不劣于上一步。

3.1.2 自適應航路節(jié)點的選擇策略

基本蟻群算法在解的產(chǎn)生過程中，通過產(chǎn)生隨機數(shù)的策略來選擇，這種策略選擇方法使得算法具有很大的隨機性，導致算法收斂速度慢；利用正反饋原理進行選擇容易出現(xiàn)停滯現(xiàn)象，導致算法陷入局部最優(yōu)。將以上兩種方式相結合構造節(jié)點選擇策略，并且在搜索過程中動態(tài)調(diào)整節(jié)點的選擇概率，在迭代次數(shù)到達一定程度后，適當?shù)丶哟箅S機選擇概率，從而對空間進行完全搜索［18-19］。

假定在t時刻螞蟻處于位置i，則其選擇位置j的概率可以表示為：

式中：

r為［0，1］中均勻分布的隨機數(shù)；

r0為動態(tài)權值，表示隨機選擇策略的權值，當r＞r0時，根據(jù)pkab的值采用賭輪盤的方式選擇j。

3.1.3 自適應調(diào)節(jié)信息素蒸發(fā)因子

由于路徑上信息素隨時間蒸發(fā)，使得那些長時間沒有被搜索到的節(jié)點上信息素逐步趨于0，降低了算法的全局搜索能力。通過動態(tài)改變信息素蒸發(fā)因子ρ能夠在算法的全局搜索能力與收斂速度之間進行平衡。一種自適應調(diào)節(jié)信息素蒸發(fā)因子的方法為：

ρmax為信息素揮發(fā)因子的最大值，防止信息素揮發(fā)過快降低算法的收斂速度。

3.1.4 螞蟻可以選擇走回頭路策略

基本蟻群算法中，限制人工螞蟻不能走回頭路。但是在威脅區(qū)比較復雜的情況下，可能會出現(xiàn)螞蟻前進的道路上信息素為0，從而使算法停滯。為了避免這種情況的出現(xiàn)，本文中設定螞蟻可以走回頭路，即可以回溯到前幾步，并重新進行路徑規(guī)劃。

3.1.5 冗余航路段的裁剪策略

由于引入螞蟻可以走回頭路的機制，蟻群算法在求解的過程中會出現(xiàn)環(huán)狀路徑。此時需要進行裁剪，去掉環(huán)狀路徑。具體方法為：搜索航路中相同的位置，刪除相同位置之間的航路。

3.2 改進蟻群算法的程序流程

依據(jù)上述改進蟻群算法模型，給出基于改進蟻群算法的航路規(guī)劃算法流程如下：

Step 1：初始化任務飛行區(qū)域內(nèi)各節(jié)點的信息素濃度值，形成一個信息素矩陣T；

Step 2：將m只人工螞蟻放置在UAV的起始位置等待出發(fā)；

Step 3：每一只螞蟻根據(jù)式（20）、式（21）的方法選擇下一個節(jié)點，最終到達目標點，形成一條可行的航路，假設螞蟻從當前節(jié)點移動到其相鄰所有節(jié)點所用的時間相同；

Step 4：計算每一只螞蟻得到的可行航路的目標函數(shù)，并保存航路代價最小的航路解；

Step 5：根據(jù)目標函數(shù)，按照信息素調(diào)整策略更新各節(jié)點的信息素濃度；

Step 6：判斷是否完成迭代條件（達到最小目標函數(shù)或者迭代次數(shù)），若不滿足，則返回Step 2重新執(zhí)行，若滿足，則完成搜索；

Step 7：根據(jù)冗余航路段裁剪策略，進行冗余航路的裁剪；

Step 8：輸出最優(yōu)路徑。

3.3 多UAV協(xié)同航路規(guī)劃的協(xié)同進化蟻群算法

多UAV協(xié)同航路規(guī)劃是在單UAV航路規(guī)劃的基礎上，考慮執(zhí)行任務的多個UAV之間在空間協(xié)同性和時間協(xié)同性等的約束關系，使UAV飛行航線在任務空間上能夠避免碰撞，在時間上能夠在要求的時間順序內(nèi)到達任務區(qū)域，這是一個復雜的優(yōu)化問題。在單UAV航路規(guī)劃方法的基礎上，結合協(xié)同進化（Co-Evolution）的思想，引入了多螞蟻種群協(xié)作機制，對不同種群內(nèi)各螞蟻的狀態(tài)選擇概率進行改進，設計了協(xié)同進化多種群蟻群算法（Co-Evolution Multi-Ant Colony Algorithm，CEMACA） 對多UAV協(xié)同航路規(guī)劃問題進行求解。

基于提出的蟻群算法改進策略，結合協(xié)同進化思想，引入nv個種群的螞蟻，先求解每架UAV的航路，不同種群的螞蟻在進化過程中，維護各自種群的信息素，其間不存在競爭關系。各種群的螞蟻需要與其他種群的螞蟻進行空間和時間上的協(xié)同，主要表現(xiàn)為：

①各種群的螞蟻不能實現(xiàn)時間協(xié)同時，通過調(diào)整其自身選擇概率pij，使距離任務區(qū)域遠的螞蟻以更大概率選擇較近的航路，距離任務區(qū)域近的螞蟻以更大的概率選擇較遠的航路，設計時間協(xié)同系數(shù)和時間協(xié)同約束條件下的螞蟻選擇概率為：

式中：

ti為從i到終點的剩余時間；

tj為從j到終點的剩余時間；

ti，ave為各種群中螞蟻到終點的平均剩余時間；

σ為系數(shù)調(diào)節(jié)因子，取較小的正常數(shù)；

②各種群的螞蟻在不能實現(xiàn)空間協(xié)同時，通過調(diào)整沖突航路的選擇概率pij，使螞蟻對沖突航路的選擇概率減小，從而避免UAV之間的碰撞。

協(xié)同進化多種群多UAV航路規(guī)劃結構圖如圖1所示。

圖1 協(xié)同進化多種群蟻群算法結構圖

協(xié)同進化多種群蟻群算法運行流程為：

Step1.初始化各種群ACi，及各種群的相關參數(shù)；

Step2.對坌Anti，j∈ACi，執(zhí)行以下操作：

Step2.1各種群中螞蟻在每一步中按照式（23）、式（24）構造選擇概率pij（m，n），其中m表示螞蟻當前位置，n表示螞蟻在當前位置可選擇的位置；

Step2.2通過調(diào)整pij（m，n），對各種群中對應螞蟻的位置進行時間和空間協(xié)調(diào)；

Step2.3各種群的螞蟻通過式（20）、式（21）選擇航路節(jié)點；

Step2.4重復step2，直至螞蟻到達終點。

Step3.對各種群的信息素進行更新；

Step4.從各種群選擇滿足協(xié)同條件的航路。

4 仿真實驗

4.1 仿真設定

圖2 任務空間威脅分布示意圖

圖3 任務空間柵格化示意圖

構造了具有8個威脅源的任務場景，每個威脅源具有不同的威脅屬性和威脅等級，任務空間為40 km*40 km的二維戰(zhàn)場環(huán)境，如圖2所示威脅分布情況。威脅源處的高度信息代表了在當前位置（x，y）處UAV被損毀的概率，為了分析問題方便，將圖2所示威脅分布中的損毀概率投影到二維平面中，并對規(guī)劃空間進行柵格化處理，如圖3所示。

仿真采用Intel 2.2 GHz主頻、4 G內(nèi)存的PC機，Windows 7操作系統(tǒng)，Matlab2012b仿真環(huán)境。UAV的最大航程Lmax=100 km，UAV的最大轉(zhuǎn)彎角速率△θmax=3°/s。設定算法中螞蟻數(shù)量為20個，迭代次數(shù)為50次，初始參數(shù)設置分別為：α=5，β=2，Q=10，δ=0，ρ=0.7，θ=0.1，其中：θ為信息素蒸發(fā)因子；ρ為搜索因子，隨著迭代次數(shù)減小。

4.2 改進蟻群算法的單UAV航路規(guī)劃問題仿真分析

假設UAV的起點坐標為S=（5 km，2 km），UAV需要到達的待執(zhí)行任務點坐標為G=（30 km，14km）。分別設定改進蟻群算法中的威脅因子δ=0及δ=0.2進行仿真計算，根據(jù)設定的初始仿真條件，改進蟻群算法的航路規(guī)劃結果分別如圖4、圖5所示。

圖4 δ=0時的任務航路規(guī)劃結果

圖5 δ=0.2時的任務航路規(guī)劃結果

通過仿真分析可以看出，改進的蟻群算法能夠快速有效地為UAV規(guī)劃出較優(yōu)的任務航路。當設定的威脅因子較大時，UAV能夠承受的威脅更大，此時允許UAV穿過威脅區(qū)，體現(xiàn)了在任務飛行過程中，UAV對威脅程度與航路代價的協(xié)調(diào)；威脅因子較小時，UAV能夠承受的威脅比較小，此時不允許UAV穿越威脅區(qū)，體現(xiàn)了在任務飛行過程中，對UAV的安全飛行要求更高一些。

4.3 改進協(xié)同進化蟻群算法的多UAV協(xié)同航路規(guī)

劃仿真分析

假設我方3架UAV，記為U1、U2、U3，其初始坐標分別為S1=（5 km，1 km）、S2=（20 km，1 km）、S3=（30 km，1 km）；有2個需要到達的任務執(zhí)行點，分別為t1=（12 km，15 km）和t2=（30 km，14 km）；要求U2與U3到達t2，U1到達t1，且3架UAV同時到達任務執(zhí)行點，UAV之間的空間協(xié)同約束為Rmin=1 km，根據(jù)本文提出的改進協(xié)同進化蟻群算法進行協(xié)同航路規(guī)劃，則多UAV協(xié)同航路規(guī)劃的結果如圖6所示。

圖6 多UCAV協(xié)同航路規(guī)劃結果

由仿真結果可以看出，各UAV的航路長度分別為15、18、18，滿足時間協(xié)同約束，U2與U3在到達任務執(zhí)行點之前的路徑點距離能夠滿足空間協(xié)同要求。

4.4 算法的收斂性分析

文獻［20］從數(shù)學理論的角度對蟻群算法的全局收斂性進行了分析，本文從不同迭代次數(shù)中各螞蟻的平均路徑長度分析蟻群算法的收斂性能。對上面給出的仿真設定，改進蟻群算法中的螞蟻在每次迭代過程中的航路代價隨著迭代次數(shù)的變化曲線如圖7所示。

圖7 蟻群算法收斂性分析

由圖7可以看出，本文所給出的改進蟻群算法在收斂速度方面明顯優(yōu)于基本蟻群算法，并且改進的蟻群算法能夠比基本蟻群算法找到航路代價更小的航路。由此，可以說明改進的蟻群算法效果要好于基本的蟻群算法。通過以上仿真算例的分析可以看出，本文提出的改進蟻群算法具有良好的尋優(yōu)能力和收斂性。

5 結論

本文針對UAV在執(zhí)行任務過程中遇到的各類威脅源，如敵方防空火力、地形障礙及惡略天氣等，采用概率分布的方法進行威脅的量化處理，構建任務空間的威脅概率密度分布圖，有效消除了威脅源的差異性。根據(jù)UAV在任務飛行過程中的性能約束與時、空協(xié)同約束，同時考慮任務過程中UAV的損毀概率最小、任務航程最短，構建了相應的綜合任務航路代價最優(yōu)化目標函數(shù)。針對傳統(tǒng)遺傳算法收斂速度慢、容易陷入局部最優(yōu)等缺點，提出了采用精英保留策略、自適應信息素蒸發(fā)調(diào)節(jié)因子以及螞蟻可以選擇走回頭路等策略，對傳統(tǒng)蟻群算法進行了相應改進，并提出采用協(xié)同多種群ACO進化策略來實現(xiàn)多UAV在任務過程中的時、空協(xié)同能力，得出了滿意的航路規(guī)劃結果，具有一定的實用性。

［1］KLESH A T，KABAMBA P T，GIRARD A R.Path planning forcooperative time-optimal information collection［C］//American ControlConference， 2008.IEEE， 2008：1991-1996.

［2］SEBBANE Y B.Planning and decision making for aerial robots［M］.Springer，2014.

［3］LEE J W，WALKER B，CONEN K.Path planning of unmanned aerial vehicles in a dynamic environment［M］.AIAA Aerospace，St.Louis，Missouri，2011:29-31.

［4］ERGEZER H，LEBLEBICIOGLU K.Path planning for UAVs for maximum information collection［J］.Aerospace and Electronic Systems，IEEE Transactions on，2013，49（1）：502-520.

［5］PURCARU C，PRECUP R E，IERCAN D，et al.Multi-robot GSA-and PSO-based optimal path planning in static environments［C］//Robot Motion and Control（RoMoCo），2013 9th Workshop on.IEEE，2013：197-202.

［6］SHIN H S，LEBOUCHER C，TSOURDOS A.Resource allocation with cooperative path planning for multiple UAVs［C］// Control（CONTROL），2012 UKACC International Conference on.IEEE，2012：298-303.

［7］任鵬，高曉光.有限干預下的UAV低空突防航跡規(guī)劃［J］.系統(tǒng)工程與電子技術，2014，36（4）：679-684.

［8］馬冠軍，段海濱，劉森琪，等.基于MAX-MIN自適應蟻群優(yōu)化的無人作戰(zhàn)飛機航路規(guī)劃［J］.航空學報，2008，29（B05）：243-248.

［9］宋金澤，戴斌，單恩忠，等.一種改進的RRT路徑規(guī)劃算法［J］.電子學報，2010，38（2A）：225-228.

［10］張毅，楊秀霞，周硙硙.基于速度障礙法的多UAV可飛行航跡優(yōu)化生成［J］.系統(tǒng)工程與電子技術，2015，37（2）：323-330.

［11］LU J，WANG N，CHEN J，et al.Cooperative path planning for multiple UCAVs using an AIS-ACO hybrid approach［C］//Electronic and Mechanical Engineering and Information Technology（EMEIT），2011 International Conference on.IEEE，2011，8：4301-4305.

［12］SWARTZENTRUBER L，F(xiàn)OO J L，WINER E.Multi-objective UAV path planning with refined reconnaissance and threat formulations［C］//Proceedings of 6th AIAA Multidisciplinary Design Optimization Specialist Conference，2010：1-14.

［13］TSOURDOS A，WHITE B，SHANMUGAVEL M.Cooperative path planning of unmanned aerial vehicles［M］.John Wiley&Sons，2010.

［14］SAMADI M，OTHMAN M F.Global path planning for autonomous mobile robot using genetic algorithm［C］//2013 International Conference on Signal-Image Technology& Internet-Based Systems.IEEE Computer Society，2013：726-730.

［15］EUN Y，BANG H.Cooperative task assignment/path plan

ning of multiple unmanned aerial vehicles using genetic algorithm［J］.Journal of Aircraft，2009，46（1）：338-343.

［16］GAO M，JIANG J，MING N K，et al.Cooperative path planning for UAVs with UAV loss considerations［C］//Computational Intelligence for Security and Defense Applications（CISDA），2013 IEEE Symposium on.IEEE，2013：38-44.

［17］倪天權，王建東，劉以安.交叉粒群算法在無人機航路規(guī)劃中的應用［J］.系統(tǒng)工程與電子技術，2011，33（4）：806-810.

［18］MONTEMANNI R，WEYLAND D，GAMBARDELLA L M. An enhanced ant colony system for the team orienteering problem with time windows［C］//Computer Science and Society（ISCCS），2011 International Symposium on.IEEE，2011：381-384.

［19］KE L，F(xiàn)ENG Z.A new ant colony optimization approach for the orienteering problem［C］//2008 7th World Congress on Intelligent Control and Automation，2008：2027-2032.

［20］段海濱，王道波.蟻群算法的全局收斂性研究及改進

［J］.系統(tǒng)工程與電子技術，2004，26（10）：1506-1509.

Cooperative Path Planning for Multi-UAVs Based on Improved ACO Algorithm

ZHANG Yao-zhong，LI Ji-wei，HU Bo，ZHANG Jian-dong
（School of Electronics and Information，Northwestern Polytechnical University，Xi’an 710129，China）

In this paper，a cooperative path planning method by utilizing improved ant colony optimization（ACO）is presented.In the military domain UAVs usually require the intelligence to safely maneuver along a task path to an intended target，avoiding obstacles such as enemy threats，terrain or bad weather.The method of probability distribution is adopted to deal with such obstacles is adopted. By constructing the obstacles probability density distribution map of the task area the individual diversity of the obstacles effectively can be eliminated.Then according to the flying performance，spatial and temporal constraints of the UAVs，a path cost optimization objective function is proposed by balancing the damage probability of UAV and shortest voyage.For the deficiency of standard ACO algorithm，an improved ACO algorithm is brought that some improvement strategies is put forward for such optimization problems，also a co-evolution multi-ant colony algorithm is proposed to solving the cooperative path planning problems for multi-UAVs.Simulation results show that the improved ACO algorithm can solve the problem effectively，and compared with standard ACO algorithm，it is also more efficiency.

path planning，unmanned aerial vehicle，ant colony optimization（ACO），cooperation evolution

TP391

A

1002-0640（2017）05-0139-07

2016-02-18

2016-05-18

軍隊預研基金（9140c470xxx14）；西北工業(yè)大學研究生創(chuàng)意創(chuàng)新種子基金資助項目（Z2016125）

張耀中（1974- ），男，河南舞陽人，碩士生導師。研究方向：先進火力控制原理，復雜系統(tǒng)的建模與仿真。