一、 歷史背景

無人機最早在20世紀20年代出現(xiàn)，當時是作為訓練用的靶機使用的，是一個許多國家用于描述最新一代無人駕駛飛機的術語。1945年，第二次世界大戰(zhàn)之后將多余或者是退役的飛機改裝成為特殊研究或者是靶機，成為近代無人機使用趨勢的先河。隨著電子技術的進步，無人機在擔任偵查任務的角色上開始展露他的彈性與重要性。隨著研究的深入，無人機開始逐步扮演各種空戰(zhàn)角色，如：無人偵察機可以繞過敵方的雷達威脅區(qū)而獲得重要的軍事情報。1982年以色列航空工業(yè)公司(IAI)首創(chuàng)以無人機擔任其他角色的軍事任務。以色列國防軍主要用無人機進行偵察，情報收集，跟蹤和通訊。20世紀90年代后，西方國家充分認識到無人機在戰(zhàn)爭中的作用，競相把高新技術應用到無人機的研制與發(fā)展上。

早期的無人機都是按照地面任務規(guī)劃中心預先計算并設定好的航路飛行，因此一旦在既定航路段出現(xiàn)新的威脅，無人機將束手無策，無人機航路規(guī)劃無疑成為無人機導航任務中最重要的任務之一。

二、 研究意義

無人機航路規(guī)劃是指在特定約束條件下,尋找從起始點到目標點并滿足無人機性能指標的最優(yōu)或可行的航路。其問題本質(zhì)是多約束條件下，多目標函數(shù)求極值的優(yōu)化問題。規(guī)劃出滿足任務要求、導航、安全性等約束的較優(yōu)航路，對提高無人機的武器系統(tǒng)性能有重要意義。通過對無人機航路規(guī)劃的研究，對無人機航路規(guī)劃問題進行了概括和總結(jié)，闡述了無人機航路規(guī)劃的框架結(jié)構(gòu)以及靜態(tài)全局規(guī)劃和動態(tài)局部規(guī)劃方法的研究現(xiàn)狀。分析了近年來常用的幾種規(guī)劃算法，在此基礎上，對今后的研究方向進行了展望。

無人機航路規(guī)劃主要包括環(huán)境信息、飛行約束、航路目標以及航路規(guī)劃器4部分。

根據(jù)不同的任務環(huán)境，按照環(huán)境模型是否實時更新，即無人機飛行環(huán)境是否確定,航路規(guī)劃可分為靜態(tài)全局航路規(guī)劃和實時的局部航路規(guī)劃。靜態(tài)全局航路規(guī)劃根據(jù)無人機飛行環(huán)境的確定信息，在無人機離線狀態(tài)下進行規(guī)劃設計，然后把預先規(guī)劃好的最優(yōu)路徑裝載在無人機上，無人機自動駕駛沿預定航線飛行。這一過程一般在無人機起飛前完成,實時性要求不高,因而可以采用的規(guī)劃算法比較寬。實時局部航路規(guī)劃通過傳感器對環(huán)境變化的反饋更新后，在相應時間內(nèi)對航路進行規(guī)劃設計，這種規(guī)劃實時性要求高，是提高無人機的生存概率的一種最有效的手段。按照實時性要求，可分為強實時規(guī)劃算法和弱實時規(guī)劃算法。

近年來，無人機實時航路規(guī)劃技術的研究在國內(nèi)明顯加強，但距實時規(guī)劃要求還有較大的差距。

三、 無人機航路規(guī)劃建模

3.1 圖形環(huán)境模型

基于圖形的航路規(guī)劃方法中,首先根據(jù)一定的規(guī)則將飛行環(huán)境表示成由一系列飛行航路組成的網(wǎng)絡圖，然后根據(jù)特定的評價函數(shù)對網(wǎng)絡圖進行航路搜索，最后得到連接起始點和目標點的“最優(yōu)”航路。構(gòu)造可飛航路的方法有多種,其中典型的方法有切線圖法、Voronoi圖法和PRM(Probabilistic RoadmapPlanner)法。切線圖法是用威脅的切線表示可飛航路，構(gòu)造出的可飛航路圖是最短航路圖。這種方法構(gòu)造出來的航路幾乎接近威脅，其缺點是在無人機飛行過程中出現(xiàn)位置偏差就很易被敵方發(fā)現(xiàn)。Voronoi圖則是根據(jù)地面威脅的分布情況依次做出相鄰兩威脅的中垂線，垂線可以根據(jù)威脅等級適當?shù)南虻偷燃壨{靠近，從而形成圍繞各威脅的多邊形，多邊形的邊就是所有可飛的航路，其寬度可以適當選取從而形成所謂的安全走廊。然后通過搜索算法，得到“最優(yōu)”的飛行航路。當威脅分布均勻時這種方法顯得非常有效。PRM(Probabilistic Roadmap Planner)法的優(yōu)點是可以針對不同的環(huán)境特征采用不同的采樣方式，在航路質(zhì)量和構(gòu)造時間上可以權衡，構(gòu)造的時間越長得到最優(yōu)的航路的可能性越大。當飛行環(huán)境變化時，PRM方法需要重新對環(huán)境進行采樣分析，實時性不強，一般不用于實時的局部航路規(guī)劃。在實時航路規(guī)劃時，這幾種方法都需要重新構(gòu)造航路圖。

3.2 柵格環(huán)境模型

柵格法將無人機的飛行環(huán)境分為一系列具有二值信息的大小相同或不同的單元格，其中的一些單元格為不可飛單元，其他的為可飛單元。每個柵格的信息可以用結(jié)構(gòu)體類型定義。這一方法的關鍵在于柵格大小的選取，柵格大小直接影響信息的存儲量的大小和規(guī)劃時間的長短。柵格大,信息存儲量減小，規(guī)劃時間短，但是航路質(zhì)量下降。柵格小，信息存儲量大，規(guī)劃時間長，航路質(zhì)量高。針對這一問題，往往對威脅密集的環(huán)境進行單元格細分，而對稀疏環(huán)境單元格大小適當放大。柵格法的實現(xiàn)簡單，當環(huán)境更新時能夠做出快速的對局部柵格信息進行更新以滿足實時規(guī)劃要求，近來被廣泛采用。

3.3 威脅模型

航路規(guī)劃中的關鍵問題在于地形信息和威脅源信息的獲取與處理，這些信息的獲取及處理的準確度直接決定了航路規(guī)劃的質(zhì)量。這類信息一般通過衛(wèi)星遙感技術和其他情報手段獲得。由于航路規(guī)劃大部分工作由計算機自動完成，對于地形信息，需要建立數(shù)字地形數(shù)據(jù)庫，即電子地圖的形式來表示地形。航路規(guī)劃系統(tǒng)必須對地形特征做出分析，根據(jù)地形數(shù)據(jù)來確定無人機的可飛區(qū)及飛行高度。同時需要從威脅源信息中分析出敵方防御系統(tǒng)的雷達探測區(qū)、火力殺傷范圍和相應的地形遮蔽區(qū)，并將其填入地形數(shù)據(jù)庫中。威脅模型分為地形威脅模型、雷達威脅模型以及大氣威脅模型。

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

航路規(guī)劃算法可以分為傳統(tǒng)經(jīng)典算法和現(xiàn)代智能算法兩大類。其中，前者主要包括動態(tài)規(guī)劃法、導數(shù)相關法、最優(yōu)控制法;后者主要包括啟發(fā)式尋優(yōu)搜索、遺傳算法、人工神經(jīng)網(wǎng)絡、群體智能(主要包括蟻群算法、粒子群算法、蜂群算法)等。上述這些方法所要解決的問題都是大范圍航路規(guī)劃過程中巨大的信息存儲量和全局最優(yōu)之間的矛盾,現(xiàn)在這方面仍然還有許多工作要做。

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

動態(tài)規(guī)劃是分階段決策過程的最優(yōu)化的一種數(shù)學方法。使用這種方法的無人機航路規(guī)劃要求構(gòu)造的航路圖分為各級的連接,并最終歸結(jié)于目標點。每一級的航路代價由特定的評價函數(shù)給出，然后按照分階段決策規(guī)則尋找最優(yōu)的航路。這種方法在無人機高空作業(yè)并且威脅單一的情況下得到了良好的效果。

4.2 啟發(fā)式算法

啟發(fā)式方法是指通過尋求一種能產(chǎn)生可行解的啟發(fā)式規(guī)則，找到問題的一個最優(yōu)解或近似最優(yōu)解。該方法求解問題的效率較高，但是對每一個所求的問題必須找到特有的啟發(fā)式規(guī)則，啟發(fā)式規(guī)則沒有通用性。這一方法的典型有A*法，以及各種改進A*算法。A*算法是利用問題擁有的啟發(fā)信息來引導搜索，達到減少搜索范圍，降低問題復雜度的目的。

無人機航路規(guī)劃問題應用中，啟發(fā)式項采用當前節(jié)點于目標節(jié)點的歐式距離能夠得到較好的效果。啟發(fā)式項在滿足小于實際的耗費值的前提,越接近實際耗費值越能提高搜索效率。傳統(tǒng)的A*算法存在搜索速度慢和耗內(nèi)存空間大的缺陷。曾佳等人通過結(jié)合無人機的飛行約束,將前項搜索點限制在一定的范圍，提出了基于五叉樹的A*搜索算法。Szczerba等人為了加快搜索過程和節(jié)省內(nèi)存空間，通過分區(qū)搜索并結(jié)合飛行約束削減搜索節(jié)點，提出了稀疏A*算法。Bander為提高A*算法的搜索速度，引入了經(jīng)驗知識和人工干預，提出了自適應A*算法。S.Al-Hasan等采用柵格的形式構(gòu)造飛行環(huán)境，采用A*算法進行搜索，評價函數(shù)由威脅、距離、機動能力的加權和以及啟發(fā)式項構(gòu)成。并且評價函數(shù)中使用了人工智能的模糊技術，針對環(huán)境的變化可以調(diào)整權系數(shù)，對動態(tài)環(huán)境有較高的適應性。

4.3 遺傳算法

遺傳算法是模仿自然界生物進化機制發(fā)展起來的隨機全局搜索和優(yōu)化方法，可用于復雜系統(tǒng)優(yōu)化的具有魯棒性的搜索算法。強調(diào)利用概率轉(zhuǎn)換規(guī)則來引導搜索過程。遺傳算法通過染色體的復制、交叉、變異得到新的個體，并對個體性能進行評估，從而得到最優(yōu)的符合要求的個體。但是由于無人機航路規(guī)劃存在時間上和計算機資源的約束，遺傳算法會出現(xiàn)早熟現(xiàn)象，得不到全局的最優(yōu)解。JurisVagners等通過采用多種群并發(fā)計算,通過競爭機制優(yōu)選的思想來解決遺傳算法的早熟現(xiàn)象。遺傳算法的關鍵在于對群體的編碼，Michalewicz經(jīng)過大量的實驗表明使用浮點數(shù)編碼比二進制編碼在CPU計算時間上更加有效。初始群體的選取應具有多樣性，使得規(guī)劃空間的每一個體都有機會參與進化。Changwen Zheng等用導航點的坐標信息以及一位校驗位對航路進行實值編碼，結(jié)合航路的約束條件以及評價函數(shù)對航路群體進行分析,然后采用自設定的幾種遺傳算子對群體進行操作，得到了較好的結(jié)果。蟻群算法則是一種由于受自然界生物的行為啟發(fā)而產(chǎn)生的“自然”算法，通過跟蹤螞蟻的生物信息激素來決定后續(xù)行為的算法,根據(jù)信息素的強弱決定航路的優(yōu)劣。此方法關鍵在于信息素的調(diào)整。

4.4 元胞螞蟻算法

蟻群算法是受自然界中真實蟻群的集體覓食行為的啟發(fā)而發(fā)展起來的一種基于群體的模擬進化算法，屬于隨機搜索算法。蟻群算法是最新發(fā)展的一種模擬昆蟲王國中螞蟻群體智能行為的仿生優(yōu)化算法，該算法利用生物信息素作為螞蟻選擇后續(xù)行為的依據(jù)，并通過螞蟻的協(xié)同來完成尋優(yōu)過程。蟻群算法具有較強的魯棒性、優(yōu)良的分布式計算機制、易于與其他方法相結(jié)合等優(yōu)點。

五、 未來與展望

無人機的任務規(guī)劃系統(tǒng)給無人機制定飛行計劃,分配飛行任務。對使用無人機完成預定任務計劃具有十分重要的作用。而任務規(guī)劃系統(tǒng)中最重要的一部分就是航路規(guī)劃。任務規(guī)劃系統(tǒng)制定無人機的任務，航路規(guī)劃系統(tǒng)引導無人機如何選擇合適的航路去完成任務。因此航路規(guī)劃的研究對于提高無人機的執(zhí)行任務的效率有重要的意義。

隨著無人機所要執(zhí)行任務越來越復雜，環(huán)境的不確定性，對航路規(guī)劃的要求也將越來越高。不確定環(huán)境下的實時航路規(guī)劃將是未來的研究重點，首要解決弱實時的航路規(guī)劃，其次要解決戰(zhàn)術級的強實時的航路規(guī)劃問題。當一種方法無法滿足航路規(guī)劃要求時，高效的全局搜索方法和局部搜索方法的混合使用將是一種趨勢。