Taxisim — optimizing autonomous taxi size with reinforcement learning

This was my final-year project for my computer engineering degree — using reinforcement learning (a branch of AI) to optimize the size of individual vehicles in a simulated fleet of autonomous ride-sharing taxis roaming the streets of Manhattan.

Sample path of a simulated taxi over a four hour period, 8 a.m. to 12 noon. Pick-ups are shown in green, drop-offs in red.

Driverless taxis are one of those 'near future' technologies that will have a revolutionary impact if and when they finally become a reality. People have been anticipating their imminent arrival for decades and AI researchers have already devoted years of effort to developing efficient strategies for dispatching and managing autonomous taxi fleets.

An Overlooked Question

One important question that's been strangely overlooked in all this research is the optimal size for the individual vehicles within these fleets. Would single-seater microtaxis be the most efficient option or would driverless minibuses perform better instead? How can we predict their relative performance and what metrics should we use to measure it?

I decided to investigate these questions using a technique called reinforcement learning, a branch of AI which focusses on the behaviour of goal-seeking agents. These agents attempt to maximize their long-term reward by interacting with their environment and learning from the consequences of their actions. (Who doesn't like the idea of modelling autonomous taxis as predators roaming the streets in search of passengers to prey on?)

Results

The graph below shows the distribution of simulated taxi sizes over a 2,000 day training run.

Distribution of taxi sizes over 2,000 days of training.

What's happening here is that a fleet of 3,600 autonomous taxis is battling it out on the streets of a simulated Manhattan, competing with each other to pick up tiny electronic passengers generated using real-world demand data from New York City's Taxi and Limousine Commission. Each of these taxis has the (magical) ability to expand or shrink its seating capacity at will — at the beginning of each day each taxi gets to decide whether it wants to add a seat, remove a seat, or maintain its existing capacity. Over time the taxis experiment with different sizes and learn from their experiences using a reinforcement learning algorithm called q-learning.

Distribution of taxi sizes on the final day of training.

Don't worry, I won't make you read the full report — the end result is a solid preference for a seating capacity of about seven seats. (Though do see the report for all the necessary caveats!)

To be honest, I was a little disappointed by this result — I was hoping for a future filled with swarms of tiny single-seater taxibots. A future filled with autonomous minivans is comparatively meh 😕