How SpaceX land first stage boosters

Animations and Mathematics

(Some of the technical details, as well as a neural network approach are detailed here.)
I loosely followed a discussion on how SpaceX land their first stage rocket boosters, and thought I would try to understand how the boosters are controlled to land so accurately.
There are lots of different aspects to this question:
I'm just going to discuss how they work out what to wiggle and when, during flight, in order to get their rocket to land on its bottom.
I'm not affiliated with SpaceX, and my information is based on a handful of papers on the subject in the public domain. My aim is to explain the method in a way that does work, at least in my simulations, and is hopefully understandable.

Image from SpaceX, with copyright waived.

SpaceX make rockets that go to orbit. As far as we're concerned, these rockets have three bits: The side booster(s) detach from the main body of the rocket, and with a small amount of fuel remaining, make a controlled landing either near the launch site, or on barges out at sea. Like this:

The booster

The booster is a 42m long cylinder with fuel inside, and nine engines on the bottom. It also has grid fins on the top and thrusters on the top.

The booster is controlled in four ways:

The Task

The task here starts when the boosters detach from the main body of the rocket. They then become separate vehicles, which need to The way to solve this task, from the onboard computer's point of view, is to send signals continuously to the engines, thrusters and grid fins, to make sure this happens.

How to solve it.

There are several ways to solve this, for instance:

Convex optimisers

An optimiser is a simple beast. It takes a list of statements about a problem, and spits out the solution to the problem. My aim here is to convince you that convex optimisers are not complicated to use or understand, and so this G-FOLD algorithm isn't actually all that difficult.

For instance, you may tell it to find a series of 3 numbers, separated by 2 or less from the previous, with the first not more than 0, and and the last number as large as possible. It should then output 0,2,4 as the solution.

All you have to do to use the optimiser is choose what to optimise, and write down two things: A scoring system, and a list of constraints.

In this article, I'm going to set up the problem as follows: So the variables I'm going to optimise are:

vx0The x-velocity at time 0 seconds
vy0The y-velocity at time 0 seconds
vz0The z-velocity at time 0 seconds
thrust0The absolute thrust at time 0 seconds
vx1The x-velocity at time 1 seconds
vy1The y-velocity at time 1 seconds
vz1The z-velocity at time 1 seconds
thrust1The absolute thrust at time 1 seconds
vx2The x-velocity at time 2 seconds
vy2The y-velocity at time 2 seconds
vz2The z-velocity at time 2 seconds
thrust2The absolute thrust at time 2 seconds
vxN-1The x-velocity at time N-1 seconds --- at the end of the flight
vyN-1The y-velocity at time N-1 seconds --- at the end of the flight
vzN-1The z-velocity at time N-1 seconds --- at the end of the flight
thrustN-1The absolute thrust at time N-1 seconds

Now we have to tell the optimiser what the scoring system is. There are several scores that make sense: You could try to minimise the fuel used, or you could minimise the distance from the last position in the trajectory to the target, or perhaps minimise the velocity at the end.

In this article, we're going to minimise fuel used. It's an arbitrary choice, and other choices may work better in real life. We tell the optimiser:

Note that this isn't complicated yet: We're just minimising the total sum of the thrust we're going to use.

Next we have to write down a list of constraints. These are rules that the optimiser has to obey.

Rule 1: The initial velocity

Let's say we're on the booster, and we're moving downwards at 100 metres per second. The optimal useful trajectory has to have, at time t=0 (now), that vy = -100. Otherwise we can't use the trajectory: it's not our trajectory, it's just a trajectory.

Rule 2: The final velocity

We want to be stopped at the end of the trajectory.

Rule 3: Position

During the first second, our average x velocity is (vx0 + vx1)*0.5 --- the average of the two velocities at either side of the second.

We also know that the distance, in the x direction, that we'll move is going to be equal to this (because we have 1 second timesteps).

We can add these 1-second steps up, and get the total distance we'll move over the trajectory:

distance x = 0.5 vx0 + vx1 + vx2 + ... + vxN-2 + 0.5 vxN-1

Let us imagine now that we are at a known current height, and that the landing site is 100m in the x direction away, and level in the z direction. This gives us the following constraints:

Rule 4: Acceleration

At the moment, the optimiser could pick basically any trajectory it wanted: It could start here, move to the finish line, and stop there, and also declare that the total fuel is zero: We haven't told it anything about thrust or acceleration.

We can tell the optimiser to be aware of how thrust works as follows. Let's pick the first timestep as an example:

Note that this is just Pythagoras' theorem applied to the velocity difference. The constant, g, is gravity. This constraint is for the first timestep. We add one constraint per timestep, except for the last, resulting in N new constraints here.

The main effect of this is that the optimiser now has to keep track of what the thrust magnitudes are: It can no longer take an arbitrary path to the destination and declare that the total thrust is zero.

Rule 5: Max thrust

We have to limit the thrust to what the rocket can actually do.

This is a set of N constraints: we tell the optimiser that at every second, the total thrust for that second must be below an upper bound.

Note that this constraint isn't exactly what SpaceX, or the other papers use, since they model the vehicle getting lighter, and therefore the acceleration caused by thrust getting stronger as time goes on.

Let's see how this all works

Ok, so we have a way to calculate a trajectory. There are several things to look at: What is the trajectory, and more importantly, does a vehicle using this trajectory actually land?

If we take an example test problem, and run it through the optimiser, we get one complete trajectory.

This isn't the path that the rocket would take, it's just what the optimiser *thinks* will happen in its dreams: Just a plan.

Next we need to see if it works in practice. Rather than build a 42m rocket, which planning laws prohibit, we can run a simulation. What we do is run a simulation with short timesteps (eg., 50 ms), and re-run the entire optimisation every second or so. The optimiser says something like "In the first second, accelerate along the (1.0,0.5,0.3) vector", and you can take that advice and use it for the first 20 or so timesteps.

Note that the optimiser's useful output is just the thrust vector, it doesn't say how to fire the RCS thrusters to spin the vehicle.

I've implemented a basic PD controller that won't allow the vehicle to tilt more than 45' that tries to orient the vehicle with future planned thrust directions.

If we do that, we get the path the (simulated) rocket actually does take --- not just the optimisers plan:

Note that the black line, in the video, is the plan that the rocket intends to take. Even the best-laid plans often go amiss, though, and these ones are no different: The optimiser isn't fed exactly the same physics as in real life: for instance, it doesn't know that the rocket tilt is unlikely to go outside 45', and it doesn't know that the thrust direction can't change instantly. As a result, the plan does change a fair bit during the flight. This is something that any real rocket will face in real life. Consequently, plans always do need to be re-optimised periodically.

This does ok, but it's not upright when it hits its target, and when it hits the target, it doesn't really know it, so it keeps buzzing around re-planning how to get back to the target. We can improve this by adding a few more common-sense rules to the problem the optimiser solves each second.

Other rules

You could add other rules, such as that the thrust has to be accelerating the vehicle roughly upwards: This prevents the rocket from wasting fuel by accelerating towards the target more than it should. This would happen if the number of timesteps is minimised. Another rule might be that the thrust direction shouldn't change too much from one second to the next (which I haven't implemented, but it wouldn't be difficult).

Another quite extreme rule that I've added is that in the last second or two, the vehicle has to be travelling downwards (with almost no side-ways motion) at a certain speed.

When you do these, and use that in the same old simulation as before, with the usual PD controller for the rocket RCS thrusters, you get this:

Comparison with SpaceX

The way I solved this differs from SpaceX in several ways. Firstly, I am trying to illustrate how convex optimisers are used to generate trajectory plans, and hopefully you can see how flexible the approach is. It is certain that the actual constraints used by spaceX are quite different to the ones I've chosen. For instance, some of the papers discuss constraining the trajectory to finish off inside a landing cone --- rather than a narrow landing cuboid that I have used --- which probably saves fuel.

There are, however, a number of things that I've brushed over which will be quite a bit more complicated for SpaceX than for me: About the last point: My optimisation typically takes around a second, maybe half a second, on my laptop. I also run it several times to search for the smallest number of timesteps that produces a feasible result --- although this could be done in parallel with just 10 cores quite easily in the same time. Either way, I couldn't easily get an optimal trajectory recalculated in under a second. It may be that the trajectory should be re-optimised more often than that: Basically this works as a reaction time, and it seems possible that you need reaction times faster than 1 second in order to guarantee landing the thing.

I think that there are a suite of tricks that SpaceX use to speed up getting this optimal trajectory, and I can imagine that it would be things like storing bits and pieces off line, or re-using old trajectories as starting points for future trajectories, but to be honest, I don't know.

One thing I also think is that even if 1-second optimisation times are ok for a 42-meter long rocket, they wouldnt' be ok for a 1-meter long model rocket: Scaling laws mean that it's probably easier to optimise real-time trajectories for large objects than small.

Some of the technical details, as well as a neural network approach are detailed here.

Literature review

Here's a quick literature review in an order that perhaps makes sense to the reader. No guarantee that this is in any way complete. These all seem to be free to the public.

Lossless Convexification of Nonconvex Control Bound and Pointing Constraints of the Soft Landing Optimal Control Problem (Behçet Açıkme¸se, John M. Carson III, and Lars Blackmore) and Lossless convexification (Lars Blackmore)
These two sites discuss, in particular, the way of overcoming what seems like an inconvexity in the problem due to various thrust limits that were ignored in my article. These two sites are of particular interest because they are by Lars Blackmore who was involved in the original development of the algorithm, and its use in actual landers. He works at SpaceX.

G-FOLD: A Real-Time Implementable Fuel Optimal Large Divert Guidance Algorithm for Planetary Pinpoint Landing (by a team from the JPL)
This paper talks about the algorithm, called G-FOLD, in terms of what it can do for mars landers, pointing out how much better it is than the algorithms that were used half a century ago in the Apollo program.

Fuel-Optimal Spacecraft Guidance for Landing in Planetary Pits (Neal S. Bhasin)
This gives a lot more mathematical detail about how convex optimisation can solve trajectories, and has some cool pictures, and is also focussed on landing on Mars and places like that.

Landing Rockets Propulsively (Jonny Hyman)
This has a video of G-Fold being used in KSP.

ECOS: An SOCP Solver for Embedded Systems (Alexander Domahidi, Eric Chu and Stephen Boyd)
This is the conical solver that I used in this article.

Some of the technical details, as well as a neural network approach are detailed here.

Other Articles:

Moon Formation

A Kotlin N-Body code, and lots of animations of the collision between Earth and a hypothetical Theia that people think created the moon.

BodyWorks: Neuromuscular Activity / Muscle EMG

An interactive simulation showing how nerves travel to and down muscles, and how this gets picked up by EMG sensors.

Generating Plant-like Structures Using Neural Networks

© Hugo2015. Session @sessionNumber