室内导航技术综述

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



室内导航技术综述

郝天鹿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-），男，河北唐山人，硕士，实验师，研究方向为物联网。

（责任编辑、校对：田敬军）