How Google Uses AI And 'Supersegments' To Predict Traffic In Google Maps

According to Google, more than 1 billion kilometres are driven by people while using its Google Maps app, every single day.

In more than 220 countries and territories around the world, the app has been one of the most relied on for commuting and travelling.

And that is for many reasons.

The Google Maps app is default on Android phones. And on iOS devices, it's superior to Apple Maps. The service from Google is not only reliable and fast, but also packed with features that many people find them useful.

One of which, is its ability to predict estimated time of arrival (ETA).

This particular feature makes Google Maps so powerful. It's the critical feature that are especially useful when users need to be routed around a traffic jam, if they need to notify friends and family that they're running late, or if they need to leave in time to attend an important meeting.

This ETA feature is also useful for businesses like ride-hailing companies, and others.

Estimating ETA on Google Maps.
Credit: Google/DeepMind
"When you hop in your car or on your motorbike and start navigating, you’re instantly shown a few things: which way to go, whether the traffic along your route is heavy or light, an estimated travel time, and an estimated time of arrival (ETA). While all of this appears simple, there’s a ton going on behind the scenes to deliver this information in a matter of seconds."

According to this Google 101 post from Google, Google Maps uses aggregated location data to understand traffic conditions on roads all over the world.

But to predict make ETA, it needs to detect traffic jam, congestion, and other things that can contribute to travelling time. It needs to know whether at any point of the route, users will encounter traffic jam affecting their commute right now, and not like 10, 20, 30 minutes into the journey.

Google Maps deals with real time data, and this is where technology comes in to play.

To do this, Google Maps analyzes historical traffic patterns for roads over time.

For example, one pattern may show a road typically has vehicles traveling at a speed of 100kmh between 6-7am, but only at 15-20kmh in the late afternoon. Google can combine this historical data with live traffic conditions, and then use machine-learning technology to generate the ETA predictions.

The provider of the AI technology, is DeepMind, an Alphabet company that also operates Google.

"By partnering with Google, DeepMind is able to bring the benefits of AI to billions of people all over the world," wrote DeepMind on its web page.

According to the company, Google Maps uses DeepMind's AU to combine historical traffic patterns with live traffic conditions to predict ETAs.

"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 explained.

To allow the AI to work on the data, DeepMind and Google divided the roads into "Supersegments" consisting of multiple adjacent segments of road that share significant traffic volume.

The goal when creating this technology, is to create a machine learning system to estimate travel times using Supersegments, which are represented dynamically using examples of connected segments with arbitrary accuracy.

At first the two companies 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, the team were 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," DeepMind wrote.

Estimating ETA on Google Maps.
Credit: Google/DeepMind

To address the issue, the team needed models that could handle variable length sequences.

Using Graph Neural Networks, which extends the learning bias of AI imposed by Convolutional Neural Networks and Recurrent Neural Networks by generalizing the concept of “proximity”, the team can model network dynamics and information propagation into the system.

"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."

After much trial and error, the team finally developed an approach to solve the problem by adapting a reinforcement learning technique for use in a supervised setting.

The approach is called 'MetaGradients', which is capable of dynamically adapt the learning rate during training. This effectively allow the system to learn in its own optimal learning rate schedule.

"By automatically adapting the learning rate while training, our model not only achieved higher quality than before, it also learned to decrease the learning rate automatically. This led to more stable results, enabling us to use our novel architecture in production," DeepMind explained.

So here, what appears to be a simple ETA, is actually a complex strategy that involves prediction and determining routes.

Read: How An Artist 'Hacked' Google Maps Using 99 Mobile Phones And A Cart