La navigation des piétons dans la ville

Le système de navigation de Silicon City utilise une implémentation de l’algorithme A* (A Star) [1], très populaire dans les intelligences artificielles actuelles.

Il est possible pour un piéton d’utiliser les trottoirs disponibles le long des routes, ainsi que les passages piétons aux intersections. Ici, chaque case est pondérée d’une valeur de 1, la vitesse étant constante pour le citoyen, ce qui se traduit en une augmentation de 1 à chaque passage d’une case à l’autre lors du calcul du trajet. Pour un automobiliste, le concept reste le même mais les voies empruntées en voiture auraient une valeur inférieure à 1, ce qui rends une portion de route plus favorable à emprunter. Au même titre, une case avec un feu rouge se verra pondérée d’une valeur supérieure à 1, en fonction de la durée d’attente, pour rendre le chemin emprunté plus long.

Voici une description simplifiée du calcul du meilleur trajet pour un piéton qui souhaite se rendre de son domicile (en jaune à gauche) à son travail (en vert, à droite).

Le chemin commence à 0 sur la case de départ. Il commence par deux choix, le chemin A en empruntant la case directement située au nord ce celle de départ et en longeant le trottoir vers l’est, et le chemin B, en prenant la case située à l’ouest de celle de départ et en empruntant un passage piéton en direction du nord.

Chaque chemin est parcouru en parallèle, case après case. Arrivée à la 8^ème étape, le chemin A offre un embranchement avec 2 solutions : L’algorithme divise alors le chemin A en 2, l’un continuant vers l’est, l’autre vers le nord. Chacun des 3 chemins continue d’être analysé case après case.

A la 17^ème étape, le chemin B rencontre le chemin A-2. Le chemin B a couté 17 déplacements pour en arriver là alors que l’autre, seulement 16. Le chemin B est alors abandonné, n’étant pas le meilleur pour arriver jusque-là.

A la 25^ème étape, le chemin A-1 sera à son tour divisé en deux. Le premier d’entre eux A-1-1 rencontrera à son tour le chemin A-2 lors de la 43^ème étape. Il sera abandonné, toujours au profit de ce dernier, plus rapide jusque-là.

A là 47^ème étape, le chemin A-2 arrive à destination en premier. Il est conservé comme la meilleure solution pour le trajet et nourrit l’algorithme de cette découverte.

Pour en savoir plus sur A*: http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html