http://ijr.sagepub.com/
Robotics Research
The International Journal of
http://ijr.sagepub.com/content/29/9/1131
The online version of this article can be found at:
DOI: 10.1177/0278364909340592
2010 29: 1131 originally published online 21 July 2009The International Journal of Robotics Research
Michael Milford and Gordon Wyeth
Persistent Navigation and Mapping using a Biologically Inspired SLAM System
Published by:
http://www.sagepublications.com
On behalf of:
Multimedia Archives
can be found at:The International Journal of Robotics ResearchAdditional services and information for
http://ijr.sagepub.com/cgi/alertsEmail Alerts:
http://ijr.sagepub.com/subscriptionsSubscriptions:
http://www.sagepub.com/journalsReprints.navReprints:
http://www.sagepub.com/journalsPermissions.navPermissions:
http://ijr.sagepub.com/content/29/9/1131.refs.htmlCitations:
What is This?
- Jul 21, 2009Proof
- Aug 5, 2010Version of Record >>
at UNIV OF GUELPH on December 28, 2011ijr.sagepub.comDownloaded from
Michael Milford
Queensland Brain Institute
and
School of Information Tech nology
and Electrical Engineering,
The University of Queensland,
Brisbane, Queensland 4072,
Australia
milford@itee.uq.edu.au
Gordon Wyeth
School of Information Technology
and Electrical Engineering,
The University of Queensland,
Brisbane, Queensland 4072,
Australia
wyeth@itee.uq.edu.au
Persistent Navigation
and M apping using a
Biologically Inspired
SLAM System
Abstract
The challeng e of persistent navigation and mapping is to de velop an
autonomous robot system that can simultaneously localize, map and
navigate over the lifetime of the robot with little or no human inter-
vention. Most solutions to th e simultaneous localization and mapping
(SLAM) pr oblem aim to produce highly accurate maps of areas that
are assumed to be static. In contrast, solutions for persistent navi-
gation and mapping must produce reliable goal-directed navigation
outcomes in an environment that is assumed to be in constant flux.
We investigate the persistent navigation and mapping problem in
the context of an autonomous robot that p erforms mock deliveries
in a working office environment o ver a two-week period. The so-
lution was based on the biologically inspired visual SLAM system,
RatSLAM. RatSLAM performed SLAM continuously while interacting
with global and local navigation systems, and a task selection module
that selected between exploration, delivery, and r echarging modes.
The robot performed 1,143 delivery tasks to 11 different locations
with only one delivery failure (from which it recovered), traveled a
total distance of more than 40 km over 37 hours of active operation,
and rechar ged autonomously a total of 23 times.
The International Journal of Robotics Research
Vol. 29, No. 9, August 2010, pp. 1131–1153
DOI: 10.1177/0278364909340592
c
1
The Author(s), 2010. Reprints and permissions:
http://www.sagepub.co.uk/journalsPermissions.nav
Figures 1–3, 6–12, 15–19, A.1 appear in color online: http://ijr.sagepub.com
KEY WORDS—persistent navigation and mapping, SLAM,
RatSLAM, biologically inspired
1. Introduction
The simultaneous localization and mapping (SLAM) problem
is often identified as one of the key challenges in mobile ro-
botics that must be solved before robots can become part of
everyday life in domestic homes and the workplace. Over the
past two decades, a significant proportion of the research in the
robotics community has been dedicated to solving this prob-
lem. Typically, research in the SLAM field has been performed
based on datasets gathered from robots or vehicles that have
been manually driv en through an environment, with many re-
searchers making use of commonly available datasets (Stach-
niss et al., 20071 Howard and Roy, 2008). SLAM algorithms
developed in this manner are generally assessed by the qual-
ity of the map they produce, and by the size and complexity
of the environment that they are capable of mapping. There
are currently several SLAM algorithms that enable a robot
to form accurate maps of environments ranging from office
buildings (Grisetti et al., 2007) to mine shafts (Thrun et al.,
2003). The advent of competent SLAM algorithms has en-
abled investigations of autonomous robot operation based on
the localization resource provided by the algorithm. For exam-
ple, the MobileRobots MAPPER software package
1
can cre-
1. Available at http://www.activrobots.com/SOFTWARE/index.html
1131
at UNIV OF GUELPH on December 28, 2011ijr.sagepub.comDownloaded from
1132 THE INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH / August 2010
ate a map by wandering an environment during a user-defined
mapping phase. Subsequently, the acquired map can be used
for autonomous goal-based navigation. This is typical of the
use of maps built using SLAM algorithms: there is an initial
mapping phase after which the map is fixed, followed by au-
tonomous operation that assumes that the world will remain
unchanged.
The challenge of persistent navigation and mapping is to
break the assumption that the world remains static by continu-
ously and autonomously performing SLAM throughout the ro-
bot’s lifetime. The difficulty of this challenge lies in the range
of timescales over which change can occur, as well as the vari-
ation in what can change in an environment. The static world
assumption means that most current SLAM algorithms will
fail in the long term from accumulation of errors as the world
changes about the robot. Some research has extended exist-
ing SLAM algorithms to handle certain classes of dynamic
objects such as people (Wang et al., 2003), or to detect and
incorporate changes in a map (Biber and Duckett, 20051 Wolf
and Sukhatme, 2005). Despite these advances, the goal of pro-
ducing an autonomous robot that can concurrently maintain
and use a map over its lifetime is yet to be achieved.
Biological systems, on the other hand, demonstrate the abil-
ity to build and maintain spatial representations that are used
as the basis of goal directed navigation throughout the lifetime
of the organism. A rat, for example, forages over a wide ter-
ritory that is constantly changing due to the activity of other
animals, the weather and the season. Despite the constant state
of flux of sensory cues and available paths, the rat can reliably
return to known sources of food and return home to its own
nest. Based on this insight, we have investigated a biologically
inspired approach to the persistent navigation and mapping
problem.
This paper demonstrates the performance of the RatSLAM
algorithm as the core of a persistent navigation and mapping
system. RatSLAM is a biologically inspired localization and
mapping algorithm based on computational models of parts
of the rodent brain. The parts of the brain believed to under-
pin navigation in the rodent are centered on the hippocampus,
which has been shown to form spatial representations based
on the integration of self-motion signals with calibration from
external sensory cues (O’Keefe and Conway, 19781 Ranck,
19841 Hafting et al., 2005). RatSLAM has been demonstrated
in pre v ious work to be able to perform real-time visual SLAM
in areas as large as an entire subu rb (Milford and Wyeth,
2008a).
The challenge set for this paper was to develop an au-
tonomous mobile robot system which could perform mock de-
livery tasks over a two-week period in a real-world, non-static
environment with a minimum of human intervention. The en-
vironment was a busy, functioning floor of an office building
with cubicles, laboratories, corridors, offices and a kitchen.
There were no modifications to the environment to aid map-
ping or localization, such as placing of navigation beacons, and
no instructions giv en to the occupants of the building. Apart
from providing the robot with locations for deliveries, there
was no human intervention in robot operation or map building
and maintenance. As a further challenge, the robot was trans-
ferred without notice to a different office building with an array
of corridors. New delivery locations were specified in the new
building, and the robot was asked to perform delivery tasks.
After a period of time the robot was returned to the original
environment.
1.1. Contributions of This Paper
Our key contribution is to demonstrate a system for “out of
the box”, long-term mobile robot autonomy with vision-based
lifelong SLAM. We achieve this by using the biologically in-
spired RatSLAM system (Milford and Wyeth, 2008a), and
achieve long-term stability through a simple but effective map
maintenance procedure. Unlike past autonomous mobile ro-
bots, SLAM is run continuously in parallel to whatever task
the robot is performing, whether it is exploring, delivering, or
recharging. There are no stages of learning and the robot’s map
of the world is never considered “complete” and made static,
removing the need for human input. As SLAM is always run-
ning, the robot is also able to learn changes in the appearance
of the environment, enabling operation over day–night cycles
and in the long term. Map maintenance ensures that an appro-
priate amount of information is retained at any one location
in the map1 enough to enable localization but with an upper
bound to limit map size. Consequently, computational demand
is dependent only on the size of the environment(s) and is sta-
ble over time. RatSLAM also provides the robot with a spatial
awareness of its entire environment, providing instantaneous
and continual information about where the robot is currently
located as well as sufficient information to plan and execute
effective paths to any part of the environment.
The paper draws on earlier work published in conference
papers (Milford et al. 2004, 2005, 2006), and which has
been used in offline dataset SLAM experiments (Milford and
Wyeth, 2008a, b). We present for the first time a ne w system
for inte grating continuous SLAM with autonomous behaviors,
a system of map maintenance, and new results demonstrating
the use of the entire system in live delivery experiments over a
two-week period across two different office buildings.
2. Autonomous Robot Navigation and Mapping
Systems
In this section we review the current state of the art in research
that contributes to solutions for persistent navigation and map-
ping, including an ov erview of neurorobotic navigation sys-
tems based on rodents, such as the RatSLAM system.
at UNIV OF GUELPH on December 28, 2011ijr.sagepub.comDownloaded from
Milford and Wyeth / Persistent Navig ation and Mapping using a Biologically Inspired SLAM System 1133
2.1. Autonomous SLAM: Map Building and Maintenance
The SLAM problem captures the dual challenges faced by a
navigating robot when placed in an unknown environment. In
order to navigate effectively, the robot must build up a rep-
resentation or map of the environment. Howev er, new infor-
mation from sensor observations of the environment can only
be integrated into the map if the robot knows the location in
the map from which the observ ations were made, so the robot
must also localize within this evolving map. The current state
of the art solutions to the SLAM problem work well in environ-
ments that are “static, structured and of limited size” (Thrun
and Leonard, 2008). The challenge of lifelong SLAM in un-
structured and dynamic environments is however very much
an open problem.
Three major SLAM paradigms exist. Extended Kalman
filter (EKF) SLAM uses a single state vector to represent both
the estimated robot and landmark locations in the environment,
along with an estimate of the error in these estimates, main-
tained in a covariance matrix (Cheeseman and Smith, 19861
Smith et al., 1990). Self-motion estimates and observ ations
of landmarks update the state vector and covariance matrix.
For EKF SLAM to work the data association problem must
be solved1 the system must be able to recognize whether an
observed landmark matches one of the landmarks in the map.
Graphical SLAM techniques represent the robot and landmark
locations as nodes in a graph (Lu and Milios, 19971 Duck-
ett et al., 20021 Folkesson and Christensen, 20041 Thrun and
Montemerlo, 2006). Nodes experienced in sequence are con-
nected by links that encode the movement of the robot given
by odometry. Graph relaxation can ensure the best overall map
(Duckett et al., 2002). The third paradigm uses particle filters,
where particles sample the posterior distribution. One of the
most successful implementations using particle filters is Fast-
SLAM (Montemerlo et al., 2002, 2003). Implementations of
all three SLAM paradigms have been used to successfully cre-
ate various maps of large real-world indoor and outdoor envi-
ronments.
The maps created from any of these paradigms are gen-
erally used as static resources. The robot performs SLAM
during a designated mapping phase, and the map is subse-
quently used for autonomous operation. A well-known ex-
ample of this approach was the Minerva museum tour guide
robot (Thrun, 2000), which operated using a pre-acquired
static occupancy grid map and ceiling mosaic map. Dy-
namic features of the environment were ignored or filtered
and only features known to be static were used for local-
ization. If the static features were to be changed (for exam-
ple, when the displays were re-arranged), the robot would
need to be told to re-map the environment. In a museum ap-
plication this is perhaps acceptable, but for the wide range
of applications where change is more accumulative and less
structured, the required level of human intervention is not
acceptable.
The problem of lifelong mapping in a dynamic environment
is very challenging, and compared with the static SLAM prob-
lem only a small amount of work has been done. Such work
that has been done has focused on specific aspects of the prob-
lem. For example, work by Wolf and Sukhatme (2005) showed
that, with some help from artificial beacons with known posi-
tions, a robot was able to learn separate occupancy grid maps
of the environment, one each for static and dynamic sections
of the environment. Work by Wang et al. (2003) addressed
detection and tracking of moving objects (DATMO) in con-
junction with SLAM and demonstrated success ov er more
than 100 miles of vehicle travel through urban areas. Biber
and Duckett (2009) represented the environment over multiple
timescales using parallel occupancy maps, where laser -scan
memories faded at different rates depending on timescale. Re-
peated manually controlled robot trav erses through an environ-
ment demonstrated that such an approach could enable robust
map updating in the f ace of changes ranging in timescale from
seconds (moving people) to days (permanent installation of
new radiators). A vision-based version was also successfully
demonstrated (Dayoub and Duckett, 2008).
2.2. Rat-based Neurorobotic Navigation and Mapping
Systems
Animals, particularly mammals, have innate spatial under-
standing that enables reliable navigation to known food and
water sources, territorial boundaries and guides the return to
the den or nest. In this section we focus briefly on robot map-
ping or navigation systems based on the neural mechanisms
thought to underlie these processes.
The rodent family has been extensively studied with re-
gard to the neural underpinnings of navigation and mapping.
A part of the rat brain known as the hippocampus contains
spatially responsive cells which usually form the basis for rat-
based neurorobotic systems. Place cells are cells that fire only
when the rat is located at a certain place in the en vironment
(O’Keefe and Conway, 1978), while head-direction cells fire
only when the rat is facing in certain direction (Ranck, 1984).
Taken together, the firing of these cells encodes the complete
(x, y, 1 ) state of the rat within a two-dimensional plane over
the environment. More recently, a new type of cell known as a
grid-cell was discovered, which encodes multiple rat locations
arranged in a tessellating hexagonal grid over the environment
(Hafting et al., 2005).
Arleo and Gerstner (2000) developed a computational
model of place and head-direction cells which was demon-
strated using a Khepera robot in a small (0.5 2 0.5 m
2
)arena
with bar-coded walls. The model was coupled strongly to the
biology of place cells, and showed how place cell firing can
enable mapping and goal navigation within the arena (Burgess
et al., 1997). The Psikharpax project is building an artificial
robotic rat driven by mapping and navigation algorithms mim-
icking place cells (Meyer et al., 2005). More recent approaches
at UNIV OF GUELPH on December 28, 2011ijr.sagepub.comDownloaded from
1134 THE INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH / August 2010
Fig. 1. Structure and connectivity of the persistent navigation and mapping system. The three main system components are the
core RatSLAM system, the na vigation system, and robot task selection. Italic text denotes sensory inputs.
have also used grid cells (Giovannangeli and Gaussier, 2008)
to enable navigation and mapping on a robot in a larger room-
sized arena. Barrera and Weitzenfeld (2008) have developed a
biologically inspired robot architecture with spatial cognition
and navigation capabilities. Their system is able to learn and
unlearn designated goal locations and navigate to them from
any point within their map. The system was demonstrated in
an eight-arm radial maze and a single and double T-Maze, with
artificial visual cues on the walls of the maze.
In our previous work, we have shown that a neurorobotic
system based on models of hippocampus can map large un-
modified areas based on natural visual cues. The RatSLAM
system has been demonstrated mapping office environments
(Milford et al., 2006), a university campus (Prasser et al.,
2005) and an entire suburb (Milford and Wyeth, 2008a). Rat-
SLAM produces topological maps that have some local met-
ric properties, and shares similarities with established systems
such as the spatial semantic hierarchy (Kuipers and Byun,
1991). As a primarily appearance-based SLAM system, it is
one of a number of recent appearance-based systems (An-
dreasson et al., 20081 Angeli et al., 20081 Cummins and Ne w-
man, 20081 Mahon et al., 2008) that have been catching up to
large-scale metric mapping systems. RatSLAM is the basis of
the algorithm at the core of persistent navigation and mapping
system described in this paper, and is described in detail in
Section 4.
2.3. Summary
Clearly, state-of-the-art SLAM algorithms are capable of pro-
ducing accurate maps of large indoor or outdoor environments.
One of the main challenges now appears to be how best to in-
corporate SLAM algorithms into autonomous robot systems in
a manner that provides significant improvements in robot ca-
pabilities and autonomy. The key to opening a new range of
applications for mobile robots is to provide long-term goal-
directed navigation ability without user supervision or inter-
vention. The most significant challenge is to provide a method
for keeping spatial representations up to date in environments
that change across a range of time scales. The challenge set
in this paper was to develop a system where SLAM occurred
continually and over the entire operating life of the robot, in
order to enable effective navigation performance over the long
term.
3. System Architecture
In this section we provide a high-level o verview of the system
architecture. The autonomous navigation and mapping system
can be divided by functionality into three subsystems, SLAM,
navigation, and task selection, as shown in Figure 1.
The RatSLAM system takes visual and self-motion sensor
data and creates a semi-metric spatial representation known
as an experience map, which is used to plan global routes in
the navigation system and to facilitate exploration. RatSLAM
continuously maintains its spatial representations without in-
tervention from humans or other processes, while providing a
localization and planning resource. There are no specific learn-
ing or recall phases.
The robot has two separate representations of space avail-
able to it1 the global semi-metric experience map from Rat-
SLAM and a local obstacle map built from sensor readings.
The experience map is set in a fixed world reference frame,
and describes the layout and connectivity of all of the navi-
gable regions that have been explored by the robot. The local
obstacle map is set in a robot-centered reference frame, and
describes the local navigable regions based on a short history
of range sensor readings. Long-term goals, such as navigating
to a delivery location, are based on the experience map, while
short-term behaviors use the local obstacle map.
at UNIV OF GUELPH on December 28, 2011ijr.sagepub.comDownloaded from
- 1
- 2
前往页