Skip to main content
Vector Map-Based, Non-Markov Localization for Long-Term Deployment of Autonomous Mobile Robots
  • Joydeep Biswas, Carnegie Mellon University
Date of Award
Degree Type
Degree Name
Doctor of Philosophy (PhD)
Robotics Institute
Manuela M. Veloso
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 introduces several algorithms for localization of autonomous mobile robots in real human environments with the goal of having them autonomously deployed over extended periods of time. Monte Carlo Localization with Sampling-Importance Resampling (MCL-SIR) 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-SIR 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.
Citation Information
Joydeep Biswas. "Vector Map-Based, Non-Markov Localization for Long-Term Deployment of Autonomous Mobile Robots" (2014)
Available at: