4 ms·

Nice article on an important tool. My understanding is that linear Kalman filters are an optimal solution to linear problems. Linear Kalman filters are relativ

Nice article on an important tool. My understanding is that linear Kalman filters are an optimal solution to linear problems. Linear Kalman filters are relatively easy to understand and implement. Most applications I've found are non-linear. Extended (and unscented) Kalman filters are much tougher to grasp and implement. Resources and libraries are fewer and less useful. For example, I have an AHRS/GNSS CAN device intended for small UAVs. Extended Kalman filters for these I've come across (like for PX4 and Ardupilot) are very complex, and have many parameters. I've found it more straightforward to take an ab-initio approach using quaternion fundamentals, and nudging the gyro solution towards the accelerometer "up", and the magnetometer inclination vector. If the accelerometer magnitude differs much from 1G or the mag vector differs much from the local earth mag field strength, downweight or skip the update from that sensor, letting the gyro coast. Likely, an EKF would be the correct play, but I've given up trying to understand one, or make or adapt one that would work or be easier to tune and diagnose than the ab-initio approach.

toasted-subs 3y ago
Yea, when you know what you are trying to model it's extremely easy to write a model that represents a traditional linear Kalman filter. But there are many ways to write a Kalman filter; depending on where you start non-linear transformation becomes extremely cumbersome to get right.
nextos 3y ago
A probabilistic programming language can make it much easier to implement a non-linear filter. Essentially, you implement the generative model, and you get inference compiled for you. Interesting options to look at include ForneyLab.jl, Infer.net, Gen.jl, and Pyro.
- tnecniv 3y ago
  This can work if the time scale of inference is smaller than the time scale of your measurements. I’m skeptical that this would work on a quadrotor that requires a fast control loop. However, model predictive control (determining actions given a state and dynamic model; the Kalman filter is model predictive estimation) first found major use in chemical plants because they could crunch the numbers on a big computer that didn’t need to fit on a robot and the real time between each time step was large. For such a situation, you might be able to get MCMC to work.
  - nextos 3y ago
    The options I suggested above are not necessarily MCMC, they are mostly message passing algorithms. ForneyLab and Gen in particular are designed for online inference.
    - tnecniv 3y ago
      Good point! Still, a big reason why the reason why the KF is a staple is that it’s really really fast. When I’ve used tools like the ones that you mentioned, it was normally not for inference not in a feedback loop. I’m less familiar with message passing methods than Monte Carlo methods but I’m going to look into them now
      - nextos 3y ago
        Message passing can lead to extremely fast maximum likelihood or variational inference. I have used it for realtime control problems. It is a very interesting domain!
        tnecniv 3y ago
        Do you have a good reference? Preferably one that mentions a control application because I’m curious to see what the model assumptions and speed look like in that context
        nextos 3y ago
        You can start with a review [1], and then BRML [2]. I think applications that are very focused on control tend to come from the military and thus not so well documented. [1] An introduction to factor graphs. https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=1267047 https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=1267047 [2] Bayesian Reasoning and Machine Learning. http://web4.cs.ucl.ac.uk/staff/D.Barber/textbook/200620.pdf http://web4.cs.ucl.ac.uk/staff/D.Barber/textbook/200620.pdf
sheepshear 3y ago
My recommendation if open courseware is the type of resource that might interest you: http://mocha-java.uccs.edu/ECE5550/index.html http://mocha-java.uccs.edu/ECE5550/index.html
tnecniv 3y ago
For what it’s worth, the EKF isn’t much more complicated than the regular KF. You are basically just linearizing your dynamics / sensor model then doing the KF updates with that linear model. However, for quadrotors specifically, there is a huge pain point: the rotations. A nuance of the linear models of the Kalman filter is that everything lives in Euclidean space. However, rotations place you on a manifold — for quaternions specifically this manifold is the set of unit quaternions. If you naively apply an EKF to estimate your quaternion, you will no longer have a unit quaternion and then your estimates will be garbage. There are well-known ways to handle this manifold constraint but they result in some of the ugliest equations I have ever turned into code. As a simple example of the difficulty, consider a state (x, y) that, due to physics or whatever, we know will always be on the unit circle, I.e., if f(x, y) is your dynamics, it outputs a new point on the circle. However, if you linearize f(x, y), these approximate dynamics are not guaranteed to keep you on the unit sphere and you end up with a non-physical state (or state estimate for the extended Kalman filter).
- cmehdy 3y ago
  You just threw me back into time I spent on EKF implementations on early iPads over a decade ago (as an exchange student), as part of a M.Sc. in Control Theory... before I had learnt about KF. The goal was to compensate for the drift observed on the position of those devices which made them useless for the need (art exhibition stuff). I don't think I even fully completed the project because my understanding of both quaternions and KF were at that point pretty shaky, this could be a fun project to pull with some old hardware now..

toasted-subs 3y ago

Yea, when you know what you are trying to model it's extremely easy to write a model that represents a traditional linear Kalman filter. But there are many ways to write a Kalman filter; depending on where you start non-linear transformation becomes extremely cumbersome to get right.

nextos 3y ago

A probabilistic programming language can make it much easier to implement a non-linear filter. Essentially, you implement the generative model, and you get inference compiled for you. Interesting options to look at include ForneyLab.jl, Infer.net, Gen.jl, and Pyro.

tnecniv 3y ago
This can work if the time scale of inference is smaller than the time scale of your measurements. I’m skeptical that this would work on a quadrotor that requires a fast control loop. However, model predictive control (determining actions given a state and dynamic model; the Kalman filter is model predictive estimation) first found major use in chemical plants because they could crunch the numbers on a big computer that didn’t need to fit on a robot and the real time between each time step was large. For such a situation, you might be able to get MCMC to work.
- nextos 3y ago
  The options I suggested above are not necessarily MCMC, they are mostly message passing algorithms. ForneyLab and Gen in particular are designed for online inference.
  - tnecniv 3y ago
    Good point! Still, a big reason why the reason why the KF is a staple is that it’s really really fast. When I’ve used tools like the ones that you mentioned, it was normally not for inference not in a feedback loop. I’m less familiar with message passing methods than Monte Carlo methods but I’m going to look into them now
    - nextos 3y ago
      Message passing can lead to extremely fast maximum likelihood or variational inference. I have used it for realtime control problems. It is a very interesting domain!
      - tnecniv 3y ago
        Do you have a good reference? Preferably one that mentions a control application because I’m curious to see what the model assumptions and speed look like in that context
        nextos 3y ago
        You can start with a review [1], and then BRML [2]. I think applications that are very focused on control tend to come from the military and thus not so well documented. [1] An introduction to factor graphs. https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=1267047 https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=1267047 [2] Bayesian Reasoning and Machine Learning. http://web4.cs.ucl.ac.uk/staff/D.Barber/textbook/200620.pdf http://web4.cs.ucl.ac.uk/staff/D.Barber/textbook/200620.pdf

sheepshear 3y ago

My recommendation if open courseware is the type of resource that might interest you: http://mocha-java.uccs.edu/ECE5550/index.html http://mocha-java.uccs.edu/ECE5550/index.html

tnecniv 3y ago

For what it’s worth, the EKF isn’t much more complicated than the regular KF. You are basically just linearizing your dynamics / sensor model then doing the KF updates with that linear model. However, for quadrotors specifically, there is a huge pain point: the rotations. A nuance of the linear models of the Kalman filter is that everything lives in Euclidean space. However, rotations place you on a manifold — for quaternions specifically this manifold is the set of unit quaternions. If you naively apply an EKF to estimate your quaternion, you will no longer have a unit quaternion and then your estimates will be garbage. There are well-known ways to handle this manifold constraint but they result in some of the ugliest equations I have ever turned into code. As a simple example of the difficulty, consider a state (x, y) that, due to physics or whatever, we know will always be on the unit circle, I.e., if f(x, y) is your dynamics, it outputs a new point on the circle. However, if you linearize f(x, y), these approximate dynamics are not guaranteed to keep you on the unit sphere and you end up with a non-physical state (or state estimate for the extended Kalman filter).

cmehdy 3y ago
You just threw me back into time I spent on EKF implementations on early iPads over a decade ago (as an exchange student), as part of a M.Sc. in Control Theory... before I had learnt about KF. The goal was to compensate for the drift observed on the position of those devices which made them useless for the need (art exhibition stuff). I don't think I even fully completed the project because my understanding of both quaternions and KF were at that point pretty shaky, this could be a fun project to pull with some old hardware now..