Hierarchical Map Building and Planning based on Graph Partitioning ∗

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 higherlevel 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 clusters. Index Terms — mobile robots, hierarchical map building, topological map, path planning I