無人機(jī)航路規(guī)劃研究

刁德權(quán)

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

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

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

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

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

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

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

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

2.2 無人機(jī)物理限制

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

2.3 飛行任務(wù)要求

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

2.4 實(shí)時(shí)性要求

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

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

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

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

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

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

3.2 啟發(fā)式算法

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

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

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

3.3 遺傳算法

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

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

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

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

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

[參考文獻(xiàn)]

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