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.

Autonomous or driverless taxis are one of the few 'near-future' technologies we can safely predict will have a transformative impact on society over the next couple of decades, particularly on city life. People have been anticipating their arrival for a very long time and it turns out that AI researchers have already devoted years of effort to developing effective strategies for dispatching and repositioning autonomous taxi fleets. One important question has been largely overlooked though and that's the optimal size for individual vehicles within these fleets.

I decided to investigate this question using reinforcement learning, a branch of AI which focusses on 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?)

The project report is of the show-your-workings variety so it's on the long and stilted side but it does contain some interesting graphs, like this one:

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

This graph shows the distribution of taxi sizes over a 2,000-day training run. 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.

The end result is a solid preference for a seating capacity of about seven seats. (See the accompanying report for all the necessary caveats.)

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