Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Recherche de chemin
Résumé
La recherche de chemin, couramment appelée pathfinding par anglicisme, est un problème de l'intelligence artificielle qui se rattache plus généralement au domaine de la planification et de la recherche de solution. Il consiste à trouver comment se déplacer dans un environnement entre un point de départ et un point d'arrivée en prenant en compte différentes contraintes.
Initialement, un problème de pathfinding peut se ramener à un problème de recherche du meilleur chemin entre deux nœuds dans un graphe. Il existe un ensemble d'algorithmes classiques pour résoudre ce type de problème. Toutefois, le pathfinding devient un problème complexe lorsque l'on cherche à prendre en compte diverses contraintes additionnelles (exécution en temps réel, présence d'incertitudes, contrainte de ressources, environnement évolutif, etc.).
Problème de plus court chemin
Deux algorithmes déterministes principaux sont utilisés pour la recherche du plus court chemin dans un graphe :
l'algorithme de Dijkstra, qui permet de déterminer le chemin optimal. Il est, par exemple, utilisé pour le routage Internet ;
l'algorithme A*, qui est beaucoup plus rapide à condition d'avoir une bonne fonction heuristique, et dont l'optimalité n'est garantie que sous certaines conditions. En pratique, l'algorithme A* est un bon compromis entre coût de calcul et optimalité de la solution.
Il existe des algorithmes qui permettent de calculer le plus court chemin de manière contrainte, par exemple par rapport à une courbure du type chemin de Dubins. Ces algorithmes sont développés pour répondre aux problèmes rencontrés en robotique vis-à-vis des contraintes matérielles.
Dans le domaine des télécommunications et du traitement du signal, la modélisation est légèrement différente (probabiliste), et le problème est alors résolu par l'algorithme de Viterbi.
En pratique, la recherche de chemin est souvent difficile à programmer et son exécution est souvent coûteuse.
Tout d'abord, la complexité augmente fortement avec le nombre d'obstacles présents simultanément.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.