Probabilistic Self-Localization for Sensor Networks

AAAI Conferences

This paper describes a technique for the probabilistic self-localization of a sensor network based on noisy inter-sensor range data. Our method is based on a number of parallel instances of Markov Chain Monte Carlo (MCMC). By combining estimates drawn from these parallel chains, we build up a representation of the underlying probability distribution function (PDF) for the network pose. Our approach includes sensor data incrementally in order to avoid local minima and is shown to produce meaningful results efficiently. We return a distribution over sensor locations rather than a single maximum likelihood estimate. This can then be used for subsequent exploration and validation.


Monte Carlo Localization: Efficient Position Estimation for Mobile Robots Dieter Fox, Wolfram Burgard, Frank Dellaert, Sebastian Thrun

AAAI Conferences

This paper presents a new algorithm for mobile robot localization, called Monte Carlo Localization (MCL). MCL is a version of Markov localization, a family of probabilistic approaches that have recently been applied with great practical success. However, previous approaches were either computationally cumbersome (such as grid-based approaches that represent the state space by high-resolution 3D grids), or had to resort to extremely coarse-grained resolutions. Our approach is computationally efficient while retaining the ability to represent (almost) arbitrary distributions. MCL applies sampling-based methods for approximating probability distributions, in a way that places computation "where needed." The number of samples is adapted online, thereby invoking large sample sets only when necessary. Empirical results illustrate that MCL yields improved accuracy while requiring an order of magnitude less computation when compared to previous approaches. It is also much easier to implement.


Bayesian Calibration for Monte Carlo Localization

AAAI Conferences

Localization is a fundamental challenge for autonomous robotics. Although accurate and efficient techniques now exist for solving this problem, they require explicit probabilistic models of the robot's motion and sensors. These models are usually obtained from time-consuming and error-prone measurement or tedious manual tuning. In this paper we examine automatic calibration of sensor and motion models from a Bayesian perspective. We introduce an efficient MCMC procedure for sampling from the posterior distribution of the model parameters. We also present a novel extension of particle filters to make use of our posterior parameter samples. Finally, we demonstrate our approach both in simulation and on a physical robot. Our results demonstrate effective inference of model parameters as well as a paradoxical result that using posterior parameter samples can produce more accurate position estimates than the true parameters.


Particle Filters in Robotics (Invited Talk)

arXiv.org Artificial Intelligence

This presentation will introduce the audience to a new, emerging body of research on sequential Monte Carlo techniques in robotics. In recent years, particle filters have solved several hard perceptual robotic problems. Early successes were limited to low-dimensional problems, such as the problem of robot localization in environments with known maps. More recently, researchers have begun exploiting structural properties of robotic domains that have led to successful particle filter applications in spaces with as many as 100,000 dimensions. The presentation will discuss specific tricks necessary to make these techniques work in real - world domains,and also discuss open challenges for researchers IN the UAI community.


Monte Carlo Localization With Mixture Proposal Distribution

AAAI Conferences

Monte Carlo localization (MCL) is a Bayesian algorithm for mobile robot localization based on particle filters, which has enjoyed great practical success. This paper points out a limitation of MCL which is counterintuitive, namely that better sensors can yield worse results. An analysis of this problem leads to the formulation of a new proposal distribution for the Monte Carlo sampling step. Extensive experimental results with physical robots suggest that the new algorithm is significantly more robust and accurate than plain MCL. Obviously, these results transcend beyond mobile robot localization and apply to a range of particle filter applications.