一種基于航跡片段的多蟻群協同規劃算法

劉慧娟,蔡 超,孫希霞

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

一種基于航跡片段的多蟻群協同規劃算法

劉慧娟,蔡 超,孫希霞

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

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

協同航跡規劃;網絡圖;多子群;蟻群算法;異質信息素

1 概述

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

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

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

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

2 規劃空間及協同問題描述

2.1 協同航跡規劃問題描述

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

圖1 航跡網絡的局部示意圖

設V={Vi,i=1,2,…,Nv}為執行協同規劃任務的無人飛行器集合,S={Si,i=1,2,…,Ns}和T= {Ti,i=1,2,…,Nt}分別為與各無人飛行器相對應的起始點和目標點所構成的集合,F={Fi,i=1,2,…,Nf}為禁飛區集合,規劃空間為在R行C列(R和C為常數)的網格環境下構造出的航跡網絡圖。Vi的航跡Ri由一系列航跡片段{Ei,i=1,2,…,Ne}構成,航跡片段由一系列導航點{Pk=(xk,yk,zk),k=1, 2,…,N}表示。

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

2.2 協同約束分析

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

(1)空間協同約束

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

(2)時間協同約束

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

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

2.3 協同航跡代價函數設定

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

(1)單航跡代價

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

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

(2)多航跡協同代價

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

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

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

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

3 多蟻群協同規劃算法

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

3.1 多子群蟻群協同進化機制

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

圖2 多子群蟻群的協同進化

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

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

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

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

3.2 基于異質信息素互斥的狀態轉移

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

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

3.3 信息素更新

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

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

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

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

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

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

迷失螞蟻信息更新機制的作用主要表現在:對迷失螞蟻所經路徑上的信息素進行按比例衰減,從而對后續螞蟻個體產生引導作用,減少后續螞蟻迷失的概率。

3.4 算法步驟

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

步驟1 初始化螞蟻子群及相關參數。

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

步驟3 子群中的螞蟻個體按照狀態轉移規則為對應飛行器構造航跡。

步驟4 一次迭代完畢后,根據構造的航跡結果對信息素結構進行更新。

步驟5 迭代次數達到子蟻群算法上限或構造出的最優航跡與上次迭代相近,則停止迭代,否則跳轉到步驟3。

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

4 實驗結果及分析

在CPU為CoreE7200 2.53 GHz、內存為2.0 GB的PC機上,對算法進行了驗證。PC機的操作系統為Windows XP,程序開發環境為Visual Studio 2005。實驗中使用在分辨率為90 m的3 000×3 000像素的數字地形高程圖上生成的航跡網絡圖,網絡圖由3 680條航跡片段構成。

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

實驗1 為了驗證異質信息素和迷失螞蟻信息素的效果,在規劃環境、協同任務一致的情況下進行2組對比實驗。

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

圖3 規劃時間對比

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

圖4 對比實驗結果和三維仿真

實驗2 為了驗證多蟻群協同算法對不同任務的適應度,在相同環境下對不同規劃任務進行實驗,圖5給出了部分實驗結果圖,表1給出相應的實驗數據。

圖5 不同任務的規劃結果

表1 不同任務的規劃結果數據

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

實驗3 為驗證多蟻群協同算法對不同環境的適應度,對同一任務在不同環境下進行實驗,圖6給出部分實驗結果,表2給出了相應的實驗數據。

圖6 不同規劃環境下的規劃結果

表2 不同規劃環境下的規劃結果數據

表2中的數據和實驗結果驗證了本文算法能夠在不同的規劃環境下規劃出滿足時間和空間協同的協同航跡。

5 結束語

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

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

［2］ 唐 強,張翔倫,左 玲.無人機航跡規劃算法的初步研究［J］.航空計算技術,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］ 嚴 平,丁明躍,周成平.航跡規劃的一種路線圖方法［J］.計算機工程與應用,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］ 王銀年.遺傳算法的研究與應用［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算法的無人機航跡規劃算法研究［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-),女,碩士,主研方向:飛行器路徑規劃,計算機視覺;蔡 超,副教授、博士;孫希霞,博士研究生。

2013-12-19

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

中文引用格式:劉慧娟,蔡 超,孫希霞.一種基于航跡片段的多蟻群協同規劃算法［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.