一種改進A*算法的無人機路徑規劃研究*

陳 志，秦學富

（1.桂林航天工業學院機械工程學院，廣西 桂林 541004；2.桂林長海發展有限責任公司，廣西 桂林 541001）

0 引 言

近年來，隨著無人機技術的不斷發展，越來越多的機構、個人參與到無人機的研發和使用中來[1]。無人機憑借其高機動性和低風險性被廣泛應用與地質勘測、人員搜救以及戶外偵察等[2-3]。目前無人機的研究方向主要是無人機的路徑規劃等，其研究內容涉及到環境建模、編航跡規劃等[4]。針對無人機路徑規劃研究，文獻[5]提出出了一種結合分段自適應B 樣條（PABS）方法的領航-跟隨策略，有效提高無人機飛行效率；文獻[6]將改進后的鴿群算法和無人機控制量結合作為控制系統中的直接控制環，結果表明該控制系統能夠為無人機提供最優飛行路徑；文獻[7]面對無人機編隊控制系統中系統函數未知的情況下，使用模糊邏輯系統逼近未知函數，并設計了飛行路徑控制器，確保無人機在飛行過程中減少搜索時間。文獻[8]采用A*算法對無人機搜索空間中冗余部分進行了刪除，以減少搜索空間，提升搜索效率。文獻[9]則對搜索空間進行拓展，使其成為三維平面，此外根據無人機的性能約束來對搜索空間進行剪除，提高無人機飛行效率。

通過研究發現，現有的無人機路徑規劃算法能夠在一定程度上提高無人機路徑規劃的效率，但是所采用的路徑規劃算法普遍存在算法收斂速度慢，且容易陷入局部最優[10]。鑒于此，本文在研究無人機飛行特點基礎上對傳統的A*算法進行改進，以提高無人機在三維空間中路徑規劃的效率，從而減少飛行成本。

1 無人機飛行空間的障礙和威脅程度

無人機在航行的過程中，必須避開一些障礙以保證自身的安全。對于無人機來說，飛行中的障礙主要分為兩類，一為地形障礙，例如高層建筑物、山峰等；二為渦流障礙，多為惡劣的氣象引發導致。

1.1 地形障礙

無人機需要對其航行空間中的地形障礙進行躲避，在路徑規劃階段首先要對地形進行建模，因此本文以常見的山體障礙作為對象進行建模，山體的近似描述如式（1）所示：

式（1）中，z表示山體表面某點的高度，(x,y)表示該點在水平面上的坐標位置，hi表示控制高度的參數，ai為山體中心投影的橫坐標，bi為山體中心投影的縱坐標；ki表示控制地形坡度的參數。在上述表達式中設置的參數值不同，所得到的山體也不同。為描述山體對無人機的威脅程度，可以用式（2）表示：

式（2）中，Rm為山體的半徑，dm為山體中心點與無人機之間的距離。式（2）表示了如果無人機距離山體邊緣大于10 m，則認為無人機是安全的，其威脅程度為0；如果無人機距離山體邊緣小于10 m、 大于4 m，則無人機的威脅程度隨著距離的減小而增加；如果無人機距山體邊緣小于4 m，則認為威脅程度無窮大。

1.2 渦流障礙

在惡劣氣象區域常會有渦流產生[11]，為了使無人機有效規避渦流，需要對渦流進行建模。在渦流模型構建中，本文將渦流近似表達成為一個球體，球體半徑記為Rmax，其威脅程度如式（3）所示：

式（3）中，dv表示渦流中心點和無人機之間的距離；Rmax表示渦流的最大半徑。對渦流的威脅程度可以理解為：如果無人機不處于渦流所在范圍內，則其威脅程度為0；如果無人機處于渦流內，那么無人機的威脅程度與其距離渦流中心的大小呈負相關，即距離渦流中心越遠，越安全。

2 改進A＊算法

2.1 傳統的A＊算法

A*算法是指在目標空間中通過啟發式函數指引搜索方向，并通過估價函數評估路徑值對節點進行不斷搜索，進而得到最短路徑的一種算法。其中，估價函數至關重要，如式（4）所示：

式（4）中，n表示無人機當前所在的位置，f(n)表示估價函數，即無人機從初始位置航行并經過當前位置n而后到達目標位置的代價，h(n)表示指無人機從當前位置n到目標位置所需要的代價的估計值；g(n)表示無人機從初始位置到當前位置n所需要的實際代價。

搜索步長和方向是決定A*算法搜索效率的關鍵因素，因此如果要提高搜索效率，則需要從搜索步長和搜索方向兩個方面入手。

2.2 搜索方向和搜索步長節點的改進

無人機的搜索方向主要有三個，分別為前向搜索、俯仰方向搜索、偏航方向搜索，在俯仰和偏航兩個搜索方向上，其搜索的范圍受到無人機的轉彎半徑、仰俯角等機動性能的約束[12]。

固定的步長對于無人機航行路徑規劃范圍有諸多限制，若采用變化步長，根據無人機在三個搜索方向上、不同的搜索階段設定不同的步長，則能夠較好的提高路徑規劃的機動性。需要注意的是最大搜索步長應當為無人機雷達所能探測的最大距離。此外，還需要在一定區間內調整搜索步長以應對突發的渦流情況。故搜索步長在以最小轉彎半徑為最小步長，并在最小步長、最大步長這個區間內根據情況變化調整。如圖1 所示為采用變化步長的改進A*算法的三維空間搜索范圍圖。

圖1 改進A*算法的三維空間搜索范圍

在圖1 中，O 點為當前位置，OA 為最小步長，OE 為最大步長?！螰ON=θ為最大偏航角，∠EON=2θ為偏航范圍，∠HOM=φ為最大爬升角，∠FOG=2φ為俯仰范圍。

由圖1 可知，O 的可搜索范圍是由兩個球面和四棱錐面所包圍的區域內，可以將其柵格化為幾個節點，對其從俯仰方向按照p等距離劃分，從前向按照t等距離劃分，從偏航方向按照q等距離劃分，可以形成(t+1)*(q+1)*(p+1)個搜索節點。在規劃的過程中，從當前節點選擇下一個節點的方式，可采用估價函數來評估節點的優劣，而后選擇其中最好的節點，如此循環直到最終達到目標位置。

2.3 路徑評估代價函數的設計

（1）變權值評估函數

如果節點n被定義為無人機當前所在位置，那么在A*算法中，當前節點的代價可以用f(n)=g(n)+h(n) 來表示。其中g(n)表示無人機從初始位置到當前位置n所需要的實際代價，h(n)表示指無人機從當前位置n到目標位置所需要的代價的估計值，兩者對無人機航行路徑價值評估的影響有一定的差異，故使用加權評估的方法對其進行優化，如式（5）所示：

式（5）中，wg為g(n)的權值，wh為h(n)的權值，兩項權值之和應為1，可以通過合理的配置兩項權重來設計更合理的路徑。對該評估函數進行仿真驗證，可以發現g(n)和h(n)在無人機航行路徑規劃的不同時期，對于無人機航行路徑價值評估的影響是不同的，所以調整wg和wh會使路徑發生變化。另外，wh偏大會獲得較為理想的前半段路徑，wg偏大會獲得較為理想的后半段路徑。故可以通過對權重的實時調整，使評估函數得以優化，具體的調整方法如式（6）所示：

式（6）中，wgmin表示wg的初始值；wgmax表示wg的最大值；D 表示無人機從初始位置到目標位置的直線距離，h(n)表示無人機當前所在位置至目標位置的直線距離。通過該方法，可以實現無人機接近目標位置時，g(n)的權值會逐漸變大，進而獲得更合理的路徑。

（2）無人機飛行高度對評估函數的影響

無人機飛行高度設計在無人機航行路徑規劃中較為重要，其主要體現在合理的飛行高度可以保證無人機飛行的安全穩定，如果無人機在無障礙的情況下需要長距離平穩飛行，則保持一個固定的高度飛行可以縮短飛行時間，如果無人機有“隱形”飛行的需求，那么需要無人機飛行高度低一些，在不同的路徑規劃中，飛行高度會根據需求調整，故在路徑評估函數中還需要增加高度評估的部分，如式（7）所示：

g(n)=wLL(n)+wCC(n)+wTT(n) （7）

式（7）中，L(n)表示無人機從初始位置航行到當前所在位置n的飛行代價，T(n)表示威脅代價，其一般取Tmountain(n)和Tvortex(n)之間的最大值C(n)表示高度代價，wL為L(n)的權重，wC為C(n)的權重，wL為T(n)的權重。在前文中，h(n)也被稱為啟發函數，其表示無人機當前位置至目標位置之間的歐式距離，如式（8）所示：

式（8）中，當前節點的坐標為(xn,yn,zn)，目標節點的坐標為(xg,yg,zg)。

3 仿真結果與討論

3.1 仿真參數設定

本文使用Matlab 軟件進行無人機路徑規劃仿真。假設無人機的初始位置坐標為（0，0，0），目標位置的坐標為（10，10，2），設置無人機的爬升角為45°，初始航向角為45°，在其航行的區域內，存在的障礙包括地形障礙山體和氣象渦流，表1 為山峰的仿真參數、表2 為渦流的仿真參數。

表1 山體模型參數

表2 氣象渦流模型參數

3.2 仿真結果

設置p=t=q=3，即將無人機在三個方向上分成多個柵格進行節點搜索，在此參數下分別從步長、評估函數兩個因素對比分析無人機路徑規劃仿真結果。

（1）步長

設定無人機雷達最大搜索半徑為r=100 m，最小步長lmin=80 m，wh=0.7，wh=0.3，最大爬升角為30°，最大轉彎角為35°，最大步長lmax=lmin+l(r-lmin)，對λ分別取值為（0，0.2，0.4，0.6，0.8，1.0），而后進行仿真，如表3 所示為仿真結果。

表3 不同步長下路徑規劃

根據表3，最大步長調整后，無人機航行規劃的路徑不同，體現在規劃總航程、規劃步數上均有差異。從表3 中可知，當λ為0.8 時，無人機航行規劃的總路程最短。

（2）評價wh和wg對路徑的影響。

通過設置不同的wh和wg實現無人機的路徑規劃，如圖2 所示為其仿真結果。

如圖2 所示，wgmin=0.3，wgmax=0.7 時對路徑評估參數權重進行實時調整后的規劃路徑，由此可知如果wg較大時，則無人機航行的前半段路徑飛行高度會比較高，而且飛行不平滑，wh較大時前半段飛行路徑較為理想，如表4 所示為其航行過程中不同權值下路徑參數。

表4 航行過程中不同權值下路徑參數

由表4 可知，此方法能獲得較短的路徑規劃時間和規劃總航程，對于路徑規劃效果有較好的提升作用。

3.3 改進A＊算法仿真驗證

為了驗證本次提出的路徑規劃算法的有效性，利用改進后的A*搜索算法對無人機路徑進行仿真驗證，如圖3 為該路徑規劃的三維圖。

圖3 路徑規劃的三維圖

仿真實驗中，通過設置不同參數來比較改進A*算法的差異：

（1）步長、評價函數權值均不變。（2）步長為變化值，確定變化范圍，評價函數的權值不變。（3）步長和評價函數權值均為變化值，給定其變化范圍。如表5 所示為A*算法改進前后的數據對比。

表5 A＊算法改進前后的數據對比

4 結 語

本文對傳統A*算法進行改進，分別從前向、偏航方向、俯仰方向三個方向采用球形節點拓展的方法進行節點搜索。此外，該算法采用變步長搜索方法，將步長設置于最小步長和最大步長之間，同時采用實時調整權重的路徑評價函數，實現了無人機路徑規劃效率的提升和路徑規劃合理性的優化。仿真實驗證明了改進A*算法在無人機航行路徑規劃中可以有效縮短航程時間和路徑總長度。