Autonomous Robots 12, 287–300, 2002

c 2002 Kluwer Academic Publishers. Manufactured in The Netherlands.

Fast, On-Line Learning of Globally Consistent Maps

TOM DUCKETT
Department of Technology, University of Örebro S-70182 Örebro, Sweden
[email protected]

STEPHEN MARSLAND AND JONATHAN SHAPIRO

Department of Computer Science, University of Manchester, Oxford Road, Manchester M13 9PL, UK
[email protected]
[email protected]

Abstract. To navigate in unknown environments, mobile robots require the ability to build their own maps. A
major problem for robot map building is that odometry-based dead reckoning cannot be used to assign accurate
global position information to a map because of cumulative drift errors. This paper introduces a fast, on-line
algorithm for learning geometrically consistent maps using only local metric information. The algorithm works
by using a relaxation technique to minimize an energy function over many small steps. The approach differs from
previous work in that it is computationally cheap, easy to implement and is proven to converge to a globally optimal
solution. Experiments are presented in which large, complex environments were successfully mapped by a real
robot.

Keywords: simultaneous localization and mapping, concurrent map-building and self-localization, relaxation
algorithm, Gibbs sampling, learning and adaptation

1. Introduction This paper introduces a fast, on-line algorithm for

obtaining globally consistent maps. The approach dif-
Maps are very useful for mobile robot navigation fers from previous work in that it is computationally
in complex environments, being needed for self- cheap, easy to implement and is guaranteed to find a
localization and path planning, as well as enabling hu- solution that is statistically optimal. Our algorithm as-
man operators to see where the robot has been. While sumes three sources of perceptual information:
successful navigating robots have been developed us-
(i) a place recognition system,
ing pre-installed maps, to operate in unknown envi-
(ii) a global orientation obtained from a compass, and
ronments a robot needs the ability to build its own
(iii) local distance information from odometry.
maps. However, the sensor information available to
the robot is noisy and can produce errors when inte- Experiments are presented in which large, complex en-
grated into the map. In particular, the robot’s odom- vironments were successfully mapped by a real robot
etry is subject to drift errors caused by factors such using ultrasonic range-finder sensors for (i), a flux-gate
as wheel slippage, which can lead to an inconsistent compass for (ii), and uncorrected odometer sensors
mapping of the environment. To maintain a coherent for (iii).
representation of the environment that can be recon- The map representation consists of a topologically
ciled with future sensory perceptions, some means connected network of places, where each link is labeled
of maintaining geometric consistency in the map is with noisy metric information describing the relative
required. distance and absolute angle between the two places it
288 Duckett, Marsland and Shapiro

connects. The purpose of our algorithm is to assign a

globally consistent set of Cartesian coordinates to the
places in the map. In this approach, the coordinates of
the places are treated as free variables, and the algo-
rithm finds an optimal set of coordinates using only the
local metric relations between places.
The rest of this paper is structured as follows.
Section 2 provides a detailed description of the prob-
lem. Section 3 derives a map learning algorithm from
a statistical model of the noise on the robot’s sensors
and proves that the algorithm converges to a globally Figure 1. The map representation consists of a topologically
connected set of places, each place being associated with a local
optimal solution, together with a complexity analy- occupancy grid. The core problem addressed by this paper is to assign
sis. Section 4 describes the robotic platform used for geometrically consistent coordinates to the places.
the experiments, including implementation details of
the place recognition system and incremental map-
ping strategy applied. This is followed by experimen-
– Each place i is associated with a pair of Cartesian
tal results, related work and conclusions. Finally, two
coordinates ri = (xi , yi )T that are initially unas-
variants of the map learning algorithm are discussed:
signed (or they could be initialized approximately
a simplification of the basic algorithm for use when
by dead reckoning). The true coordinates are un-
only approximate geometric information is required
known to the robot.
(Appendix A), and a generalization for use when the
– Each link connects two places i and j, and is associ-
robot is not equipped with a compass (Appendix B).
ated with an estimated metric relation li j = (di j , θi j ),
measured by the robot, that describes the relative
2. The Problem
distance di j and angle θi j between the two places.
The angle θi j is an absolute measurement obtained
When maps are generated from the estimates of dis-
from the compass. In this paper, the links were con-
tances and angles measured by the robot, the geometry
strained to be bi-directional, that is, di j = d ji and
of the space will be non-Euclidean. For example, the
θi j = θ ji + π .
angles inside a triangle may not add up to 180◦ . As the
robot is exploring in Euclidean space, this is a problem.
Our map building algorithm aims to find an evidence- The algorithm derived in the next section aims to as-
based way of fixing this problem so that the maps are sign a globally consistent set of Cartesian coordinates
geometrically consistent. {r1 , . . . , r N } to the places in the map using the noisy
In our experiments, we use a graph-based model measurements of the distances and angles between the
of the environment, in which the nodes correspond places. This noise means that a perfect map cannot
to places and the links to traversable paths between be generated. Instead, we derive a statistically opti-
places (see Fig. 1). Each node in the graph is associ- mal algorithm to deal with this problem in a principled
ated with a local occupancy grid, constructed using the way.
robot’s sonar sensors, which is used as a place signa-
ture. For place recognition, we use the self-localization
algorithm described in Duckett and Nehmzow (2001),
which applies an occupancy grid-matching technique 3. The Map Learning Algorithm
to identify both the robot’s current place in the map and
the relative displacement of the robot from the center 3.1. Estimating the Noise
of that particular place (see Section 4 for more details).
For the following analysis, we define our maps as When the robot travels between two map places, a large
follows: number of small distances and angles are measured as
the robot continually updates its heading (see Fig. 2).
– The topological component of the map consists of a In our experiments, the distances are measured with
set of N place nodes and a set of links that connect odometry and the angles are measured with a flux-gate
pairs of places. compass. Let δt be the displacement and αt the heading
 Fast, On-Line Learning of Globally Consistent Maps 289

where δt is the noise in the estimate of the true dis-

tance δt∗ and αt is the noise in the estimate of the true
angle αt∗ .
Assuming that the noise measurements are small
compared to the distances traveled, the covariance ma-
trix C ji of the link measurements (d ji , θ ji ) can be cal-
culated using small deviation expansions as
 
−1
δδ δ ji αδ
C ji = T ji R(φ ji ) R(φ ji ), (5)
δ ji αδ δ 2ji αα

T
where δ ji = ( t ji δt )/T ji , that is the average distance
between updates, the δδ , etc. are global noise esti-
Figure 2. Example of how the robot travels between two map nodes, mates of the subscripted variables, and φ ji is the rota-
constantly updating its heading. In reality the number of update steps tional error between the two nodes, where R(φ) is the
is higher. rotation matrix

cos φ sin φ
R(φ) ≡ . (6)
at the tth step. Then − sin φ cos φ

 In our model, it is assumed that φ ji = 0 because of the

 T ji 2  T 2 compass, so the rotation matrix R(φ ji ) = I . This model
   ji

d ji =  δt cos αt + δt sin αt , (1) is invariant to global rotations and depends only on the
t t direction of travel. The noise parameters δδ , etc. are
 T  calculated by maximum likelihood estimation as part
−1 t
ji
δt sin αt
θ ji = tan T ji , (2) of the relaxation algorithm (Eqs. (12)–(14)).
t δt cos αt
3.2. The Algorithm
where T ji is the number of steps, i.e., the number of
updates the robot performs along a path. The map can be considered as a set of free nodes that are
Assuming that the number of updates made while held together by springs, where each spring connects
traveling between two map places is large and that the two adjacent places i and j (this analogy can also be
statistical properties of each step are independent, the found in (Lu and Milios, 1997a; Golfarelli et al., 1998;
Central Limit Theorem (Reif, 1982) implies that mea- and Shatkay, 1998)). Each spring reaches minimum
surements of d ji and θ ji will be normally distributed energy when the relative displacement between the co-
around their true values. ordinates of node i and node j is equal to the vector
Suppose that the noise properties are the same along (di j , θi j ) measured by the robot. Equilibrium is reached
a path between two map places (but not necessarily in the whole map when the total energy over all of the
between paths) and that successive measurements are springs reaches a global minimum. Thus, global con-
independent. That is, the measurement of the path from sistency is maintained in the map by minimizing the
place i to place j is independent of the measurement following energy function, which corresponds to the
from place j to place k (this means that the model log likelihood:
cannot deal with cumulative phenomena such as battery
drain). Then we can write the estimates of the distance 

travelled and the heading of the robot at each small E= (ri − r j − D ji )T C −1

ji (ri − r j − D ji ),
i j
step as
(7)

δt = δt∗ + δt 
(3) where
j refers to the sum over the neighbors of
θ ji
αt = αt∗ + αt (4) node i, ri = (xi , yi )T , and D ji = d ji ( cos
sin θ ji
).
290 Duckett, Marsland and Shapiro

Since each C ji is symmetric, Since E is bounded below, the algorithm must converge
and any legitimate stopping criterion must be reached.


The energy function is quadratic and therefore has a
∇ Ei = 2 C −1
ji (ri − r j − D ji ), (8) unique minimum, so the algorithm can only converge
j
to a global minimum. The fact that the energy function
is quadratic also means that the updates could be com-
when the position of node i is updated. Therefore, the puted in a single step by inverting the (N × N ) matrix
algorithm that finds the maximum likelihood solution showing connections between all of the nodes in the
is the one that finds the ri
that minimizes E, that is, map. Our system performs an iterative update instead,
 −1 which is computationally simple and fast, and therefore




more suitable for robotics applications.
ri
= C −1
ji C −1
ji (r j + D ji ). (9)
j j
3.4. Complexity Analysis
This can be considered as a form of Gibbs sampling
at zero temperature (Reif, 1982). One component is The computational cost of the new algorithm is lin-
optimized by keeping all of the others fixed. ear in the number of places in the map. Because the
The algorithm derived from Eq. (9) is given in Fig. 3. algorithm makes an iterative refinement to the existing
The basic principle of the algorithm is to “move each solution, rather than recalculating the entire coordinate
node to where its neighbors think it should be”. By it- system from scratch, only one iteration is typically re-
eration, the coordinates in the map converge towards quired whenever new information is added to the map.
a global minimum in the energy function (Eq. (7)). The complexity of the algorithm is thus bounded by
For on-line map learning, steps 2 and 3 in Fig. 3 are O(N M), where M is the maximum number of neigh-
inter-leaved with the rest of the navigation control soft- bors per node. For a topological map, the number of
ware so that the map is adapted continually during links per node will not grow with the size of the map,
exploration. so M is constant and the overall complexity is approxi-
An example illustrating the convergence of the re- mately O(N ). This compares favorably with the worst
laxation algorithm is given in Figs. 4 and 5. In this ex- case O(N 3 ) complexity of matrix inversion methods
periment, the coordinates of the self-acquired map in such as Lu and Milios (1997a) and Golfarelli et al.
Fig. 4 were randomly reinitialized to arbitrary values, (1998) (though that can be reduced to O(N 2 ) by using
then the algorithm was iterated until the map returned a sparse matrix solver if the covariance matrix is not
to its globally consistent solution. (Note that this differs required (Frese and Hirzinger, 2001)).
from the normal, on-line use of the algorithm, where
the coordinates are not reinitialized; rather, the existing
coordinates are adapted continually over time.) 4. Robotic Implementation

The relaxation algorithm was tested on a Nomad 200

3.3. Proof of Convergence robot as part of a complete system for mapping un-
known environments (Duckett, 2000). In this system,
To prove convergence of the algorithm, we show here the robot attempts to space the place nodes in the map
that the algorithm always minimizes the energy func- at equal intervals of 1 meter. Some important details of
tion (Eq. (7)). When a node i with position ri is up- the robotic implementation are given as follows.
dated, its new position ri
will be given by Eq. (9). That
is,
 the
new position is picked to minimize the value of 4.1. Compass Sense
j (ri − r j − D ji ). Hence, the change in energy will be

To pre-process the readings from the robot’s flux-gate



 compass, we used the behavior-based filtering method

E = (ri
− r j − D ji ) T
C −1

ji (ri − r j − D ji )
j
described in Duckett and Nehmzow (2001). In this ap-
 proach, a separate behavior is used to rotate the robot’s
− (ri − r j − D ji )T C −1
ji (ri − r j − D ji ) (15) turret at small speeds in the direction of an arbitrary
≤ 0. (16) ‘North’, as indicated by the compass. Then the angular
 Fast, On-Line Learning of Globally Consistent Maps 291

Figure 3. The maximum likelihood map learning algorithm.

estimates are obtained by measuring the relative tation around the average value of ‘North’. We have
displacement of the turret against the direction of travel. found that the performance of this method degrades
The effect of this behavior is to smooth out any fluc- gracefully with respect to the magnetic variations in
tuations in the compass readings caused by electro- the environment. It also has the advantage of keeping
magnetic disturbances, maintaining a constant orien- the robot’s range-finder sensors at a steady orientation,
292 Duckett, Marsland and Shapiro

Figure 4. Left: floor plan of a corridor environment at Manchester University (size 34 m × 33 m). Right: the corresponding map acquired by
the robot.

Figure 5. Convergence of the relaxation algorithm. In the first picture, the coordinates of the self-acquired map shown in Fig. 4 have been
randomly reinitialized. The remaining pictures show the map after 10, 25, 50, 100, 250, 500 and 1000 iterations respectively of the relaxation
algorithm.

which can help to reduce the noise on the ultrasonic – Predicted. Places presumed to exist but not yet vis-
sensor readings. This compass sense was also used for ited by the robot.
the on-line dead reckoning, as illustrated in Fig. 6. – Confirmed. Places actually visited by the robot.

The basic exploration strategy consists of trying to

4.2. Exploration Strategy move towards the nearest predicted place, using a stan-
dard graph-based path planning algorithm to determine
Topological map building was performed using an in- the route. An artificial neural network is used to predict
cremental exploration strategy, in which the robot con- new places by classifying the robot’s sonar readings in
tinually tries to expand the territory that has already all directions (see Duckett and Nehmzow (1999) for
been charted (see Fig. 7). To implement this strat- full details). A local dead reckoning strategy is used
egy, two different types of place are included in the to decide whether to confirm the predicted places: a
map: predicted place is replaced by a confirmed place if a
 Fast, On-Line Learning of Globally Consistent Maps 293

Figure 6. Left: raw odometry. Right: compass-based odometry. The accumulated rotational drift in the robot’s raw odometry was removed
on-line using the compass sense. In this example, the robot repeatedly traversed the environment of Fig. 4 by wall-following.

any other confirmed places lying less than 2 meters

from the added node, provided that the neural network
indicates open space in that particular direction. The
whole process is repeated until all predicted places in
the map have either been visited by the robot or deleted.
In the experiments presented here, an extra heuristic
was added to this strategy to force the robot to close
loops, described as follows. Whenever a new confirmed
place is added to the map, a search is carried out on each
of the adjacent confirmed place nodes to determine the
shortest path actually traversed by the robot from that
particular node. If the length of that path exceeds a
pre-specified threshold of 3 meters, then the robot is
forced to travel directly to that node in order to obtain a
measurement of the metric relation for the connecting
link. Only the physically traversed links are used by
Figure 7. Example of incremental map building. Places predicted the relaxation algorithm in the calculation of the node
but not yet visited by the robot are shown by squares. Places visited coordinates (the inferred links are used only for path
by the robot are shown by filled circles (the numbers indicate the planning). In the self-acquired map of Fig. 12, the links
sequence in which they were visited). actually traversed by the robot are shown in bold, while
the inferred links are shown by dotted lines.
The links in the topological map are maintained us-
distance of 1 meter from the nearest existing confirmed
ing the following rules taken from Yamauchi and Beer
place can be traveled, otherwise the predicted place
(1996). Whenever a new link is added to the map, a con-
is deleted from the map. The coordinates produced
fidence level, ci j , for that link is initialized to a value
by dead reckoning (relative to the last visited place)
of 0.5. During repeat traversals of the same link, the
are also used to initialize the coordinates of the con-
confidence level is increased using
firmed places before the relaxation algorithm is ap-
plied. Whenever another confirmed place is added to
the map, the neural network is used again to predict
more places. In addition, connections are inferred to ci
j = λ + (1 − λ)ci j , (17)
294 Duckett, Marsland and Shapiro

where the link adaptation rate, λ = 0.5 in these experi-

ments. Conversely, whenever the robot fails to traverse
a given link, e.g., because the robot reaches a different
destination to the one intended by the path planner, the
confidence value is decreased using

ci
j = (1 − λ)ci j . (18)

A link is deleted from the map whenever its confi-

dence level falls below a pre-specified threshold (0.2
in these experiments). A node is deleted from the map
if no path can be found to that node from the robot’s
current location, i.e., when no possible routes exist due
to link deletion. Figure 8. Example occupancy grid and histograms. Occupied cells
are shown in black, empty cells in white and unknown cells in gray.

4.3. Use of Local Metric Information

In the derivation of the relaxation algorithm in

Section 3, it was assumed that the robot takes mea-
surements of the relative distances and angles between
a discrete set of places, which correspond to the nodes
of a graph. In reality, the robot moves in a continuous
space, and the places are contiguous regions rather than
single points in space. So to implement the algorithm,
some means of measuring the position of the robot rel-
ative to the centre of the current place is required. In
our approach, as in others (Weiss and von Puttkamer,
1995; Lu and Milios, 1997a; Gutmann and Konolige, Figure 9. Matching the x and y histograms. The observation
1999), this is achieved by scan matching. Specifically, histograms are convolved with the stored histograms for each place
in the robot’s map to find the best match.
we use the local occupancy maps embedded in the hy-
brid metric-topological representation of Fig. 1.
In our approach, we do not store or match the actual 2. The most likely offset of the robot from the center of
occupancy grids. Instead, we first reduce each grid to the place, i.e., the position in which the sonar scan
a pair of histograms, one in x-direction and one in for that place was taken.
y-direction, as shown in Fig. 8. This is done by adding
up the total number of occupied, empty and unknown The strength of the match between two histograms
cells in each row or column of the grid (see Duckett T a and T b is calculated using the following evaluation
and Nehmzow (2001) for a full description). A pair of function:
occupancy histograms is stored for each place in the
robot’s map, and scan matching then consists of con- 1   
Match(T a , T b ) = min O aj , O bj
volving a new pair of histograms constructed from the w j
robot’s immediate sonar readings with the stored his-    
tograms, as in Fig. 9. In the absence of a compass, we + min E aj , E bj + min U aj , U bj ,
would also have to consider angle histograms, as in (19)
Hinkel and Knieriemen (1988). For each stored place
i, the matching procedure yields two useful quantities: where O j , E j and U j refer to the number of occu-
pied, empty and unknown cells contained in the jth
1. A metric that quantifies the strength of the match element of histogram T , and w is a normalizing con-
between the observation histograms and the stored stant such that 0 ≤ Match( ) ≤ 1. The match scores are
histograms for place i. used for place recognition: the most likely location
 Fast, On-Line Learning of Globally Consistent Maps 295

of the robot in the map is determined by a Bayesian where

multi-hypothesis tracking algorithm (Duckett and
Nehmzow, 2001), which takes into account the prior xi j = r xi + x − r x j , (26)
probability distribution over the places in the map, the yi j = r yi + y − r y j , (27)
movement of the robot between observations and the
new observation match scores. with the vector (x, y) referring to the link mea-
The most likely offset (r x∗ , r y∗ ) of the robot from the surement obtained by dead reckoning, and the (r xi , r yi )
centre of the current place is then obtained by multi- referring to the filtered offsets for place i from Eq. (22).
plying the best-matching translations for the x and y In the current implementation, the link measurement is
histograms by the dimensions of one grid cell (15 cm × obtained from the first traversal of the link only, and
15 cm). To obtain an estimate of the error in the scan the metric information from any subsequent traversals
matching, the following heuristic functions are used: is discarded.

k 5. Experimental Results
σx2 = , (20)
(Mx∗
− M̄ x )2
k The system was tested in the office environment shown
σ y2 = ∗
, (21) in Figs.10 and 11. The map acquired by the robot in
(M y − M̄ y )2
Fig. 12 shows the position of the places in global co-
where σx2 refers to the error estimate for the ordinates calculated by the new algorithm. To illus-
x-histograms, Mx∗ refers to the value of Match( ) pro- trate the accuracy of the acquired map, we have also
duced by the best-matching alignment of x histograms combined the relaxed coordinates with the recorded
for the current place, M̄ x refers to the mean value of sonar data to produce a global occupancy grid model
Match( ) in the convolution of x histograms, and the of the environment, using the standard technique de-
constant k = 1.0 m2 in these experiments. veloped by Moravec and Elfes (1985). The derived
To minimize the overall error due to scan matching, gridmap is shown in Fig. 13. The map has a resolution
all of the estimates of the offset from the place center of 0.15 meters, and should be accurate enough for safe
that are made by the robot as it travels through the navigation and planning. This can be compared to the
current place are combined together using an iterative gridmap constructed from the robot’s compass-based
filtering technique, which is specified by the following odometry in Fig. 14.
equations: The entire process requires minimal computational
resources. Maximum likelihood estimation with the
σx2

r x = r x
+ (r ∗ − r x
), (22) new algorithm was performed on-line as part of the
σx2
+ σx2∗ x
1 1 1
= 2 + 2, (23)
σx2 σx
σx ∗
where r x is the new x-offset relative to the place cen-
tre, r x∗ is the x-offset from the latest observation, and r x

is the previous x-offset updated by dead reckoning to

take into account the movement of the robot between
observations. The quantities σx2 , σx2∗ , and σx2
are the
corresponding error measures. In the experiments pre-
sented here, the occupancy histograms were extracted
from sonar scans taken at intervals of 50 cm by the
traveling robot.
The estimated metric relation, li j = (di j , θi j ), for the
link connecting two places i and j is then obtained as

di j = (xi j )2 + (yi j )2 , (24)

Figure 10. The Nomad 200 mobile robot Milou in the test environ-
yi j
θi j = tan−1 , (25) ment at Örebro University (corresponding to the right-hand side of
xi j the map in Fig. 11).
296 Duckett, Marsland and Shapiro

Figure 11. A semi-structured office environment at Örebro University, with an approximate size of 46 × 12 meters.

Figure 12. The map acquired with the new map learning algorithm. The links actually traversed by the robot are shown in bold, and the inferred
links are shown by dotted lines (only the traversed links were used to estimate the node coordinates).

Figure 13. The global gridmap constructed with the new algorithm, by combining the recorded sonar data with the global coordinates generated
by the algorithm.

Figure 14. The global gridmap constructed without the new algorithm, by combining the recorded sonar data with the global coordinates
calculated using the compass and odometry. Without the algorithm, the robot fails to build a consistent map.

map building process. One iteration of the algorithm 6. Related Work

on the full map, consisting of 137 places and 188 phys-
ically traversed links, required 20 msec. on a 200 MHz Lu and Milios (1997a) considered the problem of
Pentium II processor. enforcing geometric consistency in a metric map
 Fast, On-Line Learning of Globally Consistent Maps 297

constructed using laser range-finder sensors without ter data) to avoid local maxima and hence build topo-
a compass. Their approach maintained a history of all logically correct maps. The approach would not scale
the local frames of sensor data used to construct the well to larger environments due to the large amount of
map and the network of spatial relations between the data needed and the high computational cost of the EM
frames. The spatial relations were obtained either by algorithm.
odometry or pairwise matching of the range-finder data A similar approach is described by Thrun et al.
in adjacent frames, using the scan matching algorithm (1998), where an EM algorithm was used to learn an
described in Lu and Milios (1997b). A maximum like- occupancy grid model of a large environment (90 m ×
lihood algorithm was then used to derive a position 90 m). Again, this method is extremely expensive, re-
estimate for each of the frames, by minimizing the quiring up to two hours of computation to generate a
Mahalanobis distance between the actual and derived grid map with a spatial resolution of 1 meter, and it
relations over the whole network of frames. A draw- depends on a manually labeled set of landmarks. This
back of this method is that it requires the inversion of approach was later extended by Burgard et al. (1999) to
a 3n × 3n matrix, where n is the number of frames, so use a network of local gridmaps constructed from sonar
the approach is likely to be computationally expensive data, as in our approach, instead of the pre-defined
in large environments. This approach was extended by landmarks.
Gutmann and Konolige (1999) to build maps in envi-
ronments containing large cycles. 7. Discussion
A similar approach is described by Golfarelli et al.
(1998), using a graph-based model of the robot’s envi- In this paper, we have presented a relaxation algorithm
ronment. Their algorithm operates under the assump- for maintaining geometric consistency in a robot’s map.
tion of no topological errors, so that the robot recog- The algorithm is computationally very cheap, enabling
nises a place when it visits it for a second time. Their globally consistent map learning in real-time. Its O(N )
system was based on the analogy of a mechanical spring complexity compares favorably to that of matrix in-
system, in which each link in the graph is modeled version methods such as Lu and Milios (1997a). The
by a pair of springs, a linear axial spring and a ro- method is particularly efficient because it does not
tational one. The elasticity parameters of the springs throw any useful information away; instead of recalcu-
were used to represent the uncertainty in the robot’s lating the entire map from scratch every time, the exist-
odometry measurements, and the equilibrium position ing solution is refined. As a result, only small changes
for the whole structure was then calculated, generating to the map are typically required when new informa-
a 4n × 4n matrix that requires inverting. The algorithm tion is added. In the experiments conducted, we found
can be applied with or without a compass, although all it was only necessary to run the relaxation algorithm for
of their experiments appear to use a compass. Their a single iteration at each cycle of the map acquisition
results seem qualitatively similar to ours (at least by process.
visual inspection) despite the added complexity of the The method works by minimizing an energy func-
mechanical spring system model. tion in lots of small steps, rather like a Hopfield network
Shatkay and Kaelbling (1997) and Shatkay (1998) (Hopfield, 1982). Because this energy function corre-
addressed the problem of incorporating metric infor- sponds to the log likelihood, minimizing this function
mation from odometry into robot maps based on Par- provides us with the maximum likelihood solution to
tially Observable Markov Decision Process (POMDP) the map learning problem, provided that the map is
models and enforcing geometric consistency in these topologically correct. We have proved that the relax-
maps, both with and without a compass. The sensor ation algorithm always converges to a globally optimal
data from which the models were acquired were first solution, in contrast to EM algorithms, which are sub-
collected by the robot under manual control, then an ject to local optima. We should, of course, point out
expectation-maximization (EM) algorithm was used that our method assumes a place recognition system
to find the map which best fitted the recorded data. (in other words, no topological errors) before maxi-
While this algorithm does not explicitly make the as- mum likelihood estimation takes place, an assumption
sumption of an initial topological map, in practice it that is not made by Shatkay and Kaelbling (1997) and
depends heavily on a sufficiently good initial model Burgard et al. (1999). However, all of our experiments
(obtained in Shatkay (1998) from the recorded odome- were conducted on a real, self-navigating robot using a
298 Duckett, Marsland and Shapiro

real self-localization system (Duckett and Nehmzow, Appendix A: A Simplification of the Algorithm
2001), without requiring any pre-installed environ-
ment model, thus demonstrating the efficacy of our In the derivation of the algorithm in Section 3, various
approach. assumptions were made, e.g., that small angle approxi-
Through our experiments, we have demonstrated mations could be made, and that the covariance matrix
a complete solution to the problem of simultaneous C ji was symmetric. In fact, the most common noise
localization and mapping (SLAM) for indoor, office model estimate for a mobile robot’s position is an el-
environments. This solution agrees favorably with lipse, with the major axis lying perpendicular to the
the theoretical requirements for an ideal SLAM so- direction of travel, as in Smith and Cheeseman (1986).
lution outlined by Frese and Hirzinger (2001), as However, when a compass is used, the noise on the dis-
follows: tance measurement (odometry) could be greater than
the noise on the rotation measurement, so that the ma-
1. The hybrid metric-topological representation pre- jor axis lies along the direction of travel. Both of these
serves the “certainty of relations despite the uncer- models assume that the robot is perfectly symmetrical,
tainty of positions”. which is not necessarily the case. For instance, the robot
2. This representation also means that the memory re- may measure turns more accurately anticlockwise than
quired for storage grows only linearly with the num- clockwise, or one of the wheels could slip more than
ber of nodes in the map. the other, so that the robot does not follow a straight
3. The new map learning algorithm is computationally line.
cheap, having a cost that is linear in the number of In previous experiments (Duckett et al., 2000), we
places stored in the map. found that surprisingly good results can be obtained by
making one further simplifying assumption: that the
There is one possible situation where the new algo- noise in the robot’s position estimates is distributed
rithm may be significantly slower than usual—that is equally in all directions around points in Cartesian
if the robot closes a very large cycle and the accumu- space according to a Gaussian distribution, i.e., a cir-
lated odometric error is very high. Here it might be cle rather than an ellipse in used to represent the area
faster to use a simultaneous equation solver, as in Lu in which the robot may be located with non-negligible
and Milios (1997a) and Gutmann and Konolige (1999), probability. Thus, the uncertainty in any point to point
depending on the magnitude of the initial error in the measurement can be represented by a single variance
map (cf. Fig. 5). However, while theoretically possible, measure (this makes the covariance matrix C ji propor-
this situation tends to be very rare in practice, and re- tional to the identity matrix). For dead reckoning, this
laxation should be faster in the vast majority of cases. can be taken as some small proportion, e.g., 5%, of the
The relatively large loops in the test environment of distance travelled by the robot. The algorithm can then
Fig. 11 did not pose a problem in any of the experi- be described in two steps, as given in Fig. 15. While
ments conducted. less accurate than the algorithm in Fig. 3, this variant
A further benefit of the new algorithm is that all of the is much easier to implement, and is useful when only
global noise parameters are continually re-estimated by approximate geometric information is required in the
the algorithm itself, so we do not need to compute the robot’s map.
values of these parameters ourselves. This is a distinct
advantage for building autonomous robots, since re-
ducing the number of pre-installed parameter values Appendix B: Relaxation without a Compass
reduces the dependence of the robot on a priori knowl-
edge provided by the system designer. Although in this paper we have used a compass to
Future work will investigate more intelligent strate- provide a global ‘North’ from which all angular mea-
gies for selecting the landmarks or place signatures surements are taken, this should not be necessary if
in the topological map (see Marsland et al. (2001) the robot is equipped with some other means of mea-
for some first results). The current strategy of adding suring the angles that it turns through. Suppose that
new places at 1 meter intervals is clearly inefficient, the robot has the ability to measure the change in its
and could be greatly improved. We will also con- pose when moving between two adjacent places, e.g.,
sider building maps in environments containing large by matching laser range-finder scans, as in Weiss and
cycles. von Puttkamer (1995), Lu and Milios (1997a), and
 Fast, On-Line Learning of Globally Consistent Maps 299

1. For each node i , do:

a) For each of the neighbors j of node i , i.e., the places that are topologically connected
to i , obtain an estimate r
ji of the coordinates of node i using

r
ji = r j + D ji , (28)

where r j = (x j ,y j )T refers to the coordinates of node j , and D ji = d ji ( cos θ ji ).

sin θ ji
b) Combine the position estimates r
ji for all j to produce new coordinates ri
for node i
using
 −1
 



ri
= v −1
ji v −1

ji r ji , (29)
j j

where
j refers to the sum over the neighbours of node i , and v ji is the variance for
the link from node i to node j .

2. Repeat from step 1 untill the change in energy falls below some pre-defined threshold, or
some other stopping criterion is reached.

Figure 15. A simplification of the map learning algorithm, based on the assumption of circular noise in the robot’s odometry.

Gutmann and Konolige (1999). To maintain geometric References

consistency in the map, the relaxation algorithm can
then be extended to estimate a pose ri = (xi , yi , θi )T Burgard, W., Fox, D., Jans, H., Matenar, C., and Thrun, S. 1999.
for each node i of the map, where the angle θi corre- Sonar-based mapping with mobile robots using EM. In Proc. of
the International Conference on Machine Learning.
sponds to the orientation of the robot in which the scan Duckett, T. 2000. Concurrent map building and self-localisation for
for that particular place was taken. Equation (10) of the mobile robot navigation. Ph.D. Thesis, Department of Computer
algorithm in Fig. 3 is rewritten as: Science, University of Manchester.
Duckett, T., Marsland, S., and Shapiro, J. 2000. Learning glob-
ally consistent maps by relaxation. In Proceedings of the
r
ji = ri + F ji , (30) IEEE International Conference on Robotics and Automation
(ICRA’2000), San Francisco, CA.
Duckett, T. and Nehmzow, U. 1999. Exploration of unknown envi-
ronments using a compass, topological map and neural network. In
where Proceedings of the 1999 IEEE International Symposium on Com-
putational Intelligence in Robotics and Automation, Monterey,
  CA, pp. 312–317.
x ji cos θi − y ji sin θi Duckett, T. and Nehmzow, U. 2001. Mobile robot self-localisation
  using occupancy histograms and a mixture of Gaussian loca-
F ji =  x ji sin θi + y ji cos θi  , (31) tion hypotheses. Robotics and Autonomous Systems, 34(2/3):119–
φ ji 130.
Frese, U. and Hirzinger, G. 2001. Simultaneous localization and
mapping—A discussion. In Proceedings of the IJCAI-2001 Work-
shop on Reasoning with Uncertainty in Robotics (RUR’01), D. Fox
with (x ji , y ji , φ ji )T referring to the relative pose be- and A. Saffiotti (Eds.).
tween nodes i and j, after Lu and Milios (1997a). The Golfarelli, M., Maio, D., and Rizzi, S. 1998. Elastic correction of
derived orientation θ j for node j will be an estimate dead-reckoning errors in map building. In Proceedings of the
relative to an arbitrary ‘North’, i.e., the orientation of IEEE/RSJ International Conference on Intelligent Robots and Sys-
tems (IROS’98), Victoria, Canada, pp. 905–911.
the robot at the origin.
Gutmann, J.-S. and Konolige, K. 1999. Incremental mapping
With suitable changes to the covariance matrix (i.e., of large cyclic environments. In Proceedings of the 1999
making it 3 × 3, with estimates of the noise in the IEEE International Symposium on Computational Intelligence in
angles), the nature of the algorithm can then be pre- Robotics and Automation, Monterey, CA.
served. Obviously, this requires the storage of more Hinkel, R. and Knieriemen, T. 1988. Environment perception with a
laser radar in a fast moving robot. In Symposium on Robot Control
angles, and there will be noise in the rotational mea-
(SYROCO’88), Karlsruhe, Germany.
surements. This is why using a compass, even in indoor Hopfield, J. 1982. Neural networks and physical systems with emer-
environments where there are likely to be a lot of elec- gent collective computational abilities. In Proceedings of the Na-
tromagnetic disturbances, is advantageous. tional Academy of Sciences, USA, 79:2554–2558.
300 Duckett, Marsland and Shapiro

Lu, F. and Milios, E. 1997a. Globally consistent range scan alignment his B.Sc. from Warwick University in Computer and Management
for environment mapping. Autonomous Robots, 4:333–349. Sciences, M.Sc. from Heriot-Watt University in Knowledge Based
Lu, F. and Milios, E. 1997b. Robot pose estimation in unknown en- Systems, and Ph.D. from Manchester University on simultaneous
vironments by matching 2D range scans. Intelligent and Robotics localisation and map-building for mobile robot navigation. His re-
Systems, 18:249–275. search interests include autonomous robots, machine learning and
Marsland, S., Nehmzow, U., and Duckett, T. 2001. Learning to select neural networks, artificial intelligence, and biology inspired sensor
distinctive landmarks for mobile robot navigation. Robotics and systems.
Autonomous Systems, 37(4):241–260.
Moravec, H. and Elfes, A. 1985. High resolution maps from wide
angle sonar. In Proceedings of the IEEE International Confer-
ence on Robotics and Automation (ICRA’85), St. Louis, Missouri,
pp. 116–121.
Reif, F. 1982. Fundamentals of Statistical and Thermal Physics.
McGraw-Hill: New York.
Shatkay, H. 1998. Learning models for robot navigation. Ph.D. The-
sis, Department of Computer Science, Brown University.
Shatkay, H. and Kaelbling, L.P. 1997. Learning topological maps
with weak local odometric information. In Proceedings of the 15th
International Joint Conference on Artificial Intelligence.
Smith, R. and Cheeseman, P. 1986. On the representation and es- Stephen Marsland recently completed his Ph.D. on unsupervised
timation of spatial uncertainty. International Journal of Robotics novelty detection and is currently a lecturer of machine learning at
Research, 5(4):56–68. the University of Manchester. Prior to that he completed a degree
Thrun, S., Burgard, W., and Fox, D. 1998. A probabilistic approach to in Mathematics and Computation at Somerville College, University
concurrent mapping and localisation for mobile robots. Machine of Oxford. His research interests include many aspects of theoreti-
Learning, 31(5):1–25. cal machine and statistical learning, such as neural networks, self-
Weiss, G. and von Puttkamer, E. 1995. A map based on laserscans organisation and topology preservation, and Gaussian processes. He
without geometric interpretation. In Proceedings of Intelligent is interested in many applications of machine learning techniques
Autonomous Systems 4 (IAS-4), Karlsruhe, Germany, pp. 403– to real world domains, such as robotics, medical informatics and
407. bioinformatics.
Yamauchi, B. and Beer, R. 1996. Spatial learning for navigation in
dynamic environments. IEEE Transactions on Systems, Man and
Cybernetics Section B, 26(3).

Jonathan Shapiro got his Ph.D. from UCLA in theoretical con-

densed matter physics. He works in the fields of theory of neu-
ral networks, application of neural networks, particularly to cog-
nitive modelling, and theory of evolutionary algorithms. He is
Tom Duckett is an Assistant Professor at Örebro University, where currently Senior Lecturer in Computer Science at the University
he is currently setting up a new research laboratory in robot learning of Manchester, and External Faculty member of The Santa Fe
within the Centre for Applied Autonomous Sensor Systems. He got Institute.