By partnering with Google, DeepMind is able to bring the benefits of AI to billions of people all over the world. From reuniting a speech-impaired user with his original voice, to helping users discover personalised apps, we can apply breakthrough research to immediate real-world problems at a Google scale. Today we’re delighted to share the results of our latest partnership, delivering a truly global impact for the more than one billion people that use Google Maps.
People rely on Google Maps for accurate traffic predictions and estimated times of arrival (ETAs). These are critical tools that are especially useful when you need to be routed around a traffic jam, if you need to notify friends and family that you’re running late, or if you need to leave in time to attend an important meeting. These features are also useful for businesses such as rideshare companies, which use Google Maps Platform to power their services with information about pickup and dropoff times, along with estimated prices based on trip duration.
Researchers at DeepMind have partnered with the Google Maps team to improve the accuracy of real time ETAs by up to 50% in places like Berlin, Jakarta, São Paulo, Sydney, Tokyo, and Washington D.C. by using advanced machine learning techniques including Graph Neural Networks, as the graphic below shows:
To calculate ETAs, Google Maps analyses live traffic data for road segments around the world. While this data gives Google Maps an accurate picture of current traffic, it doesn’t account for the traffic a driver can expect to see 10, 20, or even 50 minutes into their drive. To accurately predict future traffic, Google Maps uses machine learning to combine live traffic conditions with historical traffic patterns for roads worldwide. This process is complex for a number of reasons. For example - even though rush-hour inevitably happens every morning and evening, the exact time of rush hour can vary significantly from day to day and month to month. Additional factors like road quality, speed limits, accidents, and closures can also add to the complexity of the prediction model.
DeepMind partnered with Google Maps to help improve the accuracy of their ETAs around the world. While Google Maps’ predictive ETAs have been consistently accurate for over 97% of trips, we worked with the team to minimise the remaining inaccuracies even further - sometimes by more than 50% in cities like Taichung. To do this at a global scale, we used a generalised machine learning architecture called Graph Neural Networks that allows us to conduct spatiotemporal reasoning by incorporating relational learning biases to model the connectivity structure of real-world road networks. Here’s how it works:
We divided road networks into “Supersegments” consisting of multiple adjacent segments of road that share significant traffic volume. Currently, the Google Maps traffic prediction system consists of the following components: (1) a route analyser that processes terabytes of traffic information to construct Supersegments and (2) a novel Graph Neural Network model, which is optimised with multiple objectives and predicts the travel time for each Supersegment.
The model architecture for determining optimal routes and their travel time.
The biggest challenge to solve when creating a machine learning system to estimate travel times using Supersegments is an architectural one. How do we represent dynamically sized examples of connected segments with arbitrary accuracy in such a way that a single model can achieve success?
Our initial proof of concept began with a straight-forward approach that used the existing traffic system as much as possible, specifically the existing segmentation of road-networks and the associated real-time data pipeline. This meant that a Supersegment covered a set of road segments, where each segment has a specific length and corresponding speed features. At first we trained a single fully connected neural network model for every Supersegment. These initial results were promising, and demonstrated the potential in using neural networks for predicting travel time. However, given the dynamic sizes of the Supersegments, we required a separately trained neural network model for each one. To deploy this at scale, we would have to train millions of these models, which would have posed a considerable infrastructure challenge. This led us to look into models that could handle variable length sequences, such as Recurrent Neural Networks (RNNs). However, incorporating further structure from the road network proved difficult. Instead, we decided to use Graph Neural Networks. In modeling traffic, we’re interested in how cars flow through a network of roads, and Graph Neural Networks can model network dynamics and information propagation.
Our model treats the local road network as a graph, where each route segment corresponds to a node and edges exist between segments that are consecutive on the same road or connected through an intersection. In a Graph Neural Network, a message passing algorithm is executed where the messages and their effect on edge and node states are learned by neural networks. From this viewpoint, our Supersegments are road subgraphs, which were sampled at random in proportion to traffic density. A single model can therefore be trained using these sampled subgraphs, and can be deployed at scale.
Graph Neural Networks extend the learning bias imposed by Convolutional Neural Networks and Recurrent Neural Networks by generalising the concept of “proximity”, allowing us to have arbitrarily complex connections to handle not only traffic ahead or behind us, but also along adjacent and intersecting roads. In a Graph Neural Network, adjacent nodes pass messages to each other. By keeping this structure, we impose a locality bias where nodes will find it easier to rely on adjacent nodes (this only requires one message passing step). These mechanisms allow Graph Neural Networks to capitalise on the connectivity structure of the road network more effectively. Our experiments have demonstrated gains in predictive power from expanding to include adjacent roads that are not 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. 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. This ability of Graph Neural Networks to generalise over combinatorial spaces is what grants our modeling technique its power. Each Supersegment, which can be of varying length and of varying complexity - from simple two-segment routes to longer routes containing hundreds of nodes - can nonetheless be processed by the same Graph Neural Network model.