Artificial Intelligence - Computer Science Hub

DeepMind, an AI company which was acquired by Google in 2014 is now helping Google Maps to improve ETA(Estimated Time of Arrival) predictions. Whenever a user uses Google Maps to navigate from one location to other then Google Maps provides an ETA prediction based upon different factors like time, day of week, area etc. ETA can be really useful in case you need to reach at some location by a certain time, as it can help you to plan your journey beforehand. As ETA is quite useful for users of Google Maps, that’s why Google have always been working on improving their systems for making better predictions about ETA. For improving ETA predictions DeepMind used GNN models - Graph Neural Networks. Using these models they achieved a huge accuracy increase in prediction of actual ETAs. Research Paper published by DeepMind - ETA Prediction with Graph Neural Networks in Google Maps Below is a table listing how much ETA predictions improved using GNN models. Google Maps ETA Improvements using DeepMind GNN ModelsLocationPercentage(%) improvement in prediction actual ETATaichung City51Sydney43Osaka37Orlando34Singapore31DenverWashington, DC29Chicago27Toronto26Sao Paulo23San JoseLas VegasJakarta22BerlinNew YorkBangkok21Chennai20LondonCopenhagen16 What is ETA in Google Maps? ETA(Estimated Time of Arrival) can be described as estimated time for traveling between two locations as predicted by Neural Networks. Whenever a user enters information about going from one location to another, the first thing which Google Maps does is to predict at least 3 routes between locations provided by the user. Then Neural Networks kicks in and provides ETA predictions for each route to the user, based upon this user can make a choice which route to choose for navigating from one location to another. Why is predicting ETA a difficult problem in Machine Learning? Predicting ETA for travelling from one location to another using the road is difficult as real time information like current traffic condition, weather etc. need to be processed by Machine Learning system at the same time. Moreover for Machine Learning training, it's quite difficult to set which of these affecting parameters is more significant as compared to other parameters. That's why it's quite difficult to build models which can accurately guess ETA. Why DeepMind used GNN Models for ETA Prediction? DeepMind used GNN models for ETA prediction because the road network is naturally modelled by a graph of road segments and intersections. So ETA prediction is amenable to graph representation learning approaches, particularly graph neural networks(GNNs). How does DeepMind improve ETA predictions for Google Maps? For achieving accurate travel time estimates, DeepMind modelled the road network using Supersegments which are sequences of connected road segments that follow typical traffic routes. For a given starting time, DeepMind learns the travel time of each supersegment for different fixed time horizons into the future. As serving time, the sequence of supersegments that are in a proposed route are queried sequentially for increasing horizons into the future. This process specifically involves sequentially using prediction time of an earlier supersegment to determine relevant fixed horizons for the next supersegment and interpolating between prediction times of fixed horizons to arrive at a travel time for the next supersegment. This process enables accurate travel time estimates in a scalable way, taking into account both information captured within the road network and evolution of traffic conditions over time.