陳慧杰

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

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

陳慧杰

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

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

無人機；航路規(guī)劃；稀疏A*算法

0 引言

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

1 稀疏A＊算法及其特性

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

2 規(guī)劃空間的劃分

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

3 代價函數(shù)設(shè)計

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

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

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

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

4 稀疏A＊算法流程

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

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

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

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

步驟2 如果OPEN表為空，算法搜索失敗。調(diào)整算法參數(shù)（將規(guī)劃空間的網(wǎng)格精度調(diào)高，或調(diào)整啟發(fā)函數(shù)保證其滿足可接納性），重新運行搜索。

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

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

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

步驟6 返回步驟2。

5 仿真驗證

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

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

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

6 結(jié)論

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

圖1 采用等權(quán)重的航路規(guī)劃等高線圖

圖2 航程最優(yōu)航路等高線圖

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

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

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

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

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

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

[7]席慶彪，蘇鵬，劉慧霞．基于A*算法的無人機航路規(guī)劃[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—），男，漢，山西忻州人，碩士研究生，主要研究方向為無人機總體設(shè)計。