一種基于緩沖區分析的A*算法路徑規劃

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

(1.桂林理工大學 a.廣西空間信息與測繪重點實驗室;b.測繪地理信息學院,廣西 桂林 541006;2.廣東省土地調查規劃院，廣州 510075)

0 引 言

地理信息系統是一種采集、存儲、管理、分析、顯示和應用地理信息的計算機系統,是分析和處理海量地理數據的通用技術。GIS空間分析是對地理空間中目標的空間關系和空間行為進行描述,為目標的空間查詢和空間相關分析提供參考,進一步為空間決策提供服務的技術。空間分析是地理信息系統區別于一般信息系統、CAD或電子地圖系統的主要功能特征,是GIS的核心和靈魂[1-2]。

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

本文提出一種基于GIS空間分析的A*算法路徑規劃方法,通過對景區空間地理數據進行整理編輯,將景區空間信息進行可視化表達,并對空間信息進行充分解譯與利用,結合A*算法,對傳統路徑規劃方法加以改進,優化旅游路線。

1 專題地圖的生成與解譯

1.1 GIS緩沖區分析

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

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

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

1.2 影像數字信息提取

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

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

圖1 點、線、面緩沖區示意圖Fig.1 Buffer schematic of point, line and surface

圖2 影像數字信息提取實例Fig.2 Image digital information extraction example

2 基于A*算法的景區路徑規劃

A*算法的主體思想是在搜索下一個節點并選擇該節點路徑時加入與問題相關的啟發性信息,指導搜索朝目標方向進行,用于搜索狀態空間的最短路徑[12-13]。A*算法是一種在靜態格網狀地圖上求最佳路徑的算法,為實現A*算法求解景區路徑規劃問題,需對景區影像進行信息提取。對于不同類型地物,設定不同的緩沖區半徑及影響因子,生成不同屬性緩沖區,創建包含多元空間信息的專題地圖;對專題地圖進行離散化處理,生成規則的格網狀數字地圖,供算法實現最優路徑的計算;在A*算法啟發式函數中添加緩沖區影響因子,實現緩沖區參與路徑規劃的思想。

2.1 A*算法思想

啟發式搜索是在狀態空間中對每一個搜索位置進行評估并得出最好的位置,然后從這個位置再次進行搜索評估,直至達到目標節點。啟發式搜索可以省略大量無用的搜索路徑,提高了效率。在啟發式搜索中,對位置的評估十分重要[14]。

A*算法的估價函數可以表示為

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

(1)

其中:F(n)為估價函數, 表示從起始點到目標點的估計代價;G(n)指在狀態空間中從初始節點到節點n的實際代價;H(n)是節點n到目標節點最佳路徑的估計代價。

最短路徑(最優解)的關鍵在于H(n)的選取。

2.2 基本A*算法流程

2.3 基于景區緩沖區域的A*算法

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

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

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

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

(2)

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

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

(3)

因此, 面向景區路徑規劃的估價函數為

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

(4)

式中:θmHm(n)表示某一類區域影響因子與該區域內曼哈頓距離的乘積。在路況復雜多變的景區,影響因子可以充分結合景區基本道路網和景區可通行區域,從而通過改進后的A*算法輸出一條最優路徑。基于景區緩沖區的A*算法流程見圖3。

3 七星公園景區路徑規劃系統設計

以廣西桂林市七星公園景區為例,驗證基于A*算法的景區緩沖區路徑規劃的可行性。

3.1 數據準備及處理

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

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

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

圖4 電子地圖Fig.4 Electronic map

3.2 路徑規劃及顯示

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

圖5 傳統A*算法路徑規劃結果Fig.5 Traditional A* Algorithm path planning results

圖6 基于緩沖區A*算法路徑規劃結果Fig.6 Path planning results based on buffer A* Algorithm

實驗結果表明,對影像執行基本的繪制并作緩沖區處理后,景區內部多元化的區域信息以可視化的方式加載在影像上,影像信息更加豐富。較傳統A*算法而言,添加緩沖區影響因子的A*算法,可有效結合景區道路網及多元區域的路況信息規劃出一條最佳行進路線,為景區瀏覽提供參考信息。

4 結束語

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

本文分析了一種適用于緩沖區的路徑規劃方法的可行性,但在實際應用時,改進的A*算法中緩沖區影響因子設定需考慮多方面因素,沒有一個統一的設定標準。因此，關于影響因子與緩沖區半徑及緩沖區域性質之間的關系函數,還有待進一步研究。