一種改進(jìn)的分層路網(wǎng)的路徑規(guī)劃算法應(yīng)用

呂方興，方昕

一種改進(jìn)的分層路網(wǎng)的路徑規(guī)劃算法應(yīng)用

呂方興，方昕

為了提高路徑規(guī)劃效率，提出一種改進(jìn)的分層路網(wǎng)的路徑規(guī)劃算法。首先，城市路網(wǎng)進(jìn)行分層處理，以經(jīng)典A*算法為核心，在高層路網(wǎng)上使用改進(jìn)機(jī)制，評估函數(shù)做相應(yīng)調(diào)整，然后，對其權(quán)值設(shè)置上下限閾值，提高算法的搜索精度及搜索效率。實驗結(jié)果表明，規(guī)劃的路徑并非Dijkstra算法的最短，但是改進(jìn)的算法使快速路段所占比例達(dá)90%以上，實際運行最優(yōu)。

分層路網(wǎng)；路徑規(guī)劃；A*算法；Dijkstra算法

0 引言

交通擁擠、道路狀況已經(jīng)成為智能交通系統(tǒng)（Intelligent Transportation System，ITS）重點解決的問題，其中路徑規(guī)劃顯得尤為重要，即給定起點和終點，求解一條符合出行者心理需求的路徑。此路徑需要通過路徑搜索算法求得，路徑搜索可分為平面搜索和分層搜索兩類。平面搜索典型代表是Dijkstra最短路徑算法[1]，其時間復(fù)雜度為為O(n2)，效率較低。為了提高搜索效率，減少搜索范圍，后來學(xué)者提出帶有啟發(fā)函數(shù)的A*算法[2]等。但這些算法求解的路徑有時并非人們理想的“最優(yōu)”路徑，例如：司機(jī)希望在較寬的主干道上行駛，而并非小道小巷。于是，路網(wǎng)分層的思想及算法逐漸誕生[3-7]，但這些算法不能較好兼顧效率和準(zhǔn)確率。而本文視圖設(shè)計一種實用的改進(jìn)分層路徑規(guī)劃算法，首先建立分層路網(wǎng)，結(jié)合A*算法采用OPEN表排序提高搜索效率，然后改變啟發(fā)函數(shù)[8-9]改進(jìn)A*算法在高層路網(wǎng)上搜索，以當(dāng)前高層搜索節(jié)點到目標(biāo)節(jié)點的距離作為評估值，通過權(quán)值在某一規(guī)定區(qū)間上的變化來控制算法的搜索范圍和精度，最后通過實驗驗證改進(jìn)的路徑規(guī)劃算法搜索效果。

1 分層路網(wǎng)

根據(jù)出行者習(xí)慣可以對一個城市路網(wǎng)進(jìn)行分層處理，一般一個城市路網(wǎng)具有不同道路等級，目前我國將城市道路網(wǎng)絡(luò)分為快速路、主干路、次干路及支路等[10]，快速路和主干路路況較好，不易擁堵，符合人們出行需求，而次干路和支路易產(chǎn)生擁堵。所以，在進(jìn)行最短路徑規(guī)劃時，應(yīng)盡可能選擇高等級道路出行。但是，城市道路等級又不易劃分過多，否則數(shù)據(jù)存儲不便，因此本文將某市區(qū)MapInfo格式電子地圖分為兩層：高層路網(wǎng)包括城市快速道、主干道、國道、省道、縣道等且連通和低層路網(wǎng)包括次干道、支路、市區(qū)小道等且與高層保持連通。同時，添加道路等級，節(jié)點名稱及編號等重要屬性信息。每條路段都有各自編號、頭尾節(jié)點編號、路段距離、節(jié)點經(jīng)緯度坐標(biāo)、路段所在路網(wǎng)（0代表低層路網(wǎng)，1代表高層路網(wǎng)）。

2 分層A*算法

A*算法是一種啟發(fā)式路徑搜索算法，啟發(fā)式搜索主要體現(xiàn)在評估函數(shù)：f(n)=g(n)+h(n)，f(n)代表從起點經(jīng)由擴(kuò)展點n到達(dá)終點的耗費，g(n)是起點到擴(kuò)展點n的實際代價，可能被更新，h(n)是擴(kuò)展點n到終點的估價值，保持不變。當(dāng)h(n)總小于等于從n點到終點的實際代價值時，能保證得到最優(yōu)解[11]啟發(fā)函數(shù)h(n)采用擴(kuò)展點到終點的歐氏距離，當(dāng)h(n)=0時，f(n)=g(n)即演變?yōu)镈ijkstra算法。因此，h(n)的選取是算法求解關(guān)鍵也是高層路網(wǎng)節(jié)點選取的切入點，可進(jìn)一步縮小搜索空間，只存儲快速路段。

分層A*算法首先判斷起點與終點之間的歐式距離，當(dāng)距離長時采用分層計算，當(dāng)距離短時采用傳統(tǒng)A*算法計算。分層計算分為三個階段，前兩個階段分別從起點S和終點T出發(fā)，搜索高層路網(wǎng)的入口與出口節(jié)點（S1和T1），計算過程采用傳統(tǒng)A*算法；第三階段以S1和T1為高層路網(wǎng)的起點終點搜索一條路徑，采用改進(jìn)的算法求解。這種分層算法最終可以規(guī)劃得到一條“S->S1->T1->T”的路徑，此路徑也許不是最短距離但卻是最優(yōu)選擇。

3 改進(jìn)算法及實現(xiàn)

改進(jìn)算法[12]主要體現(xiàn)在高層路段即“S1->T1”，對評估函數(shù)f(n)=g(n)+h(n)的調(diào)整，算法思想：（1）獲得S1和T1經(jīng)緯度坐標(biāo)計算兩點間直線距離D。（2）計算當(dāng)前節(jié)點的一個鄰接點到終點T1的直線距離D1，若D1>D，則權(quán)值w=Q，Q小于1的常數(shù)，W∈[L，H]；否則W=D1 /D，W∈[L，H]，L和H是距離長度單位為m，根據(jù)經(jīng)驗設(shè)定。（3）啟發(fā)函數(shù)修改為：f(n)=(1-w)*g(n)+w*h(n)，選取評估函數(shù)值最小的節(jié)點作為下一個當(dāng)前節(jié)點。如此循環(huán)直到當(dāng)前節(jié)點為T1為止，即找到了“S1->T1”的路徑。設(shè)置w可以雙重保證搜索效率和搜索精度，而算法時間復(fù)雜度最壞理論值為O（n2）。但是，由于在實際的路網(wǎng)中關(guān)聯(lián)節(jié)點并不多且高層關(guān)聯(lián)節(jié)點更少，改進(jìn)A*算法在對OPEN表和CLOSE表掃描時時間復(fù)雜度可認(rèn)為O（Cn），明顯優(yōu)于Dijkstra算法。

每個階段算法實現(xiàn)的具體步驟如下：

初始化的狀態(tài)：起點S，終點T，g(0)=0，h(0)=D(S，T)，f(0)=g(0)+h(0)，并將起點加入開啟列表，采用最小二叉堆管理開啟列表，使用OPEN表和CLOSE表。OPEN表存儲最小臨時節(jié)點，CLOSE表存儲永久節(jié)點，每次循環(huán)從OPEN表選點并將其轉(zhuǎn)為永久點。

（1）加載路網(wǎng)，設(shè)定初始狀態(tài)。

（2）判斷OPEN表是否為空，如果為空則尋路失敗，退出循環(huán)；否則轉(zhuǎn)向（3）。

（3）獲得S和T所在路網(wǎng)層次，判斷是否采用改進(jìn)的A*算法，若為高層節(jié)點則采用改進(jìn)A*算法，否則轉(zhuǎn)入（4）。

（4）搜索OPEN表和CLOSE表，采用經(jīng)典A*算法，找到由低層到高層的節(jié)點S1和T1，求解路徑“S→S1”和“T1→T”。

（5）采用改進(jìn)A*算法，求解路徑“S1→T1”。

（6）連接三條路徑“S→S1→T1→T”為最優(yōu)路徑，算法結(jié)束。

4 實驗結(jié)果及分析

本系統(tǒng)采用某市區(qū)地圖數(shù)據(jù)，將此算法在Visual Studio2005.net環(huán)境下用VC++編程實現(xiàn)，采用MapInfo8.0，MapX5.0整理和加載數(shù)據(jù)。為了更好統(tǒng)計算法性能，以實際道路長度和搜索時間作為參考，分別用Dijkstra算法、分層A*算法和改進(jìn)的A*算法計算兩個節(jié)點的最優(yōu)路徑，并在地圖上使用不同顏色粗線條顯示，隨機(jī)選取幾對起止點，統(tǒng)計各個算法搜索結(jié)果如圖1、圖2和表1所示：

圖1 節(jié)點1025-1110各個算法搜索結(jié)果

圖2 節(jié)點2325-1121各個算法搜索結(jié)果

表1 路徑長度統(tǒng)計對比

圖中藍(lán)色線路為Dijkstra算法結(jié)果，黃色線路為分層A*算法結(jié)果，紅色線路為改進(jìn)算法結(jié)果。

硬件環(huán)境：Intel(R) Core(TM)2 CPU 6320，1.0GB；

操作系統(tǒng)：Microsoft Windows XP；

軟件環(huán)境：Visual Studio2005，MapInfo8.0，MapX5.0;

從圖1和圖2中可以看到，分層A*算法和改進(jìn)A*算法搜索路徑主要以高層主干道為主，選取路況環(huán)境相對較好的道路，這樣通常符合人們出行需求。從表1中也可看到，分層A*算法和改進(jìn)A*算法搜索路徑長度不一定最短。這是因為在選取主干道和快速道時可能會出現(xiàn)繞道情況。但是，改進(jìn)的A*算法搜索路徑長度較為接近最短，接近程度取決于參數(shù)w值(經(jīng)驗值），這說明改進(jìn)算法能在一定程度上提高算法搜索精度。表2中各個算法求解時間會隨著路徑增長而加大，Dijkstra 算法增長最快，改進(jìn)A*算法次之。Dijkstra 算法雖然能夠找到最短路徑，但是會隨著路徑長度增長搜索節(jié)點大幅增加。而改進(jìn)A*算法會根據(jù)評估函數(shù)找到高層節(jié)點，減小搜索范圍，提高了算法搜索效率。綜合上述分析，改進(jìn)后的算法即在一定程度上保證了搜索精度，又提高了算法運行時間，符合人們出行需求。

本文首先對實際路網(wǎng)進(jìn)行分層處理，采用啟發(fā)式搜索算法和二叉堆隊列管理搜索列表實現(xiàn)路徑規(guī)劃。同時，為了提高算法搜索精度和搜索效率，對分層A*算法進(jìn)行改進(jìn)，修改評估函數(shù)，增加了權(quán)值。實驗表明，改進(jìn)后的算法總體優(yōu)于原算法，并能夠應(yīng)用于實際的城市路網(wǎng)，但算法性能穩(wěn)定性有待提升。

[1] Dijkstra E W.A note on two problems in connection with graphs[J].Numerische Mathematik, 1959,1 (1):269-271.

[2] Hart P E, Nilsson N J, Raphael B.A formal basis for the heuristic determination of minimum cost paths [J].IEEE Transactions on Systems Science and Cybernetics,1968,14 (3): 100-107.

[3] 李建元,師軍．基于層次空間推理模型的交通網(wǎng)絡(luò)最優(yōu)路徑算法［J］．計算機(jī)工程,2006,32( 20) : 207 - 209．

[4] 李清泉,鄭年波,徐敬海等．一種基于道路網(wǎng)絡(luò)層次拓?fù)浣Y(jié)構(gòu)的分層路徑規(guī)劃算法［J］.中國圖象圖形學(xué)報,2007,12(7) : 1280-1285.

[5] CAR A. Hierarchical spatial reasoning: theoretical consideration and its application to modeling way finding［D］. Vienna: Technical University of Vienna,1997．

[6] CHOU Y, ROMEIJN H E,SMITH R L. Approximating shortest paths in large-scale networks with an application to intelligent transportation systems［J］. Informs Journal on Computing Spring, 1998,10( 2) : 163-179．

[7] 李建元,師軍,曹菡等. 一種分層尋路算法中的閾值放棄策略［J］. 計算機(jī)應(yīng)用,2007,27( 2) : 473-478.

[8] Chen Xi. A new shortest path algorithm based on heuristic strategy[C]//Proceedings of the 6th World Congress on Intelligent Control and Automation (WCICA 2006), 2006:2531-2536.

[9] Qi Minju, Sun Huaining, Gao Guangfa. Research on an improved algorithm for shortest path searching in urban traffic based on GIS[C]//Proceedings of Electrical and Control Engineering International Conference, 2011: 1184-1187.

[10] 高立兵.汽車導(dǎo)航系統(tǒng)的動態(tài)路徑規(guī)劃優(yōu)化模型與算法研究[J].甘肅聯(lián)合大學(xué)學(xué)報:自然科學(xué)版,2012,26(1):55 -58.

[11] DAI Z Q, GUAN Y, GUAN R. Dynamicadjustment A* routing algorithm［C］./ / 2010 International Conference on Innovative Computing and Communication. Washington, DC: IEEE Computer Society,2010: 316-318.

[12] 錢紅昇,葛文鋒,鐘鳴等. 基于分層的改進(jìn)A*算法在路徑規(guī)劃中的應(yīng)用[J]計算機(jī)工程與應(yīng)用,2014,50(7):225-229.

5 總結(jié)

基于硬件的交互，另一種是基于計算機(jī)視覺的交互?；谟布慕换バ枰容^昂貴的電磁式或光學(xué)式等跟蹤設(shè)備，而且這些設(shè)備往往比較笨重，不便于攜帶，使交互操作受到一定的限制?；谟嬎銠C(jī)視覺的交互包括基于智能識別技術(shù)的交互。目前，識別目標(biāo)不再局限于之前的黑白marker，而是把范圍擴(kuò)大到普通的2D圖片以及現(xiàn)實中的立體物體，如照片、logo、海報的識別、人體識別技術(shù)、人臉、手勢等識別等。而且對識別對象的識別響應(yīng)速度也得到了大大提高，解決了識別的局限性的問題，增加了增強(qiáng)現(xiàn)實類產(chǎn)品的實用性。

3）跟蹤注冊

跟蹤注冊是為了使用戶在真實環(huán)境的運動過程中保持虛擬場景在真實環(huán)境中的存在性和一體性。隨著先進(jìn)的2D圖片跟蹤及現(xiàn)實3D物體跟蹤技術(shù)的發(fā)展，物體跟蹤技術(shù)的穩(wěn)定性有了明顯的提高，能夠進(jìn)行識別的距離和范圍都有了很大的提升，能最大程度的保證虛擬物體不丟失。跟蹤注冊技術(shù)效果的好壞直接決定增強(qiáng)現(xiàn)實系統(tǒng)的成功與否。

1.2 增強(qiáng)現(xiàn)實的應(yīng)用領(lǐng)域：

溯江而下，江面的水產(chǎn)養(yǎng)殖，一度成為生態(tài)公害。珍珠、漁業(yè)這些新興產(chǎn)業(yè)給村民帶來財富的同時，也付出著昂貴的生態(tài)代價。

目前，增強(qiáng)現(xiàn)實技術(shù)應(yīng)用的領(lǐng)域越來越廣泛，如在市場營銷上可采用AR互動大屏的方式，使現(xiàn)場的人與里面的虛擬場景進(jìn)行互動，這樣消費者更容易接受，更有親切感和具傳播性，如圖3所示：

在移動端AR的應(yīng)用上，用戶可以掃下優(yōu)惠卷就可以看到真實的優(yōu)惠商品；掃下購買后的商品可以聽到一首歌、一段視頻、一個游戲或是其他有趣的互動；掃下餐桌就可以出現(xiàn)3D菜單隨意搭配自己想吃的口味，這樣有趣的體驗，更利用產(chǎn)品營銷推廣。還如現(xiàn)在的3D試衣體驗和谷歌眼鏡用的就是增強(qiáng)現(xiàn)實技術(shù)。另外在其他的醫(yī)療、軍事、電視轉(zhuǎn)播等各方面都有應(yīng)用，如圖4所示：

2 基于AR-Builder的增強(qiáng)現(xiàn)實應(yīng)用

2.1 增強(qiáng)現(xiàn)實編輯器（AR-Builder）

增強(qiáng)現(xiàn)實編輯器（AR-Builder）是由中視典公司在虛擬現(xiàn)實編輯器（VRP）的基礎(chǔ)上開發(fā)的，面向增強(qiáng)現(xiàn)實行業(yè)的編輯器。它既具有VRP的絕大部分基礎(chǔ)功能又包括了AR的核心技術(shù)。它可以讓不懂編程的用戶也能用PC/移動端針對動作捕捉設(shè)備創(chuàng)建增強(qiáng)現(xiàn)實互動應(yīng)用。

增強(qiáng)現(xiàn)實編輯器使用了先進(jìn)的2D圖片跟蹤及現(xiàn)實3D物體跟蹤技術(shù)，在5米之外仍然能夠識別對象。即使識別對象被遮擋只剩1/32時，軟件仍能保證虛擬物體不丟失。

2.2 在主題公園互動的應(yīng)用

在公園互動區(qū)域內(nèi)，可以通過AR互動方式可以讓游客進(jìn)入虛擬地社區(qū)環(huán)境中，也可選擇喜歡的場景，感覺親臨現(xiàn)場；讓游客和各種動畫人物親密接觸、拍照留念，也可以讓動畫人物和游客互動。 下面以迪斯尼樂園案例為例，介紹下基于增強(qiáng)現(xiàn)實編輯器（AR-Builder）的AR互動的具體操作流程：

1）先安裝好3dsMax軟件、再安裝AR-Builder和VRP-for-3dsMAX插件，安裝的路徑選擇3dsMax的安裝路徑，這樣會發(fā)現(xiàn)3dsMax工具集中會多了一個[*VRPlatform*]菜單，如圖5所示：

然后通過VRP_For_Max插件中的“導(dǎo)出”命令保存場景至.vrp文件。

3）打開AR-Builder，導(dǎo)入剛剛保存的vrp文件，從“增強(qiáng)現(xiàn)實”菜單中選擇“插入節(jié)點”菜單項，將在界面左側(cè)的場景樹中增加一個新的“增強(qiáng)現(xiàn)實 1”節(jié)點，如圖7所示：

圖3 AR互動大屏的應(yīng)用

圖4 增強(qiáng)現(xiàn)實應(yīng)用領(lǐng)域

圖5 VRPlatform插件

圖6 創(chuàng)建模型

圖7 添加節(jié)點

4）選擇識別對象：點擊選擇上一步中新建好的“增強(qiáng)現(xiàn)實 1”節(jié)點，界面右側(cè)的屬性欄中將顯示此節(jié)點的屬性。通過在屬性欄中的“從庫中選擇卡片”、 “選擇自定義圖片”、“綁定KINECT動作”3個按鈕選項，可分別設(shè)置黑白卡片（Marker）、普通圖像與手勢動作3種識別對象。

5）添加展示的虛擬內(nèi)容：展示內(nèi)容是指當(dāng)識別到卡片或圖像時，在其上疊加的對象。通過在“增強(qiáng)現(xiàn)實 1”節(jié)點屬性欄中選擇“綁定視頻”，或?qū)⑾胍砑拥娜S物體拖到“增強(qiáng)現(xiàn)實 1”節(jié)點之下，可添加視頻與三維模型兩種展示內(nèi)容。

6）添加交互腳本：通過腳本事件來實現(xiàn)交互目的。

7）測試運行：先將攝像頭連接好，再點擊 “測試運行”按鈕，程序?qū)㈤_啟攝像頭。將攝像頭對準(zhǔn)識別對象，在其上將顯示疊加的展示內(nèi)容，如圖8所示：

圖8 選擇識別對象

8）發(fā)布：點擊工具欄上的“發(fā)布EXE包”按鈕和 “發(fā)布IOS工程包”按鈕，可分別發(fā)布到PC端和移動端。

9）通過攝像頭獲取現(xiàn)場畫面，將將現(xiàn)場畫面與虛擬場景融合后輸出。

10）捕捉現(xiàn)場體驗者的動作，電腦主機(jī)接收到動作信號后，觸發(fā)虛擬場景動作，完成交互，如圖9、圖10、圖11所示：

圖9 綁定視頻

圖10 識別對象

圖11 體驗著交互

3 總結(jié)

雖然受到一些計算機(jī)視覺算法和移動設(shè)備硬件的限制，目前增強(qiáng)現(xiàn)實技術(shù)的潛力還遠(yuǎn)遠(yuǎn)沒有發(fā)揮出來。將來隨著這個問題的逐漸改善，我們所能體驗到的視覺空間將得到極大延展。市場發(fā)展的腳步從不會停歇，增強(qiáng)現(xiàn)實技術(shù)應(yīng)用前景是很廣闊的。據(jù)美國市場研究分析公司ABI research的預(yù)測：增強(qiáng)現(xiàn)實的開發(fā)商將會在增強(qiáng)現(xiàn)實這個應(yīng)用上投資巨大金額，分析師還認(rèn)為“AR”這個應(yīng)用將會成為“更加日常化的移動設(shè)備應(yīng)用的一部分”尤其在市場營銷、車載系統(tǒng)、游戲娛樂和醫(yī)學(xué)醫(yī)療等領(lǐng)域?qū)⒌玫皆絹碓綇V泛的應(yīng)用。增強(qiáng)現(xiàn)實技術(shù)將成為展覽展示的趨勢；增強(qiáng)現(xiàn)實技術(shù)將成為市場營銷的賣點；憑借車速和車距計算出行車安全性，AR技術(shù)能顯示出對空間的感知能力，結(jié)合增強(qiáng)現(xiàn)實技術(shù)的車載系統(tǒng)將成為汽車標(biāo)配；增強(qiáng)現(xiàn)實讓游戲娛樂拉進(jìn)現(xiàn)實；增強(qiáng)現(xiàn)實成為醫(yī)生的“助手”；增強(qiáng)現(xiàn)實讓圖書更立體更互動。

參考文獻(xiàn)

[1] 吳帆,張亮.增強(qiáng)現(xiàn)實技術(shù)發(fā)展及應(yīng)用綜述.電腦知識和技術(shù).2012.

[2] 王貞東,肖租秀.增強(qiáng)現(xiàn)實應(yīng)用研究.玉林師范學(xué)院學(xué)報(自然科學(xué)).2012.

[3] F. Niebling,etal. Using Augmented Reality and Interactive Simulations to Realize Hybrid Prototypes. in 4th International Symposiumon Visual Computing,Las Vegas,NV, 2008.

[4] Dengzhe Ma, Jurgen Gausemeier, Michael Grafe.虛擬現(xiàn)實與增強(qiáng)現(xiàn)實技術(shù)及其工業(yè)應(yīng)用.上海交通大學(xué)出版社,2011.

（收稿日期：2014.11.16）

Application of an Improved Layered Path Planning Algorithm on Road Network

Lv Fangxing, Fang Xin
(Department of Electronic and Information Engineering, Ankang University, Ankang725000, China)

In order to improve the efficiency of path planning, an improved hierarchical path planning algorithm is been proposed on road network. First, classical A* algorithm as the core, urban road network is layered. Using an improved mechanism for high-level road network, the evaluation function is adjusted accordingly. Its weight is set upper and lower threshold to improve search accuracy and search efficiency. Experimental results show that the path planning length is not Dijkstra shortest, but the improved algorithm enables rapid road proportion is more than 90% and the actual operation of the optimum.

Hierarchical Road Network; Path Planning; A* Algorithm; Dijkstra Algorithm

TP311

A

2014.08.29）

1007-757X(2015)1-0059-03

陜西省教育廳自然科學(xué)專項項目（NO.14JK1014）；安康學(xué)院高層次人才項目專項（NO.AYQDZR201204）；安康學(xué)院高層次人才項目專項（NO.AYQDZR201203）；安康學(xué)院教材建設(shè)基金項目（NO.Jc201307）

呂方興（1985-），男，黃淮學(xué)院，信息工程學(xué)院，助教，碩士，研究方向：測控技術(shù)，電氣工程，安康，725000

方 昕（1985-），女，安康學(xué)院，電子與信息工程系，講師，碩士，研究方向：智能優(yōu)化、數(shù)據(jù)挖掘，安康，725000