Information Technology Reference
In-Depth Information
Most previous works mentioned above present methods to visually extract the topo-
logical representation. However, many of these do not correctly characterize vertices
and edges on the graph (like Voronoi Diagrams, EVG, thinning or skeletonization). As
for those that do, the methods which are based on Delaunay Triangulation need a man-
ual definition of the vertices in the environment to compute the topology and usually
generate non-elegant and unbalanced representations. In the case of visibility graphs,
highly inadequate topologies are produced since the vertices are positioned very close
to obstacles, which is unnatural for robot navigation. The Generalized Voronoi Graph
(GVG), which consists of a vertex for every meet and end point of the GVD and edges
reflecting the connectivity of the GVD, results in very complex graphs with a large
number of vertices and edges that are mostly redundant, especially when considering
navigation tasks for robots. In addition, all of these methods assume that the edges con-
necting pairs of neighboring vertices must be a straight line, which is not necessarily
true for robots with the ability to locally plan paths between two vertices.
In this work, we intend to go further ahead, by firstly extracting an elegant topo-
logical representation and then focusing on identifying vertices, edges and their length
(
i.e.
, their weight) and obtaining relevant data concerning the vertices and the connec-
tivity between areas of the map so as to assist robots navigation in tasks like patrolling,
coverage, monitoring, surveillance, pursuit-evasion and others.
3
Problem Statement
In this work, the environment is assumed to be known
apriori
and a metric represen-
tation, typically with the form of an occupancy grid, is available. The goal is to ab-
stract the environment through a topological representation,
i.e.
, a graph, and obtain all
information about the graph's connectivity.
The techniques described in the previous section will lead to different graph rep-
resentations, like placing vertices close to obstacles, inserting them halfway between
obstacles or positioning them in a uniform way along the terrain. Having this in mind,
a careful choice should be made, considering the applications in which the extraction is
applied.
We start with a skeleton representation and then focus on extracting topological in-
formation to characterize the connectivity of the environment. There are several tech-
niques to compute the initial skeleton as seen previously in section 2. In this work, it is
obtained via the EVG computation, mainly because of its results in terms of producing
visually attractive path representations that stay away from obstacles and that consider
the sensing range of the robots as an input of the method. Additionally, it is a relatively
recent technique, which is open source and is easily adaptable to the code that was de-
veloped. Having the representation of the skeleton, the graph is obtained through image
processing techniques by correct identification of vertices and edges. The topological
map is modeled as an undirected graph. Vertices represent places and edges represent
the connectivity (in both directions) between those places.
In the next section, we present the algorithm to extract the complete topological
information and its simplicity and efficiency becomes clear.
