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

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

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

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

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

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

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

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

0 引言

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

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

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

1 問題描述

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

其中S表示起始點(diǎn)，G表示終點(diǎn)，Pi表示中間航路點(diǎn)，每一個(gè)航路點(diǎn)Pi需要預(yù)先知道該點(diǎn)的位置坐標(biāo)（xi，yi）、航路代價(jià)等相關(guān)信息。

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

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

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

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

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

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

2.1 航路代價(jià)的表示方法

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

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

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

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

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

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

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

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

2.2 約束條件分析

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

2.2.1 速度約束

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

2.2.2 最大航程約束

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

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

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

2.2.4 時(shí)間協(xié)同約束

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

2.2.5 空間協(xié)同約束

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

3 蟻群算法原理

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

式中：

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

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

3.1 蟻群算法的改進(jìn)策略

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

3.1.1 精英保留策略

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

3.1.2 自適應(yīng)航路節(jié)點(diǎn)的選擇策略

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

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

式中：

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

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

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

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

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

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

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

3.1.5 冗余航路段的裁剪策略

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

3.2 改進(jìn)蟻群算法的程序流程

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

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

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

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

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

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

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

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

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

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

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

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

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

式中：

ti為從i到終點(diǎn)的剩余時(shí)間；

tj為從j到終點(diǎn)的剩余時(shí)間；

ti，ave為各種群中螞蟻到終點(diǎn)的平均剩余時(shí)間；

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

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

協(xié)同進(jìn)化多種群多UAV航路規(guī)劃結(jié)構(gòu)圖如圖1所示。

圖1 協(xié)同進(jìn)化多種群蟻群算法結(jié)構(gòu)圖

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

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

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

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

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

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

Step2.4重復(fù)step2，直至螞蟻到達(dá)終點(diǎn)。

Step3.對各種群的信息素進(jìn)行更新；

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

4 仿真實(shí)驗(yàn)

4.1 仿真設(shè)定

圖2 任務(wù)空間威脅分布示意圖

圖3 任務(wù)空間柵格化示意圖

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

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

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

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

圖4 δ=0時(shí)的任務(wù)航路規(guī)劃結(jié)果

圖5 δ=0.2時(shí)的任務(wù)航路規(guī)劃結(jié)果

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

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

劃仿真分析

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

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

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

4.4 算法的收斂性分析

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

圖7 蟻群算法收斂性分析

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

5 結(jié)論

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

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

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

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

［10］張毅，楊秀霞，周硙硙.基于速度障礙法的多UAV可飛行航跡優(yōu)化生成［J］.系統(tǒng)工程與電子技術(shù)，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］倪天權(quán)，王建東，劉以安.交叉粒群算法在無人機(jī)航路規(guī)劃中的應(yīng)用［J］.系統(tǒng)工程與電子技術(shù)，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ìn)

［J］.系統(tǒng)工程與電子技術(shù)，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

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

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