Collision avoidance

Once every aircraft could taxi on its own, the next problem was obvious: they drove straight into each other. On the ground, a controller’s main job is keeping them apart, so aircraft need to queue behind each other and give way at intersections.

This was the hardest part of the whole project. It took about three weeks, from early to late February, and most of that time went into an approach that never worked.

Letting the aircraft learn it

My first idea was to let the aircraft learn to give way themselves, with multi-agent reinforcement learning. Every aircraft is an agent deciding one thing each frame: stop or go. I used centralised training with decentralised execution. Training is centralised: every aircraft is a copy of the same learner, sharing one neural network and one memory of past experience, so whatever one aircraft learns, they all learn. Execution is decentralised: each aircraft decides for itself, from only what it can see around it. Each decision stands in for an instruction a controller would give, which could be passed on to a pilot or carried out automatically. The setup also copes with any number of aircraft, which matters when they spawn and leave all the time.

Each aircraft saw its own speed and how far it was from its next and final waypoints. It also saw the two nearest aircraft within about 250 metres: their speed, distance, angle, and how close each was to its own goal. Whoever was closer to its final waypoint had priority.

To tell when giving way mattered, each aircraft had a cone of vision: 45° either side of its nose, out to about 100 metres.

The rewards depended on what was in the cone, and who had priority:

The training was extremely noisy and never settled. Looking back, the rules were too rigid. A cone and a priority flag can’t describe most of what actually happens at an intersection.

A model that predicts the future

What I really wanted the reward to know was whether two aircraft were going to collide. So I trained an LSTM to predict where an aircraft will be in a few seconds.

To get data, I ran the simulation for about eight hours with the taxiing model driving: 200 episodes of 20 aircraft each. Every half a second it recorded each aircraft’s position, heading, speed, state and distance to its next waypoint. That came to just over 1.2 million examples and 2.26 GB.

The model takes the last 10 of those snapshots, so the last five seconds, and predicts where the aircraft will be 3, 5 and 7 seconds later. It’s two stacked LSTM layers of 128 units. Training stopped itself after 38 epochs, once the validation loss stopped improving, at 0.0009. On average, each prediction was within about 25 metres of where the aircraft actually went. I also snapped the predictions onto each aircraft’s planned route, so they could never drift off the taxiway.

As a plain rule, it worked immediately: if two predictions overlap, the aircraft further from its goal gives way. But at this point I wanted the aircraft to learn that, so I used the LSTM as a judge instead, rewarding the agents when they matched what the predictions said they should do.

It didn’t work. The aircraft learned to almost never stop. Moving towards the runway paid off often, and stopping rarely did.

Why they wouldn’t stop

To check that, I looked at what was actually in the memory the agents learned from. I expected about 91% of decisions to be “go” and 9% to be “stop”, which is fine on its own. The problem was in how good those decisions were:

So there was almost nothing to learn good stopping from. Part of the reason was how episodes ran. At the start, every aircraft is at its stand, so there’s no traffic and no reason to stop. The first collision then reset everything, so the busy moments where stopping mattered barely happened. The first fix was to remove only the aircraft that collided and let the rest carry on.

Fixing what they learned from

Balanced Experience Replay sorts every decision into four buckets, by whether it was a stop or a go and whether it was right or wrong, and trains on the same amount from each.

It overcorrected. Seeing rare cases so often made the aircraft so cautious that they wouldn’t move even when they had priority, and the reward kept falling.

Prioritised Experience Replay instead learns most from the experiences the model predicted worst, the surprising ones. It was more than ten times slower, so one run took up to six hours. But it gave the best results of anything I tried… at first.

Then it would collapse. Given enough time, the reward peaked and crashed, sometimes recovered briefly, and crashed again, and afterwards the aircraft hardly ever stopped. My guesses were exploding gradients or the model forgetting what it had learned. Clipping the gradients and strengthening the sampling correction over time didn’t fix it.

Everything else

I tried three more things:

• Frame skipping: holding each decision for 10 frames instead of deciding every frame. The aircraft became overly cautious.
• A smaller memory, down to 25,000 decisions. They stayed just as cautious.
• One reward for everyone, shared by all the aircraft. Training got noisier, and nobody stopped.

None of it produced aircraft that gave way properly. I talked it through with colleagues and professors, who agreed the approach was sound, but nobody could say why it failed. That’s part of what makes deep reinforcement learning hard: when it fails, it rarely tells you why.

By this point I was exhausted. I’d tried so much, and spent so long on this one part. I started to wonder whether I was overcomplicating it, or whether my models weren’t complicated enough, even though it already felt far too complicated for something I’d thought would be simple. I began looking into graph neural networks, and the more I read, the more potential they had, but far more than this problem needed. That’s when I realised I was overcomplicating it. I needed to keep it simple, get everything working together first, and come back to improve it later.

A simple yes or no

Stop or go is a yes-or-no question, so maybe it didn’t need reinforcement learning at all. I used the LSTM rule to label 120,000 situations as stop or go, half of each, and trained standard classifiers on them.

The first versions scored over 90%, but they leaned almost entirely on one or two features, so they weren’t really reading the situation. That called for some feature engineering. The one that helped most was projected distance: how far ahead of you another aircraft is, along the direction you’re facing, so one off to your side barely counts.

The best set used only the two nearest aircraft: their speed, projected distance, angle, and who had priority. The decision tree leaned most on the angle to the other aircraft and the projected distance.

The numbers looked fine. In the simulation, though, they were more cautious than any of the reinforcement learning models: aircraft stopped after pushback and never moved again. A classifier only sees one moment. It has no idea whether a situation is getting better or worse.

What worked

In the end I went back to the plain rule from the start of the LSTM work. The LSTM predicts where every aircraft will be. When two predictions overlap, the aircraft further from its final waypoint brakes and gives way, and the other carries on.

I’d avoided it at first because the LSTM only knows Birmingham’s layout, so it can’t move to another airport without retraining. But it was the only approach that actually worked, and that mattered more for a proof of concept.

The distances come from the size of the aircraft. A give-way triggers when predictions come within about 90 metres of each other. With each aircraft about 42 metres long, that leaves about 50 metres to stop in, and keeps queueing aircraft at least one aircraft length apart. That’s close to the roughly 50 metres that real-world guidance gives as a minimum. In the simulation, it removed every collision, and it produced realistic queues, since aircraft naturally stop behind each other.

What it can’t do

The LSTM only knows what it saw in training, and it never saw a go-around. When an arrival has to abort its landing and fly around, the predictions get pulled back towards the taxiways it knows.

The other gap is two aircraft meeting head-on on the same stretch of taxiway. Neither can get past the other, and with no rerouting, they wait forever. It only showed up in long stress tests. I designed a fix, detecting conflicts by taxiway segment and rerouting with a modified Dijkstra’s algorithm, but didn’t build it.