Best Conference Paper Award

IEEE International Conference on Robotics

and Automation, San Francisco, April 2000

A Real-Time Algorithm for Mobile Robot Mapping With Applications to

Multi-Robot and 3D Mapping

Sebastian Thrun1 Wolfram Burgard2 Dieter Fox1

1 2
Computer Science Department Computer Science Department
Carnegie Mellon University University of Freiburg
Pittsburgh, PA Freiburg, Germany

Abstract multaneously considering the locations of all past scans,

using a probabilistic argument for iterative refinement dur-
We present an incremental method for concurrent mapping ing map construction. While these approaches have suc-
and localization for mobile robots equipped with 2D laser cessfully mapped large cyclic environments, they are batch
range finders. The approach uses a fast implementation algorithms that cannot be run in real-time. Thus, a natural
of scan-matching for mapping, paired with a sample-based goal is to devise methods that combine the advantages of
probabilistic method for localization. Compact 3D maps both methodologies, without giving up too much of the full
are generated using a multi-resolution approach adopted power of EM so that large cycles can be mapped in real-
from the computer graphics literature, fed by data from a time.
dual laser system. Our approach builds 3D maps of large,
Most previous approaches also construct 2D maps only, and
cyclic environments in real-time. It is remarkably robust.
they only address single-robot mapping. Here our focus is
Experimental results illustrate that accurate maps of large,
also on multi-robot mapping and 3D maps.
cyclic environments can be generated even in the absence
of any odometric data. This paper presents a novel algorithm that combines ideas
from the EM approach, but nevertheless is strictly incre-
mental. The basic idea is to combine the idea of posterior
1 Introduction estimation—a key element of the EM-based approach—
with that of incremental map construction using maximum
Building maps of indoor environments is a pivotal problem
likelihood estimators—a key element of previous incre-
in mobile robotics. The problem of mapping is often re-
mental approaches. The result is an algorithm that can
ferred to as the concurrent mapping and localization prob-
build large maps in environments with cycles, in real-time
lem, to indicate its chicken-and-egg nature: Building maps
on a low-end computer. The posterior estimation approach
when a robot’s locations are known is relatively straight-
makes it possible to integrate data collected my more than
forward, as early work by Moravec and Elfes has demon-
one robot, since it enables robots to globally localize them-
strated more than a decade ago [10]. Conversely, localizing
selves in maps built by other robots. We also extend our
a robot when a map is readily available is also relatively
approach to the generation of 3D maps, where a multi-
well-understood, as a flurry of algorithms has successfully
resolution algorithm is used to generate low-complexity 3D
demonstrated [1]. In combination, however, the problem is
models of indoor environments.
hard.
In evaluations using a range of mobile robots, we found that
Recent progress has led to a range of new methods. Most
our approach is extremely robust. Figure 1 shows some of
of these approaches build maps incrementally, by iterating
the robots used in our experiments; not shown there are
localization and incremental mapping for each new sensor
RWI B21 and Nomad Scout robots which we also used
scan the robot receives [8, 13, 19, 20]. While these methods
in evaluating our approach. Some of our robots have ex-
are fast and can well be applied in real-time, they typically
tremely poor odometry, such as the robot shown in Fig-
fail when mapping large cyclic environments. This is be-
ure 1c. We show a collection of results obtained under a
cause in environments with cycles, the robot’s cumulative
vast range of conditions, including cases where no odome-
error can grow without bounds, and when closing the cycle
try was available for mapping at all.
error has to be corrected backwards in time (which most
existing methods are incapable of doing). A recent fam-
ily of probabilistic methods based on EM overcome this
problem [15, 18]. EM searches the most likely map by si-
(a) (b) (c)
Figure 1: Robots: (a) Pioneer robots used for multi-robot mapping. (b) Pioneer robot with 2 laser range finders used for 3D mapping. (c) Urban robot for
indoor and outdoor exploration. The urban robot’s odometry is extremely poor. All robots have been manufactured by RWI/ISR.

2 Mapping As shown in [18], the map likelihood function P (m | dt )

can be transformed into the following product:
At the most fundamental level, the problem of concurrent
mapping and localization can be treated as a maximum like- Z Z Y
t
lihood estimation problem, in which one seeks to find the P (m | dt ) = η P (m) ··· P (oτ | m, sτ )
most likely map given the data. In this section, we will τ=0
briefly restate the well-known map likelihood function, and Y
t−1
then discuss a family of incremental on-line algorithms that · P (sτ+1 | aτ , sτ ) ds1 . . . dst (4)
approximate the maximum likelihood solution. Our ap- τ=0
proach is somewhat specific to robots equipped with 2D
laser range finders or similar proximity sensors, which have where η is a normalizer (which is irrelevant when comput-
become very popular in recent years. As we will show, ing (3)) and P (m) is prior over maps which, if assumed to
our approach works well even in the complete absence of be uniform, can safely be omitted. Thus, the map likelihood
odometry data, and it also extends to the generation of 3D is a function of two terms, the motion model, P (sτ+1 |
with laser range finders. aτ , sτ ), and the perceptual model, P (oτ | mt , sτ ). Since
we can safely assume stationarity (i.e., neither model de-
2.1 Likelihood Function pends on the time index τ ), we omit the time index and
instead write P (s | a, s0 ) for the motion model and P (o |
Let m be a map. Following the literature on laser scan
m, s) for the perceptual model.
matching [6, 9], we assume that a map is a collection of
scans and their poses; the term pose refers to the x-y loca- Throughout this paper, we adopt the probabilistic motion
tion relative to some hypothetical coordinate system and a model shown in Figure 2. This figure depicts (projected
scan’s orientation θ. At time t, the map is written into 2D) the probability of being at pose s, if the robot pre-
viously was at s0 and executed action a. As can be seen,
mt = {hoτ , ŝτ i}τ=0,...,t (1) the shape of this conditional density resembles that of a
banana. This distribution is obtained by the (obvious) kine-
where oτ denotes a laser scan and ŝτ its pose, and τ is matic equations, assuming that robot motion is noisy along
a time index. Pictures of maps can be found pervasively its rotational and translational component.
throughout this paper. The perceptual model is inherited from the rich literature
The goal of mapping is to find the most likely map given on scan matching and projection filtering [6, 9]. Here the
the data, that is, assumption is that when a robot receives a sensor scan, it
is unlikely that future measurements perceive an obstacle
argmax P (m | dt ) (2) within space previously perceived as free. The larger the
m
distance between current and previous measurements, the
The data dt is a sequence of laser range measurements and lower the likelihood. This is illustrated in Figure 3. This
odometry readings: figure shows a sensor scan (dots at the outside), along with
the likelihood function (grayly shaded area): the darker a
dt = {s0 , a0 , s1 , a1 , . . . , st } (3) region, the smaller the likelihood of observing an obstacle.
Notice that the likelihood function only applies a “penalty”
where sτ denotes an observation (laser range scan), aτ de- to regions in the visual range of the scan; it is usually com-
notes an odometry reading, and t and τ are time indexes. puted using ray-tracing.
Without loss of generality, we assume here that observa- A key feature of both models, the motion model and the
tions and odometry readings are alternated. perceptual model, is the fact that they are differentiable.
 Figure 3: Likelihood function generated from a single sensor scan. The
robot is on the left (circle), and the scan is depicted by 180 dots in front of
the robot. The likelihood function is shown by the grey shading: the darker
a region, the smaller the likelihood for sensing an object there. Notice that
occluded regions are white (and hence incur no penalty).
Figure 2: The motion model: shown here is the probability distribution
P (s | a, s0 ) for the robot’s posterior pose s after moving distance a be- The idea is simple, and probably because of its simplicity
ginning at location s0 , for two example trajectories. it is popular: Given a scan and an odometry reading, deter-
mine the most likely pose. Then append the pose and the
More specifically, our approach uses the gradients
scan to the map, and freeze it once and forever.
∂P (s | a, s0 ) ∂P (o | m, s) Mathematically, the most likely pose at time t is given by
(5)
∂s ∂s
ŝt = argmax P (st | ot , at−1, ŝt−1 ) (6)
for efficiently searching the most likely pose of a robot st
given its sensor measurements. The derivation of the equa-
tions is relatively straightforward (though tedious) and will which is usually determined using hill climbing (gradient
not be given for brevity. However, in our implementation ascent). The result of the search, ŝt is then appended to the
the gradient computation is carried out highly efficiently, map along with the corresponding scan ot :
enabling us to compute 1,000 or more gradients per sec-
mt+1 = mt ∪ {hot , , ŝt i} (7)
ond on a low-end PC. Further down, we will exploit the
fact that the gradient can be computed so quickly, and use As noticed above, this approach typically works well in
hill climbing for determining the most likely solution of non-cyclic environments. When closing cycle, however,
mapping-related subproblems. this approach suffers form two crucial shortcomings:
Let us briefly get back to the general likelihood function
(4). Obviously, maximization of (4) yields the most likely 1. Pose errors can grow arbitrarily large. When closing the
map. Unfortunately, it is infeasible to maximize (4) in real- loop in a cyclic environment, search algorithms like gra-
time, while the robot moves. This is because the likeli- dient descent might fail to find the optimal solution.
hood cannot be maximized incrementally; instead, sensor
measurements often carry information about past robot lo- 2. When closing a loop in a cyclic environment, Past poses
cations, which makes it necessary to revise past estimates may have to be revised to generate a consistent map,
as new information arrives. As noticed on [6, 9], this is which this approach is incapable of doing.
most obvious when a robot “closes a loop,” that is, when
The brittleness of the approach, thus, is due to two factors:
it traverses a cyclic environment. When closing a loop,
Past estimates are never revised, and only a single guess is
the robot’s error might be arbitrarily large, and generating maintained as to where the robot is, instead of a full distri-
a consistent map requires the correction of the map back- bution. Notice that neither of these restrictions applies to
wards in time. Therefore, past approaches, such as the EM
the EM family of mapping algorithms [15, 18].
algorithm presented in [15, 18], are off-line algorithms that
may sometimes take multiple hours for computing the most 2.3 Incremental Mapping Using Posteriors
likely map.
Following the literature on probabilistic mapping with
2.2 Conventional Incremental Mapping EM [15, 18] and the literature on Markov localization [16,
3], our approach computes the full posterior over robot
Before describing our approach for incremental likelihood
poses, instead of the maximum likelihood pose only (as
maximization, let us first consider a baseline approach,
given in (6)). The posterior is a probability distribution over
which is extremely popular in the literature. This approach
poses conditioned on past sensor data:
is incremental, is attacks the concurrent localization and
mapping problem, but it is unable to revise the map back- Bel(st ) = P (st | dt , mt−1 ) (8)
wards the time and therefore is unable to handle cyclic en-
vironments (and close a loop). Nevertheless, it is used as a The short notation Bel indicates that the posterior is the
subcomponent in our algorithm which follows. robot’s subjective belief as to where it might be. In past
 mismatch -

6
path
robot -

Figure 5: Sample-based approximation for the posterior Bel(s). Here

each density is represented by a set of samples, weighted by numerical
importance factors. Particle filters are used to generate the sample sets.

= η P (ot | st , mt−1 )
Figure 4: Result obtained using the most simple incremental approach, Z
which is common in the literature. This approach fails to close the cycle
and leads to inconsistent maps. P (st | at−1 , st−1 ) Bel(st−1 ) dst−1
work, various researchers have found that algorithms that
After computing the posterior, the new map is generated by
maintain a posterior estimation—instead of a single max-
maximizing a slightly different expression for pose estima-
imum likelihood guess—are typically more robust and
tion (c.f., ŝt in Equation (6)):
hence lead to more scalable solutions.
The algorithm for computing the posterior is identical to s̄t = argmax Bel(st ) (11)
the Markov localization algorithm [16]. It is incremental. st
Initially, at time t = 0, the belief Bel(s0 ) is centered on
which leads to the new map
a (fictitious) origin of the coordinate system hx = 0, y =
0, θ = 0i. Thus, Bel(s0 ) is initialized by a Dirac distri- mt+1 = mt ∪ {hot , , s̄t i} (12)
bution (point distribution). Suppose at time t we know the
previous belief Bel(st−1 ), which is distribution over poses Just as in (6) and (7), the map is grown by adding a scan
st−1 at time t − 1, and we just executed action at−1 and at location s̄t . However, here we use the entire posterior
observed ot . Then the new belief is obtained through: Bel(st ) for determining the most likely pose, not just the
Bel(st ) (9)most recent sensor scan and its pose (as in (6)). As a re-
Z sult, the increasing diameter of uncertainty is modeled so
= η P (ot | st , mt−1 ) P (st | at−1 , st−1 ) Bel(st−1 ) dst−1that, when closing the loop, the correct uncertainty can be
taken into account: the larger the loop, the wider the margin
where η is (different) normalizer, and mt−1 is the best of uncertainty. This difference is important when mapping
available map. large cyclic environments—where a robot needs to know
Update equation (9) is derived using the common Markov where to search when closing a loop.
localization approach (see also [16, 3]), assuming a static Our approach uses samples to approximate the posterior.
map: Figure 5 shows an example, for a sequence of robot poses
along a U-shaped trajectory. Here each of the sample sets
Bel(st ) = P (st | dt , mt−1 ) is an approximation of densities (of the type shown in Fig-
= P (st | dt−1 , at−1, ot , mt−1 ) ure 2). The idea of using samples goes back to Rubin’s
= η P (ot | st , dt−1 , at−1, mt−1 ) importance sampler [14] and, in the context of temporal
P (st | dt−1 , at−1, mt−1 ) posterior estimation is known as particle filters [12]. It has,
with great success, been applied for tracking in computer
= η P (ot | st , mt−1 ) (10) vision [7] and mobile robot localization [2, 3]. As argued
Z
P (st | dt−1, at−1 , st−1 , mt−1 ) in the statistical literature, this representation can approx-
imate almost arbitrary posteriors at a convergence rate of
P (st−1 | dt−1, at−1 , mt−1 ) dst−1 √1 [17]. It is convenient for robotics, since it is easy to
N
  robot and samples




robot and
samples




robot
and samples
(a) (b) (c)
Figure 6: Incremental algorithm for concurrent mapping and localization. The dots, centered around the robot, indicate the posterior belief which grows
over time (a and b). When the cycle is closed as in (c), the posterior becomes small again.

implement, and both more efficient and more general than yield a maximum likelihood match; however, it places
most alternatives [3]. the intermediate poses in a good starting position for sub-
The sample-based representation directly facilitates the op- sequent gradient descent search.
timization of (11) using gradient descent. Our approach
performs gradient descent using each sample as a start- 3. Finally, gradient descent search is applied iteratively for
ing point, then computes the goodness of the result using all poses inside the loop, until the map is maximally con-
the obvious likelihood function. If the samples are spaced sistent (maximizes likelihood) under this new constraint
reasonably densely (which is easily done with only a few arising from the cycle.
dozen samples), one can guarantee that the global maxi-
mum of the likelihood function can be found. This dif-
fers from the simple-minded approach above, where only a These three steps implement an efficient approximation to
single starting pose is used for hill-climbing search, and the maximum likelihood estimator for the entire loop. Our
which hence might fail to produce the global maximum approach has been found to be extremely robust in prac-
(and hence the best map). tice (we never obtained a single wrong result) and also ex-
tremely fast (the entire maximization can be carried out
2.4 Backwards Correction between two sensor measurements for all experiments re-
ported in this paper).
As argued above, when closing cycles it is imperative that
maps are adjusted backwards in time. The amount of back-
wards correction is given by the difference (denoted ∆st ): 2.5 Multi-Robot Mapping

∆st = s̄t − ŝt (13) The posterior estimation component of our approach makes
it straightforward to generate maps with multiple robots.
where s̄t is computed according to Equation (11) and ŝt is Here we assume that the initial pose of the robots relative
obtained through Equation (6). This expression is the dif- to each other is unknown; however, we make the important
ference between the incremental best guess (c.f., our base- restrictive assumption that each robot starts within the map
line approach) and the best guess using the full posterior. of a specific robot, called the team leader. To generate a
If ∆st = 0, which is typically the case when not closing single, unified map, each robot must localize itself in the
a loop, no backwards correction has to take place. When map of the team leader.
∆st 6= 0, however, a shift occurred due to reconnection The insight for multi-robot mapping is closely tight to the
with a previously mapped area, and poses have to be revised notion of posterior estimation. As the reader might have
backwards in time. noticed, our posterior computation is equivalent to Monte
Our approach does this in three steps: Carlo localization [2, 3], a version of Markov localization
capable of performing global localization. Thus, to local-
1. First, the size of the loop is determined by determining
ize a robot in the map of the team leader, its initial samples
the scan in the map which led to the adjustment (this is a
are distributed uniformly across the team leader’s map, as
trivial side-result in the posterior computation).
shown in Figure 7a. The posterior estimation then quickly
2. Second, the error ∆st is distributed proportionally localizes the robot (see [2, 3]), which then enables both
among all poses in the loop. This computation does not robots to build a single, uniform map.
  team leader  team leader  team leader

robot









robot robot
(a) (b) (c)
Figure 7: A second robot localizes itself in the map of the first, then contributes to building a single unified map. In (a), the initial uncertainty of the relative
pose is expressed by a uniform sample in the existing map. The robot on the left found its pose in (b), and then maintains a sense of location in (c).

2.6 3D Mapping
Finally, a key goal of this research is to generate accu-
rate 3D maps. With accurate localization in place, this ex-
tension is obtained using a robot equipped with two laser
range finder, such as the one shown in Figure 1b. Here the
forward-looking laser is used for concurrent mapping and
localization in 2D, and the upward-pointed laser is used to
build a 3D map of the environment.
At first glance, one might simply generate 3D maps by
connecting nearby laser measurements into small polygons.
Figure 8: Mapping without odometry. Left: Raw data, right: map, gener-
However, this approach has two disadvantages: First, it is ated on-line in real-time.
prone to noise, and second, the number of measurements
are excessively large, and the resulting maps are therefore all scans, however, were used in localization. This kept
overly complex. the complexity of maps manageable (a few hundred scans,
Our approach filters our outliers based on distance; if two instead of several thousand). Also, to make the mapping
measurements are further than a factor 2 apart from the ex- problem more challenging, we occasionally introduced ran-
pected measurement under the robot motion (and assum- dom error into the odometry (30 degrees or 1 meter shifts).
ing the robot faces a straight wall), this measurement does Figure 6 shows results obtained using the same data set as
not become part of a polygone. We also apply a sim- in Figure 4. Here the robot traverses the cycle, but it also
plification algorithm [4, 5], previously developed to sim- keeps track of its posterior belief Bel(s) represented by
plify polygonal models for real-time rendering in computer samples, as shown by the dots centered around the maxi-
graphics.1 In a nutshell, this approach iteratively simplifies mum likelihood pose in Figure 6. When the cycle is closed
multi-polygon surface models by fusing polygons that look (Figure 6b), the robot’s error is significant; however, the
similar when rendered. The result is a model with much “true” pose is well within its posterior at this time. Our ap-
reduced complexity, which nevertheless is similarly accu- proach quickly identifies the true pose, corrects past beliefs,
rate and looks about as good as the original when rendered. and reduces the robot’s uncertainty accordingly. The final
The simplification uses only a small fraction of the avail- map is shown in Figure 6c. As can be seen there, the map
able time, hence is easily applied in real-time. is highly accurate and the error in the cycle has been elim-
inated. All these results have been obtained in real-time on
a low-end PC.
3 Results
3.2 Mapping Without Odometry
3.1 Mapping A Cycle
To test the robustness of the approach, we attempted to
In our experiments, scans were only appended to the map
build the same map but in the absence of odometry data.
when the robot moved a presprecified distance (2 meters);
The raw data, stripped of the odometry information, is
1 We gratefully acknowledge Michael Garland’s assistance in using the shown in Figure 8a. Obviously, these data are difficult to
software. interpret (we are not aware of an algorithm for mapping
Figure 9: Autonomous exploration and mapping using the urban robot:
Raw data and final map, generated in teal-time during exploration.

that works well without odometry information). Figure 8b Figure 10: 3D Map.
shows the resulting map. This map has been generated us-
ing identical software settings. When traversing the cycle, situation after a few more seconds, Here the second robot
this map is less accurate than the one generated with odom- has progressed through the map of the team leader. It still
etry data. However, when closing the cycle, these errors are knows its position with high accuracy.
identified and eliminated, and the final result is optically
equivalent to the one with odometry. The reader should no- 3.5 3D Mapping
tice, however, that the odometry-free results are only pos- Results for 3D mapping are shown in Figures 10 and 11.
sible because the environment possess sufficient variation. Figure 10 shows a short corridor segment. The free-flying
In a long, featureless corridor, our approach would clearly surfaces are ceiling regions inside offices, which the robot’s
fail in the absence of odometry data. Nevertheless, these lasers sensed while moving through the corridor.
results illustrate the robustness of our approach. Figure 11 shows a sequence of rendered views of a larger
(cyclic) map, which is approximately 60 meters long. The
3.3 Autonomous Exploration
rendering algorithm is a standard virtual reality tool (VR-
Figure 9 shows results of an autonomously exploring robot, web), which enables the user to remotely inspect the build-
obtained at a recent DARPA demonstration. These results ing by “flying through the map.” The top rowin Figure 11
were obtained using the Urban Robot shown in Figure 1c. has been generated from raw laser data; this model contains
This robot is able to traverse extremely rugged terrain. 82,899 polygons. The bottom row is the simplified polyg-
However, its skid-steering mechanism using tracks is ex- onal model, which contains only 8,289 polygons. The ap-
tremely erroneous, and odometry errors are often as large pearance of both is similar; however, rendering the more
as 100%, depending on the conditions of the floor. compact one is an order of magnitude faster.
Figure 9 shows the raw data (left diagram) and the map
(right diagram) along with the robot’s trajectory. This is 4 Discussion
the worst map ever generates using our approach: some of
the walls are not aligned perfectly, but instead are rotated This paper presented a new, online method for robust map-
by approximately 2 degrees. However, given the extremely ping and localization in indoor environments. The ap-
poor odometry of the robot, and the fact that our approach proach combines ideas from incremental mapping (maxi-
does not resort to assumptions like recto-orthogonal walls, mum likelihood, incremental map construction) with ideas
these results are actually surprisingly accurate. The map of more powerful, non-incremental approaches (posterior
is clearly sufficient for navigation. We suspect if the envi- estimation, backwards correction). The result is a fast and
ronment possessed a loop, the final result would be more robust algorithm for real-time mapping of indoor environ-
accurate. ments, which extends to multi-robot mapping and mapping
in 3D. A fast algorithm was employed to generate compact
3.4 Multi-Robot Mapping 3D models of indoor environments.
Figure 7 illustrates our approach to multi-robot mapping. Experimental results illustrated that large-scale environ-
Here a second robot localizes itself in the map built by ments can be mapped in real-time. The resulting maps
the team leader (left diagram), as explained above. After were highly accurate. We also demonstrated that our ap-
a short motion segment, the posterior is focused on a single proach can generate 3D maps, and it can fuse information
location (center diagram) and the incoming sensor data is collected though multiple robot platforms.
now used to further the map. The right diagram shows the When compared to EM, the ability to generate maps in real
 Figure 11: Views of the 3D map, for the high-res model (top row) and the lower resolution model (bottom row).

time comes at a price of increased brittleness. EM is a [4] M. Garland and P. Heckbert. Surface simplification using quadric
principled approach to finding the best map, which simul- error metrics. In SIGGRAPH-97.
[5] M. Garland and P. Heckbert. Simplifying surfaces with color and
taneously revises beliefs arbitrarily far in the past—which texture using quadric error metrics. In IEEE Visualization-98.
makes it necessarily inapplicable in real-time. However, [6] J.-S. Gutmann and C. Schlegel. Amos: Comparison of scan match-
our approach inherits some of the power of EM by us- ing approaches for self-localization in indoor environments. In
ing posterior estimations and a fast mechanisms for back- EUROMICRO-96.
[7] M. Isard and A. Blake. Condensation: conditional density propaga-
wards revision, specifically tuned for mapping cyclic en- tion for visual tracking. International Journal of Computer Vision,
vironments. As a result, our approach can handle a large 1998.
range of environments in real-time. [8] J.J. Leonard, H.F. Durrant-Whyte, and I.J. Cox. Dynamic map
building for an autonomous mobile robot. International Journal of
Nevertheless, our approach surpasses previous incremental Robotics Research, 11(4), 1992.
approaches in robustness, specifically in environments with [9] F. Lu and E. Milios. Robot pose estimation in unknown envi-
cycles. Our results make us confident that the approach is ronments by matching 2d range scans. Journal of Intelligent and
very robust to errors, in particular odometry errors. Robotic Systems, 1998.
[10] H. P. Moravec and A. Elfes. High resolution maps from wide angle
sonar. In ICRA-85..
Acknowledgments [11] H.P. Moravec and M.C. Martin. Robot navigation by 3D spatial
evidence grids. Internal Report, CMU, 1994.
We thank Michael Garland for his assistance with the polygon fusing soft-
[12] M. Pitt and N. Shephard. Filtering via simulation: auxiliary particle
ware, Todd Pack and RWI/ISR for their superb support with the robot
filter. Journal of the American Statistical Association, 1999.
hardware, and the members of CMU’s Robot Learning Lab for many fruit-
ful discussions. The idea to build 3D maps was brought to our attention [13] W.D. Rencken. Concurrent localisation and map building for mobile
by our DARPA-PM LTC John Blitch, which we gratefully acknowledge. robots using ultrasonic sensors. In IROS-93.
[14] D.B. Rubin. Using the SIR algorithm to simulate posterior distribu-
This research is sponsored in part by DARPA via TACOM (contract num- tions. In Bayesian Statistics 3, 1988.
ber DAAE07-98-C-L032) and Rome Labs (contract number F30602-98- [15] H. Shatkay. Learning Models for Robot Navigation. PhD thesis,
2-0137), and by the National Science Foundation (regular grant number CSD, Brown University, 1998.
IIS-9877033 and CAREER grant number IIS-9876136), which is grate- [16] R. Simmons and S. Koenig. Probabilistic robot navigation in par-
fully acknowledged. tially observable environments. In IJCAI-95.
[17] M.A. Tanner. Tools for Statistical Inference. Springer, 1993.
References [18] S. Thrun, D. Fox, and W. Burgard. A probabilistic approach to con-
current mapping and localization for mobile robots. Machine Learn-
[1] J. Borenstein, B. Everett, and L. Feng. Navigating Mobile Robots: ing, 31, 1998.
Systems and Techniques. A. K. Peters, 1996. [19] B. Yamauchi and R. Beer. Spatial learning for navigation in dynamic
[2] F. Dellaert, W. Burgard, D. Fox, and S. Thrun. Using the condensa- environments. IEEE Transactions on Systems, Man, and Cybernet-
tion algorithm for robust, vision-based mobile robot localization. In ics - Part B: Cybernetics, 1996.
CVPR-99. [20] B. Yamauchi, P. Langley, A.C. Schultz, J. Grefenstette, and
[3] D. Fox, W. Burgard, F. Dellaert, and S. Thrun. Monte carlo localiza- W. Adams. Magellan: An integrated adaptive architecture for mo-
tion: Efficient position estimation for mobile robots. In AAAI-99. bile robots. TR 98-2, ISLE, Palo Alto, 1998.