Information Technology Reference
In-Depth Information
2
Related Work
In the literature, there are a few existing techniques to extract topological representa-
tions using metric maps. In particular, Voronoi Diagrams [9] have been extensively used
to plan a path that stays away from obstacles as far as possible. In addition, the Gener-
alized Voronoi Diagram (GVD) [10] was described as a “retraction of the free space of
the working space onto a network of one-dimensional curves reflecting the connectivity
of free space” and a hierarchically organized Voronoi-based route graph representation
for robot navigation in indoor scenarios was proposed.
Furthermore, the Extended Voronoi Graph (EVG) [11] has been presented more re-
cently. In this new approach, the diagram (or skeleton) computation overcomes
limitations in the sensory horizon of robots by clearly defining a transition from corridor-
following to wall-following in large rooms. Although defined as a graph, beyond
the actual diagram no information about vertices or edges is available after the final
computation.
Additionally, Kolling and Carpin [12] proposed a method to extract graph represen-
tations from occupancy grids for surveillance tasks, based on the GVD. Graph modifi-
cations, called contractors, are promoted to simplify the surveillance problem towards
solving it using fewer robots.
Another commonly used technique when extracting graphs is the Delaunay triangu-
lation (DT) [13]. In fact, the DT of a discrete point set generally corresponds to the dual
graph of the Voronoi diagram for the same point set.
Katsilieris
et al.
[14] extract the traversability graph from the original metric map in
the context of searching intruders with a team of robots. Firstly, the obstacle-free area
is triangulated and then triangles are merged to form large convex regions where the
vertices are extracted. The set of edges consists of all pairs of regions that share a side.
In addition, a technique called Reduced Constrained Delaunay Triangulation to build
graphs is also becoming popular. This technique is based on a DT computation together
with a mechanism to reduce the graph by minimizing the distance each robot has to
traverse. It was applied by Fazli
et al.
[15] in the context of a multi-robot area coverage
task in a known and static 2D environment.
Another method presented in the literature to extract the graph of an environment
is the visibility graph [16], which is composed of straight lines joining a sequence of
vertices that are normally placed near the limits of obstacles in the environment (consid-
ering the dimension and pose of the robot). The graph is created connecting all vertices
that can “see” each other, hence the name visibility graph.
Among the most used techniques are also thinning [17] and skeletonization [18]
methods. These are operations used to remove the foreground pixels from binary im-
ages, analogously to peeling an onion. They provide a skeleton of the image, reducing
all lines to a single pixel thickness. The output of such techniques is similar to the GVD.
Szab o [18] also refers in his work some other methods for extracting topological maps
from occupancy grids, namely sparse pixel approaches and matching opposite contours.
Moreover, another technique called C-cells can be found in the literature [19]. It has the
principle to divide the space not occupied by obstacles into convex polygons and the
vertices of the graph are positioned in the center of those polygons, having each vertex
connected in a straight line to the closest visible vertex.
