警用無人機路徑規劃技術研究

劉碩 陳毅雨

武警工程大學裝備工程學院，陜西西安，710086

警用無人機路徑規劃技術研究

劉碩 陳毅雨

武警工程大學裝備工程學院，陜西西安，710086

針對無人機在武警部隊的使用情況，為解決無人機路徑規劃問題，搭建無人機路徑規劃的求解框架，分析了無人機性能約束及戰場威脅約束，探討了無人機路徑幾何建模方法；并介紹了在無人機路徑規劃中用到的幾種路徑規劃算法（其中包括傳統經典算法和現代智能算法）。最后，闡述了無人機路徑規劃面臨的重要問題及發展方向。

無人機；武警部隊；路徑規劃；規劃算法

1 引言

作為維護國家安全的一支重要武裝力量，為了更好的完成使命任務，武警部隊不斷加快其信息化發展的步伐。無人機為超低空或近距離偵察、監視和打擊提供了平臺，是超低地面環境中的有力偵查手段，因而在武警部隊執行任務中扮演越來越重要的角色。但是先前的無人機都是根據地面任務要求，按照預先計算設定好的軌跡飛行。無人機實時路徑規劃是無人機集群配合、集群戰術再規劃、集群戰術目標再制定等自主飛行的技術基礎，是提高無人機的生存概率的一種最有效的方法。

2 無人機路徑規劃

路徑規劃是根據任務目標規劃滿足約束條件的飛行軌跡，是自主系統中不可分割的一個整體部分，它負責從一個地方運動到另一個地方的路徑問題。路徑規劃的目的是根據預設數字地圖，通過GPS/INS組合導航系統，在適當時間內計算出最優或最短的飛行軌跡。考慮到數字地圖誤差及隨機環境的影響（如障礙物等），要求無人機在飛行過程中具有動態修正軌跡的能力，能回避犯罪分子威脅到的環境，安全地完成預定任務。無人機航跡規劃主要包括環境信息（如障礙物、犯罪分子打擊威脅區、地形因素）、無人機系統約束、路徑規劃器、無人機自動駕駛儀等。其中無人機系統有兩個回路，內回路是自動駕駛儀回路；外回路是制導系統回路。制導系統提供側向加速度指令以保持無人機跟蹤路徑，而自動駕駛儀控制無人機的升降舵、副翼和方向舵實現所需要的側向加速度。

路徑規劃的目標和方法按照無人機應用于武警部隊領域的不同而不同，這些應用包括：監視、搜索與跟蹤、營救任務和災難監控等。主要方法可用圖1所示的簡化框圖表示。

圖1 現有路徑規劃算法

3 無人機系統性能約束及戰場威脅約束

3.1 無人機系統性能約束

無人機因有其自身的機動性能和物理限制，在對無人機路徑進行規劃時有許多約束。路徑規劃中約束條件主要有以下幾個方面：

（1）最小路徑段長度：飛行器的機動性能決定無人機在變換下一個飛行姿態前，必須飛行的一段最短的直線距離，我們把這個最短的距離稱為最小路徑段長度。

（2）最大拐彎角：在水平方向無人機可以拐彎的最大角度。路徑規劃時設定的路徑必須在不大于最大拐彎角范圍內拐彎，路徑規劃時必須保證生成的路徑是在允許的拐彎角范圍之內變化。則設無人機最大轉彎角度：航跡點或，每一航段向量，則最大轉彎角約束可寫成：

（3）最大爬升/俯沖角：在垂直方向上無人機允許爬升和俯沖的最大角度；無人機的機動性能約束決定了其在垂直方向上不能以任意角度上升或下降，而是需要在最大爬升或俯沖角允許的范圍內變化的。

（4）最大航程：無人機飛行的航跡的最大長度。無人機由于自身體積的限制，且所攜帶的燃料也是有限的，所以無人機要安全地返回就必須在燃料允許的情況下飛行，其飛行的最大長度便有了一個約束。

3.2 戰斗威脅場約束

無人機在飛行過程中要考慮威脅源（包括自然地理障礙、惡劣復雜氣候、犯罪分子占據地等）的空間位置、可威脅半徑等。假設犯罪分子位置坐標，可威脅半徑，則區域

（1）威脅場分區。

（2）可行路線識別及網絡建立。

（3）威脅場包絡識別及綜合網絡建立。

4 無人機路徑幾何建模

4.1 基于柵格的幾何建模

柵格，也稱網格。是將二維平面按照一定的標準進行分解的產物。按照單元格的大小和形狀是否相同，網格可以分為均勻網格和非均勻網格。均勻網格中以正多邊形網格最為常見，包括正三角形網格、正方形網格和正六邊形網格；非均勻網格中以對均勻網格局部單元遞歸分解得到的遞階網格最為多見；正方形網格由于意義明確、描述方便而最為常用；正六邊形網格具有良好的平面幾何性質。

4.2 基于圖形的環境表示

對于二維平面內的無人機路徑規劃問題，根據圖的來源不同，可將路徑規劃中用到的圖劃分為三類：

（1）可視圖和切線圖

可視圖法，在穿越的環境中能產生由視線連接的路徑，這個路徑是由直線段連接的無方向圖構成的圖形網絡生成。該方法中，只考慮多邊形障礙物。在圖G=（V，E）中，V表示障礙物的頂點，邊線E表示不與障礙物相交的連接所有頂點的直線段，因此頂點僅包含那些相互間可視的點。如果障礙物也用圓或扇形表示，那么可視圖就演變成切線圖。因此威脅的切線可表示可飛航跡,構造出的可飛路徑圖是最短路徑圖。圖3中S為起點，D為目標點，圖3（a）和圖3（b）分別表示不同威脅情況下的切線圖。

圖3 不同威脅情況下的切線圖

（2）VORONOI圖

VORONOI圖是由若干個圍繞障礙物的共邊多邊形產生的連接圖。將VORONOI圖運用于無人機路徑規劃當中一般分為兩個步驟，第一個步驟是先生成初始的航路，將已經探明的需要避開的一些構成威脅的區域構造VORONOI圖，根據VORONOI圖的性質，VORONOI多邊形的每條邊上的點到相對應的兩個點等距離。也就是說，VORONOI邊上的點是到威脅點的最遠點，所以VORONOI圖的邊界即為無人機的所有可供飛行的航路，將這些邊界設定權重值后即可利用搜索算法來求得最優的路徑規劃，這樣就完成了初步的路徑規劃。圖4為生成VORONOI圖的示例，其中圖4（a）是經過戰場態勢分析評估犯罪分子位置后生成的威脅分布圖，圖4（b）是用平面掃描算法生成上述威脅分布的帶邊界的VORONOI圖模型。

圖4 生成VORONOI圖前后對比示意圖

（3）概率路標圖(PRM)

概率法是隨機選取相鄰點使其滿足一定的優化準則，如最短距離，此時概率法稱為概率路圖法。在二維平面或三維空間內隨機采樣得到可行路標點，連接彼此可見的相鄰路標點得到自由路徑，路標點和自由路徑即構成概率路標圖。

5 無人機路徑規劃算法

路徑規劃算法可以分為傳統經典算法和現代智能算法兩大類。

傳統經典算法主要是動態規劃法，它是求解多步決策問題的一種有效方法，它通過把一個多步決策問題轉化為多個一步優化問題并逐個求解從而降低復雜決策問題求解的難度。該算法應用于無人機路徑規劃中，要求模型相對簡單，不要求威脅場連續性，可以獲得全局最優解，但缺陷是動態規劃在用于求解復雜優化問題時可能引起維數災害，這限制了它的應用范圍。

現代智能算法主要有A*算法和遺傳算法。A*算法是在無人機航跡規劃中運用最為經典的方法之一，該算法屬于一種啟發式搜索算法，啟發式搜索有利于減少搜索路徑，大大提高了搜索效率。遺傳算法是一種通過模擬自然進化過程，運用于復雜系統搜索最優解的算法，遺傳算法屬于優化算法。

6 結語

隨著無人機在武警部隊承擔的任務越來越復雜，其飛行環境的不確定性，對路徑規劃的要求也將越來越高。未來無人機在算法方面的發展方向及研究重點主要有：（1）不確定環境下的實時路徑規劃。對多傳感信息運用不確定性理論進行綜合處理，真正實現在無人干預的情況下，根據探測結果自動修改路徑；（2）戰術級的強實時的路徑規劃問題；（3）多任務目標（如低空突防、目標搜索營救、信息偵察等任務）綜合的規劃算法；（4）多機協同規劃算法；（5）針對地形、敵情信息處理方法的研究算法。

[1]鄭昌文,嚴平,丁明躍.飛行器航跡規劃研究現狀與趨勢[J].宇航學報,2007.28(6):1441-1446.

[2]徐翔,梁瑞仕,楊會志.基于改進遺傳算法的智能體路徑規劃仿真[J].計算機仿真,2014.31(6):357-361.

[3]Roberge V，Tarbouchi M，Labonte G. Comparison of parallel genetic algorithm and particle swarm optimization for real-time UAV path planning[J].IEEE Transactions on Industrial Informatics,2013，9(1):132-141.

[4]周青,李廣文.基于A*算法的無人機四維航跡規劃研究[J].計算機仿真,2014.31(4):92-96.

[5]葛艷,稅薇,韓玉.基于貝葉斯網絡和蟻群算法的航路優化[J].計算機工程,2009.35(12):175-177.

[6]J Yang,Y Zhuang. An improved ant colony optimization algorithm for solving a complex combinatorial optimization problem[J].Applied soft computing,2010,10(2):653-660.

[7]Sun H L,Yue L Y,Yao S Y. Study on selection of emergency rescue based on GIS[J].Advanced Materials Research，2014,864:2804-2807.

[8]王俊,周樹道,朱國濤.無人機航跡規劃常用算法[J].火力與指揮控制,2012.37(8):5-8.

[9]任波,于雷,韓李勛.自適應蟻群算法的無人機航跡規劃方法[J].電光與控制,2007.14(6):36-39.

[10]馮軍紅,陳明強.基于自適應蟻群算法的救援直升機航跡規劃[J].計算機仿真,2015.32(5):55-57.

劉碩/1992年生/男/遼寧沈陽人/碩士/研究方向為裝備科研與實驗

陳毅雨/1992年生/男/廣東湛江人/碩士/研究方向為裝備建設與發展