郝天鹿，劉玉民，彭宏玉，胡博涵

?

室內(nèi)導航技術綜述

郝天鹿1,2，劉玉民1,2，彭宏玉1,2，胡博涵3

（1. 唐山學院 計算機科學與技術系，河北 唐山 063000；2. 唐山市室內(nèi)定位技術重點實驗室，河北 唐山 063000；3. 澳大利亞國立大學，商業(yè)與經(jīng)濟學院，澳大利亞 堪培拉 2601）

總結了當前典型的室內(nèi)導航技術，以及其中關鍵的路徑規(guī)劃技術和展示技術，分析了當前室內(nèi)導航技術的研究點以及研究現(xiàn)狀，為室內(nèi)導航研究及系統(tǒng)大范圍部署提供支持。

物聯(lián)網(wǎng)；室內(nèi)導航；路徑規(guī)劃

導航需要融合移動及定位技術來實現(xiàn)[1]，導航服務包括基于感知數(shù)據(jù)的路徑規(guī)劃服務以及基于路徑規(guī)劃的導航服務[2]。通常情況下，不論是室內(nèi)還是室外導航都是通過計算與一個或者多個坐標點的距離以及方向來實現(xiàn)。通過不斷計算導航對象位置和方向的變化就可以規(guī)劃出相應路徑[3]。在這種應用中，可以不使用地圖，此時對移動物體進行導航，需要保存每個移動物體所有路徑變化[4]。也可以輔助地圖-基于路標的路徑規(guī)劃，在這種路徑規(guī)劃中必須輔以地圖。通過計算當前所處位置與路標的距離和角度就可以獲得導航對象當前位置以及具體方位。在探索一個新的環(huán)境過程中，路徑規(guī)劃是十分有用的，因為導航者雖然不清楚新環(huán)境的實際情況，但是可以通過路標以及地圖清楚地知道當前所處位置以及接下來的路徑規(guī)劃[5-8]。研究表明，基于路標和地圖的路徑規(guī)劃已經(jīng)成為大眾出行首選導航方式[9-12]。

導航系統(tǒng)功能包括定位和繪制導航者移動軌跡。用戶位置信息可以用來進行路徑規(guī)劃以及提供環(huán)境信息。當用戶位置被確定后，就可以在用戶迷路時為用戶提供一條新路徑或者同時為用戶提供一條備選路徑。優(yōu)秀的路徑規(guī)劃可以根據(jù)用戶的具體要求，為用戶提供特殊的方向規(guī)劃。導航系統(tǒng)的首要功能是根據(jù)用戶不同需求為其提供一條最優(yōu)路徑，如，最短路徑和最安全路徑等。導航系統(tǒng)通過與用戶交互為用戶提供方位以及周圍環(huán)境信息。導航系統(tǒng)中的交互可以有多種表現(xiàn)形式，包括通過GIS地圖形式顯示導航人員移動軌跡、在嘈雜的環(huán)境下為用戶提供點擊接口等。當導航者位置確定后，導航系統(tǒng)即可為導航者提供周圍環(huán)境信息，其中包括障礙物位置及重要路標位置等。近年來，已經(jīng)有大量的室內(nèi)導航系統(tǒng)被研發(fā)出來。本文對室內(nèi)導航系統(tǒng)中路徑規(guī)劃、展示技術兩大關鍵技術進行了總結。

1 路徑規(guī)劃

路徑規(guī)劃是室內(nèi)定位系統(tǒng)中重要組成部分，路徑規(guī)劃優(yōu)劣直接影響導航系統(tǒng)的整體性能。導航設計者在設計路徑規(guī)劃需要盡可能地提高易用性以及可靠性，盡可能地降低由于規(guī)劃路徑出錯而導致用戶迷路的概率。優(yōu)秀的路徑規(guī)劃系統(tǒng)應該考慮用戶要求的特殊性以及支持用戶定制。

通常情況下，室內(nèi)導航系統(tǒng)通過運行最短路徑算法獲取距離最短路徑或者最省時路徑[13-14]。如對年老以及行動受限的導航者，需要為其規(guī)劃一條障礙物最少，危險系數(shù)最低的路徑[15-18]。

圖1 尋路的不確定性

如圖1所示，通過最短路徑算法來獲取的最短路徑可能會導致較高的不確定性和危險性，這樣的導航系統(tǒng)在獲取路徑時需要將規(guī)劃路徑的危險性以及不確定性降到最低[19]。當為輪椅用戶或者年老用戶進行導航時，需要規(guī)劃一條無障礙路徑，該路徑中不應該有樓梯，應該全部由平地及斜坡組成[20]。成熟的室內(nèi)導航系統(tǒng)應該支持導航用戶根據(jù)實際需要設置參數(shù)進行定制路徑規(guī)劃[21]。

在典型路徑規(guī)劃算法中，通常使用圖形和網(wǎng)格來標識整個導航場景，使用圖形學算法進行路徑規(guī)劃。整個導航場景抽象為點的集合、以及連接點的邊的集合。導航場景中的點可以是任何類型的物體，例如十字路口、門、或者障礙物等。邊用于將導航場景中的所有點連接到一起，也可以表示一個節(jié)點是否可以從另一個點出發(fā)訪問到。每一條邊都應該具有一個權值，該權值根據(jù)路徑規(guī)劃的側重點不同代表的含義也不一樣。在基于柵格的導航算法中，導航場景劃分為小單元格。每個單元格中都包含導航對象的位置信息以及描述導航場景的信息。在基于圖形的導航算法中，導航場景也劃分為小單元格，其中單元格具有類似邊的權值。在基于柵格的定位場景中，存在如下問題：當單元格很大時，每個單元格中會存在大量的導航者，同時每個單元格需要定義一個數(shù)據(jù)結構來存儲所有細節(jié)信息。如果單元格較小，那么單元格數(shù)據(jù)就會增加，在導航系統(tǒng)尋找導航者時，需要遍歷更多的單元格，從而會增加導航系統(tǒng)計算負擔。

基于圖形的室內(nèi)導航系統(tǒng)優(yōu)點在于：只有導航者確定時才建立節(jié)點，當導航者與其他的所有導航者都可以相互訪問時才建立對應的邊，這樣會有效地降低導航系統(tǒng)運行負載，提高導航系統(tǒng)運行效率。缺點是在復雜的導航場景中，導航物體圖大多會很大，從而導致路徑規(guī)劃算法性能降低。當前主流的室內(nèi)導航算法主要使用Dijkstra[22-24]或者A*[25-26]來進行路徑規(guī)劃。

2 展示

在移動物體導航系統(tǒng)中需要存儲并檢索不同類型的信息。存儲的信息用于導航服務、路徑規(guī)劃、給導航用戶提供相關導航場景。

根據(jù)室內(nèi)導航系統(tǒng)中采用的算法，在進行展示時，展示信息包括樓宇平面圖、室內(nèi)定位場景中陳設物的描繪以及擺放位置、定位標簽部署以及傳感器回傳的數(shù)據(jù)。室內(nèi)導航場景展示時可以采用2維（2D）的地圖，在2維地圖上可以展示墻、門或者每條邊上都帶有權值的訪問路線圖[27]。地圖可以基于導航區(qū)域以及導航用戶實時位置來進行路徑規(guī)劃。如果導航系統(tǒng)使用標簽法來進行用戶導航，那么標簽的信息將被存儲到地圖中[28]。2D地圖是使用最少資源的一種展示方式。這樣的2D地圖很容易通過建筑物導航場景的CAD圖進行創(chuàng)建。但是考慮到導航物體的特殊性以及導航區(qū)域的危險性，例如容易碰頭等，這使得向2D地圖中添加詳細信息難度加大。

3D模型可以用來展示室內(nèi)導航場景[29]。大量的有用信息可以從這個3D模型中提取出來，例如門的位置信息、斜坡的坡度、容易碰頭的位置等。雖然建立這些模型費用高昂，但是這些模型是語言獨立的并且可以通過物體識別算法自動提取信息從而有助于系統(tǒng)的全球部署。由于3D模型需要更高存儲容量、更快的運算速度進行信息提取，因此3D模型是資源更加密集型表現(xiàn)形式。表1給出了用于展示的不同技術的概覽。

表1 不同展示技術概覽

3 討論

3.1 路徑規(guī)劃

目前很多室內(nèi)定位系統(tǒng)是為有視覺障礙的人開發(fā)部署的，由于障礙物路標的確認對有視覺障礙的人在熟悉的環(huán)境中活動是十分重要的，因此室內(nèi)定位系統(tǒng)可以以此作為指導，沿著容易確認的路標規(guī)劃一條更為合理、更能容易完成的路徑，盡量避免經(jīng)過寬敞的大門，而是應規(guī)劃一條沿著墻行走的路線，這樣使得有視覺障礙的人可以確認自己能順利達到目的地。室內(nèi)定位導航系統(tǒng)也應該根據(jù)用戶不同的需求為用戶規(guī)劃更能為合理、智能的路線，例如為輪椅用戶規(guī)劃的路線應盡量避免樓梯和斜坡。

3.2 展望

在很多室內(nèi)定位系統(tǒng)中，使用2D或者建筑的CAD圖來表示室內(nèi)導航環(huán)境進行導航。3D虛擬化模型可以被用來更精確、多層次地表示室內(nèi)定位場景，比如哪里容易碰頭、斜坡、不平的地面和路軌等。這些因素對視覺有障礙的用戶來說應該避免。雖然隨著3D地圖自動生成技術的進步，3D模型制作成本顯著下降，但是相比創(chuàng)建一個2D模型而言，創(chuàng)建一個3D模型的成本還是太高。不論是2D模型還是3D模型，都需要備注地址信息，例如房間號、路標、門等，這可以利用群眾資源以及開發(fā)接口來獲得。

[1] Zeinalipour-Yazti D, Laoudias C, Georgiou K, et al. Internet-based Indoor Navigation Services[J]. IEEE Internet Computing, 2017, 21(4): 54-63.

[2] Zheng Y, Shen G, Li L, et al. Travi-Navi: Self- Deployable Indoor Navigation System[J]. IEEE/ACM Transactions on Networking, 2017, 25(5): 2655-2669.

[3] Li Y, Zhuang Y, Zhang P, et al. An improved inertial/wifi/magnetic fusion structure for indoor navigation[J]. Information Fusion, 2017, 34(C): 101- 119.

[4] Ivanov R. An approach for developing indoor navigation systems for visually impaired people using Building Information Modeling[J]. Journal of Ambient Intelli- gence & Smart Environments, 2017, 9(4): 449- 467.

[5] Kumar G A, Patil A K, Patil R, et al. A LiDAR and IMU Integrated Indoor Navigation System for UAVs and Its Application in Real-Time Pipeline Classification[J]. Sensors, 2017, 17(6): 51-67.

[6] Jamali A, Rahman A A, Boguslawski P, et al. An automated 3D modeling of topological indoor navi- gation network[J]. Geojournal, 2017, 82(1): 157- 170.

[7] Chrysanthis P K, Zeinalipour-Yazti D, Konstantinidis A. IoT Data Prefetching in Indoor Navigation SOAs[J]. Acm Transactions on Internet Technology, 2018, 11(5): 75-91.

[8] Liu G, Shi L. An overview about development of indoor navigation and positioning technology[J]. Journal of Navigation & Positioning, 2018, 21(7): 85-101.

[9] Semwal S K. Wayfinding And Navigation In Haptic Virtual Environments[C]. Japan: DBLP, 2001: 143-143.

[10] Apostolopoulos I, Fallah N, Folmer E, et al. Feasibility of Interactive Localization and Navigation of People with Visual Impairments[J]. 11th IEEE Intelligent Autonomous Systems, 2010, 5(11): 51-63.

[11] Bessho, Masahiro, Kobayashi, et al. A space-identifying ubiquitous infrastructure and its application for tour-guiding service[J]. Sac, 2016, 13(5): 1616-1621.

[12] Kulyukin V, Gharpure C, Nicholson J, et al. Robot-assisted wayfinding for the visually impaired in structured indoor environments[J]. Autonomous Robots, 2006, 21(1): 29-41.

[13] Koide S, Kato M. 3-D human navigation system considering various transition preferences[C]. IEEE International Conference on Systems: Man and Cybernetics, 2006: 859-864.

[14] J?rg Baus, Wahlster W. A resource-adaptive mobile navigation system[C]. International Conference on Intelligent User Interfaces: DBLP, 2002: 15-22.

[15] Helal A, Moore S E, Ramachandran B. Drishti: An Integrated Navigation System for Visually Impaired and Disabled[C]. IEEE International Symposium on Wearable Computers: IEEE Computer Society, 2001: 149-161.

[16] Petrie H, Johnson V, Strothotte T, et al. MOBIC: Designing a Travel Aid for Blind and Elderly People[J]. Journal of Navigation, 1996, 49(1): 45-52.

[17] Arikawa M, Konomi S, Ohnishi K. Navitime: Supporting Pedestrian Navigation in the Real World[J]. IEEE Pervasive Computing, 2007, 6(3):21-29.

[18] Tsetsos V, Anagnostopoulos C, Kikiras P, et al. Semantically enriched navigation for indoor environ- ments[J]. International Journal of Web & Grid Services, 2006, 2(4): 453-478.

[19] Hollerer T, Hallaway D, Tinna N, et al. Steps Toward Accommodating Variable Position Tracking Accuracy in a Mobile Augmented Reality System[J]. Proc Aims’, 2001: 31-37.

[20] Lertlakkhanakul J, Li Y, Choi J, et al. GongPath: Development of BIM Based Indoor Pedestrian Navigation System[C]. International Joint Conference on Inc: IEEE Computer Society, 2009: 382-388.

[21] Lyardet F, Grimmer J, Muhlhauser M. CoINS: Context Sensitive Indoor Navigation System[J]. IEEE, 2006, 15(8): 209-218.

[22] 何靜濤,王奎,代文斌,朱舒歡,姚平平.物聯(lián)網(wǎng)技術在高校圖書館管理中的應用[J].唐山師范學院學報,2016,38(5):143-145.

[23] 孫曄.京津冀一體化與區(qū)域智慧物流的協(xié)同發(fā)展[J].唐山師范學院學報,2015,37(5):149-152.

[24] 朱程.淺析信任管理在物聯(lián)網(wǎng)安全中的應用[J].唐山師范學院學報,2015,37(2):52-54.

[25] 劉曉春.加快唐山市物聯(lián)網(wǎng)發(fā)展打造“U唐山”的對策[J].唐山師范學院學報,2011,33(5):98-100.

[26] Retscher G. NAVIO-A Navigation and Guidance Service for Pedestrians[J]. J Gps, 2004, 3(1): 208-217.

[27] Koch O, Teller S. A Self-Calibrating, Vision-Based Navigation Assistant[J]. Workshop on Computer Vision Applications for the Visually Impaired, 2008, 9(12): 101-115.

[28] D'Atri E, Medaglia C M, Serbanati A, et al. A system to aid blind people in the mobility: A usability test and its results[C]. International Conference on Systems: IEEE, 2007: 31-35.

[29] Fischer C, Muthukrishnan K, Hazas M, et al. Ultrasound-aided pedestrian dead reckoning for indoor navigation[C]. ACM International Workshop on Mobile Entity Localization and Tracking in Gps-Less Environments: ACM, 2008: 31-36.

[30] Hoggan E, Brewster S A, Johnston J. Investigating the effectiveness of tactile feedback for mobile touch- screens[C]. Conference on Human Factors in Computing Systems: CHI, 2008: 1573-1582.

A Survey of Indoor Navigating Technology

HAO Tian-lu1,2, LIU Yu-min1,2, PENG Hong-yu1,2, HU Bo-han3

(1. Department of Computer Science and Technology, Tangshan College, Tangshan 063000, China; 2. Tangshan Key Laboratory of Indoor Positioning Technology, Tangshan College, Tangshan 063000, China; 3. Australian National University, College of Business and Economics, Canberra 2601, Australia)

Indoor navigating technology aim at moving objects. Indoor navigating technology is the extension of indoor positioning technology. Typical outdoor navigating technologies are introduced. The decayed Satellite signal can’t navigate the indoor objects. So the present typical outdoor navigating technologies are suitable for the Indoor navigating technology. Typical Indoor navigating technologies and key path planning and presentation technology are given. So as to promote the extensive deployment of indoor navigating systems.

internet of things; indoor navigation; path plan

TP39

A

1009-9115(2018)06-0087-04

10.3969/j.issn.1009-9115.2018.06.020

博創(chuàng)基金項目（1401801），西南交大合作智慧水務項目（1200305），唐山市科技計劃項目（220020502）

2018-07-30

2018-09-19

郝天鹿（1980-），男，河北唐山人，碩士，實驗師，研究方向為物聯(lián)網(wǎng)。

（責任編輯、校對：田敬軍）