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

陳 志，秦學富

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

0 引 言

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

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

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

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

1.1 地形障礙

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

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

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

1.2 渦流障礙

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

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

2 改進A＊算法

2.1 傳統(tǒng)的A＊算法

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

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

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

2.2 搜索方向和搜索步長節(jié)點的改進

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

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

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

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

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

2.3 路徑評估代價函數(shù)的設(shè)計

（1）變權(quán)值評估函數(shù)

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

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

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

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

無人機飛行高度設(shè)計在無人機航行路徑規(guī)劃中較為重要，其主要體現(xiàn)在合理的飛行高度可以保證無人機飛行的安全穩(wěn)定，如果無人機在無障礙的情況下需要長距離平穩(wěn)飛行，則保持一個固定的高度飛行可以縮短飛行時間，如果無人機有“隱形”飛行的需求，那么需要無人機飛行高度低一些，在不同的路徑規(guī)劃中，飛行高度會根據(jù)需求調(diào)整，故在路徑評估函數(shù)中還需要增加高度評估的部分，如式（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)的權(quán)重，wC為C(n)的權(quán)重，wL為T(n)的權(quán)重。在前文中，h(n)也被稱為啟發(fā)函數(shù)，其表示無人機當前位置至目標位置之間的歐式距離，如式（8）所示：

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

3 仿真結(jié)果與討論

3.1 仿真參數(shù)設(shè)定

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

表1 山體模型參數(shù)

表2 氣象渦流模型參數(shù)

3.2 仿真結(jié)果

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

（1）步長

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

表3 不同步長下路徑規(guī)劃

根據(jù)表3，最大步長調(diào)整后，無人機航行規(guī)劃的路徑不同，體現(xiàn)在規(guī)劃總航程、規(guī)劃步數(shù)上均有差異。從表3 中可知，當λ為0.8 時，無人機航行規(guī)劃的總路程最短。

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

通過設(shè)置不同的wh和wg實現(xiàn)無人機的路徑規(guī)劃，如圖2 所示為其仿真結(jié)果。

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

表4 航行過程中不同權(quán)值下路徑參數(shù)

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

3.3 改進A＊算法仿真驗證

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

圖3 路徑規(guī)劃的三維圖

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

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

表5 A＊算法改進前后的數(shù)據(jù)對比

4 結(jié) 語

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