張 華 史思總 周一廷 霍建文

(西南科技大學信息工程學院，四川 綿陽 621010)

一種動態(tài)參數(shù)更新的無人機三維路徑規(guī)劃方法

張 華 史思總 周一廷 霍建文

(西南科技大學信息工程學院，四川 綿陽 621010)

針對動態(tài)環(huán)境下無人機三維路徑規(guī)劃的復(fù)雜性及優(yōu)化效率問題，提出了一種可視域下動態(tài)參數(shù)更新的無人機三維路徑規(guī)劃方法。在動態(tài)參數(shù)更新過程中，采用啟發(fā)式動態(tài)更新機制的信息素進行全局更新；利用模擬柵格法進行兩次空間區(qū)域劃分，形成局部節(jié)點集合和全局離散點集合。先在節(jié)點集合中搜索局部路徑，然后在離散點集合中搜索出最優(yōu)路徑。為更好地逼近真實環(huán)境，算法引入函數(shù)DF1產(chǎn)生復(fù)雜的三維動態(tài)環(huán)境。實驗結(jié)果表明，新的蟻群算法具有較好的可行性和實時性，能夠有效解決空間復(fù)雜度、搜索效率等問題，加快全局收斂速度，保持基本蟻群算法較強的魯棒性，實時避開障礙物規(guī)劃出最優(yōu)路徑。

無人機 三維路徑規(guī)劃 蟻群算法 可視域 動態(tài)參數(shù)更新

0 引言

路徑規(guī)劃是無人機實現(xiàn)自動導(dǎo)航的重要組成部分，但在動態(tài)環(huán)境中對無人機路徑規(guī)劃評價標準與靜態(tài)不同，預(yù)先確定的代價函數(shù)不能反映特定任務(wù)的要求。動態(tài)環(huán)境下需要根據(jù)環(huán)境的變化實時做出反應(yīng)。

王維平等在無人機軌跡規(guī)劃方法的文獻綜述中，對規(guī)劃空間的構(gòu)造方法、路徑規(guī)劃算法進行了分類比較，同時提出分析求解無人機路徑規(guī)劃的過程模型[1]。Hao Meng等將遺傳模擬退火算法用于無人機的三維路線規(guī)劃，利用飛行路段和障礙之間的距離轉(zhuǎn)換成俯仰值，并將該值添加到適應(yīng)度函數(shù)，達到路徑最優(yōu)化的目的[2]。Liu Xin等提出利用網(wǎng)格和迭代懲罰方法來實現(xiàn)無人機多路徑規(guī)劃的方法，該方法自動根據(jù)高分辨率的分布地形找到最優(yōu)路徑，以滿足無人機的可操作性的要求[3]。Zhao Junwei等提出改進變步長的A*尋優(yōu)搜索算法，降低了時間和空間的計算復(fù)雜度，達到最佳的搜索策略的合理性和軌跡，從時間協(xié)調(diào)與空間協(xié)調(diào)實現(xiàn)多無人機空中對地攻擊的路線規(guī)劃[4]。洪曄等為解決算法時空開銷大、無人機(unmanned aerial vehicle， UAV)航向改變頻繁的缺點，提出一種基于狀態(tài)聚類方法的分層馬爾可夫決策過程(hierarchical Markov decision processes， HMDP)模型，并將其拓展到三維規(guī)劃中，有效解決UAV 的三維全局路徑規(guī)劃問題，為其在實際飛行中的局部規(guī)劃奠定了基礎(chǔ)[5]。李霞等提出一種改進遺傳算法的三維路徑規(guī)劃方法，該方法對地形高程數(shù)據(jù)進行綜合平滑處理, 建立滿足無人飛行器機動性能的安全飛行曲面, 結(jié)合威脅的量化模型, 采用改進遺傳算法在安全飛行曲面上規(guī)劃出三維飛行路徑[6]。張航等提出一種量子行為粒子群優(yōu)化算法的飛行器三維路徑規(guī)劃策略，該策略建立新地圖和粒子適應(yīng)度函數(shù),從而決定靜態(tài)和動態(tài)避障的適應(yīng)值，可在動態(tài)和靜態(tài)的環(huán)境中產(chǎn)生最優(yōu)路徑[7]。

目前，國內(nèi)外對蟻群算法在動態(tài)環(huán)境下的無人機三維路徑規(guī)劃研究較少，同時傳統(tǒng)蟻群算法存在收斂速度慢和易陷入局部最優(yōu)的缺點。本文提出一種可視域下動態(tài)參數(shù)更新的蟻群算法，進行無人機的三維路徑規(guī)劃。

1 動態(tài)環(huán)境下的三維空間模型建立

設(shè)無人機初始位置為O點，目的地設(shè)為S點，視無人機模型為質(zhì)點，建立無人機飛行三維坐標系O-XYZ，其中X、Y、Z軸分別與地球坐標系的三個軸平行，即初始位置O的坐標相對地球坐標的原點平移N個單位，則S點的坐標為(x,y,z)。設(shè)S點在XOZ、XOY、YOZ平面投影的點為Sxz、Sxy、Syz。由此，點Sxz、Sxy、Syz與S點坐標(x,y,z)分解的點Sx、Sy、Sz及初始點O構(gòu)成三維路徑規(guī)劃空間，如圖1所示。

圖1 三維路徑規(guī)劃空間

在圖1中，將三維空間O-S沿邊OSx進行m等分，沿邊OSy進行n等分，沿邊OSz進行h等分，則三維空間可離散化為序號坐標(i,j,k) (i=0,1,2,…,m；j=0,1,2,…,n；k=0,1,2,…,h)和位置坐標(x,y,z)構(gòu)成的三維離散點集合，則任意一點的坐標可由如下公式求得：

(1)

在三維空間中，假設(shè)O點與S點間有B1，…，Bi個簡化的錐體動態(tài)障礙物。動態(tài)障礙物的模擬采用函數(shù)DF1(Dynamic Function 1)的動態(tài)模型，可模擬復(fù)雜的高維系統(tǒng)[8]。DF1動態(tài)模型中一個錐體的中心高度和中心位置不變化，而另外一個錐體的中心高度H和中心位置(Xd,Yd)時刻變化，從而由式(2)模擬出動態(tài)障礙物。

(2)

式中：Ri為第i個錐體的傾斜度，從而避免錐體高度之間的相互影響；(Xi,Yi)為第i個錐體的中心位置；f(Xd,Yd)為在 (Xd,Yd) 位置的適應(yīng)值。

動態(tài)障礙物通過中心位置坐標、高度、傾斜度可得到局部點的坐標，從而對整個O-S三維空間進行規(guī)劃，構(gòu)成序號坐標和位置坐標的三維點集合空間。利用蟻群算法在三維點集合中進行規(guī)劃，最終得到最優(yōu)路徑。

2 混合啟發(fā)式蟻群算法

2.1 信息素的表示與更新

蟻群算法采用信息素來吸引螞蟻搜索，因此信息素的設(shè)定與更新對最優(yōu)路徑的搜索至關(guān)重要。三維空間中構(gòu)造圖的節(jié)點多，若把相鄰節(jié)點間的路徑作為信息素的載體，算法的空間復(fù)雜度將急劇增大。為避免增大算法的空間復(fù)雜度，將|OSx|、|OSy|、|OSz|中最小的邊作為空間規(guī)劃等分基礎(chǔ)，將三維空間O-S等分成M個子空間，其中M= min{|OSx|,|OSy|,|OSz|}。每個子空間都包含環(huán)境模型的三維離散點的信息素，即三維空間O-S中的每個離散點都有一個信息素值，該子空間總體的信息素構(gòu)成初節(jié)點模型的信息素。

當螞蟻位于某離散點時，對于下一點的搜索就存在一個可視區(qū)域，如圖2所示，從而簡化了子空間的搜索，提升了算法的搜索效率。

當螞蟻每次到達初節(jié)點后，將根據(jù)離散點的信息素進行可視化的搜索。假設(shè)螞蟻在子空間搜索過程中，只有前、橫、縱三種運動方式，即規(guī)定螞蟻在向前運動單位長度的情況下，運動的最大橫向距離為Ly，運動的最大縱向距離為Lz。

圖2 螞蟻搜索可視區(qū)域

當螞蟻經(jīng)過初節(jié)點和子空間離散點后，經(jīng)過路徑的信息素會進行更新處理，避免殘留信息素淹沒啟發(fā)信息。根據(jù)上述信息素的表示，節(jié)點空間采用局部更新的方式，則螞蟻經(jīng)過節(jié)點后，該節(jié)點信息素減弱。信息素在傳統(tǒng)算法模型[9]上，引入動態(tài)更新機制，則更新公式為：

τi′j′k′(t)=(1-ξ)τi′j′k′(t-1)+ξτ0(t0)

(3)

式中：τi′j′k′(t)為當前時刻節(jié)點的信息素，即更新后的信息素；τi′j′k′(t-1)為前一時刻節(jié)點的信息素；i′j′k′為節(jié)點的序號坐標；ξ為信息素的衰減系數(shù)，ξ∈[0,1]；τ0(t0)為節(jié)點上信息素的初值，并規(guī)定初始節(jié)點信息素與鄰域產(chǎn)生的路徑和約束條件的特征節(jié)點數(shù)成反比。

(4)

式中：τijk(t,tn)為更新后離散點的信息素值；ρ(t,tn)為信息素更新系數(shù)；τijk(t)為t時刻離散點的信息素值；i、j、k為離散點的序號坐標；Δτijk(t,tn)為在當前迭代過程中，良好個體從t時刻到tn時刻從一離散點轉(zhuǎn)移到另一離散點留下的信息素量；K為系數(shù)；length(m)為第m只螞蟻經(jīng)過的路徑；min表示最小值。

在搜索過程中，ρ的改變會引起算法的全局搜索能力、收斂速度的改變。為防止搜索能力下降、收斂速度減慢，ρ的值將采用自適應(yīng)調(diào)節(jié)策略。設(shè)計采用揮發(fā)約束系數(shù)ω(ω∈[0,1])來約束ρ的變化，則約束公式如下[10]：

(5)

ω的過程函數(shù)關(guān)系式如下：

ω(Ni)=ω0(1-Ni/NiSum)

(6)

式中：ω0為ω的初始值；Ni為搜索次數(shù)；NiSum為總的搜索次數(shù)。

2.2 啟發(fā)式函數(shù)設(shè)計

信息素大小代表對螞蟻的初次吸引程度，螞蟻經(jīng)過后將自動更新節(jié)點信息素，而螞蟻在可視區(qū)域從當前離散點移動到下一個離散點時，需要根據(jù)啟發(fā)函數(shù)來計數(shù)區(qū)域內(nèi)各離散點的選擇概率。在動態(tài)環(huán)境下，路徑最短和無人機的安全系數(shù)是路徑規(guī)劃的優(yōu)化標準。路徑最短包括當前離散點a與下個離散點b之間的路徑最短Ld，下個離散點b與目標點S的路徑最短Ls，則最短路徑計算公式如下：

(7)

(8)

無人機的安全系數(shù)要求無人機盡可能地遠離動態(tài)環(huán)境中的障礙物?？紤]障礙物存在一定的速度，只要障礙物在空間中的模型不改變，也就是障礙物的離散點不變，則根據(jù)可視區(qū)域來考慮邊界約束，其約束關(guān)系式如下：

δ=(fp-nfp)/fp

(9)

式中：fp為可視區(qū)域中點(i,j,k)中可視點的數(shù)量；nfp為可視點中不可到達區(qū)域的點的數(shù)量。

綜上，啟發(fā)式函數(shù)如下：

(10)

式中：α1、α2、α3為系數(shù)，表示各因素的權(quán)重。

由此，選擇概率pa,b為：

(11)

2.3 路徑規(guī)劃策略

在動態(tài)環(huán)境下，利用蟻群算法進行無人機三維路徑規(guī)劃的算法流程可歸納如下。

① 根據(jù)文中所述方法，建立抽象三維空間、動態(tài)障礙物模型，設(shè)置起點和目標點位置，確定模型中所有離散點、節(jié)點、障礙物的集合，從而確定可視區(qū)域內(nèi)可行點集合；設(shè)置算法運行的初始參數(shù)，將螞蟻置于起點位置，確定螞蟻移動方向。

② 初始化信息素值，計算出節(jié)點信息素值；依據(jù)啟發(fā)函數(shù)(式10)依次計算當前離散點的可視區(qū)域內(nèi)可行點集合的啟發(fā)信息值。

③ 根據(jù)節(jié)點信息素值，設(shè)置螞蟻選擇在節(jié)點上運動的選擇概率，節(jié)點選擇概率的大小與節(jié)點信息素值成正比；按局部信息素更新方式(式3)，進行局部信息素更新。

④ 螞蟻是否在節(jié)點中完成一次路徑的搜索，若是，進入④；否，轉(zhuǎn)到③。

⑤ 根據(jù)離散點選擇概率函數(shù)(式11)，計算離散點的選擇概率；根據(jù)各個離散點的選擇概率采用賭輪盤法選擇可行區(qū)域內(nèi)的點。

⑥ 按全局信息素更新方式(式4)，進行全局信息素更新；在節(jié)點路徑下進行搜索，并判斷算法是否達到迭代次數(shù)；是，輸出結(jié)果；否，轉(zhuǎn)到③。

3 仿真與結(jié)果分析

3.1 實驗仿真

為了驗證算法的可行性，實驗采用Matlab R2010a軟件進行算法仿真驗證。首先，按照DF1模型設(shè)置動態(tài)環(huán)境參數(shù)，地圖有效區(qū)域設(shè)置為100 km×100 km×1.8 km，DF1模型中規(guī)定錐體的中心高度和位置分布為910 m、25 km、25 km，動態(tài)變化次數(shù)為1 200次。

設(shè)置路徑規(guī)劃起點坐標和目標點坐標分別為(2,60,0.35)、(100,4,1.5)，蟻群種群的個數(shù)為20，迭代次數(shù)為200次，螞蟻橫向、縱向的最大變動為0.2 km，信息素的衰減系數(shù)為0.9，系數(shù)K=2，ω的初始值為0.7，啟發(fā)函數(shù)中的因素權(quán)重α1、α2、α3都為1。為了更好地驗證算法，在仿真過程中對適應(yīng)度變化進行監(jiān)測，顯示個體適應(yīng)度值，其個體適應(yīng)度值為長度加上高度，減少程序的計算量，其仿真結(jié)果如圖3～圖5所示。

圖3 t1時刻的仿真結(jié)果圖

圖4 t2時刻的仿真結(jié)果圖

圖5 t3時刻的仿真結(jié)果圖

3.2 結(jié)果分析

比較分析圖3(a)、4(a)、5(a)，障礙物在設(shè)定的整個空間中變化，能有效模擬現(xiàn)實環(huán)境，但局部錐體受到其他錐體高度的影響，錐體的變化不明顯。分析圖3(b)、4(b)、5(b)，路徑規(guī)劃的結(jié)果較為優(yōu)越。比較分析圖3(c)、4(c)、5(c)，隨著環(huán)境障礙物的改變，達到穩(wěn)定的最佳個體適應(yīng)度值，需要迭代的次數(shù)不同，與環(huán)境模型的難易度有關(guān)。圖6為改進的蟻群算法與蟻群算法在GPU加速情況下運行10次的時間對比圖。從圖6可以看出，改進的蟻群算法在實時性優(yōu)于傳統(tǒng)方法。

圖7為動態(tài)環(huán)境高度值變化規(guī)律，隨著動態(tài)變化次數(shù)的增加，錐體中心高度值不斷變化，最后在某個值區(qū)域平穩(wěn)。從圖7可看出，DF1模型產(chǎn)生的動態(tài)環(huán)境并不是隨機變化的。

圖6 改進算法與原始算法運行時間對比

圖7 動態(tài)環(huán)境高度值變化規(guī)律

仿真結(jié)果表明，算法具有可行性、可靠性。其算法的本質(zhì)是基于圖論的蟻群算法，根據(jù)Gutjahr W J給出的圖搜索算法收斂證明[11]，算法能保證收斂，在此不再贅述。

4 結(jié)束語

針對無人機在三維空間動態(tài)環(huán)境下實時路徑規(guī)劃的復(fù)雜性，提出了一種可視域下動態(tài)更新參數(shù)的蟻群算法。算法引入DF1產(chǎn)生復(fù)雜的三維動態(tài)環(huán)境，模擬柵格法進行兩次空間區(qū)域劃分，形成離散點集合和節(jié)點集合。先采用節(jié)點局部搜索一次路徑，然后在可視區(qū)域下離散點全局搜索，并結(jié)合自適應(yīng)算法進行動態(tài)更新機制的信息素全局更新，有效解決無人機在動態(tài)環(huán)境下進行三維路徑規(guī)劃的空間復(fù)雜度、搜索效率等問題，提高實時性。

在實現(xiàn)過程中，算法需要模擬網(wǎng)格進行劃分，如果網(wǎng)格劃分過大，會導(dǎo)致路徑規(guī)劃達不到最優(yōu)化；如果網(wǎng)格劃分過小，則增大算法的計算量。此外，DF1產(chǎn)生復(fù)雜的三維動態(tài)環(huán)境，需要依賴于錐體傾斜度的約束。如何解決這些問題，有待進一步研究。

[1] 王維平,劉娟. 無人飛行器航跡規(guī)劃方法綜述[J].飛行力學,2010,28(2):6-10.

[2] Meng H,Xin G Z.UAV route planning based on the genetic simulated annealing algorithm[C]//Proceedings of the 2010International Conference on Mechatronics and Automation, Xi’an :IEEE,2010:788-793.

[3] Liu X,Zhou C P,Ding M Y.3D Multipath planning for UAV based on network graph[J]. Journal of Systems Engineering and Electronics,2011,22(4): 640-646.

[4] Zhao J W,Zhao J J. Path planning of multi-UAVs concealment attack based on new A* method[A]. Proceedings of the 2014 6th International Conference on Intelligent Human-Machine Systems and Cybernetics[C]//Hangzhou:IEEE,2014:401-404.

[5] 洪曄,房建成. 基于HMDP的無人機三維路徑規(guī)劃[J].北京航空航天大學學報,2009,35(1):100-103.

[6] 李霞,魏瑞軒,周軍,等. 基于改進遺傳算法的無人飛行器三維路徑規(guī)劃[J].西北工業(yè)大學學報，2010,28(3):343-347.

[7] 張航,劉梓溪.基于量子行為粒子群算法的微型飛行器三維路徑規(guī)劃[J].中南大學學報：自然科學版,2013,44(S2):58-62.

[8] Morrison R W, De J K A. A test problem generator for non-stationary environments[C]//Proceedings of the 1999 Congress on Evolutionary Computation,Washington:IEEE,1999:2047- 2053.

[9] Colorni A，Dorigo M,Maniezzo V.Ant system:optimization by a colony of cooperating agents[J].IEEE Transactions on Systems,1996,26(1):1-13.

[10] 王慕抽.基于混合蟻群算法的物流配送路徑優(yōu)化研究[J].物流科技, 2013(4):50-52.

[11] Gutjahr W J.A graph-based ant system and its convergence[J].future generation computer system, 2000 (16):837-888.

A Kind of UAV Three-dimensional Path Planning Method by Dynamic Parameter Update

Aiming at the complexity and optimize efficiency problems of three-dimensional path planning of UAV(unmanned aerial vehicle) in dynamic environment, an ant colony algorithm by dynamic parameters update under a visual domain is proposed. Dynamic parameter update process of the ant algorithm, using heuristic dynamic update mechanism updates global pheromone and using the simulation grid method to zone the space twice and form the local node-set and global collection of discrete points. The algorithm searches partial path between the nodes,and then search for the optimal path between the discrete points. To better approximate real-world environment, the algorithm introduced dynamic function 1 ( DF1 ) produce complex three-dimensional dynamic environment. Through experimental results, the proposed algorithm has good feasibility and real-time for avoiding obstacle and planning the optimal path in real-time,and it can effectively solve spatial complexity, the search efficiency, and accelerate the global convergence speed at the same time maintaining the strong robustness of basic ant colony algorithm.

UAV 3D path planning Ant colony algorithm Visible region Dynamic parameter update

四川省科技廳科技支撐計劃基金資助項目(編號：2014RZ0049)。

張華(1969-)，男，2006年畢業(yè)于重慶大學控制理論與控制工程專業(yè)，獲博士學位，教授；主要從事機器人技術(shù)及其應(yīng)用、嵌入式系統(tǒng)及其應(yīng)用以及智能控制等方向的研究。

TP24

A

10.16086/j.cnki.issn1000-0380.201509004

修改稿收到日期：2015-05-13。