AI Researchers Introduce A Graph Neural Network Estimator for ETA Prediction at Google Maps

Web mapping services like Google Maps are excellent tools for dynamically navigating portions of the Earth, especially in urban areas. These tools are not only used by everyday users looking for (best) routes between waypoints but also by businesses that rely on accurate mapping features for food delivery services and many more. 

Given current road network conditions and a certain candidate route between waypoints, accurate prediction of Expected time of arrival (ETA) prediction is a vital task. With accurate predictions, traffic participants can make better judgments, potentially avoiding crowded areas and reducing the overall time spent stuck in traffic. It’s vital to remember that effective ETA predictors must be able to reason about future conditions that aren’t always evident from the current road condition.

A team of researchers from DeepMind, Waymo, Google, Amazon, Facebook AI, Sea AI Lab propose a new graph neural network model for ETA prediction. The proposed model is deployed in production at Google Maps. Compared to the prior production baseline, the new model has resulted in considerable reductions in negative ETA outcomes across all trips worldwide.

The team explains that because the road network is readily characterized by a graph of road segments and intersections, graph representation learning techniques, notably graph neural networks (GNNs), are suited to ETA prediction.

Providing anticipated trip time given a user-provided beginning point and a route indicated by a prior system is known as arrival time estimation. This is challenging to solve since it requires both spatial (as collected within the road network) and temporal information (the evolution of traffic conditions over time). 

The model is based on the Graph Network architecture and follows the concept of the encodeprocess-decode. This helped the team better to align itself with the iterative nature of traffic calculations and tracking systems. It is known that improving this alignment helps GNNs to generate a different distribution of graphs.

While the model’s main components are based on the Graph Network paradigm, ETA prediction in production invites highly unstable training conditions over multiple batches of requests, especially over routes of varying scales. The researchers used reinforcement learning’s MetaGradients methodology to dynamically modify the learning rate during training and stabilize it across several unequal query batches, resulting in a production-ready GNN model.

Historically, GNNs are widely used to estimate traffic conditions. In the case of road networks, such time-series often correlate to historical speeds measured at regular time periods. While the proposed GNN model only processes static inputs and does not anticipate future speeds, having some idea of future traffic flow behavior is likely to be useful for ETA prediction.

Furthermore, there are numerous patterns inherent in the topology of the road network that may be very useful in anticipating traffic flow. Similar themes in a region’s road network are likely to correspond to similar traffic dynamics. Therefore automatically detecting and compressing them could be beneficial. For this, the researcher has directly modified proven unsupervised GNN approaches such as graph auto-encoders and deep graph infomax to permit such effects and demonstrated benefits to more accurate ETA predictions.

In addition to this, different types of heuristical computations over road networks may need distinct data aggregation methods. The shortest path-finding, for example, would need optimizing the signals in a node’s neighborhood, but flow estimates might necessitate summing such signals. The team investigated various combinations of GNN aggregation functions inspired by the primary neighborhood aggregation design and found them helpful across many modeling situations.

Paper: https://arxiv.org/pdf/2108.11482.pdf

Suggested