Recherche de chemin
Définition
La recherche de chemin, couramment appelée pathfinding, 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.
Ce domaine de recherche s'appuie fortement sur l'algorithme de Dijkstra pour tracer le plus court chemin possible sur un graphe pondéré.
En robotique mobile, planifier un déplacement est 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 précision. Afin de prendre en compte ces incertitudes, il est nécessaire de passer à des modèles mathématiques probabilistes. 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.
Français
recherche de chemin
Anglais
pathfinding
pathing
Sources
Contributeurs: Evan Brach, Jacques Barolet, wiki
