Hierarchical Voronoi-based route graph representations for mobile robots [1]

A route graph as proposed in [2] is a spatial representation of large-scale space that focuses on integrating qualitatively different routes that an agent can use for navigation. Goal of this work is to develop a route graph representation for a mobile robot based on the generalized Voronoi diagram (GVD) of the 2D environment as perceived by a robot equipped with range sensors. We propose a hierarchical organization of the graph structure resulting in more abstract layers that represent the environment at coarser levels of granularity well-suited for planning, spatial reasoning and communication.

Generalized Voronoi diagram and generalized Voronoi graph

The generalized Voronoi diagram (GVD) is a retraction of free space onto a network of one-dimensional curves and is related to the idea of a shape's skeleton introduced in [3]. The generelized Voronoi graph (GVG) corresponding to a GVD consists of a vertex for every meet and end point of the GVD and edges reflecting the connectivity of the GVD.

(click to enlarge)

Annotated GVGs as route graphs

To facilitate robust localization within the GVG and efficient exploration, the graph structure of the GVG is annotated with the following additional information:

  • Vertices are labeled with a signature (see left figure below) that contains the distance to the generating points (those points at which the maximal inscribed circle centered on the Voronoi vertex touches the obstacle boundaries) and the angles between the lines connecting the vertex with its generating points.
  • The approximate relative position of vertices is represented by annotating the edges with the approximate distances between the connected vertices and by annotating the vertices with the approximate angles between their leaving edges (see right figure below).
  • Every edge is annotated with a description of the Voronoi curve corresponding to this edge since this curve may deviate from the direct connection between the two vertices.
  • Additional information about which edges are traversable (not too close to obstacles) for the robot and which edges lead to still unexplored areas is also annotated to the graph structure.
  • Incremental construction and localization

    Incremental construction and driving along a planned path both require the ability to localize within the graph representation. For this purpose, a matching scheme has been developed that compares a local GVG computed from a single 360 degree scan taken from the robot's current position with the (partially constructed) global GVG to identify corresponding vertices and edges while taking into account the vertex signatures, the relative position information, and the odometry information about the last movement.

    The figure below illustrates this localization scheme showing on the left a simple environment with the partially constructed global GVG, and in the middle the segmented current scan data together with the local GVG. The dashed arrows indicate vertices that have been identified by the matching algorithm. Based on these associations the position of the robot relative to the vertices of the local GVG can be transferred back to the global GVG and thus localization within the global GVG can be achieved.

    The matching scheme as described above allows the robot to track its position relative to the global GVG while driving along a planned path. Furthermore, it enables the robot to build up the global GVG incrementally by sequentially merging local GVGs computed for different positions starting with the local GVG computed for the start position of the robot.

    Hierarchical GVGs

    Voronoi-based route graphs as described above contain the information required for successful navigation. However, they also contain details not required for many tasks since not all meet points of the underlying GVD really correspond to decision points relevant for navigation. For high-level reasoning, planning, and for communication issues a more abstract level of representation is preferable if it is still linked to the detailed level required for actually acting within the environment.

    Therefore, we developed a hierarchically structured multi-layer route graph representation that bridges from detailed navigational information to abstract high-level route information about the environment and allows to efficiently reason in a hierarchical manner. Every layer of this representation consists of a route graph that models the environment at a certain level of granularity and its features are linked to those of the next higher and next lower layer in a way that allows to switch to a finer or coarser level. This idea is illustrated in the figure below.

    To derive more abstract layers from the original GVG, we need to assess the relevance of individual Voronoi vertices and edges for navigation. This will be described in the next section.

    Assessing the relevance of Voronoi vertices

    How relevant a Voronoi vertex v is for navigation depends directly on the regions accessible via its leaving edges. To be regarded as a decision point, at least three of v's regions need to be significant enough to be judged as different continuations after arriving at this point.

    To measure the significance of a region we have developed a region significance measure RSM that takes into account the distance from v to the remotest goals belonging to the region and the visibility of this region seen from v. Our measure allows to compute the significance of a region from the information stored in the GVG without referring to a geometric description of boundaries of obstacles. Cyclic regions are treated as maximally significant so that cycles in the graph will never be split up when deriving a coarser route graph from the GVG.

    The RSM measure is defined as follows:

    1. RSM(rv)=∞, if v and the leaving edge corresponding to rv belong to a cycle in the route graph.
    2. Otherwise, the shortest paths from v to the corner vertices belonging to rv in terms of the distance along the GVD are considered. It is determined for which corner vertex the length of this path minus the length of the part of this path lying within the maximal inscribed circle of v is maximal, and this is returned as the value RSM(rv).

    Given the RSM values of its regions, the Voronoi vertex relevance measure VVRM simply takes the the RSM value of v's third most significant region. In the left figure below the individual VVRM values of the vertices are depicted by the radii of the corresponding circles. Vertices that have a VVRM value of ∞ because at least three of their leaving edges belong to cycles in the GVG are displayed by the non-filled circles. On the right you can see a coarser Voronoi graph that the simplification algorithm that will be explained in the section generated from these VVRM values.


    The simplification algorithm takes the VVRM values and a threshold value θ and generates a coarser GVG has the following properties:

    1. The coarser graph will be connected (assuming that the original GVG was connected).
    2. All inner vertices v of the GVG with VVRM(v) ≥ θ will remain in the coarser graph.
    3. All cycles in the original GVG will remain in the coarser graph.
    4. For every inner vertex v remaining in the coarser graph, a leaving edge exists for every region rv of v with RSM(rv) ≥ θ.
    5. The coarser route graph will not contain any vertices with degree two.

    The algorithm prunes the graph by removing different cases of degree one vertices until no further pruning is possible. After that, degree two vertices that have been left over by the first step are removed. As long as at least one vertex v with VVRM(v) ≥ θ exists in the given GVG, the result of the simplification is uniquely determined. The coarser GVG in the right figure above has been computed with threshold θ = 1000mm (the size of the complete environment is approximately 9x10 meter.

    The Java applet below allows you to play around with different simplification thresholds for the GVGs of two environments. Use the slider on the bottom right or the text field above to adjust the threshold value and the checkboxes to control which information is displayed.


    [1]J. O. Wallgrün. Autonomous Construction of Hierarchical Voronoi-based Route Graph Representations. In Christian Freksa, Markus Knauff, Bernd Krieg-Brückner, Bernhard Nebel, Thomas Barkowsky (Eds.), Spatial Cognition IV. Reasoning, Action, Interaction: International Conference Spatial Cognition 2004, Vol. 3343, pp. 413-433, Lecture Notes in Artificial Intelligence. Springer, Berlin.
    [2]S. Werner, B. Krieg-Brückner, and T. Herrmann. Modelling Navigational Knowledge by Route Graphs. In Spatial Cognition II, 295-316, Springer, 2000.
    [3] H. Blum. A transformation for extracting new descriptors of shape. In W. Wathen-Dunn, editor, Models for the Perception of Speech and Visual Form, pages 362-380, Cambridge, MA, 1967. M.I.T. Press.