Google Maps, le service de cartographie en ligne de la firme de Mountain View, propose une fonctionnalité permettant d’en savoir plus sur l’ETA : l’estimation de l’heure d’arrivée à un endroit prédéfini par l’utilisateur. La précision de cette estimation repose sur quelques technologies dont celle des graph neural networks (GNN) qui sont fournies par DeepMind, la filiale de Google spécialisée dans l’IA. Retour sur les techniques exploitées par Google Maps pour estimer au mieux l’heure d’arrivée.
Objectif : améliorer la précision de la prédiction de l’heure d’arrivée sur Google Maps
Faire en sorte que l’application Google Maps puisse estimer au mieux l’heure d’arrivée d’un usager à la minute près. C’est le défi que ce sont lancés plusieurs chercheurs de DeepMind, de Google, accompagnés également de chercheurs de Waymo, d’Amazon, de Facebook AI ou de Sea AI Lab. Leurs recherches ont fait l’objet d’une publication qui explique comment la prédiction de l’heure d’arrivée est possible avec précision.
Le calcul de l’ETA ne se fonde bien évidemment pas uniquement sur le trafic routier que Google Maps observe grâce aux mouvements des smartphones via leur position GPS : il faut aussi estimer le trafic à venir sur la route qui sera empruntée par le conducteur, un paramètre qui varie selon le jour ou le moment de la journée.
Tout ceci nécessite de tenir à la fois compte du trafic actuel et des données passées pour prédire les éventuels ralentissements à venir. Parmi les paramètres observés figurent notamment l’horaire de circulation, les limitations de vitesse, mais aussi la qualité de la chaussée (si elle est pavée ou non, par exemple), la présence d’éventuels chantiers sur la route, la survenue de circonstances particulières (un embouteillage, un carambolage, etc.), des déviations, etc.
Simple en apparence, l’analyse d’un réseau routier ouvert est selon DeepMind extrêmement complexe, car la prédiction ne dépend pas uniquement de l’analyse des segments de route empruntés mais également des segments environnants :
“étant donné la taille dynamique des supersegments, nous avons eu besoin d’un modèle de réseau neuronal formé séparément pour chacun d’entre eux. Pour le déployer à grande échelle, nous aurions dû former des millions de ces modèles, ce qui aurait été un défi considérable en matière d’infrastructure.”
La solution pour une EPA précise en temps réel : le graph neural network
Ne pouvant pas exploiter les réseaux de neurones conventionnels, les équipes de DeepMind se sont penchées sur le GNN qui permet selon la firme de “mener un raisonnement spatio-temporel en incorporant des biais d’apprentissage relationnel pour modéliser la structure de connectivité des réseaux routiers du monde réel”.
Les GNN permettent selon DeepMind de conserver une fidélité à grande échelle. La précision est difficile à maintenir, car les modèles sont si volumineux et complexes que la seule façon de les former est de les diviser en segments ou en lots. L’introduction de ce type de segmentation peut créer des problèmes de convergence. C’est pour cela que DeepMind a conçu des réseaux de neurones capables de traiter les super segments :
“Chaque supersegment, qui peut être de longueur et de complexité variables — de simples routes à deux segments à des routes plus longues contenant des centaines de nœuds — peut néanmoins être traité par le même modèle de Graph Neural Network.”
Ci-dessous, on peut remarquer comment les rues sont segmentées par Google :
Ainsi, avant d’être introduites dans les GNN, toutes les informations sont divisées en super segment. Chacun de ces “morceaux de route” est généré selon un certain volume de trafic qu’ils se partagent afin de refléter la réalité de la circulation. Voici un schéma qui explique pas à pas comment Google Maps fonctionne afin de proposer une EPA précise :
Selon les villes du monde, la précision diffère : à Londres ou à Copenhague, la précision du modèle a augmenté de 16 % tandis que dans d’autres villes comme Sydney ou Osaka, le système a vu sa précision monter en flèche avec une augmentation respective de 43 et 37 %. Malheureusement, aucune donnée n’est disponible pour les villes françaises.
