Indoor navigation network models: A comparative investigation

Abstract

Nowadays, the use of outdoor navigation applications is quite common. For indoor navigation, this case is still an emerging application due to the lack of use of a standardised positioning equipment, higher costs, accuracy issues, the more complex structure of indoor spaces and the fact that a comprehensive network model to support indoor navigation for floor-level paths and non-level paths and the studies on the computation of routes are not fully developed yet. Due to the degree of complexity of indoor spaces vary depending on the non-standard structures of buildings and the freedom of movement capability is in a wide spectrum, different navigation networks can be generated. In this study, the Medial Axis Transform (MAT) based methods and the Visibility Graph (VG) based network model that originates from isovists theory which are the prominent navigation network models in the literature are generated in the building information modelling of Yildiz Technical University Civil Engineering Faculty building by utilizing the two-dimensional floor plans of the building and a new approach is proposed based on the VG model by restricting the line of sight between sub-corridors of indoor space and combining it with the MAT. The usability of these navigation network models is compared in terms of the shortest distance and the fewest turns made on the route. The findings of the experimental study showed that the VG based network model which is shown in previous studies to be correlated with human perception enables a mean of 1.17 m shorter distances and 0.20 times fewer turns than the compared routes compared to closest network model. The statistical tests demonstrated that the proposed hybrid approach does not differ significantly from VG thus can be used instead of VG based model for various scenarios.

Keywords

• Indoor navigation
• Navigation network model
• Medial axis transform
• Visibility graph
• Building information modelling

İç mekân navigasyonu ağ modelleri: Karşılaştırmalı bir inceleme

Abstract

Günümüzde açık alanlarda kullanılan navigasyon uygulamaları oldukça yaygındır. İç mekânlarda ise bu durum herkes tarafından kabul görmüş standart bir konumlama donanımının kullanılmaması, daha yüksek maliyet, doğruluk sorunları, iç mekânın yapısının dış mekânlara kıyasla karmaşıklık göstermesi ve iç mekân navigasyonunu kat düzeyi ve katlar arası düzeyde destekleyecek kapsayıcı ağ modelleri ve rota hesaplamalarına yönelik çalışmaların yeterince olgunlaşmamış olması nedeniyle henüz gelişme aşamasındadır. İç mekânların standart olmayan yapısına bağlı olarak karmaşıklık derecesinin değişkenlik göstermesi ve iç mekân içerisindeki hareket kabiliyetinin geniş bir spektrumda olması nedeniyle farklı navigasyon ağ modelleri oluşturulabilmektedir. Bu çalışmada literatürde öne çıkan Orta Eksen Dönüşümü (OED) tabanlı ağ modelleri ve eş görünüm alanları teorisinden yararlanarak geliştirilen Görünürlük Çizgesi (GÇ) tabanlı ağ modeli, Yıldız Teknik Üniversitesi İnşaat Fakültesi binasına ilişkin kat planları kullanılarak üretilen yapı bilgi modeli üzerinde uygulanmış, alt koridorlar arasında görüş alanı sınırlaması getirilerek GÇ ve OED kombinasyonuyla yeni bir yaklaşım önerilmiştir. Elde edilen modellerin kullanılabilirlikleri en kısa mesafe ve rotalar üzerinden yapılan dönüş sayısı kriterlerine göre karşılaştırılmıştır. Deneysel çalışmaya ilişkin bulgular, literatürde insan algısı ile ilişkili olduğu gösterilen GÇ’nin karşılaştırılan rotalar için en yakın ağ modeline göre mesafelerin ortalama 1.17 m kısalmasını ve dönüş sayılarının 0.20 kez azalmasını sağladığını göstermiştir. İstatistiki test sonuçları, önerilen hibrit yöntemin GÇ’den anlamlı bir şekilde farklılaşmadığını ve çeşitli senaryolar için GÇ tabanlı ağ modeli yerine kullanılabileceğini göstermiştir.

Keywords

• İç mekân navigasyonu
• Navigasyon ağ modeli
• Orta eksen dönüşümü
• Görünürlük çizgesi
• Yapı bilgi modellemesi

References

1. Afyouni, I., Ray, C., & Christophe, C. (2012). Spatial models for context-aware indoor navigation systems: A survey. Journal of Spatial Information Science, 1(4), 85-123.
2. Benedikt, M. L. (1979). To take hold of space: isovists and isovist fields. Environment and Planning B: Planning and design, 6(1), 47-65.
3. Chen, A. Y., & Huang, T. (2015). Toward BIM-enabled decision making for in-building response missions. IEEE Transactions on Intelligent Transportation Systems, 16(5), 2765-2773.
4. Chen, J., & Clarke, K. C. (2020). Indoor cartography. Cartography and Geographic Information Science, 47(2), 95-109.
5. Choi, J., & Lee, J. (2009). 3D geo-network for agent-based building evacuation simulation. In 3D geo-information sciences (s. 283-299). Springer, Berlin, Heidelberg.
6. Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische mathematik, 1(1), 269-271.
7. Fallah, N., Apostolopoulos, I., Bekris, K., & Folmer, E. (2013). Indoor human navigation systems: A survey. Interacting with Computers, 25(1), 21-33.
8. Fisher, R. A. (1921). On the probable error of a coefficient of correlation deduced from a small sample. Metron, 1, 1-32.

9. Giudice, N. A., Walton, L. A., & Worboys, M. (2010). The informatics of indoor and outdoor space: a research agenda. In Proceedings of the 2nd ACM SIGSPATIAL International Workshop on Indoor Spatial Awareness (s. 47-53).
10. Gunduz, M., Isikdag, U., & Basaraner, M. (2016). Trending Technologies for Indoor FM: Looking for" Geo" in Information. ISPRS Annals of Photogrammetry, Remote Sensing & Spatial Information Sciences, 4.
11. Isikdag, U., Zlatanova, S., & Underwood, J. (2013). A BIM-Oriented Model for supporting indoor navigation requirements. Computers, Environment and Urban Systems, 41, 112-123.
12. Kneidl, A., Borrmann, A., & Hartmann, D. (2012). Generation and use of sparse navigation graphs for microscopic pedestrian simulation models. Advanced Engineering Informatics, 26(4), 669-680.
13. Knoth, L., Mittlböck, M., Vockner, B., Andorfer, M., & Atzl, C. (2019). Buildings in GI: How to deal with building models in the GIS domain. Transactions in GIS, 23(3), 435-449.
14. Koyuncu, H., & Yang, S. H. (2010). A survey of indoor positioning and object locating systems. IJCSNS International Journal of Computer Science and Network Security, 10(5), 121-128.
15. Kwan, M. P., & Lee, J. (2005). Emergency response after 9/11: the potential of real-time 3D GIS for quick emergency response in micro-spatial environments. Computers, Environment and Urban Systems, 29(2), 93-113.
16. Lee, D. T. (1982). Medial axis transformation of a planar shape. IEEE Transactions on pattern analysis and machine intelligence, (4), 363-369.
17. Lee, J. (2004). A spatial access-oriented implementation of a 3-D GIS topological data model for urban entities. GeoInformatica, 8(3), 237-264.
18. Lee, J. K., Eastman, C. M., Lee, J., Kannala, M., & Jeong, Y. S. (2010). Computing walking distances within buildings using the universal circulation network. Environment and Planning B: Planning and Design, 37(4), 628-645.
19. Li, D., & Lee, D. L. (2008). A lattice-based semantic location model for indoor navigation. In The Ninth International Conference on Mobile Data Management (mdm 2008) (s. 17-24). IEEE.
20. Li, H., Chan, G., Wong, J. K. W., & Skitmore, M. (2016). Real-time locating systems applications in construction. Automation in Construction, 63, 37-47.
21. Lin, W. Y., & Lin, P. H. (2018). Intelligent generation of indoor topology (i-GIT) for human indoor pathfinding based on IFC models and 3D GIS technology. Automation in construction, 94, 340-359.
22. Liu, L., Li, B., Zlatanova, S., & van Oosterom, P. (2021). Indoor navigation supported by the Industry Foundation Classes (IFC): A survey. Automation in Construction, 121, 103436.
23. Mast, V., Jian, C., & Zhekova, D. (2012). Elaborate descriptive information in indoor route instructions. In Proceedings of the Annual Meeting of the Cognitive Science Society (Vol. 34, No. 34).
24. Mortari, F., Zlatanova, S., Liu, L., & Clementini, E. (2014). Improved Geometric Network Model (IGNM): A novel approach for deriving connectivity graphs for indoor navigation. ISPRS Annals of Photogrammetry, Remote Sensing & Spatial Information Sciences, 2(4).
25. Müller, M., Ohm, C., Schwappach, F., & Ludwig, B. (2017). The path of least resistance: Calculating preference adapted routes for pedestrian navigation. KI-Künstliche Intelligenz, 31(2), 125-134.
26. Ohm, C., Müller, M., & Ludwig, B. (2015). Displaying landmarks and the user’s surroundings in indoor pedestrian navigation systems. Journal of Ambient Intelligence and Smart Environments, 7(5), 635-657.
27. Pang, Y., Zhou, L., Lin, B., Lv, G., & Zhang, C. (2020). Generation of navigation networks for corridor spaces based on indoor visibility map. International Journal of Geographical Information Science, 34(1), 177-201.
28. Park, J., Goldberg, D. W., & Hammond, T. (2020). A comparison of network model creation algorithms based on the quality of wayfinding results. Transactions in GIS, 24(3), 602-622.
29. Puértolas Montañés, J. A., Mendoza Rodríguez, A., & Sanz Prieto, I. (2013). Smart indoor positioning/location and navigation: A lightweight approach, International Journal of Interactive Multimedia and Artificial Intelligence, 2(2), 43-50.
30. Rüetschi, U. J., & Timpf, S. (2005). Modelling wayfinding in public transport: Network space and scene space. In International Conference on Spatial Cognition (s. 24-41). Springer, Berlin, Heidelberg.
31. Taneja, S., Akinci, B., Garrett, J. H., Soibelman, L., & East, B. (2011). Transforming IFC-based building layout information into a geometric topology network for indoor navigation assistance. In Computing in Civil Engineering (2011) (s. 315-322).
32. Stoffel, E. P., Lorenz, B., & Ohlbach, H. J. (2007). Towards a semantic spatial model for pedestrian indoor navigation. In International conference on conceptual modeling (s. 328-337). Springer, Berlin, Heidelberg.
33. Turner, A., Doxa, M., O'sullivan, D., & Penn, A. (2001). From isovists to visibility graphs: a methodology for the analysis of architectural space. Environment and Planning B: Planning and design, 28(1), 103-121.
34. Vanclooster, A., Vanhaeren, N., Viaene, P., Ooms, K., De Cock, L., Fack, V., ... & De Maeyer, P. (2019). Turn calculations for the indoor application of the fewest turns path algorithm. International Journal of Geographical Information Science, 33(11), 2284-2304.
35. Yang, L., & Worboys, M. (2015). Generation of navigation graphs for indoor space. International Journal of Geographical Information Science, 29(10), 1737-1756.
36. Zhong, R. Y., Xu, X., Klotz, E., & Newman, S. T. (2017). Intelligent manufacturing in the context of industry 4.0: a review. Engineering, 3(5), 616-630.
37. Zlatanova, S., Liu, L., & Sithole, G. (2013). A conceptual framework of space subdivision for indoor navigation. In Proceedings of the fifth ACM SIGSPATIAL international workshop on indoor spatial awareness (s. 37-41).
38. Zlatanova, S., Liu, L., Sithole, G., Zhao, J., & Mortari, F. (2014). Space Subdivision for Indoor Applications; OTB Research Institute for the Built Environment. Delft University of Technology: Delft, The Netherlands. URL-1: https://standards.buildingsmart.org/IFC/RELEASE/IFC2x3/FINAL/HTML/ (Erişim Tarihi: 25 Mayıs 2021).