Autonomous Construction of Hierarchical Voronoi-Based Route Graph Representations

A route graph as proposed in Werner et al. (2000) is a spatial representation of the environment that focuses on integrating qualitatively different routes an agent can use for navigation. In this paper we describe how a route graph based on the generalized Voronoi diagram (GVD) of the environment can be used for mobile robot mapping and navigation tasks in an office-like indoor environment. We propose a hierarchical organization of the graph structure resulting in more abstract layers that represent the environment at coarser levels of granularity. For this purpose, we define relevance measures to weight the meet points in the GVD based on how significant they are for navigation and present an algorithm that utilizes these weights to generate the coarser route graph layers. Computation of the relevance values from either complete or incomplete information about the environment is considered. Besides robot navigation, the techniques developed can be employed for other tasks in which abstract route graph representations are advantageous, e.g. automatically generating route descriptions from floor plans.