室內導航技術綜述

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

?

室內導航技術綜述

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

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

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

物聯網；室內導航；路徑規劃

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

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

1 路徑規劃

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

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

圖1 尋路的不確定性

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

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

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

2 展示

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

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

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

表1 不同展示技術概覽

3 討論

3.1 路徑規劃

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

3.2 展望

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

[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] 何靜濤,王奎,代文斌,朱舒歡,姚平平.物聯網技術在高校圖書館管理中的應用[J].唐山師范學院學報,2016,38(5):143-145.

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

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

[25] 劉曉春.加快唐山市物聯網發展打造“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

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

2018-07-30

2018-09-19

郝天鹿（1980-），男，河北唐山人，碩士，實驗師，研究方向為物聯網。

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