Event Location: GHC 4405

Abstract: As robots become increasingly available and capable, there has been an increased
interest in having robots continue to perform autonomously over time despite
changes in their environment.

This thesis recognizes the wide variations in the applications and
constraints of mobile robot localization in human environments, and proposes a
number of localization algorithms geared towards specific tradeoffs between the
constraints. While each of the algorithms introduced might not be perfect for
every robot and every environment, they attempt to optimize for the tradeoffs
for specific robot configurations and in specific environments.

Monte Carlo Localization (MCL) is commonly used for indoor mobile
robot localization, with the frequently prescribed suggestion of increasing the
number of particles to increase accuracy or robustness. Furthermore, most
variants of MCL sample from the odometry model of a robot, which are far less
accurate than modern range sensors. We address both these challenges
by introducing Corrective Gradient Refinement (CGR), which, instead of relying
on more particles, does more with fewer particles. In particular, it uses the
analytically computed state space derivatives of the observation likelihood
function to refine the proposal distribution, thus improving the accuracy as
well as robustness while requiring fewer particles than MCL-SIR.
For robots equipped only with inexpensive depth cameras, we introduce the Fast
Sampling Plane Filtering algorithm to extract dominant planar features from
observed depth images, to use with CGR.

Going beyond MCL, we recognize that human environments have objects that are
either permanent, like walls, movable, like tables and chairs, or moving, like
humans. We introduce Episodic non-Markov Localization, which reasons about the
nature of such observations, and accounts for correlations between observations
even if they are of unmapped objects, to provide location estimates that
are accurate globally with respect to the long-term features, as well as
locally, with respect to the short-term features. By examining the short-term
features detected by the robot over multiple deployments, the robot is further
able to build a Model-Instance map of its environment, reasoning about the
shapes or models of common movable objects separately from the specific
occurrences or instances.

We extensively demonstrate the accuracy and robustness of the localization
algorithms introduced in this thesis over a “1000km Challenge”: to deploy a
team of robots, over multiple floors of multiple buildings, spanning a duration
of a few years. We present quantitative and qualitative results from the 1000km
Challenge, and the data collected in the process.

Committee:Manuela M. Veloso, Chair

Reid Simmons

David Wettergreen

Dieter Fox, University of Washington