基于稀疏A*算法的無人機航路規劃方法

陳慧杰

（92419部隊,遼寧興城，125106）

基于稀疏A*算法的無人機航路規劃方法

陳慧杰

（92419部隊,遼寧興城，125106）

針對多約束條件下三維空間航路規劃問題，分析了三維規劃空間的劃分方法，綜合考慮航程代價、爬升代價和威脅代價等因素,針對航路規劃任務對各種指標的偏重程度，引入指標的權重系數，設計了代價函數，并編制了稀疏A*算法流程，對算法的有效性進行了仿真驗證。驗證結果表明：采用稀疏A*算法能夠有效地解決多約束條件下的三維空間航路規劃問題。

無人機；航路規劃；稀疏A*算法

0 引言

航路規劃涉及的約束條件眾多，主要包括飛行環境約束、無人機物理性能約束、飛行任務與戰術目標約束三種主要約束條件[1]。飛行環境約束主要包括地形威脅、雷達探測威脅、復雜氣象區威脅等；無人機物理性能約束主要包括最小航路段長度、最大偏航角、最大爬升/下滑角、最大航程約束等；飛行任務與戰術目標約束主要包括飛行高度限制、目標任務區進入方向、戰術目標約束等，而且這些約束條件往往相互耦合，航路規劃中需要根據任務的類型，合理的考慮和處理約束條件并建立威脅模型，以保證所規劃航路的安全性，提高無人機的生存能力；另外，航路規劃的空間范圍比較大，規劃中需要處理的信息量大，在三維空間中實現對航路的合理規劃更是增加了規劃難度，采用稀疏A*算法能夠有效解決三維空間下航路規劃問題[2]。

1 稀疏A＊算法及其特性

稀疏A*算法（Sparse A*Search，SAS）是由Robert J.Szczerba等提出了一種改進的A*算法。具有普通A*搜索算法一些性質：（1）只要存在到達目標的路徑，在規劃網格不是特別大的前提下，SAS算法保證終止于到達目標的一條最小代價路徑。（2）只要啟發式函數滿足容許條件，適當增大啟發式函數值，可以加速搜索進程。（3）只要啟發式函數滿足一致性條件，那么當它擴展到某一節點時，它已經找了從起始點到達該節點的一條最優路徑。（4）平均搜索時間短。將SAS應用到三維空間中去，在擴展節點時把最小航路段長度、最大拐彎角、最大爬升/俯沖角、航路距離約束、飛行高度限制、固定目標進入方向等航路約束條件結合到搜索算法中去[3-4]，能夠有效地減小搜索空間，縮短了搜索時間。

2 規劃空間的劃分

為了簡化空間劃分和空間搜索的難度，將三維規劃空間中每個網格取為一個小立方體。其中，水平剖面以滿足最小步長和最大拐彎角的限制為準則，取為正方形，最小步長為其邊長。當無人機從一個網格節點進入相鄰網格節點時，可在最大拐彎角的范圍內選擇下一個可行航向[5]。同理，在高度剖面考慮到最大爬升/俯沖角的限制，假設取為30°，可把網格的垂直剖面取為長方形，長方形的長是最小步長，寬為最小步長的1/4。當無人機從一個網格節點進入相鄰網格節點時，垂直方向的下一可行航向的范圍也至多包括3個相鄰網格，同樣，如果需要增加精度，可以進一步細化網格，增加擴展節點個數。網格的劃分與具體任務對精度的要求以及所提供的數字地形圖的精度有關，因此可以綜合考慮兩者的關系，對網格進行適當劃分。當無人機進入下一個網格時，只需考慮固定的網格，從而減少了搜索時間，進而減少整個規劃的時間和存儲空間。

3 代價函數設計

規劃航路中的撞地概率、被探測概率、被擊毀概率與無人機的狀態（如飛行高度、速度、地面跟蹤等）之間的關系比較難定義，因此，在規劃中可以簡化代價函數的計算公式，主要考慮航程代價、燃油代價、爬升代價、威脅代價等。

通過縮短航程可以減少無人機在敵方區域的飛行時間，一方面降低了無人機的危險系數，另一方面也可以減少油耗；通過適當的限制無人機爬升降低無人機的飛行高度，可以提高航路的隱蔽性；燃油代價指油耗情況，可以歸并到航程代價和爬升代價之中；威脅代價主要是指通過雷達探測威脅區域和敵方防空區域等，無人機盡量遠離威脅區域或通過威脅較小的區域。

式中的啟發函數可以表示為無人機在地圖當前點到目標點之間的歐式距離，即：

由以上兩式，無人機航路規劃的代價函數可以確定。但是考慮到無人機在執行具體任務時對航路的指標要求，如航程長短、時間長短、油耗大小，是否最大程度避開威脅等[6]。因此，針對航路規劃任務對各種指標的偏重程度，引入指標的權重系數w，則無人機航路規劃的代價函數為：

4 稀疏A＊算法流程

稀疏A*算法首先需要對規劃空間進行合理的劃分，然后按照設計的評價函數擴展節點。在規劃空間中進行搜索，其中的節點在搜索過程中可分為三類：

1）已被擴展的節點，又成為封閉節點，存放在CLOSED表中；2）當前節點的可行子節點等待擴展的節點，在搜索過程中存放在OPEN表中；3）尚未產生的節點。

采用稀疏A*算法規劃航路，步驟如下：

步驟1 將起始節點插入OPEN表中，將CLOSE表置為空。

步驟2 如果OPEN表為空，算法搜索失敗。調整算法參數（將規劃空間的網格精度調高，或調整啟發函數保證其滿足可接納性），重新運行搜索。

步驟3 從OPEN表中移出代價最小的節點作為當前節點，并將其放入到CLOSE表中。

步驟4 如果當前節點與目標節點之間的距離小于最小步長，則將目標點的父節點指針指向當前節點，航路搜索結束，算法搜索成功。從目標點開始向上回溯到起始位置，得到從起始點到目標點的最小代價航路。

步驟5 擴展當前節點。根據當前節點劃分規劃空間，并判斷后繼節點是否滿足最小飛行高度和航程的約束，若滿足，則作為有效后繼節點，否則舍棄。將有效后繼節點的父指針指向當前節點。

步驟6 返回步驟2。

5 仿真驗證

設計數字地圖，其中威脅區（如雷達）用坐標為(500,120)和(900,850)，半徑分別為80和75的兩個圓表示。按照最大拐彎角為45°，最大爬升/俯沖角為30°，最小步長為2km，對規劃空間進行劃分，代價函數采用式（6）。選擇無人機起點網格坐標為（0，0，0），目標點網格坐標（1000，1000，15）。

取啟發函數權重為wh=0.4，并取實際代價函數g( n)中航程代價、爬升代價、威脅代價權重相等，即wL=0.2，wC=0.2，wT=0.2。采用稀疏A*算法得到的航路規劃等高線圖見圖1。采用該算法規劃的航路可以避開雷達和山峰的威脅，能夠實現三維范圍內的航路規劃功能。但由圖1可以看出該航路的航程較長，在緊急任務或航路航程限制嚴格時可能不滿足實際要求。

可以調整實際代價函數g( n)中各參數的權重來實現航程最短[7]。在啟發函數和雷達威脅權重不變的情況下，通過調高航程代價并降低爬升代價，即wL=0.3，wC=0.1，wT=0.2，wh=0.4，得到三維航程最優仿真得到的航路規劃等高線圖如圖2所示。由航程最優航路仿真圖可以看出，航路在滿足威脅規避的情況下，在損失了局部爬升代價的情況下，明顯的縮短了航程。

6 結論

通過分析無人機在多約束條件下的三維空間航路規劃問題，采用稀疏A*算法的航路規劃方法，研究了航路規劃空間的劃分方法，針對航路規劃任務對各種指標的偏重程度，引入指標的權重系數w，得到無人機航路規劃的代價函數。在啟發函數和雷達威脅權重不變的情況下，通過調整實際代價函數中各參數的權重來實現航程最短。

圖1 采用等權重的航路規劃等高線圖

圖2 航程最優航路等高線圖

仿真結果表明該方法能夠較好地解決多約束條件下的航路最優規劃問題，實際應用后的效果進一步驗證了該方法的有效性。

[1]李素娟，肖前貴．多約束條件下無人機航路規劃動態評價方法[J]．指揮控制與仿真，2012，34（2）：40-44．

[2]劉希，朱凡等．一種改進的快速航路規劃方法[J]．飛行力學，2011，29（1）：89-92．[3]丁吉．未知環境中無人機偵察機動態航路規劃[J]．四川兵工學報，2012，33（5）：28-31．

[4]張書宇，張金雨，李雪梅．多方向飽和攻擊時反艦導彈航路規劃方法[J]．指揮控制與仿真，2012，31（11）：6-9．

[5]劉海橋，馬東立．無人機三維航跡規劃與可視化仿真[J]．火力與指揮控制，2011，36（7）：72-74．

[6]吳劍，喻玉華等．無人機航路規劃中的變步長A*算法[J]．光電與控制，2011，18（5）：1-5．

[7]席慶彪，蘇鵬，劉慧霞．基于A*算法的無人機航路規劃[J]．指揮控制與仿真，2013，38（11）：5-9．

Method of Unmanned Aerial Vehicle Path Planning Based on Sparse A* Algorithm

Chen Huijie
（No.92419 Unit of PLA，Xingcheng，125106）

Aiming at the path planning of three dimensional space under constraint condition，analyzed the dividing method of three dimensional space, comprehensive consideration of voyage cost, cost to climb and threat to the price and other factors, tasks on the degree of lay particular stress on various indicators for path planning, the introduction of the index weight coefficient, designed the cost function, compiled the algorithm process, simulation is conducted on the effectiveness of the algorithm. The result shows that, using spare A* algorithm can effectively solve the constraint conditions of path planning problem in three dimensional space.

unmanned air vehicle；path Planning；sparse A* algorithm

陳慧杰（1983—），男，漢，山西忻州人，碩士研究生，主要研究方向為無人機總體設計。