UAI2002 
THRUN 
511 
Particle Filters in Robotics 
Sebastian Thrun 
Computer Science Department 
Carnegie Mellon University 
Pittsburgh, PA 15213 
http://www.cs.cmu.edu/othrun 
Abstract 
In recent years, particle filters have solved several hard 
perceptual problems in robotics. Early successes of 
particle filters were limited to low-dimensional esti­
mation problems, such as the problem of robot lo­
calization in environments with known maps. More 
recently, researchers have begun exploiting structural 
properties of robotic domains that have led to success­
ful particle filter applications in spaces with as many 
as I 00,000 dimensions. The fact that every model-no 
mater how detailed-fails to capture the full complex­
ity of even the most simple robotic environments has 
lead to specific tricks and techniques essential for the 
success of particle filters in robotic domains. This arti­
cle surveys some of these recent innovations, and pro­
vides pointers to in-depth articles on the use of particle 
filters in robotics. 
1 
INTRODUCTION 
One of the key developments in robotics has been the adop­
tion of probabilistic techniques. In the 1970s, the predomi­
nant paradigm in robotics was model-based. Most research 
at that time focused on planning and control problems un­
der the assumption of fully modeled, deterministic robot 
and robot environments. This changed radically in the mid-
1980s, when the paradigm shifted towards reactive tech­
niques. Approaches such as Brooks's behavior-based ar­
chitecture generated control directly in response to sensor 
measurements [ 4]. Rejections of models quickly became 
typical for this approach. 
Reactive techniques were ar­
guable as limited as model-based ones, in that they replaced 
the unrealistic assumption of perfect models by an equally 
unrealistic one of perfect perception. Since the mid-1990s, 
robotics has shifted its focused towards techniques that uti­
lize imperfect models and that incorporate imperfect sensor 
data. An important paradigm since the mid-1990s-whose 
origin can easily be traced back to the 1960s-is that of 
probabilistic robotics. Probabilistic robotics integrates im­
perfect models and and imperfect sensors through proba-
bilistic laws, such as Bayes rule. 
Many recently fielded 
state-of-the-art robotic systems employ probabilistic tech­
niques for perception [12, 46, 52]; some go even as far as 
using probabilistic techniques at all levels of perception and 
decision making [39]. 
This article focuses on particle filters and their role in 
robotics. Particle filters [9, 30, 40] comprise a broad fam­
ily of sequential Monte Carlo algorithms for approximate 
inference in partially observable Markov chains (see [9] 
for an excellent overview on particle filters and applica­
tions). In robotics, early successes of particle filter imple­
mentations can be found in the area of robot localization, 
in which a robot's pose has to be recovered from sensor 
data [51]. Particle filters were able to solve two important, 
previously unsolved problems known as the global local­
ization [2] and the kidnapped robot [ 14] problems, in which 
a robot has to recover its pose under global uncertainty. 
These advances have led to a critical increase in the robust­
ness of mobile robots, and the localization problem with a 
given map is now widely considered to be solved. More re­
cently, particle filters have been at the core of solutions to 
much higher dimensional robot problems. Prominent ex­
amples include the simultaneous localization and mapping 
problem [8, 27, 36, 45], which phrased as a state estima­
tion problem involves a variable number of dimensions. A 
recent particle-filter algorithm known as FastSLAM [34] 
has been demonstrated to solve problems with more than 
I 00,000 dimensions in real-time. Similar techniques have 
been developed for robustly tracking other moving entities, 
such as people in the proximity of a robot [35, 44]. 
However, the application of particle filters to robotics prob­
lems is not without caveats. 
A range of problems arise 
from the fact that no matter how detailed the probabilistic 
model-it will still be wrong, and in particular make false 
independence assumptions. In robotics, all models lack im­
portant state variables that systematically affect sensor and 
actuator noise. Probabilistic inference if further compli­
cated by the fact that robot systems must make decisions 
in real-time. This prohibits, for example, the use of vanilla 
(exponential-time) particle filters in many perceptual prob­
lems. 
512 
THRUN 
UAI2002 
(a)r--------, 
(b) 
Robot polition 
.• 
Robot position 
>-'-== ---
'--""' -·-· ' -=·.-
--
(c)r--------, 
•, Robot position 
Figure 1: Monte Carlo localization, a particle filter algorithm 
for state-of-the-art mobile robot localization. (a) Global uncer­
tainty, (b) approximately bimodal uncertainty after navigating in 
the (symmetric) corridor, and (c) unimodal uncertainty after en­
tering a uniquely-looking office. 
This article surveys some of the recent developments, and 
points out some of the opportunities and pitfalls specific to 
robotic problem domains. 
2 
PARTICLE FILTERS 
Particle filters are approximate techniques for calculat­
ing posteriors in partially observable controllable Markov 
chains with discrete time. Suppose the state of the Markov 
chain at time t is given by Xt. Furthermore, the state Xt 
depends on the previous state Xt-! according to the prob­
abilistic law p(xt I Ut, Xt_1), where Ut is the control as­
serted in the time interval ( t- 1; t]. The state in the Markov 
chain is not observable. Instead, one can measure Zt, which 
Figure 2: Particle filters have been used successfully for on-board 
localization of soccer-playing Aibo robots with as few as 50 par­
ticles [26]. 
is a stochastic projection of the true state Xt generated via 
the probabilistic law p(zt I Xt). Furthermore, the initial 
state Xo is distributed according to some distribution p( x0). 
In robotics, p(xt I Ut, Xt-1) is usually referred to as ac­
tuation or motion model, and p(zt I Xt) as measurement 
model. They as usually highly geometric and generalize 
classical robotics notions such as kinematics and dynamics 
by adding non-deterministic noise. 
The classical problem in partially observable Markov 
chains is to recover a posterior distribution over the state 
Xt at any tinie t, from all available sensor measurements 
zt = zo, ... , Zt and controls ut = uo, ... , Ut. A solution 
to this problem is given by Bayes filters [20], which com­
pute this posterior recursively: 
p(xt I zt,ut) 
= 
canst. 
· p(ztiXt) j p(xtlut,Xt-I) 
p(xt-IIzt-!, ut-I) dxt-! 
(I) 
under the initial conditionp(xo I z0,u0) =p(xo). If states, 
controls, and measurements are all discrete, the Markov 
chain is equivalent to hidden Markov models (HMM) [41] 
and (I) can be implemented exactly. Representing the pos­
terior takes space exponential in the number of state fea­
tures, though more efficient approximations exist that can 
exploit conditional independences that might exist in the 
model of the Markov chain [3]. 
In robotics, particle filters are usually applied in continu­
ous state spaces. For continuous state spaces, closed form 
solutions for calculating (1) are only known for highly spe­
cialized cases. If p(x0) is Gaussian and p(xt I Ut, Xt-I) 
and p( Zt I Xt) are linear in its arguments with added in­
dependent Gaussian noise, (I) is equivalent to the Kalman 
filter [23, 32]. Kalman filters require O(d3) time ford­
dimensional state spaces, although in many robotics prob­
lems the locality of sensor data allows for O(d2) imple­
mentations. A common approximation in non-linear non­
Gaussian systems is to linearize the actuation and measure­
ments models. If the linearization is obtained via a first­
order Taylor series expansion, the result is known as ex­
tended Kalman filter, or EKF [32]. Unscented filters [21] 
obtain often a better linear model through (non-random) 
sampling. However, all these techniques are confined to 
cases where the Gaussian-linear assumption is a suitable 
approximation. 
Particle filters address the more general case of (nearly) un­
constrained Markov chains. The basic idea is to approxi-
UA12002 
THRUN 
513 
mate the posterior of a set of sample states { xlil}, or par­
ticles. Here each xliJ is a concrete state sample of index i, 
where is ranges from 1 to M, the size of the particle fil­
ter. The most basic version of particle filters is given by the 
following algorithm. 
• Initialization: At time t = 0, draw M particles accord­
ing to p(x0). Call this set of particles Xo. 
• Recursion: At time t > 0, generate a particle xlil for 
each particle xl1 E Xt-1 by drawing from the actua­
tion model p( Xt I Ut, x\id 1). Call the resulting set X t. 
Subsequently, draw M particles from Xt, so that each 
xli] E Xt is drawn (with replacement) with a probabil­
ity proportional to p(zt I xlil ). Call the resulting set of 
particles Xt. 
In the limit as M _, 
oo, this recursive procedure leads 
to particle sets Xt that converge uniformly to the desired 
posterior p(xt I zt, ut), under some mild assumptions on 
the nature of the Markov chain. 
Particle filters are attractive to roboticists for more than 
one reason. First and foremost, they can be applied to al­
most any probabilistic robot model that can be formulated 
as a Markov chain. Furthermore, particle filters are any­
time [6, 53], that is, they do not require a fixed computa­
tion time; instead, their accuracy increases with the avail­
able computational resources. This makes them attractive 
to roboticists, who often face hard real-time constraints 
that have to be met using hard-to-control computer hard­
ware. Finally, they are relatively easy to implement. The 
implementer does not have to linearize non-linear models, 
and worry about closed-form solutions of the conditional 
p(xt I Ut, Xt-1), as would be the case in Kalman filters, 
for example. The main criticism of particle filter has been 
that in general, populating a d-dimensional space requires 
exponentially many particles in d. Most successful applica­
tions have therefore been confined to low-dimensional state 
spaces. The utilization of structure (e.g., conditional in de­
pendences ), present in many robotics problems, has only 
recently led to applications in higher dimensional spaces. 
3 
PARTICLE FILTERS IN LOW 
DIMENSIONAL SPACES 
In robotics, the 'classical' successful example of particle 
filters is mobile robot localization. Mobile robot local­
ization addresses the problem of estimation of a mobile 
robot's pose relative to a given map from sensor measure­
ments and controls. The pose is typically specified by a 
two-dimensional Cartesian coordinate and the robot's rota­
tional heading direction. The problem is known as posi­
tion tracking if the error can be guaranteed to be small at 
all times [2]. More general is the tile global localization 
problem, which is the problem of localizing a robot under 
4500 
4000 
3500 
"E 3000 
.2. 2500 
1l 
c 2000 
.!!1 
< 
i5 1500 
1000 
500 
500 1000 , 500 2000 2500 3000 3500 4000 
Time [sec] 
Figure 3: MCL with the standard proposal distribution (dashed 
curve) compared to MCL with a hybrid mixture distribution (solid 
line) [51]. Shown here is the error for a 4,000-second episode of 
camera-based MCL of a museum tour-guide robot operating in 
Smithsonian museum [50]. 
global uncertainty. The most difficult variant of the local­
ization, however, is the kidnapped robot problem [14], in 
which a well-localized robot is tele-ported to some other 
location without being told. This problem was reported, 
for example, in the context of the Robocup soccer compe­
tition [25], in which judges picked up robots at random oc­
casions and placed them somewhere else [26]. Other local­
ization problems involve multiple robots that can observe 
each other [ 15]. 
Figure I illustrates particle filters in the context of global 
localization of a robot in a known environment. Shown 
there is a progression of tllree situations, in which a number 
of particles approximate tile posterior (I) at different stages 
of robot operation. Each particle is a sample of a three­
dimensional pose variable, comprising the robot's Carte­
sian coordinates and its orientation relative to the map. The 
progression of snapshots in Figure 1 illustrate the develop­
ment of the particle filter approximation over time, from 
global uncertainty to a well-localized robot. 
In the context of localization, particle filters are commonly 
known as Monte Carlo localization (MCL) [7, 51]. MCL's 
original development was motivated by tile condensation 
algorithm [19], a particle filter that enjoyed great popu­
larity in computer vision applications. In most variants 
of the mobile localization problem, particle filters have 
been consistently found to outperform alternative tech­
niques, including parametric probabilistic techniques such 
as the Kalman filter and more traditional techniques (see 
e.g., [18, 51]). MCL has been implemented with as few 
as 50 samples [26] on robots with extremely limited pro­
cessing and highly inaccurate actuation, such as the soccer­
playing AIBO robotic shown in Figure 2. 
Recent research has led to a range of adaptations of the ba­
sic particle filter. Generating particles using the next state 
probability p(xt I Ut, Xt-1) alone has been recognized as 
insufficient under a range of conditions, such as in the kid­
napped robot problem [26] or in situations where the sensor 
514 
THRUN 
UAI2002 
accuracy is high in comparison to the control accuracy (51]. 
Common extensions involve hybrid sampling techniques, 
in which a subset of all samples is generated according to 
measurement model. Figure 3 shows a comparison of plain 
MCL versus an extended version using such a hybrid sam­
pling scheme, obtained for data collected by a deployed 
mobile tour-guide robot. Other extensions regard the exis­
tence of unmodeled environmental state-which is a given 
in real-world robotics. 
A common approach inflates the 
uncertainty in the Markov chain model artificially, to ac­
commodate systematic noise [16]. The same problem has 
also given rise to the development of probabilistic filters 
for pre-processing sensor data [ 16]. An example of the lat­
ter includes filters for range sensors that remove measure­
ments corrupted by people (5]. MCL has also been made 
temporally more persistent by clustering particles and us­
ing different resampling rates for different clusters-a tech­
nique that empirically increases the robustness to errors in 
the map used for localization [33]. Stratified sampling tech­
niques have been exploited to increase the variance of the 
resampling step [9]. Extensions to multi-robot localization 
problems are reported in [15]. 
4 
PARTICLE FILTERS IN HIGH 
DIMENSIONAL SPACES 
An often criticized limitation of plain particle filters is their 
poor performance in higher dimensional spaces. This is 
because the number of particles needed to populate a state 
space scales exponentially with the dimension of the state 
space, not unlike the scaling limitations of vanilla HMMs. 
However, many problems in robotics possess structure that 
can be exploited to develop more efficient particle filters. 
One such problem is the simultaneous localization and 
mapping problem, or SLAM [8, 27, 36, 45]; see [ 48] for an 
overview. SLAM addresses the problem of building a map 
of the environment with a moving robot. The SLAM prob­
lem is challenging because errors in the robot's localization 
induce systematic errors in the localization of environmen­
tal features in the map. The absence of an initial map in the 
SLAM problem makes it impossible to localize the robot 
during mapping using algorithms like MCL. Furthermore, 
the robot faces a challenging data association problem of 
determining whether two environment features, observed 
at different point in time, correspond to the same physical 
feature in the environment. To make matters worse, the 
space of all maps often comprises hundreds of thousand of 
dimensions. In the beginning of mapping the size of the 
state space is usually unknown, so SLAM algorithms have 
to estimate the dimensionality of the problem as well. On 
top of all this, most applications of SLAM require real-time 
processing. 
Until recently, the predominant approach for SLAM that 
meets most of the requirements above-with the exception 
of a sound solution of the data association problem-was 
Figure 4: The SLAM problem as a 'dynamic Bayes network:' 
The robot moves from pose x1 through a sequence of controls, 
u1, u2, ... , u,. As it moves, it observes nearby features. At time 
t 
= 1, it observes feature llt out of two features, {lit, 112}. The 
measurement is denoted z1 (range and bearing). At time t = 1, 
it observes the other feature, 112, and at time t = 3, it observes 111 
again. The SLAM problem is concerned with estimating the loca­
tions of the features and the robot's path from the controls u and 
the measurements z. The gray shading illustrates a conditional 
independence relation exploited by the FastSLAM algorithm. 
based on extended Kalman filters, or EKFs [8, 36, 45]. 
As noted above, EKFs implement Equation (1) using lin­
earized actuation and measurement models, with indepen­
dent Gaussian noise. 
In their implementation, they cru­
cially exploit that the environment is static. 
The result­
ing estimation problem is then described as a problem of 
jointly estimating a time-variant robot pose x, and the time­
invariant location of N features, denoted Yl through YN: 
p(x,, Yl, ... , YN I z', u') 
= 
const. 
· p(z,lx,) j p(x,lut, Xt-l) 
p(Xt-l, Y1, · · · ,  YNiz'-1, u'-1) dXt-1 
(2) 
Notice that this integration involves only the robot pose x,, 
and not the variables Y1 ... YN. For the linear-Gaussian 
model in EKFs, this integral is tractable [8, 45]. The EKF 
solution to the SLAM problem, however, suffers three key 
limitations: 
I. First, the complexity of each update step is in 0( N2), 
even in the absence of a data association problem. This 
limitation poses important scaling limitations. 
EKF 
algorithms can rarely manage more than a thousand 
features in realistic time. 
This limitation has spurred 
a flurry of research on hierarchical map representa­
tions, where maps are decomposed recursively into local 
submaps (17, 28]. Most of these approaches are still in 
O(N2) but with a constant factor that is orders of mag­
nitude smaller than that of the monolithic EKF solution. 
2. Second, EKFs cannot incorporate negative information, 
which is, they cannot use the fact that a robot failed 
to see a feature even when expected. 
The reason for 
this inability is that negative measurements give rise to 
non-Gaussian posteriors, which cannot be represented by 
EKFs. 
UAI2002 
THRUN 
515 
FutSJam 
l!Xl 
150 . 
F 100 -
i 
 50 
0 . 
·'"J;o!::---.:O:,oo;;---.,.,*""----;;
, ------;;o!;-----;;:,oo;;------;,;o 
East (melers) 
Figure 5: FastSLAM with real-world data: Shown here is a map of an outdoor environment (Victoria Park in Sydney), along with GPS 
information displayed here only for evaluating the accuracy of the resulting map. The resulting map error is extremely small, comparable 
in magnitude to the EKF solution. These results were obtained Juan Nieto, Eduardo Nebot, and Jose Guivant from the Australian Center 
of Field Robotics in Sydney, and are reprinted here with permission. 
3. Third, EKFs provide no sound solution to the data asso­
ciation problem. It is common practice to use a maxi­
mum likelihood estimator for data association [8], using 
thresholding to detect (and reject) outliers. New environ­
mental features are first placed on a provisional list, to 
reduce the odds of mistaking random noise for new, pre­
viously unseen features in the environment. However, as 
generally acknowledged in the literature [8], false data 
associations often lead to catastrophic failures. 
The first and second of these limitations, and possibly the 
third, have recently been overcome by particle filters. Re­
cent research [10, 34, 35, 37] has led to a family of so­
called Rao-Blackwellized particle filters that, in the con­
text of SLAM, lead to solutions that are significantly more 
efficient than the EKF. These particle filters require time 
O(M log N) instead of O(N2), where M is the number 
of particles as above. Empirical evidence suggest that M 
may be a constant in situations with bounded uncertainty­
which includes all SLAM problems that can be solved 
via EKFs [34]. They can also incorporate negative infor­
mation, hence make better use of measurement data than 
EKFs. 
Finally, highly preliminary experimental results 
suggest that particle filters provide a better solution to the 
data association problem than currently available with the 
EKF-although at present, this claim is not yet backed up 
by sufficient experimental evidence. 
To understand particle filter solutions to the SLAM prob­
lem, it is helpful to analyze the structure of the SLAM 
problem. Assume, for a moment, that there is no data 
association problem, that is, the robot can uniquely iden­
tify individual features detected by its sensors. In this case, 
the SLAM problem is characterized by an important inde­
pendence property [37], which is presently not exploited in 
EKF solutions. In particular, knowledge of the path of the 
robot renders the individual feature locations conditionally 
independent: 
N 
p(y1, · · ·, YN I xl, Z1) 
= IT P(Yn I x1, z1) 
(3) 
n=l 
Figure 4 illustrates this independence, as explained in the 
caption to this figure. This important conditional indepen­
dence property of the SLAM problem leads to the formu­
lation of a more efficient version of Equation (2), one that 
estimates a posterior over robot paths x1 (instead of poses 
x1) along with the feature locations Yn: 
p(xl, Yl, ... , YN I z\ u1) 
= p(x1 I zl, u1) P(Yl, ... , YN I xt, z1) 
N 
p(x1 I z1, u1) IT p(yn I xt, z1) 
(4) 
n=l 
A key property of particle filter is that each particle can be 
interpreted as a posterior over entire paths, and not just the 
present pose [9, 34]-a property that is not shared by EKFs. 
Thus, it is natural to implement the posterior over paths 
p(x1 I z1, u1) in (4) by particle filters. The resulting fea­
ture estimators P(Yn I x1, z1) are conditioned on individual 
particles representing path posteriors p(x1 I z1, u1). How­
ever, since feature posteriors are conditionally independent 
given the path xt, as stated in (3), the joint posterior over 
the features can be decomposed into separate estimators for 
each feature p(yn I x1, z1), for each n = 1, ... , N. The 
516 
THRUN 
UA12002 
(a) 
(b) 
(c) 
(d) 
(e) 
(f) 
Figure 6: Lazy version ofFastSLAM with unknown data association and point estimators (no variance) for environmental features: The 
top row (a) through (c) illustrates the result of mapping a cycle using conventional techniques. The bottom row (d) through (f) uses 
particle filters for estimating robot poses, hence is able to recover from large localization error that frequently occur when traversing 
cyclic environments. This real-time particle filter algorithm has proven to be highly robust in many environments. 
resulting filter maintains M particles. Each particle con­
tains a concrete robot path xt, and a set of N independent 
estimates of the locations of individual features in the envi­
ronment. 
In the FastSLAM algorithm [34], these feature posteriors 
p(yn I xt, zt) are implemented by EKFs, one for each fea­
ture. Each of these posteriors is of fixed dimension (e.g., 2 
for landmarks in a plane). The resulting filter, thus, com­
bines particle filters and Kalman filters: Posteriors over 
robot paths are represented by particle filters, very much 
as in the MCL algorithm described in the previous sec­
tion. Each particle is then linked to N Kalman filters, one 
for each feature in the map. Each of those particle filters 
corresponds to one feature, hence its dimension is inde­
pendent of N. The resulting particle filter is called Rao­
Blackwellized filter since the posterior for certain dimen­
sions (the feature locations) are calculated exactly, whereas 
others (the robot pose) are approximated using particle fil­
ters. 
Updating this Rao-Blackwellized particle filter in the naive 
way requires time O(N M), where M is the number of par­
ticles. Even the naive implementation avoids the quadratic 
complexity of the EKF solution by virtue of the decom­
position in (3), which suggests that individual features can 
be localized independently when conditioned on a concrete 
robot path. The FastSLAM algorithm is even faster. Up­
dates exploit the fact that the robot may only observe a 
finite number of features at any point in time. By repre­
senting feature estimates using tree structures as described 
in [34], the FastSLAM problem can be implemented in 
O(M log N) time. Initial empirical evidence in [34] sug-
gest that under bounded robot pose uncertainty, this ap­
proach scales well even with constantly many particles 
M. This finding suggests that particle filters can ( approxi­
mately) solve the SLAM problem in O(log N) time. 
The use of particle filters opens the door to an improved so­
lution to the data association problem. FastSLAM makes 
it possible to sample over data associations-rather than 
simply assuming that the most likely associations is cor­
rect. Thus, FastSLAM implements a full Bayesian solution 
to the SLAM problem with unknown data association­
something that has previously only been achieved us­
ing a recently developed mixture of Gaussian representa­
tion [II, 31]. FastSLAM can also incorporate negative in­
formation, that is, not seeing a feature that the robot expects 
to see. This is achieved by modifying the importance fac­
tors of individual particles accordingly. 
As reported in [34], the Rao-Blackwellized particle fil­
ter algorithm delivers stat-of-the-art performance in large­
scale SLAM problems, involving up to 100,000 dimen­
sions. Figure 5 shows a typical result of FastSLAM ob­
tained for an outdoor navigation problem. In this experi­
ment, an autonomous land vehicle is used to map the loca­
tion of trees in a public park.1 This specific experiment 
involves several dozen circular features (stems of trees), 
which are detected using a laser range finder mounted on 
an outdoor vehicle. As the figure illustrates, the location 
of the trees and the vehicle is determined with high ac­
curacy, which is comparable to the computationally much 
1 These results were obtained Juan Nieto, Eduardo Nebot, and 
Jose Guivant from the Australian Center of Field Robotics in Syd­
ney, and are reprinted here with permission. 
UAI2002 
THRUN 
517 
Figure 7: Particle filter-based people tracker: This algorithm uses maps to simultaneously localize a moving robot and an unknown 
number of nearby people. This sequence shows the evolution of the conditional particle filter from global uncertainty to successful 
localization and tracking of the robot. 
more cumbersome EKF solution. A second result is shown 
in Figure 6. This algorithm [ 49]-which was originally 
not stated as a version of FastSLAM--can be viewed as a 
lazy FastSLAM implementation where each particle uses 
maximum likelihood data association, and where feature 
locations are calculated in a lazy way, that is, for the most 
likely particle only. It also does not consider feature uncer­
tainty in mapping, and instead memorizes the most likely 
feature location only. However, just like FastSLAM it uses 
particle filters to estimate posteriors over robot paths, and it 
uses those to find the most consistent map. This approach 
has been applied extensively to the problem of mapping in­
door environments from laser range scans, where maps are 
collections of raw point features. It is presently one of the 
most robust real-time algorithms in existence for the indoor 
mapping problem with range finders. 
In a similar vein, particle filters have also been used 
for tracking moving features, not just static ones. Here 
again, the underlying state spaces are high-dimensional, 
and particle filters have generated state-of-the-art results. 
In robotics, a prime example of tracking moving objects 
is the problem of tracking people [35, 44]. This prob­
lem is of great significance to the emerging field of ser­
vice robotics [13, 43]. Service robots are robots designed 
to provide services to individual persons and hence have to 
be aware of where they are. The two dominant approaches 
that track people based on range measurements are both 
based on particle filters. The work by Schulz et a!. [ 44] ex­
ploits a factored particle filter, where features are extracted 
from range measurements and associated with independent 
particle filters using maximum likelihood. The work by 
Montemerlo et a!. [35] uses maps to detect people, in that 
it relies on differences between a previously acquired map 
of the environment and actual range scans, to identify and 
localize people. The map-based people tracking problem 
is similar in nature to the SLAM problem, since it involves 
the simultaneous localization of robots and people. The 
approach in [35] uses particle filters similar to FastSLAM, 
specifically exploiting the conditional independence prop-
erty (3) that also applies to the people localization problem. 
Figure 7 depicts results using this particle filter-based peo­
ple tracker under global initial uncertainty. The approach is 
able to simultaneously localize a robot under global uncer­
tainty in real-time, and at the same time estimate the num­
ber and locations of nearby people. A similar approach for 
tracking the status of doors in mapped environments has 
been proposed in [ 1]. 
5 
DISCUSSION 
This article has described some of the recent successes of 
particle filters in the field of robotics. Traditionally, par­
ticle filters were mostly applied to low-dimensional robot 
localization problems-, where researchers have developed 
a rich repertoire of techniques to cope with the specifics of 
concrete robot environments. Recently, advanced variants 
of particle filters have provided new solutions to challeng­
ing higher-dimensional problems, such as the problem of 
robot mapping and people tracking. These approaches use 
hybrid representations that exploit structure in the underly­
ing problems, expressed by conditional independences. In 
several of such structured robotics domains, particle filters 
are now among the most efficient and scalable solutions in 
existence. 
Despite this progress, there exist plenty opportunities for 
future research. The most important opportunity con­
cerns robot control: All the examples above address only 
the robot perception problem, but in robotics, the key 
problem is one of control: robots ought to do the right 
thing, no matter how their perception is organized. At 
present, relatively little is known about robot control un­
der uncertainty. Recent developments in the field of par­
tially observable Markov decision processes mostly ad­
dress low-dimensional discrete spaces [22], and to the au­
thor's knowledge only a single algorithm exist that has ap­
plied continuous-space particle filters to such control prob­
lems [ 4 7]. This approach, however, is still too inefficient 
518 
THRUN 
UAI 2002 
to be of relevance to robotics. Other discrete-state approx­
imations have been developed [29, 42], yet they have only 
solved isolated navigation problems in mobile robotics. 
More generally, recent research in AI has led to a great 
number of efficient algorithm for probabilistic inference in 
high-dimensional spaces with structure, beginning with the 
seminal work by Pearl [38]. Such techniques offer promis­
ing new solutions to hard robotics problems. The remain­
ing challenge is to further develop them, and adapt them 
to the specific requirements characteristic of robotics do­
mams. 
Acknowledgment 
Much of the material presented here has been developed 
in close collaboration with the following people: Wolfram 
Burgard, Nando de Freitas, Frank Dellaert, Hugh Durrant­
Whyte, Dieter Fox, Jose Guivant, Daphne Koller, Hannes 
Kruppa, Michael Montemerlo, Eduardo Nebot, Juan Nieto, 
Joelle Pineau, Nicholas Roy, and Ben Wegbreit. Their var­
ious contributions are gratefully acknowledged. 
The research reported here is partially sponsored by 
DARPA's TMR Program (contract number DAAE07-98-C­
L032), DARPA's MARS Program, and DARPA's CoABS 
Program (contract number F30602-98-2-0137). It is also 
sponsored by the National Science Foundation (regular 
grant number IIS-9877033 and CAREER grant number 
IIS-9876136), all of which is gratefully acknowledged. 
References 
[I] D. Avots, E. Lim, R. Thibaux, and S. Thrun. A probabilistic technique for 
simultaneous localization and door state estimation with mobile robots in 
dynamic environments. In /ROS-2002. 
[2] J. Borenstein, B. Everett, and L. Feng. Navigating Mobile Robots: Systems 
and Techniques. A. K. Peters, 1996. 
[3] X. Boyen and D. Koller. 
Tractable inference for complex stochastic pro­
cesses. In UAJ-98 
[4] R. A. Brooks. 
A robot that walks; emergent behaviors from a carefully 
evolved network. Neural Computation, 1(2):253, 1989. 
[5] W. Burgard, A.B. Cremers, D. Fox, D. Hiihnel, G. Lakemeyer, D. Schulz, 
W. Steiner, and S. Thrun. 
Experiences with an interactive museum tour­
guide robot Artificia/Intelligence, 114(1-2), 1999. 
[6] T.L. Dean and M. Boddy. An analysis of time-dependent planning. In AAAI-
92. 
[7] F. Dellaert, W. Burgard, D. Fox, and S. Thrun. Using the condensation algo­
rithm for robust, vision-based mobile robot localization. In CVPR-99. 
[8] G. Dissanayake, P. Newman, S. Clark, H.F. Durrant-Whyte, and M. Csorba. 
An experimental and theoretical investigation into simultaneous localisation 
and map building (SLAM). In Lecture Notes in Control and Information 
Sciences: Experimental Robotics VI, 2000. Springer. 
[9] A. Doucet, J.F.G. de Freitas, and N.J. Gordon, editors. Sequential Monte 
Carlo Methods In Practice. Springer, 2001. 
[10] A Doucet, N. de Freitas, K. Murphy, and S. Russell. 
Rao-Blackwellised 
particle filtering for dynamic Bayesian networks. In UAI-00. 
[II] H. Durrant-Whyte, S. Majumder, S. Thrun, M. de Battista, and S. Scheding. 
A Bayesian algorithm for simultaneous localization and map building. In 
ISRR-OI. 
[12] H.F. Durrant-Whyte. Autonomous guided vehicle for cargo handling appli­
cations. International Journal of Robotics Research, 15(5), 1996. 
[13] G. Engelberger. Services. In Handbook of Industrial Robotics, Wiley, 2nd 
edition, 1999. 
[14] S. Engelson and D. McDermott. Error correction in mobile robot map learn­
ing. In /CRA-92. 
{15] D. Fox, W. Burgard, H. Kruppa, and S. Thrun. A probabilistic approach to 
collaborative multi-robot localization. Autonomous Robots, 8(3), 2000. 
[16] D. Fox, W. Burgard, and S. Thrun. Markov localization for mobile robots in 
dynamic environments. Journal of Artijicial lntelligence Research, 11, 1999. 
[17] J. Guivant and E. Nebot. Optimization of the simultaneous localization and 
map building algorithm for real time implementation. IEEE Transactions of 
Robotics and Automation, 2001. 
[18] J.-S. Gutmann, W. Burgard, D. Fox, and K. Konolige. An experimental com­
parison of localization methods. In /ROS-98. 
(19] M. Isard and A. Blake. CONDENSATION: conditional density propagation 
for visual tracking. International Journal of Computer Vision, 29(1), 1998. 
[20] A.M. Jazwinsky. 
Stochastic Processes and Filtering Theory. 
Academic 
Press, 1970. 
[21] S. J. Julier and J. K. Uhlmann. A new extension of the Kalman filter to 
nonlinear systems. In ADSSC-97. 
(22] L.P. Kaelbling, M.L. Littman, and A.R. Cassandra. 
Planning and acting 
in partially observable stochastic domains. Artijicial Intelligence, 101(1-2), 
1998. 
[23] R. E. Kalman. A new approach to linear filtering and prediction problems. 
Trans. ASME, Journal of Basic Engineering, 82, 1960. 
[24] K. K.anazawa, D. Koller, and S.J. Russell. Stochastic simulation algorithms 
for dynamic probabilistic networks. In UA/-95. 
[25] H. Kitano, editor. Proceedings of RoboCup-97: The First Robot World Cup 
Soccer Games and Conferences, Springer, 1998. 
[26] S. Lenser and M. Veloso. Sensor resetting localization for poorly modelled 
mobile robots. In /CRA-00. 
[27] J.J. Leonard, H.F. Durrant-Whyte, and I.J. Cox. Dynamic map building for 
an autonomous mobile robot. International Journal of Robotics Research, 
11(4),1992. 
[28] J.J. Leonard and H.J.S. Feder. A computationally efficient method for large­
scale concurrent mapping and localization. In ISRR-99. 
[29] M. Littman, T. Cassandra, S. Hanks, and L.P. Kaelbling, editors. AMI Fall 
Symposium, Workshop on Planning with Partially Observable Markov Deci­
sion Processes, AAAI, 1998. 
[30] J. Liu and R. Chen. Sequential Monte Carlo methods for dynamic systems. 
Journal of the American Statistical Association, 93, 1998. 
[31] S. Majumder, H. Durrant-Whyte, S. Thrun, and M. de Battista. An approxi­
mate Bayesian method for simultaneous localisation and mapping. Submit­
ted for publication, 2002. 
[32] P. Maybeck. Stochastic Models, Estimation, and Control, Volume 1. Aca­
demic Press, 1979. 
[33] A. Milstein, J. Sanchez, and E. Williamson. Robust global localization using 
clustered particle filtering. In AAA/-02. 
[34] M. Montemerlo, S. Thrun, D. Koller, and B. Wegbreit. FastSLAM: A fac­
tored solution to the simultaneous localization and mapping problem. In 
AAAI-02. 
[35] M. Montemerlo, W. Whittaker, and S. Thrun. Conditional particle filters for 
simultaneous mobile robot localization and people-tracking. In ICRA-02. 
[36] P. Moutarlier and R. Chatila. An experimental system for incremental envi­
ronment modeling by an autonomous mobile robot. In ISER-89. 
[37] K. Murphy. Bayesian map learning in dynamic environments. In N/PS-99. 
[38] J. Pearl. Probabilistic reasoning in intelligent systems: networks of plausible 
inference. Morgan Kaufmann, 1988. 
{39] J. Pineau and S. Thrun. High-level robot behavior control using pomdps. In 
AAAI Workshop notes, 2002. 
[40] M. Pitt and N. Shephard. Filtering via simulation: auxiliary particle filter. 
Journal of the American Statistical Association, 94, 1999. 
[41] L.R. Rabiner and B.H. Juang. An introduction to hidden markov models. 
IEEE ASSP Magazine, 3(1), 1986. 
[42] N. Roy and S. Thrun. Coastal navigation with mobile robot. In N/PS-99. 
[43] R.D. Schraft and G. Schmierer. Service Robots. Peters, 2000. 
[44] D. Schulz, W. Burgard, D. Fox, and A. Cremers. Tracking multiple moving 
targets with a mobile robot using particles filters and statistical data associa­
tion. In ICRA-01. 
[45] R. Smith, M. Self, and P. Cheeseman. Estimating uncertain spatial relation-
ships in robotics. In Autonomous Robot Vehicles, Springer, 1990. 
[46] C. Thorpe and H. Durrant-Whyte. Field robots. In ISRR-01). 
[47] S. Thrun. Monte Carlo POMDPs. In NIPS-00. 
[ 48] S. Thrun. Is robotics going statistics? The field of probabilistic robotics. 
Communications of the ACM, 2001. 
[49] S. Thrun. 
A probabilistic online mapping algorithm for teams of mobile 
robots. International Journal of Robotics Research, 20(5), 2001. 
[50] S. Thrun, M. Beetz, M. Bennewitz, W. Burgard, A.B. Cremers, F. Dellaert, 
D. Fox, D. Hahnel, C. Rosenberg, N. Roy, J. Schulte, and D. Schulz. Prob­
abilistic algorithms and the interactive museum tour-guide robot minerva. 
International Journal of Robotics Research, 19( II), 2000. 
[51] S. Thrun, D. Fox, W. Burgard, and F. Dellaert. Robust monte carlo localiza­
tion for mobile robots. Artificial Intelligence, 128(1-2), 2000. 
[52] S. Williams, G. Dissanayake, and H.F. Durrant-Whyte. 
Towards terrain­
aided navigation for underwater robotics. Advanced Robotics, 15(5), 2001. 
[53] S. Zilberstein and S. Russell. Approximate reasoning using anytime algo­
rithms. In IAC-95.