5 ms·

Often alterations of the Kalman filter are a good compromise. E.g. the extended Kalman https://en.m.wikipedia.org/wiki/Extended_Kalman_filter https://en.m.wikip

Often alterations of the Kalman filter are a good compromise. E.g. the extended Kalman https://en.m.wikipedia.org/wiki/Extended_Kalman_filter https://en.m.wikipedia.org/wiki/Extended_Kalman_filter As you stated particle filters are computationally expensive. Also I found them more fidgety to configure for my application cases (in activity recognition).

gugagore 6y ago
Have you heard of the "Unscented Kalman Filter"? It goes by UKF. It uses a different approximation scheme than the EKF, which creates a linear approximation of the dynamics, in order to propagate the mean and variance. The UKF computation using "sigma points" resembles a specific part of the particle filter. And why the name? Well the EKF stinks in many applications (it diverges). The UKF is more robust, especially when there is more significant uncertainty.
- wutbrodo 6y ago
  >Unscented Kalman Filter Funny factoid: the paper that named the UKF did so because "it doesn't stink"
  - gugagore 6y ago
    I explained that in my comment.
    - wutbrodo 6y ago
      Ha yea, I missed that you used the word stink to describe the EKF. Sorry!
- amirhirsch 6y ago
  We upgraded from an EKF to a UKF for our drone. I feel like our code is a good reference for using an Unscented Kalman Filter to estimate a drone’s rotational state, later this year I expect to add an optical flow and ToF sensor and update the filter for better velocity and displacement estimation. https://github.com/Flybrix/flybrix-firmware/blob/master/ukf.cpp https://github.com/Flybrix/flybrix-firmware/blob/master/ukf....
kkylin 6y ago
Another extension is the ensemble Kalman filter (https://en.wikipedia.org/wiki/Ensemble_Kalman_filter https://en.wikipedia.org/wiki/Ensemble_Kalman_filter), which can work well for certain kinds of nonlinear systems, and when it does it can be more robust than particle filters. (Particle filters can "collapse"; this limits their usefulness.)
wenc 6y ago
The Extended Kalman Filter (EKF) relies on local linear linearizations to handle nonlinearity. This works for mildly nonlinear systems, but doesn’t do so well when the system is highly nonlinear (divergence happens). The Unscented Kalman Filter (UKF) is a kind of particle-like filter but instead of propagating a large number of points, it only propagates carefully chosen “sigma points”. It’s much more economical and works relatively well with nonlinear systems. To me, the gold standard in estimation is the Moving Horizon Estimator (MHE) [1] which solves an explicit optimization problem to arrive at the state estimate, which allows it to accommodate constraints in the system. It is however computationally much heavier than the Kalman family of filters. I’ve implemented UKFs in the past and think they’re a good trade off between computational speed and accuracy in the presence of nonlinearities. They cannot handle constraints however, which is a major weakness that MHEs don’t succumb to. (Imagine you are estimating a quantity x in the interval [0, 1] - UKFs can return estimates like 1.32 or -0.3 whereas MHEs accommodate bound constraints like 0 <= x <= 1 as well as more complex constraints to prevent weird outputting impossible or weird state estimates) [1] https://murray.cds.caltech.edu/images/murray.cds/0/0d/L4-2_MHE.pdf https://murray.cds.caltech.edu/images/murray.cds/0/0d/L4-2_M...
- isatty 6y ago
  I mayve read the presentation wrong but it says 3s/iteration on the MHE. That’s insane. I’ve run close to real time UKF for nav and control applications so it’s an apples vs oranges comparison.
  - touisteur 6y ago
    Right now, yes. There was a time where doppler filtering was too expensive in programmable COTS HW, or digital beamforming, or SVD... What's missing here is the gain vs optimisation effort. If there is an order of magnitude of gain here, we'll reduce the latency one way or the other. I see impossible-20-years-ago heavy-duty solvers in RT sensors more and more. Also depending on your refresh rate 3s might still be worth it IF the filter gain is so much better.
  - wenc 6y ago
    For real time mechanical and electrical applications, the MHE is generally not competitive (at present) However, there many types of dynamic systems that are much slower like chemical plants (minute to hour level control) that can accommodate MHE’s execution time scales. If you need to simultaneously handle nonlinearities and constraints, it may be a superior choice. Also there are potential ways to make MHE run faster. For certain forms of the optimization problem (like a linear or quadratic program), it’s possible to convert it to a lookup table (search for “explicit MPC”) which can then be implemented in an embedded system for fast lookups. That said, I agree with you in practice. An nonlinear optimization problem tends to be a numerical black box and can be hard to diagnose when things go wrong. The Kalman family of algorithms is much more straightforward (only involves function evaluations), faster and have failure modes that are much more easily understood. They just don’t do so well with constraints.

gugagore 6y ago

Have you heard of the "Unscented Kalman Filter"? It goes by UKF. It uses a different approximation scheme than the EKF, which creates a linear approximation of the dynamics, in order to propagate the mean and variance. The UKF computation using "sigma points" resembles a specific part of the particle filter. And why the name? Well the EKF stinks in many applications (it diverges). The UKF is more robust, especially when there is more significant uncertainty.

wutbrodo 6y ago
>Unscented Kalman Filter Funny factoid: the paper that named the UKF did so because "it doesn't stink"
- gugagore 6y ago
  I explained that in my comment.
  - wutbrodo 6y ago
    Ha yea, I missed that you used the word stink to describe the EKF. Sorry!
amirhirsch 6y ago
We upgraded from an EKF to a UKF for our drone. I feel like our code is a good reference for using an Unscented Kalman Filter to estimate a drone’s rotational state, later this year I expect to add an optical flow and ToF sensor and update the filter for better velocity and displacement estimation. https://github.com/Flybrix/flybrix-firmware/blob/master/ukf.cpp https://github.com/Flybrix/flybrix-firmware/blob/master/ukf....

kkylin 6y ago

Another extension is the ensemble Kalman filter (https://en.wikipedia.org/wiki/Ensemble_Kalman_filter https://en.wikipedia.org/wiki/Ensemble_Kalman_filter), which can work well for certain kinds of nonlinear systems, and when it does it can be more robust than particle filters. (Particle filters can "collapse"; this limits their usefulness.)

wenc 6y ago

The Extended Kalman Filter (EKF) relies on local linear linearizations to handle nonlinearity. This works for mildly nonlinear systems, but doesn’t do so well when the system is highly nonlinear (divergence happens). The Unscented Kalman Filter (UKF) is a kind of particle-like filter but instead of propagating a large number of points, it only propagates carefully chosen “sigma points”. It’s much more economical and works relatively well with nonlinear systems. To me, the gold standard in estimation is the Moving Horizon Estimator (MHE) [1] which solves an explicit optimization problem to arrive at the state estimate, which allows it to accommodate constraints in the system. It is however computationally much heavier than the Kalman family of filters. I’ve implemented UKFs in the past and think they’re a good trade off between computational speed and accuracy in the presence of nonlinearities. They cannot handle constraints however, which is a major weakness that MHEs don’t succumb to. (Imagine you are estimating a quantity x in the interval [0, 1] - UKFs can return estimates like 1.32 or -0.3 whereas MHEs accommodate bound constraints like 0 <= x <= 1 as well as more complex constraints to prevent weird outputting impossible or weird state estimates) [1] https://murray.cds.caltech.edu/images/murray.cds/0/0d/L4-2_MHE.pdf https://murray.cds.caltech.edu/images/murray.cds/0/0d/L4-2_M...

isatty 6y ago
I mayve read the presentation wrong but it says 3s/iteration on the MHE. That’s insane. I’ve run close to real time UKF for nav and control applications so it’s an apples vs oranges comparison.
- touisteur 6y ago
  Right now, yes. There was a time where doppler filtering was too expensive in programmable COTS HW, or digital beamforming, or SVD... What's missing here is the gain vs optimisation effort. If there is an order of magnitude of gain here, we'll reduce the latency one way or the other. I see impossible-20-years-ago heavy-duty solvers in RT sensors more and more. Also depending on your refresh rate 3s might still be worth it IF the filter gain is so much better.
- wenc 6y ago
  For real time mechanical and electrical applications, the MHE is generally not competitive (at present) However, there many types of dynamic systems that are much slower like chemical plants (minute to hour level control) that can accommodate MHE’s execution time scales. If you need to simultaneously handle nonlinearities and constraints, it may be a superior choice. Also there are potential ways to make MHE run faster. For certain forms of the optimization problem (like a linear or quadratic program), it’s possible to convert it to a lookup table (search for “explicit MPC”) which can then be implemented in an embedded system for fast lookups. That said, I agree with you in practice. An nonlinear optimization problem tends to be a numerical black box and can be hard to diagnose when things go wrong. The Kalman family of algorithms is much more straightforward (only involves function evaluations), faster and have failure modes that are much more easily understood. They just don’t do so well with constraints.