黃書捷

(漳州市測繪設(shè)計研究院,福建漳州 363000)

無人機在高原山地環(huán)境下航攝軌跡的規(guī)劃

黃書捷?

(漳州市測繪設(shè)計研究院,福建漳州 363000)

在高原、山地地形起伏較大的環(huán)境下,無人機對點狀、線狀、面狀多個目標(biāo)拍攝時的軌跡需要進(jìn)行最優(yōu)化規(guī)劃?？傮w航跡規(guī)劃分為兩個階段:全局規(guī)劃階段,即對多個目標(biāo)進(jìn)行全局最短路線規(guī)劃;局部規(guī)劃階段,即為躲避地形威脅,對最短路線中,目標(biāo)點之間不符合要求的路線進(jìn)行重規(guī)劃,最終得到最優(yōu)的路線軌跡。分別采用蟻群算法和A?算法進(jìn)行全局規(guī)劃和局部規(guī)劃,仿真結(jié)果表明了本文軌跡規(guī)劃方法的有效性及高效性。

無人機航線;分段規(guī)劃;蟻群算法;A?算法

1　引 言

由于傳統(tǒng)航空攝影受天氣、航空管制等諸多條件的限制,成本高,時效性較差。無人機攝影測量相對傳統(tǒng)航測具有靈活,高效,機動性能好等特點,在高山等高分辨率遙感影像數(shù)據(jù)缺乏的地區(qū),具有很大的應(yīng)用前景。近年來,無人機攝影測量技術(shù)發(fā)展迅速,已廣泛應(yīng)用于農(nóng)業(yè)、林業(yè)、水利、交通、國土資源等國民經(jīng)濟各領(lǐng)域。在高原地區(qū),需要定期對道路,橋梁,鐵路,電力線路等進(jìn)行巡檢,由于環(huán)境惡劣,需要投入大量人力物力,成本高,效率低,因此,使用無人機進(jìn)行巡檢,具有很大優(yōu)勢。

無人機航跡規(guī)劃是指在一定的約束條件下,比如無人機的機動性能、地形環(huán)境限制、燃油量等因素,從起始點出發(fā),經(jīng)過預(yù)定的任務(wù)點,到達(dá)目標(biāo)點的最優(yōu)飛行軌跡。本文首先對地形進(jìn)行仿真,建立三維模型,使得規(guī)劃環(huán)境更加貼近實際,然后將航線規(guī)劃分為全局規(guī)劃和局部規(guī)劃,全局規(guī)劃是TSP(Traveling Salesman Problem)問題,不考慮無人機機動能力和地形威脅;局部規(guī)劃是針對全局路線中兩任務(wù)點之間,根據(jù)無人機的性能,飛經(jīng)的地理環(huán)境、威脅環(huán)境等因素,對已知目標(biāo)規(guī)劃出滿足要求的航跡。蟻群算法(ant colony optimization,ACO)是一種新的啟發(fā)式仿生類并行智能進(jìn)化算法,近幾年在優(yōu)化領(lǐng)域中出現(xiàn)不久,最早成功應(yīng)用于解決TSP問題[1],在解決TSP問題上具有較高效率,本文采用蟻群算法得到全局最短路徑。局部規(guī)劃是兩任務(wù)點之間的線路規(guī)劃,目前常用解決方法有:動態(tài)規(guī)劃法、快速隨機搜索樹算法、遺傳算法、概率地圖法、Voronoi圖法和啟發(fā)式搜索算法等。啟發(fā)式搜索算法最早運用在計算機和機器尋路等領(lǐng)域,在較大的搜索空間下搜索時間很短,效率高。目前,研究最多的是啟發(fā)式A?算法[2]。本文將采用啟發(fā)式A?算法進(jìn)行局部航線規(guī)劃。

2　主要威脅源及限制條件

對于測繪型無人機,主要的威脅源為地形威脅及大氣條件威脅,主要考慮的限制條件有無人機的轉(zhuǎn)彎角度限制,飛行高度限制以及航跡的長度約束以及燃油限制等。

2．1地形限制

對于地形的限制,實驗中采用隨機函數(shù)法進(jìn)行仿真,通過數(shù)學(xué)模型函數(shù),來模擬已知地形的原始三維地形。數(shù)學(xué)模型函數(shù)形式為[3]:

其中,x,y是水平面上的點坐標(biāo),z是水平面上對應(yīng)的坐標(biāo)點的高度。a,b,c,d,e,f,g是常系數(shù)。通過控制這幾個常系數(shù)的取值,可以對各種實際地貌的地形進(jìn)行模擬,作為在地面已探知的任務(wù)區(qū)域的地形地貌等信息。

接著采用式(2)生成山峰威脅模型,函數(shù)形式為[3]:

其中,zi為第i個山峰最高點的高度,xoi,yoi對應(yīng)第i個山峰最高點在水平面上的坐標(biāo),xsi,ysi的值決定了第i個山峰的坡度,通過改變這兩個值,可以控制x軸方向和y軸方向的陡峭程度。

將地形模型和山峰模型進(jìn)行疊加,即選取兩個模型中較高的點,函數(shù)形式為[3]:

通過疊加融合,模擬了真實的地形地物,再現(xiàn)了山峰威脅模型,用此模型作為航線規(guī)劃環(huán)境,簡化了航線規(guī)劃的復(fù)雜程度。

2．2大氣威脅

在起飛階段,為了獲得足夠的爬升力,無人機需要逆風(fēng)起飛,而各種不同的無人機對于風(fēng)速的具體數(shù)值有著嚴(yán)格的限制。無人機在升空后,在巡航階段可能會遇到天氣變化,云層將會給無人機帶來威脅,無人機表面可能會結(jié)冰或者無人機電子設(shè)備受到云層中雷電的襲擊而破壞[4]。由于天氣的變化情況十分復(fù)雜,本文不對此威脅進(jìn)行模擬。

2．3無人機約束條件

無人機由于制造水平,成本的限制以及用途的不同,不同類型的無人機性能各異。在航跡規(guī)劃中,需要考慮的限制如下:

(1)角度限制。由于飛行器機動性能的限制,需要考慮飛行器的最大爬升/下降角和最大拐彎角。測繪型無人機航拍需要所得的相片比例尺一致,所以無人機不進(jìn)行垂直方向的機動,可不考慮爬升角和下降角。

(2)高度限制。無人機必須與地面保持足夠的安全距離,才能有效地降低觸地概率。

(3)最大航跡長度限制。由于無人機受燃油有限負(fù)荷或者到達(dá)時間的限制,因此需要對航跡限定最大允許長度Lmax。當(dāng)無人機飛行狀態(tài)不同時,如爬升、下滑及平飛時的油耗系數(shù)是不一樣的。規(guī)劃過程中,長度大于最大允許長度的航跡需被排除。

3　航跡規(guī)劃

3．1地圖數(shù)據(jù)表示方法

由地圖學(xué)的基本理論,我們將航拍目標(biāo)分為點狀目標(biāo)、線狀目標(biāo)和面狀目標(biāo)。點狀目標(biāo)是指按照設(shè)定的分辨率要求,單張照片可以覆蓋的地物,如獨立房屋等。在線狀目標(biāo)具有一定長度且比較狹窄的地物,如河流,公路,堤壩等。對于此類地物,無人機必須沿其中心線飛行進(jìn)行拍攝。面狀目標(biāo)是指占有比較大地理空間區(qū)域的地物,如湖泊,森林,城鎮(zhèn)等。對于面狀目標(biāo)的軌跡規(guī)劃可見參考文獻(xiàn)[5]。

3．2全局航跡規(guī)劃

3．2．1TSP問題

旅行商問題,即TSP問題,是數(shù)學(xué)領(lǐng)域中著名問題之一。假設(shè)有一個旅行商人要拜訪n個城市,他必須確定每個城市的拜訪順序,得到最終的拜訪路徑。每個城市只能拜訪一次,而且最后要回到原來出發(fā)的城市,問題的關(guān)鍵在于要求拜訪的最終路徑最短。無人機的航線規(guī)劃問題是從起始點出發(fā),經(jīng)過若干任務(wù)點,再回到回收場,類似于TSP問題。

3．2．2蟻群算法原理

研究表明,螞蟻在行進(jìn)過程中會留下一種分泌物,而這種分泌物可以引導(dǎo)后面的螞蟻對路徑的選擇。一條路徑上走過的螞蟻越多,留下的分泌物就會越多,而分泌物越多,螞蟻選擇這條路徑的概率就越大。因此,螞蟻群體的集體行為實際上形成一種學(xué)習(xí)信息的正反饋現(xiàn)象,通過這種信息交流,促使螞蟻找到通向食物的最短路徑[6]。整個蟻群就是通過這種信息素進(jìn)行相互協(xié)作,形成正反饋,從而使多個路徑上的螞蟻都逐漸聚集到最短的那條路徑上。

3．2．3蟻群算法基本流程

以TSP問題為例,螞蟻系統(tǒng)具體包括了以下三個方面的內(nèi)容。

第一、初始化。首先構(gòu)造一個禁忌表,用來記錄每一只螞蟻走過的節(jié)點,將螞蟻所在的起始節(jié)點放入禁忌表;接著還要對每條路徑上的信息素的濃度進(jìn)行初始化,假設(shè)初始濃度為r。

第二、選擇路徑。計算螞蟻到其他節(jié)點的概率分布。概率的計算如式(4):

式(4)表示螞蟻在t時刻由節(jié)點i選擇節(jié)點j的概率。τij(t)為i,j路徑上的信息素濃度,ηij是j相對于i的可見度(在TSP問題中常以距離的倒數(shù)表示),α,β分別表征信息素和可見度在概率計算中的權(quán)重,其值越大,則信息素和可見度對于螞蟻選擇下一個節(jié)點的影響越大。allowed是指不在螞蟻禁忌表中的節(jié)點集合,即螞蟻還未經(jīng)過的節(jié)點。由于禁忌表的制約,螞蟻不會選擇已經(jīng)在禁忌表中的節(jié)點。

第三、信息素更新。由于各條路線上的信息素也會隨時間逐漸蒸發(fā),而螞蟻經(jīng)過會增加信息素濃度,所以需對信息素進(jìn)行更新。ρ為信息素的殘留因子,1-ρ表示信息素的揮發(fā)因子。經(jīng)過tn個時間單位后,根據(jù)式(5)式(6),對各條路線上的信息素進(jìn)行更新。

△τij表示第k只螞蟻在本次循環(huán)中,節(jié)點i,j之間的路徑上留下的信息素增量,用式(7)計算。

其中,Q為常數(shù),Fk表示第k只螞蟻在本次循環(huán)中的目標(biāo)函數(shù)值(一般為路徑的總長度)[7]。

蟻群算法一般流程基本步驟描述如下:

(1)初始化螞蟻數(shù)量m,最大循環(huán)次數(shù)NC_max,初始信息素值和禁忌表;

(2)開始迭代,將各螞蟻的初始出發(fā)點放入禁忌表中;

(3)計算每只螞蟻移至下個節(jié)點的概率;

(4)按概率(采用輪盤法)選擇并移動至下個節(jié)點,將此節(jié)點加入禁忌表;

(5)如果螞蟻走遍所有節(jié)點則執(zhí)行(6),否則返回(3);

(6)計算螞蟻該次總路線長度,并記錄當(dāng)前最短路線;

(7)用式(5),式(6),式(7)更新全局信息素;

(8)若迭代次數(shù)達(dá)到NC_max則輸出最優(yōu)解,退出算法,否則返回(2)繼續(xù)執(zhí)行[8]。

3．3局部航跡規(guī)劃

3．3．1A?算法原理

A?算法是在1968年由Hart,Nilsson,Raphael等人提出的一種啟發(fā)式的搜索算法,用于搜尋最短路徑,其被廣泛運用于尋找目標(biāo)和圖形遍歷[9]。無人機航跡規(guī)劃本質(zhì)上是從起點不斷擴展航跡節(jié)點,最終找到終點。A?算法進(jìn)行航跡搜索時,通常將規(guī)劃環(huán)境按一定比例劃分為二維或者三維網(wǎng)格的形式,每個節(jié)點可以往任意方向擴展,按代價函數(shù)找到最小代價點。由于需要考慮無人機的機動性能,所以要根據(jù)無人機的最大轉(zhuǎn)彎角來限定可以擴展的節(jié)點。有時出現(xiàn)障礙阻礙了最小代價點的擴展,此時要退回上一個節(jié)點,尋找次優(yōu)代價點繼續(xù)擴展,最終找到最小代價軌跡。其中A?算法的航跡代價函數(shù)為:

其中x為當(dāng)前節(jié)點,g(x)為從起始點到該點的真實代價,u(x)為啟發(fā)函數(shù),表示當(dāng)前節(jié)點到目標(biāo)位置代價的估值,f(x)即為搜索空間節(jié)點的總代價[10]。

3．3．2算法流程

搜索過程中需要用到以下幾個關(guān)鍵的矩陣:①搜索圖G,存儲當(dāng)前已生成的路線;②OPEN列表,存儲已經(jīng)生成但還沒進(jìn)行擴展的結(jié)點;③CLOSED表,存儲已經(jīng)擴展過的結(jié)點。同時,每個結(jié)點的代價估計值f和g也包含在兩張列表中。

A?算法的流程步驟如下:

(1)生成一個搜索圖G,此時圖中只包含了起始點s,同時把起始點s加入到OPEN列表中。

(2)生成一個CLOSED列表,初始值為空。

(3)循環(huán):

①如果OPEN列表為空,則退出循環(huán),搜索失敗。

②如果目標(biāo)點被加入CLOSED列表,說明目標(biāo)點找到,則退出循環(huán),搜索成功。

③對當(dāng)前節(jié)點n可選擇的每一個節(jié)點ni進(jìn)行判斷,如果ni已經(jīng)在CLOSED列表或者OPEN列表中,則將其跳過,否則將其加入OPEN列表中,把當(dāng)前節(jié)點n作為節(jié)點ni的父節(jié)點。

④在OPEN列表中尋找f值最小的節(jié)點m,然后把當(dāng)前節(jié)點n放入CLOSED中,把當(dāng)前節(jié)點換成節(jié)點m,把當(dāng)前節(jié)點移動的方向記錄在搜索圖G中,把f和g的值分別記錄在OPEN和CLOSED列表中。

(4)如果找到目標(biāo)點g,順著搜索圖G,得到從目標(biāo)點g到起始點s的路徑,獲得最優(yōu)路徑,成功退出[11]。

4　仿真實驗

4．1 航跡規(guī)劃環(huán)境模型

利用式(1),式(2),得到原始地形和山峰模型,通過對原始地形和山峰模型進(jìn)行融合疊加,得到航跡規(guī)劃的環(huán)境模型得到規(guī)劃環(huán)境模型,規(guī)劃空間為100× 100×300的區(qū)間,如圖1所示。式(1)中參數(shù)取值為:a =20,b=0,c=20,d=3,e=8,f=1,g=0,h=20,i=0。山峰數(shù)為7,參數(shù)取值如表1所示。4．2 規(guī)劃區(qū)域

山峰威脅模型參數(shù)設(shè)置　表1

圖1　環(huán)境模型

如圖2所示。1,2,3,6,9為點狀目標(biāo),4與5的連線為線狀目標(biāo),7,8為面狀目標(biāo)航拍路線的切入點以及退出點。

圖2　航線規(guī)劃區(qū)域

文中分別采用蟻群算法和A?算法,matlab2013a中進(jìn)行全局和局部規(guī)劃仿真實驗。

4．3仿真實驗

4．3．1全局規(guī)劃仿真實驗

為保持比例尺一致,無人機飛行高度不變,不進(jìn)行垂直方向機動,只進(jìn)行水平機動,飛行高度為100,表2為航線規(guī)劃時蟻群算法的參數(shù)設(shè)置。以點1為無人機的起飛點與降落點,圖3為用蟻群算法得到的最短路線,全局規(guī)劃階段用時6．6 s。但是從三維圖4中可以看出點1與點9之間的航線直接穿越了山體,顯然不符合航線規(guī)劃的要求,需要對點1～點9之間的航線進(jìn)行重規(guī)劃。

蟻群算法參數(shù)設(shè)置　表2

圖3　蟻群算法所得最短航線

圖4　蟻群算法所得最短航線三維圖

4．3．2局部航線重規(guī)劃

為證實A?算法在局部規(guī)劃中的有效性,本文先取區(qū)域中的(0,0)為起始點,(100,100)為目標(biāo)點,進(jìn)行仿真實驗,得到航線如圖5,可以看出航線有效地避開了地形的威脅,滿足規(guī)劃要求。

圖5　A?算法所得最優(yōu)航線

接著對點1和點9之間的航線重規(guī)劃,得到航線如圖6所示。局部重規(guī)劃用時1．8 s。

圖6　點1與點9之間最優(yōu)航線

4．3．3全局規(guī)劃航線與局部規(guī)劃航線合成

將全局規(guī)劃的最短航線與局部規(guī)劃的最優(yōu)航線進(jìn)行合成,得到了最終的無人機規(guī)劃航線,兩階段的航線設(shè)計用時為8．4 s,如圖7所示。

圖7　合成的最終航線

4．3．4結(jié)果分析

航跡規(guī)劃所得的結(jié)果表明:

(1)基于航跡約束條件,通過分階段設(shè)計,能夠規(guī)劃出一條滿足要求的航跡,總設(shè)計時間為8．4 s,算法高效,具有工程實用性。

(2)對圖7分析可知,所得的最優(yōu)航跡有效的避開了威脅,實現(xiàn)了無人機的安全飛行。

5　結(jié) 語

本文將航線設(shè)計分為兩個部分,首先用蟻群算法規(guī)劃出最短航線,接著采用A?算法對最短航線中不符合航線要求的航線段進(jìn)行重規(guī)劃,最后進(jìn)行航線合成得到最終航線。文中詳細(xì)闡述了蟻群算法,A?算法的原理及算法流程,很好地滿足航線設(shè)計的要求,而且分階段規(guī)劃后,僅需要對部分航線段重規(guī)劃,減少了處理時間,效率高,能夠滿足高原、山地等地形起伏較大的地區(qū)航測無人機航線規(guī)劃。同時,該方法也可以用于低空無人機在城市中飛行的航線規(guī)劃。

[1] Mettler B,Bachelder E．Combining on-and offline optimization techniques for efficient autonomous vehicle’s trajectory planning[C]//AIAA Guidance,Navigation,and Control Conference,San Francisco,CA．2005．

[2] 鄭家良．無人機航跡規(guī)劃與導(dǎo)航的方法研究及實現(xiàn)[D]．成都:電子科技大學(xué),2009．

[3] Nikolos I K,Valavanis K P,Tsourveloudis N C,et al．Evolutionary algorithm based offline/online path planner for UAV navigation[J]．Systems,Man,and Cybernetics,Part B:Cybernetics,IEEE Transactions on,2003,33(6):898～912．

[4] 戴定川,盛懷潔,邊曉利．無人機航跡規(guī)劃分段需求分析[J]．戰(zhàn)術(shù)導(dǎo)彈技術(shù),2011(6):63～69．

[5] 陳海,王新民,焦裕松等．一種凸多邊形區(qū)域的無人機覆蓋航跡規(guī)劃算法[J]．航空學(xué)報,2010,31(9):1802～1807．

[6] Macro Dorigo,Mauro Birattari,Thomas Stiitzle．Ant Colony Optimization[J]．IEEE Computational Intelligence Magazine,2006(8):30～35．

[7] Sharon Rosenberg and Kathleen A Meade．A practical guide to Adopting the universal verification Methodology(UVM) [M]．Cadence Design Systems,2010．

[8] 馬良,朱剛,寧愛兵．蟻群優(yōu)化算法[M]．北京:科學(xué)出版社,2008．2

[9] 丁明躍,鄭昌文,周成平等．無人飛行器航跡規(guī)劃[M]．北京:電子工業(yè)出版社,2009．1

[10] Hart,Nilsson,Raphael,A Formal Basis for the Heuristic Determination of Minimum Cost Paths．IEEE Transactions on Systems Science and Cybernetics SSC4 4(2):100-107．

[11] Nils J．Nilsson．人工智能[M]．北京:機械工業(yè)出版社, 2000．9

Trajectory Planning of UAV in Plateaus,Mountainous Environment

Huang Shujie

(Zhangzhou Geomatic Institution,Zhangzhou 363000,China)

The trajectory of UAV must be planned when UAV is about to shooting the punctate,linear,planar multiple targets in the undulating environment such as plateau and mountainous terrain．Overall trajectory planning is divided into two phases:global planning stages,namely to plan global shortest route for multiple targets;local planning stages,re -planning the route between the destination points which do not meet the requirements in order to avoid the terrain threat,and ultimately get the best route trajectory．Ant colony algorithm and A?algorithm were used in global planning and local planning．The results of the simulation show the effectiveness and efficiency of the trajectory planning method．

UAV trajectory;segmented planning;ant colony algorithm;A?algorithm

1672-8262(2016)01-53-06

P237

A

?2015—10—20

黃書捷(1990—),男,碩士,助理工程師,主要從事GPS/INS組合導(dǎo)航研究。