一種基于改進(jìn)A*算法的室內(nèi)導(dǎo)航路徑規(guī)劃方法

葉小艷，鐘華鈞，鄧可兒

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

0 引 言

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

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

1 A*算法

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

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

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

F

()=

G

()+

H

()，其中

F

()表示節(jié)點(diǎn)

n

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

H

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

G

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

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

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

將起始點(diǎn)加入開(kāi)放列表中

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

while(當(dāng)前節(jié)點(diǎn)不為終點(diǎn)時(shí))：

獲取并處理當(dāng)前節(jié)點(diǎn)的周?chē)赏ㄟ^(guò)的節(jié)點(diǎn)，

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

G

值、

H

值，

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

遍歷當(dāng)前節(jié)點(diǎn)的周?chē)?jié)點(diǎn)

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

if(該節(jié)點(diǎn)在開(kāi)啟列表):

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

F

()進(jìn)行比較

if(開(kāi)啟列表的節(jié)點(diǎn)的估價(jià)函數(shù)大于該節(jié)點(diǎn)的估價(jià)函數(shù)):

將開(kāi)啟列表的節(jié)點(diǎn)進(jìn)行覆蓋

else:

將該節(jié)點(diǎn)加入開(kāi)啟列表

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

對(duì)開(kāi)啟列表進(jìn)行排序

當(dāng)前節(jié)點(diǎn)<-獲得開(kāi)啟列表的第一個(gè)元素

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

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

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

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

返回路徑結(jié)果集

結(jié)束

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

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

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

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

2.1 改進(jìn)的A*算法的基本思想

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

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

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

dis_r向上取整，得到

r

，如下：

r

=dis_r

獲得圓方程，如下：

(

x

-startx)+(

y

-starty)=

r

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

圖1 算法步驟

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

x

坐標(biāo)與終點(diǎn)的

x

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

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

2.2 改進(jìn)的A*算法

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

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

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

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

r

<-獲得終點(diǎn)和起點(diǎn)的相對(duì)距離

r

<-對(duì)

r

進(jìn)行向上取整以起點(diǎn)為圓心，

r

為半徑

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

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

r

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

r

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

r

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

r

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

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

if(終點(diǎn)在起點(diǎn)的下方):

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

else:

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

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

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

設(shè)置一個(gè)時(shí)間值

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

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

結(jié)束

3 仿真實(shí)驗(yàn)

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

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

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

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

圖2 仿真效果

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

4 算法效率測(cè)試

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

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

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

圖3 A*算法改進(jìn)前后效率對(duì)比

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

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

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

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

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

5 結(jié)束語(yǔ)

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