DeepMind today detailed a collaboration with Google that reportedly improved the accuracy of real-time driving ETAs in Google Maps and Google Maps Platform APIs by up to 50% in some regions, including Berlin, Jakarta, São Paulo, Sydney, Tokyo, and Washington D.C. Through the use of machine learning techniques, DeepMind claims it minimized traffic prediction inaccuracies by incorporating relational learning biases that model road networks.
Google Maps analyzes live traffic for roads around the world to calculate ETAs, which gives the platform a picture of current traffic but doesn’t account for conditions drivers can expect to see 10, 20, or even 50 minutes into their route. Machine learning enables Google Maps to combine traffic conditions with historical patterns for roads worldwide, and to achieve this at scale, DeepMind developed an architecture called graph neural networks that conducts spatiotemporal reasoning.
Google Maps divides road networks into “supersegments” consisting of multiple adjacent segments of road that share significant traffic volume. A route analyzer processes terabytes of traffic information to construct the supersegments while the graph neural network model, which is optimized with multiple objectives, predicts the travel time for each supersegment.
The graph neural network treats each local road network as a graph, where the route segments correspond to nodes and edges exist between consecutive segments and those connected via intersections. The supersegments are in effect road subgraphs sampled at random in proportion to traffic density, linked by a message-passing algorithm that learns the effect on edge and node states.
Because the graph neural network can generalize, each supersegment can be of varying length and complexity, from two-segment routes to longer routes containing hundreds of nodes. DeepMind says its experiments have shown gains in predictive power from expanding to include adjacent roads that aren’t a part of the main road. “For example, think of how a jam on a side street can spill over to affect traffic on a larger road,” the company wrote in a blog post. “By spanning multiple intersections, the model gains the ability to natively predict delays at turns, delays due to merging, and the overall traversal time in stop-and-go traffic.”
MetaGradients dynamically adapt the graph neural network’s learning rate during training to let the system learn its own optimal learning rate schedule. According to DeepMind, by automatically adapting the learning rate while training, the model not only achieves higher quality than before but learns to decrease the learning rate automatically, leading to more stable results.
“Thanks to our close and fruitful collaboration with the Google Maps team, we were able to apply these novel and newly developed techniques at scale,” DeepMind continued. “Together, we were able to overcome both research challenges as well as production and scalability problems. In the end, the final model and techniques led to a successful launch.”
DeepMind’s work with the Google Maps team follows the lab’s other partnerships with Google product divisions, including an effort to improve the Google Play Store’s discovery systems. Beyond Google, DeepMind has contributed algorithms, frameworks, and methodologies to Waymo to bolster the latter’s autonomous driving systems.
