A Probabilistic Technique for Simultaneous Localization and Door State
Estimation with Mobile Robots in Dynamic Environments
Dzintars Avots
1
, Edward Lim
1
, Romain Thibaux
1
, Sebastian Thrun
2
1
Stanford University,
dzin,elim,thibaux
@cs.stanford.edu
2
Carnegie Mellon University, thrun@cs.cmu.edu
Abstract
Virtually all existing mobile robot localization techniques
operate on a static map of the environment. When the
environment changes (e.g., doors are opened or closed),
there is an opportunity to simultaneously estimate the
robot’s pose and the state of the environment. The re-
sulting estimation problem is high-dimensional, render-
ing current localization techniques inapplicable. This pa-
per proposes an efficient, factored estimation algorithm
for mixed discrete-continuous state estimation. Our al-
gorithm integrates particle filters for robot localization,
and conditional binary Bayes filters for estimating the
dynamic state of the environment. Experimental results
illustrate that our algorithm is highly effective in estimat-
ing the status of doors, and outperforms a state-of-the-art
localizer in dynamic environments.
1 Introduction
In the past decade, mobilerobot localization and mapping
has received substantial interest in AI and robotics [1,
12]. The localization problem concerns itself with esti-
mating the pose of a robot relative to a fixed map [9, 11],
whereas the mapping addresses the problem of learning a
map from sensor data [4, 13, 16].
A striking characteristic of the rich literature on this topic
is that virtually all published work assumes that the envi-
ronment is static. This is in contrast to most robotic en-
vironments, which usually change over time. For exam-
ple, most office environments possess doors, chairs, and
other items whose location or state changes over time. A
worthwhile research goal, thus, is to extend existing tech-
niques by algorithms that can perform localization and
mapping functions in dynamic environments. Of course,
the recognition that natural environments are dynamic is
not new. For example, Fox et al. [8] have developed a
localization algorithm that is robust to the presence of
people in the environment, as demonstrated in a crowded
museum experiment [2]. However, such algorithms still
assume a static map, which is never revised in accordance
to sensor evidence. Instead, the paper is an example of a
more common methodology of treating dynamic effects.
In mobile robotics, dynamic effects are usually regarded
as noise and filtered out [7].
This paper addresses a specific dynamic environment
problem: Estimating the state of a set binary state vari-
ables (e.g., doors, or grid cells in an occupancy grid map)
in an environment that changes. The difficulty of this
problem arises from the fact that localizing a robot in
such environment is generally difficult. From an esti-
mation point of view, there is interaction between the
problem of estimating the robot’s location and the state
of the environment. For example, if a robot encounters
an obstacles in an area that previously corresponded to
an open door, there exist two quite complementary ways
to explain such measurements: Either the door status has
changed, or the robot is not where it believes to be (a less
plausible explanation would be that the observation is the
effect of sensor noise). As this example illustrates, the
problem of localization and environment state estimation
cannot be decoupled.
This paper proposes an efficient algorithm for localizing
a robot in an environment with discrete states, while si-
multaneously estimating the state of the environment. We
show that under the appropriate formulation, the estima-
tion problem can be factored into a problem reminiscent
(but not identical) to conventional mobile robot localiza-
tion, and a number of conditional Bayes filters for esti-
mating the environment’s state. The specific algorithm
extends the work by Murphy [15] on state estimation in
Bayesian networks. Like Murphy, our approach employs
a particle filter for estimating the robot’s pose. The dis-
crete environment state variables are estimated via dis-
crete Bayesian filters (similar in nature to the standard
occupancy grid algorithm [14]). However, those Bayes
filters are conditioned on the robot’s path estimate, hence
are attached to individual particles. The resulting algo-
rithm scales linear in the number of state variables in the
environment, and linear in the number of particles. This
is significantly more efficient than existing existing map-
ping algorithms that combine localization and map esti-
mation [4, 13], which scale quadratically in the number
of environment state variables (and typically involve only
continuous state variables).