刁德權

摘 要：通過對無人機航路規(guī)劃的研究，對無人機航路規(guī)劃問題進行了概括和總結，介紹了無人機航路規(guī)劃流程，分析了無人機航路規(guī)劃的約束條件，闡述了目前國內(nèi)外應用和研究的幾種航路規(guī)劃算法，并對無人機航路規(guī)劃算法的發(fā)展趨勢進行了展望。

關鍵詞：無人機；航路規(guī)劃；動態(tài)規(guī)劃算法；啟發(fā)式算法；遺傳算法

1 無人機航路規(guī)劃問題的描述

無人機航路規(guī)劃是依據(jù)地形信息和執(zhí)行任務環(huán)境條件信息，綜合考慮無人機的性能、到達時間、耗能、威脅以及飛行區(qū)域等約束條件，為無人機規(guī)劃出一條或多條自出發(fā)點到目標點的最優(yōu)或可行的飛行航路，保證無人機高效、圓滿地完成飛行任務，并安全返回基地[1]。其本質(zhì)是多約束條件下最優(yōu)或可行解的求解問題。無人機航路規(guī)劃一般分兩步：首先是飛行前預規(guī)劃，即根據(jù)既定任務，結合環(huán)境限制與飛行約束條件，從整體上制定最優(yōu)參考路徑并裝訂特殊任務；其次是飛行過程中的重規(guī)劃，即根據(jù)飛行過程中遇到的突發(fā)狀況，如地形、氣象變化、未知限飛禁飛因素等，局部動態(tài)的調(diào)整飛行路徑或改變動作任務（如圖1所示）。

從框圖中可知，按照任務環(huán)境模型是否實時變化，即無人機飛行環(huán)境是否確定，航路規(guī)劃可分為已知威脅信息環(huán)境下航路規(guī)劃和未知威脅信息環(huán)境下航路規(guī)劃。已知威脅信息環(huán)境下航路規(guī)劃根據(jù)無人機飛行環(huán)境的確定信息，在無人機執(zhí)行任務之前就可以進行規(guī)劃設計，這一過程一般在無人機起飛前完成，實時性要求不高；未知威脅信息環(huán)境下航路規(guī)劃通過無人機對環(huán)境變化更新后，在飛行中對航路進行重規(guī)劃，實時性要求較高。

2 無人機航路規(guī)劃約束條件

2.1 飛行環(huán)境限制

無人機在執(zhí)行任務時，會受到如禁飛區(qū)、障礙物、險惡地形等復雜地理環(huán)境的限制，因此在航路規(guī)劃時，應盡量避開這些區(qū)域，可將這些區(qū)域在地圖上標識為禁飛區(qū)域，以提升無人機工作效率。此外，飛行區(qū)域內(nèi)的氣象因素也將影響任務效率，應充分考慮大風、雨雪等復雜氣象下的氣象預測與應對機制。

2.2 無人機物理限制

⑴最小轉(zhuǎn)彎半徑：由于無人機飛行轉(zhuǎn)彎形成的弧度將受到自身飛行性能限制，它限制無人機只能在特定的轉(zhuǎn)彎半徑范圍內(nèi)轉(zhuǎn)彎。⑵最大俯仰角：限制了航跡在垂直平面內(nèi)上升和下滑的最大角度。⑶最小航路段長度：無人機飛行航路由若干個航點與相鄰航點之間的航路段組成，在航路段飛行途中沿直線飛行，而到達某些航點時有可能根據(jù)任務的要求而改變飛行姿態(tài)，最小航路段長度是指限制無人機在開始改變飛行姿態(tài)前必須直飛的最短距離。⑷最低安全飛行高度：限制通過任務區(qū)域最低飛行高度，防止飛行高度過低而撞擊地面而墜毀。

2.3 飛行任務要求

無人機具體執(zhí)行的飛行任務主要包括到達時間和進入目標方向等，需滿足如下要求：⑴航路距離約束：限制航路長度不大于一個預先設定的最大距離。⑵固定的目標進入方向：確保無人機從特定角度接近目標。

2.4 實時性要求

當預先具備完整精確的環(huán)境信息時，可一次性規(guī)劃自起點到終點的最優(yōu)航路。而實際情況是難以保證獲得的環(huán)境信息不發(fā)生變換；另一方面，由于任務的不確定性，無人機常常需要臨時改變飛行任務。在環(huán)境信息變化區(qū)域不大的情況下，可通過局部更新的方法進行航路的在線重規(guī)劃；而當環(huán)境變化區(qū)域較大時，無人機航路規(guī)劃系統(tǒng)則必須具備在線重規(guī)劃功能。

3 無人機航路規(guī)劃算法

由于無人機所處的戰(zhàn)場環(huán)境異常復雜遼闊，規(guī)劃約束條件眾多，各因素之間又存在強耦合，再加上無人機自身獨特的控制方式，航路規(guī)劃在處理這些因素時面臨極大挑戰(zhàn)。Canny在1988年就已經(jīng)證明航路規(guī)劃是一個NP問題，對其直接求解往往導致組合爆炸。為了加速規(guī)劃進程，近年來國內(nèi)外學者已提出了許多不同的規(guī)劃方法。下面對已有的規(guī)劃方法加以概述。

3.1 動態(tài)規(guī)劃算法

動態(tài)規(guī)劃是分階段決策過程的最優(yōu)化方法。動態(tài)規(guī)劃法是對于存在多個空中封鎖和地面障礙等多約束的情況下，采用航路圖分類法進行航路規(guī)劃。無人機根據(jù)約束，在有限的探測和處理范圍內(nèi)，根據(jù)不同的滾轉(zhuǎn)角度，得到下一時刻無人機可能到達的位置，并在新的飛行點上，計算再下一時刻的位置。以此類推，得到一棵航路樹，比較樹枝終點的性能指標并找到代價最小的節(jié)點，反向搜索其父節(jié)點，得到最優(yōu)航路。

動態(tài)規(guī)劃法模型簡單，對地形要求不高，算法不依賴于威脅場的連續(xù)性，容易實現(xiàn)。但由于動態(tài)規(guī)劃算法具有維數(shù)爆炸特性，如果在大范圍內(nèi)進行動態(tài)搜索，計算機無法處理大量信息，因此動態(tài)規(guī)劃算法適于小范圍內(nèi)航路規(guī)劃，對于范圍較大的區(qū)域會出現(xiàn)組合爆炸。

3.2 啟發(fā)式算法

啟發(fā)式算法是指通過尋求一種能產(chǎn)生可行解的啟發(fā)式規(guī)劃，找到問題的一個最優(yōu)解或近似最優(yōu)解。啟發(fā)式算法比較典型的是啟發(fā)式A*搜索法，是利用問題擁有的啟發(fā)信息來引導搜索，以達到減少搜索范圍，降低問題復雜度的目的。啟發(fā)式搜索首先定義以下代價函數(shù)：f（M）=g（M）+h（M）

式中：g（M）為啟發(fā)式因子，表示從初始節(jié)點到當前節(jié)點M的真實代價；h（M）表示從當前節(jié)點M到目標節(jié)點的最小代價估計值；f（M）則表示從初始節(jié)點經(jīng)M到目標節(jié)點的最小代價路徑的估計值。搜索的原則是優(yōu)先擴展f（M）小的節(jié)點，最終搜索得到最優(yōu)航路（如圖2所示）。

啟發(fā)式算法由于提供了智能搜索，因此大幅度提高了搜索效率。用啟發(fā)式A*搜索法進行航路搜索時，由于需要綜合考慮各種因素，獲得一條最優(yōu)航路需要很長的收斂時間和極大的內(nèi)存空間，因此不適于實時求解。為此，Robert J.Szczerba等人提出了一種用于二維規(guī)劃的稀疏A*搜索算法。該算法結合航路約束有效地消減搜索空間，大大縮短了搜索時間，節(jié)省了內(nèi)存空間，較好地滿足了實時性要求。

3.3 遺傳算法

遺傳算法提供了一種求解復雜問題的通用框架，它仿效生物的遺傳和進化機制，借助復制、雜交、變異等操作，使所要解決的問題從初始解一步步逼近最優(yōu)解。其5個要素包括染色體編碼、初始群體、適應度函數(shù)、遺傳操作和控制參數(shù)。很多學者都將遺傳算法用于飛行器的航路規(guī)劃求解。

在角頻率組固定的情況下，使用幅值組構造一條染色體，其基因位置表示對應的角頻率，數(shù)值代表相應的幅值。應用該型染色體構造方法進行遺傳搜索得到的優(yōu)化航路（如圖3所示）。

遺傳算法計算速度快，得到的航路滿足無人機機動性能，無須再進行平滑處理，所得航路能夠嚴格經(jīng)過起始點和目標點，但是容易產(chǎn)生早熟現(xiàn)象，不能得到最優(yōu)解。Juris Vagners等人通過采用多種群并發(fā)計算，通過競爭機制優(yōu)選的思想來解決遺傳算法的早熟現(xiàn)象。Ioannis K.Nikolos等人采用更能符合實際的B樣條曲線來表示航路，對無人機全局和局部航路進行規(guī)劃，得到了較好的結果。

綜上，無人機航路規(guī)劃有多種算法，既有適于小范圍的規(guī)劃算法，可在無人機上進行動態(tài)修改；又有適于大范圍的規(guī)劃算法，可在已知信息下求得全局最優(yōu)解；既能進行人為的智能規(guī)劃，又能在一定范圍內(nèi)進行模型的自動求解。應在具體問題具體分析基礎上，發(fā)展高效的無人機航路規(guī)劃方法。

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

[參考文獻]

[1]J.F.Gilmore.Autonomous vehicle planning analysis methodology[J].In：The Proceeding of American Control Conference，Kluwer.Boston，MA，1991.

[2]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.

[3]S.A.Bortoff. Path planning for UAVs[A].the Proceedings of the American Control Conference，Chicago，USA，2000：364-368.