一種基于緩沖區(qū)分析的A*算法路徑規(guī)劃

康傳利,張臨煒,2,陳 洋,時滿星,顧俊峰

(1.桂林理工大學(xué) a.廣西空間信息與測繪重點(diǎn)實(shí)驗(yàn)室;b.測繪地理信息學(xué)院,廣西 桂林 541006;2.廣東省土地調(diào)查規(guī)劃院，廣州 510075)

0 引 言

地理信息系統(tǒng)是一種采集、存儲、管理、分析、顯示和應(yīng)用地理信息的計(jì)算機(jī)系統(tǒng),是分析和處理海量地理數(shù)據(jù)的通用技術(shù)。GIS空間分析是對地理空間中目標(biāo)的空間關(guān)系和空間行為進(jìn)行描述,為目標(biāo)的空間查詢和空間相關(guān)分析提供參考,進(jìn)一步為空間決策提供服務(wù)的技術(shù)?？臻g分析是地理信息系統(tǒng)區(qū)別于一般信息系統(tǒng)、CAD或電子地圖系統(tǒng)的主要功能特征,是GIS的核心和靈魂[1-2]。

路徑規(guī)劃技術(shù)在眾多領(lǐng)域都有著廣泛的應(yīng)用,如機(jī)器人自主無碰運(yùn)動、無人機(jī)避障突防飛行、巡航導(dǎo)彈躲避雷達(dá)搜索、GPS導(dǎo)航、基于GIS的道路規(guī)劃、城市道路網(wǎng)規(guī)劃導(dǎo)航等[3]。凡是可以拓?fù)錇殡娋€網(wǎng)絡(luò)的規(guī)劃問題,基本上都可以采用路徑規(guī)劃的方法來解決。路徑規(guī)劃的核心是算法的設(shè)計(jì),目前路徑規(guī)劃算法的研究已經(jīng)得到了廣泛的關(guān)注。傳統(tǒng)解決最短路徑規(guī)劃問題的算法包括Floyd算法、Dijkstra算法,它們需要較大的存儲空間,并且隨著頂點(diǎn)的增多,復(fù)雜度急劇上升。為了更好地解決最短路徑規(guī)劃問題,學(xué)者們受自然界生物群體活動或者自然現(xiàn)象的啟發(fā),開始關(guān)注智能算法的研究,并不斷在原有基本算法的基礎(chǔ)上開拓創(chuàng)新,提出新的啟發(fā)式算法[4-5]，比較常見的有遺傳算法(GA)、 蟻群算法(ACO)、 粒子群算法(PSO)。這些基于自然界特征的算法都有各自的不足之處,如遺傳算法容易出現(xiàn)早熟現(xiàn)象、粒子群算法容易陷入局部最優(yōu)解并且對初始種群依賴性太大、蟻群算法收斂速度較慢。因此,對算法的改進(jìn)是學(xué)者們近年的重點(diǎn)研究方向[5-6]。A*算法是一種啟發(fā)式搜索算法,通過設(shè)定合理的啟發(fā)式評估函數(shù),全面評估網(wǎng)格化區(qū)域內(nèi)各擴(kuò)展節(jié)點(diǎn)權(quán)重,從而規(guī)劃最優(yōu)行進(jìn)路線。

本文提出一種基于GIS空間分析的A*算法路徑規(guī)劃方法,通過對景區(qū)空間地理數(shù)據(jù)進(jìn)行整理編輯,將景區(qū)空間信息進(jìn)行可視化表達(dá),并對空間信息進(jìn)行充分解譯與利用,結(jié)合A*算法,對傳統(tǒng)路徑規(guī)劃方法加以改進(jìn),優(yōu)化旅游路線。

1 專題地圖的生成與解譯

1.1 GIS緩沖區(qū)分析

緩沖區(qū)分析是地理信息系統(tǒng)重要的空間操作功能之一,基本思想是給定一個空間實(shí)體,在實(shí)體周圍建立一定緩沖半徑的帶狀區(qū)域, 以確定這些物體對周圍環(huán)境的影響范圍或服務(wù)范圍。緩沖區(qū)分析主要用來解決地理空間中地物距離相近程度問題。一般情況下,緩沖區(qū)分析與疊加分析、網(wǎng)絡(luò)分析、服務(wù)設(shè)施查詢等空間分析功能相結(jié)合,處理地理空間信息數(shù)據(jù),解決空間決策問題。緩沖區(qū)分析在城市規(guī)劃、道路交通管理、環(huán)境監(jiān)測、軍事應(yīng)用等領(lǐng)域得到廣泛應(yīng)用[6-8]。

對于不同的目標(biāo)要素類型,所產(chǎn)生的緩沖區(qū)也不同。點(diǎn)緩沖區(qū)通常是以點(diǎn)為圓心,以一定距離為半徑的圓;線緩沖區(qū)是以線為中心軸線,距離中心軸線一定距離的平行條帶多邊形;面緩沖區(qū)是以面的邊界向外或向內(nèi)擴(kuò)展一定距離所生成的新的多邊形。其中，線狀目標(biāo)的緩沖區(qū)的生成是關(guān)鍵和基礎(chǔ)。圖1a—c分別是點(diǎn)、線、面元素緩沖區(qū)建立的基本方式。

在地理信息桌面軟件中,加載景區(qū)影像數(shù)據(jù),依據(jù)網(wǎng)絡(luò)開源數(shù)據(jù)及實(shí)地考察,用點(diǎn)要素代表景點(diǎn)、車站;線要素代表道路網(wǎng);面要素代表景點(diǎn)參觀區(qū)域、水域、休閑活動區(qū)域等在景區(qū)影像數(shù)據(jù)上描繪新的矢量圖層。根據(jù)采集的實(shí)際數(shù)據(jù),設(shè)定緩沖區(qū)半徑, 在新生成的矢量圖層上建立點(diǎn)、線、面要素的緩沖區(qū),代表景區(qū)所有的可通行區(qū)域。結(jié)合矢量圖層,輸出路徑規(guī)劃用的專題地圖。

1.2 影像數(shù)字信息提取

A*算法是一種應(yīng)用在格子環(huán)境中的啟發(fā)式搜索算法,為了滿足算法需要,需將輸出的矢量專題地圖離散化,轉(zhuǎn)換為具有一定分辨率的柵格地圖。柵格地圖是按照一定的索引規(guī)則,將空間數(shù)據(jù)分割成有規(guī)律的網(wǎng)格,每一個網(wǎng)格稱為一個像元,每個像元的位置由行列號來定義。像元也可以稱為像素,表示圖像的基本元素,是存儲數(shù)字化影像的最小單元,像元的大小由圖像分辨率的高低來決定:分辨率越高,像元所包含的信息就越抽象;分辨率越低,像元所包含的信息就越豐富[9-11]。

通過計(jì)算機(jī)程序,對柵格影像進(jìn)行解譯,將像元值存儲在一個有序的二維數(shù)組中,數(shù)組行列號代表像元所在的行列號,數(shù)組存儲的數(shù)值代表該像元的RGB值。在生成的專題地圖中,景區(qū)道路網(wǎng)及多元性質(zhì)的緩沖區(qū)域設(shè)有不同的RGB值,這是A*算法識別像元屬性的關(guān)鍵。A*算法通過讀取二維數(shù)組,對移動至每個像元的代價(jià)進(jìn)行評估, 從而規(guī)劃出最短路徑。 圖2是影像數(shù)字信息提取的一個實(shí)例。

圖1 點(diǎn)、線、面緩沖區(qū)示意圖Fig.1 Buffer schematic of point, line and surface

圖2 影像數(shù)字信息提取實(shí)例Fig.2 Image digital information extraction example

2 基于A*算法的景區(qū)路徑規(guī)劃

A*算法的主體思想是在搜索下一個節(jié)點(diǎn)并選擇該節(jié)點(diǎn)路徑時加入與問題相關(guān)的啟發(fā)性信息,指導(dǎo)搜索朝目標(biāo)方向進(jìn)行,用于搜索狀態(tài)空間的最短路徑[12-13]。A*算法是一種在靜態(tài)格網(wǎng)狀地圖上求最佳路徑的算法,為實(shí)現(xiàn)A*算法求解景區(qū)路徑規(guī)劃問題,需對景區(qū)影像進(jìn)行信息提取。對于不同類型地物,設(shè)定不同的緩沖區(qū)半徑及影響因子,生成不同屬性緩沖區(qū),創(chuàng)建包含多元空間信息的專題地圖;對專題地圖進(jìn)行離散化處理,生成規(guī)則的格網(wǎng)狀數(shù)字地圖,供算法實(shí)現(xiàn)最優(yōu)路徑的計(jì)算;在A*算法啟發(fā)式函數(shù)中添加緩沖區(qū)影響因子,實(shí)現(xiàn)緩沖區(qū)參與路徑規(guī)劃的思想。

2.1 A*算法思想

啟發(fā)式搜索是在狀態(tài)空間中對每一個搜索位置進(jìn)行評估并得出最好的位置,然后從這個位置再次進(jìn)行搜索評估,直至達(dá)到目標(biāo)節(jié)點(diǎn)。啟發(fā)式搜索可以省略大量無用的搜索路徑,提高了效率。在啟發(fā)式搜索中,對位置的評估十分重要[14]。

A*算法的估價(jià)函數(shù)可以表示為

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

(1)

其中:F(n)為估價(jià)函數(shù), 表示從起始點(diǎn)到目標(biāo)點(diǎn)的估計(jì)代價(jià);G(n)指在狀態(tài)空間中從初始節(jié)點(diǎn)到節(jié)點(diǎn)n的實(shí)際代價(jià);H(n)是節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)最佳路徑的估計(jì)代價(jià)。

最短路徑(最優(yōu)解)的關(guān)鍵在于H(n)的選取。

2.2 基本A*算法流程

2.3 基于景區(qū)緩沖區(qū)域的A*算法

在A*算法中,啟發(fā)式函數(shù)H(n)對路徑的生成速度和質(zhì)量有重要的影響,常用的啟發(fā)式函數(shù)計(jì)算方法有歐氏距離、曼哈頓距離和切比雪夫距離。本文采用曼哈頓距離作為啟發(fā)式函數(shù)計(jì)算的基本方法,在此基礎(chǔ)上,添加有關(guān)景區(qū)的影響因子,提高景區(qū)路徑規(guī)劃的精度。

曼哈頓距離是指在歐幾里得空間的固定直角坐標(biāo)系上,兩點(diǎn)所形成的線段對坐標(biāo)軸產(chǎn)生投影距離的總和。曼哈頓距離受坐標(biāo)系統(tǒng)轉(zhuǎn)度的影響,而非坐標(biāo)軸的平移或者映射。

在二維平面兩點(diǎn)a1(x1,y1) 與a2(x2,y2)間的曼哈頓距離

d12=|x1-x2|+|y1-y2|,

(2)

在原有的曼哈頓距離計(jì)算基礎(chǔ)上, 添加景區(qū)影響因子。 景區(qū)影響因子是對景區(qū)原本道路網(wǎng)、 景點(diǎn)區(qū)域、 水域以及各要素生成的緩沖區(qū)域設(shè)定一個系數(shù)θ, 用來表示某一類區(qū)域的權(quán)重值,其中0<θ≤1或者θ=∞。 權(quán)重值越小, 代表該區(qū)域可通行優(yōu)先級越高, 例如：景區(qū)道路網(wǎng)系數(shù)設(shè)定為1, 道路網(wǎng)緩沖區(qū)系數(shù)設(shè)定為0.8, 水域系數(shù)設(shè)定為∞。 計(jì)算公式為

d12=θ(|x1-x2|+|y1-y2|)，

(3)

因此, 面向景區(qū)路徑規(guī)劃的估價(jià)函數(shù)為

F(n)=G(n)+θ1H1(n)+θ2H2(n)+…+θmHm(n)，

(4)

式中:θmHm(n)表示某一類區(qū)域影響因子與該區(qū)域內(nèi)曼哈頓距離的乘積。在路況復(fù)雜多變的景區(qū),影響因子可以充分結(jié)合景區(qū)基本道路網(wǎng)和景區(qū)可通行區(qū)域,從而通過改進(jìn)后的A*算法輸出一條最優(yōu)路徑?；诰皡^(qū)緩沖區(qū)的A*算法流程見圖3。

3 七星公園景區(qū)路徑規(guī)劃系統(tǒng)設(shè)計(jì)

以廣西桂林市七星公園景區(qū)為例,驗(yàn)證基于A*算法的景區(qū)緩沖區(qū)路徑規(guī)劃的可行性。

3.1 數(shù)據(jù)準(zhǔn)備及處理

數(shù)據(jù)源采用天地圖發(fā)布的影像為基礎(chǔ)底圖,參考OpenStreetMap電子矢量地圖,結(jié)合實(shí)地考察結(jié)果,對七星公園景區(qū)道路網(wǎng)、休息活動區(qū)域、景區(qū)保護(hù)區(qū)域、景點(diǎn)游覽區(qū)域等進(jìn)行重新勾繪。使用ArcGIS空間分析工具箱中Buffer工具,對繪制好的矢量多要素圖層執(zhí)行緩沖區(qū)操作,分別設(shè)立不同緩沖區(qū)半徑的要素緩沖區(qū)域,結(jié)合原繪制好的矢量圖層,設(shè)定不同區(qū)域色彩灰度值,生成A*算法所需的24位真彩色、JPG格式專題地圖,專題地圖見圖4。

圖3 基于景區(qū)緩沖區(qū)域的A*算法流程Fig.3 A* Algorithm flow chart based on buffer area of scenic area

本文使用ENVI 5.1自帶的IDL編譯器,自行編寫了一套用于解譯圖像的腳本程序,遍歷離散化圖像的像元,將讀取到的像元值按一定順序存貯在二維數(shù)組中,生成供A*算法計(jì)算最優(yōu)路徑的“數(shù)組地圖”。

圖4 電子地圖Fig.4 Electronic map

3.2 路徑規(guī)劃及顯示

根據(jù)A*算法基本思想及改進(jìn)后適用于景區(qū)緩沖區(qū)算法原理, 自主編寫了一套景區(qū)路徑規(guī)劃系統(tǒng)。 系統(tǒng)讀取已勾繪完成的專題地圖,轉(zhuǎn)換為對應(yīng)的數(shù)組數(shù)據(jù), 識別像元RGB值, 判定緩沖區(qū)區(qū)域性質(zhì), 創(chuàng)建不同性質(zhì)緩沖區(qū)影響因子的A*算法。 基于緩沖區(qū)的A*算法根據(jù)各區(qū)域的影響因子, 計(jì)算每一次節(jié)點(diǎn)之間移動的代價(jià), 輸出一條由用戶輸入的起點(diǎn)及終點(diǎn)間的最佳路徑。 將實(shí)驗(yàn)結(jié)果和執(zhí)行傳統(tǒng)A*算法規(guī)劃路徑進(jìn)行對比分析, 驗(yàn)證了基于景區(qū)緩沖區(qū)的A*算法的有效性。 圖5是執(zhí)行傳統(tǒng)A*算法的路徑規(guī)劃結(jié)果, 圖6是經(jīng)緩沖區(qū)處理后,執(zhí)行改進(jìn)后的A*算法最優(yōu)路線。

圖5 傳統(tǒng)A*算法路徑規(guī)劃結(jié)果Fig.5 Traditional A* Algorithm path planning results

圖6 基于緩沖區(qū)A*算法路徑規(guī)劃結(jié)果Fig.6 Path planning results based on buffer A* Algorithm

實(shí)驗(yàn)結(jié)果表明,對影像執(zhí)行基本的繪制并作緩沖區(qū)處理后,景區(qū)內(nèi)部多元化的區(qū)域信息以可視化的方式加載在影像上,影像信息更加豐富。較傳統(tǒng)A*算法而言,添加緩沖區(qū)影響因子的A*算法,可有效結(jié)合景區(qū)道路網(wǎng)及多元區(qū)域的路況信息規(guī)劃出一條最佳行進(jìn)路線,為景區(qū)瀏覽提供參考信息。

4 結(jié)束語

地理信息系統(tǒng)是空間信息可視化的主要途徑，可通過對影像的繪制及處理,將影像數(shù)據(jù)信息以數(shù)字或圖像的方式呈現(xiàn)在計(jì)算機(jī)上,為影像使用者提供有力的空間決策支持。本文首先對景區(qū)影像進(jìn)行信息挖掘,得到所需的專題地圖;對專題地圖進(jìn)行離散化處理,生成A*算法所需的“數(shù)組地圖”;針對景區(qū)道路網(wǎng)及緩沖區(qū)域的特性對A*算法進(jìn)行改進(jìn),生成了一套適用于景區(qū)路徑規(guī)劃的軟件系統(tǒng),為景區(qū)觀光提供參考信息。

本文分析了一種適用于緩沖區(qū)的路徑規(guī)劃方法的可行性,但在實(shí)際應(yīng)用時,改進(jìn)的A*算法中緩沖區(qū)影響因子設(shè)定需考慮多方面因素,沒有一個統(tǒng)一的設(shè)定標(biāo)準(zhǔn)。因此，關(guān)于影響因子與緩沖區(qū)半徑及緩沖區(qū)域性質(zhì)之間的關(guān)系函數(shù),還有待進(jìn)一步研究。