How does Google Maps use Graph Neural Networks?

Author(s): Daksh Trehan

Deep Learning, Algorithms

Traffic & ETA prediction with Graph Neural Networks

Gone were the days, when travelers used to look for long, rough maps to chose their route. Now, they rely upon a popular tool, Google Maps.

Every day, around 1 billion kilometers are traveled using Google maps that are present in more than 220 countries worldwide. When you hop in your cars/bikes and start navigating, Google maps helps you by predicting traffic, an estimated travel time, an estimated time of arrival(ETA), and the best route for you to take.

But, behind this super-functionality of Google Maps, there is a pinch of AI.

How does Google determines Live traffic?

Google maps are smart, they can easily predict the traffic conditions on roads all over the world. When people navigate with Google Maps, their aggregate location, the route, the speed at which they’re traveling are all recorded by Google and are used to help users who might be taking that route soon.

By computing the speed of various users at a particular route, the AI can easily determine whether the route is affected by the traffic jam and thus helping future commuters.

If a lot of Google Maps users are stuck at a particular portion of the route, it means that route might suffer traffic jams, and thus AI colors that part as red, similarly for slow moving traffic AI colors that part to yellow.

But, Google Maps can only show the live location and can’t predict the future condition of traffic on the road.

Information collected by Google Map to predict live traffic:

• Live location of the user.
• Total cars, their speeds, conditions of roads, feedbacks of users.
• Traffic history for the specific route at a specific time.

How Google Maps calculate ETA and offers the best route?

ETA(Estimated Time of Arrival) is one of the highlighted features of Google Maps. Google Maps tries to calculate the different routes to reach the destination and then upon calculating the ETA, it suggests users the best route. And that’s where Machine Learning comes into play.

To calculate the ETA for each route, the algorithms divide the route into smaller routes and then calculate ETA for each route separately.

But, how ETA is calculated for each path?

Step 1:

To calculate ETA for a particular segment, we need the road segment, the previous path.

We could use feed the above-mentioned requirements to Feed Forward Neural Networks, but usually, Feed Forward Neural Networks require independent samples, but in practicality, the traffic on one segment of the road can directly influence the traffic on another road which eventually would lead to inaccuracies.

The data fed by us would be sequential, and hence RNNs/Transformers could be of great help. But, RNNs require a high amount of data. If we wish to use RNNs for Google Maps, it would need different data for each route.

Even if, we’re able to gather the data, it would require high computation power to learn the relation between each route from scratch.

The optimal solution could be Graphs.

Each city can be represented in the form of graphs where each road segment can be distinguished as a vertex and each node can be defined as an edge.

Node Network → Embeddings → Feedforward Neural Network → ETA for each segment

Step 2:

After deploying each city as a graph, to learn the routes we require embeddings.

For each node, an embedding would be defined and updated.

Since the routes are interconnected, the embeddings would be created, the states would be updated and new embeddings would be created until we reach the destination.

For complex paths:

A + B + AC + BC → encoder-decoder → embedding for C

Each new message will be created for a single pass for a single node.

Since the nodes are interconnected, each node has the following information:

• Its neighbors.
• Its neighbor’s neighbors.

The above information helps to create a relationship between each node with different nodes and thus helps us to improve our accuracies.

After X passes, the final embeddings for the route will be generated which can be updated in dictionaries with road vector as the key and information and relations as the values.

Traffic information + Speed Limit + Accident + Previous record → Feedforward Neural Network → Compute ETAs.

Final Work Flow:

• Start.
• Find some path.
• Determine segments.
• Road Embedding mappers.
• Add real-time feature → Feed Forward Neural Network → ETA
• Calculate sum of all ETAs.

Conclusion

Google Maps is a powerful tool and bliss for travelers. The combination of Graph Neural Networks and the use of embeddings help the algorithm to calculate ETA and return with the best route for users.

If you like this article, please consider subscribing to my newsletter: Daksh Trehan’s Weekly Newsletter.

References:

[1] Traffic prediction with advanced Graph Neural Networks | DeepMind

[2] This Is How Google Maps Works — Pritesh Pawar

[3] Google Maps 101: How AI helps predict traffic and determine routes (blog.google)

Find me on Web: www.dakshtrehan.com

Follow me at LinkedIn: www.linkedin.com/in/dakshtrehan

Read my Tech blogs: www.dakshtrehan.medium.com

Connect with me at Instagram: www.instagram.com/_daksh_trehan_

Want to learn more?

How is YouTube using AI to recommend videos?
Detecting COVID-19 Using Deep Learning
The Inescapable AI Algorithm: TikTok
GPT-3 Explained to a 5-year old.
Tinder+AI: A perfect Matchmaking?
An insider’s guide to Cartoonization using Machine Learning
How Google made “Hum to Search?”
One-line Magical code to perform EDA!
Give me 5-minutes, I’ll give you a DeepFake!

Cheers

---

How does Google Maps use Graph Neural Networks? was originally published in Towards AI on Medium, where people are continuing the conversation by highlighting and responding to this story.

Published via Towards AI