This post originally appeared on Split’s blog here.
Remember feeding quarters into the classic arcade game Pac-Man? Do you have fond memories of maneuvering a chomping yellow pie chart around two-dimensional mazes, gobbling up cherries and avoiding Blinky, Pinky, Inky, and Clyde? How about that joyous, joy-stick-filled day when you finally mastered that last level, Pac-Man ate his ultimate dot, and, at long last, Ms. Pac-Man was introduced?
The answers to these questions are likely: of course, sort of, and definitely not.
As it turns out, Pac-Man is pretty hard. In fact, mathematicians have proved that the game is not just hard, it’s “NP-hard,” meaning that winning Pac-Man is as challenging as some of the hardest problems that optimization scientists spend their careers trying to solve. More than that: Pac-Man is impossible to beat – after 255 successful rounds, a bug in the original computer code unceremoniously ends Pac-Man’s gluttony.
At Split, where I am the science team lead, we work every day to invent, refine, and deploy computer algorithms to solve the “traveling salesperson problem,” seeking the shortest path through a series of set points. Just as Pac-Man seeks the fastest, most-direct path to eat as many dots, power-ups, and 8-bit fruit as possible, Split is constantly directing its fleet of cars and vans through city streets. Routes are optimized to pick up and drop off as many riders as possible and to avoid slow-moving traffic, like Pac-Man dodges ghosts. It’s impossible to know exactly when and where the next pickup will be or next pocket of roadway congestion will emerge, so the routes are recalculated to respond in real time, similar to how you choose Pac-Man’s movements based on the random nature of cherries and Blinky.
Computers are really good at solving such hard problems. They don’t get tired or bored when they are asked to systematically search through a seemingly endless set of possibilities. IBM’s Deep Blue trumped Kasparov in chess. Google’s DeepMind recently bested the world’s top Go player, a game that is a googol (that’s 10 to the 100) times more challenging than chess. And artificial intelligence can handily win Pac-Man.
Split’s algorithm is tuned to find routes that maximize the use of vehicles’ seats and swiftly get riders where they need to go. It’s like toggling a massive matrix of joysticks, each controlling one of many Pac-Men with each moving around a maze of city streets. Each Pac-Man doesn’t simply eat cherries, but instead moves them from where they are to where they have to go. This is where Split and the real Pac-Man differ: while Pac-Man’s motivation is strictly more and more points, Split’s motive is sustainability. Split selects smart routes that reduce miles traveled, move people quickly, and use up all the seats. Winning Split means moving more people with fewer resources.
To visualize a Split car’s journey around Washington, D.C., we’ve animated a typical morning commute, Pac-Man-style (above). One Split driver scoops up riders, moves them, and drops them off, navigating a labyrinth of streets and avenues along the way. Unlike Pac-Man, this game never ends: there’s always another rider to move from point A to point B.
Photos, from top: Pac-Man street art in Bilbao, Spain (Roberto Latxaga, Flickr, Creative Commons). A Pac-Man pick-up and drop-off route (Split).