Programmer's Toolbox
Quiet down out there!
Jack Crenshaw
1/30/2012 3:23 PM EST
Understand how to cut down on the noise in your system, using the math behind the Kalman filter. If you know something about the dynamics of the system, you can make a better estimate of what it's doing now and what it's going to do next.
The universe is a noisy place. More so in Manhattan, Detroit, or the galactic core; less so in the Swiss Alps or interstellar space, but noisy everywhere. No matter how hard you try, you can't escape the noise.
Few people understand this better than scientists and engineers, especially those of us who work with embedded real-time systems. Chances are, the first time you hooked up some measuring sensor to an analog-to-digital converter, you learned this lesson well.
Most likely, you decided to insert a low-pass filter into the signal path. That will remove a lot of the noise, all right, but also the fine structure of the system behavior. And it necessarily adds a time delay to the system--a delay that will affect the stability of a control system.
Filters have their place, for sure. But in the end, the use of a low-pass filter is a tacit admission that we don't have a clue what the system is really doing. We filter it because it's the only recourse we have. We treat the input signal as pseudo-static, and hope that our sample rate is fast enough to make the signal look like a constant.
On the other hand, there can be times when we do know--or think we know--how the system should behave. A real physical system obeys the laws of physics. A reactor in a chemical plant is going to follow the laws governing its particular chemical reaction. An airplane in flight is going to obey Newton's laws of motion.
In such cases, we can do a little better than simply relying on brute force low-pass filters. If we know something about the dynamics of the system, we can make a better estimate of what it's doing now and what it's going to do next. That concept has been the focus of my last few columns and will remain our focus for the near future. This is the third installment of the series.
The universe is a noisy place. More so in Manhattan, Detroit, or the galactic core; less so in the Swiss Alps or interstellar space, but noisy everywhere. No matter how hard you try, you can't escape the noise.
Few people understand this better than scientists and engineers, especially those of us who work with embedded real-time systems. Chances are, the first time you hooked up some measuring sensor to an analog-to-digital converter, you learned this lesson well.
Most likely, you decided to insert a low-pass filter into the signal path. That will remove a lot of the noise, all right, but also the fine structure of the system behavior. And it necessarily adds a time delay to the system--a delay that will affect the stability of a control system.
Filters have their place, for sure. But in the end, the use of a low-pass filter is a tacit admission that we don't have a clue what the system is really doing. We filter it because it's the only recourse we have. We treat the input signal as pseudo-static, and hope that our sample rate is fast enough to make the signal look like a constant.
On the other hand, there can be times when we do know--or think we know--how the system should behave. A real physical system obeys the laws of physics. A reactor in a chemical plant is going to follow the laws governing its particular chemical reaction. An airplane in flight is going to obey Newton's laws of motion.
In such cases, we can do a little better than simply relying on brute force low-pass filters. If we know something about the dynamics of the system, we can make a better estimate of what it's doing now and what it's going to do next. That concept has been the focus of my last few columns and will remain our focus for the near future. This is the third installment of the series.
|
|
|
|
|
Navigate to related information
RidgeRat
1/31/2012 11:10 PM EST
Though enlightening as always, unfortunately, this story line appears to be branching away from this topic prematurely. Models for Kalman filtering are not an independent choice that can be fathomed by examining input/output data plots. There are two special requirements: First, the model must be one-step predictive. Given past and current data, it must provide a prediction (a very good one can't hurt!) of what the next output response will be, given the next input, but before that new output is observed. Second, the model form does not use "x-y" past history directly like the least-squares fitting discussed so far, but instead, it must reduce past history to bare essentials in the form of a set of "state" variables (sometimes without any direct physical interpretation), with model outputs subsequently derived from these state variables, and with new inputs serving to influence future state variable values. The key relationships are described by a matrix of parameters that I'll call a "state matrix" for brevity. Without this matrix model, you can't calculate the variance propagation equations, nor "Kalman gain" corrections to keep the model on-track, and the ordinary Kalman Filter idea is in trouble.
Control theory students know that a state matrix is easily obtained by looking at the last page of the homework handout. In real world applications, however, the problem of estimating parameter values for the "state matrix" is a whole lot harder. I suspect that most attempts to apply Kalman filtering are already in trouble at this point, well before reaching the less familiar territory of the variance model. It might be interesting to hear about difficulties others have had with this.
I hope that Jack gets back to describe clear and effective ways to deal with the tricky "model identification" fitting problem, or the rest won't matter much. Of course, this article was still just the beginning of the story...
Sign in to Reply
sharps_eng
2/17/2012 2:54 PM EST
I remember the Kalman making a bit of a comeback after Fuzzy Logic hit the headlines and fizzled out.
Truth is, both work for the cases that suit them, just the same as prior art from PID to digital filers that exploit delay-tolerant applications to create negative time.
Why is this typical engineering outcome not a surprise? The more tools in your toolbox, the more elegant the solutions.
But you still need to know how to use the basic tools for those application cases that don't have a happy relationship with a whizzy 'new skool' filter.
Sign in to Reply
JackCrens
2/24/2012 8:22 PM EST
Ridgerat, your last sentence says it all: We are still only at the beginning of the story.
Two points: First, it's true that the KF needs a model. I've tried to emphasize that point. In most uses of the KF for guidance & control, etc., the model is based on the laws of physics. But it needn't be that way -- a purely math-based model, like a polynomial or Fourier series, is a perfectly valid model. And yes, the recursive least squares in my examples fits your one-step predictive requirement. Look at the graphs again. At any given step, you have your best estimate of the state, which in the examples are the coefficients of a polynomial. Using those coefficients, you predict the value of f(x) you expect to get at the next measurement time. Then you compare it to the actual measurement, and update the estimate of state. See my Equation 3:
e = y - y_bar.
The y_bar is the prediction, y the measurement.
Second, please don't be misled by the notation. I've been using x as the independent variable, and y as the dependent variable, because that's the traditional form for both the function y = f(x), and the graphical notion of the x-y graph.
In the KF, the independent variable is something else; usually time, or the discrete equivalent of it. The state variables are x, and the measurables are y. I was going to get around to that, but I didn't want to throw a change of notation into the mix yet. You jumped ahead of me.
In the end, the difference between a least-square solution and the KF is almost exclusively the optimal use of the covariance matrix. We'll get around to that.
Sign in to Reply
cdhmanning
3/7/2012 6:02 PM EST
I think your statement that the model need not be rooted in physics is very true. Sometimes a completely unrelated physical analogy is a good model.
One thing though: ensure that the models actually do relate mathematically to the Real World physics.
For example, if you are modeling something analogous to acceleration, ensure that your model looks something like x/t^2. If you find you have a cube in there because it seems to work, then expect some instability down the track.
Sign in to Reply
jusboa
2/25/2012 3:13 AM EST
Hello. I enjoy the series about Optimal estimation a lot. But it takes so long the new article is released. When can I expect another contribution?
Again thanks a lot for thorough and comprehensible column.
Sign in to Reply
GLink
2/29/2012 8:31 AM EST
I too have very much enjoyed this series, but it's now a full year since the first article was posted. Every time you post a new one, I have to go back and re-read the first few just to get in context again - it's quite jarring.
If we give you enough positive feedback (good articles! we want more!), what are the odds we can get this series published at 1 article per month, rather than every 6 months?
Sign in to Reply
JackCrens
2/29/2012 3:53 PM EST
I'm very sorry to keep all my readers waiting. It's not my usual way of doing business. I'm well aware that, because I tend to write multiple related columns, I owe it to you guys to keep 'em coming.
In my defense, I can only say: Two really vicious computer malware attacks, one heart surgery, seven weeks of in-home therapy, and two sessions in civil court.
Please be patient, folks. I'm pedaling as fast as I can.
Sign in to Reply
Rich Krajewski
3/5/2012 11:27 AM EST
When I started spending more time in the country for the benefit of my son's health, I found my health improved, as well. Watching wild turkeys feed while you work on the computer can do a lot of good for your state of mind. I hope you scale to the level that your "system" can manage without damage to it.
Sign in to Reply
Patmac
3/5/2012 8:41 AM EST
Take your time man! Don't rush back. I came back to work too soon after Heart Surgery and have always regretted it. I still owe myself that 6 months.
The articles are important and very valuable to us, but you need to realize what is really important! And what you owe yourself.
Sign in to Reply