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, "sensinglimited" robots. These
robots have shortrange 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 sensinglimited 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 sensinglimited robots, addressing issues of
exploration strategy, map representation, and loop closure. In the
area of multirobot mapping, we have developed an algorithm for
merging topological maps without common reference frames.

Simple singlerobot 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, "welldefined" features of the environment that are easily
detectable even by sensinglimited robots. Typically, these
features are significantlysized corners — interior or exterior
— found by the robot as it performs a wall or hallfollowing
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 hallfollowing behavior when mapping. In
open spaces, they use a wallfollowing behavior. Second, we have
developed the idea of "refinements" to a map created using wall and
hallfollowing. 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
sensinglimited robots. In M. Erdmann et al., editors, Algorithmic Foundations of
Robotics VI, pages 235250, Zeist, Springer, 2005.


Kristopher R. Beevers. Topological mapping and map merging with
sensinglimited robots. Master's thesis, Rensselaer Polytechnic
Institute, Troy, NY, April 2004.



Loopclosing 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 evidentialreasoning approach based on the
DempsterShafer theory of evidence. When the map estimate indicates
the robot may have returned to a previouslyvisited place, it
"hypothesizes" that it has closed the loop. It then continues to
traverse the environment, seeking "evidence" — generally by
taking walllength 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 DempsterShafer theory to manage loopclosing
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 43784383, 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 onedimensional 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
L_{2}, 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 0506, 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):601613, August 2005.


Wesley H. Huang and Kristopher R. Beevers. Topological map merging.
In 7th Intl. Symposium on Distributed Autonomous Robotic Systems
(DARS 2004), pages 91100, Toulouse, France, June 2004.


Kristopher R. Beevers. Topological mapping and map merging with
sensinglimited robots. Master's thesis, Rensselaer Polytechnic
Institute, Troy, NY, April 2004.


