Comment Google Maps fait pour estimer encore mieux votre heure d'arrivée
L'avantage de disposer d'une filiale reconnue pour son savoir-faire dans le domaine de l'intelligence artificielle, c'est que l'on peut faire profiter ses autres services des percées qu'elle obtient dans ce secteur.
Ces dernières années, on a ainsi appris que Google utilise les méthodes de DeepMind pour optimiser la consommation énergétique de ses centres de traitement de données, en lui donnant accès au système de refroidissement. Dernièrement, c'est son célèbre service de cartographie et de navigation qui a gagné en efficacité, grâce à un nouveau procédé pour prédire la circulation et, donc, mieux diriger l'internaute.
Ce nouveau procédé a fait l'objet d'une double publication, la première généraliste sur le blog de Google, l'autre plus pointue sur le site de DeepMind. Ce qu'il ressort de l'annonce conjointe entre la maison-mère et sa filiale, c'est que les nouveaux modèles mis en œuvre dans Maps améliorent la justesse des heures d'arrivée estimées (« ETA ») en temps réel de 16 à 51 % selon les cas choisis par Google.
Quelques villes tout autour du monde ont été prises en exemple, et à chaque fois un gain est relevé. Parfois, celui-ci est plutôt modeste (16 % à Londres ou Copenhague, ou bien 21 % à New York, Berlin ou Bangkok), parfois il est vraiment significatif (43 % à Sydney, 37 % à Osaka ou bien 31 % à Singapour). Dix-neuf localités sont présentées -- aucune indication n'est donnée pour une ville française.
Des paramètres très divers pris en compte
Le calcul de l'ETA d'un trajet ne se fonde pas que sur le trafic actuel que Google Maps observe via les smartphones de sa communauté (en se basant notamment sur le déplacement des smartphones dans les véhicules, via leur position GPS), mais doit estimer le trafic à venir sur la route qui sera empruntée par le conducteur, qui varie entre autres selon le moment de la journée, et même selon le jour de l'année.
C'est là que les algorithmes de DeepMind entrent en jeu. Il s'agit de mouliner à la fois ce qui est observé en temps réel avec ce que Google a déjà observé historiquement, en termes de circulation, pour toutes les voies concernées.
Cela parait simple dit comme cela, mais le modèle de prédiction de Google inclut d'autres facteurs : l'horaire de circulation, les limitations de vitesse, 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, et ainsi de suite.
« Ce processus est complexe », fait observer DeepMind, car le simple paramètre de l'heure de circulation peut bouger significativement d'un jour à l'autre, même s'il semble d'une apparente régularité. C'est typiquement le cas de l'heure de pointe : certes, celle-ci survient toujours tôt le matin, vers 7-8h, puis le soir, vers 18-19h. Mais son déclenchement précis peut varier dans la semaine, ou au cours de l'année.
Avant d'être introduites dans les réseaux de neurones artificiels de DeepMind, sa grande spécialité, toutes ces informations sont réparties sur des segments de la voie publique que le système découpe, et fait « converser » entre eux lorsqu'ils sont adjacents. Ces segments sont générés selon un certain volume de trafic qu'ils se partagent, afin de refléter de façon cohérente la circulation locale.
« Cependant, étant donné la taille dynamique des supersegments, raconte DeepMind, 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 ». Il leur a donc fallu utiliser un réseau de neurones artificiels spécifique.
Nouvelle approche pour Maps : le Graph Neural Network
Son nom ? Graph Neural Network. « Dans la modélisation du trafic, nous nous intéressons à la façon dont les voitures circulent dans un réseau de routes, et le Graph Neural Network peut modéliser la dynamique du réseau et la propagation de l'information », écrit l'entreprise. Cela, alors que la construction des supersegments nécessite de traiter des téraoctets de données au préalable.
L'architecture du Graph Neural Network « nous permet 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 », poursuivent les chercheurs. La capacité d'un Graph Neural Network « à généraliser sur des espaces combinatoires est ce qui donne à notre technique de modélisation son efficacité ».
Le Graph Neural Network repose sur une architecture d'apprentissage automatique, une méthode de travail courante dans l'intelligence artificielle. Il s'agit d'un système qui « apprend» à partir des données qui lui sont soumises et des modèles qu'il peut déceler. Selon DeepMind, le Graph Neural Network peut « mieux exploiter la structure de connectivité du réseau routier ».
« 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 », est-il indiqué. Ce qui est pratique quand l'on sait qu'un même trajet peut emprunter des voies très diverses.
Une fois moulinées, ces données d'estimation sont croisées avec Google Maps et surtout avec le trajet demandé par l'utilisateur. Les différents itinéraires sont alors évalués, basés sur le travail en amont réalisé par les réseaux de neurones artificiels, et le plus pertinent d'entre eux est alors retourné à l'usager, avec une estimation de l'heure d'arrivée. Heure qui pourra être révisée au fil du parcours.