基于地形的直升機路徑規劃算法研究

石璐璐，徐金明

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

0 引言

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

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

1 標準A*算法

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

h

(

m

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

標準A*算法的代價函數形式為：

f

(

m

)=

g

(

m

)+

h

(

m

)

(1)

其中，

f

(

m

)表示當前節點

m

的代價值，

g

(

m

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

m

的實際代價值，啟發函數

h

(

m

)表示從當前節點

m

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

g

(

m

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

h

(

m

)一般設為當前節點到目標點的歐式距離。已經證明，只要啟發函數滿足可接納性條件，即

h

(

m

)小于等于節點

m

到目標點的真實代價

h

(

m

)，且狀態空間中存在可行解，則A*算法可以保證找到最優解。當

h

(

m

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

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

2 標準A*算法的改進

2.1 代價函數的設計

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

g

(

m

)和啟發函數

h

(

m

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

g

(

m

)的求解公式：

g

(

m

)=

k

∑

D

(

i

)+

k

∑

A

(

i

)+

k

∑

S

(

i

)

(2)

式中，

D

(

i

)為節點

i

與節點

i

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

A

(

i

)為節點

i

與節點

i

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

S

(

i

)為節點

i

與節點

i

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

k

、

k

、

k

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

g

(

m

)拆分成三項，并通過設置合適的加權系數，最終規劃出綜合航程較短、爬升

/

下降較少、轉彎次數較少的期望路徑。啟發函數通常使用當前節點與目標節點之間的歐式距離來表示，以保證

h

(

m

)≤

h

(

m

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

h

(

m

)求解公式為：

h

(

m

)=

a

(

k

D

(

m

)+

k

A

(

m

))

(3)

式中，

D

(

m

)為節點

m

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

A

(

m

)為節點

m

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

k

、

k

分別為各項的加權系數，與實際代價值求解公式中的系數相同，

a

為啟發函數預估代價值的權值參數。角度差代價

S

(

i

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

g

(

m

)相比，

h

(

m

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

D

(

m

)、高度差代價

A

(

m

)。此外，還增加了權值參數

a

，用以調節算法運行速度。

2.2 節點擴展改進

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

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

m

-1為節點

m

的父節點，即

m

-1—

m

為當前節點

m

的路徑方向。

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

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

length

_

step

>

R

(4)

式中，

length

_

step

為柵格距離

/

算法的搜索步長距離值，

R

為直升機的最小轉彎半徑。

2.3 搜索步驟優化

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

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

1)如果

m

點是起始點，則節點

m

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

m

點不是起始點，計算節點

m

與節點

m

-1的相對位置(Δ

x

,Δ

y

)，其中Δ

x

=

x

-

x

-1,Δ

y

=

y

-

y

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

x

,Δ

y

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

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

圖2 改進A*算法流程圖

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

/

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

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

3 算法性能分析

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

影響算法性能的參數有：

1)

k

(代價函數—水平距離加權系數)；2)

k

(代價函數—地形高度差加權系數)；3)

k

(代價函數—角度加權系數)；4)

a

(啟發函數的權值參數)；5)

length

_

step

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

k

、

k

、

k

、

a

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

length

_

step

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

length

_

step

>180m的要求，

length

_

step

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

length

_

step

=8×25m。

3.1 加權系數的影響分析

根據算法原理來看，加權系數不是通過自身的數值，而是通過三個加權系數之間的比值關系來對算法性能產生影響的。因此，為了便于分析，將

k

設為1。1)

k

的影響分析在分析

k

值影響的仿真試驗中，將

k

、

a

四個參數均設為1，

k

取0，通過調整

k

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

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

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

k

=0時，直升機完全進行貼地直線飛行，當地形起伏較大時，飛行操作難度大，不滿足實際的飛行需求；在

k

一定的情況下，

k

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

k

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

k

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

k

/k

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

k

值設定為5。2)

k

的影響分析在分析

k

值影響的仿真試驗中，將

k

、

a

三個參數均設為1，

k

設為5，通過調整

k

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

k

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

k

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

k

=2000時，路徑角度對算法的影響遠遠大于超越地形高度差的影響，規劃路徑變為一條連接起點、終點的直線。

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

在不同地圖中，

k

與

k

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

k

/k

=20時，實現在低海拔區域的路徑平滑效果；當

k

/k

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

3.2 權值參數a的影響分析

啟發函數的權值參數

a

是用來調整算法的搜索效率的。從算法原理來看，

a

值越大，算法越快地趨向終點，搜索效率越高。基于前文的仿真結果，為了便于分析，本文中將

k

設為1，

k

設為5，

k

設為100。不同

a

值下的算法搜索步數如圖5所示。可以明顯地看出，隨著

a

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

a

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

a

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

a

值大于2后，隨著

a

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

a

值下的規劃路徑圖進行對比分析，如圖6所示。結合圖5中的算法搜索步數與

a

值關系以及圖6中的路徑規劃結果，可知：當

a

<2時，啟發函數的權值比重仍然比實際代價值小，規劃結果受實際代價值影響更大；當

a

>2時，啟發函數的權值比重逐漸超過實際代價值。

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

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

從兼顧算法搜索效率和規劃路徑效果的出發點來考慮，

a

值應該小于圖5中圖線轉折點對應的

a

值，在本文的地圖和參數設置條件下，即為

a

<2。

4 總結

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

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