Google Maps a l’air magique. Depuis son lancement en 2005, des milliards de personnes l’ont utilisé, notamment pour trouver le meilleur itinéraire d’un trajet.
Ce qui semble irréel avec Google Maps, c’est que l’itinéraire est disponible immédiatement, que ce soit pour changer de quartier ou rejoindre le Groenland.
Chaque clic sur le bouton “Itinéraire” était un mystère. À mes yeux, il y avait trop de possibilités et d’inconnues pour qu’un ordinateur trouve la destination.
Dans ce cas, admettons que je veuille rejoindre la tour Montparnasse depuis la tour Eiffel à pied par le trajet le plus court.
Pour trouver un itinéraire sur une carte, il faut se baser sur la théorie des graphes, un domaine des mathématiques.
Les graphes
La théorie des graphes étudie les graphes. C'est une structure qui relie des objets entre eux. Les objets sont appelés sommets (ou nœuds) et leur relation est une arête.
Sur Maps, les lieux et intersections sont maintenant considérés comme des sommets. Les rues deviennent des arêtes.
La tour Eiffel devient A et la tour Montparnasse devient F. Il existe plusieurs intermédiaires à atteindre avant d'arriver à destination.
Le chemin de A à F demande de passer à travers les sommets, via les arêtes. L’objectif est de trouver quelles arêtes mènent à l’arrivée. Parmi ces chemins possibles, lequel est le plus court ?
Une solution est d’attribuer un poids à chaque arête. En additionnant les poids, le chemin le plus court est connu. Le poids peut correspondre à la distance en mètres ou au temps de trajet.
Google Maps attribue des poids différents selon le mode de transport (vélo, voiture, métros ...) ainsi que selon le trafic.
Même si les poids varient, cela permet de définir le chemin le plus court. Les options deviennent plus faciles à comparer.
En additionnant les poids, le trajet idéal se dessine naturellement parmi les chemins possibles :
Néanmoins, le monde est bien plus vaste et ouvert que ce schéma. En zoomant sur les routes autour de la tour Eiffel, il existe des centaines d’intersections, de routes et aucun panneau pour aider à trouver le chemin. Chaque intersection ouvre une nouvelle possibilité à étudier.
En 1959, le mathématicien Edsger Dijkstra se pose exactement la même question en faisant du shopping avec sa fiancée. Il crée un algorithme en 20 minutes pour résoudre le problème du chemin le plus court.
L’algorithme de Dijkstra
Pour trouver le chemin le plus court, l’algorithme choisit en priorité les options qui ont la distance cumulée la plus faible.
En reprenant le graphe depuis , l’algorithme étudie et . est choisi en premier, car 2 est la plus petite distance cumulée. Ensuite, et sont analysés. La priorité est à qui atteint . Pour s’assurer que c’est le meilleur chemin, est analysé avec et . Le meilleur chemin est donc .
En appliquant l’algorithme de Dijkstra pour le trajet entre la tour Eiffel et la tour Montparnasse, voici tous les nœuds étudiés.
Le trajet le plus court entre la tour Eiffel et la tour Montparnasse est maintenant visible !
Plus de 13 000 arêtes sont étudiées alors que le chemin idéal (en orange) fait seulement 3 km. Toute la partie sud-ouest de Paris est analysée, ce qui peut forcer l’ordinateur à consommer beaucoup de ressources ou à prendre plus de temps.
Pour des distances plus longues, cet algorithme peut montrer des limites. Toutes les directions sont traitées de la même manière, ce qui rallonge le temps nécessaire pour trouver le bon itinéraire.
Pour cela, Google Maps complète l’algorithme de Dijkstra avec A* (prononcé a-star).
A*
Moins de 10 ans après la publication de l’algorithme de Dijkstra, le chercheur en intelligence artificielle Nils Nilsson essaye d’améliorer la recherche de chemin pour un robot. Rapidement optimisé par d’autres chercheurs, l’algorithme A* est publié en 1968.
Cet algorithme est un complément de celui de Dijkstra. A* permet de rendre le calcul plus efficace. La distance avec le point de départ et d’arrivée est connue, ce qui simplifie le calcul.
A* utilise une estimation mathématique (aussi appelée heuristique) de la distance restante.
Les chemins étudiés en priorité sont ceux qui ont le coût total estimé le plus faible, c’est-à-dire le coût déjà calculé + la distance restante estimée.
Pour estimer la distance restante, le meilleur moyen est de déterminer la distance à vol d'oiseau.
Calculer une distance à vol d'oiseau
Sur une courte distance, appliquer le théorème de Pythagore à partir des coordonnées fonctionne très bien. Néanmoins, la Terre n’est pas plate. Les distances plus longues deviennent inexactes.
La formule de Haversine permet de calculer la distance à vol d’oiseau dans une sphère. Au lieu de mesurer une ligne droite sur une carte plate, elle mesure l’arc le plus court à la surface du globe.
Concrètement, elle utilise les latitudes et longitudes des deux points. Ces coordonnées sont converties en angles, puis la formule estime l’angle entre les deux lieux depuis le centre de la Terre. En multipliant cet angle par le rayon de la Terre, on obtient une distance en kilomètres.
Popularisée au début du XIXe siècle, elle était déjà très utilisée en navigation.
Maintenant que nous connaissons la distance à vol d’oiseau, l’algorithme A* peut prioriser les chemins les plus prometteurs, en actualisant la distance restante estimée à chaque nouveau nœud étudié.
Etant donnée que A* priorise les nœuds dont le coût total estimé est le plus faible, l'algorithme analyse moins de nœuds.
Sur la même carte, A* se dirige rapidement dans la bonne direction et visite moins d’intersections.
Le trajet idéal est le même que celui trouvé par l’algorithme de Dijkstra. A* a deux avantages :
- Le trajet idéal est trouvé plus rapidement
- Moins de nœuds sont analysés, ce qui réduit les calculs nécessaires pour l’itinéraire
Limites
Si l’estimation guide mal la recherche, l’algorithme peut être moins efficace, notamment si le chemin idéal part dans la direction opposée.
Ces algorithmes ne sont pas les seules raisons de l’adoption globale de Google Maps. Le fait que le poids des arêtes s’adapte en fonction du trafic permet d’éviter les bouchons aux heures de pointe. Les millions d’adresses disponibles font que nous n’avons plus à entrer les coordonnées.
Bien que Google Maps a changé notre manière de se déplacer, l'application se base sur des découvertes qui existent depuis longtemps. D'ailleurs, elles seront toujours utilisées dans le futur. Au-delà des cartes, ces systèmes continueront d’être utiles pour les nouvelles technologies, comme la voiture autonome ou la robotique.
Sources
Wikipedia - Théorie des graphes
UDIT - The mathematics behind Google Maps
Algorithme de Dijkstra (publication originale)
At the core of Google Maps: Dijkstra's Algorithm
DataCamp - A* Algorithm
Google Maps 101 - How AI helps predict traffic and determine routes