陳占龍,吳貝貝,王 潤(rùn),戴薇薇,徐道柱,馬 超

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

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

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

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

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

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

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

1.1.2 影響因子量化

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

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

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

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

(1)

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

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

(2)

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

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

(3)

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

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

(4)

式中,Wc(n)為格網(wǎng)n處地表覆蓋類(lèi)型對(duì)格網(wǎng)通行能力的影響能力。為了方便使用,還需要對(duì)Wc(n)進(jì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)兩個(gè)過(guò)程。其具體步驟為:①將格網(wǎng)地圖中的所有格網(wǎng)作為初始集合S1。②對(duì)S1中的格網(wǎng)進(jìn)行格網(wǎng)層次壓縮,將被壓縮的格網(wǎng)組成集合S2,再對(duì)S2進(jìn)行鄰接關(guān)系重構(gòu);將S2從S1中刪除,生成集合S3。③將S2作為步驟②中的S1,重復(fù)步驟②。當(dāng)S2為空時(shí),將步驟②每次生成的集合S3合并,生成多層次通行模型。

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

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

(7)

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

(8)

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

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

在多層次格網(wǎng)地圖中,由于原先格網(wǎng)鄰接關(guān)系失效,路徑規(guī)劃算法不能夠正確運(yùn)行,因此需要重新構(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)會(huì)出現(xiàn)部分未覆蓋或格網(wǎng)重疊的問(wèn)題,如圖5所示,這些問(wèn)題會(huì)導(dǎo)致地理坐標(biāo)不能映射到格網(wǎng)或映射格網(wǎng)沖突。為了解決這個(gè)問(wèn)題,基于多層次格網(wǎng)剖分系統(tǒng)地理坐標(biāo)與格網(wǎng)映射機(jī)制,本文在進(jìn)行地理坐標(biāo)映射時(shí)采取從格網(wǎng)地圖最低層級(jí)逐級(jí)向上轉(zhuǎn)換策略,正確計(jì)算地理坐標(biāo)對(duì)應(yīng)的格網(wǎng)索引,消除格網(wǎng)地圖邏輯上空缺與重疊部分。

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

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

圖6 多層次格網(wǎng)坐標(biāo)點(diǎn)與格網(wǎng)對(duì)應(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ā)式算法,通過(guò)對(duì)啟發(fā)函數(shù)的設(shè)計(jì),可以減少無(wú)謂的路徑搜索,縮小搜索范圍,提高搜索效率[34],其啟發(fā)函數(shù)可以表示為

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

(9)

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

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

(10)

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

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

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

(11)

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

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

(12)

(13)

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

ρ(n,goal)

(14)

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

2.1 試驗(yàn)區(qū)域

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

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

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

2.2.1 影響因子的計(jì)算

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

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

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

2.2.2 多層次通行模型的生成

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

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

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

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

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

2.3 通行模型有效性評(píng)價(jià)

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

圖11 通行模型對(duì)比Fig.11 Traffic model comparison

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

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

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

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

圖13 算法運(yùn)行效率對(duì)比Fig.13 Comparison of algorithm operation efficiency

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

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

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

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

3 總 結(jié)

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

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