無人機航跡規劃算法綜述

成都飛機工業集團有限責任公司 彭閃 殷苑 田峰 馮張偉 姚森

航跡規劃作為任務規劃的核心，在任務規劃中起著決定性作用。本文首先介紹了無人機航跡規劃的國內外研究現狀，再介紹了幾種常見的航跡規劃算法，最后表述了航跡規劃中的一些難點與問題，并對航跡規劃的發展進行了總結。

近幾十年來，無人駕駛飛機在戰爭中已得到廣泛應用，由于其機上無人操作的特點，直接減少了人員傷亡，缺少飛行員可以減輕體重，降低成本，并為新的作戰范例提供機會。將使無人機能夠在最少或沒有人為干預的情況下執行任務，這樣的軍事和民用任務可能包括情報搜集、目標跟蹤和救援任務[1]。

1 國內外研究現狀

近年來，國內外涌現了大量關于航跡規劃的算法。各式各樣的算法優缺點各異，所適用的場景也不盡相同。Al等人[2]提出了一種以較低的計算復雜度提供動態路徑發現的啟發式算法。2003年，Nikolos等人[3]設計出一種用于無人駕駛飛行器(UAV)自主導航的離線/在線路徑規劃器。解決了在已知環境中使用離線規劃器的無人機導航問題。Sahingoz等人[4]采用遺傳算法(GA)，提出了一種多無人機系統的可飛行路徑規劃。2006年，Foo等人[5]提出了一種粒子群優化(PSO)算法來規劃三維路徑。通過使用PSO算法規劃出避開障礙物和威脅區的可行路徑。魏等人[6]在2016年研究了一種基于高度層引導因子的改進蟻群算法。2013年，劉等人[7]提出了一種改進后的稀疏A*算法，通過降維將三維航跡規劃將至二維航跡規劃，降低了計算復雜度與規劃時間。2014年，王等人[8]研究了一種基于三維約束的人工勢場法，用于實時航跡規劃。2016年，丁等人[9]提出了一種改進后的人工勢場法，該方法簡單易于實現，且具有較好的適應性。

2 航跡規劃算法

近年來，國內外學者研究了許多航路規劃的算法，主要可分為三類：確定性算法、隨機性算法、最優化算法。

2.1 確定性算法

確定性算法，大致理解是指當前節點的下一節點或下一序列是確定的。下面將介紹幾種典型的確定性算法。

2.1.1 Voronoi圖

Voronoi圖是根據戰場上的場景信息，將威脅區域的中心區域用一個圓點代替，再構建相鄰威脅區之間的連線的垂直中位線，使得該垂直中位線上的每一點，與該相鄰威脅點的作用距離一致，或者根據戰場環境和任務需求調整權重，均衡了各區域的威脅。每一條垂直平分線共同構成了一個由若干多邊形組成的網格，以此將航路規劃轉換成最小路徑求解。如圖1所示。其中灰色圈表示威脅區中心位置，多邊形的任一條邊為相鄰威脅點的垂直中位線。

圖1 Voronoi圖Fig.1 Voronoi diagram

Voronoi圖通常應用于劃分復雜場景的區域，通過Voronoi圖劃分后，復雜區域被分成了很多個子區域。而多邊形的每一條邊則為可行路徑，但可行路徑不一定是最優路徑，因此還需要采取其他搜索算法進行尋優，最終得出最優或次優航跡。Voronoi圖的一大特征是直觀，通過劃分區域，可以將躲避威脅轉變為求解最短路徑問題，Voronoi圖一般適合用在二維航路規劃中。

2.1.2 A?算法

A*算法的主要思想是：設定合適的啟發函數，選取一個當前節點，搜索其下一節點，計算其所有下一節點的代價值，并將所有下一節點的代價值進行比較，選取代價值最小的點，將其標記為擴展節點，作為潛在最優航跡節點之一，以此不斷遞推，直到計算到最終的目標節點。從起始點到目標點做標記的擴展點，即可構成由A*算法搜索出的最優路徑。

在A*算法中，通常會設定一個OPEN表和一個CLOSE表。其中，OPEN表用來表示已經計算出代價值但還未標記為擴展節點的點集合，不包括已擴展的點。如圖2所示，若當前節點為A點，則A點的下一節點有B點、C點和D點，計算出A點到B點的代價值為3，A點到C點的代價值為4，A點到D點的代價值為2，因此將B點、C點和D點放入OPEN表中，即OPEN=[B,C,D]。比較其大小，得出A點到D點的代價值最小，因此將D點放入CLOSE表，即CLOSE=[D]，同時將D點從OPEN表中刪除，更新后的OPEN=[B,C]。以此類推，按A*算法計算出的CLOSE表中所存儲的節點為CLOSE=[A,D,E,F,H,K]，即構成由該算法搜索出的最優航跡。

圖2 路線示意圖Fig.2 Schematic diagram of the route

A*算法的搜索過程用數學模型表示，代價估計值表示為：

f(n)=h(n)+g(n)

其中，f(n)表示從起始點經過節點n到目標點的代價估計函數，g(n)表示起始點到當前節點n的實際代價函數，h(n)是啟發函數，也是從當前節點n到目標點的代價估計函數。通常情況下，啟發函數h(n)決定了是否能找到最優路徑，因此啟發函數的選取尤為重要。

A*算法其實是一種擴展節點不斷擴大的搜索過程，算法簡單，計算量小，具有較快的規劃計算速度。并且A*算法收斂程度更好，時間復雜度更小，應用范圍更廣，全局性好，計算效率高，內存需求少，適合解決靜態的規劃問題。

2.1.3 人工勢場法

人工勢場法采用虛擬模仿的方法，將戰場上的敵方威脅區及各種禁飛區、避飛區、障礙物等視為無人機飛行的阻力，將該阻力假設成戰場空間中，無人機飛行前進中的所受到的排斥力，阻礙無人機飛行。而無人機的目標終點被視為對無人機產生吸引力，于是將無人機在復雜環境下的航路規劃過程看作由吸引力和排斥力組成的合力的作用過程。

人工勢場法具有安全性高、算法計算簡單易實現的優點，其規劃時間短、速度快、實時性好。若斥力的合力大于或等于目標的吸引力，將導致無法規劃出最優或次優路徑，容易陷入局部最優。人工勢場法一般適用于協同規劃和局部靜態航跡規劃。

2.2 隨機性算法

隨機性算法，大致理解是當前節點的下一節點或下一序列通常是隨機出現的，該類算法的不確定性增強。下面將介紹幾種典型的隨機性算法。

2.2.1 遺傳算法

在航跡規劃中，首先建立代價函數，再通過代價函數計算出每一節點的數值，并將其作為下一代節點選取的依據，不斷進化迭代，最終規劃出最優航跡。通常情況下，遺傳算法的穩定性很強，能實現在全局范圍內尋找最優解，時間復雜度更小，不容易陷入局部極值，找到全局最優解的概率很大。適用于三維全局航跡規劃和靜態航跡規劃[10]。

2.2.2 蟻群算法

蟻群算法的思想是：由于蟻群在覓食的時候，會產生某種能傳遞信息的物質。因此螞蟻在經過的路段中，都會存在這種物質，在找到食物的最短路徑上存在的該種物質會越積越多，含量越來越高，進而使得該條路徑上的螞蟻不斷增加，最終所有的螞蟻都選擇這條路徑，逐漸收斂。

在航路規劃中，滿足約束條件下，信息素濃度相當于航跡代價，航跡代價越小的路徑，會被無人機優先選擇，并將代價反饋。蟻群算法具有很好的穩定性與通用性，易于并行實現，也適合和其他算法共同規劃路徑，其收斂程度更好，時間復雜度更小，范圍更廣泛，適用于離線狀態下的全局航跡規劃。

2.2.3 粒子群算法

粒子群優化算法基本思想為：(1)已知當前粒子的位置與速度矢量，包括大小和方向；(2)已知當前節點的歷史最優速度矢量，包括歷史最優速度大小與方向，即節點自身的極值；(3)已知在全部節點中的全局歷史最優速度矢量，即全部節點的極值。根據這三個已知量，不斷進化最后達到一個收斂的狀態，直到搜索出全局最優解。以此更新后的位置點距離真實目標點有一定的偏差，通過不斷進化更新，逐漸收斂于真實值。

粒子群算法具有易于實現、快速收斂的優點，可變參數少，其算法魯性較強，原理簡單，搜索能力全面。

2.3 數學規劃

動態規劃。動態規劃算法一種求解決策過程最優的算法。它將一個問題分解成多個子問題，每一個子問題之間不是相互獨立的，上一個子問題的解會影響對下一個子問題的求解，但是下一個子問題的解不會改變前面上一個子問題的解。在航跡規劃中，選取恰當的代價函數，從最后一個節點往前推，找到其表示形式，直到到達起始節點。如圖3所示。

圖3 動態規劃算法Fig.3 Dynamic programming algorithm

其中，每一條路徑的數字代表該路徑的代價數，到K點的代價f(K)表示為:

f(K)=min[f(D)+4,f(E)+3]

f(D)=min[f(B)+2,f(A)+4,f(C)+4]f(E)= min[f(D)+2,f(B)+1]

到每一個節點地代價為該節點的前一節點的代價加上兩節點之間的代價，動態規劃的思想是通過找到代價最小的節點，從目標點倒推，最終規劃出一條選取代價最小的路徑，并以此類推，直到規劃出最優航跡或次優航跡。動態規劃算法具有搜索效率高，耗費時間短的優點，并且其穩定可靠。

3 結語

在真實作戰中，作戰場景通常都是非常復雜的，當提前規劃好的路徑，在戰場上遇到緊急情況時，如突然增加的障礙物，緊急出現的威脅源，例如敵方的導彈等等，如何及時規避新的障礙物以及重新規劃接下來的航跡，是一個值得研究的問題。

在規劃航跡時需要考慮約束條件，如飛機性能限制、任務約束等。同時也需考慮性能指標，如按照規定時間到達、飛行時間最短、任務效能最高等。而各類算法則是針對各種約束與指標形成的規劃出最優航跡的方法，不同算法適用的場景不同，在實際選擇規劃方法時，應選擇相應的算法進行航跡規劃，以尋得最優航跡。