Hierarchical map building and planning based on graph partitioning
- 10 July 2006
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10504729,p. 803-809
- https://doi.org/10.1109/robot.2006.1641808
Abstract
Mobile robot localization and navigation requires a map - the robot's internal representation of the environment. A common problem is that path planning becomes very inefficient for large maps. In this paper we address the problem of segmenting a base-level map in order to construct a higher-level representation of the space which can be used for more efficient planning. We represent the base-level map as a graph for both geometric and appearance based space representations. Then we use a graph partitioning method to cluster nodes of the base-level map and in this way construct a high-level map, which is also a graph. We apply a hierarchical path planning method for stochastic tasks based on Markov decision processes (MDPs) and investigate the effect of choosing different numbers of clustersKeywords
This publication has 16 references indexed in Scilit:
- Environmental modeling with fingerprint sequences for topological global localizationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Distinctive Image Features from Scale-Invariant KeypointsInternational Journal of Computer Vision, 2004
- Semi-Supervised Learning on Riemannian ManifoldsMachine Learning, 2004
- Navigation for human-robot interaction tasksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- Topological simultaneous localization and mapping (SLAM): toward exact localization without explicit localizationIEEE Transactions on Robotics and Automation, 2001
- A probabilistic model for appearance-based robot localizationImage and Vision Computing, 2001
- Normalized cuts and image segmentationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2000
- Learning metric-topological maps for indoor mobile robot navigationPublished by Elsevier ,1998
- Subspace methods for robot visionIEEE Transactions on Robotics and Automation, 1996
- The Mobile Robot RhinoPublished by Springer Nature ,1995