Join thousands of AI enthusiasts and experts at the Learn AI Community.

Publication

Latest

How does Google Maps use Graph Neural Networks?

Last Updated on June 28, 2021 by Editorial Team

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?

Photo by Isaac Mehegan onย Unsplash

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.

Signals for traffic condition, Source

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.

Dividing the route to multiple smallerย routes

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:

Google Maps ETA calculation workflow, Designed by Author, All Rights Reserved.
  • 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

Feedback โ†“