郝天鹿,劉玉民,彭宏玉,胡博涵
?
室內(nèi)導(dǎo)航技術(shù)綜述
郝天鹿1,2,劉玉民1,2,彭宏玉1,2,胡博涵3
(1. 唐山學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系,河北 唐山 063000;2. 唐山市室內(nèi)定位技術(shù)重點(diǎn)實(shí)驗(yàn)室,河北 唐山 063000;3. 澳大利亞國立大學(xué),商業(yè)與經(jīng)濟(jì)學(xué)院,澳大利亞 堪培拉 2601)
總結(jié)了當(dāng)前典型的室內(nèi)導(dǎo)航技術(shù),以及其中關(guān)鍵的路徑規(guī)劃技術(shù)和展示技術(shù),分析了當(dāng)前室內(nèi)導(dǎo)航技術(shù)的研究點(diǎn)以及研究現(xiàn)狀,為室內(nèi)導(dǎo)航研究及系統(tǒng)大范圍部署提供支持。
物聯(lián)網(wǎng);室內(nèi)導(dǎo)航;路徑規(guī)劃
導(dǎo)航需要融合移動(dòng)及定位技術(shù)來實(shí)現(xiàn)[1],導(dǎo)航服務(wù)包括基于感知數(shù)據(jù)的路徑規(guī)劃服務(wù)以及基于路徑規(guī)劃的導(dǎo)航服務(wù)[2]。通常情況下,不論是室內(nèi)還是室外導(dǎo)航都是通過計(jì)算與一個(gè)或者多個(gè)坐標(biāo)點(diǎn)的距離以及方向來實(shí)現(xiàn)。通過不斷計(jì)算導(dǎo)航對象位置和方向的變化就可以規(guī)劃出相應(yīng)路徑[3]。在這種應(yīng)用中,可以不使用地圖,此時(shí)對移動(dòng)物體進(jìn)行導(dǎo)航,需要保存每個(gè)移動(dòng)物體所有路徑變化[4]。也可以輔助地圖-基于路標(biāo)的路徑規(guī)劃,在這種路徑規(guī)劃中必須輔以地圖。通過計(jì)算當(dāng)前所處位置與路標(biāo)的距離和角度就可以獲得導(dǎo)航對象當(dāng)前位置以及具體方位。在探索一個(gè)新的環(huán)境過程中,路徑規(guī)劃是十分有用的,因?yàn)閷?dǎo)航者雖然不清楚新環(huán)境的實(shí)際情況,但是可以通過路標(biāo)以及地圖清楚地知道當(dāng)前所處位置以及接下來的路徑規(guī)劃[5-8]。研究表明,基于路標(biāo)和地圖的路徑規(guī)劃已經(jīng)成為大眾出行首選導(dǎo)航方式[9-12]。
導(dǎo)航系統(tǒng)功能包括定位和繪制導(dǎo)航者移動(dòng)軌跡。用戶位置信息可以用來進(jìn)行路徑規(guī)劃以及提供環(huán)境信息。當(dāng)用戶位置被確定后,就可以在用戶迷路時(shí)為用戶提供一條新路徑或者同時(shí)為用戶提供一條備選路徑。優(yōu)秀的路徑規(guī)劃可以根據(jù)用戶的具體要求,為用戶提供特殊的方向規(guī)劃。導(dǎo)航系統(tǒng)的首要功能是根據(jù)用戶不同需求為其提供一條最優(yōu)路徑,如,最短路徑和最安全路徑等。導(dǎo)航系統(tǒng)通過與用戶交互為用戶提供方位以及周圍環(huán)境信息。導(dǎo)航系統(tǒng)中的交互可以有多種表現(xiàn)形式,包括通過GIS地圖形式顯示導(dǎo)航人員移動(dòng)軌跡、在嘈雜的環(huán)境下為用戶提供點(diǎn)擊接口等。當(dāng)導(dǎo)航者位置確定后,導(dǎo)航系統(tǒng)即可為導(dǎo)航者提供周圍環(huán)境信息,其中包括障礙物位置及重要路標(biāo)位置等。近年來,已經(jīng)有大量的室內(nèi)導(dǎo)航系統(tǒng)被研發(fā)出來。本文對室內(nèi)導(dǎo)航系統(tǒng)中路徑規(guī)劃、展示技術(shù)兩大關(guān)鍵技術(shù)進(jìn)行了總結(jié)。
路徑規(guī)劃是室內(nèi)定位系統(tǒng)中重要組成部分,路徑規(guī)劃優(yōu)劣直接影響導(dǎo)航系統(tǒng)的整體性能。導(dǎo)航設(shè)計(jì)者在設(shè)計(jì)路徑規(guī)劃需要盡可能地提高易用性以及可靠性,盡可能地降低由于規(guī)劃路徑出錯(cuò)而導(dǎo)致用戶迷路的概率。優(yōu)秀的路徑規(guī)劃系統(tǒng)應(yīng)該考慮用戶要求的特殊性以及支持用戶定制。
通常情況下,室內(nèi)導(dǎo)航系統(tǒng)通過運(yùn)行最短路徑算法獲取距離最短路徑或者最省時(shí)路徑[13-14]。如對年老以及行動(dòng)受限的導(dǎo)航者,需要為其規(guī)劃一條障礙物最少,危險(xiǎn)系數(shù)最低的路徑[15-18]。
圖1 尋路的不確定性
如圖1所示,通過最短路徑算法來獲取的最短路徑可能會(huì)導(dǎo)致較高的不確定性和危險(xiǎn)性,這樣的導(dǎo)航系統(tǒng)在獲取路徑時(shí)需要將規(guī)劃路徑的危險(xiǎn)性以及不確定性降到最低[19]。當(dāng)為輪椅用戶或者年老用戶進(jìn)行導(dǎo)航時(shí),需要規(guī)劃一條無障礙路徑,該路徑中不應(yīng)該有樓梯,應(yīng)該全部由平地及斜坡組成[20]。成熟的室內(nèi)導(dǎo)航系統(tǒng)應(yīng)該支持導(dǎo)航用戶根據(jù)實(shí)際需要設(shè)置參數(shù)進(jìn)行定制路徑規(guī)劃[21]。
在典型路徑規(guī)劃算法中,通常使用圖形和網(wǎng)格來標(biāo)識(shí)整個(gè)導(dǎo)航場景,使用圖形學(xué)算法進(jìn)行路徑規(guī)劃。整個(gè)導(dǎo)航場景抽象為點(diǎn)的集合、以及連接點(diǎn)的邊的集合。導(dǎo)航場景中的點(diǎn)可以是任何類型的物體,例如十字路口、門、或者障礙物等。邊用于將導(dǎo)航場景中的所有點(diǎn)連接到一起,也可以表示一個(gè)節(jié)點(diǎn)是否可以從另一個(gè)點(diǎn)出發(fā)訪問到。每一條邊都應(yīng)該具有一個(gè)權(quán)值,該權(quán)值根據(jù)路徑規(guī)劃的側(cè)重點(diǎn)不同代表的含義也不一樣。在基于柵格的導(dǎo)航算法中,導(dǎo)航場景劃分為小單元格。每個(gè)單元格中都包含導(dǎo)航對象的位置信息以及描述導(dǎo)航場景的信息。在基于圖形的導(dǎo)航算法中,導(dǎo)航場景也劃分為小單元格,其中單元格具有類似邊的權(quán)值。在基于柵格的定位場景中,存在如下問題:當(dāng)單元格很大時(shí),每個(gè)單元格中會(huì)存在大量的導(dǎo)航者,同時(shí)每個(gè)單元格需要定義一個(gè)數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)所有細(xì)節(jié)信息。如果單元格較小,那么單元格數(shù)據(jù)就會(huì)增加,在導(dǎo)航系統(tǒng)尋找導(dǎo)航者時(shí),需要遍歷更多的單元格,從而會(huì)增加導(dǎo)航系統(tǒng)計(jì)算負(fù)擔(dān)。
基于圖形的室內(nèi)導(dǎo)航系統(tǒng)優(yōu)點(diǎn)在于:只有導(dǎo)航者確定時(shí)才建立節(jié)點(diǎn),當(dāng)導(dǎo)航者與其他的所有導(dǎo)航者都可以相互訪問時(shí)才建立對應(yīng)的邊,這樣會(huì)有效地降低導(dǎo)航系統(tǒng)運(yùn)行負(fù)載,提高導(dǎo)航系統(tǒng)運(yùn)行效率。缺點(diǎn)是在復(fù)雜的導(dǎo)航場景中,導(dǎo)航物體圖大多會(huì)很大,從而導(dǎo)致路徑規(guī)劃算法性能降低。當(dāng)前主流的室內(nèi)導(dǎo)航算法主要使用Dijkstra[22-24]或者A*[25-26]來進(jìn)行路徑規(guī)劃。
在移動(dòng)物體導(dǎo)航系統(tǒng)中需要存儲(chǔ)并檢索不同類型的信息。存儲(chǔ)的信息用于導(dǎo)航服務(wù)、路徑規(guī)劃、給導(dǎo)航用戶提供相關(guān)導(dǎo)航場景。
根據(jù)室內(nèi)導(dǎo)航系統(tǒng)中采用的算法,在進(jìn)行展示時(shí),展示信息包括樓宇平面圖、室內(nèi)定位場景中陳設(shè)物的描繪以及擺放位置、定位標(biāo)簽部署以及傳感器回傳的數(shù)據(jù)。室內(nèi)導(dǎo)航場景展示時(shí)可以采用2維(2D)的地圖,在2維地圖上可以展示墻、門或者每條邊上都帶有權(quán)值的訪問路線圖[27]。地圖可以基于導(dǎo)航區(qū)域以及導(dǎo)航用戶實(shí)時(shí)位置來進(jìn)行路徑規(guī)劃。如果導(dǎo)航系統(tǒng)使用標(biāo)簽法來進(jìn)行用戶導(dǎo)航,那么標(biāo)簽的信息將被存儲(chǔ)到地圖中[28]。2D地圖是使用最少資源的一種展示方式。這樣的2D地圖很容易通過建筑物導(dǎo)航場景的CAD圖進(jìn)行創(chuàng)建。但是考慮到導(dǎo)航物體的特殊性以及導(dǎo)航區(qū)域的危險(xiǎn)性,例如容易碰頭等,這使得向2D地圖中添加詳細(xì)信息難度加大。
3D模型可以用來展示室內(nèi)導(dǎo)航場景[29]。大量的有用信息可以從這個(gè)3D模型中提取出來,例如門的位置信息、斜坡的坡度、容易碰頭的位置等。雖然建立這些模型費(fèi)用高昂,但是這些模型是語言獨(dú)立的并且可以通過物體識(shí)別算法自動(dòng)提取信息從而有助于系統(tǒng)的全球部署。由于3D模型需要更高存儲(chǔ)容量、更快的運(yùn)算速度進(jìn)行信息提取,因此3D模型是資源更加密集型表現(xiàn)形式。表1給出了用于展示的不同技術(shù)的概覽。
表1 不同展示技術(shù)概覽
目前很多室內(nèi)定位系統(tǒng)是為有視覺障礙的人開發(fā)部署的,由于障礙物路標(biāo)的確認(rèn)對有視覺障礙的人在熟悉的環(huán)境中活動(dòng)是十分重要的,因此室內(nèi)定位系統(tǒng)可以以此作為指導(dǎo),沿著容易確認(rèn)的路標(biāo)規(guī)劃一條更為合理、更能容易完成的路徑,盡量避免經(jīng)過寬敞的大門,而是應(yīng)規(guī)劃一條沿著墻行走的路線,這樣使得有視覺障礙的人可以確認(rèn)自己能順利達(dá)到目的地。室內(nèi)定位導(dǎo)航系統(tǒng)也應(yīng)該根據(jù)用戶不同的需求為用戶規(guī)劃更能為合理、智能的路線,例如為輪椅用戶規(guī)劃的路線應(yīng)盡量避免樓梯和斜坡。
在很多室內(nèi)定位系統(tǒng)中,使用2D或者建筑的CAD圖來表示室內(nèi)導(dǎo)航環(huán)境進(jìn)行導(dǎo)航。3D虛擬化模型可以被用來更精確、多層次地表示室內(nèi)定位場景,比如哪里容易碰頭、斜坡、不平的地面和路軌等。這些因素對視覺有障礙的用戶來說應(yīng)該避免。雖然隨著3D地圖自動(dòng)生成技術(shù)的進(jìn)步,3D模型制作成本顯著下降,但是相比創(chuàng)建一個(gè)2D模型而言,創(chuàng)建一個(gè)3D模型的成本還是太高。不論是2D模型還是3D模型,都需要備注地址信息,例如房間號(hào)、路標(biāo)、門等,這可以利用群眾資源以及開發(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)技術(shù)在高校圖書館管理中的應(yīng)用[J].唐山師范學(xué)院學(xué)報(bào),2016,38(5):143-145.
[23] 孫曄.京津冀一體化與區(qū)域智慧物流的協(xié)同發(fā)展[J].唐山師范學(xué)院學(xué)報(bào),2015,37(5):149-152.
[24] 朱程.淺析信任管理在物聯(lián)網(wǎng)安全中的應(yīng)用[J].唐山師范學(xué)院學(xué)報(bào),2015,37(2):52-54.
[25] 劉曉春.加快唐山市物聯(lián)網(wǎng)發(fā)展打造“U唐山”的對策[J].唐山師范學(xué)院學(xué)報(bào),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)基金項(xiàng)目(1401801),西南交大合作智慧水務(wù)項(xiàng)目(1200305),唐山市科技計(jì)劃項(xiàng)目(220020502)
2018-07-30
2018-09-19
郝天鹿(1980-),男,河北唐山人,碩士,實(shí)驗(yàn)師,研究方向?yàn)槲锫?lián)網(wǎng)。
(責(zé)任編輯、校對:田敬軍)