四旋翼無人飛行器的航跡規劃*

李 翊 王 朕 姜 鵬 楊智勇 康宇航

(1.海軍裝備部駐西安地區軍事代表局 西安 710054) (2.海軍航空工程學院 煙臺 264001)(3.海軍航空兵學院艦載機系 葫蘆島 125001)

四旋翼無人飛行器的航跡規劃*

李 翊1王 朕2姜 鵬3楊智勇2康宇航2

(1.海軍裝備部駐西安地區軍事代表局 西安 710054) (2.海軍航空工程學院 煙臺 264001)(3.海軍航空兵學院艦載機系 葫蘆島 125001)

針對已知的局部地圖,對現有的各種遺傳算法進行了修改,提出一種改進型的遺傳算法對四旋翼無人飛行器進行航跡規劃。傳統的遺傳算法收斂慢,且容易陷入局部最優解或者“早熟”現象。針對這些同題,論文對交叉概率與變異概率進行自適應調整,自適應函數也進行了動態標定。實驗結果表明該算法的可行性及可靠性。

四旋翼無人飛行器; 自適應函數; 交叉概率; 變異概率; 航跡規劃

Class Number TP242.6

1 引言

無人飛行器航跡規劃是在綜合考慮無人飛行器到達時間、燃料消耗、威脅以及飛行區域等因素的前提下,尋找從初始點到目標點,并且滿足某些特定指標最優的飛行航跡。航跡規劃方法主要有：柵格法、SAS搜索算法、動態幾何規劃算法、蟻群算法、魚群算法、人工勢場法和遺傳算法。其中遺傳算法全局尋優能力最強,本文選用遺傳算法來對四旋翼無人飛行器進行航跡規劃[1～5]。

2 遺傳算法

遺傳算法是借鑒生物界的進化規律(適者生存,優勝劣汰)演化而來的搜索算法。由美國密西根大學Holland教授的學生Bagley在1967年首次提出的。遺傳算法是一種隨機全局搜索算法。

圖1 遺傳算法的進化

圖1表示遺傳算法循環流程。在遺傳算法中,首先產生初始種群。通過適應度函數決定種群中個體的好壞,根據適應度函數計算出種群中每一個個體的適應值。適應值高的個體更可能被留下來,而適應值低的個體則很可能被淘汰。選擇中應盡可能地保證優秀的個體被選中。根據實際情況確定選擇機制,如輪盤賭選擇機制、均勻排序機制、隨機聯賽機制等[6]。

3 遺傳算法在航跡規劃中的應用

本文的研究背景是第六屆國際空中大賽,四旋翼無人飛行器已經從起飛點飛到一個包含若干小房間的大房間中(如圖2所示),建立起了局部的環境特征地圖,需要通過航跡規劃找出一條從航跡規劃起始點返回到起飛點的路徑。如果四旋翼無人飛行器在小房間中,則需要先飛出房間然后再進行航跡規劃;如果沒有,僅僅是在大房間的走廊中,則直接進行航跡規劃。本文采用一種改進型的遺傳算法對無人飛行器進行航跡規劃,該算法將動態標定遺傳算法、自適應遺傳算法和大變異遺傳算法結合在一起,設計思想如圖2。

圖2 國際空中機器人大賽比賽場地示意圖

3.1 四旋翼無人飛行器的編碼

遺傳算法的第一步就是確定染色體的編碼方式,它決定了四旋翼無人飛行器在航跡規劃的表現形式,航跡的編碼方式主要包括利用導航點位置來編碼、利用飛行距離編碼、利用飛行距離和航向角的編碼等,優秀的編碼方式能夠提高算法效率;反之也能降低算法效率。由于四旋翼無人飛行器創建的是特征地圖,且四旋翼無人飛行器每隔50ms給一次指令,結合這一特點可以對四旋翼無人飛行器采用導航點位置方位的編碼方式：將四旋翼無人飛行器從航跡規劃起始點到四旋翼無人飛行器的起飛點的所有航路作為種群的個體[11],其染色體結構如圖3所示。

圖3 染色體結構

xhi和yhi分別為四旋翼無人飛行器第i個航路點的橫坐標和縱坐標;φhi為四旋翼無人飛行器在第i個航路點的航向角;bhi為四旋翼無人飛行器的航跡點中的狀態變量,如果第i個航跡點可行,即滿足約束條件(如在地圖的可行范圍內),并且第i個航跡點到第i+1個航跡點的航跡是可行的,則bhi=1,否則bhi=0。

3.2 四旋翼無人飛行器的適應度函數

適應度函數的選取直接影響到算法的最優解及效率[12]。適應度函數越復雜,則遺傳算法就越復雜,這樣遺傳算法的效率就越低,所以適應度函數應該盡量簡潔。適應度函數的值始終大于零,這一值越大,表示種群中的個體性能越好。四旋翼無人飛行器定高飛行,并且沒有固定翼無人飛行器的最大爬升/俯沖角、最大轉向角等限制,其需要考慮的約束條件主要有最小航跡段長度、航跡距離約束等,具體約束如下：

最小航跡段長度：假設四旋翼無人飛行器的最小航跡段長度為lmin,則四旋翼第i段飛行的航跡段長度lhi必須滿足如下條件:

lhi≥lmin

(1)

航跡距離約束：假設四旋翼無人飛行器的航跡規劃起始點到其起飛點為的直線距離為ldis,則無人飛行器飛行的航跡總長度必須滿足如下條件:

(2)

航跡離最近障礙約束：假設四旋翼無人飛行器在航跡規劃中的安全距離為lsecurity,第i個航跡點(xhi,yhi)用激光測距儀測得的最小距離為dlimin,則

dlimin≥lsecurity

(3)

在航跡點數目限制：四旋翼無人飛行器從航跡規劃起始點到其起飛點所確定的航跡點數目應該有一個上限Nhj

∑i≤Nhj

(4)

在滿足上述條件后,本文采用了罰函數法作為適應度函數計算種群中個體的適應值。罰函數的公式如式(5)

(5)

(6)

航跡的優劣通過其適應度函數來評估,每一條航跡的適應值都是采用動態標定適應度函數的方法來計算的,如式(8)和式(9)。

(8)

(9)

3.3 航跡規劃中的遺傳操作

細個體選擇的好壞直接影響到航跡點的最優選擇。如果種群中的個體選擇得不好會使種群中相似度接近的個體增加而導致算法過早收斂而陷入局部最優解。選擇操作算子主要是決策采用何種方式將子代種群從父代種群選擇出來,本文主要采用輪盤賭的選擇原則[13]。

交叉在航跡規劃中表現為將航跡規劃中的兩條航跡按照某種規則進行組合而產生新的航跡,它是產生新的種群、新個體的主要手段,包括單點交叉與多點交叉、均勻交叉等。單點交叉僅僅是在航跡種群中的航跡個體上隨機的選出某一個航跡點作為交叉點,而多點交叉則是在航跡種群中的航跡個體上隨機的選出相同幾個位置上的航跡點作為多個交叉點,這樣可以產生更多不同的航跡,增加種群的多樣性。交叉算子的收斂性決定了整個航跡搜索的收斂性能,它對算法的全局搜索能力起著決定性的作用。

變異與交叉都屬于進化過程,不同的僅僅是變異只是單條航跡中的某一個或某幾個航跡點發生變化,而不需要兩條航跡,本文的變異操作僅僅是讓航跡中的一個點發生變化。變異主要對算法的局部搜索能力起著決定性的作用。變異算子一般包括六個算子,分別為擾動算子、插入算子、刪除算子、平滑算子、定向擾動算子、交換算子。

4 仿真驗證

運用Matlab構建走廊、小房間、障礙環境模型,走廊的兩面墻平行,房間分布于走廊兩側,由帶小圓圈的矩形方塊表示,障礙全部假定為正方形,由實心黑色正方形表示。如前所述,四旋翼無人飛行器需要先飛到房間門口在進行航跡規劃,四旋翼無人飛行器航跡規劃起始點為(25,40),終點為(0,0);分別將迭代次數設置為100和200求取四旋翼無人飛行器的最優航跡,可得仿真路線圖(圖4,圖5)。

圖4 最優航跡(100代)

圖5 最優航跡(200代)

當遺傳迭代次數為100代時,四旋翼無人飛行器完全找到最優的航跡,并且適應值也很快收斂了;而當遺傳迭代次數增加到200代時,四旋翼無人飛行器找到的最優航跡又要優于迭代次數為100代的航跡,兩個航跡的步數都為25步。

5 結語

本文在局部特征地圖的基礎上,采用改進型的遺傳算法對四旋翼無人飛行器的返程路線進行航跡規劃。首先介紹遺傳算法的基本原理及所要用到的一些遺傳算法,針對實際情況,提出了一種改進型的遺傳算法,該遺傳算法在航跡規劃時適應性比較強,在保證效率的基礎上,也避免了陷入局部最優解與“早熟”。

[1] 謝曉方,孫濤,歐陽中輝.反艦導彈航路規劃技術[M].北京:國防工業出版社,2010:1-10.

[2] 鄭昌文,嚴平,丁明躍.無人飛行器航跡規劃研究現狀與趨勢[J].宇航學報.2007:28(6):1441-1446.

[3] C. Zheng, M. Ding, C Zhou. Real-time route planning for unmanned air vehicle with an evolutionary algorithm[J]. International Journal of pattern Recognition and Artificial Intelligence,2003,17(1):63-81.

[4] C. Zheng, L. Li, F. Xu, et al. Evolutionary route planner for unmanned air vehicles[J]. IEEE Transactions on Robotics,2005,21(4):609-620.

[5] T. Asano, L. Guibas, J. Hershberger, et al. Visibility-polygon search and Euclidean shortest path[J]. In the Proceedings of 26th Symposium on Foundations of Computer Science, Berkeley, CA,1989:155-164.

[6] 丁明躍,鄭昌文,周成平,等.無人飛行器航跡規劃[M].北京:電子工業出版社,2009:42-60.

[7] 龔純,王正林.精通MATLA最優化計算[M].北京:電子工業出版社,2009:380-400.

[8] 金晶,蘇勇.一種改進的自適應遺傳算法[J].計算機工程與應用,2005,18:64-69.

[9] Godberg. D. Genetic Algorithms in Search Optimization and Machine Learning[M]. USA: Addison Wesley Publishing Company,1988:7-10,59-308

[10] 馬鈞水,劉貴忠,賈玉蘭.改進遺傳算法性能的大變異操作[J].控制理論與應用,1998,15(3):404-408.

[11] 郭穎輝,朱華勇.基于遺傳算法的飛行航路規劃[J].計算機仿真,2004,1(2):69-71.

[12] 劉勇,康立山,陳鎮屏.非線性并行算法—遺傳算法[M].北京:科學出版社,1995:86-102.

[13] 雷英杰,張善文,李續武,等.MATLAB遺傳算法工具箱及應用[M].西安:西安電子科技大學出版社,2005:56-80.

Path Planning of Quad-rotor

LI Yi1WANG Zhen2JIANG Peng3YANG Zhiyong2KANG Yuhang2

(1. Navy Military Representative Office of Equipment Department in Xi’an, Xi’an 710054) (2. Naval Aeronautical Engineering Institute, Yantai 264001)(3. Naval Aviation Academy, Huludao 125001)

Under the premise of local map known, a variety of existing genetic algorithm has been modified. This paper proposes an improved genetic algorithm to carry out four-rotor UAV route planning. Traditional genetic algorithm converges slowly and is easy to fall into local optimal solution or “premature” phenomenon. In this paper, crossover probability and mutation probability has been adjusted adaptively, adaptive dynamic calibration function is also carried out. The experimental results show the algorithm’s feasibility and reliability.

quad-rotor, adaptive function, crossover probability, mutation probability, path planning

2014年6月7日,

2014年7月28日

李翊,男,碩士,工程師,研究方向:自動控制。王朕,男,碩士,講師,研究方向:模式識別。姜鵬,男,碩士,副教授,研究方向:導航制導與控制。楊智勇,男,博士,講師,研究方向:自動控制,人機交互系統。康宇航,男,博士,研究方向:導航制導與控制。

TP242.6

10.3969/j.issn1672-9730.2014.12.015