0 引言

    隨著無人機技術的不斷完善，無人機的應用越來越廣泛。如何使無人機在規劃的某片區域中尋找出一條從起始點到目標點既安全又滿足相應約束條件且所花費代價最小的航跡一直是研究的熱點^[1]。標準解決航跡規劃問題的順序是按照預先選定好的航跡代價函數，通過一定的搜索算法，選出總的代價函數值最小的路線作為規劃出的航跡^[2-3]。

    在路徑規劃中，常用的搜索算法有A*算法、動態規劃法、Dijkstra算法、遺傳算法等。在這些算法中，由于A*算法計算簡單，算法實現容易且在理論上能夠保證規劃出的路徑全局最優，因此得到廣泛應用^[3]。但是把A*算法應用在航跡規劃中搜索空間將急劇增加，由此導致收斂時間變長，所需內存空間增加。針對這個問題，本文提出把無人機的機動限制結合到搜索空間中從而縮小搜索空間，同時對A*算法中的open表的管理進行改進，以提高收斂時間，縮小內存使用量。

1 改進A*算法實現航跡規劃

    航跡規劃的本質是在規劃的區域內，在給定的約束條件下尋找一條從起點到目標點的最優或次優的飛行航跡。傳統的規劃算法是基于預先確定的航跡代價函數生成一條具有最小代價的航跡^[4-5]。然而，在許多應用中，這樣得到的最小代價的航跡并不能滿足實際需求。在實際應用中，航跡規劃需考慮無人機的機動性能、碰撞概率、飛行時間等約束條件，同時由于無人機航跡規劃的地域廣闊，因此形成的搜索空間大。通常的搜索算法要獲得一條最優航跡需要很長的收斂時間和極大的內存空間，所以在實際應用中需對搜索算法進行相應的改進。由于A*算法計算速度快、實現容易且能達到全局最優的特點，因此選擇對A*算法進行改進，使其適用于無人機航跡規劃。

1.1 改進A*算法

    無人機由于受機動性能、最小飛行距離、航跡距離、飛行高度等的約束，通過A*規劃出來的航跡不一定能夠滿足無人機的實際飛行條件。在擴展節點時通常把相關的約束條件結合到搜索算法中，這樣既有效減少了搜索空間，也縮短了規劃所需的時間。無人機飛行時為達到最佳狀態一般需要滿足的約束條件有：最小飛行距離、最大拐彎角、最大爬升/下滑角、最長飛行距離、最低離地高度^[6]。

    假設給定了起始點和目標位置，一條從起始位置到當前節點的航跡，最小航跡段長度為L，最大拐彎角為φ，最大爬升/下滑角為θ，則從當前位置在最小飛行距離、最大拐彎角以及最大爬升/下滑角的約束條件下能夠到達的就只有有限的位置空間。如圖1所示，節點o處的縱向的張角為2θ₂，在水平面上的張角為2θ₁，扇面的半徑為最小飛行距離。

    圖1是未經離散化的可搜索空間示意圖。在離散規劃空間時，柵格的邊長長度為無人機的最小飛行距離。把規劃空間離散化后結合無人機的約束條件可縮小算法搜索空間。無人機飛行是有方向性的，在進行當前節點擴展時，飛行反方向的節點以及垂直于該飛行方向的鄰接節點都可以裁剪掉。這樣在水平方向上的最大拐彎角就可以限制在3個搜索空間中，垂直方向上的最大爬升/下滑角也同樣可以限制在3個搜索空間中，這樣把擴展當前節點的后繼節點的搜索空間縮小為9個。如圖2所示，B節點是當前新擴展節點，A點是B點的父親節點，C點為新擴展節點的鄰接計算節點。

    在三維空間中，每個柵格都是一個立方體，在水平剖面和豎直剖面上都要滿足最小步長、最大拐彎角和最大爬升/下滑角。但是在實際控制中，最大轉彎角和最大爬升/下滑角可以通過一定的關系轉換，轉化為其他直接控制的參數來滿足要求。下面就分別對水平面和豎直平面進行轉換。

1.1.1 水平面關系轉化

    假設無人機當前節點的坐標為(x，y，z)，新擴展的節點坐標為(x₁，y₁，z₁)，航跡偏角為θ，航跡傾斜角為β，轉彎半徑為R，最大側向過載為N_ymax，S₁、S₂分別為水平面上兩節點的擴展步長。三維航跡規劃是基于地球坐標系，水平方向是通過改變航向來躲避障礙物，因此在水平方向上的轉化關系如圖3所示。

    根據圖3的幾何關系可知新擴展的節點坐標為：

1.1.2 縱向關系轉化

    無人機的縱向機動性能主要受到最大爬升/下滑角的限制。在低空飛行時，可以通過對地形坡度的限制來達到對最大爬升角的限制。

    如圖4所示，假設當前節點的空間坐標為(x_i，y_i，z_i)，待擴展節點的空間坐標為(x_i+1，y_i+1，z_i+1)，兩節點之間的距離為l，其爬升角為β，則由幾何關系可知：

1.1.3 對open表結構進行改進

    由于在進行節點擴展尋找最優航跡時頻繁地對open表中的節點執行插入、刪除、排序操作，同時open表中的節點數目也相對較多，每次執行插入、刪除操作后都需要對open表進行排序。順序存儲結構執行插入、刪除、排序操作均較費時。執行插入、刪除操作的時間復雜度是O(n)，排序的時間復雜度為O(n²)。由于在搜索時從open表中刪除的是代價值最小的節點，而open表是按照節點代價值大小來組成的有序表，因此實際在執行刪除操作時的時間復雜度是O(1)，當有新節點插入時即需對open表進行排序以保證open表一直處于有序狀態。由此分析得出對open表的管理主要時間花銷是在節點排序上，為提高整體的運行效率，這里對open表的數據結構進行一定的改進，通過采用樹形的數據結構來管理open表。最小二叉堆是一種典型的樹形數據結構，通過最小二叉堆對節點進行排序的時間復雜度為O(n log₂ n)，通過此種數據結構可減少open表節點排序的時間花銷。

1.2 代價函數的建立

    軍用無人機航跡規劃的目標是在滿足無人機物理特性約束以及具體飛行任務約束的前提下生成超低空地形跟隨、地形回避以及威脅回避的飛行軌跡，以提高無人機的生存概率。其數學表達式為：

其中P_Ci為無人機在第i航跡的撞地概率；P_Di是無人機在第i段航跡被敵方雷達探測到的概率，P_Ki為無人機在第i段航跡被敵方雷達探測到并被擊毀的概率^[7]。由于這些概率和地區的地形、威脅的分布密度、發現威脅的能力等都存在著很大關系，同時這些概率和無人機的各項狀態（飛行高度、速度、油量等）之間的關系很難定義，即使找出他們之間關系，該公式也將十分復雜，勢必將增加代價函數的計算難度。由此需要對上述的代價函數進行優化。無人機在低空突防時飛行的高度越低，被敵人發現的幾率就越小，規劃出的航跡飛行時間越短，越能達到出其不意的效果，同時也提高了無人機的生存概率；若飛行時間過長，會增加累計威脅，同時也增加油量的消耗。基于上述原因再結合啟發式A*算法的表達式，把g(n)和h(n)分別簡化為如下形式：

    起始節點到當前節點的代價函數值：

    上述代價函數表達式中L_i表示從起始點到當前節點飛行過的路程，F_max表示無人機油箱中的總的油量，H_min、H_max分別表示無人機為防止撞地的最小飛行高度和為防止被敵人雷達探測到的最高飛行高度，T_f表示無人機能接受威脅的最大門限值。啟發函數中L_n表示當前節點到目標節點的距離，h_n表示目標節點的高程值，λ₁、λ₂、λ₃、μ₁、μ₂為表達式中各項的加權系數。設定不同的加權系數，獲得的航跡也有所不同：如果增大高度值的系數λ₁，則規劃出來的平均航跡高度就會越低，增大威脅值的系數值λ₂，則規劃出來的航跡將遠離威脅，同理增大航跡長度系數值λ₃，這樣規劃出來的航跡長度將減少。通過對這些權重系數的不同組合，可以得到所期望的滿足條件的最優航跡。

1.3 算法實現

    通過結合無人機的自身限制以及任務要求，在三維航跡搜索過程中將大大縮小搜索空間，從而規劃出滿足條件的航跡。A*算法的實現主要是維護兩個表：open表以及closed表。在三維空間中算法實現的具體實現步驟如下：

    (1)把地理威脅等環境信息初始化到規劃空間中。

    (2)把起始點添加到open表中，同時把closed表置空。

    (3)判斷open表是否為空，若為空則算法結束；反之，則找出open表中代價值最小的節點作為當前節點，同時把該節點從open表中刪除，放入closed表中。

    (4)判斷當前節點是否為目標節點，若當前節點到目標節點的距離小于最小飛行距離，則將目標節點的父親節點當作當前節點，航跡搜索過程結束。

    (5)對當前節點進行擴展：

    ①根據約束條件產生當前節點待擴展區；

    ②對待擴展區中的每個節點，根據式(5)、(6)計算每個節點的航跡代價；

    ③如果待擴展區域中的某個節點已經在closed表中且其代價估值小于closed表中的估價值，則更新closed表中的估價值，同時把該節點移出closed表，放入open表中；如若不在closed表中，則判斷該節點是否在open表中，如果不在則把該節點插入到open表中；

    ④如果該節點在open表中且open表中的g(n)值都大于當前計算的g(n)值，則更新open表中節點g(n)的值，更新后需保證open表仍然有序。

    (6)接著繼續跳轉到步驟(3)執行上述操作直至找到目標節點。

    由于在節點擴展時，每個被擴展的節點都會記錄其父節點，當算法找到目標節點后則算法結束。接著通過從目標節點向前回溯直到起始位置，這樣就得到了從起始點到目標點的最小代價航跡。

2 仿真結果    

    對上述改進后的算法在Intel Core i5、3.1 GHz的PC上進行驗證試驗，運行環境是Windows7操作系統。規劃的空域大小為60 km×60 km，假設起始節點的坐標為(0，0，0)，目標節點的坐標為(60，60，0)，最低離地間隙為100 m，最大轉彎角為45°，最大爬升/下滑角為30°。實驗通過用基本A*算法和改進后的A*算法分別設置二組不同的λ₁、λ₂、λ₃、u₁，u₂值來規劃最優航跡并對算法改進前后的性能進行比較分析。仿真圖5的λ₁、λ₂、λ₃、μ₁、μ₂分別為λ₁=0.1，λ₂=0.3，λ₃=0.6，μ₁=0.45，μ₂=0.55，由于λ₃所占權重較大，所以規劃出來的航跡總的路程較小。仿真圖6的λ₁，λ₂，λ₃，μ₁，μ₂分別為λ₁=0.4，λ₂=0.5，λ₃=0.1，μ₁=0.45，μ₂=0.55，由于λ₁、λ₂所占權重較大，所以規劃出的航跡飛行高度較低，安全性較高。

    兩種參數的飛行高度分別如圖7、圖8所示。通過對比可知，第一組數據的平均飛行高度要高于第二組，這就印證了參數λ₁的大小影響無人機的平均飛行高度，飛行高度越低也間接提高了無人機的安全性，飛行高度越低，越難被敵人雷達發現。

    基本A*算法與改進后的A*算法性能比較如表1所示。通過各項數據對比可以看出，改進后的算法規劃時間較改進前的少很多，并且總的航跡路程也縮減了不少，這樣能夠在最快的時間內規劃出滿足需求的最優航跡。通過改變參數λ₁、λ₂、λ₃的權重比例可以規劃出更側重于飛行高度、安全性以及飛行距離的航跡。

3 結束語

    本文通過把無人機的各項機動性能限制、飛行路程以及飛行高度等約束條件相結合的方式來縮小節點擴展時的搜索空間，同時對節點水平方向和縱向方向的空間劃分，使規劃出的航跡節點包含了無人機在該節點的各項狀態。在三維空間中，經過限制后滿足要求的節點已很少，大大提高了搜索效率，對open表結構的改進減少了open表中節點排序的時間。同時對評價代價函數進行優化，使算法能夠更快地收斂到最優解。

參考文獻

[1] 董文洪，易波，栗飛.無人機航路規劃環境模型研究[J].計算機工程與應用，2012，48(15)：236-239.

[2] 高暉，陳欣，夏云程.無人機航路規劃研究[J].南京航空航天大學學報，2001，33(2)：135-138.

[3] 宋建梅，李侃.基于A*算法的遠程導彈三維航跡規劃算法[J].北京理工大學學報，2007，27(7)：613-617.

[4] 趙鋒，楊偉，楊朝旭，等.無人機三維航路動態規劃及導引控制研究[J].計算機工程與應用，2014，50(2)：58-64.

[5] 李季，孫秀霞.基于改進A-Star算法的無人機航跡規劃算法研究[J].兵工學報，2008，29(7)：789-792.

[6] 杜萍，楊春.行器航跡規劃算法綜述[J].飛行力學，2005，23(2)：10-14.

[7] 辛貴州.無人飛行器航跡規劃算法研究[D].哈爾濱：哈爾濱工程大學，2010.