立體空間A*算法在尋找商場室內(nèi)導(dǎo)航最優(yōu)路徑中的應(yīng)用

畢小順

（禾麥科技開發(fā)（深圳）有限公司，廣東　深圳　518001）

立體空間A*算法在尋找商場室內(nèi)導(dǎo)航最優(yōu)路徑中的應(yīng)用

畢小順

（禾麥科技開發(fā)（深圳）有限公司，廣東深圳518001）

文章研究了用于商場室內(nèi)路徑規(guī)劃導(dǎo)航的算法，對比了各種算法的優(yōu)缺點(diǎn)，提出了一種優(yōu)化的A*算法。該算法結(jié)合了Dijkstra算法以及廣度優(yōu)先搜索（Breadth First Search，BFS）算法的優(yōu)點(diǎn)，同時(shí)充分考慮了商場的立體空間結(jié)構(gòu)，并結(jié)合了商場通行的大數(shù)據(jù)，可以給出最有效的商場室內(nèi)路徑規(guī)劃。

室內(nèi)；路徑規(guī)劃；導(dǎo)航；A*算法

1　概述

室內(nèi)定位技術(shù)［1］可以為用戶提供精準(zhǔn)的商場定位、導(dǎo)航、導(dǎo)購服務(wù)，有利于提高商場的服務(wù)質(zhì)量，提升購物者的購物體驗(yàn)。通過商場購物引導(dǎo)、線上線下結(jié)合，其應(yīng)用的市場潛力十分巨大。

室內(nèi)導(dǎo)航服務(wù)作為室內(nèi)定位技術(shù)的重要應(yīng)用，可以為用戶展示其感興趣的商品、門店、停車位等位置的方向、距離，方便用戶抵達(dá)目的地，效用明顯。但是在室內(nèi)導(dǎo)航服務(wù)中，單純地提供目的地位置，由用戶自行考慮抵達(dá)的路徑，仍不是最佳的服務(wù)，有必要通過算法，基于室內(nèi)定位和商場地圖進(jìn)行快速的智能路徑規(guī)劃導(dǎo)航，為用戶提供更滿意的服務(wù)。

2　路徑規(guī)劃算法

路徑規(guī)劃有很多算法，在導(dǎo)航中，主流的算法就是廣度優(yōu)先搜索（Breadth First Search，BFS）算法，Dijkstra算法和A*算法。

Dijkstra算法［2］以物體所在的出發(fā)點(diǎn)為中心開始訪問地圖中的結(jié)點(diǎn)。它迭代檢查待檢查結(jié)點(diǎn)集中的結(jié)點(diǎn)，并把和該結(jié)點(diǎn)最靠近的尚未檢查的結(jié)點(diǎn)加入待檢查結(jié)點(diǎn)集。該結(jié)點(diǎn)集從初始結(jié)點(diǎn)向外擴(kuò)展，直到到達(dá)目標(biāo)結(jié)點(diǎn)，是一種擴(kuò)張式的遍歷方法。Dijkstra算法的優(yōu)點(diǎn)是一定能獲得最短的路徑，缺點(diǎn)在于其是一種窮舉式算法，對于復(fù)雜地圖系統(tǒng)，運(yùn)算量很大。

BFS算法與Dijkstra算法類似［3］，不同的是它引入了啟發(fā)式算法（heuristic algorithm）對每一個(gè)搜索位置進(jìn)行評估，得到最好的位置，再從這個(gè)位置進(jìn)行搜索直到目標(biāo)。BFS不能保證找到的一定是一條最短路徑。然而，它可以省略大部分無意義的搜索路徑，相比Dijkstra算法運(yùn)行速度快很多。BFS算法的缺點(diǎn)在于它向目標(biāo)移動(dòng)僅僅考慮到達(dá)目標(biāo)的代價(jià)，而忽略了當(dāng)前已消耗的代價(jià)，這使得其在復(fù)雜情況下會得出錯(cuò)誤的路徑。

A*算法是BFS和Dijsktra算法的結(jié)合，吸取了兩者的優(yōu)點(diǎn)。和Dijkstra一樣，A*能用于搜索最短路徑，和BFS一樣，A*能用啟發(fā)式函數(shù)引導(dǎo)它自己，給出當(dāng)下的最佳解。同時(shí)，由于引入了Dijsktra算法的思想，A*算法會也會評估已經(jīng)走過路徑的代價(jià)，以保證找到一條最短路徑。A*算法的估價(jià)函數(shù)如下式：

f（n）=g（n）+ h（n）

其中g(shù)（n）表示從初始結(jié)點(diǎn)到任意結(jié)點(diǎn)n的代價(jià)，h（n）表示應(yīng)用啟發(fā)函數(shù)從結(jié)點(diǎn)n到目標(biāo)結(jié)點(diǎn)的評估代價(jià)。

因此A*算法是進(jìn)行商場導(dǎo)購路徑規(guī)劃的最佳選擇。但是大型商場，均為立體多層空間，其地圖信息更加復(fù)雜，需要對A*算法進(jìn)一步優(yōu)化以適應(yīng)多層空間的路徑搜索。

3　立體空間A*算法優(yōu)化

本文認(rèn)為，在商場這種多層級的立體空間，應(yīng)用A*算法，有必要分層開展，逐層尋優(yōu)，最后匯總評估，來獲得最終的最優(yōu)路徑。其軟件框圖如圖1所示。首先評估目標(biāo)地址是否在本層，對于本層的地址，直接應(yīng)用A*搜索算法即可尋找到最優(yōu)路徑。對于其他層的地址，首先采用A*搜索算法計(jì)算由出發(fā)點(diǎn)到不同樓梯口的最優(yōu)路徑，再繼續(xù)采用A*搜索算法計(jì)算由目標(biāo)地址反推到該層各個(gè)樓梯口的最優(yōu)路徑。然后各個(gè)對應(yīng)的樓梯口的路徑對接合成，即形成了經(jīng)過不同樓梯口抵達(dá)目標(biāo)層目標(biāo)地址的最優(yōu)路徑集。

經(jīng)過不同樓梯口的最優(yōu)路徑集不能簡單對比路徑長度進(jìn)行評估。而應(yīng)該結(jié)合其跨越的樓層數(shù)，上樓的方式（扶梯式電梯，轎箱式電梯，步行樓梯）以及結(jié)合商場的大數(shù)據(jù)分析評估不同上樓方式占用的時(shí)間，以便給出精確可靠的評估結(jié)果，包括：最短路徑，最省時(shí)間路徑，最輕松路徑等，給用戶提供最精確可靠的評估結(jié)果。

4　結(jié)語

大型商場結(jié)構(gòu)復(fù)雜，路徑繁多，面積龐大。傳統(tǒng)的導(dǎo)購圖，指示牌等由于傳播能力有限，導(dǎo)航效果不佳，有必要借助現(xiàn)代信息技術(shù)和手機(jī)等智能終端的結(jié)合為大型商場的客人提供更高效的路徑規(guī)劃導(dǎo)航。本文提出了采用優(yōu)化的A*算法在商場等大型多樓層立體空間的路徑規(guī)劃算法。為大型商場或建筑物提供路徑規(guī)劃導(dǎo)航算法提供了可行的方案。

圖1　算法框圖

［1］汪苑，林錦國.幾種常用室內(nèi)定位技術(shù)的探討［J］.中國儀器儀表，2011（2）：54-57.

［2］楊劉翔.Dijkstra算法在物流配送中的應(yīng)用研究［J］.電子世界，2014（12）：209-209.

［3］李辰寅，徐健，張淑梅，等.立體停車庫調(diào)度算法的研究與實(shí)現(xiàn)［J］.蘇州科技學(xué)院學(xué)報(bào)（工程技術(shù)版），2008（1）：63-66.

Application of three-dimensional space A* algorithm for fnding the optimal path in shopping mall indoor navigation

Bi Xiaoshun
（Roy Mark Technology Development（Shen Zhen）Co.， Ltd.， Shenzhen 518001， China）

This paper studied the algorithm of indoor path planning and navigation in shopping mall and compared with the advantages and disadvantages of various navigation algorithms. This paper proposed an optimized A* algorithm which combined with the advantage of both Dijkstra algorithm and breadth frst search（BFS）algorithm， and fully considered the three-dimensional structures and the big data of shopping mall. It can give the most effective indoor path planning for shopping malls.

indoor； path planning； navigation； A* algorithm

畢小順（1979— ），男，江西臨川，本科，中級職稱；研究方向：計(jì)算機(jī)軟件及應(yīng)用。