Google Maps, the Mountain View company’s online mapping service, offers a feature that allows users to learn more about ETA: estimating the time of arrival at a location predefined by the user. The accuracy of this estimate is based on several technologies, including graph neural networks (GNN), which are provided by DeepMind, the Google subsidiary specializing in AI. Let’s take a look at the techniques used by Google Maps to better estimate the time of arrival.

Goal: Improve the accuracy of arrival time prediction on Google Maps

To make sure that the Google Maps application can best estimate the arrival time of a user to the minute. This is the challenge that several researchers from DeepMind, Google, accompanied by researchers from Waymo, Amazon, Facebook AI or Sea AI Lab have set themselves. Their research was the subject of a publication that explains how the prediction of the arrival time is possible with precision.

Of course, the calculation of the ETA is not only based on the road traffic that Google Maps observes thanks to the movements of the smartphones via their GPS position: it is also necessary to estimate the upcoming traffic on the road that will be used by the driver, a parameter that varies depending on the day or time of day.

All this requires taking into account both current traffic and past data to predict possible future slowdowns. Among the parameters observed are the traffic schedule, speed limits, but also the quality of the road (whether it is paved or not, for example), the presence of any construction sites on the road, the occurrence of particular circumstances (a traffic jam, a pile-up, etc.), diversions, etc.

Seemingly simple, the analysis of an open road network is, according to DeepMind, extremely complex, as the prediction depends not only on the analysis of the road segments used but also on the surrounding segments:

“given the dynamic size of the supersegments, we needed a neural network model trained separately for each of them. To deploy it on a large scale, we would have had to train millions of these models, which would have been a considerable infrastructure challenge.”

The solution for real-time accurate APE: the graph neural network

Unable to harness conventional neural networks, DeepMind’s teams turned to the GNN, which the firm says allows it to “conduct spatio-temporal reasoning by incorporating relational learning biases to model the connectivity structure of real-world road networks.”

GNNs allow DeepMind to maintain fidelity at large scale, according to DeepMind. Accuracy is difficult to maintain because the models are so large and complex that the only way to train them is to split them into segments or batches. Introducing this type of segmentation can create convergence problems. That’s why DeepMind designed neural networks that can handle super segments:

“Each supersegment, which can vary in length and complexity – from simple two-segment routes to longer routes containing hundreds of nodes – can nonetheless be processed by the same Graph Neural Network model.”

Below, you can notice how streets are segmented by Google:

So, before being fed into GNNs, all the information is divided into super segments. Each of these “road chunks” is generated according to a certain volume of traffic that they share in order to reflect the reality of the traffic. Here is a step-by-step diagram that explains how Google Maps works to provide an accurate LFS:

Depending on the city in the world, the accuracy differs: in London or Copenhagen, the accuracy of the model has increased by 16% while in other cities like Sydney or Osaka, the system has seen its accuracy skyrocket with an increase of 43% and 37% respectively. Unfortunately, no data is available for French cities.

Translated from Comment Google Maps parvient à être aussi précis pour prédire l’heure d’arrivée de ses usagers ?