Recherche de chemin
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.
Nature du problème
modifierInitialement, 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.).
Algorithmes de recherche de chemin
modifier
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.
Mise en œuvre
modifierEn 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. Ces obstacles peuvent être des objets statiques (comme des rochers ou des murs), ou mobiles (comme d'autres personnages, un meuble déplaçable) ; ils peuvent être infranchissables (comme un mur ou un trou), ou traversables avec difficulté (comme du sable ou de l'eau).
La difficulté peut également venir du fait que des décisions importantes doivent être prises en temps réel et qu'elles ont des conséquences parfois contradictoires sur les choix précédents.
Les calculs de recherche de chemin sont actuellement effectués par le processeur de l'ordinateur, mais il est possible qu'ils soient bientôt accélérés matériellement[réf. nécessaire].
Applications de la recherche de chemin
modifierLes applications du pathfinding sont multiples, allant par exemple de la gestion des déplacements dans un jeu vidéo, à ceux d'un robot entre des obstacles, du problème classique du voyageur de commerce, à la restauration des erreurs de transmissions.
Jeu vidéo
modifierLe pathfinding est utilisé de façon intensive dans les jeux vidéo où des entités, telles que des personnages, se déplacent en temps réel dans un environnement en évolution.
Robotique
modifierEn robotique mobile, planifier un déplacement devient encore plus complexe. En effet, il s'agit de se déplacer dans un environnement réel. Tout d'abord, le robot ne dispose que d'une estimation de sa position, car ses capteurs ne sont pas parfaits. De la même façon, il doit se déplacer au moyen d'effecteurs qui ne peuvent l'amener là où il décide qu'avec une certaine imprécision.
Afin de prendre en compte ces incertitudes, il est nécessaire de passer à des modèles mathématiques probabilistes (comme les MDP et les POMDP). Il existe également plusieurs méthodes ensemblistes qui préfèrent alors assurer à 100 % que la position du robot est dans un pavé de l'espace, plutôt qu'une question de probabilités.
De plus, si on ajoute dans l'environnement des humains ou des animaux, il faut prévoir comment ces entités vont se déplacer afin de les éviter.
La recherche de chemin pour des systèmes physiques réels ou simulés (robot, véhicule, objet solide…) est un domaine de recherche nommé planification de mouvement.
Recherche de chemin multi-agents
modifierLe problème de recherche de chemins pour un système multi-agents consiste, à partir de positions de départ, de positions d'arrivée, à générer des chemins sans collision pour les agents, qui minimise le coût global[1].
Annexes
modifierArticles connexes
modifier- Algorithme de Dijkstra
- A*, un algorithme très répandu de calcul de pathfinding
- Problème de plus court chemin
- Algorithme de Viterbi
- Contractions hiérarchiques
- Mesh de navigation
