基于地形的直升機(jī)路徑規(guī)劃算法研究

石璐璐，徐金明

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

0 引言

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

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

1 標(biāo)準(zhǔn)A*算法

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

h

(

m

)來估計(jì)當(dāng)前節(jié)點(diǎn)到目標(biāo)點(diǎn)的代價(jià)，從而引導(dǎo)搜索方向，達(dá)到減少搜索范圍、提高搜索效率的目的。

標(biāo)準(zhǔn)A*算法的代價(jià)函數(shù)形式為：

f

(

m

)=

g

(

m

)+

h

(

m

)

(1)

其中，

f

(

m

)表示當(dāng)前節(jié)點(diǎn)

m

的代價(jià)值，

g

(

m

)表示從起始位置點(diǎn)到當(dāng)前節(jié)點(diǎn)

m

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

h

(

m

)表示從當(dāng)前節(jié)點(diǎn)

m

到目標(biāo)點(diǎn)的預(yù)估代價(jià)值。在標(biāo)準(zhǔn)A*算法中，

g

(

m

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

h

(

m

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

h

(

m

)小于等于節(jié)點(diǎn)

m

到目標(biāo)點(diǎn)的真實(shí)代價(jià)

h

(

m

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

h

(

m

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

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

2 標(biāo)準(zhǔn)A*算法的改進(jìn)

2.1 代價(jià)函數(shù)的設(shè)計(jì)

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

g

(

m

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

h

(

m

)。首先需要確定實(shí)際代價(jià)值

g

(

m

)的求解公式：

g

(

m

)=

k

∑

D

(

i

)+

k

∑

A

(

i

)+

k

∑

S

(

i

)

(2)

式中，

D

(

i

)為節(jié)點(diǎn)

i

與節(jié)點(diǎn)

i

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

A

(

i

)為節(jié)點(diǎn)

i

與節(jié)點(diǎn)

i

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

S

(

i

)為節(jié)點(diǎn)

i

與節(jié)點(diǎn)

i

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

k

、

k

、

k

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

g

(

m

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

/

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

h

(

m

)≤

h

(

m

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

h

(

m

)求解公式為：

h

(

m

)=

a

(

k

D

(

m

)+

k

A

(

m

))

(3)

式中，

D

(

m

)為節(jié)點(diǎn)

m

、目標(biāo)點(diǎn)之間的水平距離，

A

(

m

)為節(jié)點(diǎn)

m

、目標(biāo)點(diǎn)之間的地形高度差，

k

、

k

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

a

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

S

(

i

)項(xiàng)是航段之間的夾角，難以準(zhǔn)確預(yù)估，因此與實(shí)際代價(jià)值

g

(

m

)相比，

h

(

m

)少了角度差代價(jià)項(xiàng)，僅有水平距離代價(jià)

D

(

m

)、高度差代價(jià)

A

(

m

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

a

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

2.2 節(jié)點(diǎn)擴(kuò)展改進(jìn)

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

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

m

-1為節(jié)點(diǎn)

m

的父節(jié)點(diǎn)，即

m

-1—

m

為當(dāng)前節(jié)點(diǎn)

m

的路徑方向。

圖1 改進(jìn)A*算法節(jié)點(diǎn)擴(kuò)展方向示意圖

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

length

_

step

>

R

(4)

式中，

length

_

step

為柵格距離

/

算法的搜索步長距離值，

R

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

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

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

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

1)如果

m

點(diǎn)是起始點(diǎn)，則節(jié)點(diǎn)

m

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

m

點(diǎn)不是起始點(diǎn)，計(jì)算節(jié)點(diǎn)

m

與節(jié)點(diǎn)

m

-1的相對位置(Δ

x

,Δ

y

)，其中Δ

x

=

x

-

x

-1,Δ

y

=

y

-

y

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

x

,Δ

y

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

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

圖2 改進(jìn)A*算法流程圖

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

/

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

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

3 算法性能分析

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

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

1)

k

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

k

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

k

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

a

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

length

_

step

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

k

、

k

、

k

、

a

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

length

_

step

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

length

_

step

>180m的要求，

length

_

step

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

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

值影響的仿真試驗(yàn)中，將

k

、

a

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

k

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

k

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

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

比較圖3中4條路徑可知：當(dāng)

k

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

k

一定的情況下，

k

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

k

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

k

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

k

/k

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

k

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

k

的影響分析在分析

k

值影響的仿真試驗(yàn)中，將

k

、

a

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

k

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

k

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

k

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

k

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

k

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

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

在不同地圖中，

k

與

k

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

k

/k

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

k

/k

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

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

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

a

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

a

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

k

設(shè)為1，

k

設(shè)為5，

k

設(shè)為100。不同

a

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

a

值的增加，算法的搜索效率也在增加。當(dāng)

a

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

a

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

a

值大于2后，隨著

a

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

a

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

a

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

a

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

a

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

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

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

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

a

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

a

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

a

<2。

4 總結(jié)

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

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