People are dependent on Google Maps for precise traffic forecasting and estimated times of arrival (ETAs). These are vital utilities that are particularly useful when you require to be routed to circumvent a traffic jam, if you are required to provide notifications to family and friends that you’re going to be a bit late, or if you require to start in time to reach a critical meeting. These functions are also vital for enterprises like rideshare entities, which leverage Google Maps to drive their services with data about pickup and drop-off times, in conjunction with price estimates on the basis of trip distance and duration. 

Scientists and analysts at DeepMind have collaborated with the Google Maps team to enhance the precision of real-time ETAs by nearly half in localities such as Berlin, Sao Paulo, Jakarta, Tokyo, Sydney, and Washington D.C. by leveraging sophisticated machine learning strategies which includes graph neural networks. 

How does Google Maps forecast ETAs? 

To estimate ETAs, Google Maps undertakes analysis of current traffic information for road areas around the globe. While this information provides Google Maps a precise perspective on current traffic, it doesn’t take into account the traffic a commuter can look forward to 10, 20, or even 45 minutes into their journey. To precisely forecast upcoming traffic, Google Maps leverages machine learning to bring together live traffic situations with traffic patterns from history for roadways globally. This procedure is complicated for a variety of reasons. For instance – although rush-hour unanimously occurs each morning and evening, the precise time of rush hour experiences considerable variance on a daily basis and a monthly basis. Other factors such as road quality, speed limitations, accidents, and closed off segments of the road can also contribute to the intricacy of the forecasting model. 

DeepMind collaborated with Google Maps to assist in enhancing the precision of their ETAs globally. While Google Maps predictive ETAs have been precise on a consistent basis, >97% of trips, they collaborated with the team to reduce the remainder inaccuracies even more – at times by more than half in locations such as Taichung. To do this at an international level, they leveraged a generalized machine learning system referred to as Graph Neural Networks that facilitate the conducting of spatiotemporal reasoning by integrating relational learning biases to go about modelling the connectivity structure of real-world roadways. This is how it functions: 

Demarcating the planet’s roads into supersegments 

They demarcated the roadways into supersegments which included several adjacent segments of road that share considerable traffic volumes. Presently, the Google Maps traffic forecasting system includes the following components:  

1. A route analyser that undertakes processing of TBs of traffic data to develop supersegments, and 
2. A novel graph neural network, which features optimisation with several objectives and forecasts the travel time for every supersegment 

On track to novel ML architectures for traffic forecasting 

The biggest hurdle to resolve when developing a machine learning framework is to forecast travel times leveraging supersegments is of an architectural nature. How does one go about representing dynamically sized instances of connected segments with random precision in such a manner that a singular model can accomplish success? 

The preliminary proof of concept started with a direct approach that leveraged the current traffic framework to its fullest extent, particularly the current segmentation of road-networks and the connected real-time data pipeline. This implied that a supersegment encompassed a grouping of road segments, where every segment has a particular length and related speed features. To start with, they undertook training of a singular completely connected neural network framework for each supersegment. These preliminary outcomes showed promise, and illustrated the possibility in leveraging neural networks for forecasting travel times. But, provided the dynamic sizes of the supersegments, there was a necessity for an independently trained neural network framework for every supersegment. In order to go about deploying this at scale, they were faced with training millions of these models, which would have presented a huge infrastructure challenge. This compelled them to investigate models that could manage variable length sequences, like Recurrent Neural Networks  (RNNs). But, integrating subsequent structure from the road network proved to be tough. Rather, they came to the decision to leverage Graph Neural Networks. By modelling traffic, we’re fascinated in how vehicles flow through a network of roadways, and Graph Neural Networks can go about modelling network dynamics and data propagation. 

The model treats the local roadway network like a graph, where every route segment correlates to a node and edges are present amongst segments that are consecutive on the same roadway or connected via an intersection. Within a Graph Neural Network, a message passing algorithm is carried out in which the messaging and the influence on node and edge states are understood by neural networks. From this perspective, supersegments are road subgraphs, which were arbitrarily sampled proportionally to the density of traffic. A singular model can thus receive training leveraging these sampled subgraphs, and can then have deployment at scale. 

Graph Neural Networks go about extending the learning bias put forth by Convolutional Neural Networks and Recurrent Neural Networks through generalization of the theory of proximity, facilitating to have random complicated connections to manage not just traffic ahead of behind us, but also along intersecting and adjacent roadways. With a graph neural network, adjacent nodes transmit messaging to one another. By retaining this structure, a locality bias is imposed where nodes will find it simpler to be reliant on adjacent nodes. These mechanisms enable Graph Neural Networks to take advantage of the connectivity structure of the roadway network more efficiently. The experiments have illustrated gains in forecasting power from expanding to integrate adjacent roadways that are not included in the main road. For instance, visualize how a jam on a side street can boil over to impact traffic on a bigger road. Through spanning several intersections, the model obtains the capability to natively forecast delays at turns, delays owing to merging, and the cumulative traversal time in stop-and-go traffic. This capacity of Graph Neural Networks to generalize over combinatorial spaces is what confers upon the modelling strategies its capabilities. Every supersegment, which can vary drastically in length and can be of varying intricacy, ranging from simplistic two-segment routes to bigger routes consisting of hundreds of nodes – can nevertheless be processed by the identical Graph Neural Network model. 

From fundamental research to production-ready ML models 

A significant hurdle for a production machine learning framework that is often ignored in the research setting consists of the massive variability that can be present throughout several training runs of the same model. While small variations in quality can merely be rejected as poor initializations in more research-oriented settings, these minimal incongruencies can have a massive influence when taken together across millions of end-users. As such, producing the Graph Neural Network robust to this variance in training took focus as the model was put forth into production. It was discovered that the Graph Neural Network are especially sensitive to alterations in the training syllabus – the main reason of this instability being the large variance in graph structures leveraged over the course of training. A singular batch of graphs could consist of anywhere from small two-node graphs to large >100 node graphs.  

Following a lot of trial and error, they produced a strategy to find a solution to this issue through the adaptation of a novel reinforcement learning strategy for leveraging in a supervised scenario. 

When training an ML framework, the learning speed of a system details how plastic or modifiable to new data – it is. Scientists usually minimize the learning pace of their models over the course of time, as there is a sacrifice between knowing new things and forgetting critical features that have already been learned, just like the advancement from childhood to adulthood. At the start, they made utilization of an exponentially decaying learning rate schedule to go about stabilising the parameters after a pre-defined duration of training. They also looked into and undertook analysis of model ensembling strategies which have proved their efficacy in prior work to see if they could minimize model variance amongst training runs.  

Ultimately, the most efficient strategy to tackle this issue was leveraging MetaGradients to dynamically adapt the learning pace over the course of training, basically allowing the system learn its own optimum learning rate schedule. Through automatic adaptation of the learning rates during training, the framework not just accomplished increased quality in contrast to before, it also learned to minimize the learning rate automatically. This had the consequence of outcomes with increased stability, facilitating us to leverage our novel architecture in production. 

Making models generalise via customised loss functions 

While the eventual objective of the modelling framework is to minimize errors amongst travel estimates, it was discovered that leveraging of a linear combo of multiple loss functions (weighted appropriately) largely enhanced the capability of the model to generalize. Particularly, they devised a multi-loss objective making use of a regularizing factor on the model weights L_2 and L_1 losses on the global traversal duration, in addition to individual Huber and negative-log likelihood (NLL) losses for every node within the graph. By bringing together these losses, they were able to provide guidance to their model and prevent overfitting within the training dataset. While the measurements of quality within training did not alter, enhancements observed during training converted more directly to held-out tests sets and to the end-to-end experiments. 

Presently they are looking into if the MetaGradient strategy can also be leveraged to alter the composition of the multi-component loss-function over the course of training, leveraging the reduction in travel estimate errors as a guiding metric. This draws inspiration from the MetaGradient efforts that have proven effective within reinforcement learning, and preliminary experiments demonstrate promise. 

Collaboration 

Owing to the close and positive collaboration DeepMind experienced with the Google Maps team, they were capable of applying these novel and newly developed strategies at scale. They were able to surpass both research hurdles in addition to scalability and production issues. Ultimately, the final model and strategies had the effect of a successful launch, enhancing the precision of ETAs on Google Maps and Google Maps Platform APIs around the globe.