一種三維環境中的無人機多路徑規劃方法

劉洋, 章衛國, 李廣文, 史靜平

(西北工業大學 自動化學院, 陜西 西安 710129)

路徑規劃作為無人機實現自主任務的基本部分已經得到了廣泛研究。在戰場環境中要為無人機規劃出合理的路徑需要考慮多方面的因素,如無人機本身的性能、地形障礙、威脅等,同時考慮這些因素并得到一個最優的路徑是困難的。此外,不同任務對路徑的評價標準是不同的,因此預先確定的代價函數往往不能反映特定任務的要求。為了解決這些問題,可以預先規劃出多條路徑,在執行任務時根據不同需要選擇合適的路徑。

多路徑規劃問題的研究已有很多,文獻[1]采用了一種小生境粒子群方法,通過多個子種群的共同進化得到多個路徑解,但這種方法需要提前給定代價函數中各指標的權重。文獻[2]采用聚類粒子群算法得到多條路徑,但這種方法只考慮了單個目標。近年來開始有學者將路徑規劃問題當作一個多目標問題來求解,文獻[3]提出了一種改進的多目標進化算法,可以得到一組近似最優多目標解集。文獻[4]提出了一種逆向多目標啟發式搜索方法,可以得到最優路徑集合。文獻[5]首先采用RRT方法生成多條路徑,然后采用進化算法優化路徑。這些方法雖然都得到了非常好的結果,但多是應用于二維連續環境中,很難擴展到高維環境使用。同時,這些方法在規劃過程中每次路徑點位置變化都需要重新計算路徑的可行性,運算速度較慢。

概率地圖法(probability roadmap method, PRM)是一種基于采樣的方法,可以應用于高維環境并能快速構建路線圖。概率地圖法可以將連續空間的規劃問題轉化為拓撲空間的規劃問題,這樣就使路徑規劃問題的復雜度與環境的復雜程度和規劃空間的維數不再相關,而主要依賴于路徑搜索復雜度。但是概率地圖法存在窄通道的問題,當環境中的障礙物離得近時,障礙物間的區域會出現沒有采樣點覆蓋的情況。

本文首先對概率地圖法進行改進,通過移動落在障礙物上的采樣點來增加窄通道中的采樣點數量,使概率地圖能夠更好地覆蓋規劃環境。然后采用改進的蟻群算法生成路徑。蟻群算法是一種可以應用于路線圖的智能算法,但只能優化單個目標。本文通過引入Pareto最優解的思想,提出了一種多目標蟻群算法,同時優化路徑長度和威脅大小2個目標,取得了良好的效果。

1 改進的概率地圖法

概率地圖法用基本構型近似表示環境中的障礙物和威脅。但是實際環境中地面起伏較多,用基本構型近似表示會丟失較多信息,因此地形信息很難用基本構型表示。地形的構建一般采用柵格法,這種方法把環境均勻分解成多個簡單的柵格,每個柵格存儲一個高度數據來表示當前柵格的情況。但是規劃環境中不止包含高程信息,還包含很多的威脅信息。為了解決這個問題,文獻[6]在柵格表示的地形中加入威脅信息擴充為最小威脅曲面。但是構造最小威脅曲面耗時較長。此外,地形信息和威脅信息往往不是同時得到的。地形信息可以通過衛星數據或提前偵查得到,而威脅信息往往在規劃前或任務執行過程中才能得到,因此很難將2種數據一起處理。為了能夠精確表示地形信息并提高運算效率,本文直接將高程數據采用柵格法存儲,同時將威脅信息單獨存儲,然后采用概率地圖法對這些信息進行綜合,將環境信息轉化為概率地圖。這樣在尋找路徑時就不再需要考慮地形和威脅的碰撞問題。

仿真采用的規劃環境中威脅設置為雷達威脅和高炮威脅。其中雷達威脅為半球形,離球心越遠,威脅越小。高炮威脅為圓柱形,離中軸線越遠威脅越小。對于威脅較大的區域設置為禁飛區,飛機不允許通過。雷達禁飛區邊緣的表達式如(1)式所示,高炮禁飛區的表達式如(2)式所示。

(1)

式中：(xc,yc,zc)為雷達威脅中心坐標,(x,y,z)為禁飛區邊緣上點的坐標。

(2)

式中：(xp,yp)為高炮威脅中心的水平坐標,(x,y,z)為禁飛區邊緣上點的坐標,h為高炮威脅禁飛區的最大高度。

1.1 窄通道問題

傳統PRM算法采用均勻采樣的采樣策略,在大多數情況下算法性能都能得到充分發揮,但是當規劃環境可擴展性較差,如規劃環境中存在窄通道時,會出現概率地圖無法完全覆蓋規劃環境的情況。當2個威脅靠的較近時,中間會出現一個狹長的區域,即窄通道。由于采用點數量有限,而窄通道中的自由空間較小,當采樣點數量一定時,落在通道中的采樣點相對較少,可能無法連接通道兩端的子圖。為了完成路線圖的構建,需要增加采樣點的數量,這樣就使算法效率下降。本文在概率地圖的構建過程中利用了與威脅碰撞的點,通過將這些點移動到自由空間中,來增加窄通道中的采樣點密度,這樣就不再需要補充采樣,提高了地圖的構建效率。

為了簡化計算,移動落在威脅上的采樣點時不改變點的高度,只改變其水平坐標,這樣就可以將問題簡化到一個二維平面中,2種威脅在采樣點高度處的橫截面都為圓形,因此可以采用相同的方法移動采樣點。如圖1所示為一個威脅的橫截面。一個采樣點落在威脅內,初始位置為A,由于位于威脅體內,它被檢測為碰撞的,將A點沿著由圓心向圓外的方向移動,就可以得到障礙物周圍的一個無碰撞的采樣點B。點B的位置計算公式如下式所示:

OB=OA·r2/d2

(3)

式中:OA、OB為向量,d為向量OA的長度,r為圓的半徑。

圖1 檢測為碰撞的采樣點的移動

1.2 威脅值的計算

對于一個路徑段上的威脅強度計算,一般都是在路徑段上取一定數量的點計算威脅值然后累加得到。當飛機暴露在雷達范圍內越久越容易被雷達發現,因此當飛行速度一定時路徑段越長則受到的威脅越大。仿真中計算威脅時采用如(4)式所示的計算方法,在計算得到的威脅值基礎上乘以路徑段長度。這樣路徑段越長,威脅就越大。此外,當威脅與路徑點相距較遠時,認為威脅對路徑點沒有威脅,因此在計算時只考慮了一定距離范圍內的所有威脅。在計算時將路徑段均分為5段,取4個分割點進行計算并累加。

(4)

式中:Tthreat,i表示第i段路徑上的威脅值,Li表示路徑段的長度,d表示威脅j與路徑段i上點之間的距離,當距離大于設定的范圍值時為無窮大。

2 多目標蟻群算法

蟻群算法在多目標問題中的應用已有很多,文獻[7]將所有的優化目標統一在一個代價函數中進行求解。但這樣只能得到一個解,不利于決策者進行決策。此外幾個優化目標之間往往是相互沖突的,很難找到一個解在各個優化目標上都是最優的。為了解決這個問題,本文將Pareto解集引入蟻群算法中。多目標蟻群算法可以尋找到多個解,即Pareto解集。Pareto解的定義如定義1所示。

定義1(Pareto最優解) 假設以函數F(x)=min[f1(x),f2(x)…fm(x)]為目標進行優化,X為問題的決策空間。如果不存在任何的x∈X,可以使得fi(x)≤fi(x′),?i∈{1,2,…,m},并且fj(x)≤fj(x′),?j∈{1,2,…,m},則x′是多目標優化問題的一個Pareto最優解。

一個多目標優化問題一般存在多個Pareto解,這些解共同構成Pareto解集。多目標蟻群算法(MACA)的目標就是以最小路徑長度和最小威脅強度為目標進行路徑的選擇,產生一個有效的Pareto解集。傳統的蟻群算法將多個目標加權,只播撒一種信息素。若將不同目標分開并同時播撒不同種類的信息素,就能夠同時對螞蟻選擇路徑產生影響。可以將信息素分為2類:路徑長度信息素和威脅大小信息素。當螞蟻搜索到路徑之后計算路徑的長度和威脅大小,并分別播撒信息素,從而使各個優化目標的信息素都能對后續的搜索產生影響,同時優化多個目標。當所有螞蟻找到路徑后對結果按照路徑長度和威脅大小分別排序,對排名靠前的螞蟻額外播撒信息素。同時在每次迭代后,將螞蟻尋找到的路徑進行整理,得到目前最優的Pareto解集并保存下來,最終得到位于Pareto前沿上的多個路徑結果。

2.1 改進的信息素局部更新機制

在局部信息素更新中,需要同時考慮2種信息素的更新,路徑段(r,s)上的信息素更新如下式所示:

τ(r,s)←ρ·τ(r,s)+Δτ1(r,s)+Δτ2(r,s)

(5)

式中：ρ為揮發系數,τ(r,s)為路徑段上的信息素含量,Δτi(r,s)為2種信息素的增量。

2.2 改進的信息素全局更新機制

為了能夠得到Pareto前沿,我們對得到的路徑分別按照路徑長度和威脅強度2個指標進行排序并按照基于排序的蟻群算法更新路徑段上的信息素含量。對于多目標蟻群算法,全局信息素更新規則如下所示:

τ(r,s)=(1-ρ1)τ(r,s)+Δτ(r,s)

(6)

式中：ρ1為揮發系數,Δτ(r,s)為信息素增量,計算如下所示:

(7)

式中：k′為到目前為止搜索到的解的個數,ai,bj分別表示按路徑長度和按威脅強度排序中的第i位和第j位對應的系數。Δτ1k(r,s)和Δτ2k(r,s)表達式如下所示:

(8)

(9)

式中：Lk和Tk為第k條Pareto最優路徑的長度和威脅強度,Q1、Q2為常數。

3 仿真實驗

為了驗證算法有效性,針對如圖1所示的規劃環境進行了仿真實驗,規劃環境范圍為400 km×400 km,威脅設置為1個雷達威脅和3個高炮威脅,其中高炮威脅位置為(280,220)、(95,149)、(155,101),雷達威脅位置為(170,280)。位于(95,149)和(155,101)的2個高炮威脅由于距離較近,中間形成了窄通道。構建概率地圖的采樣點數量為300個,采樣點最大高度設為4 km。

圖2為基本概率地圖法構建的路線圖,圖3為改進的概率地圖法構建的路線圖。由仿真結果可知,采用基本概率地圖法時,窄通道中沒有采樣點。改進的概率地圖法由于將落在威脅上的采樣點進行了移動,其中部分采樣點移動到了窄通道中,連通了窄通道的兩側,因此改進的概率地圖法比傳統概率地圖法對環境有更好的覆蓋。

圖2 基本概率地圖法

在改進的概率地圖法得到的路線圖基礎上,對本文提出的改進蟻群算法進行了仿真驗證。圖4a)為改進蟻群算法在迭代10次之后的仿真結果,圖4b)為迭代100次后的仿真結果,此時算法已經收斂。各個解的值如表1和表2所示。

圖3 改進的概率地圖法 圖4 算法仿真結果

表1 10次迭代時各個Pareto解

表2 200次迭代時各個Pareto解

圖5為不同迭代次數時的各個解。由仿真結果可知,改進的蟻群算法可以同時找到多個解,隨著迭代次數的增加,算法可以收斂到一個Pareto解集上。在算法執行到10代時已經有多個解出現,在執行到200代時算法已經收斂到最優解。各個解各有側重,具有較好的多樣性,有利于決策者根據當前的需求,從這組非支配解中選擇合適的解作為無人機的路徑。同時,當無人機任務發生改變時可以直接從解集中選擇其他合適的解,不需要重新計算。

圖5 不同迭代次數時的Pareto解對比

4 結 論

本文針對多路徑規劃問題,在采用改進概率地圖法構建路線圖的基礎上,提出了一種多目標蟻群算法,這種方法將路徑長度和威脅強度2個目標分開計算并分別播撒信息素。仿真結果表明,改進的概率地圖法可以更好地覆蓋環境,多目標蟻群算法可以同時優化2個目標并得到一組解,有利于決策者選擇合適的路徑。

參考文獻：

[1] 于會,于忠,李偉華. 基于小生境粒子群技術的多航跡規劃研究[J]. 西北工業大學學報,2010,28(3):415-520

Yu Hui, Yu Zhong, Li Weihua. Multiple Routes Planning for Air Vehicles Based on Niche Particle Swarm Optimization[J]. Journal of Northwestern Polytechnical University,2010, 28(3):415-520 (in Chinese)

[2] 韓維,司維超,丁大春,等. 基于聚類PSO算法的艦載機艦面多路徑動態規劃[J]. 北京航空航天大學學報,2013,39(5):610-614

Han Wei, Si Weichao, Ding Dachun, et al. Multi-Routes Dynamic Planning on Deck of Carrier Plane Based on Clustering PSO[J]. Journal of Beijing University of Aeronautics and Astronautics,2013,39(5): 610-614 (in Chinese)

[3] Conesa-Munoz J, Ribeiro A, Andujar D, et al. Multi-Path Planning Based on a NSGA-II for a Fleet of Robots to Work on Agricultural Tasks[C]∥2012 IEEE Congress on Evolutionary Computation, 2012: 1-8

[4] 魏唯,歐陽丹彤,呂帥,等. 動態不確定環境下多目標路徑規劃方法[J]. 計算機學報,2011,34(5):836-846

Wei Wei, Ouyang Dantong, Lü Shuai, et al. Multiobjective Path Planning under Dynamic Uncertain Environment[J]. Chinese Journal of Computers, 2011,34(5): 836-846 (in Chinese)

[5] Seok J H, Lee J Y, Oh C, et al. Diverse Multi-Path Planning with a Path-Set Costmap[C]∥11th International Conference on Control, Automation and Systems, 2011: 694-699

[6] 唐強,王建元,朱志強. 基于粒子群優化的三維突防航跡規劃仿真研究[J]. 系統仿真學報,2004,16(9):2033-2036

Tang Qiang, Wang Jianyuan, Zhu Zhiqiang. The Simulation Study of PSO Based 3-D Vehicle Route Planning for Low Attitude Penetration[J]. Journal of System Simulation,2004,16(9): 2033-2036 (in Chinese)

[7] 稅薇,葛艷,韓玉,等. 基于混合蟻群算法的無人機航路規劃[J]. 系統仿真學報,2011,23(3):574-576

Shui Wei, Ge Yan, Han Yu, et al. Path Planning for UAV Based on Mixed Ant Colony Algorithm[J]. Journal of System Simulation, 2011, 23(3): 574-576 (in Chinese)