Recherche de chemin

Recherche de chemin
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.

Sommaire

Nature du problème

À la base, un problème de pathfinding peut se ramener à 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

Article détaillé : Problèmes de cheminement.
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, 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 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


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Recherche de chemin de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Recherche De Chemin — 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 …   Wikipédia en Français

  • CHEMIN (symbolisme) — CHEMIN, symbolisme Dans toute tradition religieuse ou métaphysique, l’image du chemin est un symbole de la quête de l’Être. Il s’agit probablement d’une des images les plus sacrées ce qu’exprime bien la parole du Christ: «Je suis le Chemin, la… …   Encyclopédie Universelle

  • Chemin (théorie des graphes) — Pour les articles homonymes, voir Chemin. Dans un graphe orienté, un chemin d origine x et d extrémité y est défini par une suite finie d arcs consécutifs, reliant x à y. La notion correspondante dans les graphes non orientés est celle de chaîne …   Wikipédia en Français

  • Chemin de fer — ● Chemin de fer outil de tailleur de pierre et de maçon servant à ravaler la pierre tendre. chemin de fer n. m. d1./d Moyen de transport qui utilise les voies ferrées. Voyager en chemin de fer. Accident de chemin de fer. Syn. train. d2./d… …   Encyclopédie Universelle

  • Chemin De Fer-Musée Blonay-Chamby — Automotrice historique BCFe 4/4 11 du chemin de fer Montreux Oberland Bernois Pays …   Wikipédia en Français

  • Chemin de fer-Musee Blonay-Chamby — Chemin de fer musée Blonay Chamby Chemin de fer musée Blonay Chamby Automotrice historique BCFe 4/4 11 du chemin de fer Montreux Oberland Bernois Pays …   Wikipédia en Français

  • Chemin de fer-Musée Blonay-Chamby — Automotrice historique BCFe 4/4 11 du chemin de fer Montreux Oberland Bernois Pays …   Wikipédia en Français

  • Chemin de fer-musée Blonay-Chamby — Chemin de fer musée Blonay–Chamby Locomotive à vapeur HG 3/4 3 du chemin de fer Brig–Furka–Disentis en tête d un train Pays …   Wikipédia en Français

  • Chemin de fer-musée Blonay - Chamby — Automotrice historique BCFe 4/4 11 du chemin de fer Montreux Oberland Bernois Pays …   Wikipédia en Français

  • Chemin de fer-musée blonay-chamby — Automotrice historique BCFe 4/4 11 du chemin de fer Montreux Oberland Bernois Pays …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”