一種基于改進A*算法的室內導航路徑規劃方法

葉小艷，鐘華鈞，鄧可兒

(廣州軟件學院 網絡技術系，廣東 廣州 510990)

0 引 言

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

因此，為提高路徑規劃方法中的效率和穩定性，達到加速導航算法的目的，采用分層計算的思想對普通A*算法進行優化，提出了一種改進型A*算法優化的方案。經過算法效率測試，改進型A*算法在室內導航路徑規劃的效率和穩定性比較優。

1 A*算法

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

1.1 A*算法的基本思想與實現步驟

A*算法的基本思想主要是在規劃最優路徑的前提下運用啟發函數引導搜索，A*算法的啟發函數為

F

()=

G

()+

H

()，其中

F

()表示節點

n

從初始點到目標點的函數，

H

()表示從當前節點到目標節點的估計代價，

G

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

其實現步驟用偽代碼表示如下：

創建開啟列表、關閉列表

將起始點加入開放列表中

彈出開啟列表的第一個節點，將該元素作為當前節點

while(當前節點不為終點時)：

獲取并處理當前節點的周圍可通過的節點，

為這些節點設置

G

值、

H

值，

添加當前節點為這些可通過節點的父節點

遍歷當前節點的周圍節點

if(該節點可通過且不在關閉列表):

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

根據 估價函數

F

()進行比較

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

將開啟列表的節點進行覆蓋

else:

將該節點加入開啟列表

將當前節點添加到關閉列表中

對開啟列表進行排序

當前節點<-獲得開啟列表的第一個元素

創建一個路徑結果集

while(當前節點的父節點不為空):

獲得當前節點的索引，存入路徑結果集中

當前節點<-當前節點的父節點

返回路徑結果集

結束

1.2 室內導航中A*路徑算法存在的問題

A*路徑算法在路徑搜索過程中，刪除了大量的節點，導致產生的結果可能不是最優路徑。但由于該算法是用于室內導航的，所以這種可能的發生率非常小。

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

2 室內導航中A*算法的改進

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

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

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

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

dis_r向上取整，得到

r

，如下：

r

=dis_r

獲得圓方程，如下：

(

x

-startx)+(

y

-starty)=

r

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

圖1 算法步驟

步驟3：再次劃分地圖數據。在商城導航中，節點往往是很多的。當從起點到達終點時，往往不會出現“以退為進”的選擇。對步驟2中得到的新的地圖數據進行再次劃分，根據起點的

x

坐標與終點的

x

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

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

2.2 改進的A*算法

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

將該方案應用于室內導航中A*算法實現偽代碼，如下所示：

創建一個地圖數據列表

將原地圖數據存入列表尾部

r

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

r

<-對

r

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

r

為半徑

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

以起點的橫坐標-

r

或者0作為正方形的上邊界以起點的橫坐標+

r

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

r

或者0作為正方形的左邊界以起點的縱坐標+

r

或者縱坐標的最大值作為正方形的右邊界

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

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

將起點的橫坐標作為正方形的上邊界

else:

將起點的橫坐標作為正方形的下邊界

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

當前地圖數據<-彈出地圖數據列表尾部元素

設置一個時間值

該時間值內無法通過A*算法獲得結果,跳出

當前地圖數據<-彈出地圖數據列表尾部元素

結束

3 仿真實驗

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

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

(2)存儲數字0的正方形區域模擬的是路網中的障礙，并且使用黑色陰影進行了標記。

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

圖2 仿真效果

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

4 算法效率測試

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

表1 A*算法優化前后效率比較 ms

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

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

下面以位置定位導航測試、活動詳情的跳轉測試、搜索并導航至商鋪測試為例進行系統測試。

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

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

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

最終測試結果顯示，改進的A*算法運用在室內導航小程序符合室內導航目標的需求預期。在室內導航上實現了最優路線規劃和導航，解決了用戶在室內環境無法快速準確到達目的地的問題。

5 結束語

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