Abstract
Route planning, which is used to calculate feasible routes in a given environment, is one of the key issues in navigation systems. According to different constraints in different given space, various route planning strategies have been developed in recent years. Current route planning models for indoor space focus on providing routes for pedestrians or fix-sized users, like robots and persons in wheelchairs. None of the existing model can provide feasible routes for arbitrary-shape users, which appears to be more and more useful in many situations, like users driving small indoor autos or moving carts with products. This paper proposes a two-phase route planning model which can support route planning for users with arbitrary shapes. In the first phase, the LEGO model represents the entire space by using different types of cubes. These cubes are further merged in the second phase to form the maximum accessible blocks. By computing the maximum accessible widths and lengths between blocks, a LEGO graph is built to perform route searching algorithms.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Gilliéron, P.Y., Merminod, B.: Personal Navigation System for Indoor Applications. In: 11th IAIN World Congress, pp. 21–24 (2003)
Urs-Jakob, R.: Wayfinding in Scene Space: Transfers in Public Transport. PhD thesis, University of Zürich (2007)
Lyardet, F., Grimmer, J., Muhlhauser, M.: CoINS: Context Sensitive Indoor Navigation System. In: ISM 2006: Eighth IEEE International Symposium on Multimedia, pp. 209–218 (2006)
Lyardet, F., Szeto, D.W., Aitenbichler, E.: Context-Aware Indoor Navigation. In: Aarts, E., Crowley, J.L., de Ruyter, B., Gerhäuser, H., Pflaum, A., Schmidt, J., Wichert, R. (eds.) AmI 2008. LNCS, vol. 5355, pp. 290–307. Springer, Heidelberg (2008)
Hu, H., Lee, D.L.: Semantic Location Modeling for Location Navigation in Mobile Environment. In: Proc. Of the IEEE International Conference on Mobile Data Management (MDM), pp. 52–61 (2004)
Werner, S., Krieg-Brückner, B., Herrmann, T.: Modelling Navigational Knowledge by Route Graphs. In: Habel, C., Brauer, W., Freksa, C., Wender, K.F. (eds.) Spatial Cognition 2000. LNCS (LNAI), vol. 1849, pp. 295–316. Springer, Heidelberg (2000)
Lorenz, B., Ohlbach, H., Stoffel, E.P.: A Hybrid Spatial Model for Representing Indoor Environments. In: Carswell, J.D., Tezuka, T. (eds.) W2GIS 2006. LNCS, vol. 4295, pp. 102–112. Springer, Heidelberg (2006)
Stoffel, E.P., Lorenz, B., Ohlbach, H.: Towards a Semantic Spatial Model for Pedestrian Indoor Navigation. In: Advances in Conceptual Modeling C Foundations and Applications, pp. 328–337 (2007)
Yuan, W., Schneider, M.: inav: An indoor navigation model supporting length-dependent optimal routing. In: 13th AGILE Int. Conf. on Geographic Information Science. Springer, Heidelberg (2010)
Lee, J.: A Spatial Access-Oriented Implementation of a 3-D GIS Topological Data Model for Urban Entities. GeoInformatica 8(3), 237–264 (2004)
Lee, J.: A Combinatorial Data Model for Representing Topological Relations among 3D Geographical Features in Micro-Spatial Environments. International Journal of Geographic Information Science 19(10), 1039–1056 (2005)
Thomas Becker, C.N., Kolbe, T.H.: A Multilayered Space-Event Model for Navigation in Indoor Spaces. In: Advances in 3D Geoinformation Systems, pp. 61–77. Springer, Heidelberg (2009)
Li, Y., He, Z.: 3D Indoor Navigation: a Framework of Combining BIM with 3D GIS. In: 44th ISOCARP Congress (2008)
Meijers, M., Zlatanova, S., Pfeifer, N.: 3D Geo-Information Indoors: Structuring for Evacuation. In: Proceedings of Next generation 3D City Models, pp. 21–22 (2005)
Bandi, S., Thalmann, D.: Space Discretization for Efficient Human Navigation. In: Proc. Computer Graphics Forum, vol. 17, pp. 195–206 (1998)
Thrun, S., Bücken, A.: Integrating Grid-Based and Topological Maps for Mobile Robot Navigation. In: Proceedings of the AAAI Thirteenth National Conference on Artificial Intelligence, Portland, Oregon, pp. 944–950 (1996)
Bandera, A., Urdiales, C., Sandoval, F.: A Hierarchical Approach to Grid-based and Topological Maps Integration for Autonomous Indoor Navgation. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 883–888 (2001)
Han, C.S., Law, K.H., Jean-claude Latombe, J.C., Kunz, J.C.: A Performance-Based Approach to Wheelchair Accessible Route Analysis. Advanced Engineering Informatics 16, 53–71 (2002)
Yuan, W., Schneider, M.: Supporting 3d route planning in indoor space based on the lego representation. In: 2nd ACM SIGSPATIAL Int. Workshop on Indoor Spatial Awareness (ISA), pp. 16–23. Springer, Heidelberg (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Yuan, W., Schneider, M. (2011). 3D Indoor Route Planning for Arbitrary-Shape Objects. In: Xu, J., Yu, G., Zhou, S., Unland, R. (eds) Database Systems for Adanced Applications. DASFAA 2011. Lecture Notes in Computer Science, vol 6637. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-20244-5_12
Download citation
DOI: https://doi.org/10.1007/978-3-642-20244-5_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-20243-8
Online ISBN: 978-3-642-20244-5
eBook Packages: Computer ScienceComputer Science (R0)