一種基于航跡片段的多蟻群協(xié)同規(guī)劃算法

劉慧娟,蔡 超,孫希霞

(華中科技大學自動化學院多譜信息處理技術(shù)國防科技重點實驗室,武漢430074)

一種基于航跡片段的多蟻群協(xié)同規(guī)劃算法

劉慧娟,蔡 超,孫希霞

(華中科技大學自動化學院多譜信息處理技術(shù)國防科技重點實驗室,武漢430074)

在協(xié)同航跡規(guī)劃過程中,針對傳統(tǒng)蟻群算法存在的收斂速度慢、航跡易沖突等問題,結(jié)合由航跡片段構(gòu)成的網(wǎng)絡(luò)圖特點,提出一種基于多蟻群的飛行器協(xié)同航跡規(guī)劃算法。將蟻群算法中的人工蟻群劃分為與飛行器數(shù)量相對應(yīng)的螞蟻子群,通過引入異質(zhì)信息素實現(xiàn)子群之間的競爭,采取基準長度協(xié)同進化的方法引導(dǎo)子群規(guī)劃出滿足時間協(xié)同要求的航跡,利用迷失螞蟻信息素更新策略加快算法收斂速度。實驗結(jié)果表明,針對不同規(guī)劃任務(wù),在多種復(fù)雜規(guī)劃環(huán)境中,該算法都能生成滿足時間和空間約束的協(xié)同飛行航跡。與傳統(tǒng)蟻群算法相比,該算法能夠?qū)⒁?guī)劃速度提高2倍～3倍,所規(guī)劃出的航跡具有更好的時空協(xié)同性能。

協(xié)同航跡規(guī)劃;網(wǎng)絡(luò)圖;多子群;蟻群算法;異質(zhì)信息素

1 概述

協(xié)同航跡規(guī)劃技術(shù)是提高無人飛行器協(xié)同作戰(zhàn)效能,保證無人飛行器協(xié)同作戰(zhàn)順利實施的關(guān)鍵技術(shù)之一［1］。其目標是在飛行器性能允許的范圍內(nèi),為多架飛行器設(shè)計從起點到目標的飛行航跡,要求在盡可能降低多飛行器執(zhí)行飛行任務(wù)代價的同時滿足多飛行器執(zhí)行任務(wù)的協(xié)同要求,是一個 NP難題［2］。

針對多飛行器協(xié)同規(guī)劃問題中存在的搜索空間大、規(guī)劃速度慢等問題,本文采用基于航跡片段圖(航跡網(wǎng)絡(luò)圖［3］)的方法進行規(guī)劃,將航跡規(guī)劃問題轉(zhuǎn)化為一個圖搜索問題,以減少搜索空間、加快搜索速度。航跡片段圖是一種類似于Voronoi［4］圖或路線圖［5］的圖結(jié)構(gòu),圖的邊由一系列滿足飛行約束條件的航跡片段構(gòu)成,節(jié)點是一系列的導(dǎo)航控制點。常用的圖搜索算法有Dijkstra算法［6］、遺傳算法［7］、蟻群算法［8］、A*算法［9］等。蟻群算法作為一種新興的演化計算技術(shù),由于其靈活性和自我組織等特點,近年來成為研究熱點,并被用于解決多飛行器協(xié)同規(guī)劃問題［10］。

蟻群算法相比于其他進化算法,在求解協(xié)同航跡規(guī)劃問題時,具備無需編碼、求解效率高等優(yōu)點［11］。但是一般的蟻群算法只考慮了同一種群內(nèi)部信息素的影響,在解決多任務(wù)問題時無法很好地滿足協(xié)同約束。文獻［12］提出一種多蟻群協(xié)作模式,解決了約束條件復(fù)雜的組合優(yōu)化問題。

本文針對協(xié)同航跡規(guī)劃存在的問題,設(shè)計了多蟻群協(xié)同規(guī)劃算法,將人工蟻群劃分為與飛行器對應(yīng)的螞蟻子群,同一子群內(nèi)部通過信息素引導(dǎo)個體趨向最優(yōu)路徑,采用異質(zhì)信息素互斥策略降低航跡沖突概率,增加迷失螞蟻信息素更新策略提高規(guī)劃速度。

2 規(guī)劃空間及協(xié)同問題描述

2.1 協(xié)同航跡規(guī)劃問題描述

本文的規(guī)劃空間為構(gòu)造完畢的航跡網(wǎng)絡(luò)圖,其局部示意圖如圖1所示,其中橢圓形區(qū)域為禁飛區(qū)。航跡網(wǎng)絡(luò)圖表示為圖G=(V,E),其中,V為圖中節(jié)點集合;E為航跡片段(圖G中的邊)的集合,節(jié)點位置為(x,y,z)。

圖1 航跡網(wǎng)絡(luò)的局部示意圖

設(shè)V={Vi,i=1,2,…,Nv}為執(zhí)行協(xié)同規(guī)劃任務(wù)的無人飛行器集合,S={Si,i=1,2,…,Ns}和T= {Ti,i=1,2,…,Nt}分別為與各無人飛行器相對應(yīng)的起始點和目標點所構(gòu)成的集合,F={Fi,i=1,2,…,Nf}為禁飛區(qū)集合,規(guī)劃空間為在R行C列(R和C為常數(shù))的網(wǎng)格環(huán)境下構(gòu)造出的航跡網(wǎng)絡(luò)圖。Vi的航跡Ri由一系列航跡片段{Ei,i=1,2,…,Ne}構(gòu)成,航跡片段由一系列導(dǎo)航點{Pk=(xk,yk,zk),k=1, 2,…,N}表示。

假設(shè)所有飛行器以速度v勻速飛行,本文中的協(xié)同規(guī)劃問題為:在給定的航跡網(wǎng)絡(luò)圖上為飛行器集合V規(guī)劃出從起始點到目標點的代價最小且滿足協(xié)同約束的協(xié)同航跡組。

2.2 協(xié)同約束分析

多飛行器協(xié)同航跡規(guī)劃除了要滿足飛行器自身飛行約束外,還必須滿足多機協(xié)同約束,包括空間協(xié)同約束和時間協(xié)同約束。

(1)空間協(xié)同約束

多架飛行器協(xié)同執(zhí)行任務(wù)過程中,任意時刻各飛行器之間必須滿足一定的空間安全間隔ds,設(shè)Pi(t)為Vi在t時刻的位置,即要求任意時刻兩飛行期間的歐氏距離大于等于間隔ds:

(2)時間協(xié)同約束

在協(xié)同規(guī)劃問題中,飛行器到達目標的時間往往存在一定的時間窗［0,T］限制,即對協(xié)同規(guī)劃任務(wù)中飛行器最早抵達目標和最晚抵達目標的時間間隔有一定的要求。任務(wù)時間約束可表達如下:

其中,Tmax,Tmin分別為飛行器集合V中最早抵達目標點和最晚抵達目標點的時間。

2.3 協(xié)同航跡代價函數(shù)設(shè)定

對于多飛行器協(xié)同航跡規(guī)劃問題,一方面應(yīng)考慮單航跡本身的代價,另一方面還應(yīng)考慮航跡的協(xié)同性能。

(1)單航跡代價

飛行器的航跡Ri由起始點到目標點之間相互連接的航跡片段構(gòu)成,因此單航跡的代價為構(gòu)成該航跡的片段代價之和。每段航跡片段上都存儲了相應(yīng)的航跡長度代價、威脅代價、轉(zhuǎn)彎次數(shù)代價等信息,由此可以得到航跡Ri的單航跡代價:

其中,nr為構(gòu)成航跡Ri的航跡片段數(shù)目;Fl(Ek),Ft(Ek)和Fz(Ek)分別為航跡Ri上第k條航跡片段的航跡長度代價、威脅代價和轉(zhuǎn)彎次數(shù)代價;a,b和c分別為對應(yīng)代價的加權(quán)系數(shù),三者之和為1。

(2)多航跡協(xié)同代價

對于多航跡的協(xié)同性能,不能僅考慮多條航跡的代價之和,還需考慮時間協(xié)同性能。定義協(xié)同系數(shù)λ來衡量協(xié)同航跡對時間協(xié)同約束的滿足程度:

顯然,時間約束要求λ不大于1,λ越接近于0,時間協(xié)同性能越好(發(fā)射段和攻擊段避碰問題另行考慮)。

綜合單航跡代價、協(xié)同系數(shù)以及協(xié)同約束可得航跡組的協(xié)同評價指標:

其中,F為綜合航跡代價;N為協(xié)同航跡數(shù)目。2個不等式分別代表時間和空間協(xié)同約束。協(xié)同航跡規(guī)劃目標為:在滿足時間和空間協(xié)同的情況下,盡可能地減小F的取值。

3 多蟻群協(xié)同規(guī)劃算法

多飛行器協(xié)同航跡規(guī)劃問題包含多類協(xié)同約束,本文基于協(xié)同進化思想,設(shè)計了多子群蟻群算法。

3.1 多子群蟻群協(xié)同進化機制

多無人飛行器協(xié)同航跡規(guī)劃中,每架飛行器對應(yīng)不同的任務(wù),因此可將蟻群算法中的人工蟻群劃分為與飛行器對應(yīng)的螞蟻子群。同一個子群中的螞蟻個體之間相互合作,不同子群之間存在競爭關(guān)系,如圖2所示。

圖2 多子群蟻群的協(xié)同進化

在圖2中,黑色原點代表螞蟻,ACi對應(yīng)于Vi的螞蟻子群,Antij為第i個子群中的第j只螞蟻個體,m為子群的規(guī)模。螞蟻子群之間通過信息素進行通信。每個螞蟻子群散發(fā)不同種類的信息素,并維護各自的信息素結(jié)構(gòu)。蟻群算法采用信息素更新策略引導(dǎo)螞蟻個體選擇優(yōu)化路徑,螞蟻個體根據(jù)備選航跡片段上的信息素濃度及啟發(fā)信息大小計算轉(zhuǎn)移概率,依據(jù)狀態(tài)轉(zhuǎn)移規(guī)則選擇相應(yīng)的航跡片段。

為實現(xiàn)各任務(wù)的時間協(xié)同,依據(jù)基準長度協(xié)同進化思想,使所有子群都規(guī)劃出最接近基準長度的航跡。一次規(guī)劃結(jié)束后,若規(guī)劃次數(shù)達到最大迭代次數(shù)或者綜合協(xié)同代價與上次規(guī)劃結(jié)果的差值小于最小基準值ΔF,則停止迭代,否則對基準長度進行調(diào)整,調(diào)整方法為:

其中,Ls為該次協(xié)同規(guī)劃過程中的基準航跡長度;Lmax為所有起始點到目標點直線距離中最大的值;i為迭代次數(shù);MAX為最大迭代次數(shù);Lave為上一代航跡組的平均長度;α為基準長度進化系數(shù);ΔL為上一代規(guī)劃產(chǎn)生的航跡與標準航跡長度的最大差值。

本文在狀態(tài)轉(zhuǎn)移概率計算公式中加入異質(zhì)信息素,在子群間引入競爭機制,減少了不同子群的螞蟻挑選到同一航跡片段的概率,避免產(chǎn)生沖突,實現(xiàn)空間協(xié)同。同時考慮到未成功找出路徑的螞蟻個體(迷失螞蟻)的經(jīng)驗信息,在帶精英策略蟻群算法［13］信息素更新策略基礎(chǔ)上,加入迷失螞蟻信息素更新以減少其他螞蟻的迷失概率,加快算法的收斂速度。

3.2 基于異質(zhì)信息素互斥的狀態(tài)轉(zhuǎn)移

子群i中的螞蟻按照輪盤賭選擇規(guī)則,決定下一步移向哪個節(jié)點,這個過程稱為狀態(tài)轉(zhuǎn)移。與傳統(tǒng)的圖搜索問題不同,本文搜索的航跡網(wǎng)絡(luò)圖中,2個節(jié)點之間可能存在多條航跡片段(邊)。因此本文將傳統(tǒng)的蟻群算法進行圖搜索中的節(jié)點選擇問題轉(zhuǎn)化為航跡片段選擇問題,即通過選擇航跡片段來確定到達的節(jié)點。為避免航跡沖突,引入異質(zhì)信息素互斥的概念,在進行狀態(tài)轉(zhuǎn)移時不僅考慮本子群的信息素,同時考慮其他子群信息素濃度對航跡片段選擇的影響。如果螞蟻當前位于航跡片段Er,下一步可選航跡片段的集合為E(r),從航跡片段Es到集合E(r)中的Es片段的轉(zhuǎn)移概率為:

其中,Pi(r,s)為子群i中位于航跡片段Er上的螞蟻挑選航跡片段Es的概率值;τis和F(Es)分別為子群i在航跡片段Es上留下的信息素值和片段Es的代價值;~τis為引入的異質(zhì)信息素,其值為除子群i外的其他螞蟻子群在航跡片段Es上留下的信息素的最大值;α,β和γ分別為信息素系數(shù)、啟發(fā)信息系數(shù)和異質(zhì)信息素系數(shù)。

3.3 信息素更新

蟻群算法通過信息素的更新對螞蟻起到引導(dǎo)作用。當螞蟻子群中所有個體完成了當前迭代過程中的路徑搜索后,如下原因會造成部分螞蟻沒有能夠成功規(guī)劃出路徑:(1)可能的航跡片段搜索完畢沒能到達目標;(2)經(jīng)過的路徑長度超過了長度約束; (3)因機動性能約束或目標進入方向約束使得不能到達目標。這類螞蟻個體即前文定義的迷失螞蟻,這些螞蟻應(yīng)該對后續(xù)螞蟻起到警示作用。因此,本文對規(guī)劃出的路徑上的片段采用帶精英策略螞蟻系統(tǒng)的更新策略,同時對迷失螞蟻所經(jīng)路徑上的片段采用迷失螞蟻信息素更新策略進行更新,減少后續(xù)螞蟻迷失的概率。

(1)帶精英策略的信息素更新

子群i完成一次迭代后,從規(guī)劃出的路徑中找出與標準航跡長度值最接近的航跡作為最優(yōu)航跡,找出這條航跡的螞蟻被稱為精英螞蟻。假設(shè)所有成功規(guī)劃出路徑的螞蟻所經(jīng)過的片段集合為E(S),對集合中片段Es上的信息素按照下式更新:其中,τis(n)和τis(n-1)分別為迭代前后片段Es的信息素值;ρ為信息素揮發(fā)因子(0＜ρ＜1);Δ表示第k只螞蟻在本次迭代中留在片段Es上的信息素量;mk為子群k中成功規(guī)劃出路徑的螞蟻數(shù)量;Δτis表示本次迭代中片段Es的信息素的增加量;Δτ*is表示精英螞蟻引起的片段Es上的信息素增量;Q為信息素常量;mσ為精英螞蟻數(shù)量;ΔLk和ΔL*分別為第k只螞蟻構(gòu)造的航跡和最優(yōu)航跡與標準航跡的長度差值。

(2)迷失螞蟻的信息素更新

假設(shè)子群i本次迭代中迷失螞蟻所經(jīng)路徑上的片段集合為E(F),其片段Es上的信息素的更新策略如下:

其中,mj為子群i第n次迭代中的迷失螞蟻數(shù)目;為第j只迷失螞蟻在片段Es上產(chǎn)生的衰減系數(shù);Lj為螞蟻j所經(jīng)路徑的總長度;Ljs為螞蟻j到達片段Es時所經(jīng)路徑的長度。

迷失螞蟻信息更新機制的作用主要表現(xiàn)在:對迷失螞蟻所經(jīng)路徑上的信息素進行按比例衰減,從而對后續(xù)螞蟻個體產(chǎn)生引導(dǎo)作用,減少后續(xù)螞蟻迷失的概率。

3.4 算法步驟

本文算法首先將蟻群算法中的人工蟻群分為多個與飛行器對應(yīng)的螞蟻子群,每個子群采用上文提出的狀態(tài)轉(zhuǎn)移規(guī)則和信息素更新策略為對應(yīng)飛行器構(gòu)造與標準航跡長度最接近的航跡,并通過航跡綜合代價值判斷是否需要動態(tài)調(diào)整標準航跡值,以構(gòu)造出符合協(xié)同約束的協(xié)同航跡組,具體算法步驟如下:

步驟1 初始化螞蟻子群及相關(guān)參數(shù)。

步驟2 對所有的螞蟻子群均執(zhí)行步驟3～步驟5。

步驟3 子群中的螞蟻個體按照狀態(tài)轉(zhuǎn)移規(guī)則為對應(yīng)飛行器構(gòu)造航跡。

步驟4 一次迭代完畢后,根據(jù)構(gòu)造的航跡結(jié)果對信息素結(jié)構(gòu)進行更新。

步驟5 迭代次數(shù)達到子蟻群算法上限或構(gòu)造出的最優(yōu)航跡與上次迭代相近,則停止迭代,否則跳轉(zhuǎn)到步驟3。

步驟6 在所有子群都完成上述過程后,若達到群體最大迭代次數(shù)或者規(guī)劃出的綜合航跡代價與上一次的差值小于標準差值,則停止迭代,否則更改標準航跡長度,并跳轉(zhuǎn)到步驟2。

4 實驗結(jié)果及分析

在CPU為CoreE7200 2.53 GHz、內(nèi)存為2.0 GB的PC機上,對算法進行了驗證。PC機的操作系統(tǒng)為Windows XP,程序開發(fā)環(huán)境為Visual Studio 2005。實驗中使用在分辨率為90 m的3 000×3 000像素的數(shù)字地形高程圖上生成的航跡網(wǎng)絡(luò)圖,網(wǎng)絡(luò)圖由3 680條航跡片段構(gòu)成。

本文對異質(zhì)信息素和迷失螞蟻信息素更新的效果、算法對不同任務(wù)的適應(yīng)度以及算法對不同環(huán)境的適應(yīng)度進行了實驗。每個子群中螞蟻個體的總數(shù)是一個恒量,螞蟻數(shù)量太多容易導(dǎo)致次優(yōu)路線的快速增長且計算量增大,然而,螞蟻數(shù)量太少時又會由于信息素的揮發(fā)和通信的減少而導(dǎo)致螞蟻間的協(xié)作行為減弱,通過多次測試實驗,本文將子群規(guī)模定為80只,子群最大迭代次數(shù)定為40代。由于信息素隨著時間的推移可能會累加到一個比較大的量,而片段上的代價值則是一個定值,為了避免信息素作用太強而過早陷入局部最優(yōu),將α,β,γ,ρ等參數(shù)取值分別定為0.8,0.6,0.7和0.3,動態(tài)調(diào)整標準航跡最大迭代次數(shù)為5次。

實驗1 為了驗證異質(zhì)信息素和迷失螞蟻信息素的效果,在規(guī)劃環(huán)境、協(xié)同任務(wù)一致的情況下進行2組對比實驗。

(1)為驗證迷失螞蟻信息素的作用,對多蟻群協(xié)同算法和未采用迷失螞蟻信息素更新的蟻群算法進行對比實驗,圖3給出了規(guī)劃時間曲線?？梢钥闯?在相同任務(wù)和規(guī)劃環(huán)境條件下,采用多蟻群協(xié)同算法規(guī)劃的時間均比無迷失螞蟻更新策略的算法短,說明迷失螞蟻信息素更新策略能加快算法收斂,提高規(guī)劃速度。

圖3 規(guī)劃時間對比

(2)為驗證異質(zhì)信息素的作用,對多蟻群協(xié)同算法和未加入異質(zhì)信息素的蟻群算法進行對比實驗。在10次實驗中,采用無異質(zhì)信息素蟻群算法的規(guī)劃結(jié)果中有2次出現(xiàn)了碰撞的情況,而多蟻群協(xié)同算法規(guī)劃結(jié)果均滿足空間協(xié)同,說明基于異質(zhì)信息素的狀態(tài)轉(zhuǎn)移策略能夠降低碰撞概率,提高空間協(xié)同能力。圖4為其中一次對比實驗結(jié)果和三維仿真截圖。

圖4 對比實驗結(jié)果和三維仿真

實驗2 為了驗證多蟻群協(xié)同算法對不同任務(wù)的適應(yīng)度,在相同環(huán)境下對不同規(guī)劃任務(wù)進行實驗,圖5給出了部分實驗結(jié)果圖,表1給出相應(yīng)的實驗數(shù)據(jù)。

圖5 不同任務(wù)的規(guī)劃結(jié)果

表1 不同任務(wù)的規(guī)劃結(jié)果數(shù)據(jù)

實驗結(jié)果均滿足空間協(xié)同,且從表1可以看出,每個任務(wù)的協(xié)同系數(shù)均小于1,說明算法能夠為不同任務(wù)規(guī)劃出符合時間和空間協(xié)同的航跡。

實驗3 為驗證多蟻群協(xié)同算法對不同環(huán)境的適應(yīng)度,對同一任務(wù)在不同環(huán)境下進行實驗,圖6給出部分實驗結(jié)果,表2給出了相應(yīng)的實驗數(shù)據(jù)。

圖6 不同規(guī)劃環(huán)境下的規(guī)劃結(jié)果

表2 不同規(guī)劃環(huán)境下的規(guī)劃結(jié)果數(shù)據(jù)

表2中的數(shù)據(jù)和實驗結(jié)果驗證了本文算法能夠在不同的規(guī)劃環(huán)境下規(guī)劃出滿足時間和空間協(xié)同的協(xié)同航跡。

5 結(jié)束語

多無人機協(xié)同規(guī)劃問題是一個復(fù)雜的大規(guī)模優(yōu)化問題,本文針對該問題提出了一種基于航跡片段的多蟻群協(xié)同規(guī)劃算法。該算法在蟻群之間引入競爭機制,并在信息素更新機制中引入迷失螞蟻信息素更新策略。實驗結(jié)果表明,該算法能夠在不同環(huán)境下為不同任務(wù)規(guī)劃出可行的協(xié)同飛行航跡,并且在規(guī)劃速度上優(yōu)于傳統(tǒng)蟻群算法,同時能夠降低飛行器的碰撞概率,更好地滿足協(xié)同規(guī)劃的空間協(xié)同約束。由于蟻群算法是一種隨機進化算法,因此對于如何平衡航跡的優(yōu)化質(zhì)量和時間消耗需要進一步研究。

［1］ 鄭昌文,嚴 平,丁明躍,等.飛行器航跡規(guī)劃研究現(xiàn)狀與趨勢［J］.宇航學報,2007,28(6):1441-1446.

［2］ 唐 強,張翔倫,左 玲.無人機航跡規(guī)劃算法的初步研究［J］.航空計算技術(shù),2003,33(1):125-128.

［3］ Li Shidong,Ding Mingyue,Cai Chao.A Novel Path Planning Method Based On Path Network［C］// Proceedings ofthe6th InternationalSymposium on Multispectral Image Processing and Pattern Recognition. Wuhan,China:［s.n.］,2009.

［4］ McLain T,Beard R.Trajectory Planning for Coordinated Rendezvous of Unmanned Air Vehicles［C］//Proceedings of AIAA Guidance Navigation and Control Conference.Clearwater,USA:AIAA Press,2000:1247-1254.

［5］ 嚴 平,丁明躍,周成平.航跡規(guī)劃的一種路線圖方法［J］.計算機工程與應(yīng)用,2004,40(17):218-221.

［6］ Dijkstra E W.A Note on Two Problems in Connexion with Graphs［J］.Numerische Mathematik,1959,1(1):269-271.

［7］ 王銀年.遺傳算法的研究與應(yīng)用［D］.無錫:江南大學,2009.

［8］ Colorni A,Dorigo M,Maniezzo V,et al.Distributed Optimization by Ant Colonies［C］//Proceedings of the 1st European Conference on Artificial Life.France,Paris: Elsevier Publishing,1991:134-142.

［9］ 李 季,孫秀霞.基于改進A-star算法的無人機航跡規(guī)劃算法研究［J］.兵工學報,2008,29(7):788-792.

［10］ Shtovba S D.Ant Algorithms:Theory and Applications［J］.Programming and Computer Software,2005,31(4): 167-168.

［11］ Dorigo M,Gambardella L M.Ant Colony System:A Cooperative Learning Approach to the Travelling Salesman Problem［J］.IEEE Transactions on Evolutionary Computation,1997,1(1):53-66.

［12］ Nowé A,Verbeeck K,Vrancx P.Multi-type Ant Colony: The Edge Disjoint Paths Problem［M］//Dorigo M, Birattari M,Blum C,et al.Ant Colony Optimization and Swarm Intelligence.Berlin,Germany:Springer,2004: 978-982.

［13］ Dorigo M,Maniezzo V,ColorniA.AntSystem: Optimization By a Colony of Cooperating Agents［J］.IEEE Transactions on Systems,Man and Cybernetics, 1996,26(1):29-41.

編輯 陸燕菲

A Multiple Ant Colony Collaborative Planning Algorithm Based on Trajectory Segment

LIU Huijuan,CAI Chao,SUN Xixia
(State Key Laboratory for Multi-spectral Information Processing Technologies, School of Automation,Huazhong University of Science and Technology,Wuhan 430074,China)

To solve the problem that the traditional ant colony algorithm is slow to converge and easy to conflict in the collaborative trajectory planning,considering the features of network graph consist of trajectory segments,a aircraft collaborative trajectory planning algorithm is proposed based on multi-subgroup ant colony coevolution.It divides the ant colony into subgroups with the same number of the aircrafts.Heterogeneous pheromone is introduced to simulate the competition among subgroups,reference length coevolution is adopted to guide the subgroups generating trajectory satisfying the temporal constraints,and the strategy of lost ants pheromone update is added to accelerate the convergence speed.Experimental results demonstrate that this algorithm can generate collaborative flight trajectorys satisfying the constraints of time and space in complex environments for different planning tasks.Compared with the traditional ant colony algorithm,it can generate better collaborative trajectorys,while the planning speed can be improved by 2～3 times.

collaborative trajectory planning;network graph;multi-subgroup;ant colony algorithm;heterogeneous pheromone

10.3969/j.issn.1000-3428.2014.11.029

1000-3428(2014)11-0143-06

A

TJ760

國家部委基金資助項目。

劉慧娟(1989-),女,碩士,主研方向:飛行器路徑規(guī)劃,計算機視覺;蔡 超,副教授、博士;孫希霞,博士研究生。

2013-12-19

2014-01-10E-mail:805577846@qq.com

中文引用格式:劉慧娟,蔡 超,孫希霞.一種基于航跡片段的多蟻群協(xié)同規(guī)劃算法［J］.計算機工程,2014, 40(11):143-148.

英文引用格式:Liu Huijuan,Cai Chao,Sun Xixia.A Multiple Ant Colony Collaborative Planning Algorithm Based on Trajectory Segment［J］.Computer Engineering,2014,40(11):143-148.