Abstract
The main task of mobile robots in large environments such as factories, warehouses, and open spaces is to transport goods and people. Planning the path in large environments using classical graph-based search is computationally too intensive. A representation by a hierarchical graph (H-graph) facilitates graph creation and reduces the complexity of path planning. In this paper, we present an algorithm for autonomously generating hierarchy of the environment from floor plans. The hierarchical abstraction depicts the environment in levels, from the most detailed to the most abstract representation of the environment, where pre-computed partial paths at the most detailed level are graph edges in a higher level. We use the E* algorithm to find partial paths in the most detailed abstraction level, and we propose the extraction of higher levels automatically from lower levels. We verified the proposed H-graph creation on our University premises resulting in five abstract levels.
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
Similar content being viewed by others
References
Galindo, C., Fernandez-Madrigal, J.A., Gonzalez, J.: Improving efficiency in mobile robot task planning through world abstraction. IEEE Trans. Robot. 20(4), 677–690 (2004)
Bonnington, C.P., Little, C.H.C.: The Foundations of Topological Graph Theory. Springer, New York (1995)
Cagigas, D.: Hierarchical D* algorithm with materialization of costs for robot path planning. Robot. Auton. Syst. 52, 190–208 (2005)
Ryu, H.: Hierarchical path-planning for mobile robots using a Skeletonization-informed rapidly exploring random tree*. Appl. Sci. 10(21) (2020)
Chen, J., Liu, C., Wu, J., Furukawa, Y.: Floor-SP: inverse CAD for floorplans by sequential room-wise shortest path. In: 2019 IEEE/CVF International Conference on Computer Vision (ICCV), pp. 2661–2670 (2019)
Sethian, J.: A fast marching level set method for monotonically advancing fronts. Proc. Natl. Acad. Sci. 93, 1591–1595 (1996)
Čikeš, M., Đakulović, M., Petrović, I.: The path planning algorithms for a mobile robot based on the occupancy grid map of the environment—A comparative study. In: 2011 XXIII International Symposium on Information, Communication and Automation Technologies, pp. 1–8 (2011)
Seder, M., Juric-Kavelj, K., Petrović, I.: Automatic creation of hierarchical maps for indoor environments. In: Proceedings of the Fifth International Conference on Computational Intelligence, Robotics and Autonomous Systems, pp. 19–24 (2008)
Seder, M., Mostarac, P., Petrović, I.: Hierarchical path planning of mobile robots in complex indoor environments. Trans. Inst. Meas. Control 33(3–4), 332–358 (2011)
Philippsen, R.: A Light Formulation of the E* Interpolated Path Replanner. Autonomous Systems Lab, Ecole Polytechnique Federale de Lausanne (2006)
Sam Ge, S., Zhang, Q., Thomas Abraham, A., Rebsamen, B.: Simultaneous path planning and topological mapping (SP2ATM) for environment exploration and goal oriented navigation. Robot. Auton. Syst. 59 (2011)
Thrun, S., Burgard, W., Fox, D.: Probabilistic Robotics. MIT Press, Cambridge, Massachusetts (2005)
Huang, Y.W., Jing, N., Rundensteiner, E.: A hierarchical path view model for path finding in intelligent transportation systems. GeoInformatica 1, 125–159 (1997)
Acknowledgements
This work has been supported by the European Regional Development Fund under the grant KK.01.2.1.02.0119 – Research and development of an advanced unit for autonomous control of mobile vehicles in logistics (A-UNIT).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Gregorić, J., Seder, M., Petrović, I. (2023). Autonomous Hierarchy Creation for Path Planning of Mobile Robots in Large Environments. In: Petrovic, I., Menegatti, E., Marković, I. (eds) Intelligent Autonomous Systems 17. IAS 2022. Lecture Notes in Networks and Systems, vol 577. Springer, Cham. https://doi.org/10.1007/978-3-031-22216-0_61
Download citation
DOI: https://doi.org/10.1007/978-3-031-22216-0_61
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-22215-3
Online ISBN: 978-3-031-22216-0
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)