無人機在高原山地環境下航攝軌跡的規劃

黃書捷

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

無人機在高原山地環境下航攝軌跡的規劃

黃書捷?

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

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

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

1　引 言

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

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

2　主要威脅源及限制條件

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

2．1地形限制

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

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

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

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

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

通過疊加融合,模擬了真實的地形地物,再現了山峰威脅模型,用此模型作為航線規劃環境,簡化了航線規劃的復雜程度。

2．2大氣威脅

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

2．3無人機約束條件

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

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

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

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

3　航跡規劃

3．1地圖數據表示方法

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

3．2全局航跡規劃

3．2．1TSP問題

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

3．2．2蟻群算法原理

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

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

以TSP問題為例,螞蟻系統具體包括了以下三個方面的內容。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(8)若迭代次數達到NC_max則輸出最優解,退出算法,否則返回(2)繼續執行[8]。

3．3局部航跡規劃

3．3．1A?算法原理

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

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

3．3．2算法流程

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

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

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

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

(3)循環:

①如果OPEN列表為空,則退出循環,搜索失敗。

②如果目標點被加入CLOSED列表,說明目標點找到,則退出循環,搜索成功。

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

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

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

4　仿真實驗

4．1 航跡規劃環境模型

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

山峰威脅模型參數設置　表1

圖1　環境模型

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

圖2　航線規劃區域

文中分別采用蟻群算法和A?算法,matlab2013a中進行全局和局部規劃仿真實驗。

4．3仿真實驗

4．3．1全局規劃仿真實驗

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

蟻群算法參數設置　表2

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

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

4．3．2局部航線重規劃

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

圖5　A?算法所得最優航線

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

圖6　點1與點9之間最優航線

4．3．3全局規劃航線與局部規劃航線合成

將全局規劃的最短航線與局部規劃的最優航線進行合成,得到了最終的無人機規劃航線,兩階段的航線設計用時為8．4 s,如圖7所示。

圖7　合成的最終航線

4．3．4結果分析

航跡規劃所得的結果表明:

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

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

5　結 語

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

[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] 鄭家良．無人機航跡規劃與導航的方法研究及實現[D]．成都:電子科技大學,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] 戴定川,盛懷潔,邊曉利．無人機航跡規劃分段需求分析[J]．戰術導彈技術,2011(6):63～69．

[5] 陳海,王新民,焦裕松等．一種凸多邊形區域的無人機覆蓋航跡規劃算法[J]．航空學報,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] 馬良,朱剛,寧愛兵．蟻群優化算法[M]．北京:科學出版社,2008．2

[9] 丁明躍,鄭昌文,周成平等．無人飛行器航跡規劃[M]．北京:電子工業出版社,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]．北京:機械工業出版社, 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組合導航研究。