石璐璐，徐金明

(中國直升機設(shè)計研究所，江西 景德鎮(zhèn) 333001)

0 引言

軍用直升機的作戰(zhàn)飛行空間主要集中在低空或超低空。在此空間內(nèi)，直升機易受到低空障礙物和地形的干擾?；诘匦蔚穆窂揭?guī)劃是直升機低空飛行路徑規(guī)劃技術(shù)的基礎(chǔ)，利用任務(wù)區(qū)域的高程地圖數(shù)據(jù)，規(guī)劃出滿足任務(wù)約束條件和直升機平臺性能約束的全局規(guī)劃航路，為直升機在山地、丘陵等復雜地形環(huán)境下安全飛行提供路徑作為參考，從而降低飛行員的負擔，提高直升機飛行的安全性。

Dijkstra算法是最經(jīng)典的最短路徑搜索算法，屬于遍歷搜索，以起始點為中心向外層層擴展，直到擴展到終點為止。A*算法是在Dijkstra算法的基礎(chǔ)上，加入啟發(fā)式函數(shù)，用來決定下一步應該優(yōu)先擴展哪個節(jié)點。很多外國學者提出了A*算法的各種改進和優(yōu)化，如IDA*算法、LPA*算法、BidirectionalA*算法等。經(jīng)過改進和優(yōu)化后的A*算法在求解準確性和算法效率上都有了極大的提高，A*算法是直升機路徑規(guī)劃領(lǐng)域目前研究較為成熟、應用較多的一種算法。文獻[6]便是基于A*搜索算法，提出了救援直升機二維航跡規(guī)劃方法，在滿足安全間隔的前提下，求解可行最短飛行路徑。因此，文本選擇A*算法進行基于地形的直升機路徑規(guī)劃研究。

1 標準A*算法

A*算法是一種啟發(fā)式搜索算法，通過設(shè)定合適的代價函數(shù)，全面評估每個待擴展節(jié)點的實際代價值和預估代價值，通過比較所有待擴展節(jié)點的代價值大小，選擇代價最小的節(jié)點進行擴展，直到找到目標節(jié)點位置。相比Dijkstra算法，A*算法引入了啟發(fā)函數(shù)

h

(

m

)來估計當前節(jié)點到目標點的代價，從而引導搜索方向，達到減少搜索范圍、提高搜索效率的目的。

標準A*算法的代價函數(shù)形式為：

f

(

m

)=

g

(

m

)+

h

(

m

)

(1)

其中，

f

(

m

)表示當前節(jié)點

m

的代價值，

g

(

m

)表示從起始位置點到當前節(jié)點

m

的實際代價值，啟發(fā)函數(shù)

h

(

m

)表示從當前節(jié)點

m

到目標點的預估代價值。在標準A*算法中，

g

(

m

)一般設(shè)為實際的路徑長度，

h

(

m

)一般設(shè)為當前節(jié)點到目標點的歐式距離。已經(jīng)證明，只要啟發(fā)函數(shù)滿足可接納性條件，即

h

(

m

)小于等于節(jié)點

m

到目標點的真實代價

h

(

m

)，且狀態(tài)空間中存在可行解，則A*算法可以保證找到最優(yōu)解。當

h

(

m

)=0時，A*算法就變成了Dijkstra算法。

在實際應用中，標準A*算法還存在一些問題，比如算法收斂時間較長、規(guī)劃路徑不滿足直升機飛行性能要求等。針對這些問題，本文對標準A*算法進行了實用性改進。

2 標準A*算法的改進

2.1 代價函數(shù)的設(shè)計

A*算法的核心部分是代價函數(shù)的設(shè)計，包括實際代價值

g

(

m

)和啟發(fā)函數(shù)

h

(

m

)。首先需要確定實際代價值

g

(

m

)的求解公式：

g

(

m

)=

k

∑

D

(

i

)+

k

∑

A

(

i

)+

k

∑

S

(

i

)

(2)

式中，

D

(

i

)為節(jié)點

i

與節(jié)點

i

-1之間航路段的水平距離；

A

(

i

)為節(jié)點

i

與節(jié)點

i

-1之間航路段的地形高度差值；

S

(

i

)為節(jié)點

i

與節(jié)點

i

-1之間的航路段及上一個航路段之間的角度值；

k

、

k

、

k

分別為各項的加權(quán)系數(shù)。相比傳統(tǒng)三維A*算法中直接通過空間距離確定的實際代價值，本文將實際代價值

g

(

m

)拆分成三項，并通過設(shè)置合適的加權(quán)系數(shù)，最終規(guī)劃出綜合航程較短、爬升

/

下降較少、轉(zhuǎn)彎次數(shù)較少的期望路徑。啟發(fā)函數(shù)通常使用當前節(jié)點與目標節(jié)點之間的歐式距離來表示，以保證

h

(

m

)≤

h

(

m

)。本文為了使啟發(fā)函數(shù)更接近實際代價值，提高算法效率，設(shè)計

h

(

m

)求解公式為：

h

(

m

)=

a

(

k

D

(

m

)+

k

A

(

m

))

(3)

式中，

D

(

m

)為節(jié)點

m

、目標點之間的水平距離，

A

(

m

)為節(jié)點

m

、目標點之間的地形高度差，

k

、

k

分別為各項的加權(quán)系數(shù)，與實際代價值求解公式中的系數(shù)相同，

a

為啟發(fā)函數(shù)預估代價值的權(quán)值參數(shù)。角度差代價

S

(

i

)項是航段之間的夾角，難以準確預估，因此與實際代價值

g

(

m

)相比，

h

(

m

)少了角度差代價項，僅有水平距離代價

D

(

m

)、高度差代價

A

(

m

)。此外，還增加了權(quán)值參數(shù)

a

，用以調(diào)節(jié)算法運行速度。

2.2 節(jié)點擴展改進

傳統(tǒng)二維A*算法在進行柵格擴展時可以向8個方向進行擴展，每次選擇待擴展子節(jié)點中代價函數(shù)值最小的節(jié)點作為下一個搜索節(jié)點，直至最終到達目標點。普通A*算法是全方向的擴展搜索，并未考慮直升機本身的性能約束，使得算法的效率低下。此處考慮采用改進A*算法，結(jié)合直升機的約束條件排除無效節(jié)點，減少節(jié)點的擴展方向，從而有效減少搜索空間，提高搜索的效率。

考慮到直升機的飛行性能等因素，在飛行速度不為零的情況下，直升機無法原地掉頭；在直升機轉(zhuǎn)彎半徑的限制以及規(guī)劃路徑平滑度要求下，排除短距離大角度轉(zhuǎn)彎的極限操作。因此，根據(jù)直升機實際飛行方向限制，將8個節(jié)點擴展方向縮減為3個。如圖1所示，在節(jié)點m處只能向其路徑方向水平投影的正前方、左前方、右前方的備選節(jié)點擴展，

m

-1為節(jié)點

m

的父節(jié)點，即

m

-1—

m

為當前節(jié)點

m

的路徑方向。

圖1 改進A*算法節(jié)點擴展方向示意圖

此外，為了使最終得到的路徑滿足直升機轉(zhuǎn)彎半徑限制，地圖柵格距離即搜索步長應滿足一定的約束條件：

length

_

step

>

R

(4)

式中，

length

_

step

為柵格距離

/

算法的搜索步長距離值，

R

為直升機的最小轉(zhuǎn)彎半徑。

2.3 搜索步驟優(yōu)化

本文的改進A*算法的搜索步驟與傳統(tǒng)A*算法大體相同，僅增加了子節(jié)點的判斷步驟和子節(jié)點是否滿足直升機性能約束的判斷步驟。改進A*算法的搜索步驟如圖2所示。

圖2中步驟(1)為改進算法的新增步驟—子節(jié)點的判斷。2.2節(jié)中介紹了節(jié)點擴展方向由8個改進為3個，但是起始點不存在父節(jié)點，因此無法將子節(jié)點縮減為3個。與其他節(jié)點不同，起始點的子節(jié)點仍然有8個。具體操作為：

1)如果

m

點是起始點，則節(jié)點

m

存在8個子節(jié)點，步驟結(jié)束；2)如果

m

點不是起始點，計算節(jié)點

m

與節(jié)點

m

-1的相對位置(Δ

x

,Δ

y

)，其中Δ

x

=

x

-

x

-1,Δ

y

=

y

-

y

-1;3)根據(jù)相對位置(Δ

x

,Δ

y

)，獲得當前節(jié)點處的路徑方向，確定3個子節(jié)點的位置，步驟結(jié)束。

圖2中步驟(2)為改進算法應用的新增步驟—子節(jié)點是否滿足直升機性能約束的判斷。為了使規(guī)劃路徑滿足直升機實際飛行性能要求，且安全可行，需要在節(jié)點擴展過程中對子節(jié)點是否滿足直升機性能約束進行判斷，不滿足的子節(jié)點則直接跳過。具體操作為：

圖2 改進A*算法流程圖

1)為子節(jié)點賦予滿足離地高度約束的高度值，計算當前節(jié)點與子節(jié)點高度差和水平投影距離的比值，判斷計算結(jié)果是否滿足直升機爬升梯度

/

下降梯度的限制，若不滿足則直接跳過該節(jié)點；

2)計算子節(jié)點水平安全范圍內(nèi)，是否有地形障礙物，若有地形障礙物，則直接跳過該節(jié)點。

3 算法性能分析

本文選擇了范圍15km×15km、精度25m的高程地圖，通過MATLAB進行改進A*算法的仿真分析。

影響算法性能的參數(shù)有：

1)

k

(代價函數(shù)—水平距離加權(quán)系數(shù))；2)

k

(代價函數(shù)—地形高度差加權(quán)系數(shù))；3)

k

(代價函數(shù)—角度加權(quán)系數(shù))；4)

a

(啟發(fā)函數(shù)的權(quán)值參數(shù))；5)

length

_

step

(搜索步長)等。本文選擇其中的

k

、

k

、

k

、

a

四個參數(shù)進行影響分析。為了不影響對參數(shù)影響的分析，為搜索步長設(shè)置合適的數(shù)值。取直升機飛行速度為200km/h。該速度下直升機的最小轉(zhuǎn)彎半徑為180m，因此要求

length

_

step

>180m。由于地圖精度為25m，為了滿足

length

_

step

>180m的要求，

length

_

step

應該≥8個地圖坐標，即200m。從仿真試驗角度來說，搜索步長越小，仿真結(jié)果越可靠。因此本文仿真試驗中，取

length

_

step

=8×25m。

3.1 加權(quán)系數(shù)的影響分析

根據(jù)算法原理來看，加權(quán)系數(shù)不是通過自身的數(shù)值，而是通過三個加權(quán)系數(shù)之間的比值關(guān)系來對算法性能產(chǎn)生影響的。因此，為了便于分析，將

k

設(shè)為1。1)

k

的影響分析在分析

k

值影響的仿真試驗中，將

k

、

a

四個參數(shù)均設(shè)為1，

k

取0，通過調(diào)整

k

的數(shù)值來得到不同的規(guī)劃路徑(圖3)。

圖3 路徑規(guī)劃結(jié)果(k1=1，k3=0，a=1)

比較圖3中4條路徑可知：當

k

=0時，直升機完全進行貼地直線飛行，當?shù)匦纹鸱^大時，飛行操作難度大，不滿足實際的飛行需求；在

k

一定的情況下，

k

值越大，算法越趨近于地形規(guī)避，即避開高海拔區(qū)域，盡量在地形平坦區(qū)域飛行。但是

k

值過大會導致算法敏感度增加，在不影響整體路徑的基礎(chǔ)上，路徑中的拐點會增加，路徑平滑度下降。因此，為了獲得合適的路徑，

k

的取值應該根據(jù)任務(wù)區(qū)域地形特點、飛行任務(wù)需求等進行綜合考慮。具體取值需要在大量樣本下進行對比分析，最終給出建議值，本文在此不做更多討論。在本文所用地圖中，當

k

/k

=5時的路徑結(jié)果最接近期望路徑，因此后面的仿真中，

k

值設(shè)定為5。2)

k

的影響分析在分析

k

值影響的仿真試驗中，將

k

、

a

三個參數(shù)均設(shè)為1，

k

設(shè)為5，通過調(diào)整

k

的數(shù)值來得到不同的規(guī)劃路徑(圖4)。比較圖4中幾條路徑可以看出：隨著

k

值的增加，規(guī)劃路徑中會在不影響整體路徑的基礎(chǔ)上拐點逐漸減少，即路徑的平滑度逐漸增加；然而，當

k

值從500開始，整體路徑受到影響，此時，在本地圖中，路徑角度對算法的影響開始超越地形高度差的影響；當

k

=2000時，路徑角度對算法的影響遠遠大于超越地形高度差的影響，規(guī)劃路徑變?yōu)橐粭l連接起點、終點的直線。

圖4 路徑規(guī)劃結(jié)果(k1=1，k2=5，a=1)

在不同地圖中，

k

與

k

的比值對路徑的影響有所不同。在本文所用地圖中，當

k

/k

=20時，實現(xiàn)在低海拔區(qū)域的路徑平滑效果；當

k

/k

=100時，路徑角度和地形高度差對規(guī)劃路徑的影響趨于平衡。

3.2 權(quán)值參數(shù)a的影響分析

啟發(fā)函數(shù)的權(quán)值參數(shù)

a

是用來調(diào)整算法的搜索效率的。從算法原理來看，

a

值越大，算法越快地趨向終點，搜索效率越高?；谇拔牡姆抡娼Y(jié)果，為了便于分析，本文中將

k

設(shè)為1，

k

設(shè)為5，

k

設(shè)為100。不同

a

值下的算法搜索步數(shù)如圖5所示?？梢悦黠@地看出，隨著

a

值的增加，算法的搜索效率也在增加。當

a

值為0時，算法幾乎遍歷了地圖上所有的節(jié)點；

a

值從0增長至2的過程中，算法的搜索步數(shù)在大幅減少；當

a

值大于2后，隨著

a

值的增長，算法搜索步數(shù)的增加幅度有著顯著的降低，且兩者之間幾乎呈線性關(guān)系。選取其中一部分

a

值下的規(guī)劃路徑圖進行對比分析，如圖6所示。結(jié)合圖5中的算法搜索步數(shù)與

a

值關(guān)系以及圖6中的路徑規(guī)劃結(jié)果，可知：當

a

<2時，啟發(fā)函數(shù)的權(quán)值比重仍然比實際代價值小，規(guī)劃結(jié)果受實際代價值影響更大；當

a

>2時，啟發(fā)函數(shù)的權(quán)值比重逐漸超過實際代價值。

圖5 算法搜索步數(shù)與a值關(guān)系圖(k1=1，k2=5，k3=100)

圖6 路徑規(guī)劃結(jié)果(k1=1、k2=5、k3=100)

從兼顧算法搜索效率和規(guī)劃路徑效果的出發(fā)點來考慮，

a

值應該小于圖5中圖線轉(zhuǎn)折點對應的

a

值，在本文的地圖和參數(shù)設(shè)置條件下，即為

a

<2。

4 總結(jié)

針對直升機在山地、丘陵等復雜地形環(huán)境下的低空飛行需求，本文設(shè)計一種基于地形的路徑規(guī)劃算法，在代價函數(shù)、節(jié)點擴展方向、約束條件等方面對A*算法進行了改進，為直升機路徑規(guī)劃算法提供設(shè)計思路和算法改進的方向；通過仿真試驗，分析了算法參數(shù)值對算法性能的影響，并給出參數(shù)選取原則，為改進A*算法在基于地形的直升機路徑規(guī)劃中的實際應用奠定基礎(chǔ)。

然而本文的算法性能分析是基于選定地圖進行的，下一步，將利用大量不同環(huán)境下的地圖數(shù)據(jù)研究算法參數(shù)值的自適應選擇方法，以解決不同任務(wù)環(huán)境中的直升機路徑規(guī)劃問題。