Most research on robot mapping and exploration makes use of
powerful computers and expensive sensors, such as scanning laser
rangefinders. We are instead studying the mapping and exploration
problem for small, inexpensive, "sensing-limited" robots. These
robots have short-range sensing that is sparse (low spatial
resolution), so that they have only a highly restricted view of
the world around them. Nevertheless, it is possible to create
maps of unknown environments with sensing-limited robots.
(This is joint work with Wes Huang.)
We have developed several algorithms for topological mapping in
indoor environments. Topological maps represent the connectivity of
the environment, usually in a graph structure where vertices are
"distinctive places" in the environment and edges represent paths,
classes of paths or behavior sequences for traveling between places.
Our research has mainly investigated single robot topological
mapping with sensing-limited robots, addressing issues of
exploration strategy, map representation, and loop closure. In the
area of multi-robot mapping, we have developed an algorithm for
merging topological maps without common reference frames.
|
Simple single-robot topological mapping
Though not always, many topological maps are augmented with some
metric information, such as the lengths of paths (based on the
robot's odometry). Our robots keep path length estimates and use an
odometry error model to maintain confidence bounds on the
estimates.
Our robots create topological maps in which vertices represent
specific, "well-defined" features of the environment that are easily
detectable even by sensing-limited robots. Typically, these
features are significantly-sized corners — interior or exterior
— found by the robot as it performs a wall- or hall-following
behavior.
Topological maps generally have difficulty representing "open
spaces," i.e., large expanses with few features. In our research,
we have addressed this problem in two ways. First, we have
introduced the idea of "portals": places where a transition between
an open space and an enclosed space occurs. In enclosed spaces
(generally corridors in which the robot can see both sides of the
hallway), our robots use a hall-following behavior when mapping. In
open spaces, they use a wall-following behavior. Second, we have
developed the idea of "refinements" to a map created using wall- and
hall-following. In open spaces, robots make "forays" through empty
areas, adding connections between places in the original map when
possible. This can significantly improve navigation efficiency in
open areas.
Publications
Wesley H. Huang and Kristopher R. Beevers. Topological mapping with
sensing-limited robots. In M. Erdmann et al., editors, Algorithmic Foundations of
Robotics VI, pages 235-250, Zeist, Springer, 2005.
|
|
Kristopher R. Beevers. Topological mapping and map merging with
sensing-limited robots. Master's thesis, Rensselaer Polytechnic
Institute, Troy, NY, April 2004.
|
|
|
Loop-closing in topological maps
A difficult problem in mapping is "closing the loop": recognizing
when the robot has returned to a place it has already been. We
address this with an evidential-reasoning approach based on the
Dempster-Shafer theory of evidence. When the map estimate indicates
the robot may have returned to a previously-visited place, it
"hypothesizes" that it has closed the loop. It then continues to
traverse the environment, seeking "evidence" — generally by
taking wall-length measurements — that supports or refutes its
hypothesis. Eventually, the robot builds enough evidence to accept
or reject a particular hypothesis, making its map consistent. Our
approach relies on Dempster-Shafer theory to manage loop-closing
hypotheses, unlike most approaches which are either probabilistic or
heuristic in nature.
Publications
Kristopher R. Beevers and Wesley H. Huang. Loop closing in topological
maps. 2005 IEEE International Conference on
Robotics and Automation (ICRA 2005), pages 4378-4383, Barcelona,
Spain, April 2005.
|
|
|
Topological mapping with the SGVD∞
We have also investigated a topological map representation based on
a version of the Generalized Voronoi Diagram (GVD) of the
environment. Others have employed the basic GVD as a topological
map, with meet points in the GVD as nodes in the map, and edges in
the GVD as edges in the map. With an omnidirectional range sensor
behaviors can be developed to trace the GVD and build a map. We
have again focused instead on the case of more limited sensing
— in our model, robots have eight one-dimensional range
sensors (e.g., infrared sensors) placed at 45 degree angles around
the perimeter of the robot. We have developed behaviors that
guarantee complete traversal of the GVD
∞ of a
rectilinear environment with such robots. (The GVD
∞
is similar to the normal GVD, but is defined under the
L∞ distance metric instead of the more
familiar
L2, or Euclidean, metric.)
If the sensors have limited range as well, one can employ the
"Saturated" GVD∞, or SGVD∞, which
essentially cuts off the GVD∞ at a "saturation
distance" corresponding to the maximum range of the sensors. We
have developed behaviors for tracing the SGVD∞ as
well, and have proved the completeness of the behaviors in the sense
that they are guaranteed to explore the entire
SGVD∞ of the environment.
Publications
Wesley H. Huang and Kristopher R. Beevers. Complete topological
mapping with sparse sensing. Technical Report 05-06, Rensselaer
Polytechnic Institute, Troy, NY, March 2005.
|
|
Topological map merging
When multiple robots explore the environment in parallel, it is
useful to merge their maps to obtain a global map. This is a
difficult problem when the maps lack a common frame of reference.
The approach we have taken to merge topological maps uses aspects
of subgraph matching methods to find "structural" matches between
map graphs. During this phase of the algorithm, vertices and edges
in each map are matched according to their characteristics —
both absolute characteristics, such as vertex degree, and
approximate characteristics, such as measured path lengths.
Structural matching typically reduces the potential matches between
the maps to a manageable number.
After finding structurally consistent matches between the two maps,
we use techniques from image registration methods to find the best
transform for each match. The matches are then clustered in
transformation space into consistent groups. The best cluster
— typically the one with the most vertices and least error
— is returned as the hypothesized match between the maps.
We have also introduced data structures for map storage and map
update procedures that lend themselves well to this merging
strategy.
Our map merging approach has proven very accurate in experiments,
and tends to merge maps quickly, usually in well under a second on a
Pentium processor — even for maps with hundreds of
vertices.
Publications
Wesley H. Huang and Kristopher R. Beevers. Topological map merging.
International Journal of Robotics Research, 24(8):601-613, August 2005.
|
|
Wesley H. Huang and Kristopher R. Beevers. Topological map merging.
In 7th Intl. Symposium on Distributed Autonomous Robotic Systems
(DARS 2004), pages 91-100, Toulouse, France, June 2004.
|
|
Kristopher R. Beevers. Topological mapping and map merging with
sensing-limited robots. Master's thesis, Rensselaer Polytechnic
Institute, Troy, NY, April 2004.
|
|
|