王修遠(yuǎn)，孫敏，李修賢，周航，趙仁亮

1.北京大學(xué) 遙感與地理信息系統(tǒng)研究所,北京 100871;

2.冀北中原巖土工程有限公司,廊坊 065001

1 引言

在地理信息科學(xué)、計(jì)算機(jī)科學(xué)等領(lǐng)域中，路徑規(guī)劃的研究一直有著非常重要的理論和應(yīng)用價(jià)值。在傳統(tǒng)的路徑規(guī)劃與導(dǎo)航方面相關(guān)的應(yīng)用相當(dāng)成熟，如車輛導(dǎo)航系統(tǒng)，當(dāng)周邊路網(wǎng)環(huán)境已知時(shí)，可以快速地規(guī)劃出從起始點(diǎn)至目標(biāo)點(diǎn)的比較合理的路線。但是在城市以外的許多野外環(huán)境，由于缺乏道路，較難使用現(xiàn)有的算法進(jìn)行路徑規(guī)劃。例如在應(yīng)急救援、軍事行動(dòng)等活動(dòng)中，工作場(chǎng)景常常是地形復(fù)雜多樣且無人工道路的野外環(huán)境。在這些環(huán)境中的路徑規(guī)劃任務(wù)并不像傳統(tǒng)的路徑規(guī)劃任務(wù)一樣有現(xiàn)成的道路信息可以使用，此時(shí)傳統(tǒng)的路徑規(guī)劃方法難以發(fā)揮作用，故需要使用新的策略進(jìn)行路徑規(guī)劃。

在沒有矢量路網(wǎng)的情況下進(jìn)行路徑規(guī)劃，主要的受制因素是地面車輛對(duì)周邊環(huán)境有限的感知能力，導(dǎo)致其無法在更大的范圍了解周邊地表環(huán)境信息。為了彌補(bǔ)地面車輛視野小的缺陷，可以使用空中的觀測(cè)平臺(tái)（如無人機(jī)，UAV）作為輔助手段擴(kuò)充視野范圍，獲取必要的環(huán)境信息，這種地面端與無人機(jī)平臺(tái)協(xié)作完成任務(wù)的方式即為稱為空地協(xié)同系統(tǒng)。

空地協(xié)同系統(tǒng)近年來在目標(biāo)檢測(cè)與跟蹤以及路徑規(guī)劃等領(lǐng)域有著廣泛的應(yīng)用。針對(duì)地面端行進(jìn)路徑規(guī)劃需求，無人機(jī)通常被用來獲取周邊地形信息。如：Choi 等（2009），Choi 和Lee（2012）設(shè)計(jì)的系統(tǒng)中，由無人機(jī)獲取的影像快速生成高分辨率的DEM、正射影像等空間信息，為地面行動(dòng)提供詳細(xì)的地圖信息，但其工作僅限于地面信息的快速獲取與處理，并沒有進(jìn)行路徑分析，無法直接引導(dǎo)地面車輛通行。Li等（2016）利用UAV獲取地面影像，并提出了一種基于柵格數(shù)據(jù)的混合路徑規(guī)劃算法為地面無人車（UGV）提供可通行路徑。但其實(shí)驗(yàn)僅在室內(nèi)進(jìn)行了仿真模擬，相關(guān)技術(shù)手段在野外真實(shí)場(chǎng)景中的有效性仍有待驗(yàn)證。席阿行等（2019）提出了一種根據(jù)UAV 獲取的信息，UGV 使用A*算法進(jìn)行全局路徑規(guī)劃的方法，并進(jìn)行了典型搜救場(chǎng)景的仿真驗(yàn)證，但其實(shí)驗(yàn)場(chǎng)景為人工搭建的比較簡(jiǎn)單的環(huán)境，不能滿足野外應(yīng)急搜救場(chǎng)景的需要。Delmerico 等（2017）對(duì)UAV 實(shí)時(shí)獲取到的影像進(jìn)行了分類，同時(shí)提取地表高程信息用來輔助分析地面的通行性，并使用D*算法為UGV 提供路徑規(guī)劃服務(wù)，但其研究實(shí)驗(yàn)場(chǎng)景較小，地物類型也比較簡(jiǎn)單，且D*算法搜索效率較低，故在野外應(yīng)急救援中的應(yīng)用比較有限。

以上研究雖然都使用UAV 獲取地表信息，且均使用路徑規(guī)劃算法為地面車輛提供路徑指引，但實(shí)驗(yàn)均未能模擬野外真實(shí)場(chǎng)景，對(duì)于野外復(fù)雜環(huán)境下的應(yīng)急救援活動(dòng)的適用性有待進(jìn)一步完善。

針對(duì)以上問題，黎曉東（2017），李修賢 等（2019）提出一種空地協(xié)同的方法：首先使用UAV獲取研究區(qū)域的遙感影像，通過圖像校正拼接、空中三角測(cè)量、遙感影像分類等過程，將遙感影像轉(zhuǎn)化為可以用于路徑規(guī)劃的影像地圖。再通過建立地表可通行性模型、構(gòu)建恰當(dāng)?shù)耐ㄐ写鷥r(jià)計(jì)算函數(shù)，使用合適的路徑規(guī)劃算法在影像地圖上搜索從起點(diǎn)到目標(biāo)結(jié)點(diǎn)之間具備最優(yōu)可通行性的路徑，實(shí)現(xiàn)了UAV 與UGV 的空地協(xié)同。其研究成果也為本研究中野外應(yīng)急救援路徑規(guī)劃問題提供了解決思路，但其所用的傳統(tǒng)A*算法存在一定的局限性，并不能完全滿足為UGV 快速提供安全且具可通行路徑的需求。

2 研究現(xiàn)狀

針對(duì)A*算法的改進(jìn)，國(guó)際上有一些研究，其中代表性的工作有：Harabor和Grastien（2011）針對(duì)A*算法逐像元搜索效率較低的問題，提出了JPS（Jump Point Search）算法，該算法通過“跳躍式”搜索大幅減少了算法搜索的結(jié)點(diǎn)個(gè)數(shù)，壓縮了搜索空間，提升了運(yùn)算效率，但是該算法僅適用于代價(jià)均勻的柵格地圖，并不適用于通行代價(jià)變化復(fù)雜的越野地形。Yap 等（2011）提出了Block A*算法，該算法將m×n單元內(nèi)所有的可能存在的障礙分布情況及對(duì)應(yīng)的可通行的路徑預(yù)先存儲(chǔ)到一個(gè)小型數(shù)據(jù)庫(kù)中，并以m×n方塊作為搜索的基本單元，從而大大提高了搜索速度，但是對(duì)于現(xiàn)實(shí)中較為復(fù)雜的地形，如果使用該算法窮舉單元內(nèi)部的可通行路徑會(huì)消耗極大的計(jì)算和存儲(chǔ)資源。

國(guó)內(nèi)近些年也有一些代表性的研究，如：吳天羿等（2013）提出了一種改進(jìn)的A*算法，分別針對(duì)特定車輛估計(jì)出了不同的地表類型的粗糙度，并以此粗糙度與格網(wǎng)間距離之比值作為A*算法的代價(jià)函數(shù)。其所提算法使用通行禁忌表以排除對(duì)不可通行單元的搜索，但其實(shí)驗(yàn)僅限于200×200格網(wǎng)的模擬數(shù)據(jù)，一方面實(shí)驗(yàn)數(shù)據(jù)過少，另一方面未能給出優(yōu)化前后算法的對(duì)比。

范林林（2017）提出了利用六角格剖分地表，并基于六角格單元進(jìn)行路徑規(guī)劃的算法，但為方便表達(dá)，在所用六角格單元中，將原始地表類型綜合為單一類型，同時(shí)六角格內(nèi)高程信息由插值得到，顯然算法主要針對(duì)的是較小比例尺的地形信息，其實(shí)驗(yàn)使用1∶5 萬地形圖，由于忽略了微地貌形態(tài)，故所搜索路徑很難用于實(shí)際應(yīng)急環(huán)境。

趙德群等（2017）針對(duì)三維路徑搜索問題，提出將地表高程信息引入A*算法的代價(jià)函數(shù)，以改進(jìn)傳統(tǒng)二維空間的A*路徑規(guī)劃算法，但其研究未考慮地表植被與土壤等信息，故其搜索路徑的可靠性不足。

孫玉澤（2020）結(jié)合了DEM 與地表分類信息用于路徑搜索，但未給出完整的通行代價(jià)評(píng)估函數(shù)，僅將DEM 坡度用于判斷路徑是否通行，地物類型用于計(jì)算通行速度。其比較研究表明，改進(jìn)A*算法較改進(jìn)蟻群算法更為穩(wěn)定。

以上這些研究工作，除了D*算法效率較低外，國(guó)內(nèi)這些工作的共通特點(diǎn)，是未使用真實(shí)的高分辨率影像數(shù)據(jù)，也未使用高分地形數(shù)據(jù)，未能融合考慮地形坡度、地表植被以及地表土壤類型信息對(duì)通行性的影響。盡管對(duì)A*算法進(jìn)行了優(yōu)化，但優(yōu)化前后效率究竟提高了多少，未能給出充分的說明。

在野外應(yīng)急救援應(yīng)用場(chǎng)景中，為了獲取現(xiàn)勢(shì)性很好的周邊環(huán)境信息，需要由UAV 為地面車輛拍攝周邊區(qū)域的高分影像，經(jīng)一系列處理后，為越野車輛快速規(guī)劃一條安全、且具最優(yōu)通行性的路線。但現(xiàn)有研究成果并不適于空地協(xié)同環(huán)境條件下的地表路徑規(guī)劃，概括而言，主要原因如下：（1）普遍使用了衛(wèi)星影像，分辨率較低，沒有顧及影響地表通行性的微地貌因素；（2）目前使用的搜索算法，就戶外應(yīng)急或遠(yuǎn)程在線使用的情景而言，計(jì)算的時(shí)效性仍有待改進(jìn)；（3）搜索算法中代價(jià)函數(shù)的構(gòu)造過于簡(jiǎn)單，對(duì)地表坡度、土壤及植被類型信息對(duì)通行性的綜合影響，未能深入分析從而使搜索結(jié)果的實(shí)用性和可靠性不足；（4）現(xiàn)有算法，無論是基于格網(wǎng)（或六角格）還是基于像元，其本質(zhì)上與基于像元的算法是一致的，均未考慮格網(wǎng)內(nèi)部信息的不均一性，搜索結(jié)果路徑是一條逐格網(wǎng)單元或像元連接且以其為寬度的路徑，與實(shí)際所用交通工具所需的通行路徑無關(guān)。然而在現(xiàn)實(shí)環(huán)境中，如不顧及實(shí)際交通工具的相關(guān)參數(shù)，則所搜索的路徑不一定具有真正可靠的通行性。

為了解決上述問題，本文提出了一種基于格網(wǎng)單元的改進(jìn)A*算法，該算法綜合考慮地物類型和高程起伏對(duì)車輛通行性的影響以構(gòu)建可通行性代價(jià)函數(shù)；同時(shí)顧及高分辨率影像與實(shí)際通行路徑之間的尺度關(guān)系，綜合利用格網(wǎng)特征像元之間的拓?fù)潢P(guān)系實(shí)現(xiàn)路徑搜索，極大地壓縮了搜索空間，提升了運(yùn)算效率，本文將該算法命名為Grid A*算法。

3 Grid A*算法基本思想

前文提及，在野外無具體道路的條件下，我們需要搜索出一條具備最佳通行性的、可供車輛行駛的路徑。如研究現(xiàn)狀所評(píng)述，在野外地形環(huán)境較為復(fù)雜的應(yīng)用場(chǎng)景中，現(xiàn)有方法機(jī)械地以像元為基本計(jì)算單元，或進(jìn)行了單元?jiǎng)澐郑ㄈ缌歉瘢?，但未考慮實(shí)際地面通行工具的路徑尺度，故無法有效地針對(duì)空地協(xié)同系統(tǒng)的應(yīng)用需求，快速地規(guī)劃出合理可行的路徑。為此，本研究構(gòu)建了一種基于原始像元信息、以地物類型和地形起伏為核心因子的通行性計(jì)算代價(jià)函數(shù)，同時(shí)結(jié)合實(shí)際交通工具的通行路徑需求，考慮影像空間分辨率與實(shí)際通行路徑寬度之間的尺度關(guān)系，以一定尺寸的格網(wǎng)單元作為路徑搜索的基本單元，使算法對(duì)路徑的評(píng)估結(jié)果以及搜索結(jié)果更符合實(shí)際車輛的行駛條件。

下面分別對(duì)傳統(tǒng)A*算法原理、格網(wǎng)單元的劃分、可通行性評(píng)估模型以及Grid A*算法計(jì)算流程等進(jìn)行詳細(xì)闡述。

3.1 傳統(tǒng)A*算法原理

傳統(tǒng)A*算法是一種啟發(fā)式的路徑規(guī)劃算法，結(jié)合了Dijkstra 算法和最佳優(yōu)先搜索算法BFS（Best First Search）的優(yōu)點(diǎn)，是在路徑規(guī)劃領(lǐng)域應(yīng)用最廣泛的算法之一。

傳統(tǒng)A*算法的代價(jià)函數(shù)f(n)表達(dá)式為

式中，g(n)表示從起點(diǎn)到結(jié)點(diǎn)n的已知通行代價(jià)，h(n)表示從結(jié)點(diǎn)n到目標(biāo)結(jié)點(diǎn)預(yù)估代價(jià)。

相鄰結(jié)點(diǎn)i、j之間的通行代價(jià)可以表示為

式中，Di，j為兩點(diǎn)的之間的距離，ri，j(Ts，X)為兩點(diǎn)間的單位長(zhǎng)度的通行阻力，則對(duì)于某條路徑上的結(jié)點(diǎn)n而言，從起點(diǎn)到該結(jié)點(diǎn)的通行代價(jià)g(n)可以定義為

A*算法定義了兩張表來存儲(chǔ)遍歷過的結(jié)點(diǎn)，式中，OPEN 表中存儲(chǔ)具備可通行性且尚未搜索的像元，CLOSED 表中存儲(chǔ)無法通行或已搜索過的像元。

傳統(tǒng)A*算法首先對(duì)起點(diǎn)的鄰域進(jìn)行遍歷，并將所獲結(jié)點(diǎn)都加入到OPEN 表中，此后每一次計(jì)算都會(huì)對(duì)OPEN 表中代價(jià)函數(shù)f(n)值最小的結(jié)點(diǎn)的鄰域進(jìn)行搜索，所獲結(jié)點(diǎn)均加入到OPEN 表中，并將該結(jié)點(diǎn)移入CLOSED表，直到搜索到目標(biāo)結(jié)點(diǎn)。最后，A*算法通過回溯結(jié)點(diǎn)之間的鄰域關(guān)系，生成一條從起點(diǎn)至目標(biāo)結(jié)點(diǎn)的路徑。

3.2 格網(wǎng)單元及其特征選取

傳統(tǒng)A*算法普遍適用于經(jīng)過通行阻力賦值的柵格地圖，但是該算法運(yùn)行時(shí)間隨著搜索范圍的增大迅速增長(zhǎng)，所以當(dāng)研究區(qū)域較大或圖像分辨率較高時(shí)，傳統(tǒng)A*算法無法實(shí)現(xiàn)快速搜索。

本研究為了提高算法效率，采用格網(wǎng)劃分、分塊處理的方式，利用格網(wǎng)單元內(nèi)部地表屬性的連通分布特點(diǎn)，在格網(wǎng)單元邊緣選取特征像元，用于路徑快速搜索，實(shí)現(xiàn)了壓縮搜索空間、提升運(yùn)算效率，但又不丟失過多格網(wǎng)單元內(nèi)部細(xì)節(jié)信息的效果。

對(duì)于空地協(xié)同過程中所采用無人機(jī)遙感影像而言，越野車輛的實(shí)際尺寸是影像空間分辨率的多倍以上，所以路徑規(guī)劃過程中需要考慮車體覆蓋范圍內(nèi)的所有像元對(duì)通行造成的影響。為此，本文顧及車體尺寸與影像分辨率之間的尺度關(guān)系，以與車體尺寸相近的格網(wǎng)單元對(duì)無人機(jī)影像進(jìn)行劃分，并以格網(wǎng)單元作為基本單位進(jìn)行通行性路徑分析計(jì)算。

影響通行性的主要兩方面因素中，地形起伏信息（即坡度）的一致性連續(xù)較差，而地物分類信息的一致性連續(xù)較強(qiáng)；同時(shí)地形坡度的突變較少，而地物類型的突變較多。尤其在不同地物之間存在明確的界限時(shí)，相鄰像元之間可通行性的主要差別更多地體現(xiàn)在地物類型的變化方面，因此，本文以地物分類影像作為格網(wǎng)單元的劃分的基礎(chǔ)。

格網(wǎng)單元的尺度大小選擇n×n像素，即把整個(gè)影像以n×n的格網(wǎng)單元進(jìn)行劃分，如圖1 所示為影像被劃分為格網(wǎng)的局部示意圖。格網(wǎng)單元大小的選擇，以通行工具的尺度要求為參考，同時(shí)一個(gè)格網(wǎng)單元內(nèi)部盡量不包含、或少包含獨(dú)立地物分類圖斑。

圖1 格網(wǎng)單元?jiǎng)澐质疽鈭DFig.1 A classified image divided into grid cells

如圖2（a）為格網(wǎng)單元尺寸為9（即n=9）時(shí)，格網(wǎng)單元的劃分方式，黑色線條所圍區(qū)域是一個(gè)9×9 大小的格網(wǎng)單元。該格網(wǎng)單元邊緣像元中，1、3、5、7 為角像元，其余為邊像元。相鄰的格網(wǎng)單元之間共用邊、角像元，整個(gè)研究區(qū)域從而被邊緣相互重疊的格網(wǎng)單元所覆蓋。利用相鄰格網(wǎng)之間共用邊界像元的特點(diǎn)，路徑搜索時(shí)便可以以邊界像元連接，實(shí)現(xiàn)相鄰格網(wǎng)之間的路徑連續(xù)搜索。

圖2 格網(wǎng)單元?jiǎng)澐峙c特征像元選取Fig.2 The division of grid cell and the selection of feature points

格網(wǎng)的邊界像元的分布有著明顯的規(guī)律性，為了方便描述格網(wǎng)的可通行性，本研究引入“特征像元”的概念。如圖2（b）所示，邊界像元中標(biāo)記為深色的像元，是格網(wǎng)邊緣某一地物類型的連續(xù)像元中的中間點(diǎn)，由于地物分布的連續(xù)性特點(diǎn)，格網(wǎng)邊緣出現(xiàn)的地物類型，一般在格網(wǎng)單元內(nèi)部也會(huì)出現(xiàn)，故將其選為“特征像元”，指其代表了格網(wǎng)在該邊緣方向上所具有的地表屬性。如圖2（b）所示，格網(wǎng)內(nèi)部地物屬性有3類，邊緣的特征像元即能代表格網(wǎng)內(nèi)部的地物類型，由于每一條格網(wǎng)邊緣至少存在一個(gè)特征像元，這些特征像元在一定程度上表達(dá)了格網(wǎng)單元中地物分布的連通性。如果存在圖2（c）中情況，當(dāng)格網(wǎng)內(nèi)部存在獨(dú)立地物分類圖斑，即某種島狀地物完全包含在格網(wǎng)單元內(nèi)部時(shí)，這類斑塊的出現(xiàn)會(huì)給特征像元的選取、格網(wǎng)單元內(nèi)部的可通行性評(píng)估增加困難，Grid A*算法可通過通行阻力平均對(duì)獨(dú)立圖斑對(duì)車輛行進(jìn)造成的影響進(jìn)行評(píng)估，本文在后續(xù)實(shí)驗(yàn)部分給出了具體解決方法。

特征像元的選取，主要是考慮了地表覆蓋類型這一個(gè)影響通行性的重要因子。由于不同地物屬性的像元意味著不同的通行性，所以對(duì)于穿行某一特定格網(wǎng)單元的路徑而言，最優(yōu)路徑不會(huì)沿地物間分界線像元經(jīng)過。在格網(wǎng)單元邊緣上，本算法選擇同類型連續(xù)像元的中間點(diǎn)作為特征像元，如果當(dāng)前格網(wǎng)中，某種地表類型具有最優(yōu)的通達(dá)性，則最優(yōu)路徑應(yīng)盡可能完全位于該類型的地表范圍中；如果在格網(wǎng)邊緣上任意選擇像元，則搜索選路徑可能同時(shí)覆蓋兩種或多種地表類型，從而無法保證最優(yōu)的通達(dá)性。對(duì)于任意選擇像元的問題，在4.4節(jié)分析與討論部分將作進(jìn)一步闡述。

此外，人們?cè)诂F(xiàn)實(shí)環(huán)境中在遇到均勻、無變化地表環(huán)境時(shí)，行走或駕車的方向隨意性較大，所以在Grid A*算法中，我們考慮選取連續(xù)同類像元的中間像元作為特征用于計(jì)算，以保證所選路徑在同類地表區(qū)域的中間，從而在優(yōu)化計(jì)算的同時(shí)，兼顧了路徑搜索的可靠性。

路徑搜索過程中，Grid A*算法通過以特征像元為結(jié)點(diǎn)建立拓?fù)潢P(guān)系的方式，縮短對(duì)格網(wǎng)單元遍歷所需時(shí)間的同時(shí)，實(shí)現(xiàn)了路徑的快速搜索。

3.3 格網(wǎng)單元及其特征選取

（1）影響通行性的主要因子賦值。合理的地表通行性代價(jià)函數(shù)是搜索到高可靠性通行路徑的重要基礎(chǔ)。在戶外環(huán)境中，影響通行性的主要因子是地表的地物類型和地形坡度。本文沿用李修賢等（2019）的研究方法，以越野車為例，依據(jù)其在不同地表環(huán)境中的行駛特點(diǎn)，給出了幾類代表性地物與3 個(gè)典型坡度值對(duì)應(yīng)條件下的行駛速度。如表1所示，車輛的最大通行坡度，在不同的地表?xiàng)l件下，對(duì)其取不同值；平地即0°坡度一般而言具有最大通行速度，在確保野外行駛安全的情況下，下坡也應(yīng)適當(dāng)減慢速度，為簡(jiǎn)便起見，取與上坡同樣的速度；據(jù)一般性經(jīng)驗(yàn)，認(rèn)為10°屬于坡度值出現(xiàn)頻率最高的中間值，故取其為一個(gè)典型坡度值。

表1 地物種類與不同坡度對(duì)應(yīng)的通行速度與通行阻力Table 1 Running speed and passability cost based on various surface type and slopes

從地物類型而言，野外道路的通行性最佳，故通行阻力最小。設(shè)S0=30 km/h 為其基準(zhǔn)通行速度，對(duì)應(yīng)的通行阻力值r0=1.0。其他地物類型的通行速度，以平地作為參照，結(jié)合經(jīng)驗(yàn)性估計(jì)給出。例如，考慮到戈壁地面主要以小砂石為主，地面較為穩(wěn)固，通行速度也較快；鹽堿地則稍弱于戈壁；低矮植物有一定的固沙作用，故也有一定的可通行性；而沙地主要是由細(xì)沙構(gòu)成，質(zhì)地松軟，不利于通行；水體則完全不能通行，故其通行阻力取無窮大。

由文獻(xiàn)綜述可以看出，現(xiàn)有研究對(duì)通行代價(jià)函數(shù)的構(gòu)建考慮普遍較為簡(jiǎn)單。本文研究依據(jù)一般性經(jīng)驗(yàn)，認(rèn)為車輛通行速度與地物及坡度之間的具有二次非線性函數(shù)關(guān)系，并非一般文獻(xiàn)中給出的簡(jiǎn)單的線性關(guān)系，故在表1所給三點(diǎn)值的基礎(chǔ)上，我們采用函數(shù)擬合法，得到對(duì)應(yīng)不同地物類型，在任意坡度條件下的通行速度表達(dá)式與通行阻力表達(dá)式，如式（4）、（5）所示。

不同地表地物和坡度環(huán)境下用于計(jì)算車輛通行速度的表達(dá)式S(Ts，X)和通行阻力表達(dá)式r(Ts，X)如下：

式中，Ts代表不同地物類型，X為表達(dá)坡度的角度值，tanX即為以百分比表示的坡度值。圖3 給出了5種地物對(duì)應(yīng)的二次曲線圖，橫軸為百分比表達(dá)的坡度值。根據(jù)以上函數(shù)關(guān)系，我們可以計(jì)算出越野車輛在不同地物類型的地表、任意坡度時(shí)的通行速度，提高了通行代價(jià)估計(jì)的準(zhǔn)確性。

圖3 不同地物種類的坡度與速度曲線Fig.3 The speed graph based on various surface type and slopes

（2）基于格網(wǎng)單元的通行性評(píng)估模型。如圖4所示，我們使用邊緣相互重疊的格網(wǎng)單元分割了整個(gè)研究區(qū)域影像（圖中灰色線框表達(dá)了對(duì)部分分類影像的分割結(jié)果），并根據(jù)地物分類特點(diǎn)，基于3.2 節(jié)所述方法，在格網(wǎng)邊緣上選取了特征像元（圖中淺黃色像元）。

圖4 特征像元的選取示意圖Fig.4 Feature points in a classified image

使用特征像元替代了格網(wǎng)單元用于路徑搜索時(shí)必須考慮格網(wǎng)單元內(nèi)部的像元信息。如圖5（a）展示了從S點(diǎn)到G點(diǎn)逐像元搜索得到的路徑，圖5（b）為基于格網(wǎng)單元的特征像元搜索所得到的路徑，從像元級(jí)別而言，與圖5（a）結(jié)果相比，該結(jié)果并不是最佳路徑。然而，因?yàn)檐囕v實(shí)際通行寬度遠(yuǎn)大于一個(gè)像元，所以圖5（a）中的路徑未必具有最高的可靠性，為此，我們需要綜合考慮實(shí)際路寬的范圍內(nèi)其他單元的通行信息。

圖5 格網(wǎng)單元的通行性Fig.5 The possibility inside a gird cell

如圖5（c）所示，由特征像元A 搜索到特征像元B基于格網(wǎng)單元進(jìn)行路徑規(guī)劃時(shí)，計(jì)算通行代價(jià)時(shí)需要考慮通行路寬的需要，在A、B 兩個(gè)特征像元周邊建立如圖所示的平行四邊形“通行區(qū)域”。設(shè)該平行四邊形的高為a個(gè)像元，底邊長(zhǎng)為b個(gè)像元，我們用該區(qū)域內(nèi)所有像元的通行阻力均值，來概括總的通行能力。為了提高可通行性的判斷條件，我們?cè)谥鹦谢蛑鹆袙呙柘裨獣r(shí)，凡是遇到連續(xù)兩行或兩列像元及以上像元均不可通行的情況，該整個(gè)區(qū)域的通行阻力設(shè)為極大值。

Grid A*算法以特征像元替代格網(wǎng)單元的通行性，所以本研究對(duì)傳統(tǒng)A*算法代價(jià)式（2）（3）加以改進(jìn)。其具體的通行代價(jià)計(jì)算函數(shù)如下：

在Grid A*算法中，兩個(gè)特征像元i、j一般不是相鄰的，引入一個(gè)參數(shù)αi，j對(duì)特征像元i、j周邊的平行四邊形“通行區(qū)域”內(nèi)的可通行性進(jìn)行評(píng)估：

式中，a、b是“通行區(qū)域”的高與底邊長(zhǎng)，Ts為地物類型，X為坡度，r(Ts，X)為根據(jù)式（4）（5）計(jì)算得出的通行阻力值。則兩特征像元間通行代價(jià)計(jì)算方式為

對(duì)于某條路徑上的結(jié)點(diǎn)n而言，從起點(diǎn)到該結(jié)點(diǎn)的通行代價(jià)定義為

與傳統(tǒng)A*算法相同，h(n)表示從結(jié)點(diǎn)n到目標(biāo)結(jié)點(diǎn)預(yù)估代價(jià)。

3.4 Grid A*算法計(jì)算流程

傳統(tǒng)A*算法采用4鄰域或8鄰域逐像元搜索策略，在本文提出的Grid A*算法為了提高路徑的連續(xù)性，在格網(wǎng)單元層面沿用了A*算法的4 鄰域搜索策略；在格網(wǎng)內(nèi)部搜索時(shí)，則選擇遍歷進(jìn)入當(dāng)前格網(wǎng)的特征像元到其他所有特征像元之間的多種路徑組合。同時(shí)，對(duì)啟發(fā)函數(shù)h(n)沿用了與A*算法的思想，表示從結(jié)點(diǎn)n到目標(biāo)結(jié)點(diǎn)預(yù)估代價(jià)，由此綜合式（1）和式（8），總的通行代價(jià)函數(shù)表達(dá)式：

在格網(wǎng)化的地表可通行性數(shù)字化專題地圖中，確定路徑搜索的起點(diǎn)像元S 和目標(biāo)像元G，以起點(diǎn)像元S作為本次搜索起點(diǎn)，算法的總體過程如下：

步驟1，圖6Ⅰ中，以起點(diǎn)像元S 作為本次搜索起點(diǎn)，得到包含起點(diǎn)像元S的格網(wǎng)單元，如果包含起點(diǎn)像元S的格網(wǎng)單元為多個(gè)，則選取距離終點(diǎn)像元G 最近的一個(gè)作為本次搜索到的格網(wǎng)單元，表示為格網(wǎng)單元grid(S)，在格網(wǎng)單元grid(S)中，采用特征像元識(shí)別算法，W0個(gè)特征像元，計(jì)算每個(gè)特征像元的估價(jià)函數(shù)f(n)并加入到OPEN 表中，OPEN表中的各像元被標(biāo)記為藍(lán)色。

圖6 Grid A*算法搜索過程Fig.6 Path plan procedures of Grid A* algorithm

步驟2，圖6Ⅱ中，Grid A*算法以O(shè)PEN 表中f(n)最小的結(jié)點(diǎn)作為下一步搜索的起點(diǎn)，并將此結(jié)點(diǎn)移入CLOSED 表中，CLOSED 表中的各像元被標(biāo)記為黃色，由于特征像元一定位于被兩個(gè)格網(wǎng)單元公用邊上，所以此時(shí)被選擇的結(jié)點(diǎn)就是兩個(gè)格網(wǎng)單元之間的媒介，算法將繼續(xù)選定前進(jìn)方向上下一個(gè)格網(wǎng)單元grid(i)，并將遍歷獲得的特征像元加入OPEN表中。

步驟3，圖6Ⅲ—Ⅶ中，算法每次均從OPEN表中取出f(n)最小的特征像元，再遍歷該特征像元所在格網(wǎng)單元，將新搜索到的特征像元加入OPEN 表中，直到某一被遍歷的格網(wǎng)單元包含目標(biāo)結(jié)點(diǎn)為止；需要注意的是，圖6Ⅳ中OPEN 表中估價(jià)函數(shù)f(n)最小的結(jié)點(diǎn)是A，并以A為起點(diǎn)搜索得到圖6Ⅴ，但A 的子結(jié)點(diǎn)f(n)均大于B，所以下一步搜索需要以當(dāng)前OPEN 表中f(n)最小的特征像元B為起點(diǎn)，故得到圖6Ⅵ。

步驟4，圖6Ⅷ中，從目標(biāo)結(jié)點(diǎn)依次回溯各特征像元的上一級(jí)結(jié)點(diǎn)，并使用線段連接，就可以得到結(jié)果路徑，此時(shí)Grid A*算法運(yùn)行結(jié)束，結(jié)果路徑中各特征像元所構(gòu)建的“通行區(qū)域”范圍使用淺黃色框體標(biāo)出，本研究認(rèn)為越野車輛在淺黃色區(qū)域內(nèi)具有最佳的可通行性。

相比于傳統(tǒng)A*算法，Grid A*算法以格網(wǎng)單元作為搜索和擴(kuò)展的基本單元，極大的壓縮了搜索空間，提高了運(yùn)算效率；并采用式（6）作為通行代價(jià)的計(jì)算方法，考慮了越野通行路寬等因素；以格網(wǎng)單元邊上的特征像元的基本單位，充分兼顧了高分辨率影像的細(xì)節(jié)信息，提高了所搜索路徑的計(jì)算速度與結(jié)果的可靠性。圖7 為Grid A*算法流程圖。

圖7 Grid A*算法流程圖Fig.7 Flowchart of Grid A* Algorithm

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)數(shù)據(jù)獲取與處理

為驗(yàn)證本研究提出的路徑規(guī)劃算法的有效性，本文使用UAV獲取了沙漠地帶的高分辨率影像數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)區(qū)域位于新疆維吾爾自治區(qū)圖木舒克市南郊地區(qū)（圖8），地處塔克拉瑪干沙漠西緣，為山脈到沙漠的過渡地帶，地貌復(fù)雜。航拍作業(yè)時(shí)間為2019年8月，影像覆蓋范圍長(zhǎng)約1.3 km，寬約0.5 km，最高點(diǎn)海拔1113.58 m，最低點(diǎn)1101.13 m，地表起伏約12 m。

圖8 Google Earth中實(shí)驗(yàn)區(qū)域Fig.8 Experiment Area in Google Earth

首先對(duì)獲取的影像使用Pix4D 軟件拼接處理并提取數(shù)字表面模型（DSM），圖9 為可見光影像的拼接圖，圖10 為使用灰度表達(dá)的區(qū)域DSM，兩張影像的大小均為9304 像素×2972 像素，空間分辨率為13.76 cm。

圖9 圖木舒克市南郊可見光拼接影像圖Fig.9 Visible light mosaic image of the southern suburb of Tumxuk City

圖10 圖木舒克市南郊DSM影像圖Fig.10 DSM image of the southern suburb of Tumxuk City

4.2 地表可通行性計(jì)算

實(shí)驗(yàn)前利用神經(jīng)網(wǎng)絡(luò)算法對(duì)可見光影像進(jìn)行分類，根據(jù)該區(qū)域內(nèi)自然景觀的特點(diǎn)，將地物分為道路、戈壁、鹽堿地、低矮植物、沙地、水體等6類，分類結(jié)果如圖11所示。

圖11 圖木舒克市南郊DSM影像圖Fig.11 DSM image of the southern suburb of Tumxuk City

同時(shí)基于DSM 數(shù)據(jù)，得到坡度值，基于前述3.2 節(jié)中式（4）（5），得到各像元的通行阻力值，如圖12 所示，亮度越高的區(qū)域通行阻力越小，亮度越低的區(qū)域通行阻力越大。

圖12 圖木舒克市南郊可通行性地圖Fig.12 Passability map of the southern suburb of Tumxuk City

4.3 路徑規(guī)劃

基于前述方法，本文以分類圖為基礎(chǔ)，對(duì)圖12所示整個(gè)通行性地圖進(jìn)行了格網(wǎng)劃分，同時(shí)其于分類圖層查找其特征像元。

本實(shí)驗(yàn)中，重新選擇一次交通工具意味著選擇不同的通行路徑寬度，也就意味著重新選擇格網(wǎng)單元的大小。為了簡(jiǎn)化問題，對(duì)于所有的交通工具我們都使用了一致的代價(jià)函數(shù)，即近似認(rèn)為摩托車與越野車在荒地具有一樣的通行能力。

基于3.2 節(jié)提出的代價(jià)函數(shù)，并結(jié)合實(shí)驗(yàn)區(qū)域的實(shí)際通達(dá)性，選擇序列5、7、9、11、13、15作為格網(wǎng)尺寸的大小。如圖13 所示，格網(wǎng)尺寸為5、7、9像元的情況，Grid A*算法搜索出了從S點(diǎn)到G點(diǎn)的可通行路徑，即所需路寬在0.7—1.5 m 間的交通工具可以在該區(qū)域通行，比如摩托車或UGV等；但對(duì)于11、13、15 像元大小的格網(wǎng)，算法無法找到可通行的路徑，換言之，對(duì)于所需1.5 m 路寬的車輛來說，兩點(diǎn)間是無法通行的。這一結(jié)果與實(shí)際環(huán)境情況基本相符。

圖13 不同圖像分辨率下的A*算法和不同格網(wǎng)尺寸的Grid A*算法路徑對(duì)比圖1Fig.13 Paths comparison 1 between A* algorithm with different image resolutions and Grid A* algorithm with different grid cell sizes

為了比較Grid A*算法與傳統(tǒng)A*算法的優(yōu)劣，同時(shí)使用A*算法在圖13 上的兩點(diǎn)間搜索路徑。表2 顯示了兩種算法結(jié)果的比較，A*算法和Grid A*算法分別按照式（1）和式（9）計(jì)算搜索路徑上的通行代價(jià)。對(duì)于Grid A*算法而言，格網(wǎng)單元越大，算法速度越快，這一點(diǎn)符合本文期望。而對(duì)于A*算法，為了保持其所搜索的像素空間分辨率與Grid A*算法格網(wǎng)單元大小一致，對(duì)原數(shù)據(jù)做了如前所述的壓縮，由于壓縮后A*算法搜索的像素?cái)?shù)大為減少，故其速度較使用原始分辨率的數(shù)據(jù)提升了很多。但從表2 中可以看出，A*算法使用壓縮圖像所搜索的路徑其通行代價(jià)較Grid A*算法偏高，同時(shí)，由圖13 可以看出，其所搜索路徑也較Grid A*算法更長(zhǎng)。

表2 不同圖像分辨率下的A*算法和不同格網(wǎng)尺寸的Grid A*算法效率對(duì)比Table 2 Efficiency comparison between A* algorithm with different image resolutions and Grid A* algorithm with different grid cell sizes

為了考察兩種算法所搜索路徑的可靠性，在圖14中，給出了以S 到A、A 到B 和B 到G 等3段通行路徑為例，對(duì)Grid A*算法和A*算法進(jìn)行了比較。如圖14 所示，Grid A*算法較基于壓縮圖像的A*算法均有較好的表達(dá)，尤其B 到G 段路徑，由于基于壓縮圖像的A*算法對(duì)格網(wǎng)單元做了平均，所以未能找到由B 到G 段早有車輛通行過的路徑，即在圖分類時(shí)將其分類為道路的地表。在圖14（d）給出了局部地表及搜索路徑的三維可視化效果，可以更直觀地看出，Grid A*算法所搜索路徑通過的地表較基于壓縮圖像的A*算法更為平穩(wěn)通暢。

圖14 不同圖像分辨率下的A*算法和不同格網(wǎng)尺寸的Grid A*算法路徑對(duì)比圖2Fig.14 Paths comparison 2 between A* algorithm with different image resolutions and Grid A* algorithm with different grid cell sizes

從圖14 可以看出，傳統(tǒng)A*算法基于單像元搜索的路徑結(jié)果，顯示不遜于Grid A*算法，但由于其找到的是一條單像元的路徑，當(dāng)區(qū)域存在特殊情時(shí)，其所搜索路徑的可靠性難以確定。為了驗(yàn)證這一點(diǎn)，人為在實(shí)驗(yàn)數(shù)據(jù)中加入了障礙物，如圖15 所示黑色長(zhǎng)條物，圖15 中兩障礙物間僅有3 個(gè)像元寬度，傳統(tǒng)A*算法依然選擇從障礙物中穿行，而Grid A*算法則找到了繞過障礙物的路徑，所以，Grid A*算法更符合實(shí)際應(yīng)用情況，具有更好的可靠性。

圖15 傳統(tǒng)A*算法和Grid A*算法路徑對(duì)比圖Fig.15 Paths comparison between traditional A* algorithm and Grid A* algorithm

4.4 討論和分析

在空地協(xié)同過程中，充分利用無人機(jī)高分影像，并為地面車輛提供現(xiàn)勢(shì)性很強(qiáng)的路徑指引，具有非常重要的意義。但是在高分影像上單像元對(duì)應(yīng)的真實(shí)地表尺寸過小，提取可通行路徑時(shí)，必須兼顧通行路徑的寬度，引入格網(wǎng)單元是提高算法效率以及解決該問題的最佳方式，可以通過3種情形分析這一問題：

（1）如圖16（a）所示，使用傳統(tǒng)A*算法4 鄰域或8 鄰域的通行策略，按期望的路寬，僅在8 鄰域或4 鄰域的方向選取矩形“通行區(qū)域”，則會(huì)忽略其余方向的可通過情況，由于地物地形的影響，最佳通行路徑未必恰在4 個(gè)或8 個(gè)鄰域方向，同時(shí)如果沒有格網(wǎng)單元，無法選擇合理的前進(jìn)步長(zhǎng)H。

圖16 傳統(tǒng)A*算法、任意角度路徑搜索與Grid A*算法搜索方向?qū)Ρ葓DFig.16 Searching directions comparison between traditional A* algorithm，any-angle path plan and Grid A* algorithm

（2）如圖16（b）所示，在選擇合適的路寬后，進(jìn)行任意角度路徑搜索。如果考慮在盡可能多的方向搜索最優(yōu)路徑，按角度增量Δα選取搜索方向，過小的Δα值會(huì)使得搜索方向過多，假如Δα=15°，則需要搜索24個(gè)方向，從而使得搜索效率很低，同時(shí)如果沒有格網(wǎng)的限制，則無法把握合理的前進(jìn)步長(zhǎng)H。

（3）如圖16（c）所示，按本文所提方法，采用格網(wǎng)單元及其邊緣特征，一方面可兼顧地表分類特征，因?yàn)榈乇砀采w物的類型是影響地表通達(dá)性的關(guān)鍵因子，格網(wǎng)邊緣上有了地物類型特征，則最佳路徑的搜索同等條件下會(huì)優(yōu)先選取最易通行的地物類型；另一方面，有了格網(wǎng)單元，則有了算法可控的規(guī)則步長(zhǎng)，易于沿用A*算法的搜索策略，充分利用A*算法本有的啟發(fā)式的特性，從而盡可能找到最優(yōu)路徑。

另外，雖然在單元格劃分時(shí)未考慮地形起伏信息，但在高分影像上，在懸崖、陡坎、突兀的山頂?shù)容^大的地形突變處，地表類型一般不連續(xù)，因此按地物圖斑進(jìn)行特征點(diǎn)選取，隱含了對(duì)異常地形起伏的處理。

對(duì)于格網(wǎng)單元內(nèi)部存在“獨(dú)立地物斑塊”的情況，對(duì)該斑塊采用形態(tài)學(xué)的膨脹算法，使用其范圍擴(kuò)展到格網(wǎng)單元的邊上，從而可在格網(wǎng)單元邊上選取表達(dá)該斑塊類型的特征像元。

總體而言，本文提出的Grid A*算法與A*算法的本質(zhì)區(qū)別在于，前者使用了由n*n像元組成的格網(wǎng)作為計(jì)算單元，而后者則使用像元作為計(jì)算單元，當(dāng)n取值為（5，7，9，…）序列值時(shí)，Grid A*比A*算法效率要高，且n值越大計(jì)算效率越高，這一特點(diǎn)由表2所給實(shí)驗(yàn)結(jié)果可以看出。

傳統(tǒng)A*算法是一種通用的路徑規(guī)劃算法，與實(shí)際應(yīng)用場(chǎng)景沒有任何關(guān)系，基于柵格數(shù)據(jù)搜索時(shí)，它以像素為單元進(jìn)行搜索，因此在像素分辨率的級(jí)別上，可以保證所搜索到的路徑是最佳的。但由于該結(jié)果路徑?jīng)]有考慮實(shí)際應(yīng)用的需求，因此該最佳路徑的僅限于像素級(jí)別，如果實(shí)際交通工具需要覆蓋多個(gè)像素的路寬，則傳統(tǒng)A*算法無法解決這一問題。

Grid A*算法則使用了格網(wǎng)單元，而格網(wǎng)單元的選擇則是依據(jù)具體應(yīng)用而決定的，以應(yīng)急救援場(chǎng)景為例，格網(wǎng)單元的大小取決于使用交通工具行駛所需的實(shí)際路寬。在格網(wǎng)單元的邊緣上選取特征像元，從而確保Grid A*算法在使用格網(wǎng)為搜索單元的同時(shí)，兼顧了格網(wǎng)單元內(nèi)部的地形特征，以便搜索到具有最優(yōu)可通行性的路徑。Grid A*算法結(jié)合了詳細(xì)的地表要素分類結(jié)果，并對(duì)不同地表要素使用了不同的通達(dá)性函數(shù)，在將路寬作為參數(shù)因子進(jìn)行計(jì)算搜索的情況下，與傳統(tǒng)路徑搜索算法相比，既具有更好的普適性，也具有更強(qiáng)的針對(duì)性。

實(shí)驗(yàn)表明，相比傳統(tǒng)A*算法，Grid A*算法在保證路徑規(guī)劃結(jié)果可通行性的前提下，大幅度縮短了路徑規(guī)劃的所需的時(shí)間，且路徑規(guī)劃結(jié)果具有更優(yōu)的通行性。

5 結(jié)論

在野外應(yīng)急救援活動(dòng)中，為應(yīng)急車輛在短時(shí)間內(nèi)提取一條具有導(dǎo)航功能的路徑具有重要的現(xiàn)實(shí)意義，通行路徑的安全性和路徑搜索的速度對(duì)任務(wù)的順利完成有著重要的影響，路徑規(guī)劃算法的性能優(yōu)劣對(duì)野外應(yīng)急救援路徑規(guī)劃的可用性起到了決定性的作用。

通過本項(xiàng)研究表明，良好可靠的路徑搜索必須基于：（1）精準(zhǔn)的地表要素分類結(jié)果，（2）盡可能完備的通行代價(jià)函數(shù)，（3）不小于實(shí)際交通工具所需的路徑寬度，以及（4）高效的搜索算法。本文所提方法是對(duì)這幾方面的良好綜合，實(shí)驗(yàn)也表明，本文提出的算法可以很好地解決基于無人機(jī)獲取的超高分辨率影像，為不同交通工具搜索可靠通達(dá)性路徑的問題。

現(xiàn)有基于影像或柵格的路徑搜索算法往往單純強(qiáng)調(diào)路徑的通達(dá)性，以上幾方面的處理比較模糊，嚴(yán)重的情況下，基本忽略了通達(dá)性必須結(jié)合交通工具所需路寬這一現(xiàn)實(shí)問題，代價(jià)函數(shù)構(gòu)造也過于簡(jiǎn)略，無法應(yīng)用于無人機(jī)獲取的超高分辨率影像，也無法良好處理影響車輛真實(shí)行進(jìn)代價(jià)的微地貌特征。

本文算法存在的主要不足在于格網(wǎng)特征像元的選取僅考慮了地表類型，而沒有考慮地形起伏，因此特征像元的代表性有待提高；其實(shí)，格網(wǎng)單元內(nèi)部像元的代價(jià)計(jì)算，除了考慮較極端情況外，對(duì)一般性的細(xì)節(jié)考慮不足。進(jìn)一步的研究我們擬考慮更為合理的格網(wǎng)劃分方法，如以高程為主，引入四叉樹的方法分層次表達(dá)影響通達(dá)性的地物和地形因子，將有望使計(jì)算結(jié)果更為合理。此外，后續(xù)的研究結(jié)果我們將與戶外實(shí)際駕車驗(yàn)證進(jìn)行結(jié)合，進(jìn)一步提高代價(jià)函數(shù)模型中有關(guān)參數(shù)的準(zhǔn)確性。