Episodic non-Markov localization

Abstract

Markov localization and its variants are widely used for mobile robot localization. These methods assume Markov independence of observations, implying that the observations can be entirely explained by a map. However, in real human environments, robots frequently make unexpected observations due to unmapped static objects like chairs and tables, and dynamic objects like humans. We therefore introduce Episodic non-Markov Localization (EnML), which reasons about the world as consisting of three classes of objects: long-term features corresponding to permanent mapped objects, short-term features corresponding to unmapped static objects, and dynamic features corresponding to unmapped moving objects. Long-term features are represented by a static map, while short-term features are detected and tracked in real-time. To reason about unexpected observations and their correlations across poses, we augment the Dynamic Bayesian Network for Markov localization to include varying edges and nodes, resulting in a novel Varying Graphical Network representation. The maximum likelihood estimate of the belief is incrementally computed by non-linear functional optimization. By detecting timesteps along the robot’s trajectory where unmapped observations prior to such time steps are unrelated to those afterwards, EnML limits the history of observations and pose estimates to “episodes” over which the belief is computed. We demonstrate EnML using different types of sensors including laser rangefinders and depth cameras, and over multiple datasets, comparing it with alternative approaches. We further include results of a team of indoor autonomous service mobile robots traversing hundreds of kilometers using EnML.