Tag Archives: Recursive Bayesian Estimation

A novel non-linear bayesian filter for continuous time estimation with a nice comparison to discrete-time filters

July 30, 2015 16:55 ,

Atiyeh Ghoreyshi and Terence D. Sanger, A Nonlinear Stochastic Filter for Continuous-Time State Estimation, IEEE Transactions on Automatic Control, vol. 60, no. 8, DOI: 10.1109/TAC.2015.2409910.

Nonlinear filters produce a nonparametric estimate of the probability density of state at each point in time. Currently known nonlinear filters include Particle Filters and the Kushner equation (and its un-normalized version: the Zakai equation). However, these filters have limited measurement models: Particle Filters require measurement at discrete times, and the Kushner and Zakai equations only apply when the measurement can be represented as a function of the state. We present a new nonlinear filter for continuous-time measurements with a much more general stochastic measurement model. It integrates to Bayes’ rule over short time intervals and provides Bayes-optimal estimates from quantized, intermittent, or ambiguous sensor measurements. The filter has a close link to Information Theory, and we show that the rate of change of entropy of the density estimate is equal to the mutual information between the measurement and the state and thus the maximum achievable. This is a fundamentally new class of filter that is widely applicable to nonlinear estimation for continuous-time control.

Posted in: Bayesian filtering , Tagged:

Substituting the update step of a bayesian filter by a maximum likelihood optimisation in order to use non-linear observation models in a (linear-transition) Kalman framework

July 30, 2015 16:32 ,

Damián Marelli, Minyue Fu, and Brett Ninness, Asymptotic Optimality of the Maximum-Likelihood Kalman Filter for Bayesian Tracking With Multiple Nonlinear Sensors, IEEE Transactions on signal processing, vol. 63, no. 17, DOI: 10.1109/TSP.2015.2440220.

Bayesian tracking is a general technique for state estimation of nonlinear dynamic systems, but it suffers from the drawback of computational complexity. This paper is concerned with a class of Wiener systems with multiple nonlinear sensors. Such a system consists of a linear dynamic system followed by a set of static nonlinear measurements. We study a maximum-likelihood Kalman filtering (MLKF) technique which involves maximum-like-lihood estimation of the nonlinear measurements followed by classical Kalman filtering. This technique permits a distributed implementation of the Bayesian tracker and guarantees the boundedness of the estimation error. The focus of this paper is to study the extent to which the MLKF technique approximates the theoretically optimal Bayesian tracker. We provide conditions to guarantee that this approximation becomes asymptotically exact as the number of sensors becomes large. Two case studies are analyzed in detail.

Posted in: Bayesian filtering , Tagged: , , , ,

A brief general explanation of Rao-Blacwellization and a new way of applying it to reduce the variance of a point estimation in a sequential bayesian setting

July 20, 2015 11:08 ,

Petetin, Y.; Desbouvries, F., Bayesian Conditional Monte Carlo Algorithms for Nonlinear Time-Series State Estimation, Signal Processing, IEEE Transactions on , vol.63, no.14, pp.3586,3598, DOI: 10.1109/TSP.2015.2423251.

Bayesian filtering aims at estimating sequentially a hidden process from an observed one. In particular, sequential Monte Carlo (SMC) techniques propagate in time weighted trajectories which represent the posterior probability density function (pdf) of the hidden process given the available observations. On the other hand, conditional Monte Carlo (CMC) is a variance reduction technique which replaces the estimator of a moment of interest by its conditional expectation given another variable. In this paper, we show that up to some adaptations, one can make use of the time recursive nature of SMC algorithms in order to propose natural temporal CMC estimators of some point estimates of the hidden process, which outperform the associated crude Monte Carlo (MC) estimator whatever the number of samples. We next show that our Bayesian CMC estimators can be computed exactly, or approximated efficiently, in some hidden Markov chain (HMC) models; in some jump Markov state-space systems (JMSS); as well as in multitarget filtering. Finally our algorithms are validated via simulations.

Posted in: Bayesian filtering , Tagged: , ,

Accelerating the updating stage of a PF through selection of a few representative particles and interpolation of their weights to the rest, with interesting methods for selection and interpolation and a nice related work of efficiency-improved PFs

July 17, 2015 09:41 ,

Shabat, G.; Shmueli, Y.; Bermanis, A.; Averbuch, A., Accelerating Particle Filter Using Randomized Multiscale and Fast Multipole Type Methods, Pattern Analysis and Machine Intelligence, IEEE Transactions on , vol.37, no.7, pp.1396,1407, July 1 2015, DOI: 10.1109/TPAMI.2015.2392754.

Particle filter is a powerful tool for state tracking using non-linear observations. We present a multiscale based method that accelerates the tracking computation by particle filters. Unlike the conventional way, which calculates weights over all particles in each cycle of the algorithm, we sample a small subset from the source particles using matrix decomposition methods. Then, we apply a function extension algorithm that uses a particle subset to recover the density function for all the rest of the particles not included in the chosen subset. The computational effort is substantial especially when multiple objects are tracked concurrently. The proposed algorithm significantly reduces the computational load. By using the Fast Gaussian Transform, the complexity of the particle selection step is reduced to a linear time in n and k , where n is the number of particles and k is the number of particles in the selected subset. We demonstrate our method on both simulated and on real data such as object tracking in video sequences.

Posted in: Bayesian filtering , Tagged: , , , ,

Analysis of the deterioration of several Kalman Filters depending on the amount of uncertainty in the observations, when the observation model is non-linear

May 4, 2015 11:51 ,

Mark R. Morelande and Ángel F. García-Fernández, Analysis of Kalman Filter Approximations for Nonlinear Measurements, IEEE Transactions on signal processing, vol. 61, no. 22, 2013 DOI: 10.1109/TSP.2013.2279367.

A theoretical analysis is presented of the correction step of the Kalman filter (KF) and its various approximations for the case of a nonlinear measurement equation with additive Gaussian noise. The KF is based on a Gaussian app roximation to the joint density of the state and the measurement. The analysis metric is the Kullback-Leibler divergence of this approximation from the true joint density. The purpose of the analysis is to provide a quantitative tool for understanding and assessing the performance of the KF and its variants in nonlinear scenarios. This is illustrated using a numerical example.

Posted in: Probability and statistics , Tagged: , , , ,

Novel recursive bayesian estimator based on approaching pdfs by polynomials and keeping a hypothesis for each of its modes

February 10, 2015 20:08 ,

Huang, G.; Zhou, K.; Trawny, N.; Roumeliotis, S.I., (2015), A Bank of Maximum A Posteriori (MAP) Estimators for Target Tracking, Robotics, IEEE Transactions on , vol.31, no.1, pp.85,103. DOI: TRO.2014.2378432

.

Nonlinear estimation problems, such as range-only and bearing-only target tracking, are often addressed using linearized estimators, e.g., the extended Kalman filter (EKF). These estimators generally suffer from linearization errors as well as the inability to track multimodal probability density functions. In this paper, we propose a bank of batch maximum a posteriori (MAP) estimators as a general estimation framework that provides relinearization of the entire state trajectory, multihypothesis tracking, and an efficient hypothesis generation scheme. Each estimator in the bank is initialized using a locally optimal state estimate for the current time step. Every time a new measurement becomes available, we relax the original batch-MAP problem and solve it incrementally. More specifically, we convert the relaxed one-step-ahead cost function into polynomial or rational form and compute all the local minima analytically. These local minima generate highly probable hypotheses for the target’s trajectory and hence greatly improve the quality of the overall MAP estimate. Additionally, pruning of least probable hypotheses and marginalization of old states are employed to control the computational cost. Monte Carlo simulation and real-world experimental results show that the proposed approach significantly outperforms the standard EKF, the batch-MAP estimator, and the particle filter.

Posted in: Mobile Robot Localization , Tagged: ,

Mathematical model of quartz crystal clocks and Kalman Filter estimation for clock synchronization

January 23, 2015 17:46 ,

Giorgi, G., An Event-Based Kalman Filter for Clock Synchronization, Instrumentation and Measurement, IEEE Transactions on , vol.64, no.2, pp.449,457, Feb. 2015, DOI: 10.1109/TIM.2014.2340631

The distribution of a time reference has long been a significant research topic in measurement and different solutions have been proposed over the years. In this context, the design of servo clocks plays an important role to get better performances by smoothing the influence of noise sources affecting a synchronization system. A servo clock is asked to provide an adaptive and conservative measure of the time distance between the local clock and the time reference by minimizing, if possible, the energy consumption. In this paper, we propose a servo clock based on an efficient implementation of the Kalman filter (KF), called in the following event-based KF that allows to overcome drawbacks of existing KF-based servo clocks with furthermore a significant reduction of the computational cost. An in-depth analysis of the synchronization uncertainty has been reported to completely characterize the proposed solution; and finally, some guidelines on how to correctly initialize the KF are provided.

Posted in: Networked telerobots , Tagged: ,

SLAM as a least-squares optimization problem and reduction of the cost through the use of spherical covariance matrices that approximate the original, sparse ones

December 9, 2014 17:09 ,

Heng Wang, Shoudong Huang, Kasra Khosoussi, Udo Frese, Gamini Dissanayake, Bingbing Liu, Dimensionality reduction for point feature SLAM problems with spherical covariance matrices, Automatica, Volume 51, January 2015, Pages 149-157, ISSN 0005-1098. DOI: 10.1016/j.automatica.2014.10.114

The main contribution of this paper is the dimensionality reduction for multiple-step 2D point feature based Simultaneous Localization and Mapping (SLAM), which is an extension of our previous work on one-step SLAM (Wang et al., 2013). It has been proved that SLAM with multiple robot poses and a number of point feature positions as variables is equivalent to an optimization problem with only the robot orientations as variables, when the associated uncertainties can be described using spherical covariance matrices. This reduces the dimension of original problem from 3 m + 2 n to m only (where m is the number of poses and n is the number of features). The optimization problem after dimensionality reduction can be solved numerically using the unconstrained optimization algorithms. While dimensionality reduction may not provide computational saving for all nonlinear optimization problems, for some SLAM problems we can achieve benefits such as improvement on time consumption and convergence. For the special case of two-step SLAM when the orientation information from odometry is not incorporated, an algorithm that can guarantee to obtain the globally optimal solution (in the maximum likelihood sense) is derived. Simulation and experimental datasets are used to verify the equivalence between the reduced nonlinear optimization problem and the original full optimization problem, as well as the proposed new algorithm for obtaining the globally optimal solution for two-step SLAM.

Posted in: Mobile robot SLAM , Tagged: , ,

Probabilistic models of several sensors plus a method for distinguishing the different hypotheses from the posterior of a PF

December 4, 2014 19:27 ,

V. Alvarez-Santos, A. Canedo-Rodriguez, R. Iglesias, X.M. Pardo, C.V. Regueiro, M. Fernandez-Delgado, Route learning and reproduction in a tour-guide robot, Robotics and Autonomous Systems, Volume 63, Part 2, January 2015, Pages 206-213, ISSN 0921-8890. DOI: 10.1016/j.robot.2014.07.013

Traditionally, route information is introduced in tour-guide robots by experts in robotics. In the tour-guide robot that we are developing, we allow the robot to learn new routes while following an instructor. In this paper we describe the route recording process that takes place while following a human, as well as, how those routes are later reproduced.

A key element of both route recording and reproduction is a robust multi-sensorial localization algorithm that we have designed, which is able to combine various sources of information to obtain an estimate of the robot’s pose. In this work we detail how the algorithm works, and how we use it to record routes. Moreover, we describe how our robot reproduces routes, including path planning within route points, and dynamic obstacle avoidance for safe navigation. Finally, we show through several trajectories how the robot was able to learn and reproduce different routes.

Posted in: Mobile Robot Localization , Tagged: , , ,