呂方興，方昕

一種改進(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ī)制，評(píng)估函數(shù)做相應(yīng)調(diào)整，然后，對(duì)其權(quán)值設(shè)置上下限閾值，提高算法的搜索精度及搜索效率。實(shí)驗(yàn)結(jié)果表明，規(guī)劃的路徑并非Dijkstra算法的最短，但是改進(jìn)的算法使快速路段所占比例達(dá)90%以上，實(shí)際運(yùn)行最優(yōu)。

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

0 引言

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

1 分層路網(wǎng)

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

2 分層A*算法

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

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

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

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果及分析

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

圖1 節(jié)點(diǎn)1025-1110各個(gè)算法搜索結(jié)果

圖2 節(jié)點(diǎn)2325-1121各個(gè)算法搜索結(jié)果

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

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

本文首先對(duì)實(shí)際路網(wǎng)進(jìn)行分層處理，采用啟發(fā)式搜索算法和二叉堆隊(duì)列管理搜索列表實(shí)現(xiàn)路徑規(guī)劃。同時(shí)，為了提高算法搜索精度和搜索效率，對(duì)分層A*算法進(jìn)行改進(jìn)，修改評(píng)估函數(shù)，增加了權(quán)值。實(shí)驗(yàn)表明，改進(jìn)后的算法總體優(yōu)于原算法，并能夠應(yīng)用于實(shí)際的城市路網(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ì)算機(jī)工程,2006,32( 20) : 207 - 209．

[4] 李清泉,鄭年波,徐敬海等．一種基于道路網(wǎng)絡(luò)層次拓?fù)浣Y(jié)構(gòu)的分層路徑規(guī)劃算法［J］.中國圖象圖形學(xué)報(bào),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ì)算機(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)的動(dòng)態(tài)路徑規(guī)劃優(yōu)化模型與算法研究[J].甘肅聯(lián)合大學(xué)學(xué)報(bào):自然科學(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ì)算機(jī)工程與應(yīng)用,2014,50(7):225-229.

5 總結(jié)

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

3）跟蹤注冊(cè)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖5 VRPlatform插件

圖6 創(chuàng)建模型

圖7 添加節(jié)點(diǎn)

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

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

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

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

圖8 選擇識(shí)別對(duì)象

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

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

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

圖9 綁定視頻

圖10 識(shí)別對(duì)象

圖11 體驗(yàn)著交互

3 總結(jié)

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

參考文獻(xiàn)

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

[2] 王貞東,肖租秀.增強(qiáng)現(xiàn)實(shí)應(yīng)用研究.玉林師范學(xué)院學(xué)報(bào)(自然科學(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)實(shí)與增強(qiáng)現(xiàn)實(shí)技術(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é)專項(xiàng)項(xiàng)目（NO.14JK1014）；安康學(xué)院高層次人才項(xiàng)目專項(xiàng)（NO.AYQDZR201204）；安康學(xué)院高層次人才項(xiàng)目專項(xiàng)（NO.AYQDZR201203）；安康學(xué)院教材建設(shè)基金項(xiàng)目（NO.Jc201307）

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

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