New AI Algorithm Beats Even the World's Worst Traffic

• Updated on: 2018-10-07
• Read original article here

The height of individual vs. collective irrationality has to be automobile traffic. We build roadways around the assumption that we as individual human actors will behave in ways that appear to reward those behaviors at the level of individuals but wind up harming the collective's goal of moving many cars through a limited amount of space as quickly as possible. Witness how a single greedy merge, for example, can send out a cascade of brake lights leading to a further wave of merges, some of which will themselves be greedy (careless). There really is no truly individual behavior in traffic and yet people are people. 

Fixing this is among the promises of driverless cars. If we can push humans and their tendencies out of the loop, and put cars under the control of cooperative AI systems, we might just be able to nuke traffic, or at least severely mitigate it. Imagine: less congestion, less pollution, fewer accidents, less roads, and more time spent not driving. That's the pitch, anyhow, but the actual systems remain largely future-tense, even as driverless cars ease into the present.

To this end, computer scientists at Nanyang Technological University in Singapore have developed a new intelligent routing algorithm that attempts to minimize the occurrence of spontaneous traffic jams—those sudden snarls caused by greedy merges and other isolated disruptions—throughout a roadway network. It's both computationally distributed and fast, requirements for any real-world traffic management system. Their work is described in the April issue of IEEE Transactions on Emerging Topics in Computational Intelligence.

Route-finding is a natural branch of computer science. What we're really talking about is graph theory, a field that's been kicking out algorithms since well before electronic computers even existed. The problem is that routing algorithms can be extraordinarily complex for even small numbers of possible paths and small numbers of actors. Traffic, however, deals with a whole lot of routes and a whole lot of cars (and other "agents," such as traffic lights).

The Nanyang researchers' algorithm starts off by just assuming that, given enough traffic density, shit is going to happen. Someone is going to make a greedy merge—something is going to cause enough of a traffic perturbation to result in a network breakdown. Breakdown in this context is a technical-ish term indicating that for some period of time the traffic outflow from a segment of roadway is going to be less than the traffic inflow. 

"We assume that the traffic breakdown model has already been given, and the probability of traffic breakdown occurrence is larger than zero (meaning that traffic breakdowns would occur), and our goal is to direct the traffic flow so that the overall traffic breakdown probability is minimized," Hongliang Guo and colleagues write. Put differently, "our objective is to maximize the probability that none of the network links encounters a traffic breakdown."

So, the goal of the algorithm is this maximization, which reduces to a fairly tidy equation. It then becomes a machine learning problem. Things get pretty messy at this point, but just understand that we're taking the current traffic load, adding an unknown additional load that might enter the network at any time, and then coming up with probabilities of network breakdown at each of the network's nodes or intersections. Crunch some linear algebra and we wind up with optimal routes through the network.   

Crucially, Guo and co. were able to come up with some mathematical optimizations that make this kind of calculation feasible in real-time. They were able to demonstrate their algorithm in simulations and are currently working on a further analysis with BMW, which is providing a vast trove of data from its Munich car-sharing fleet. 

This may not be as distant a technology as it might seem. As it turns out, only 10 percent of cars in a network need to be driving according to the optimizations for those optimizations to have a positive effect on the entire network. Breathe easy: You're free to continue driving like an unoptimized asshole.