一種三維環(huán)境中的無人機(jī)多路徑規(guī)劃方法

劉洋, 章衛(wèi)國, 李廣文, 史靜平

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

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

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

概率地圖法(probability roadmap method, PRM)是一種基于采樣的方法,可以應(yīng)用于高維環(huán)境并能快速構(gòu)建路線圖。概率地圖法可以將連續(xù)空間的規(guī)劃問題轉(zhuǎn)化為拓?fù)淇臻g的規(guī)劃問題,這樣就使路徑規(guī)劃問題的復(fù)雜度與環(huán)境的復(fù)雜程度和規(guī)劃空間的維數(shù)不再相關(guān),而主要依賴于路徑搜索復(fù)雜度。但是概率地圖法存在窄通道的問題,當(dāng)環(huán)境中的障礙物離得近時,障礙物間的區(qū)域會出現(xiàn)沒有采樣點(diǎn)覆蓋的情況。

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

1 改進(jìn)的概率地圖法

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

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

(1)

式中：(xc,yc,zc)為雷達(dá)威脅中心坐標(biāo),(x,y,z)為禁飛區(qū)邊緣上點(diǎn)的坐標(biāo)。

(2)

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

1.1 窄通道問題

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

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

OB=OA·r2/d2

(3)

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

圖1 檢測為碰撞的采樣點(diǎn)的移動

1.2 威脅值的計算

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

(4)

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

2 多目標(biāo)蟻群算法

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

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

一個多目標(biāo)優(yōu)化問題一般存在多個Pareto解,這些解共同構(gòu)成Pareto解集。多目標(biāo)蟻群算法(MACA)的目標(biāo)就是以最小路徑長度和最小威脅強(qiáng)度為目標(biāo)進(jìn)行路徑的選擇,產(chǎn)生一個有效的Pareto解集。傳統(tǒng)的蟻群算法將多個目標(biāo)加權(quán),只播撒一種信息素。若將不同目標(biāo)分開并同時播撒不同種類的信息素,就能夠同時對螞蟻選擇路徑產(chǎn)生影響?？梢詫⑿畔⑺胤譃?類:路徑長度信息素和威脅大小信息素。當(dāng)螞蟻搜索到路徑之后計算路徑的長度和威脅大小,并分別播撒信息素,從而使各個優(yōu)化目標(biāo)的信息素都能對后續(xù)的搜索產(chǎn)生影響,同時優(yōu)化多個目標(biāo)。當(dāng)所有螞蟻找到路徑后對結(jié)果按照路徑長度和威脅大小分別排序,對排名靠前的螞蟻額外播撒信息素。同時在每次迭代后,將螞蟻尋找到的路徑進(jìn)行整理,得到目前最優(yōu)的Pareto解集并保存下來,最終得到位于Pareto前沿上的多個路徑結(jié)果。

2.1 改進(jìn)的信息素局部更新機(jī)制

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

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

(5)

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

2.2 改進(jìn)的信息素全局更新機(jī)制

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

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

(6)

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

(7)

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

(8)

(9)

式中：Lk和Tk為第k條Pareto最優(yōu)路徑的長度和威脅強(qiáng)度,Q1、Q2為常數(shù)。

3 仿真實驗

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

圖2為基本概率地圖法構(gòu)建的路線圖,圖3為改進(jìn)的概率地圖法構(gòu)建的路線圖。由仿真結(jié)果可知,采用基本概率地圖法時,窄通道中沒有采樣點(diǎn)。改進(jìn)的概率地圖法由于將落在威脅上的采樣點(diǎn)進(jìn)行了移動,其中部分采樣點(diǎn)移動到了窄通道中,連通了窄通道的兩側(cè),因此改進(jìn)的概率地圖法比傳統(tǒng)概率地圖法對環(huán)境有更好的覆蓋。

圖2 基本概率地圖法

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

圖3 改進(jìn)的概率地圖法 圖4 算法仿真結(jié)果

表1 10次迭代時各個Pareto解

表2 200次迭代時各個Pareto解

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

圖5 不同迭代次數(shù)時的Pareto解對比

4 結(jié) 論

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

參考文獻(xiàn)：

[1] 于會,于忠,李偉華. 基于小生境粒子群技術(shù)的多航跡規(guī)劃研究[J]. 西北工業(yè)大學(xué)學(xué)報,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ī)艦面多路徑動態(tài)規(guī)劃[J]. 北京航空航天大學(xué)學(xué)報,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] 魏唯,歐陽丹彤,呂帥,等. 動態(tài)不確定環(huán)境下多目標(biāo)路徑規(guī)劃方法[J]. 計算機(jī)學(xué)報,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] 唐強(qiáng),王建元,朱志強(qiáng). 基于粒子群優(yōu)化的三維突防航跡規(guī)劃仿真研究[J]. 系統(tǒng)仿真學(xué)報,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ī)航路規(guī)劃[J]. 系統(tǒng)仿真學(xué)報,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)