智能優化算法在無人機航跡規劃應用研究

雷 蕾

(海軍裝備研究院 北京 100073)

智能優化算法在無人機航跡規劃應用研究

雷 蕾

(海軍裝備研究院 北京 100073)

智能優化算法具備計算效率高,適應性強的特點,通過對智能優化算法在無人機航跡規劃的研究,分析無人機航跡規劃模型,提出無人機航跡規劃的約束條件,闡述了目前國內外應用和研究的幾種航跡規劃算法,并對無人機航跡規劃算法的發展趨勢進行了展望。

無人機; 航跡規劃; 智能優化算法

Class Number TP391

1 引言

隨著計算機、通信技術、自動化的發展,無人飛行器的種類更加豐富,具有協調性強、技術密集、系統復雜的特點,因此對無人飛行器航跡規劃工作人員提出了愈來愈高的要求。同時,隨著現代無人飛行器航跡規劃難度、危險度以及要求的不斷增加,通過操作人員手工操作成功完成復雜的飛行任務越來越困難。面對這種情況,無人機航跡規劃技術成為一種有效的解決途徑。

由于無人機面臨的戰場環境將是異常復雜遼闊,規劃約束條件眾多,模糊性大,各因素之間存在強耦合及其自身獨特的控制和任務方式,航跡規劃在處理這些因素時面臨極大的挑戰。許多學者已對航跡規劃方法問題作了大量工作,就此作了不同程度的敘述。采用分層規劃方法進行航跡規劃,根據規劃層次不同,可以將航跡規劃算法分成兩大類:任務級航跡規劃和戰術級航跡規劃。任務級航跡規劃可以采用較粗糙的數字地圖和簡化的性能模型,其目的是獲得參考航跡,從而減少戰術級航跡規劃的搜索空間,任務級航跡艦劃包括網絡法、符號規劃方法、試探法和知識推理法等方法。戰術級航跡規劃實質是個軌跡優化問題,可以運用最優控制理論求解戰術級突防航跡問題,采用動態規劃算法或A*算法得到優化航跡。另外,模擬退火算法和遺傳算法也在航跡規劃問題中得到廣泛應用,而蟻群算法是這幾年發展起來的一種新方法。對于規劃無人機航跡的問題,需要協調許多約束條件,在理論上還沒有一種通用的航跡規劃算法。因此,在不同條件約束下,尋找航跡規劃時間更短,尋優更好的航跡規劃算法具有重要的現實意義。

2 無人機航跡規劃問題分析

無人機在執行任務時,會受到如禁飛區、障礙物、險惡地形等復雜地理環境的限制,因此在航跡規劃時,應盡量避開這些區域,可將這些區域在地圖上標識為禁飛區域,以提升無人機工作效率。此外,飛行區域內的氣象因素也將影響任務效率,應充分考慮大風、雨雪等復雜氣象下的氣象預測與應對機制。因此,無人機航跡規劃技術需要考慮約束條件、飛行環境、突防安全等基本因素。

1) 飛行器的物理限制。在航跡規劃過程中必須考慮無人機自身性能限制,否則無人機可能不能按照規劃航跡飛行,無人機的自身性能對航跡規劃的約束主要有:最大偏轉角,它限制在生成擴展航跡時無人機水平面的偏轉角度,生成的新航跡段偏轉角只能小于或等于無人機限定的最大角度;最大俯仰角,它限制在生成擴展航跡時無人機在垂直平面上仰或俯沖的最大角度;最小航跡段長度,它用于限制無人機在改變飛行姿態之前飛出的最短距離;最低飛行高度,雖然飛行高度越低,被敵方發現的概率越低,但飛行越低無人機觸底的概率也會增加,所以需要對最低高度進行限制。

2) 航跡距離約束。它限制規劃的無人機航跡的長度必須不大于一個預先設置的最大飛行距離。最大飛行距離對應無人機所載燃料。

3) 實時性要求。實時性要求主要針對在線航跡規劃,由于飛行現場環境復雜多變,不可能規劃出滿足突發狀況的航跡,這樣就要求無人機具有實時規劃能力。實際的地形和敵情信息與事先獲得的信息總會有出入,一般認為這種差異的影響不大,可以通過保留一定的安全裕度來解決。對于無人機,航跡規劃往往由地面規劃員在起飛前做好,存儲在機載計算機內。無人機起飛之后,就按預定的航跡飛行。從長遠來看,無人機需要具有自主控制的能力,有部分的人工智能,因而往往還需要根據戰場實際情況進行實時航跡規劃,這是由未來無人機所執行的任務復雜性決定的。在這種情況下,無人機需要利用機載傳感器及我方的偵察通信系統實時探測敵方防御區域的各種信息,通過實時航跡規劃來消除規劃軌跡的偏差。由于機載傳感器的探測距離有限,實時航跡規劃往往只能局部修正規劃航跡。

航跡規劃的另一難點是進行自適應航跡規劃。自適應航跡規劃是提高飛行器生存能力的重要方法。自適應航跡規劃包括無人機在飛向目標途中接受和分析近實時的威脅數據,以致能改變預先規劃的航跡,達到減少受機動威脅攻擊的目的。自適應航跡規劃甚至可以改變飛行器的任務內容,使得作戰任務更具靈活性。飛行器自適應航跡修改需要得到實時信息,這種實時信息應該具有某種標準格式和協議。航跡規劃算法中也應具備一定的標準模式,以便快速響應所輸入的信息。整個自適應航跡規劃程序應有一定的智能,目前這方面的研究還處于起步階段。

3 無人機航跡規劃方法研究

由于無人機所處的戰場環境異常復雜遼闊,規劃約束條件眾多,各因素之間又存在強耦合,再加上無人機自身獨特的控制方式,航跡規劃在處理這些因素時面臨極大挑戰。航跡規劃問題是一個NP問題,具有約束條件多、復雜性強、時效性要求高、規劃范圍大、直接求解比較困難的特點,近年來國內外學者已提出了許多不同的規劃方法。

其中,采用智能優化算法求解無人機航跡規劃問題一般分為兩類,一類是確定型搜索算法,如:基于極小值原理的確定性計算方法和基于動態規劃或A*算法的確定性狀態空間搜索方法;一類是不確定型搜索算法,如以隨機搜索為特征的模擬退火算法、遺傳算法和蟻群算法等優化算法,由于這些算法模擬了自然界的物質變化以及生物活動和進化的過程,具有一定的優點和特點,因而在航跡規劃應用中得到了越來越多的重視。特別是遺傳算法由于不受搜索空間限制性假設約束,不要求優化函數具備連續、可導等假設,并隱含并行性,對于航跡規劃這種含有大量模糊信息、可以適應威脅環境的變化,多約束的優化問題來說,具有特別重要的意義。

3.1 A*算法

基于A*算法的航跡規劃是目前國內外應用較多的規劃算法,屬于一種經典啟發式搜索算法,被許多學者應用于無人機二維航跡規劃中。

A*算法基本思想:通過設定啟發函數來評估搜索到的擴展航跡點代價值,通過比較選擇代價值最優的航跡點,直到到達目標航跡點后完成航跡規劃。基于A*算法的無人機航跡規劃從起始航跡點出發,通過不斷尋找最小代價值的下一個擴展航跡點,從而產生一組航跡點集,完成整個航跡規劃過程。A*算法的核心實際就是下一航跡點擴展的過程,通過這一特點,可以找到代價值最優的飛行航跡。在確定最優飛行航跡后,需要計算該航跡是否滿足航跡規劃時對燃油、航程、速度或時間等條件的約束。如果不能滿足航跡規劃約束條件,規劃航跡失敗,必須重新規劃并對參數適當的修改。

基于A*算法航跡規劃過程中建立open表和close表,其中open表用于記錄可行當時沒有被采用的次優航跡點,close表用于存放已擴展的代價值最小的航跡點。在航跡點擴展過程中,也從open表中找出代價值最小的航跡點,進行擴展并進行分析,根據分析結果修改open表和close表,選擇最合適的航跡點。

基于A*搜索算法的航跡規劃計算簡單、易實現,理論上可以實現全局最優解收斂,同時也大大提高了搜索效率。但隨著搜索空間的擴展,A*搜索算法的航跡規劃計算量也呈指數形式增長,收斂時間變長,尤其在三維航跡規劃中常常出現組合爆炸問題,同時航跡規劃效果對啟發函數有太強依賴性,得出的最優航跡只是在該啟發函數下的最優,較好的啟發函數是通過試湊方法得出的,在遇到未知障礙物陷阱時可能會導致搜索失敗。基于以上A*搜索算法航跡規劃特點一般用于二維空間的全局航跡規劃。

3.2 Voronoi圖法

Voronoi圖作為計算幾何中非常重要的幾何圖形之一,被廣泛應用許多領域中,具有簡單直觀的優點。尤其在解決要求無人機離障礙物、威脅源的距離越遠越好的問題,Voronoi圖方法具有很大的優勢。

Voronoi圖法基本思想:首先根據無人機飛行環境威脅源和障礙物的分布情況,以威脅源和障礙物的中心點為基礎構建出Voronoi圖的威脅模型;其次基于Voronoi圖計算出加權無向圖,并采用最短路徑搜索算法如Dijkstra算法搜索初始最短路徑。Voronoi圖法主要缺點在于存在不可行的尖角,主要是通過三次樣條插值法或B樣條法優化路徑,把路徑中尖角剔除生成可行的最優軌跡。

最優軌跡的精度取決于構建Voronoi圖的精度,當威脅源或障礙物位置發生變化時,需要再次構建Voronoi圖并重新計算。Voronoi圖法可用于二維航跡規劃任務。

3.3 遺傳算法

遺傳算法(Genetic Algorithm，GA)是在20世紀70年代初期被Holland等提出的,它是將生物自然選擇與基因遺傳學機理與計算機結合起來的一種隨機搜索算法。

遺傳算法基本原理:按照某種編碼方式對個體編碼,采用選擇、交叉和變異三種遺傳因子模擬自然界中生物族群遺傳變異的現象,以適應度值作為迭代過程中選取父代繁殖、交叉、變異的評價依據,不斷向好的方向發展,最終產生最優個體解決問題。

遺傳算法具有不易陷入局部最優解,魯棒性好,不受搜索空間限制,不受假設約束,不要求優化函數具備特殊特性以及隱含并行性等特點。

3.4 粒子群算法

粒子群算法(Particle Swarm Optimization，PSO)是由美國心理學家Eberhart博士、電子信息工程師Kennedy博士提出的一種模仿鳥群捕食行為的算法,是一個群體智能模型。

粒子群算法基本原理:首先,隨機初始化粒子,之后在粒子迭代時,通過跟蹤兩個最優值不斷的進化自身找到最優解,兩個最優值一個是粒子本身找到的最優解,另一種是全局粒子的最優解。該算法類似遺傳算法,也是一種采用迭代的方法不斷優化的算法。

粒子群算法的優點在于簡單容易實現、通用性較強、搜索能力全面,缺點在于容易陷入局部最優解、對參數的要求比較高。

3.5 蟻群算法

蟻群算法(Ant Colony Algorithm，ACA)是1991年由意大利學者M. Dorigo等提出的一種新興的啟發式搜索算法。該算法也是一種模擬算法,源于對自然界螞蟻覓食時最短路徑行為的研究。

蟻群算法基本原理:首先網格圖中信息素矩陣初始化,螞蟻根據狀態轉移規則,形成一條從起始點到目標點的可行航跡,計算各螞蟻航跡的目標函數得出最優航跡,然后根據目標函數和一定的信息素調整規則對網格圖中各點的信息素進行調整,經過數次迭代產生全局最優航跡。

蟻群算法是一種很好的通用型算法,具有很好的魯棒性和全局并行計算能力,缺點在于搜索時間長,收斂后期易陷入局部最優。

4 方法分析

本文綜合考慮國內外學者研究航跡規劃算法經驗的基礎上,針對兩種類型算法特點,對不同算法的分析如下:

1) 不確定型搜索算法是有方向性的自適應搜索,在適應度函數的驅使下,通過各種引導信息,如遺傳算法的交叉、變異,粒子群算法的速度和位置更新等手段,每次信息引導過程中的操作產生新個體,從而不斷擴大搜索范圍,不斷向目標方向逐步優化,最終達到近似最優解。因此,算法搜索范圍廣,易找到全局最優解。不確定型搜索算法具有不受搜索空間限制,不受假設約束,不要求優化函數具備特殊特性以及隱含并行性等特點,因此,遺傳算法通用性和魯棒性強。

2) 相比確定型搜索算法,不確定型搜索算法在具有這些優秀能力的同時也存在一些問題,如影響尋優效率的初始種群質量問題等。

因此,對無人機航跡規劃問題可采用兩種算法結合的方式進行改進,例如通過A*結合遺傳算法,在遺傳算法的基礎上,采用稀疏A*算法搜索新航跡點的方法,產生初始種群進而提高航跡規劃尋優性能。稀疏A*算法由于計算比較簡單、易實現,通過結合約束條件隨機選取航跡點的方式縮小了搜索空間,提高了搜索效率,減少搜索時間。同時,由于稀疏A*算法僅需要為遺傳算法提供初始種群,不需要得到最優航跡,所以大大降低了稀疏A*算法對啟發函數的依賴性,提高了算法的性能。

5 結語

無人機航跡規劃有多種算法,既有適于小范圍的規劃算法,可在無人機上進行動態修改;又有適于大范圍的規劃算法,可在已知信息下求得全局最優解;既能進行人為的智能規劃,又能在一定范圍內進行模型的自動求解。應在具體問題具體分析基礎上,發展高效的無人機航跡規劃方法。

隨著無人機所要執行的任務越來越復雜,加上環境的不確定性,對航跡規劃的要求也將越來越高。未知威脅信息環境下的實時航跡規劃將是未來研究的重點,高效的全局搜索方法和局部搜索方法混合使用將是無人機航跡規劃的一種趨勢。

[1] Zhonghua Hu, Min Zhao, Min Yao. Cooperative attack path planning for unmanned air vehicles Swarm based On grid model and bi-level programming[J]. Journal of Information & Compumdonal Science,2011,8(4):671-679.

[2] J. F. Gilmore. Autonomous vehicle planning analysis methodology[C]//The Proceeding of American Control Conference, Kluwer. Boston, MA,1991.

[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] S. A. Bortoff. Path planning for UAVs[C]//the Proceedings of the American Control Conference, Chicago, USA,2000:364-368.

[5] 雷興明,邢昌風,吳玲,等.基于分布式約束優化的多平臺導彈協同航路規劃[J].電子學報,2012,40(10):2068-2072.

[6] 張同法,于雷,魯藝.多架無人機協同作戰的路徑規劃[J].火力與指揮控制,2009,34(2):143-145.

[7] 馬培蓓,紀軍.3種多導彈航跡規劃算法的比較[J].電光與控制,2010,17(10):28-32.

[8] 張同法,于雷,魯藝.多架無人機協同作戰的路徑規劃[J].火力與指揮控制,2009,34(2):143-145.

[9] W Zhang, Z Xing, G Wang, et al. Distributed stochastic search and distributed breakout: properties, comparison and applications to constrains optimization problems in sensor networks[J]. Artificial Intelligence,2005,161(1-2):55-87.

[10] 胡中華,趙敏.無人機任務規劃系統研究及發展[J].航天電子對抗,2009,25(4):49-52.

Application of Intelligent Optimization Algorithm in UAV Path Planning

LEI Lei

(Navy Equipment Research Institute, Beijing 100073)

Intelligent optimization algorithm has the characteristics of high computational efficiency and abaptability. By analyzing the intelligent optimization algorithm in the UAV route planning, the UAV route planning model is researched. And the restrictions of UAV trajectory planning are proposed. This paper describes several trajectory planning algorithms applied and researched at home and abroad. And the development trend of UAV flight path planning algorithms is prospected.

UAV, route planning, intelligent optimization algorithm

2016年8月13日,

2016年9月29日

雷蕾,女,碩士研究生,工程師，研究方向:軟件工程。

TP391

10.3969/j.issn.1672-9730.2017.02.009