Indoor Semantic Modelling for Routing: The Two-Level Routing Approach for Indoor Navigation
DOI:
https://doi.org/10.7480/abe.2017.17.1879Keywords:
geoinformation, geo-information, semantic modelling, routing, navigationAbstract
Humans perform many activities indoors and they show a growing need for indoor navigation, especially in unfamiliar buildings such as airports, museums and hospitals. Complexity of such buildings poses many challenges for building managers and visitors. Indoor navigation services play an important role in supporting these indoor activities. Indoor navigation covers extensive topics such as: 1) indoor positioning and localization; 2) indoor space representation for navigation model generation; 3) indoor routing computation; 4) human wayfinding behaviours; and 5) indoor guidance (e.g., textual directories). So far, a large number of studies of pedestrian indoor navigation have presented diverse navigation models and routing algorithms/methods. However, the major challenge is rarely referred to: how to represent the complex indoor environment for pedestrians and conduct routing according to the different roles and sizes of users. Such complex buildings contain irregular shapes, large open spaces, complicated obstacles and different types of passages. A navigation model can be very complicated if the indoors are accurately represented. Although most research demonstrates feasible indoor navigation models and related routing methods in regular buildings, the focus is still on a general navigation model for pedestrians who are simplified as circles. In fact, pedestrians represent different sizes, motion abilities and preferences (e.g., described in user profiles), which should be reflected in navigation models and be considered for indoor routing (e.g., relevant Spaces of Interest and Points of Interest).
In order to address this challenge, this thesis proposes an innovative indoor modelling and routing approach – two-level routing. It specially targets the case of routing in complex buildings for distinct users. The conceptual (first) level uses general free indoor spaces: this is represented by the logical network whose nodes represent the spaces and edges stand for their connectivity; the detailed (second) level focuses on transition spaces such as openings and Spaces of Interest (SOI), and geometric networks are generated regarding these spaces. Nodes of a geometric network refers to locations of doors, windows and subspaces (SOIs) inside of the larger spaces; and the edges represent detailed paths among these geometric nodes. A combination of the two levels can represent complex buildings in specified spaces, which avoids maintaining a largescale complete network. User preferences on ordered SOIs are considered in routing on the logical network, and preferences on ordered Points of Interest (POI) are adopted in routing on geometric networks. In a geometric network, accessible obstacle-avoiding paths can be computed for users with different sizes.
To facilitate automatic generation of the two types of network in any building, a new data model named Indoor Navigation Space Model (INSM) is proposed to store connectivity, semantics and geometry of indoor spaces for buildings. Abundant semantics of building components are designed in INSM based on navigational functionalities, such as VerticalUnit(VU) and HorizontalConnector(HC) as vertical and horizontal passages for pedestrians. The INSM supports different subdivision ways of a building in which indoor spaces can be assigned proper semantics.
A logical and geometric network can be automatically derived from INSM, and they can be used individually or together for indoor routing. Thus, different routing options are designed. Paths can be provided by using either the logical network when some users are satisfied with a rough description of the path (e.g., the name of spaces), or a geometric path is automatically computed for a user who needs only a detailed path which shows how obstacles can be avoided. The two-level routing approach integrates both logical and geometric networks to obtain paths, when a user provides her/his preferences on SOIs and POIs. For example, routing results for the logical network can exclude unrelated spaces and then derive geometric paths more efficiently. In this thesis, two options are proposed for routing just on the logical network, three options are proposed for routing just on the geometric networks, and seven options for two-level routing.
On the logical network, six routing criteria are proposed and three human wayfinding strategies are adopted to simulate human indoor behaviours. According to a specific criterion, space semantics of logical nodes is utilized to assign different weights to logical nodes and edges. Therefore, routing on the logical network can be accomplished by applying the Dijkstra algorithm. If multiple criteria are adopted, an order of criteria is applied for routing according to a specific user. In this way, logical paths can be computed as a sequence of indoor spaces with clear semantics.
On geometric networks, this thesis proposes a new routing method to provide detailed paths avoiding indoor obstacles with respect to pedestrian sizes. This method allows geometric networks to be derived for individual users with different sizes for any specified spaces.
To demonstrate the use of the two types of network, this thesis tests routing on one level (the logical or the geometric network). Four case studies about the logical network are presented in both simple and complex buildings. In the simple building, no multiple paths lie between spaces A and B, but in the complex buildings, multiple logical paths exist and the candidate paths can be reduced by applying these routing criteria in an order for a user. The relationships of these criteria to user profiles are assumed in this thesis.
The proposed geometric routing regarding user sizes is tested with three case studies: 1) routing for pedestrians with two distinct sizes in one space; 2) routing for pedestrians with changed sizes in one space; and 3) a larger geometric network formed by the ones in a given sequence of spaces. The first case shows that a small increase of user size can largely change the accessible path; the second case shows different path segments for distinct sizes can be combined into one geometric path; the third case demonstrates a geometric network can be created ’on the fly’ for any specified spaces of a building. Therefore, the generation and routing of geometric networks are very flexible and fit to given users.
To demonstrate the proposed two-level routing approach, this thesis designs five cases. The five cases are distinguished according to the method of model creation (pre-computed or ’on-the-fly’) and model storage (on the client or server). Two of them are realized in this thesis: 1) Case 1 just in the client pre-computes the logical network and derives geometric networks ’on the fly’; 2) Case 2 just in the client pre-computes and stores the logical and geometric networks for certain user sizes. Case 1 is implemented in a desktop application for building managers, and Case 2 is realized as a mobile mock-up for mobile users without an internet connection.
As this thesis shows, two-level routing is powerful enough to effectively provide indicative logical paths and/or comprehensive geometric paths, according to different user requirements on path details. In the desktop application, three of the proposed routing options for two-level routing are tested for the simple OTB building and the complex Schiphol Airport building. These use cases demonstrate that the two-level routing approach includes the following merits:
- It supports routing in different abstraction forms of a building. The INSM model can describe different subdivision results of a building, and it allows two types of routing network to be derived – pure logical and geometric ones. The logical network contains the topology and semantics of indoor spaces, and the geometric network provides accurate geometry for paths. A consistent navigation model is formed with the two networks, i.e., the conceptual and detailed levels.
- On the conceptual level, it supports routing on a logical network and assists the derivation of a conceptual path (i.e., logical path) for a user in terms of space sequence. Routing criteria are designed based on the INSM semantics of spaces, which can generate logical paths similar to human wayfinding results such as minimizing VerticalUnit or HorizontalConnector.
- On the detailed level, it considers the size of users and results in obstacle-avoiding paths. By using this approach, geometric networks can be generated to avoid obstacles for the given users and accessible paths are flexibly provided for user demands. This approach can process changes of user size more efficiently, in contrast to routing on a complete geometric network.
- It supports routing on both the logical and the geometric networks, which can generate geometric paths based on user-specific logical paths, or re-compute logical paths when geometric paths are inaccessible. This computation method is very useful for complex buildings. The two-level routing approach can flexibly provide logical and geometric paths according to user preferences and sizes, and can adjust the generated paths in limited time.
Based on the two-level routing approach, this thesis also provides a vision on possible cooperation with other methods. A potential direction is to design more routing options according to other indoor scenarios and user preferences. Extensions of the two-level routing approach, such as other types of semantics, multi-level networks and dynamic obstacles, will make it possible to deal with other routing cases. Last but not least, it is also promising to explore its relationships with indoor guidance, different building subdivisions and outdoor navigation.
References
N. Akkiraju, H. Edelsbrunner, M. Facello, P. Fu, E.P. Mcke, and C. Varela. Alpha shapes: Defini- tion and software. In Proceedings of the 1st International Computational Geometry Software Workshop, pages 63–66, 1995.
U.S. Environmental Protection Agency. Buildings and their impact on the environment: A sta- tistical summary, 2009. Online https://archive.epa.gov/greenbuilding/web/pdf/gbstats.pdf.
AmsterdamTourist.info. Airport schiphol, 2015. Online http://www.amsterdamtourist.info/about-amsterdam/transportation/amsterdam- airport-schiphol/.
A.K. Andreas and J.C. Smith. Decomposition algorithms for the design of a nonsimultaneous capacitated evacuation tree network. Networks, 53(2):91–103, 2009.
C. Andújar, P. Vázquez, and M. Fairén. Way-finder: guided tours through complex walkthrough models. In Computer Graphics Forum, volume 23, pages 499–508. Wiley Online Library, 2004.
H. Alt and E. Welzl. Visibility graphs and obstacle-avoiding shortest paths. Zeitschrift für Operations Research, 32(3-4):145–164, 1988.
D.L. Butler, A.L. Acquino, A.A. Hissong, and P.A. Scott. Wayfinding by newcomers in a com- plex building. Human factors: The Journal of the Human Factors and Ergonomics Society, 35(1):159–173, 1993.
G. Brusa, M.L. Caliusco, and O. Chiotti. A process for building a domain ontology: an experience in developing a government budgetary ontology. In Proceedings of the second Australasian workshop on Advances in ontologies-Volume 72, pages 7–15. Australian Computer Society, Inc., 2006.
C. Becker and F. Dürr. On location models for ubiquitous computing. Personal Ubiquitous Computing, 9(1):20–31, January 2005. doi=http://dx.doi.org/10.1007/s00779-004-0270-
R. Bellman. On a routing problem. Quarterly of applied mathematics, pages 87–90, 1958. [BFH97] W. Burgard, D. Fox, and D. Hennig. Fast grid-based position tracking for mobile robots. In
Annual Conference on Artificial Intelligence, pages 289–300. Springer, 1997.
P. Boguslawski and C. Gold. Euler operators and navigation of multi-shell building models. In
Developments in 3D geo-information sciences, pages 1–16. Springer, 2010.
P. Boguslawski, C.M. Gold, and H. Ledoux. Modelling and analysing 3D buildings with a pri- mal/dual data structure. ISPRS Journal of Photogrammetry and Remote Sensing, 66(2):188– 197, 2011.
C. Blum. Ant colony optimization: Introduction and recent trends. Physics of Life reviews, 2(4):353–373, 2005.
J.E. Bell and P.R. McMullen. Ant colony optimization techniques for the vehicle routing prob- lem. Advanced Engineering Informatics, 18(1):41–48, 2004.
P. Boguslawski, L. Mahdjoubi, V. Zverovich, and F. Fadli. Automated construction of variable density navigable networks in a 3D indoor environment for emergency response. Automation in Construction, 72, Part 2:115 – 128, 2016.
T. Becker, C. Nagel, and T.H. Kolbe. A multilayered space-event model for navigation in in- door spaces. In J. Lee and S. Zlatanova, editors, 3D Geo-Information Sciences, Lecture Notes in Geoinformation and Cartography, pages 61–77. Springer Berlin Heidelberg, 2009.
G. Brown, C. Nagel, S. Zlatanova, and T.H. Kolbe. Modelling 3D topographic space against indoor navigation requirements. In Progress and New Trends in 3D Geoinformation Sciences, pages 1–22. Springer, 2013.
U. Brandes. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25(2):163–177, 2001.
Brumitt B. and Shafer S. Topological world modeling using semantic spaces. In Proceedings of the Workshop on Location Modeling for Ubiquitous Computing, page 55–62, September 2001 2001.
S. Bandi and D. Thalmann. Space discretization for efficient human navigation. In Computer Graphics Forum, volume 17, pages 195–206. Wiley Online Library, 1998.
[BV13] P. Boldi and S. Vigna. Axioms for centrality. Internet Mathematics, 10:222–262, 2013. [CD85] B. Chazelle and D.P. Dobkin. Optimal convex decompositions. Machine Intelligence & Pattern
Recognition, 2(5):63–133, 1985.
M. Caramia and P. Dell´ Olmo. Multi-objective optimization. Multi-objective Management in Freight Logistics: Increasing Capacity, Service Level and Safety with Optimization Algorithms, pages 11–36, 2008.
J. Choi and J. Lee. 3D geo-network for agent-based building evacuation simulation. In 3D geo-information sciences, pages 283–299. Springer, 2009.
Fuchs C., Aschenbruck N., Martini P., and Wieneke M. Indoor tracking for mission critical sce- narios: A survey. Pervasive and Mobile Computing, 7(1):1 – 15, 2011.
S.A.M. Coenen. Motion planning for mobile robots - a guide. Master’s thesis, Mechanical Engineering, Eindhoven University of Technology, Eindhoven, 2012.
SQLite Consortium. About sqlite, 2016. Online http://sqlite.org/about.html.
Hölscher C., Meilinger T., Vrachliotis G., Brösamle M., and Knauff M. Up the down staircase: Wayfinding strategies in multi-level buildings. Journal of Environmental Psychology, 26(4):284
– 299, 2006.
L.C. Chen, C.H. Wu, T.S. Shen, and C.C. Chou. The application of geometric network models and building information models in geospatial environments for fire-fighting simulations. Computers, Environment and Urban Systems, 45(0):1 – 12, 2014.
M. de Berg, O. Cheong, M. van Kreveld, and M.H. Overmars. Computational Geometry: Algo- rithms and Applications. Springer-Verlag TELOS, Santa Clara, CA, USA, 3rd ed. edition, 2008.
K. Deb. Multi-objective optimization. In E.K. Burke and G. Kendall, editors, Search Methodolo- gies, pages 403–449. Springer US, 2014. http://dx.doi.org/10.1007/978-1-4614-6940- 7_15.
P.M. Dudas, M. Ghafourian, and H.A. Karimi. ONALIN: Ontology and algorithm for indoor rout- ing. In 2009 Tenth International Conference on Mobile Data Management: Systems, Services and Middleware, pages 720–725. IEEE, 2009.
P.M. Dudas, M. Ghafourian, and H.A. Karimi. Onalin: Ontology and algorithm for indoor rout- ing. In Mobile Data Management: Systems, Services and Middleware, 2009. MDM ’09. Tenth International Conference on, pages 720–725, May 2009.
R. Diestel. Graph Theory. Springer-Verlag Berlin Heidelberg, 4th edition, 2010.
E.W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1(1):269–271, 1959.
Li D. and D.L. Lee. A lattice-based semantic location model for indoor navigation. In 2008 the 9th International Conference on Mobile Data Management, pages 17–24, April 2008.
B. Dominguez-Martin, P. van Oosterom, F. Feito-Higueruela, A.L. Garcia-Fernandez, and C.J. Ogayar-Anguita. Automatic generation of medium-detailed 3D models of buildings based on cad data (abstract). In CGI’15, 32nd annual Conference, Strasbourg, page 2, June 2015.
A.A. Diakité and S. Zlatanova. Extraction of the 3D free space from building models for indoor navigation. ISPRS Annals of Photogrammetry, Remote Sensing and Spatial Information Sciences, IV-2/W1:241–248, 2016.
D. Eppstein and J. Erickson. Raising roofs, crashing cycles, and playing pool: Applications of a data structure for finding pairwise interactions. Discrete & Computational Geometry, 22(4):569–592, 1999.
H. Edelsbrunner and E.P. Mücke. Three-dimensional alpha shapes. ACM Trans. Graph., 13(1):43–72, January 1994.
F.W. Fichtner. Semantic enrichment of a point cloud based on an octree for multi-storey pathfinding. Master’s thesis, Urbanism Department, Faculty of Architecture and The Built Environment, Delft University of Technology, Netherlands, 2016.
L.R. Ford Jr. Network flow theory. Technical report, DTIC Document, 1956.
Z. Fang, Q. Li, X. Zhang, and S. Shaw. A GIS data model for landmark-based pedestrian naviga- tion. International Journal of Geographical Information Science, 26(5):817–838, 2012.
C. Freksa, R. Moratz, and T. Barkowsky. Schematic maps for robot navigation. In C. Freksa,
C. Habel, W. Brauer, and K.F. Wender, editors, Spatial Cognition II, volume 1849 of Lecture Notes in Computer Science, pages 100–114. Springer Berlin Heidelberg, 2000.
G. Franz, H. Mallot, J. Wiener, and K. Neurowissenschaft. Graph-based models of space in archi- tecture and cognitive science-a comparative analysis. In Proceedings of the 17th International Conference on Systems Research, Informatics and Cybernetics, volume 3038, 2005.
Z. Fang, X. Zong, Q. Li, Q. Li, and S. Xiong. Hierarchical multi-objective evacuation routing in stadium using ant colony optimization approach. Journal of Transport Geography, 19(3):443– 451, 2011.
Sabidussi G. The centrality index of a graph. Psychometrika, 31(4):581–603, 1966.
R. Goldstein, S. Breslav, and A. Khan. Towards voxel-based algorithms for building performance simulation. In Proceedings of the IBPSA-Canada eSim Conference, 2014.
G. Girard, S. Côté, S. Zlatanova, Y. Barette, J. St-Pierre, and P. Van Oosterom. Indoor pedes- trian navigation using foot-mounted IMU and portable ultrasound range sensors. Sensors, 11(8):7606–7624, 2011.
G. Gröger, T.H. Kolbe, C. Nagel, and K.H. Häfele. OGC City Geography Markup Language (CityGML) Encoding Standard, 2012.
R. Geraerts and M.H. Overmars. The corridor map method: a general framework for real-time high-quality path planning. Computer Animation and Virtual Worlds, 18(2):107–119, 2007.
C. Galindo, A. Saffiotti, S. Coradeschi, P. Buschka, J.A. Fernandez-Madrigal, and J. Gonzalez.
Multi-hierarchical semantic maps for mobile robotics. In Intelligent Robots and Systems, 2005. (IROS 2005). 2005 IEEE/RSJ International Conference on, pages 2278–2283, Aug 2005.
M. Goetz and A. Zipf. Extending OpenStreetMap to indoor environments, pages 51–61. CRC Press, 2011. doi:10.1201/b11647-7.
M. Goetz and A. Zipf. Formal definition of a user-adaptive and length-optimal routing graph for complex indoor environments. Geo-spatial Information Science, 14(2):119–128, 2011.
M. Goetz and A. Zipf. Indoor route planning with volunteered geographic information on a (mobile) web-based platform. In J.M. Krisp, editor, Progress in Location-Based Services, Lecture Notes in Geoinformation and Cartography, pages 211–231. Springer Berlin Heidelberg, 2013.
B.M. Harvey. Perform + function: A proposal for a healthy public housing community. Master’s thesis, 2012.
C. Hölscher and M. Brösamle. Capturing indoor wayfinding strategies and differences in spatial knowledge with space syntax. In Proceedings, 6th International Space Syntax Symposium, İstanbul, 2007.
S.C. Hirtle and C.R. Bahm. Cognition for the Navigation of Complex Indoor Environments, pages 1–12. CRC Press, 2015. doi:10.1201/b18220-2.
M. Höcker, V. Berkhahn, A. Kneidl, A. Borrmann, and W. Klein. Graph-based approaches for simulating pedestrian dynamics in building models. eWork and eBusiness in Architecture, Engineering and Construction, pages 389–394, 2010.
Hu H. and Lee D.L. Semantic location modeling for location navigation in mobile environment. In Proceedings of 2004 IEEE International Conference on Mobile Data Management, pages 52– 61, 2004.
T. Helms. A voxel-based platform for game development. 2013.
I.H. Hijazi, M. Ehlers, and S. Zlatanova. NIBU: a new approach to representing and analysing interior utility networks within 3D geo-information systems. International Journal of Digital Earth, 5(1):22–42, 2012.
H. Hile, R. Grzeszczuk, A. Liu, R. Vedantham, J. Košecka, and G. Borriello. Landmark-based pedestrian navigation with enhanced spatial reasoning. In International Conference on Perva- sive Computing, pages 59–76. Springer, 2009.
C.S. Han, K.H. Law, J.C. Latombe, and J.C. Kunz. A performance-based approach to wheelchair accessible route analysis. Advanced Engineering Informatics, 16(1):53 – 71, 2002.
P.E. Hart, N.J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of mini- mum cost paths. IEEE transactions on Systems Science and Cybernetics, 4(2):100–107, 1968.
Zender H., Martínez Mozos O., Jensfelt P., Kruijff G.-J.M., and Burgard W. Conceptual spatial representations for indoor mobile robots. Robotics and Autonomous Systems, 56(6):493 – 502, 2008. From Sensors to Human Spatial Concepts.
A.M. Hund and A.J. Padgitt. Direction giving and following in the service of wayfinding in a complex indoor environment. Journal of Environmental Psychology, 30(4):553–564, 2010.
D. Heckmann, T. Schwartz, B. Brandherm, M. Schmitz, and M. von Wilamowitz-Moellendorff. GUMO –the general user model ontology. In L. Ardissono, P. Brna, and A. Mitrovic, editors, User Modeling 2005, volume 3538 of Lecture Notes in Computer Science, pages 428–432. Springer Berlin Heidelberg, 2005.
M.L. Hidayetoglu, K. Yildirim, and A. Akalin. The effects of color and light on indoor wayfind- ing and the evaluation of the perceived environment. Journal of Environmental Psychology, 32(1):50–58, 2012.
IAI. IFC overview summary, 2016. Online http://www.buildingsmart- tech.org/specifications/ifc-overview.
Afyouni I., Ray C., and Claramunt C. Spatial models for context-aware indoor navigation sys- tems: A survey. J. Spatial Information Science, 4(1):85–123, 2012.
The igraph core team. igraph, 2016. Online http://igraph.org.
Microsoft Inc. Visual studio downloads, 2017. online https://www.visualstudio.com/downloads/.
IndoorAtlas. Indooratlas platform, 2016. Online: https://www.indooratlas.com/.
U. Isikdag and S. Zlatanova. Towards defining a framework for automatic generation of buildings in CityGML using building information models. In 3D Geo-Information Sciences, pages 79–96. Springer, 2009.
C.S. Jensen, H. Lu, and B. Yang. Graph model based indoor tracking. In 2009 Tenth Inter- national Conference on Mobile Data Management: Systems, Services and Middleware, pages 122–131. IEEE, 2009.
Lee J. and Kwan M.P. A combinatorial data model for representing topological relations among 3D geographical features in microspatial environments. Inter- national Journal of Geographical Information Science, 19(10):1039–1056, 2005. doi=http://dx.doi.org/10.1080/13658810500399043.
C. Jiang and P. Steenkiste. A hybrid location model with a computable location identifier for ubiquitous computing. In G. Borriello and L. Holmquist, editors, UbiComp 2002: Ubiquitous Computing, volume 2498 of Lecture Notes in Computer Science, pages 246–263. Springer Berlin Heidelberg, 2002. doi=http://dx.doi.org/10.1007/3-540-45809-3_20.
D. Jones and M. Tamiz. Practical goal programming, volume 141. Springer, 2010.
Thill J., Dao T.H.D., and Zhou Y. Traveling in the three-dimensional city: applications in route planning, accessibility assessment, location analysis and beyond. Journal of Transport Geogra- phy, 19(3):405 – 421, 2011. Special Issue: Geographic Information Systems for Transporta- tion.
A. Kneidl, A. Borrmann, and D. Hartmann. Generation and use of sparse navigation graphs for microscopic pedestrian simulation models. Advanced Engineering Informatics, 26(4):669 – 680, 2012.
H.A. Karimi and M. Ghafourian. Indoor routing for individuals with special needs and prefer- ences. Transactions in GIS, 14(3):299–329, 2010.
I. Karamouzas, R. Geraerts, and M.H. Overmars. Indicative routes for path planning and crowd simulation. In Proceedings of the 4th International Conference on Foundations of Digital Games, pages 113–120. ACM, 2010.
T.H. Kolbe, G. Gröger, and L. Plümer. CityGML: Interoperable access to 3D city models. In Geo- information for disaster management, pages 883–899. Springer, 2005.
J.J. Kuffner Jr. Goal-directed navigation for animated characters using real-time path planning and control. In Modelling and Motion Capture Techniques for Virtual Environments, pages 171–
Springer, 1998.
A.A. Khan and T.H. Kolbe. Constraints and their role in subspacing for the locomotion types in indoor navigation. In Indoor Positioning and Indoor Navigation (IPIN), page 12, Nov 2012.
M. Khider, S. Kaiser, P. Robertson, and M. Angermann. The effect of maps-enhanced novel movement models on pedestrian navigation performance. In Proceedings of The 12th annual European Navigation Conference (ENC 2008), Toulouse, France, volume 2228, 2008.
N. Kostic and S. Scheider. Automated generation of indoor accessibility information for mobility-impaired individuals. In F. Bacao, M.Y. Santos, and M. Painho, editors, AGILE 2015, Lecture Notes in Geoinformation and Cartography, pages 235–252. Springer International Publishing, 2015.
Y. Kato and Y. Takeuchi. Individual differences in wayfinding strategies. Journal of Environmen- tal Psychology, 23(2):171–188, 2003.
M. Krūminaitė and S. Zlatanova. Indoor space subdivision for indoor navigation. In Proceedings of the Sixth ACM SIGSPATIAL International Workshop on Indoor Spatial Awareness, pages 25– 31. ACM, 2014.
J. Latombe. Robot Motion Planning. Kluwer Academic Publishers, Norwell, MA, USA, 1991.
X. Li, C. Claramunt, and C. Ray. A grid graph-based model for the analysis of 2D indoor spaces. Computers, Environment and Urban Systems, 34(6):532 – 540, 2010. GeoVisualization and the Digital CitySpecial issue of the International Cartographic Association Commission on Geo- Visualization.
F. Lamarche and S. Donikian. Crowd of virtual humans: a new approach for real time navigation in complex and structured environments. Computer Graphics Forum, 23(3):509–518, 2004.
C.Y. Lee. An algorithm for path connections and its applications. IRE transactions on electronic computers, (3):346–365, 1961.
J. Lee. A 3D Data Model for Representing Topological Relationships Between Spatial Entities in Built-Environments. PhD thesis, The Ohio State University, 2001.
J. Lee. A spatial access-oriented implementation of a 3-D GIS topological data model for urban entities. GeoInformatica, 8(3):237–264, 2004.
Y. Li and Z. He. 3D indoor navigation: a framework of combining BIM with 3D GIS. In 2008 the 44th ISOCARP Congress, 2008.
M. Levine, I.N. Jankovic, and M. Palij. Principles of spatial problem solving. Journal of Experi- mental Psychology: General, 111(2):157, 1982.
D. Li and D. Lee. A topology-based semantic location model for indoor applications. In Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geo- graphic Information Systems, GIS ’08, pages 6:1–6:10, New York, NY, USA, 2008. ACM. doi=http://doi.acm.org/10.1145/1463434.1463443.
Quuppa LLC. Quuppa intelligent locating system, 2016. Online http://quuppa.com/. [LLHY08] P. Lin, S.M. Lo, H.C. Huang, and K.K. Yuen. On the use of multi-stage time-varying quickest time approach for optimization of evacuation planning. Fire Safety Journal, 43(4):282–290, 2008.
J. Lee, K.J. Li, S. Zlatanova, T.H. Kolbe, C. Nagel, and T. Becker. IndoorGML, 2014.
B. Lorenz, H.J. Ohlbach, and E.P. Stoffel. A hybrid spatial model for representing indoor envi- ronments. In J.D. Carswell and T. Tezuka, editors, Web and Wireless Geographical Information Systems, volume 4295 of Lecture Notes in Computer Science, pages 102–112. Springer Berlin Heidelberg, 2006.
B. Lorenz, H.J. Ohlbach, and E.P. Stoffel. A hybrid spatial model for representing indoor envi- ronments. In J.D. Carswell and T. Tezuka, editors, Web and Wireless Geographical Information Systems, volume 4295 of Lecture Notes in Computer Science, pages 102–112. Springer Berlin Heidelberg, 2006. doi=http://dx.doi.org/10.1007/11935148_10.
F. Lyardet, D.W. Szeto, and E. Aitenbichler. Context-aware indoor navigation. In European Conference on Ambient Intelligence, pages 290–307. Springer, 2008.
L. Liu, W. Xu, W. Penard, and S. Zlatanova. Leveraging spatial model to improve indoor tracking.
The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, XL-4/W5(4):75–80, 2015.
J. Lertlakkhanakul, Li Y., Choi J., and Bu S. Gongpath: Development of BIM based indoor pedes- trian navigation system. In INC, IMS and IDC, 2009. NCM ’09. Fifth International Joint Confer- ence on, pages 382–388, Aug 2009.
L. Liu and S. Zlatanova. A ”door-to-door” path-finding approach for indoor navigation. In
Proceedings of GeoInformation For Disaster Management Conference 2011, pages 3–8, 2011.
L. Liu and S. Zlatanova. Towards a 3D network model for indoor navigation, pages 79–94. CRC Press, 2011. doi:10.1201/b11647-9.
L. Liu and S. Zlatanova. A semantic data model for indoor navigation. In Proceedings of the Fourth ACM SIGSPATIAL International Workshop on Indoor Spatial Awareness, ISA ’12, pages 1–8, New York, NY, USA, 2012. ACM.
L. Liu and S. Zlatanova. Generating navigation models from existing building data. The Inter- national Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, XL-4/W4(4):19–25, 2013.
L. Liu and S. Zlatanova. A two-level path-finding strategy for indoor navigation. In S. Zlatanova,
R. Peters, A. Dilo, and H. Scholten, editors, Intelligent Systems for Crisis Management, Lecture Notes in Geoinformation and Cartography, pages 31–42. Springer Berlin Heidelberg, 2013.
L. Liu and S. Zlatanova. An approach for indoor path computation among obstacles that consid- ers user dimension. ISPRS International Journal of Geo-Information, 4(4):2821–2841, 2015.
M. Lu, J.F. Zhang, P. Lv, and Z.H. Fan. Least visible path analysis in raster terrain. International Journal of Geographical Information Science, 22(6):645–656, 2008.
R. Mautz. Indoor positioning technologies. Südwestdeutscher Verlag Für Hochschulschriften AG, 2012.
H. Moravec and A. Elfes. High resolution maps from wide angle sonar. In Robotics and Automa- tion. Proceedings. 1985 IEEE International Conference on, volume 2, pages 116–121. IEEE, 1985.
L.E. Miller. Indoor Navigation for First Responders: A Feasibility Study, volume 77. 2006. [MJ05] Kwan M. and Lee J. 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, 2005.
A. Millonig and K. Schechtner. Developing landmark-based pedestrian-navigation systems.
IEEE Transactions on Intelligent Transportation Systems, 8(1):43–49, 2007.
J.R. Munkres. Elements of algebraic topology. 1984.
J.R. Munkres. Elements of Algebraic Topology. Advanced book classics. Addison-Wesley, 1984. [MZLC14] F. Mortari, S. Zlatanova, L. Liu, and E. Clementini. ”Improved Geometric Network Model”(IGNM): a novel approach for deriving connectivity graphs for indoor navigation. IS- PRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 2(4):45, 2014.
M. Meijers, S Zlatanova, and N. Pfeifer. 3D geo-information indoors: structuring for evacuation.
In Proceedings of Next generation 3D city models, 2005.
A. Makri, S. Zlatanova, and E. Verbree. An approach for indoor wayfinding replicating main principles of an outdoor navigation system for cyclists. In The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Indoor-Outdoor Seamless Modelling, Mapping and Navigation, Tokyo (japan), 21-22 May, 2015. International Society of Photogrammetry and Remote Sensing (ISPRS, 2015.
S. Nadi and M.R. Delavar. Multi-criteria, personalized route planning using quantifier-guided ordered weighted averaging operators. International Journal of Applied Earth Observation and Geoinformation, 13(3):322–335, 2011.
N.F. Noy and D.L. McGuinness. Ontology development 101: A guide to creating your first ontol- ogy, 2001. Stanford knowledge systems laboratory technical report KSL-01-05 and Stanford medical informatics technical report SMI-2001-0880, Stanford, CA.
C. Nagel, A. Stadler, and T.H. Kolbe. Conceptual requirements for the automatic reconstruction of building information models from uninterpreted 3D models. Proceedings of the Interna- tional Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, pages 46–53, 2009.
Inc. Open Geospatial Consortium. OpenGIS Implementation Standard for Geographic informa- tion - Simple feature access. 1.2.1 edition, 2011.
R. Otmani, A. Moussaoui, and A. Pruski. A new approach to indoor accessibility. International
Journal of Smart Home, 3(4):1 – 14, 2009.
M.H. Overmars and E. Welzl. New methods for computing visibility graphs. In Proceedings of the Fourth Annual Symposium on Computational Geometry, SCG ’88, pages 164–171, New York, NY, USA, 1988. ACM.
C. Portele, S.J.D. Cox, P. Daisey, R. Lake, and A. Whiteside. Opengis geography markup language (gml) encoding standard version 3.2.1. 07-036, 2007.
A.J. Padgitt and A.M. Hund. How good are these directions? determining direction quality and wayfinding efficiency. Journal of Environmental Psychology, 32(2):164–172, 2012.
A. Pruski. A unified approach to accessibility for a person in a wheelchair. Robot. Auton. Syst., 58(11):1177–1184, November 2010.
S. Pu and S. Zlatanova. Evacuation route calculation of inner buildings. In P. van Oosterom,
S. Zlatanova, and E.M. Fendel, editors, Geo-information for Disaster Management, pages 1143– 1161. Springer Berlin Heidelberg, 2005.
Geraerts R. Planning short paths with clearance using explicit corridors. In IEEE International Conference on Robotics and Automation, pages 1997–2004, 2010.
S. Rabin. A* Aesthetic Optimizations, pages 264–271. Charles River Media, 2000.
K. Rehrl, N. Göll, S. Leitinger, S. Bruntsch, and H. Mentz. Smartphone-based information and navigation aids for public transport travellers. In G. Gartner, W. Cartwright, and M.P. Peterson, editors, Location Based Services and TeleCartography, Lecture Notes in Geoinformation and Cartography, pages 525–544. Springer Berlin Heidelberg, 2007.
H.G. Ryoo, T. Kim, and K.J. Li. Comparison between two OGC standards for indoor space: CityGML and IndoorGML. In Proceedings of the Seventh ACM SIGSPATIAL International Work- shop on Indoor Spatial Awareness, ISA ’15, pages 1:1–1:8, New York, NY, USA, 2015. ACM.
U.J. Rüetschi. Wayfinding in Scene Space Modelling Transfers in Public Transport. PhD thesis, University of Zurich, Zurich, 2007.
O.B.P.M. Rodenberg, E. Verbree, and S. Zlatanova. Indoor A* pathfinding through an octree representation of a point cloud. ISPRS Annals of Photogrammetry, Remote Sensing and Spatial Information Sciences, IV-2/W1:249–255, 2016. doi=10.5194/isprs-annals-IV-2-W1-249- 2016.
M. Raubal and S. Winter. Enriching wayfinding instructions with local landmarks. In Interna- tional Conference on Geographic Information Science, pages 243–259. Springer, 2002.
K.F. Richter and S. Winter. Landmarks: GIScience for intelligent services. Springer Science & Business, 2014.
K. F. Richter, S. Winter, and S. Santosa. Hierarchical representations of indoor spaces. Environ- ment and Planning B: Planning and Design, 38(6):1052–1070, 2011.
D. Russo, S. Zlatanova, and E. Clementini. Route directions generation using visible landmarks. In Proceedings of the Sixth ACM SIGSPATIAL International Workshop on Indoor Spatial Aware- ness, ISA ’14, pages 1–8, New York, NY, USA, 2014. ACM.
Borgatti S. Centrality and network flow. Social Networks, 27(1):55 – 71, 2005.
D.C. Stevens, M. Akram Khan, D.P. Munson, E. J. Reid, C.C. Helseth, and J. Buggy. The impact of architectural design upon the environmental sound and light exposure of neonates who require intensive care: an evaluation of the boekelheide neonatal intensive care nursery. Journal of Perinatology, 27:20–28, 2007.
J. Schaap. Towards a 3D geo-data model to support pedestrian routing in multimodal public transport travel advices. Master’s thesis, Faculty of Geo-Information Science and Earth Obser- vation (ITC), University of Twente, 2010.
OCCS Development Committee Secretariat. Omniclass construction classification system, 2016. Online http://www.omniclass.org/.
R. Sedgewick. Algorithms in C++, part 5: Graph Algorithms-3/E. 2002.
K.R. Schougaard, K. Grønbæk, and T. Scharling. Indoor pedestrian navigation based on hybrid route planning and location modeling. In International Conference on Pervasive Computing, pages 289–306. Springer, 2012.
B.J. Stankiewicz and A.A. Kalia. Acquisition of structural versus object landmark knowledge.
Journal of Experimental Psychology: Human Perception and Performance, 33(2):378, 2007.
M. Soeda, N. Kushiyama, and R. Ohno. Wayfinding in cases with vertical motion. In MERA97: Proceedings of International Conference on Environment-Behavior Studies for the 21st Century, pages 559–564, 1997.
A. Slingsby. Digital Mapping in Three Dimensional Space: Geometry, Features and Access (un- published). PhD thesis, Centre for Advanced Spatial Analysis, University College London, 2006.
E.P. Stoffel, B. Lorenz, and H.J. Ohlbach. Towards a semantic spatial model for pedestrian indoor navigation. In Proceedings of the 2007 Conference on Advances in Conceptual Modeling: Foundations and Applications, ER’07, pages 328–337, Berlin, Heidelberg, 2007. Springer- Verlag. doi=http://dl.acm.org/citation.cfm?id=1784542.1784596.
LA Solutions. Ec schema data, 2016. Online http://www.la- solutions.co.uk/content/Databases/Databases.htm#ECSchema.
I. Spasso. Algorithms for map-aided autonomous indoor pedestrian positioning and navigation.
PhD thesis, Swiss Federal Institute of Technology in Lausanne, Switzerland, 2007.
A. Slingsby and J. Raper. Navigable space in 3D city models for pedestrians. In Advances in 3D geoinformation systems, pages 49–64. Springer, 2008.
M. Swobodzinski and M. Raubal. An indoor routing algorithm for the blind: development and comparison to a routing algorithm for the sighted. International Journal of Geographical Infor- mation Science, 23(10):1315–1343, 2009.
A. Stepanov and J.M. Smith. Multi-objective evacuation routing in transportation networks.
European Journal of Operational Research, 198(2):435–446, 2009.
E.P. Stoffel, K. Schoder, and H.J. Ohlbach. Applying hierarchical graphs to pedestrian indoor navigation. In Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, GIS ’08, pages 54:1–54:4, New York, NY, USA, 2008. ACM. doi=http://doi.acm.org/10.1145/1463434.1463499.
A. Stentz. Optimal and efficient path planning for partially-known environments. In Robotics and Automation, 1994. Proceedings., 1994 IEEE International Conference on, pages 3310– 3317. IEEE, 1994.
A. Stentz. The focussed D* algorithm for real-time replanning. In International Joint Conference on Artificial Intelligence, volume 95, pages 1652–1659, 1995.
J. Stook. Planning an indoor navigation service for a smartphone with wi-fi fingerprinting local- ization. Master’s thesis, OTB Research Institute for the Built Environment, Delft University of Technology, Netherlands, 2012.
A.W. Siegel and S.H. White. The development of spatial representations of large-scale environ- ments. Advances in child development and behavior, 10:9–55, 1975.
Bentley Systems. Design modeling software, 2016. online https://www.bentley.com/en/products/product-line/modeling-and-visualization- software/microstation.
Bentley Systems. i-model software development kit, 2016. online https://www.bentley.com/en/software-developers/sharing-deliverables/i-model-sdk.
Bentley Systems. i-models: Access and share information-rich models, 2016. online https://www.bentley.com/en/i-models.
J. Schaap, S. Zlatanova, and P. Van Oosterom. Towards a 3D geo-data model to support pedes- trian routing in multimodal public transport travel advices. Urban and Regional Data Manage- ment, UDMS Annual, pages 63–78, 2011.
V. Tsetsos, C. Anagnostopoulos, P. Kikiras, P. Hasiotis, and S. Hadjiefthymiades. A human- centered semantic navigation system for indoor environments. In ICPS’05. Proceedings. Inter- national Conference on Pervasive Services, 2005., pages 146–155. IEEE, 2005.
V. Tsetsos, C. Anagnostopoulos, P. Kikiras, and S. Hadjiefthymiades. Semantically enriched navigation for indoor environments. International Journal of Web and Grid Services, 2(4):453– 478, December 2006. doi=http://dx.doi.org/10.1504/IJWGS.2006.011714.
S. Thrun, W. Burgard, and D. Fox. Probabilistic robotics. MIT Press, 2005.
T.A. Teo and K.H. Cho. BIM-oriented indoor network model for indoor and outdoor combined route planning. Advanced Engineering Informatics, 30(3):268–282, 2016.
P.W. Thorndyke and S.E. Goldin. Spatial learning and reasoning skill. In Spatial orientation, pages 195–217. Springer, 1983.
P.W. Thorndyke and B. Hayes-Roth. Differences in spatial knowledge acquired from maps and navigation. Cognitive psychology, 14(4):560–589, 1982.
J. Torressospedra, R. Montoliu, G.M. Mendozasilva, O. Belmonte, D. Rambla, and J. Huerta. Providing databases for different indoor positioning technologies: Pros and cons of magnetic field and wi-fi based positioning. Mobile Information Systems, 2016:1–22, 2016.
G.T. Toussaint. Solving geometric problems with the rotating calipers. In Proc. IEEE MELECON 83, pages 10—02, 1983.
J. Van Bemmelen, Quak W., M. Van Hekken, and P. Van Oosterom. Vector vs. raster-based algorithms for cross country movement planning. In Proceedings AutoCarto 11, page 304–317, 1993.
M.F.S. van der Ham, S. Zlatanova, E. Verbree, and R. Voûte. Real time localization of assets in hospitals using QUUPPA indoor positioning technology. ISPRS Annals of Photogrammetry, Remote Sensing and Spatial Information Sciences, IV-4/W1:105–110, 2016.
A. Vanclooster, P. De Maeyer, and V. Fack. Implementation of indoor navigation networks using CityGML. In International Workshop on 3D Geo-Information, pages 233–240, 2009.
I. Visser. Route determination in disaster areas. Master’s thesis, MSc thesis, Utrecht University, 2009.
W. Van Toll, A.F. Cook, and R. Geraerts. Navigation meshes for realistic multi-layered environ- ments. In 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 3526–3532. IEEE, 2011.
E. Verbree, S. Zlatanova, K. Van Winden, E.B. Van der Laan, A. Makri, T. Li, and H. Ai. To localise or to be localised with WiFi in the Hubei museum? In Acquisition and Modelling of Indoor and Enclosed Environments 2013, Cape Town, South Africa, 11-13 December 2013, ISPRS Archives Volume XL-4/W4, 2013, pages p.31–35. ISPRS, 2013.
J.O. Wallgrün. Autonomous construction of hierarchical Voronoi-based route graph representa- tions. In International Conference on Spatial Cognition, pages 413–433. Springer, 2004.
H. Whitney. Non-separable and planar graphs. Transactions of the American Mathematical Society, 34:339–362, 1932.
E. Whiting. Geometric, topological and semantic analysis of multi-building floor plan data.
Master’s thesis, 1 2006.
Wikipedia. Industry foundation classes, 2016.
H. Wu, A. Marshall, and W. Yu. Path planning and following algorithms in an indoor navigation model for visually impaired. In Internet Monitoring and Protection, 2007. ICIMP 2007. Second International Conference on, pages 38–38. IEEE, 2007.
M. Worboys. Modeling indoor space. In Proceedings of the 3rd ACM SIGSPATIAL International Workshop on Indoor Spatial Awareness, ISA ’11, pages 1–6, New York, NY, USA, 2011. ACM. doi=http://doi.acm.org/10.1145/2077357.2077358.
H. Wu. Integration of 2D architectural floor plans into indoor openstreetmap for reconstructing 3D building models. Master’s thesis, Delft University of Technology, 2015.
J. Xia, C. Arrowsmith, M. Jackson, and W. Cartwright. The wayfinding process relationships between decision-making and landmark utility. Tourism Management, 29(3):445–457, 2008.
W. Xu. Spatial model-aided indoor tracking. Master’s thesis, Delft University of Technology, 2014.
M. Xu, S. Wei, and S. Zlatanova. An indoor navigation approach considering obstacles and space subdivision of 2D plan. In ISPRS - International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, volume XLI-B4, pages 339–346, 2016.
Q. Xiong, Q. Zhu, S. Zlatanova, Z. Du, Y. Zhang, and L. Zeng. Multi-level indoor path planning method. ISPRS - International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, XL-4/W5:p.19–23, 2015. doi=10.5194/isprsarchives-XL-4-W5-19- 2015.
[YCDN07] J. Ye, L. Coyle, S. Dobson, and P. Nixon. A unified semantics space model. In J. High- tower, B. Schiele, and T. Strang, editors, Location- and Context-Awareness, volume 4718 of Lecture Notes in Computer Science, pages 103–120. Springer Berlin Heidelberg, 2007. doi=http://dx.doi.org/10.1007/978-3-540-75160-1_7.
[YS11] W. Yuan and M. Schneider. 3D indoor route planning for arbitrary-shape objects. In J. Xu, G. Yu,
S. Zhou, and R. Unland, editors, Database Systems for Advanced Applications, volume 6637 of
Lecture Notes in Computer Science, pages 120–131. Springer Berlin Heidelberg, 2011.
L. Yang and M. Worboys. A navigation ontology for outdoor-indoor space: (work-in-progress). In Proceedings of the 3rd ACM SIGSPATIAL International Workshop on Indoor Spatial Awareness, ISA ’11, pages 31–34, New York, NY, USA, 2011. ACM.
S. Zlatanova and S.S.K. Baharin. Optimal navigation of first responders using dbms. In 3rd international conference on information systems for crisis response and management 4th in- ternational symposium on geoInformation for disaster management, pages 541–54. Citeseer, 2008.
J. Zhao. The validation and repair of CityGML models (unpublished), 2013. On- line http://wiki.tudelft.nl/pub/Organisation/OTB/GISt/LunchMeetings/2013-12- 06_The_Validation_and_Repair_of_CityGML_Models.pptx.
S. Zlatanova, L. Liu, and G. Sithole. A conceptual framework of space subdivision for indoor navigation. In ACM Sigspatial International Workshop on Indoor Spatial Awareness, pages 37– 41, 2013.
S. Zlatanova, L. Liu, G. Sithole, J. Zhao, and F. Mortari. Space subdivision for indoor applications, 2014. GISt Report No. 66, Delft University of Technology.
S. Zlatanova and E. Verbree. User tracking as an alternative positioning technique for lbs. In Proceedings of the Symposium on Location Based Services & Telecartography, Vienna, Austria, 28-29 January, 2004, pages p.109–115, 2004.
Y. Zhou, S. Zlatanova, Z. Wang, Y. Zhang, and L. Liu. Moving human path tracking based on video surveillance in 3D indoor scenarios. ISPRS Annals of Photogrammetry, Remote Sensing and Spatial Information Sciences, III-4:p.97–101, 2016.
