Information Technology Reference
In-Depth Information
Retrieving Topological Information
for Mobile Robots Provided with Grid Maps
David Portugal and Rui P. Rocha
Institute of Systems and Robotics, Department of Electrical and Computer Engineering
University of Coimbra, 3030-290 Coimbra, Portugal
{
davidbsp,rprocha
}
@isr.uc.pt
Abstract.
In the context of mobile robotics, it is crucial for the robot to have a
consistent representation of the surrounding area. However, common grid maps
used in robotics do not provide any evidence as to connectivity, making it harder
to find appropriate paths to particular points on the site. Therefore, abstracting
the environment where mobile robots carry out some mission can be of a great
benefit.
Topological maps have been increasingly used in robotics, because they are
fairly simple and an extremely intuitive representation for tasks that involve path
planning. In this article, a method for retrieving a topological map from an
a
priori
generic grid map of the environment is presented. Beyond extracting a 2D
diagram which portrays the topology of the infra-structure, the focus is placed
on obtaining graph-like data related to the connectivity of important points in the
area, that can be passed on to robots or to a centralized planner, in order to assist
the navigation task. The proposed method is further elaborated in detail and its
results prove the simplicity, accuracy and efficiency of the approach.
Keywords:
Robot navigation, Graphs, Topological maps, Voronoi diagrams.
1
Introduction
In robotics, it is extremely important for autonomous mobile robots to learn and pre-
serve models of the environment. Without an internal description of the environment
and information of their position and orientation with respect to this map, most mo-
bile robotic tasks, like driving while avoiding collisions and navigating, would become
impractical.
In navigation tasks, it is normally assumed that the environment is known
apriori
.
On the other hand, exploration is generally related to completely or partially unknown
environments. For both cases, maintaining or building internal representations of the
infra-structure is one of the key issues to the successful completion of the task.
The two major distinct paradigms for mapping indoor environments are grid-based
maps and topological maps [1]. In the present work, we focus on the latter one.
Grid-based methods produce accurate metric maps, are easy to build, represent and
maintain, but often suffer from memory space and time complexity, because of its fine
resolution restrictions which results in memory problems and also harder efficient plan-
ning and navigating in large-scale infrastructures. Topological maps, on the other hand,
