葉小艷，鐘華鈞，鄧可兒

(廣州軟件學(xué)院 網(wǎng)絡(luò)技術(shù)系，廣東 廣州 510990)

0 引 言

室內(nèi)導(dǎo)航是指在各種室內(nèi)空間中采用不同技術(shù)來實現(xiàn)人員室內(nèi)導(dǎo)航以及對人員、物體的定位與跟蹤。其關(guān)鍵技術(shù)主要涉及三個方面：室內(nèi)導(dǎo)航定位技術(shù)、室內(nèi)路徑規(guī)劃技術(shù)和室內(nèi)地圖構(gòu)建。路徑規(guī)劃是室內(nèi)導(dǎo)航的關(guān)鍵技術(shù)之一，按照某一性能指標(biāo)(如距離、時間、目標(biāo)等)搜索一條從起始狀態(tài)到目標(biāo)狀態(tài)的最優(yōu)或次優(yōu)路徑。目前，已有多種算法和方案的研究用于解決室內(nèi)導(dǎo)航路徑規(guī)劃問題。文獻[3]提出了一種改進啟發(fā)式飄逸消除算法，消除室內(nèi)環(huán)境中行人導(dǎo)航定位算法中的漂移誤差。文獻[4]結(jié)合室內(nèi)導(dǎo)航的魯棒特征跟蹤要求，提出了一種基于圖形處理器的加速策略，在實時導(dǎo)航時減少誤匹配機會。文獻[5]描述了一種新的地圖輔助模糊決策樹(FDT)，減少累積誤差，提高生成能力和最小化基礎(chǔ)設(shè)施的使用。文獻[6]改進地圖匹配算法，提高商場室內(nèi)導(dǎo)航地圖定位引擎的定位精度。謝民提出一種改進的蟻群算法來解決道路交通導(dǎo)航系統(tǒng)中以加權(quán)路徑網(wǎng)的以路徑長度與通行時間的線性組合為目標(biāo)函數(shù)的優(yōu)化問題。王中玉提出了一種基于A*算法改進的高效路徑規(guī)劃算法，解決規(guī)劃路徑存在的冗余點和拐點的問題。趙柯柯研究了室內(nèi)停車場的路徑規(guī)劃算法與導(dǎo)航，陶文瀚構(gòu)建了基于改進型蜻蜓算法的物流配送過程中的車輛路徑模型。王文東、周嶸針對機器人室內(nèi)路徑規(guī)劃算法，開展了A*算法的室內(nèi)路徑規(guī)劃研究。很明顯，A *算法是解決路徑規(guī)劃最優(yōu)問題的一種比較常用并且高效的算法。在大型建筑體內(nèi)環(huán)境(如大型商場、大型購物中心、復(fù)雜寫字樓、展覽館等)，運用A*算法按切身需求來規(guī)劃最佳路徑，尤其遇到緊急情況時，科學(xué)的路徑規(guī)劃方法可以根據(jù)出入口的人流量和通過權(quán)限做出調(diào)整。目前A*算法在解決室內(nèi)導(dǎo)航問題上，從起點開始，以一定的步長擴展節(jié)點，選擇路徑長度最小的節(jié)點作為擴展節(jié)點，然后逐步擴展，直至到達終點。在數(shù)值優(yōu)化算法方面，當(dāng)區(qū)域的點數(shù)量較少時，效率是非常高的。但是如果路徑點的規(guī)模較大，當(dāng)使用數(shù)值優(yōu)化算法求解最佳路徑時，難度將會急劇增加，從而導(dǎo)致規(guī)劃時間所需時間過長，明顯不符合實時性要求。

因此，為提高路徑規(guī)劃方法中的效率和穩(wěn)定性，達到加速導(dǎo)航算法的目的，采用分層計算的思想對普通A*算法進行優(yōu)化，提出了一種改進型A*算法優(yōu)化的方案。經(jīng)過算法效率測試，改進型A*算法在室內(nèi)導(dǎo)航路徑規(guī)劃的效率和穩(wěn)定性比較優(yōu)。

1 A*算法

作為一種常見的全局路徑規(guī)劃算法，A*算法在靜態(tài)路網(wǎng)中運用廣泛，對于找尋最優(yōu)路徑是最有效的直接搜索方法。目前在A*算法運用方面，很多相關(guān)的解決方案都是在A*算法的基礎(chǔ)上進行優(yōu)化和使用的。如微軟硅谷研究院提出的Crp算法(customizable route planning，可定制路線規(guī)劃)，與傳統(tǒng)的A-star(即A*算法)，基本支撐了目前工業(yè)界地圖產(chǎn)品的路徑規(guī)劃服務(wù)。Bian等提出了一種用戶偏好建模和獲取的方法，考慮用戶偏好對傳統(tǒng)的A*算法進行了改進，并通過實例說明了個性化A*算法的優(yōu)越性。邱磊提出將跳點搜索算法的思想融入傳統(tǒng)的A*算法，通過在柵格地圖中定義關(guān)鍵節(jié)點來保證獲得最優(yōu)路徑的同時提高尋路速度，有效減少了內(nèi)存開銷。但傳統(tǒng)的A*算法在室內(nèi)導(dǎo)航規(guī)劃尋徑過程中，出現(xiàn)大量無用節(jié)點，重復(fù)搜尋，導(dǎo)致尋徑耗時過長，搜索節(jié)點數(shù)量過多，搜索效果不佳。

1.1 A*算法的基本思想與實現(xiàn)步驟

A*算法的基本思想主要是在規(guī)劃最優(yōu)路徑的前提下運用啟發(fā)函數(shù)引導(dǎo)搜索，A*算法的啟發(fā)函數(shù)為

F

()=

G

()+

H

()，其中

F

()表示節(jié)點

n

從初始點到目標(biāo)點的函數(shù)，

H

()表示從當(dāng)前節(jié)點到目標(biāo)節(jié)點的估計代價，

G

()表示從起始節(jié)點到當(dāng)前節(jié)點的距離。每一次選擇最小代價的節(jié)點作為下一個處理節(jié)點。

其實現(xiàn)步驟用偽代碼表示如下：

創(chuàng)建開啟列表、關(guān)閉列表

將起始點加入開放列表中

彈出開啟列表的第一個節(jié)點，將該元素作為當(dāng)前節(jié)點

while(當(dāng)前節(jié)點不為終點時)：

獲取并處理當(dāng)前節(jié)點的周圍可通過的節(jié)點，

為這些節(jié)點設(shè)置

G

值、

H

值，

添加當(dāng)前節(jié)點為這些可通過節(jié)點的父節(jié)點

遍歷當(dāng)前節(jié)點的周圍節(jié)點

if(該節(jié)點可通過且不在關(guān)閉列表):

if(該節(jié)點在開啟列表):

根據(jù) 估價函數(shù)

F

()進行比較

if(開啟列表的節(jié)點的估價函數(shù)大于該節(jié)點的估價函數(shù)):

將開啟列表的節(jié)點進行覆蓋

else:

將該節(jié)點加入開啟列表

將當(dāng)前節(jié)點添加到關(guān)閉列表中

對開啟列表進行排序

當(dāng)前節(jié)點<-獲得開啟列表的第一個元素

創(chuàng)建一個路徑結(jié)果集

while(當(dāng)前節(jié)點的父節(jié)點不為空):

獲得當(dāng)前節(jié)點的索引，存入路徑結(jié)果集中

當(dāng)前節(jié)點<-當(dāng)前節(jié)點的父節(jié)點

返回路徑結(jié)果集

結(jié)束

1.2 室內(nèi)導(dǎo)航中A*路徑算法存在的問題

A*路徑算法在路徑搜索過程中，刪除了大量的節(jié)點，導(dǎo)致產(chǎn)生的結(jié)果可能不是最優(yōu)路徑。但由于該算法是用于室內(nèi)導(dǎo)航的，所以這種可能的發(fā)生率非常小。

另一方面在大型建筑體內(nèi)導(dǎo)航中，由于室內(nèi)建筑體復(fù)雜加深，有些建筑(如大型商場等)經(jīng)營面積巨大，且可利用空間非常多，再加上商城導(dǎo)航中一層地圖如果節(jié)點劃分越細，那么導(dǎo)航代價就越高，所以每一次利用A*算法時，都需要進行大量的搜索和估價。需要處理的節(jié)點非常多，當(dāng)節(jié)點數(shù)量增加時，算法需要的時間成指數(shù)增長，嚴重影響了路徑規(guī)劃的效率和成本。傳統(tǒng)的A*算法將規(guī)劃目標(biāo)視為質(zhì)點，規(guī)劃出的路徑實際很可能會觸碰到障礙物，使得規(guī)劃路徑較長。

2 室內(nèi)導(dǎo)航中A*算法的改進

2.1 改進的A*算法的基本思想

如上所述，在商城導(dǎo)航中，需要處理的節(jié)點數(shù)量龐大，因此在室內(nèi)導(dǎo)航中對A*算法的改進迫在眉睫。以大型商場為例對A*算法進行改進。通過對大量商城布局設(shè)計以及其他A*算法優(yōu)化的方案進行研究后，對其在商城導(dǎo)航中的A*算法進行優(yōu)化。具體思路為：對A*算法的地圖數(shù)據(jù)進行劃分，獲取有效的且可支持完成導(dǎo)航的地圖數(shù)據(jù)。

步驟1：假設(shè)在商城某一層里進行起點A到終點B的導(dǎo)航，如圖1(a)，其中陰影部分是不可通過的節(jié)點。

步驟2：進行地圖劃分。以節(jié)點A為圓心，以節(jié)點A到節(jié)點B的距離為半徑得到一個圓，如下：

dis_r向上取整，得到

r

，如下：

r

=dis_r

獲得圓方程，如下：

(

x

-startx)+(

y

-starty)=

r

根據(jù)上面的圓獲取外切正方形，同時也減少了一定數(shù)量的節(jié)點，得到圖1(b)，即是新的地圖數(shù)據(jù)。

圖1 算法步驟

步驟3：再次劃分地圖數(shù)據(jù)。在商城導(dǎo)航中，節(jié)點往往是很多的。當(dāng)從起點到達終點時，往往不會出現(xiàn)“以退為進”的選擇。對步驟2中得到的新的地圖數(shù)據(jù)進行再次劃分，根據(jù)起點的

x

坐標(biāo)與終點的

x

坐標(biāo)的相對位置，如圖1(c)。

步驟4：備用機制。當(dāng)存在個例無法通過步驟3得到的地圖數(shù)據(jù)獲得導(dǎo)航規(guī)劃路徑時，會將步驟2的地圖數(shù)據(jù)作為A*算法處理的地圖數(shù)據(jù)。同樣道理，當(dāng)無法通過步驟2得到地圖數(shù)據(jù)時，會將原地圖數(shù)據(jù)作為A*算法處理的地圖數(shù)據(jù)。那么商城布局以及商城使用的導(dǎo)航算法也相應(yīng)地需要修改。

2.2 改進的A*算法

傳統(tǒng)A*算法的啟發(fā)函數(shù)通常只考慮距離啟發(fā)信息且均采用單次計算，其應(yīng)用主要為二維平面的尋路，改進后的A*算法采用分層計算的思想，實現(xiàn)了室內(nèi)三維空間跨樓層的最優(yōu)路徑尋路。在路線規(guī)劃方法函數(shù)中加入相關(guān)限制，有效保證了最優(yōu)路徑的唯一性，同時實現(xiàn)了復(fù)雜室內(nèi)地圖環(huán)境下用戶步行路線最短的個性化需求，進一步增強了算法對復(fù)雜室內(nèi)地圖環(huán)境的適應(yīng)性。綜合室內(nèi)復(fù)雜地圖環(huán)境下用戶對最短距離和直行路程的需求，在位置計算中，引入同時考慮方向和距離啟發(fā)信息的啟發(fā)函數(shù)，把POI點與尋路節(jié)點分開處理，以映射的方式建立聯(lián)系，有效避免了直接搜尋POI節(jié)點數(shù)據(jù)量大、速率低的問題。

將該方案應(yīng)用于室內(nèi)導(dǎo)航中A*算法實現(xiàn)偽代碼，如下所示：

創(chuàng)建一個地圖數(shù)據(jù)列表

將原地圖數(shù)據(jù)存入列表尾部

r

<-獲得終點和起點的相對距離

r

<-對

r

進行向上取整以起點為圓心，

r

為半徑

獲取該圓的最小外接正方形，如下處理：

以起點的橫坐標(biāo)-

r

或者0作為正方形的上邊界以起點的橫坐標(biāo)+

r

或者橫坐標(biāo)的最大值作為正方形的下邊界以起點的縱坐標(biāo)-

r

或者0作為正方形的左邊界以起點的縱坐標(biāo)+

r

或者縱坐標(biāo)的最大值作為正方形的右邊界

將新的地圖數(shù)據(jù)(即正方形區(qū)域)存入地圖數(shù)據(jù)列表尾部

if(終點在起點的下方):

將起點的橫坐標(biāo)作為正方形的上邊界

else:

將起點的橫坐標(biāo)作為正方形的下邊界

將新的地圖數(shù)據(jù)(即正方形區(qū)域)存入地圖數(shù)據(jù)列表尾部

當(dāng)前地圖數(shù)據(jù)<-彈出地圖數(shù)據(jù)列表尾部元素

設(shè)置一個時間值

該時間值內(nèi)無法通過A*算法獲得結(jié)果,跳出

當(dāng)前地圖數(shù)據(jù)<-彈出地圖數(shù)據(jù)列表尾部元素

結(jié)束

3 仿真實驗

通過仿真實驗對A*算法與改進的A*算法進行比較。首先，使用網(wǎng)格模擬路網(wǎng)，網(wǎng)格由多個正方形組成，每一個正方形區(qū)域可存儲數(shù)字0或數(shù)字1，其中數(shù)字0表示障礙，具有不可通過的性質(zhì)；數(shù)字1表示通路，顧名思義，通路是可通過的。接下來，模擬路網(wǎng)，并在網(wǎng)格中設(shè)置起點和終點，且起點和終點必然存在可到達的性質(zhì)。最后，在同一個網(wǎng)格數(shù)據(jù)中，分別使用A*算法和改進的A*算法進行模擬導(dǎo)航。在使用算法模擬導(dǎo)航中，有以下兩點前提：

(1)存儲數(shù)字1的是可通過點；其中具有淺黑色陰影且存儲數(shù)字1的正方形區(qū)域是A*算法在網(wǎng)格數(shù)據(jù)中的掃描點；

(2)存儲數(shù)字0的正方形區(qū)域模擬的是路網(wǎng)中的障礙，并且使用黑色陰影進行了標(biāo)記。

仿真效果如圖2(a)和圖2(b)所示。

圖2 仿真效果

圖2(a)顯示A*算法對路網(wǎng)的大部分地圖數(shù)據(jù)進行了掃描；圖2(b)顯示只掃描了重要區(qū)域。由仿真實驗結(jié)果可知，在同一組網(wǎng)格數(shù)據(jù)中，改進的A*算法完成導(dǎo)航的時間遠小于A*算法。

4 算法效率測試

實驗中隨機生成地圖數(shù)據(jù)，隨機選擇起點和終點，對算法改進前后進行算法效率測試。每個節(jié)點10組數(shù)據(jù)，對10組數(shù)據(jù)求平均值，單位為毫秒，得到的數(shù)據(jù)見表1。

表1 A*算法優(yōu)化前后效率比較 ms

圖3為A*算法優(yōu)化前后效率對比，可以明顯地看到，優(yōu)化后A*算法的整體效率提升了近50%。

圖3 A*算法改進前后效率對比

下面以位置定位導(dǎo)航測試、活動詳情的跳轉(zhuǎn)測試、搜索并導(dǎo)航至商鋪測試為例進行系統(tǒng)測試。

(1)位置定位導(dǎo)航測試。當(dāng)用戶設(shè)置好起點與終點位置后，測試在不同位置設(shè)定起點，系統(tǒng)是否能設(shè)計出最優(yōu)路徑給用戶。結(jié)果顯示：設(shè)定相同終點，不同起點時，根據(jù)當(dāng)前所在位置與終點的距離，提供最優(yōu)路徑給用戶行走；設(shè)置相同終點，相同起點時，反饋的最優(yōu)路徑都是一致的；設(shè)定相同起點，不同終點時，根據(jù)所距路程遠近提供最優(yōu)路徑。

(2)活動詳情的跳轉(zhuǎn)測試。當(dāng)用戶在發(fā)現(xiàn)界面點擊當(dāng)前有最新產(chǎn)品促銷活動的心儀商鋪時，測試在瀏覽商鋪時跳轉(zhuǎn)到其相應(yīng)的產(chǎn)品促銷活動界面。結(jié)果顯示：用戶點擊心儀商鋪，點擊最新活動鏈接時，跳轉(zhuǎn)到活動詳情界面；用戶點擊心儀商鋪，接著沒有點擊最新活動，而點擊了取消按鈕時，沒有跳轉(zhuǎn)到活動詳情界面。

(3)搜索并導(dǎo)航至商鋪測試。當(dāng)用戶點擊搜索欄進行商鋪的搜索，測試是否能查找并導(dǎo)航至該商鋪。結(jié)果顯示：用戶在搜索欄輸入商鋪名稱，并確定起始位置，進行導(dǎo)航時，用戶根據(jù)導(dǎo)航到達目的地；用戶在搜索欄輸入商鋪名稱，搜索到店鋪后點擊取消按鈕時，用戶沒有導(dǎo)航至目的地；用戶在搜索欄輸入商鋪名稱，并沒有確定起始位置，點擊“到這去”按鈕時，小程序提示起始點并未確立，用戶沒有導(dǎo)航至目的地。

最終測試結(jié)果顯示，改進的A*算法運用在室內(nèi)導(dǎo)航小程序符合室內(nèi)導(dǎo)航目標(biāo)的需求預(yù)期。在室內(nèi)導(dǎo)航上實現(xiàn)了最優(yōu)路線規(guī)劃和導(dǎo)航，解決了用戶在室內(nèi)環(huán)境無法快速準(zhǔn)確到達目的地的問題。

5 結(jié)束語

提出將改進的A*算法運用于室內(nèi)導(dǎo)航，可以明顯提高算法的效率，在實際運用方面，由于自主改造使用，所以接入成本低，定制性強。對A*算法進行自主改造與使用，一方面帶來了很多好處，但另一方面，也存在許多問題。方案落地代價高，需要花費時間進行研發(fā)落地，整合進實際應(yīng)用項目中；改進空間大，即使進行了優(yōu)化，但是A*算法還是存在多種優(yōu)化方案。