劉慧娟,蔡 超,孫希霞

(華中科技大學(xué)自動(dòng)化學(xué)院多譜信息處理技術(shù)國(guó)防科技重點(diǎn)實(shí)驗(yàn)室,武漢430074)

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

劉慧娟,蔡 超,孫希霞

(華中科技大學(xué)自動(dòng)化學(xué)院多譜信息處理技術(shù)國(guó)防科技重點(diǎn)實(shí)驗(yàn)室,武漢430074)

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

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

1 概述

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

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

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

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

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

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

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

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

設(shè)V={Vi,i=1,2,…,Nv}為執(zhí)行協(xié)同規(guī)劃任務(wù)的無(wú)人飛行器集合,S={Si,i=1,2,…,Ns}和T= {Ti,i=1,2,…,Nt}分別為與各無(wú)人飛行器相對(duì)應(yīng)的起始點(diǎn)和目標(biāo)點(diǎn)所構(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)航點(diǎn){Pk=(xk,yk,zk),k=1, 2,…,N}表示。

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

2.2 協(xié)同約束分析

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

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

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

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

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

其中,Tmax,Tmin分別為飛行器集合V中最早抵達(dá)目標(biāo)點(diǎn)和最晚抵達(dá)目標(biāo)點(diǎn)的時(shí)間。

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

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

(1)單航跡代價(jià)

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

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

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

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

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

綜合單航跡代價(jià)、協(xié)同系數(shù)以及協(xié)同約束可得航跡組的協(xié)同評(píng)價(jià)指標(biāo):

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

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

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

3.1 多子群蟻群協(xié)同進(jìn)化機(jī)制

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

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

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

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

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

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

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

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

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

3.3 信息素更新

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

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

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

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

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

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

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

3.4 算法步驟

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

步驟1 初始化螞蟻?zhàn)尤杭跋嚓P(guān)參數(shù)。

步驟2 對(duì)所有的螞蟻?zhàn)尤壕鶊?zhí)行步驟3～步驟5。

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

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

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

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

4 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

圖3 規(guī)劃時(shí)間對(duì)比

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

圖4 對(duì)比實(shí)驗(yàn)結(jié)果和三維仿真

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

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

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

實(shí)驗(yàn)結(jié)果均滿足空間協(xié)同,且從表1可以看出,每個(gè)任務(wù)的協(xié)同系數(shù)均小于1,說(shuō)明算法能夠?yàn)椴煌蝿?wù)規(guī)劃出符合時(shí)間和空間協(xié)同的航跡。

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

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

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

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

5 結(jié)束語(yǔ)

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

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

［2］ 唐 強(qiáng),張翔倫,左 玲.無(wú)人機(jī)航跡規(guī)劃算法的初步研究［J］.航空計(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］ 嚴(yán) 平,丁明躍,周成平.航跡規(guī)劃的一種路線圖方法［J］.計(jì)算機(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］.無(wú)錫:江南大學(xué),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］ 李 季,孫秀霞.基于改進(jìn)A-star算法的無(wú)人機(jī)航跡規(guī)劃算法研究［J］.兵工學(xué)報(bào),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

國(guó)家部委基金資助項(xiàng)目。

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

2013-12-19

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

中文引用格式:劉慧娟,蔡 超,孫希霞.一種基于航跡片段的多蟻群協(xié)同規(guī)劃算法［J］.計(jì)算機(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.