面向越野路徑規(guī)劃的多層次六角格網(wǎng)通行模型

陳占龍,吳貝貝,王 潤,戴薇薇,徐道柱,馬 超

1. 中國地質(zhì)大學(武漢)計算機學院,湖北 武漢 430078; 2. 國家地理信息系統(tǒng)工程技術(shù)研究中心,湖北 武漢 430078; 3. 中國地質(zhì)大學(武漢)地質(zhì)探測與評估教育部重點實驗室,湖北 武漢 430074; 4. 湖北省地質(zhì)環(huán)境總站,湖北 武漢 430034; 5. 中國地質(zhì)大學(武漢)地理與信息工程學院,湖北 武漢 430078; 6. 西安測繪研究所,陜西 西安 710054; 7. 地理信息工程國家重點實驗室,陜西 西安 710054

越野環(huán)境下的路徑規(guī)劃起初應(yīng)用于軍事領(lǐng)域,通過對戰(zhàn)場環(huán)境的分析,指揮機動車輛、人員在戰(zhàn)場中的行動[1-5],隨著科學技術(shù)的不斷進步、人類需求的不斷提高,其逐漸應(yīng)用于民用交通、抗震救災(zāi)及民事生產(chǎn)等民生領(lǐng)域[6-10]。特別是近些年自然災(zāi)害增多,災(zāi)區(qū)救援爭分奪秒,盡早規(guī)劃出通往災(zāi)區(qū)的可通行路徑對救援十分必要[11]。越野環(huán)境地域廣闊,地勢起伏不定,地表覆蓋類型多樣,目前多數(shù)研究主要考慮環(huán)境因素約束,而路徑規(guī)劃問題通常還存在有限的處理時間、內(nèi)存和計算能力等性能約束,伴隨著規(guī)劃區(qū)域的擴大,通行模型數(shù)據(jù)規(guī)模增加,路徑規(guī)劃效率受限[12-13]。因此,如何在大規(guī)模越野場景中實現(xiàn)顧及多種環(huán)境因素約束的高效率越野路徑規(guī)劃方法就成為本文的研究重點。

通行環(huán)境場景建模是越野路徑規(guī)劃的基礎(chǔ),將復(fù)雜的野外通行環(huán)境量化為路徑規(guī)劃算法所需要的影響因子,便于算法感知通行環(huán)境[14]。通行模型常用拓撲法、柵格法、可視圖法和構(gòu)型空間法等構(gòu)建,其中柵格法使用簡單,可以同時對不規(guī)則的障礙物進行表達,能夠處理較為復(fù)雜的越野環(huán)境情況,也便于對多種影響因素進行疊加分析計算,本文也采用柵格法構(gòu)建通行模型[15-16]。柵格單元形狀一般為正三角形、正四邊形和正六邊形3種,在越野環(huán)境中,通行對象運動沒有路網(wǎng)的約束,前進方向多樣,因此具有更多通行方向、更一致領(lǐng)域關(guān)系的六角格網(wǎng)更適用于越野通行環(huán)境場景建模[17]。通行模型格網(wǎng)數(shù)據(jù)規(guī)模的增大會嚴重影響路徑規(guī)劃算法的計算效率,六角格網(wǎng)相較于三角和四角格網(wǎng),擁有更高的平面覆蓋率,使用六角格網(wǎng)作為柵格形狀可以相對減少通行模型格網(wǎng)數(shù)量[18]。但對于大范圍的通行模型構(gòu)建,格網(wǎng)數(shù)據(jù)規(guī)模依舊是巨大的,路徑規(guī)劃效率仍會陷入瓶頸。為了解決這類問題,文獻[19—21]提出應(yīng)用層次空間推理思想,將大規(guī)模路網(wǎng)進行分級或分層處理,縮減問題空間,利用“分而治之”的方法,將問題細分求解,有效緩解了路徑規(guī)劃在大規(guī)模路網(wǎng)中效率低下的問題。然而越野場景通常路網(wǎng)稀疏,不能依靠路網(wǎng)層次結(jié)構(gòu)對其進行分層處理以降低數(shù)據(jù)規(guī)模,提升規(guī)劃效率。據(jù)此,本文充分發(fā)揮層次空間推理思想在問題規(guī)模縮減方面的作用,在區(qū)域廣闊的無路網(wǎng)野外環(huán)境中,依靠多層次格網(wǎng)剖分系統(tǒng)構(gòu)建多層次六角格網(wǎng)通行模型,減少格網(wǎng)數(shù)據(jù)規(guī)模,提升路徑規(guī)劃效率。

越野環(huán)境路徑規(guī)劃算法需要有效兼顧多種約束條件并具有良好的運行效率,目前常用算法主要包括Dijkstra算法、A*算法、蟻群算法、遺傳算法和粒子群算法等[22]。其中A*算法作為啟發(fā)式搜索算法,可以將約束條件作為啟發(fā)因素,縮小搜索范圍以提高算法效率,常被應(yīng)用于需要考慮多約束條件的越野路徑規(guī)劃,本文也采用A*算法進行路徑規(guī)劃[23]。算法核心在于如何將選取合適的啟發(fā)因素,以得到合理的代價估計。文獻[24—25]將地形坡度、地表覆蓋等多種環(huán)境影響因子作為算法啟發(fā)因素,有效模擬真實越野環(huán)境,提升路徑規(guī)劃效率。據(jù)此,本文提出一種面向越野路徑規(guī)劃的多層次六角格網(wǎng)通行模型,該模型由普通六角格網(wǎng)通行模型,歷經(jīng)多層次格網(wǎng)壓縮及鄰接關(guān)系重構(gòu)生成。同時,本文在A*算法的基礎(chǔ)上,依據(jù)通行模型格網(wǎng)的多層次特點,針對通行環(huán)境中的各種約束條件優(yōu)化其啟發(fā)函數(shù),構(gòu)建適用于大規(guī)模越野場景的路徑規(guī)劃算法?；诖四Ｐ?本文以地形和地表覆蓋類型為例,選取遍歷格網(wǎng)數(shù)、路徑格網(wǎng)數(shù)及算法執(zhí)行時間等8個指標,在算法運行效率和算法可靠性兩個方面進行對比試驗,說明本文提出的多層次六角格網(wǎng)通行模型相較于普通六角格網(wǎng)通行模型能夠有效縮減格網(wǎng)數(shù)據(jù)規(guī)模,保持規(guī)劃路徑質(zhì)量,提升路徑規(guī)劃效率。

1 多層次六角格網(wǎng)通行模型的構(gòu)建

普通六角格網(wǎng)通行模型的構(gòu)建是生成多層次通行模型的前提。以格網(wǎng)地圖為基礎(chǔ),結(jié)合影響因子量化生成的通行能力,構(gòu)建出普通六角格網(wǎng)通行模型,經(jīng)格網(wǎng)層次壓縮及鄰接關(guān)系重構(gòu)生成多層次通行模型。由于多層次通行模型與普通六角格網(wǎng)通行模型的格網(wǎng)地圖結(jié)構(gòu)不同,所以還需要優(yōu)化路徑規(guī)劃算法使其適配多層次通行模型,流程圖如圖1所示。

1.1 普通六角格網(wǎng)通行模型

通行模型的構(gòu)建首先須生成格網(wǎng)地圖,然后分析量化影響因子,為格網(wǎng)賦予相應(yīng)的通行能力。

1.1.1 六角格網(wǎng)地圖生成

格網(wǎng)地圖通常由形狀為正三角形、正四邊形或正六邊形的格網(wǎng)組成,適用于不同的應(yīng)用場景[26-27]。如圖2所示,正六邊形與相鄰格網(wǎng)只有1種鄰接關(guān)系且有6個通行方向,正三角形有2種鄰接關(guān)系和6個通行方向,正四邊形有2種鄰接關(guān)系與8個通行方向。在路徑規(guī)劃中,由于正六邊形具有更一致的鄰接關(guān)系,擁有更多的等距通行方向個數(shù),方便算法處理鄰接關(guān)系,利于影響因子量化,因此,本文采用正六邊形作為格網(wǎng)地圖中的格網(wǎng)形狀。

圖2 3種多邊形鄰接關(guān)系與通行方向Fig.2 Adjacency relation and passage direction of three polygons

本文參照開源算法Uber-H3[28]構(gòu)建了多層次格網(wǎng)剖分系統(tǒng),如圖3所示。在該系統(tǒng)中,任意一個地理坐標在每個格網(wǎng)層次中都具有唯一的格網(wǎng)索引與之相對應(yīng),通過格網(wǎng)索引可以獲取到任意格網(wǎng)的鄰接格網(wǎng),不同層次的格網(wǎng)在范圍上具有上下層涵蓋關(guān)系。

圖3 多層次格網(wǎng)剖分系統(tǒng)Fig.3 Hierarchy grid system

1.1.2 影響因子量化

影響因子量化是對影響通行對象通行的地質(zhì)地形要素進行分析,用于對復(fù)雜豐富的越野環(huán)境進行抽象和簡化,以實現(xiàn)對實際地質(zhì)地形的量化模擬[29-30]。越野環(huán)境下的路徑規(guī)劃,不同的通行對象涉及不同的影響因子,針對輪式車輛為通行對象,本文將影響因子分為地形和地表覆蓋類型兩種,具體分類見表1[31-33]。

表1 越野路徑規(guī)劃影響因子分類

為了建立貼近通行環(huán)境的影響因子量化模型,本文將量化規(guī)則分為單因子量化和多因子量化。單因子量化得出格網(wǎng)是否能通行,用于篩選出不可通行的格網(wǎng);在格網(wǎng)可通行的基礎(chǔ)上,多因子量化用于計算格網(wǎng)通行能力。

(1) 單影響因子量化。通過確定單一影響因子的格網(wǎng)面積占比或存在與否,判斷格網(wǎng)通行性。本文將建筑物和水系進行單影響因子量化,判斷規(guī)則為

(1)

式中,sb和sw為建筑物與水體在對應(yīng)格網(wǎng)中所占面積;HS代表硬質(zhì)路面;S為對應(yīng)格網(wǎng)面積;p為不可通行的影響因子在格網(wǎng)中所占面積比例的閾值。建筑物和水體在格網(wǎng)中所占面積比例之和小于閾值p時,格網(wǎng)可通行;大于等于閾值p,且格網(wǎng)中不存在硬質(zhì)路面時,格網(wǎng)不可通行。依據(jù)實際應(yīng)用場景和通行對象類型,本文設(shè)定p值為0.5。

(2) 多影響因子量化。當格網(wǎng)的通行性為可通行時,對多種影響因子進行綜合量化,得到格網(wǎng)通行能力。坡度會影響車輛的通行速度,坡度越大,車輛受到爬坡阻力越大,通行速度越小。量化規(guī)則Ws為

(2)

式中,h為相鄰格網(wǎng)之間的高程差;d為相鄰格網(wǎng)之間的中心點距離;λs為坡度對車輛通行速度的影響系數(shù)。

硬質(zhì)路面、土質(zhì)路面、草地和森林的土質(zhì)松軟程度和地面粗糙程度各不相同,對車輛通行速度也存在著不同的影響。在本文中,它們的量化規(guī)則分為兩種:①當格網(wǎng)中存在硬質(zhì)路面時,格網(wǎng)通行能力不受地表覆蓋類型影響;②當格網(wǎng)中不存在硬質(zhì)路面時,使用土質(zhì)路面、草地和森林在格網(wǎng)中的面積占比與對于車輛速度的影響系數(shù)的乘積之和來表示它們對于格網(wǎng)通行能力的影響能力。量化規(guī)則Wc為

(3)

式中,S為對應(yīng)格網(wǎng)面積;HS代表硬質(zhì)路面;st、sg、se分別為土質(zhì)路面、草地和森林在對應(yīng)格網(wǎng)中的面積;λh、λt、λg、λe分別為格網(wǎng)中覆蓋類型為硬質(zhì)路面、土質(zhì)路面、草地和森林時對車輛速度的影響系數(shù)。

綜合以上兩種量化規(guī)則,得出格網(wǎng)n處的通行能力量化模型為

(4)

式中,Wc(n)為格網(wǎng)n處地表覆蓋類型對格網(wǎng)通行能力的影響能力。為了方便使用,還需要對Wc(n)進行歸一化操作

(5)

式中,Wcmin、Wcmax為Wc(n)的最小值和最大值。

因此,根據(jù)式(4)和式(5),可以得到顧及多種影響因子的格網(wǎng)通行能力量化模型

(6)

1.2 多層次通行模型構(gòu)建

多層次通行模型的構(gòu)建需要經(jīng)歷格網(wǎng)層次壓縮與鄰接關(guān)系重構(gòu)兩個過程。其具體步驟為:①將格網(wǎng)地圖中的所有格網(wǎng)作為初始集合S1。②對S1中的格網(wǎng)進行格網(wǎng)層次壓縮,將被壓縮的格網(wǎng)組成集合S2,再對S2進行鄰接關(guān)系重構(gòu);將S2從S1中刪除,生成集合S3。③將S2作為步驟②中的S1,重復(fù)步驟②。當S2為空時,將步驟②每次生成的集合S3合并,生成多層次通行模型。

1.2.1 格網(wǎng)層次壓縮

基于相鄰格網(wǎng)層級之間的涵蓋關(guān)系,本文提出了多層次格網(wǎng)壓縮算法,該算法將通行能力相似的鄰接子格網(wǎng)合并為父格網(wǎng)。設(shè)一組鄰接子格網(wǎng)集合C的通行能力為si(i=1,2,…,n),σ為C中所有格網(wǎng)通行能力的相似度

(7)

當相似度大于或等于格網(wǎng)相似度閾值ρ時,即σ≥ρ,表明集合C中所有格網(wǎng)表達的通行環(huán)境相似,可以被壓縮為父格網(wǎng),則壓縮后生成的父格網(wǎng)通行能力為W

(8)

在本文所構(gòu)建的多層次格網(wǎng)剖分系統(tǒng)中,n取值為7,ρ綜合對比試驗結(jié)果及本文應(yīng)用場景取值為0.80。

1.2.2 鄰接關(guān)系重構(gòu)

在多層次格網(wǎng)地圖中,由于原先格網(wǎng)鄰接關(guān)系失效,路徑規(guī)劃算法不能夠正確運行,因此需要重新構(gòu)建格網(wǎng)鄰接關(guān)系。設(shè)格網(wǎng)T的子格網(wǎng)為集合A,A的鄰接格網(wǎng)為集合U,則格網(wǎng)T的鄰接格網(wǎng)集合B={x:x∈Uandx?A},如圖4所示,橙色部分為集合B。再將格網(wǎng)T增添到B中格網(wǎng)的鄰接格網(wǎng)集合,鄰接關(guān)系重構(gòu)完成。

圖4 鄰接關(guān)系求解Fig.4 Solving adjacency relation

在多層次格網(wǎng)地圖中,不同尺寸格網(wǎng)會出現(xiàn)部分未覆蓋或格網(wǎng)重疊的問題,如圖5所示,這些問題會導(dǎo)致地理坐標不能映射到格網(wǎng)或映射格網(wǎng)沖突。為了解決這個問題,基于多層次格網(wǎng)剖分系統(tǒng)地理坐標與格網(wǎng)映射機制,本文在進行地理坐標映射時采取從格網(wǎng)地圖最低層級逐級向上轉(zhuǎn)換策略,正確計算地理坐標對應(yīng)的格網(wǎng)索引,消除格網(wǎng)地圖邏輯上空缺與重疊部分。

圖5 多層次格網(wǎng)地圖Fig.5 Multi-hierarchy grid map

如圖6(a)所示,在獲取坐標點a所在格網(wǎng)時,雖然格網(wǎng)A與格網(wǎng)B存在疊加關(guān)系,但依照最低層級逐級向上轉(zhuǎn)換策略,坐標點a會被定位到格網(wǎng)B;在獲取坐標點b所在格網(wǎng)時,會首先得到格網(wǎng)C,而格網(wǎng)C已被壓縮為父格網(wǎng)A,所以坐標點b被定位到格網(wǎng)A。實際上,格網(wǎng)A所覆蓋的區(qū)域為區(qū)域B,如圖6(b)所示。

圖6 多層次格網(wǎng)坐標點與格網(wǎng)對應(yīng)關(guān)系及格網(wǎng)覆蓋區(qū)域Fig.6 Correspondence between coordinates and grid in multi-hierarchies grid maps and grid coverage area

1.3 路徑規(guī)劃算法

A*算法作為啟發(fā)式算法,通過對啟發(fā)函數(shù)的設(shè)計,可以減少無謂的路徑搜索,縮小搜索范圍,提高搜索效率[34],其啟發(fā)函數(shù)可以表示為

F(n)=G(n)+H(n)

(9)

式中,F(n)為當前格網(wǎng)n的綜合估計值,當需要遍歷下一個格網(wǎng)時,算法總會選取綜合估計值優(yōu)先級最高的格網(wǎng);G(n)為當前格網(wǎng)n距離起始點的實際代價;H(n)為當前格網(wǎng)n距離終點的預(yù)估代價。

為了適應(yīng)多層次格網(wǎng)地圖格網(wǎng)大小不一的特點,本文摒棄通過格網(wǎng)數(shù)乘以格網(wǎng)大小計算當前格網(wǎng)G(n)的方式,轉(zhuǎn)而采用從起點到當前格網(wǎng)n所經(jīng)過格網(wǎng)距離之和計算G(n),如式(10)所示

(10)

式中,Di為從起點格網(wǎng)到當前格網(wǎng)n所經(jīng)過的第i段路徑,如圖7所示。

針對越野環(huán)境下的路徑規(guī)劃,本文選取格網(wǎng)通行能力與相鄰格網(wǎng)間的坡度值作為啟發(fā)因素。H(n)為當前格網(wǎng)n到終點格網(wǎng)goal的歐氏距離與啟發(fā)因素的累加的乘積

H(n)=(Ws(n,p)+Grid(n))·ρ(n,goal)

(11)

式中,Ws(n,p)為n格網(wǎng)處坡度對格網(wǎng)通行能力的影響能力,求解過程中的鄰接格網(wǎng)為當前格網(wǎng)n與它的前驅(qū)格網(wǎng)p;Grid(n)為當前格網(wǎng)n的通行能力值;ρ(n,goal)為當前格網(wǎng)n到終點格網(wǎng)goal的歐氏距離。

此外,為了保證啟發(fā)因素量綱統(tǒng)一,且H(n)估計值不能大于當前格網(wǎng)n到終點格網(wǎng)goal的實際值[35],須先對其進行歸一化操作

(12)

(13)

綜上可得綜合兩種影響因子的A*算法綜合估計值函數(shù)

ρ(n,goal)

(14)

2 試驗結(jié)果與分析

2.1 試驗區(qū)域

本文選取貴州省畢節(jié)市黔西縣境內(nèi)部分區(qū)域,如圖8所示,該區(qū)域中的地表覆蓋類型主要為森林與土質(zhì)路面,四方山巒綿延,中部地勢平坦開闊,較適宜作為試驗區(qū)。其中遙感影像數(shù)據(jù)為谷歌衛(wèi)星影像,空間分辨率為0.6 m;數(shù)字高程數(shù)據(jù)為美國國家航空航天局NASA提供的DEM數(shù)據(jù),空間分辨率為30 m;土地利用分類數(shù)據(jù)為2020年GlobeLand(http:∥www.globallandco ver.com/)全球土地覆蓋,空間分辨率為30 m。

圖8 試驗區(qū)區(qū)位Fig.8 Location of experimental area

2.2 多層次通行模型結(jié)果

2.2.1 影響因子的計算

為了更好地模擬通行環(huán)境,建立貼近通行環(huán)境的通行模型,基于1.1.2節(jié)影響因子量化,本文構(gòu)建了坡度、硬質(zhì)路面、土質(zhì)路面、草地和森林對于車輛速度的影響系數(shù)λs、λh、λt、λg、λe,見表2、表3。Ws與Wc的取值范圍由影響系數(shù)確定,由表3可知,Wsmax與Wcmax取值為1,Wsmin與Wcmin取值為0。

表2 坡度影響系數(shù)

表3 地表覆蓋類型影響系數(shù)

2.2.2 多層次通行模型的生成

生成多層次通行模型首先需要確定基礎(chǔ)格網(wǎng)分辨率,格網(wǎng)分辨率的確定需要綜合考慮地圖比例尺、研究區(qū)域范圍大小、應(yīng)用需求等因素。圖9展示了不同格網(wǎng)分辨率的通行模型,其中線要素為不同等級的公路,在本文中均被表示為硬質(zhì)路面地表覆蓋類型。對比不同格網(wǎng)分辨率的通行模型可以發(fā)現(xiàn),當格網(wǎng)分辨率為R=9時,通行環(huán)境可以得到很好的模擬,如圖9(c)所示。以硬質(zhì)路面為例,在基礎(chǔ)格網(wǎng)分辨率采用R=9時,硬質(zhì)路面經(jīng)過的格網(wǎng)都表現(xiàn)出了最佳的通行能力。而當基礎(chǔ)格網(wǎng)分辨率為R=8、R=7或更低時,格網(wǎng)的表達的通行能力較為粗糙,如圖9(b)右下角所示,格網(wǎng)并沒有體現(xiàn)出硬質(zhì)路面所帶來的通行能力提升。在此格網(wǎng)分辨率生成的通行模型中進行路徑規(guī)劃,規(guī)劃出的路徑會出現(xiàn)沒有優(yōu)先經(jīng)過硬質(zhì)路面的情況。雖然格網(wǎng)分辨率越大,格網(wǎng)量化精度越高,所表達的通行環(huán)境越精細,如圖9(d)所示,硬質(zhì)路面經(jīng)過的格網(wǎng)同樣表現(xiàn)出了最佳的通行能力;但當格網(wǎng)的分辨率超過地理環(huán)境的實際分辨率時,會出現(xiàn)格網(wǎng)量化時沒有坐標點相對應(yīng)的情況。在圖9(d)中,沒有坐標點映射的區(qū)域存在格網(wǎng)缺失,因此無法進行路徑規(guī)劃研究。綜上本文以R=9為基礎(chǔ)格網(wǎng)分辨率構(gòu)建多層次通行模型。

圖9 不同格網(wǎng)分辨率通行模型對比Fig.9 Comparison of traffic models with different grid resolutions

采用第1.2節(jié)多層次通行模型構(gòu)建方法生成多層次通行模型,如圖10所示。由圖10可以看出,一些通行能力相似的格網(wǎng)都被壓縮為了更高層次的格網(wǎng),通行環(huán)境細節(jié)也沒有丟失。表4所示為不同參數(shù)通行模型格網(wǎng)數(shù)量,可以看出以多層次通行模型格網(wǎng)數(shù)量僅為R=9的普通通行模型的53.75%。

表4 不同格網(wǎng)分辨率通行模型格網(wǎng)數(shù)量

圖10 多層次通行模型Fig.10 Multi-hierarchy traffic model

2.3 通行模型有效性評價

本文使用多層次六角格網(wǎng)通行模型與普通六角格網(wǎng)通行模型進行對比,路徑規(guī)劃算法均為A*算法,啟發(fā)因素一致,兩種通行模型如圖11所示。

圖11 通行模型對比Fig.11 Traffic model comparison

為了討論多層次六角格網(wǎng)通行模型對于越野路徑規(guī)劃的影響,以及基于該模型規(guī)劃路徑的合理性,本文選取5組起點O和終點D,并展示了O3D3的路徑結(jié)果。5組OD均距離較遠且地表覆蓋復(fù)雜,其中O2D2位于海拔較高且坡度多變的多山地帶,如圖12所示。

圖12 越野路徑規(guī)劃結(jié)果Fig.12 Results of off-road path planning

對比兩條路徑可以發(fā)現(xiàn),PN與PO在起點處路徑基本一致,說明在沒有格網(wǎng)層次壓縮的區(qū)域,多層次通行模型與普通通行模型規(guī)劃路徑質(zhì)量相同;中部區(qū)域通行環(huán)境多變,存在多個格網(wǎng)被壓縮的現(xiàn)象,格網(wǎng)鄰接關(guān)系發(fā)生變化,PN與PO在p1處產(chǎn)生了分歧。其中,PN折向右下方,以保證盡量沿著硬質(zhì)路面前行,有較好的通行環(huán)境,但路徑不夠平滑,拐點較多,對于考慮轉(zhuǎn)彎半徑的通行對象,會影響其通行或行進速度;而PO路徑筆直,經(jīng)過的格網(wǎng)通行難度較低且通過格網(wǎng)數(shù)少,因此路徑平滑且長度較短;最后,靠近終點時,PN與PO所經(jīng)過的區(qū)域通行難度相似,以路徑最短前行,說明啟發(fā)函數(shù)中的距離因素有效引導(dǎo)了通行對象的行動。

(1) 算法效率對比。本文以遍歷格網(wǎng)數(shù)、路徑格網(wǎng)數(shù)、算法執(zhí)行時間指標對算法效率進行定量分析,其結(jié)果如圖13所示。格網(wǎng)層次壓縮算法降低了通行模型格網(wǎng)數(shù)量的規(guī)模,極大地縮小了算法的搜索空間,使得基于多層次六角格網(wǎng)通行模型的路徑規(guī)劃算法相較于普通六角格網(wǎng)通行模型,遍歷格網(wǎng)數(shù)平均減少了47%。本文提出的路徑規(guī)劃算法在尋找路徑的過程中,需要在待遍歷格網(wǎng)集合中選擇通行能力值最大的格網(wǎng)進行,因此待遍歷格網(wǎng)集合越小,路徑規(guī)劃算法的執(zhí)行效率越高。試驗結(jié)果表明,基于多層次六角格網(wǎng)通行模型的算法效率較普通通行模型明顯提高,其算法執(zhí)行時間大大降低,平均減少了57%;在路徑格網(wǎng)數(shù)量上,由于O2D2和O4D4經(jīng)過的區(qū)域格網(wǎng)通行能力的相似度較低,被層次壓縮的格網(wǎng)數(shù)量較少,所以兩種通行模型在路徑格網(wǎng)數(shù)量上相差不大,但也有16%的數(shù)量縮減。

圖13 算法運行效率對比Fig.13 Comparison of algorithm operation efficiency

(2) 算法可靠性對比。本文選擇路徑地表覆蓋類型占比、路徑長度、拐點、坡度平均值與標準差作為定量指標,使用余弦距離來量化兩種通行模型在地表覆蓋類型占比分布相似度,綜合對比規(guī)劃路徑的優(yōu)劣。由圖14和圖15可以看出,兩種通行模型在通行環(huán)境上基本相似,地表覆蓋類型占比分布相似度平均值高達98.75%,路徑長度平均相差6%,但基于多層次六角格網(wǎng)通行模型的路徑坡度的平均值與標準差更小,拐點更少,路徑平坦順滑,更易通行。具體來說,在O3D3中,PN與PO地表覆蓋類型占比指標分布相似度為99.5%,PO在路徑長度、坡度的平均值和標準差指標上更低,且PO的拐點僅為PN的一半,PO在確保與PN相似路況的前提下,規(guī)劃了更短、更平坦、更順滑的路徑,充分體現(xiàn)了基于多層次六角格網(wǎng)通行模型規(guī)劃路徑的有效性。另外,雖然O4D4在多層次六角格網(wǎng)通行模型上拐點較多,但路徑坡度的平均值與標準差更小,路徑更加平坦;O2D2在多層次六角格網(wǎng)通行模型上路徑坡度的平均值與標準差較大,但路徑拐點更少,路徑更加順滑,通過的格網(wǎng)地表覆蓋土質(zhì)路面更多。由此可以看出,本文提出顧及多種影響因子的越野路徑規(guī)劃算法是可靠的。

圖14 路徑地表覆蓋類型占比Fig.14 Proportion of path land cover type

圖15 算法結(jié)果質(zhì)量對比Fig.15 Comparison of quality of algorithm results

綜上,不同于通行環(huán)境相對簡單的基于路網(wǎng)的路徑規(guī)劃,越野條件下的通行環(huán)境復(fù)雜,沒有道路網(wǎng)約束且規(guī)劃區(qū)域廣闊。本文針對這種特點建立了顧及地形與地表覆蓋類型兩類影響因子的多層次六角格網(wǎng)通行模型,選取遍歷格網(wǎng)數(shù)、路徑格網(wǎng)數(shù)及算法執(zhí)行時間等8個指標衡量多層次六角格網(wǎng)通行模型的優(yōu)越性。試驗結(jié)果表明,在通行環(huán)境局部相似度高的大規(guī)模越野環(huán)境中,本文提出的建模方法有效減少了路徑規(guī)劃應(yīng)用的所需計算時間與存儲空間,縮減程度均達到近50%,其規(guī)劃路徑結(jié)果也是可以被接受的。

3 總 結(jié)

面對大規(guī)模越野環(huán)境下路徑規(guī)劃效率低下的問題,本文提出了多層次六角格網(wǎng)通行模型,并基于該模型實現(xiàn)了顧及多影響因子的越野路徑規(guī)劃算法?；诙鄬哟胃窬W(wǎng)剖分系統(tǒng),普通六角格網(wǎng)通行模型歷經(jīng)相似格網(wǎng)壓縮,鄰接關(guān)系重構(gòu),最終生成了多層次六角格網(wǎng)通行模型,并對A*算法啟發(fā)函數(shù)進行優(yōu)化,使其具有更高的效率與可靠性。試驗表明,本文提出的通行模型在大規(guī)模越野場景中能保持良好的整體性能,相較于普通六角格網(wǎng)通行模型,有效降低了通行模型的格網(wǎng)數(shù)據(jù)規(guī)模,減少了算法的運行時間。

本文在實現(xiàn)多層次六角格網(wǎng)通行模型時,多層次格網(wǎng)壓縮算法僅考慮了格網(wǎng)的通行能力作為壓縮標準,壓縮后的格網(wǎng)不能完全擬合真實通行環(huán)境。因此,后續(xù)工作還需在格網(wǎng)相似程度的多因素判斷方法上進行探索,進一步優(yōu)化多層次六角格網(wǎng)通行模型。