How to land a Spaceship
On April 8th, SpaceX landed an unmanned rocket ship on a moving drone platform in the ocean. They did this remotely. This was a pretty big deal for nerds and nerd enthusiasts everywhere. Some reasons why:
- It's the first time the company has been able to pull off an ocean landing (after four previous attempts ended in failure).
- Most rockets are destroyed or lost after they launch into space, so entirely new rockets must be built for each mission.
- Now, they can potentially recover and reuse even more rockets in the future. And that could mean much greater cost savings (rockets cost up to $60M to make and only $200K to fuel - reusability eliminates a good chunk of that cost.)
- The company expects to land one-third of its rockets on land, and the rest at sea. So successful ocean landings are a big deal.
Future's march is steadily continuing forward.
The team behind SpaceX is a highly technical, extremely qualified group of scientists, engineers and mathematicians. You can be sure that whatever technology they use, it's top of the line. But the way things generally go is that people build on top of each other's work. That means that somewhere down the line they used some stuff that mere mortals like us can understand.
Thought experiment: You have a catapult and launch a pumpkin into the air. Let's say you wanted to track its every movement. Can you use some maths to figure out where in the sky that pumpkin is?
This is similar to what the folks at SpaceX needed to understand. And they did so using an extension of a modeling technique called a Kalman filter/smoother. To be clear, we cannot control the pumpkin while its majestically in flight, whereas SpaceX can control the trajectory of the rocket ship. But not that much (atmosphere, gravity and wind are formidable obstacles to control) and also it wastes fuel (i.e. money) to move it around.
In a nutshell, the Kalman filter is a recursive algorithm for predicting the future state of some physical object, by inferring parameters of interest from noisy/inaccurate measurements. Recursive means that it "calls" itself over and over again, updating at each time. And that's good because you can estimate the next state of the object in - wait for it - real time. Which we all know is the best time. Note that these days, in tech speak, real time is being supplanted by "online real time". Because gotta stay fresh.
How does it work? Before you google it don't get scared of the Greek letters. I promise they mean something to someone somewhere. For our purposes you just need to know the high level details. Say you're tracking something in space with a GPS tool.
1) The filter figures out the current position of the object, which is some combination of the previous position + some physics assumptions (say, the acceleration of the object). This is the recursive part.
2) The smoother uses all the historic data to make even better estimates than the filter. This is a more data intensive process than the filter and hence is optional
One of the important things to note with the Kalman filter is that it works even though our GPS tool might not produce perfect measurements (because it never does). The imperfections are assumed to be random, so we call it noise. The Kalman filter models this noise and accounts for it. Noise is just a fact of the real world and you can't ignore it.
Let's see an example of this applied to a serious task:
The "Punkin Chunkin" contest is an annual engineering challenge in which teams use trebuchets, catapults, and air cannons in a competition to see who can hurl a pumpkin the farthest possible distance. Check this video out for a visual.
Let's suppose we instrument a pumpkin with an accelerometer and a GPS, and we use an air cannon to launch the pumpkin straight up into the air. The device outputs measurements (position and acceleration) every millisecond. We use these measurements (which likely have some error) as an input to our Kalman filter/smoother.
The filter/smoother is used to track the position of the pumpkin as it majestically sails through space.
How well can we measure the pumpkin's position?
So we have some measurements of acceleration and position of this pumpkin. For example, here is the height and velocity of the pumpkin over time:
Notice that when the pumpkin is at its peak height, it's velocity is 0, and then goes negative (because velocity is speed AND direction, remember?).
So can we use the Kalman Filter to figure out the pumpkin's height and velocity using our measurement device and the pumpkin's previous position?
Yes we can (otherwise this post would be meaningless).
Whoa! That's a ridiculously close fit. Admittedly this is a very simple example so encoding the physics assumptions were trivial. But boy is that accurate.
So there you have it:
- Kalman filter algorithms (and their extensions) are recursive data processing algorithms
- It processes all available measurements regardless of how precise they are to make optimal estimates using:
- Knowledge of the measurement device
- Statistical assumptions of the noise and uncertainty
- As a bonus, because it's recursive, you don't need to store all the historic data when making the next estimate. Just the previous state.
- This is a huge win for people who care about data storage (which I think is everyone these days right?).
Until the next space landing!
Credit to Jeff Miller, Duke University, for providing data for this experiment