Box particle filtering for nonlinear state estimation using interval analysis

In recent years particle filters have been applied to a variety of state estimation problems. A particle filter is a sequential Monte Carlo Bayesian estimator of the posterior density of the state using weighted particles. The efficiency and accuracy of the filter depend mostly on the number of particles used in the estimation and on the propagation function used to re-allocate weights to these particles at each iteration. If the imprecision, i.e. bias and noise, in the available information is high, the number of particles needs to be very large in order to obtain good performances. This may give rise to complexity problems for a real-time implementation. This kind of imprecision can easily be represented by interval data if the maximum error is known. Handling interval data is a new approach successfully applied to different real applications. In this paper, we propose an extension of the particle filter algorithm able to handle interval data and using interval analysis and constraint satisfaction techniques. In standard particle filtering, particles are punctual states associated with weights whose likelihoods are defined by a statistical model of the observation error. In the box particle filter, particles are boxes associated with weights whose likelihood is defined by a bounded model of the observation error. Experiments using actual data for global localization of a vehicle show the usefulness and the efficiency of the proposed approach. (C) 2007 Elsevier Ltd. All rights reserved.