Information Technology Reference
In-Depth Information
produce graph-like maps that can be used much more efficiently. They are simpler,
permit efficient planning and do not require accurate determination of the robot's po-
sition. In these maps, vertices correspond to important places or landmarks, which are
connected by edges that represent paths between them. However, its inaccuracy makes
it harder to maintain consistency in large scale environments, which results in diffi-
culties in recognizing similar places that look alike. There are some other constraints
related to navigation using topological maps. Some limitations previously identified [2]
were: handling inaccurate position and orientation information and detecting neighbor
vertices in the topological map by traversing them, as opposed to sensing or recogniz-
ing them. Despite these constraints, the path planning method that was used produced
adequate results.
In addition, map validation and self-localization in topological maps is also an im-
portant issue for correct robot navigation, which has been extensively studied [3]. In the
work, the robot is given an input graph-like map and its current position and orientation
with respect to the map. The robot has no instrument for measuring distances or orien-
tations. By exploring the world systematically and using distinct markers, which can be
detected, dropped and picked up, the robot can recognize places and determine whether
the map is correct. The same authors later proposed [4] a multi-robot topological map-
ping technique. Robots simultaneously explore different regions of the environment and
they meet periodically to merge their individual maps in order to create a shared merged
map of the complete environment.
As seen before, topological maps can be a very important tool for most tasks us-
ing mobile robots. Many works exploit this simple representation to employ correct
robot navigation. In Ferreira
et al.
[5], a robot drives around the environment and self-
localizes, while using a place recognition technique to build 3D point cloud sets for
monitoring changes that might take place in the environment.
In this work, the focus is mainly on obtaining a global topological abstraction from
a preexisting metric representation of an environment. For example, for surveillance,
monitoring and patrolling tasks with multiple robots, it is common to rely on topological
maps for navigation issues. In a previous work [6], we presented a novel multi-robot
patrolling algorithm based on topological maps.
In this article, we describe in detail how complete topological information is ex-
tracted from an existing 2D grid map representation of the area to be patrolled, which
in turn can be obtained with a state-of-the-art robotic mapping technique,
e.g.
[7].
The next section presents a survey of previous techniques for extracting topologi-
cal representations like diagrams and graphs from metric representations given
apri-
ori
. Typically, these metric representations are occupancy grids, which are probabilistic
maps wherein each cell of the grid contains a probability value that indicates whether
the related location is free space or part of an obstacle [8]. These grids are usually
obtained in a preceding exploration phase. In Section 3, we state the problem to be ad-
dressed and Section 4 presents the algorithm proposed to solve it. Later on, results are
presented and the article ends with conclusions and future work.
