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

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

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

1 國內外研究現(xiàn)狀

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

2 航跡規(guī)劃算法

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

2.1 確定性算法

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

2.1.1 Voronoi圖

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

圖1 Voronoi圖Fig.1 Voronoi diagram

Voronoi圖通常應用于劃分復雜場景的區(qū)域，通過Voronoi圖劃分后，復雜區(qū)域被分成了很多個子區(qū)域。而多邊形的每一條邊則為可行路徑，但可行路徑不一定是最優(yōu)路徑，因此還需要采取其他搜索算法進行尋優(yōu)，最終得出最優(yōu)或次優(yōu)航跡。Voronoi圖的一大特征是直觀，通過劃分區(qū)域，可以將躲避威脅轉變?yōu)榍蠼庾疃搪窂絾栴}，Voronoi圖一般適合用在二維航路規(guī)劃中。

2.1.2 A?算法

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

在A*算法中，通常會設定一個OPEN表和一個CLOSE表。其中，OPEN表用來表示已經計算出代價值但還未標記為擴展節(jié)點的點集合，不包括已擴展的點。如圖2所示，若當前節(jié)點為A點，則A點的下一節(jié)點有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表中所存儲的節(jié)點為CLOSE=[A,D,E,F,H,K]，即構成由該算法搜索出的最優(yōu)航跡。

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

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

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

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

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

2.1.3 人工勢場法

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

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

2.2 隨機性算法

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

2.2.1 遺傳算法

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

2.2.2 蟻群算法

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

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

2.2.3 粒子群算法

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

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

2.3 數(shù)學規(guī)劃

動態(tài)規(guī)劃。動態(tài)規(guī)劃算法一種求解決策過程最優(yōu)的算法。它將一個問題分解成多個子問題，每一個子問題之間不是相互獨立的，上一個子問題的解會影響對下一個子問題的求解，但是下一個子問題的解不會改變前面上一個子問題的解。在航跡規(guī)劃中，選取恰當?shù)拇鷥r函數(shù)，從最后一個節(jié)點往前推，找到其表示形式，直到到達起始節(jié)點。如圖3所示。

圖3 動態(tài)規(guī)劃算法Fig.3 Dynamic programming algorithm

其中，每一條路徑的數(shù)字代表該路徑的代價數(shù)，到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]

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

3 結語

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

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