TL;DR
This paper introduces a novel data model and workflow for integrating indoor and outdoor pedestrian route planning using OpenStreetMap (OSM) data. By extending OSM's tagging system and developing new modeling approaches for building components and their connections, the authors enable seamless navigation from street level into and within buildings, addressing a significant gap in current navigation services.
What Problem Does This Paper Address?
Navigating complex environments, especially urban areas, often requires seamless transitions between outdoor streets and indoor building spaces. While outdoor navigation is well-established, integrating indoor navigation into a unified system remains a challenge. Existing route planners offer limited indoor/outdoor functionality, and while some research has explored indoor mapping and routing, a comprehensive solution leveraging widely available VGI like OpenStreetMap is needed. This paper tackles the problem of creating a unified data model and routing algorithm that can effectively represent and navigate complex indoor building structures in conjunction with outdoor road networks, specifically for pedestrian use.
Methods
The core of this work lies in a new data model designed to extend OpenStreetMap's capabilities for indoor environments. Key methodological contributions include:
- OSM-based Data Model: The model leverages OSM's primitives (nodes, ways, relations) and tags to capture indoor components. It focuses on representing horizontal elements (corridors, rooms), vertical connections (stairs, elevators), and the crucial links between indoor and outdoor spaces.
- Indoor Component Modeling: New approaches are proposed for modeling:
- Floors and Building Parts: Using OSM relations for buildings and levels, with specific tags like
indoor:levelto denote floor assignment for rooms, doors, and windows. - Horizontal Connections: Mapping indoor areas (like corridors) as OSM ways with
indoor=areatags, and for walkable paths, usinghighway=footwaytags. For complex geometries, afree_space=yestag is introduced. - Vertical Connections: Modeling stairs and escalators using OSM nodes and relations, capturing step height and sequence. Elevators are modeled as relations with shaft boundaries and connecting nodes.
- Indoor-Outdoor Connections: Entrances and exits are modeled as OSM nodes with
entrance=yes/exittags, linked to both indoor networks and outdoor road networks via OSM ways or closed ways. - Routing Graph Generation Workflow: A five-step workflow is presented to automatically construct a 3D routing graph from the OSM data. This involves processing outdoor networks, building information (including floor heights), horizontal and vertical connections, and finally merging indoor graphs with outdoor networks.
- Modified Dijkstra Algorithm: A modified Dijkstra algorithm is developed for calculating integrated indoor-outdoor routes. It incorporates user preferences (e.g., using elevators vs. stairs), estimates travel times based on building component types, and uses building entrance information to prune irrelevant search spaces, improving efficiency.
Datasets
The authors used real-world building data from two buildings on the campus of Heidelberg University: the Mathematikon building and the Geography building. This data was gathered from evacuation plans and digitized using the Java OpenStreetMap Editor (JOSM). No new benchmark datasets were introduced; instead, existing building plans were converted into the proposed OSM data model.
Key Insights and Ideas
- Leveraging VGI for Indoor Navigation: The paper demonstrates that OpenStreetMap, a widely adopted VGI platform, can be effectively extended to capture the detailed information required for indoor navigation, bridging a significant gap in current VGI applications.
- The Importance of Connections: A key insight is the critical role of accurately modeling the connections between indoor components (rooms, floors, entrances) and between indoor and outdoor environments. This connectivity is paramount for generating coherent and usable routes.
- Semantic Tagging for 3D Representation: The proposed use of OSM tags like
indoor:level,step:height, andfree_space=yesprovides a semantic layer that allows for the reconstruction of 3D spatial relationships and navigation logic from 2D data. - Efficiency through Pruning: The modification of Dijkstra's algorithm to utilize building entrance information for pruning irrelevant search spaces is a clever way to manage the computational complexity of large, integrated indoor-outdoor graphs.
Key Results
The system was tested on the Geography building for intra-building navigation and on both buildings for integrated indoor-outdoor scenarios.
- Indoor Navigation Accuracy: For intra-building navigation within the Geography building, the system achieved a Mean Absolute Percentage Error (MAPE) of 3.22%, which is below the standard threshold of 5%, demonstrating the feasibility of the approach for indoor modeling and routing.
- Integrated Route Planning: For outdoor-to-indoor navigation, the modified Dijkstra algorithm found routes comparable to the classic Dijkstra algorithm but provided more accurate travel time estimations by considering factors like stair climbing. The algorithm also showed improved efficiency by skipping irrelevant buildings.
- Preference-Based Routing: In navigation between buildings, the system demonstrated the ability to generate different routes based on user preferences, such as choosing elevators over stairs, leading to variations in travel time.
Limitations and Future Work
The authors acknowledge several limitations and suggest future research directions:
- Route Instruction Engine: The current system lacks a route instruction engine to provide voice or text guidance. Developing this would require advancements in indoor and outdoor positioning technology.
- Limited Building Information: The data model currently focuses on essential routing information and does not capture all architectural details (e.g., roof type, wall thickness).
- Underground Navigation: While the model can support underground routing, 3D map visualization technology for such environments is still an open issue.
- Data Quality and Evaluation: Indoor data is currently collected manually, which can introduce errors. New methods for evaluating indoor data quality are needed.
- Accessibility for Disabled Users: Future work includes adapting the data model and routing algorithms to support users with disabilities, considering accessibility constraints like stairs and doorway widths.
- BIM Integration: Exploring conversion between Building Information Modeling (BIM) formats (like CityGML, IFC) and the proposed OSM data model is a promising avenue for data enrichment.
- Dynamic Environments: Integrating indoor and outdoor route planning for first responders needs to account for dynamic environments with moving obstacles (e.g., fires).
- Multi-Modal Routing: Extending the system to include other travel modes (car, bus) and developing algorithms for optimal transfer points between modes is also planned.
Summary updated