Author(s: Daksh Trehan Algorithms Traffic & ETA predictions with Graph Neural Networks The days when people used long and rough maps to choose their routes are gone. They now rely on Google Maps, a widely used tool. Around 1,000,000 kilometers of travel are made every day using Google Maps, which are available in over 220 nations worldwide. Google maps allows you to navigate by pre-planning traffic and estimating travel times, estimated arrival time(ETA), as well as determining the most efficient route. Google Maps is super functional, but there’s a little bit of AI behind it. What is Google’s algorithm for determining Live traffic? Unsplash photo by Isaac Mehegan. Google Maps are so smart that they can accurately predict traffic conditions all around the globe. Google Maps records the location of all users when they navigate using Google Maps. It also tracks the travel speed and route. This information is used by Google to assist others who may be planning on taking the same route. The AI calculates the speeds of all users on a route to determine if it is affected by traffic jams and can help future commuters. Google Maps colors a portion red if there are many users stuck on a section of the route. AI also colors parts that move slowly yellow if they have traffic jams. Signs of traffic conditions, Source However, Google Maps cannot show traffic conditions in real time and is unable to predict future traffic. Google Map uses live location information to forecast traffic. The total number of cars and their speed, road conditions, as well as feedbacks from users. The traffic history of a particular route, at a given time. Google Maps determines the ETA for you and recommends the most efficient route. Google Maps’ ETA (Estimated Time Of Arrival) feature is one of its most prominent features. Google Maps calculates the most efficient route to the destination. It then recommends the optimal route after calculating the ETA. Machine Learning is where Machine Learning comes in. The algorithms split the route into smaller routes, then compute the ETA separately for each one. Divide the route into multiple smaller routes. But how is each route calculated? First, you need to know the segment of the road that is being used for the calculation. Although we could feed these requirements to Feed Forward Neural Networks (which usually requires independent samples), in practice, traffic can influence traffic on other roads, which in turn would cause inaccuracies. Our data would not be in a sequential order, so RNNs/Transformers might be of tremendous help. RNNs, however, require large amounts of data. RNNs are required to collect different information for every route in order to be able use them for Google Maps. Although we could gather data it would take a lot of computation power to determine the relationship between routes. Graphs could provide the best solution. Each city could be represented as graphs, where each segment of road can be identified as a vertex. Every node can also be described as an edge. Node Network – Embeddings – Feedforward Neural Network – ETA for each section Step 2: To learn about the routes, embeddings are required after deploying each city in a graph. An embedding for each node would be created and then updated. Because the routes are interconnected the embeddings will be created and the states updated until the destination. Complex paths will require A+ B + AC + BC + BC – Encoder-Decoder – embeddings for C. Each message created is for one node. Each node is interconnected and has the following information: The neighbors. Each node has information about its neighbor. This information allows us to establish a relation between different nodes. It also helps us improve our accuracy. The final embeddings of the route can be created after X passes. These embeddings are then updated in dictionaries using road vector as the key, and other information and relationships as the values. Traffic information + Speed limit + accident + Previous record. Feedforward neural network – Calculate ETAs. Final Work Flow: Google Maps ETA Calculation workflow. Designed by the Author. All Rights Reserved. Start. Locate a path. Determine segments. Road Embedment mappers. Add real-time features – Feed forward neural network – ETA Calculate the sum of all ETAs Google Maps can be a great tool for travellers. Combining Graph Neural Networks with embeddings allows the algorithm calculate ETA, return and determine the most convenient route. Subscribe to Daksh’s Weekly Newsletter if you enjoyed this article. 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? YouTube uses AI to suggest videos. Let’s toast how Google Maps uses Graph Neural Networks! This story was first published on Medium by . People are responding and highlighting it. Published via
What is the use of Graph Neural networks in Google Maps?
