Path-finding

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 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. 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

Exemple d'exécution de l'algorithme A* en environnement 2D discret: Les cellules rouges forment un chemin qui part de la cellule verte vers la cellule bleue en évitant l'obstacle formé par les cellules grises. Les nombres indiquent la distance de Manhattan à la cellule de départ en 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 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.

Applications de la recherche de chemin

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 voyageur de commerce, à la restauration des erreurs de transmissions.

Jeu vidéo

Le 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

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ématiques probabilistes (comme les MDP et les 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
• A*, un algorithme très répandu, de calcul de Pathfinding.
• Algorithme de parcours en largeur
• Algorithme de parcours en profondeur
• Algorithme de Viterbi

• Portail de la robotique
• Portail de l’informatique