Recherche de chemin 774175 31825633 2008-07-23T17:09:10Z Atvaark 3296 /* Robotique */ {{ébauche|informatique}} [[Image:Pathfinding 2D Illustration.svg|250px|thumb|right|Chemins équivalents allant de A à B dans un environnement à deux dimensions]] 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 (intelligence artificielle)|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 == A la base, un problème de '''''pathfinding''''' peut se ramèner à un problème de recherche du meilleur chemin entre deux noeuds dans un [[Graphe (théorie des graphes)|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 == [[Image:Pathfinding A Star.svg|250px|thumb|right|Exemple d'exécution de l'algorithme A* en environnement 2D discret: Les <font color="#800000">'''cellules rouges'''</font> forment un chemin qui part de la <font color="#008000">'''cellule verte'''</font> vers la <font color="#000080">'''cellule bleue'''</font> en évitant l'obstacle formé par les <font color="#404040">'''cellules grises'''</font>. Les nombres indiquent la [[Distance (mathématiques)#Distance sur des espaces vectoriels|distance de Manhattan]] à la cellule de départ en [[Connectivité (géométrique)|4-connectivité]].]] 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]], mais qui donne une solution qui n'est pas forcément optimale. En pratique, l'algorithme A* est un bon compromis entre coût 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 oeuvre === En pratique, la recherche de chemins 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ération matérielle|accélérés matériellement]]. == Applications de la recherche de chemins == Les 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 [[Problème du voyageur de commerce|voyageur de commerce]], à la restauration des erreurs de transmissions. === Jeu vidéo === Le ''pathfinding'' est utilisé de façon intensive dans les [[jeu vidéo|jeux vidéo]] où des entités, telles que des personnages se déplacent en [[temps réel]] dans un environnement en évolution. === Robotique === En [[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 précision. Afin de prendre en compte ces incertitudes, il est nécessaire de passer à des [[modèle mathématique]]s [[probabilité|probabilistes]] (comme les [[Processus de décision markovien|MDP]] et les [[Processus de décision markovien partiellement observable|POMDP]]). 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]]. == Voir aussi == * [[Algorithme de Dijkstra]] * [[Algorithme de Ford-Bellman]] * [[Algorithme de Dantzig-Ford]] * [[Algorithme A*|A*]], un algorithme très répandu, de calcul de Pathfinding. * [[Algorithme de parcours en largeur]] * [[Algorithme de parcours en profondeur]] * [[Algorithme de Viterbi]] == Liens externes == * [http://aiseek.com/ Aiseek] une société qui sort une carte d'IA. {{Portail|robotique|informatique}} [[Catégorie:Algorithme de recherche]] [[Catégorie:Théorie des graphes]] [[Catégorie:Intelligence artificielle]] [[de:Pathfinding]] [[en:Pathfinding]] [[fi:Polunetsintä]]