一、 歷史背景

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

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

二、 研究意義

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

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

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

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

三、 無人機航路規劃建模

3.1 圖形環境模型

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

3.2 柵格環境模型

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

3.3 威脅模型

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

四、 無人機航路規劃算法

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

4.1 動態規劃算法

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

4.2 啟發式算法

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

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

4.3 遺傳算法

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

4.4 元胞螞蟻算法

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

五、 未來與展望

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

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