考慮航線危險(xiǎn)天氣的動(dòng)態(tài)繞爬路徑規(guī)劃

馬 蘭，劉佳月

(中國(guó)民航大學(xué)空中交通管理學(xué)院，天津 300300)

1 引言

從宏觀層次來(lái)講，主要有三個(gè)方面能對(duì)飛行安全產(chǎn)生影響，三種因素分別是：人、機(jī)、環(huán)境。在導(dǎo)致航班延誤和改航的各種原因中，強(qiáng)對(duì)流天氣無(wú)疑占據(jù)較大比例，其中雷暴云團(tuán)內(nèi)的閃電、過(guò)冷卻水很容易對(duì)機(jī)身和發(fā)動(dòng)機(jī)造成損害，因其生命周期短且突發(fā)性為主要特征，飛行計(jì)劃中很難周全地考慮到。雖然這種天氣現(xiàn)象的尺度一般小于兩百公里、周期由幾分鐘至幾小時(shí)不等，但是對(duì)飛行安全來(lái)說(shuō)仍然需要提高警惕。與此同時(shí)，在飛行過(guò)程中影響飛行安全的因素有很多，許多外在條件的變化都會(huì)使飛行路線需要實(shí)時(shí)的動(dòng)態(tài)規(guī)劃。

路徑規(guī)劃的目的就是為了使飛機(jī)在受各種影響因素的情況下仍然能夠圓滿地完成飛行任務(wù)，國(guó)內(nèi)外對(duì)這方面的研究已經(jīng)有許多[1]。王莉莉、周娟為了應(yīng)對(duì)靜態(tài)和動(dòng)態(tài)突發(fā)天氣條件，設(shè)計(jì)啟發(fā)式算法將偏航因素考慮進(jìn)去建立了最短航程模型[2]；王清琦、張兆寧為通過(guò)合理劃設(shè)飛行受限區(qū)，利用狀態(tài)轉(zhuǎn)移矩陣對(duì)雷暴軌跡預(yù)測(cè)，為改航飛行提供參考[3]；陳至坤、郭寶軍、王淑香通過(guò)柵格法對(duì)空間環(huán)境建模，以遺傳算法對(duì)A*算法改進(jìn)路徑進(jìn)行規(guī)劃提高了運(yùn)算效率[4]；Victor Singh和Karen E.Willcox將動(dòng)態(tài)路徑規(guī)劃問(wèn)題分解為運(yùn)動(dòng)規(guī)劃和軌跡跟蹤兩部分，考慮了物理性能限制結(jié)合大量離線數(shù)據(jù)，把按約束條件規(guī)劃表達(dá)為馬爾科夫決策過(guò)程[5]；Egidio D’Amato和Massimiliano Mattei研究了多邊形障礙物、禁飛區(qū)等情況下的三維飛行路徑規(guī)劃問(wèn)題，通過(guò)降維可見(jiàn)性圖(RVG)方法使路徑長(zhǎng)度最小化[6]。

在實(shí)際飛行過(guò)程中，出現(xiàn)因操作誤差或天氣及其它因素導(dǎo)致的未能按既定航線飛行，需要盡快進(jìn)行路徑規(guī)劃恢復(fù)正常，這樣才能減小對(duì)其它飛機(jī)的影響，在繁忙路段更是這樣。本文通過(guò)改進(jìn)A*算法的底層結(jié)構(gòu)，提出不同的啟發(fā)函數(shù)，減少算法對(duì)環(huán)境節(jié)點(diǎn)的探索，節(jié)約運(yùn)行時(shí)間，針對(duì)危險(xiǎn)天氣在航路上出現(xiàn)的路徑規(guī)劃問(wèn)題做出主要研究思路如下：1)首先選擇全局靜態(tài)路徑規(guī)劃算法：A*算法作為頂層算法；2)通過(guò)Bresenham算法對(duì)A*算法底層結(jié)構(gòu)做出優(yōu)化，達(dá)到減少搜索節(jié)點(diǎn)的目的；3)二者結(jié)合不僅適用與靜態(tài)路徑規(guī)劃，同時(shí)也可以應(yīng)用于移動(dòng)障礙或突然出現(xiàn)障礙情況的動(dòng)態(tài)路徑規(guī)劃；4)分析總結(jié)在不同的障礙情況下能否繼續(xù)進(jìn)行自身查驗(yàn)。

2 Bresenham算法模型

以現(xiàn)代導(dǎo)航的設(shè)施設(shè)備條件，在進(jìn)行實(shí)際的飛行活動(dòng)前就能夠獲取從出發(fā)點(diǎn)到目的地的許多相關(guān)信息，包括航線、機(jī)型性能、預(yù)計(jì)出發(fā)和到達(dá)時(shí)刻以及預(yù)期航空位置等，這相當(dāng)于已知環(huán)境邊界以及部分環(huán)境做路徑規(guī)劃。傳統(tǒng)的路徑規(guī)劃的過(guò)程是有層次的，從動(dòng)態(tài)路徑規(guī)劃和靜態(tài)路徑規(guī)劃來(lái)講主要可以分為A*算法和D*算法，從框架層級(jí)上來(lái)講可以分為High Level：Dijkstra、A*算法等；Low Level：VO算法、RVO算法、ORCA算法等。A*算法作為靜態(tài)路網(wǎng)中路徑規(guī)劃最直接有效的辦法被廣泛應(yīng)用和改進(jìn)。

但是就像引言中提及的，首先，將空域轉(zhuǎn)化為柵格后計(jì)算規(guī)模較大、時(shí)間復(fù)雜度高，不能滿足動(dòng)態(tài)改航的需求；其次，雷暴云團(tuán)的生命周期短，A*算法并不具備預(yù)知突發(fā)情況的能力，使用起來(lái)會(huì)與實(shí)際運(yùn)行情況存在較大偏差。截至目前為止大部分對(duì)A*算法的改進(jìn)仍停留在針對(duì)OPEN表和CLOSED表的方面，以飛行過(guò)程中遇到雷暴云團(tuán)為例，A*算法會(huì)從出發(fā)點(diǎn)重新規(guī)劃一條到達(dá)目的地的航線，并不能直接對(duì)突發(fā)天氣現(xiàn)象這種動(dòng)態(tài)情況作出及時(shí)反映，且運(yùn)算時(shí)間也難以滿足需求。因此通過(guò)對(duì)A*算法的底層框架進(jìn)行修改，在減少探索節(jié)點(diǎn)的同時(shí)，通過(guò)對(duì)探索節(jié)點(diǎn)的判別實(shí)現(xiàn)動(dòng)態(tài)改航路徑規(guī)劃。

在一次完整的飛行過(guò)程中，不考慮備降場(chǎng)的情況下，出發(fā)點(diǎn)和目的地是固定的。Breshenham算法的原理就是通過(guò)判斷起訖點(diǎn)連線的斜率來(lái)確定前進(jìn)的方向。假設(shè)以空間環(huán)境左下角為坐標(biāo)原點(diǎn)，將空間轉(zhuǎn)化為柵格元素，坐標(biāo)原點(diǎn)(0，0)，目標(biāo)點(diǎn)(x，y)，由起訖點(diǎn)連線得到的一次方程可以表示為

(1)

以軸向右縱軸向上為正向，xi元素每次移動(dòng)一個(gè)柵格。

以d1、d2分別表示當(dāng)前位置在上下方向距離兩個(gè)柵格元素的距離。為了方便理解，圖1將線的交點(diǎn)視為質(zhì)點(diǎn)化的柵格元素。則有

(2)

圖1 d1和d2

Bresenham算法在選取前進(jìn)方向時(shí)主要有三種情況：

當(dāng)D1>D2時(shí)，前進(jìn)方向取(xi+1，yi+1)；當(dāng)D1

其中：D1、D2的大小關(guān)系可以通過(guò)計(jì)算差值確定

D1-D2=2k(xi+1)-2yi+2b-1

(3)

Δx(D1-D2)=2Δy(xi+1)-Δx·2yi+Δx·(2b-1)

(4)

因Δx不存在小于0的情況，令Pi=Δx(D1-D2)，則判斷D1和D2的關(guān)系如下：Pi≥0時(shí)，D1≥D2，取(xi+1，yi+1)為前進(jìn)方向；Pi<0時(shí)，D1

3 改進(jìn)算法

3.1 無(wú)障礙節(jié)點(diǎn)模型

對(duì)傳統(tǒng)的A*算法來(lái)說(shuō)，OPEN表和CLOSED表分別代表了環(huán)境空間內(nèi)還未到達(dá)探索過(guò)的節(jié)點(diǎn)和已經(jīng)訪問(wèn)探索過(guò)的節(jié)點(diǎn)，通過(guò)不斷的減少OPEN表中的節(jié)點(diǎn)并將其合適的節(jié)點(diǎn)添加到CLOSED表中達(dá)到以節(jié)點(diǎn)連成路徑的目的。

算法公式可以表示為

Fn=gn+h(n)

(5)

F(n)是從出發(fā)點(diǎn)到n點(diǎn)的總代價(jià)，g(n)是在運(yùn)行環(huán)境中從出發(fā)點(diǎn)到n點(diǎn)的實(shí)際代價(jià)，h(n)是從n點(diǎn)到目標(biāo)點(diǎn)的最佳路徑的估計(jì)代價(jià)。其主要判斷的是當(dāng)前位置與目標(biāo)之間的距離D，也就是h(n)的大小。A*算法會(huì)在探索當(dāng)前位置周圍全部節(jié)點(diǎn)的情況下選擇Dmin作為當(dāng)前位置的最優(yōu)節(jié)點(diǎn)，并重復(fù)這一過(guò)程，也就是不斷更新使

h(n)=h(Dmin)

(6)

F(n)=F(Dmin)

(7)

但是因?yàn)檫@一過(guò)程需要對(duì)每一個(gè)當(dāng)前節(jié)點(diǎn)的周圍節(jié)點(diǎn)都進(jìn)行探索，如果不根據(jù)改航的實(shí)際情況對(duì)算法的搜索方向進(jìn)行限制，可能會(huì)出現(xiàn)偏離終點(diǎn)方向的探索，這類探索在航空器的改航中是沒(méi)有意義的運(yùn)算，會(huì)導(dǎo)致算法運(yùn)算時(shí)間過(guò)長(zhǎng)、運(yùn)算效率低下。針對(duì)這一點(diǎn)用Bresenham算法對(duì)底層結(jié)構(gòu)做出調(diào)整，依據(jù)是在飛機(jī)的實(shí)際飛行路線中在當(dāng)前位置能夠探索的節(jié)點(diǎn)數(shù)是有限的，需要在符合飛機(jī)性能的條件下篩選符合條件的節(jié)點(diǎn)進(jìn)行運(yùn)算，從而減小問(wèn)題的規(guī)模。

Bresenham算法對(duì)A*算法的改進(jìn)可以通過(guò)如下舉例說(shuō)明：假設(shè)起點(diǎn)在環(huán)境空間偏左下的位置，終點(diǎn)在環(huán)境空間偏右上的位置，那么為了使從起點(diǎn)到終點(diǎn)走過(guò)的總距離盡量短，很明顯的是總體移動(dòng)方向會(huì)向右和向上(假設(shè)在柵格化的環(huán)境空間中不允許直接斜向移動(dòng))，也就是起點(diǎn)的前進(jìn)選擇方向是存在限制的，并不是全部的八個(gè)方向，而是最多只能從中選擇五方向前進(jìn)，如圖2所示。

圖2 五方向前進(jìn)

先定義這五個(gè)方向與當(dāng)前位置的坐標(biāo)夾角為表示該步長(zhǎng)的方向矢量，用SL·cosθ表示，若物體當(dāng)前位置已經(jīng)移動(dòng)到與終點(diǎn)同水平或同垂直邊界上，則當(dāng)前位置的選擇方向繼續(xù)減少。在前進(jìn)路徑上沒(méi)有障礙阻擋時(shí)，各方向步長(zhǎng)相同，則當(dāng)前位置到達(dá)周圍的柵格可以表示為

(8)

以當(dāng)前位置正上為0°順時(shí)針計(jì)算角度，與空中導(dǎo)航原則保持一致。這樣定義的原因是斜向前進(jìn)每次需要兩個(gè)步長(zhǎng)才能夠到達(dá)，而直向移動(dòng)僅需要一個(gè)步長(zhǎng)就可以到達(dá)。與此同時(shí)，如果在直向移動(dòng)一次后發(fā)現(xiàn)相對(duì)上一步來(lái)說(shuō)斜向移動(dòng)才是最優(yōu)路徑的話，二者最終在步長(zhǎng)上會(huì)體現(xiàn)出等同的數(shù)量，不會(huì)因?yàn)榉较騿?wèn)題而導(dǎo)致結(jié)果不準(zhǔn)確。而如果斜向移動(dòng)兩個(gè)步長(zhǎng)的方向與指向終點(diǎn)的方向相反，則判定該次移動(dòng)屬于冗余移動(dòng)，需要兩個(gè)步長(zhǎng)回到原位置后再繼續(xù)。這樣帶有矢量的方向選擇會(huì)在一定程度上減少無(wú)意義的探索運(yùn)算，對(duì)提升效率、減少運(yùn)算時(shí)間有很大幫助。

在橫軸方向上移動(dòng)的長(zhǎng)度表示為dx-nx,在縱軸方向上移動(dòng)的長(zhǎng)度表示為dy-ny，調(diào)用Matlab的abs(x)函數(shù)，用以表示移動(dòng)的絕對(duì)距離。此時(shí)算法函數(shù)可以表示為

F(n)=g(SL×cosθ)+h(abs(dx-nx)+abs(dy-ny))

(9)

3.2 有障礙節(jié)點(diǎn)模型

本文提出的改進(jìn)算法核心思路就是在碰到障礙或飛行受限區(qū)時(shí)，分別從該位置分為左右兩支緊貼障礙或受限區(qū)邊緣前進(jìn)，直到完全繞過(guò)障礙或受限區(qū)繼續(xù)前進(jìn)或者兩條分支分別按既定原則繼續(xù)前進(jìn)，最終到達(dá)目的地為止，因此稱為繞爬算法。

如圖3中所示，當(dāng)前位置在左下角，黑色區(qū)域的兩個(gè)節(jié)點(diǎn)是小尺度雷暴云團(tuán)區(qū)域，也就是障礙節(jié)點(diǎn)。飛機(jī)需要從其兩側(cè)繞飛，也就是藍(lán)色箭頭1和2代表的路線。當(dāng)右側(cè)和右上均有障礙節(jié)點(diǎn)(黑色區(qū)域)阻擋無(wú)法探索時(shí)，能夠繼續(xù)探索的節(jié)點(diǎn)相對(duì)當(dāng)前位置來(lái)說(shuō)只剩三個(gè)方向(淺藍(lán)色箭頭所指方向)，深藍(lán)色箭頭代表了緊貼障礙節(jié)點(diǎn)的繞爬節(jié)點(diǎn)，1和2分別代表從遇到節(jié)點(diǎn)開(kāi)始向左向右的兩個(gè)繞爬分支。

圖3 有障礙節(jié)點(diǎn)的前進(jìn)

如果兩個(gè)繞爬分支繞過(guò)障礙節(jié)點(diǎn)后匯合，定義為完全繞爬的情況。還有一種情況是兩個(gè)繞爬分支沒(méi)有任何在一個(gè)節(jié)點(diǎn)匯合，分別獨(dú)立繼續(xù)探索，這種定義為非完全繞爬。針對(duì)兩種不同的情況，在算法步驟中給出兩種解決辦法，保證探索過(guò)程繼續(xù)順利進(jìn)行。

4 算法設(shè)計(jì)

在進(jìn)行算法實(shí)際編程前，對(duì)一些概念和方式進(jìn)行梳理和補(bǔ)充：

A)自由節(jié)點(diǎn)：在整個(gè)路徑規(guī)劃過(guò)程中，從當(dāng)前位置向前探索的、不受障礙覆蓋的地圖柵格被標(biāo)記為自由節(jié)點(diǎn)，起始探索節(jié)點(diǎn)就是最初的自由節(jié)點(diǎn)，同時(shí)也是原點(diǎn)。

這一概念相當(dāng)于A*算法中的開(kāi)放節(jié)點(diǎn)。相對(duì)而言，不是自由節(jié)點(diǎn)的稱之為障礙節(jié)點(diǎn)或邊界節(jié)點(diǎn)，也就是本文所討論的被強(qiáng)對(duì)流天氣覆蓋的需要飛機(jī)繞飛的區(qū)域(下文將障礙節(jié)點(diǎn)和邊界節(jié)點(diǎn)視為同一種節(jié)點(diǎn)不再詳細(xì)區(qū)分)；

B)自由探索：物體一直朝向終點(diǎn)前進(jìn)的情況下，如果下一步至少存在一個(gè)柵格不是障礙節(jié)點(diǎn)，也就是可以從當(dāng)前位置繼續(xù)向前能夠正常進(jìn)入下一個(gè)自由節(jié)點(diǎn)探索，這個(gè)過(guò)程稱之為自由探索；該過(guò)程等價(jià)于基于性能的導(dǎo)航方式下的實(shí)際飛行過(guò)程。

C)繞爬節(jié)點(diǎn)：在物體朝向終點(diǎn)前進(jìn)的情況下，如果當(dāng)前位置的前進(jìn)方向上下一個(gè)柵格是障礙節(jié)點(diǎn)，則嘗試?yán)@過(guò)障礙節(jié)點(diǎn)，遵循先右后左原則繼續(xù)探索，繞爬過(guò)程中所有自由節(jié)點(diǎn)均標(biāo)記為繞爬節(jié)點(diǎn)，直到繞爬過(guò)程結(jié)束。在實(shí)際飛行過(guò)程中如果前方航線上存在雷暴云團(tuán)，分別從左右兩側(cè)對(duì)路徑進(jìn)行探索再?zèng)Q定繞飛方向。

4.1 算法技術(shù)路線圖

算法從起點(diǎn)開(kāi)始，先將起點(diǎn)柵格作為當(dāng)前節(jié)點(diǎn)對(duì)下一前進(jìn)方向的柵格進(jìn)行判斷：如果是障礙節(jié)點(diǎn)，選擇否。然后以障礙節(jié)點(diǎn)為邊界，從當(dāng)前節(jié)點(diǎn)位置分出左右分支繼續(xù)運(yùn)行，原則為先右后左原則，也就是將向左的分支先掛起到程序后臺(tái)，首先運(yùn)行向右分支的判斷，用循環(huán)語(yǔ)句重復(fù)對(duì)下一前進(jìn)方向柵格的判斷過(guò)程，直到向右分支恢復(fù)為自由節(jié)點(diǎn)。然后運(yùn)行向左分支的判斷，仍然使用循環(huán)語(yǔ)句進(jìn)行判斷，直到向左分支也恢復(fù)為自由節(jié)點(diǎn)或完成完全繞爬過(guò)程。若兩個(gè)分支匯合，則完全繞爬過(guò)程結(jié)束，重新重復(fù)整個(gè)過(guò)程，直到到達(dá)終點(diǎn)；若兩個(gè)分支未匯合，則兩個(gè)分支分別繼續(xù)探索，重復(fù)整個(gè)運(yùn)算過(guò)程，直到到達(dá)邊界或終點(diǎn)結(jié)束。

圖4 技術(shù)路線

算法的具體步驟如下：

1)開(kāi)始，將起點(diǎn)標(biāo)記為最初的自由節(jié)點(diǎn)，從當(dāng)前位置出發(fā)向終點(diǎn)進(jìn)行探索；

2)在向終點(diǎn)探索的過(guò)程中判斷下一格柵格是否為自由節(jié)點(diǎn)，

2.1)下一柵格是自由節(jié)點(diǎn)，正常前進(jìn)，步長(zhǎng)為一步，將該點(diǎn)標(biāo)記為自由節(jié)點(diǎn)，繼續(xù)；

2.2)下一柵格不是自由節(jié)點(diǎn)，以下一柵格為障礙節(jié)點(diǎn)，從該點(diǎn)向左右分出兩個(gè)繞爬分支，將兩個(gè)分支的起始探索節(jié)點(diǎn)標(biāo)記為自由節(jié)點(diǎn)，再次進(jìn)行判斷，分別嘗試?yán)@過(guò)障礙節(jié)點(diǎn)。

2.2.1)若可以繼續(xù)探索，將這兩個(gè)起始探索節(jié)點(diǎn)標(biāo)記為兩個(gè)繞爬的探索節(jié)點(diǎn)；

2.2.2)若不能繼續(xù)探索，返回上一自由節(jié)點(diǎn)；

2.3)若某一繞爬探索節(jié)點(diǎn)出現(xiàn)五方向前進(jìn)均不是自由節(jié)點(diǎn)的情況，返回繞爬探索節(jié)點(diǎn)的上一個(gè)自由節(jié)點(diǎn)并暫停，另一繞爬分支繼續(xù)探索，若該分支也出現(xiàn)同樣情況，則繼續(xù)上一自由節(jié)點(diǎn)的探索并將本次探索節(jié)點(diǎn)全部標(biāo)記為障礙節(jié)點(diǎn)。

3)兩個(gè)繞爬分支繞過(guò)障礙后可能出現(xiàn)交匯的情況，稱為完全繞爬成功，繞過(guò)障礙后，選擇探索節(jié)點(diǎn)更少的分支為合理路徑，從匯合點(diǎn)又成為自由節(jié)點(diǎn)繼續(xù)向前；

4)判斷兩個(gè)繞爬分支的長(zhǎng)度，當(dāng)一個(gè)分支A先于另一分支B遇到下一個(gè)障礙時(shí)，A分支分為A1分支和A2分支繼續(xù)尋路，B分支繼續(xù)尋路，直到分支匯合或再遇到障礙繼續(xù)分支，直到某分支到達(dá)目標(biāo)，同時(shí)停止所有分支尋路；

5)自由探索的同時(shí)也需要判斷下一柵格是否為終點(diǎn)，若是，則尋路成功，結(jié)束探索過(guò)程，選擇探索過(guò)的節(jié)點(diǎn)構(gòu)成完整路徑；若不是，返回步驟2，重復(fù)步驟2-5，直到條件“是”達(dá)成；

6)到達(dá)目標(biāo)各自后檢查路徑能否繼續(xù)優(yōu)化：在每一次遇到的障礙節(jié)點(diǎn)的分支處與下一個(gè)分支處重復(fù)尋路過(guò)程，若移動(dòng)更短，則用新的路徑替代原有路徑，若相同，則停止。

4.2 算法仿真

使用Windows10系統(tǒng)的C++語(yǔ)言對(duì)繞爬算法按步驟編寫語(yǔ)句并進(jìn)行仿真，如圖5所示，算法運(yùn)行的空間環(huán)境邊界設(shè)置為32×32，其有效空間環(huán)境為30×30的正方形區(qū)域。選取起點(diǎn)坐標(biāo)(3，3)，用左下角綠色方塊表示；終點(diǎn)坐標(biāo)(29，22)，用右上角紅色方塊表示。左側(cè)及下方黑色方塊代表空間環(huán)境的左下邊界，在整個(gè)空間環(huán)境中設(shè)置7處障礙區(qū)域，用來(lái)代表飛機(jī)在飛行過(guò)程中可能遇到的雷暴或其它強(qiáng)對(duì)流天氣障礙。如圖5中黑色長(zhǎng)條方塊區(qū)域所示。對(duì)算法運(yùn)行結(jié)果計(jì)數(shù)，分別表示當(dāng)前分支的路徑長(zhǎng)度，黃色分支被標(biāo)記為最優(yōu)路徑作為運(yùn)算結(jié)果。

為體現(xiàn)繞爬算法的有效性，另外使用同一計(jì)算機(jī)下的Matlab軟件對(duì)相同條件下的A*算法進(jìn)行仿真，如圖6所示。其中紅色點(diǎn)代表空間環(huán)境的邊界和障礙區(qū)域，綠色代表探索過(guò)但是并不是最優(yōu)路徑的節(jié)點(diǎn)。

對(duì)比兩種算法所運(yùn)行的過(guò)程和結(jié)果如下。

圖5 繞爬算法運(yùn)行結(jié)果

圖6 A*算法運(yùn)行結(jié)果

兩種算法的步長(zhǎng)和可探索空間總節(jié)點(diǎn)如表1所示。

表1 算法結(jié)果對(duì)比

5 總結(jié)

在給定仿真環(huán)境中，繞爬算法和A*算法的仿真結(jié)果對(duì)比可以很明顯的看出：1.A*算法空間環(huán)境共900格節(jié)點(diǎn)，除去障礙節(jié)點(diǎn)71格，完成路徑規(guī)劃共需探索808格節(jié)點(diǎn)；2.繞爬算法空間環(huán)境及障礙節(jié)點(diǎn)數(shù)同上，但完成路徑規(guī)劃僅需探索175格節(jié)點(diǎn)。3.雖然算法的仿真環(huán)境相較于實(shí)際情況可能復(fù)雜度更高，但算法效率的高下十分清楚，并且從圖中可以看出繞爬算法對(duì)障礙具有良好的貼邊繞障能力，對(duì)航路危險(xiǎn)天氣繞飛有實(shí)際意義。4.隨著不同運(yùn)行環(huán)境下仿真次數(shù)的增加，可以得出的結(jié)論為，環(huán)境空間越大，繞爬算法相對(duì)于A*算法的效率優(yōu)勢(shì)就越明顯；障礙物越多，雖然A*算法自身效果會(huì)越來(lái)越好，但是其效率仍然遠(yuǎn)遠(yuǎn)不及繞爬算法。

近年來(lái)許多對(duì)A*算法的改進(jìn)都停留在減少全向搜索節(jié)點(diǎn)數(shù)量方面，但是在一個(gè)固定的環(huán)境空間中，對(duì)所有柵格進(jìn)行獨(dú)立探索是十分浪費(fèi)的，隨著環(huán)境空間的增大，運(yùn)算次數(shù)會(huì)較大幅度增加。本文針對(duì)這一點(diǎn)先對(duì)底層結(jié)構(gòu)中的節(jié)點(diǎn)篩選，判斷柵格是否可以被選作當(dāng)前節(jié)點(diǎn)的下一步，然后再?gòu)倪@些節(jié)點(diǎn)判斷有哪些是應(yīng)該被選擇的路徑規(guī)劃節(jié)點(diǎn)。這樣大大減少了需要進(jìn)行判別運(yùn)算的節(jié)點(diǎn)，提高算法效率。但是繞爬算法仍然存在一些問(wèn)題：比如完全繞爬與bresenham算法在優(yōu)先級(jí)上的順序會(huì)影響路徑規(guī)劃的結(jié)果，兩者的優(yōu)先級(jí)應(yīng)根據(jù)不同情況實(shí)際判斷，未來(lái)深入研究的重點(diǎn)在于如何對(duì)運(yùn)算結(jié)果分析并優(yōu)化。