Vous êtes un visiteur passant par Paris, la célèbre ville lumière. Vous avez rendez-vous avec un vieil ami, qui donne cours dans le bâtiment historique de la Sorbonne, vieux de plus de 800 ans. Vous arrivez à une entrée du bâtiment, située au 14 rue Cujas, et vous demandez l’amphithéâtre Descartes, là où votre ami doit finir son intervention. On vous propose de vous reporter au plan qui vous est donné (figure 1). Comment procéderiez-vous pour aller au point de rendez-vous ?
Il existe plusieurs manières d’aborder le problème. L’une d’entre elles est de tracer intérieurement une ligne droite du point de départ à l’arrivée, et de regarder quel chemin s’y rapproche le plus. C’est ce qui ‘est illustré sur la figure suivante (figure 2).
Les points rouge et bleu correspondent respectivement à l’arrivée et le départ.
Peut-on alors affirmer avec certitude que le chemin indiqué en vert soit le plus court pour se rendre au point d’arrivée ? Cette question fait partie du ‘Problème du plus court chemin’. Ce problème intervient souvent dans les problèmes dites de pathfinding (recherche de chemin en anglais). Elles incluent aussi bien le trajet optimal entre deux villes pour un GPS, le déplacement autonome d’un robot, ou encore le déplacement dynamique de personnages dans les jeux-vidéos. Plusieurs mathématiciens ont tenté de résoudre ce problème du chemin le plus court.
Reprenons le moment où vous entrez en Sorbonne, et où on vous donne le plan. Vous avez identifié là où vous vous trouviez, et là où vous souhaitez aller. Pour pouvoir trouver le plus court chemin, il existe une autre solution. Commencez par marquer d’un point les intersections où il est possible de passer, ce sont les points de passage. On trouve, à peu de choses près, cette configuration, illustrée dans la figure ci-dessous (figure 3).
Les points verts représentent les lieux où il est possible de passer. Le point bleu indique le point de départ tandis que le point rouge indique l’arrivée.
Les points de passage posées, il faut désormais les relier. Pour ce faire, il faut juste que les lignes représentent des trajets qui correspondent à la structure du bâtiment, par exemple, qu’un trait ne traverse pas un mur. Cela donne la représentation suivante, illustrée dans la figure ci-dessous (figure 4) :
À présent, il faut estimer le temps de parcours entre deux points reliés par un trait. Ne pouvant pas tester tous les chemins (vous avez un rendez-vous !) vous estimez grossièrement le temps, en fonction de la distance du trait.
Chaque nombre est associé à un trait, qui indique le temps nécessaire pour le parcourir. Pour simplifier, on compare les différentes longueurs des traits (ce qui suppose que le plan soit bien proportionné !).
Pour arriver au chemin le plus court, commençons du point de départ symbolisé par le point bleu. Vous ne pouvez qu’aller tout droit, donc dépenser une unité de temps. Arrivé au second nœud, s’offre un point accessible à droite et un autre à gauche. Celui de gauche coûte une unité de temps, et celui de droite trois. Par conséquent, vous savez que depuis l’entrée, aller respectivement à l’un ou l’autre point coûte deux ou quatre unités de temps. Et ainsi de suite.
Supposons que vous souhaitez aller de A à F en un minimum de temps. Les voisins de A sont B et C. Le temps le plus court pour aller de A à B est de 1 et 3 pour aller de A à C. C n’a qu’un voisin : E, donc aller de A à E coûte 4. Or, les voisins de B sont D et E. De plus, aller de A à E coûte 3 car un chemin plus court a été trouvé. Il y a donc mise à jour des temps de parcours.
À un point donné, regardez qui sont ses voisins. Regardez ensuite le coût (en temps) du trajet entre votre point de départ jusqu’à un des voisins. Si le voisin avait déjà été exploré avant, prenez le trajet qui coûte le moins de temps. Vous vous arrêtez lorsque vous arrivez au point de destination. Si vous ne pouvez pas, c’est qu’il n’y a pas de chemin possible entre ces deux points ! Rassurez-vous, dans notre exemple, il est bien possible d’y arriver !
Edsger Dijkstra (1930 – 2002), un mathématicien néerlandais, a abordé le sujet du plus court chemin. La suite de ses étapes, telles que vous venez de les lire, représente l’algorithme de Dijkstra. Un algorithme est une suite d’actions à effectuer dans l’ordre, une à une, pour à aboutir à un résultat qui permet de résoudre un problème. On compare souvent un algorithme à une recette de cuisine (où le problème devient un plat à préparer). Dans l’algorithme de Dijkstra, la quantité d’étapes et de complexification demandée semble être importante, mais dès qu’elle est intégrée à un calculateur, la résolution devient aisée.
Ajoutons une contrainte supplémentaire à notre cas. Supposons que vous devez voir dix personnes, dans l’ordre (vous avez préparé votre planning), ces derniers sont répartis dans tout le bâtiment. Comment procéderiez-vous ? En effet, ce qui ne fut pas dit au début, c’est que la Sorbonne est un bâtiment complexe. Haut de plus d’une dizaine d’étages, sa façade à l’apparence simple, cache en réalité une mille-feuille de salles et de bureaux. C’est ainsi que le SIRIS, le service interuniversitaire du réseau informatique de la Sorbonne a décidé de déployer une application de guidage permettant aux usagers de s’orienter facilement dans le bâtiment. L’algorithme de Dijkstra, implémentée dans l’application mobile, permet de répondre à la contrainte posée : à chaque rendez-vous terminé, vous n’avez qu’à saisir le lieu du prochain.
Modifions maintenant légèrement cette contrainte. Vous avez toujours rendez-vous avec dix personnes, mais l’ordre importe peu ! L’objectif cette fois ci, est de trouver le trajet qui permet de voir toutes ces personnes, en un temps minimum, donc en optimisant les trajets de l’un à l’autre. Comment feriez-vous ? Ce nouveau problème est connu en tant que ‘Problème du voyageur de commerce’, et admet une complexité beaucoup plus grande. Il n’existe pas à l’heure actuelle d’algorithmes résolvant efficacement ce genre de problème.
Mais revenons à Dijkstra. Que penseriez-vous si nous affirmions que le procédé tel que nous l’avons présenté relève de l’Intelligence Artificielle (IA) ? Pour comprendre l’association entre cette notion et notre problème, il faut effectuer un petit retour en arrière.
Historiquement, la notion d’IA a été créé en 1956, lors d’une conférence à Dartmouth dont les organisateurs furent les scientifiques Marvin Minsky, John McCarthy, Claude Shannon et Nathan Rochester. Les années 60 étaient une époque où l’informatique était en plein essor. C’est à ce moment que la notion d’IA devint un domaine de recherche à part entière et se dissocia de l’informatique. Plusieurs scientifiques proposèrent des définitions de l’IA, dont John McCarthy. Nous retiendrons la définition française la plus récente (2019) formulée par le Larousse : « Ensemble de théories et de techniques mises en œuvre en vue de réaliser des machines capables de simuler l’intelligence humaine. »
Si l’on reprend les termes de la définition, on constate que le problème de plus court chemin répond en partie à ces termes : l’algorithme est un résultat d’études techniques et théoriques. L’algorithme simule également l’intelligence humaine car elle répond à un problème que l’humain se pose. Un autre aspect de l’intelligence humaine est l’apprentissage, elle se témoigne par l’enfant-né, apprenant à marcher, à communiquer. Or, cet algorithme n’admet aucun apprentissage, elle ne peut résoudre qu’un type de problème. C’est pour cette raison que l’on peut qualifier l’algorithme comme étant une IA faible. Elle se distingue ainsi d’une IA forte, qui, par ce qualificatif, peut résoudre un éventail plus large de problèmes et possède une capacité d’apprentissage.
Par conséquent, à chaque fois où il est possible d’entendre le terme d’IA, il est nécessaire de savoir de quel type on parle (faible ou forte). C’est une chose qui ne semble pas être faite, et occasionne des incompréhensions ou des erreurs de jugement parmi la population. Alors que le débat sur la place de l’IA dans la société cristallise ses détracteurs et ses partisans, n’oublions pas que depuis maintenant plus d’une décennie, vous transportez quotidiennement un appareil truffé d’intelligence artificielle.
Alex THAO,
assistant chef de projet, sur le déploiement du projet de guidage en Sorbonne
ingénieur de l’Ecole des Ingénieurs de la Ville de Paris (EIVP).