Planification de mouvement

La planification de mouvement (en anglais motion planning) est un ensemble de techniques mathématiques et informatiques servant à calculer des trajectoires pour un dispositif cinématique, avec pour contrainte l'absence de collision.

Il existe deux principales catégories de méthodes pour la planification de mouvement :

• La première se compose de méthodes dites déterministes, nommées ainsi car elles permettent de retrouver le même chemin à chaque exécution, sous réserve d'avoir des conditions initiales équivalentes. Les méthodes déterministes sont dites complètes en résolution car elles garantissent de trouver une solution, ou d'indiquer s'il n'y a pas de solution. Quelques algorithmes bien connus : champs de potentiel, décomposition cellulaire, diagrammes de Voronoï...
• La seconde catégorie se compose des méthodes probabilistes. Ces méthodes ne sont pas complètes en résolution, mais elles garantissent de trouver une solution s'il en existe une. On dit qu'elles sont complètes en probabilité. Ces méthodes ne trouveront pas nécessairement le même chemin à chaque éxecution, même avec des conditions initiales identiques. Les méthodes probabilistes peuvent être subdivisées en deux sous catégories : les méthodes d'échantillonnage et les méthodes de diffusion. Les premières cherchent à approximer l'environnement de l'objet qui doit être déplacé, pour construire une carte réutilisable (de la même manière qu'une carte routière). Les secondes effectuent une recherche aléatoire dans l'environnement, jusqu'à trouver la configuration finale désirée. Quelques algorithmes bien connus : algorithme du fil d'ariane, probabilistic roadmap (PRM) pour les méthodes d'échantillonnage, rapidly-exploring random trees (RRT) pour les méthodes de diffusion.

Un logiciel mettant en œuvre ces techniques est appelé un planificateur de mouvement (en anglais path planner).

Utilisations

La planification de mouvement est un domaine de recherche particulièrement actif qui a déjà un certain nombre d'applications :

• dans la conception industrielle, la résolution de problèmes de désassemblage  ;
• dans la robotique, le calcul de trajectoires permettant à un robot de se déplacer d'un point à un autre ;
• dans la robotique humanoïde, le calcul des mouvements de marche et de manipulation intégrant contraintes cinématiques et dynamiques ;
• dans la bio-informatique, l'étude des mouvements des molécules ;
• dans des environnements simulés (surtout les jeux vidéo), le calcul de trajectoires plausibles pour un personnage ou un véhicule.

Espace des configurations

La plupart des techniques de planification de mouvement ont recours au même outil mathématique pour représenter la position d'un dispositif articulé à corps rigides : l'espace des configurations. C'est un espace vectoriel de dimension finie dont chaque dimension représente un paramètre cinématique — ou degré de liberté — du dispositif (angle d'une rotation, déplacement d'une translation, etc. ). Ainsi, à chaque vecteur de l'espace des configurations correspond une position du dispositif. C'est à dire, le dispositif articulé étant connu (position des articulations et forme des corps rigides liés aux articulations), un vecteur dans l'espace des configurations suffit à représenter précisément la position de chacun de ses éléments dans l'espace réel (appelé espace de travail).

A titre d'exemple, pour un bras humain (et sans considérer les doigts de la main), l'espace des configurations est de dimension sept (trois degrés de liberté à l'épaule, un degré de liberté au coude et trois degrés de liberté au poignet).

Un solide en déplacement libre dans l'espace (appelé free-flyer) est un cas spécifique de dispositif articulé avec trois translations et trois rotations (généralement roulis, tangage et lacet, mais d'autres représentations sont envisageables). Son espace des configurations est par conséquent de dimension six.

Ainsi, sauf cas spécifique d'optimisation pour un dispositif spécifique, les algorithmes de planification de mouvement s'appliquent aussi aisément à un free-flyer qu'à un dispositif articulé complexe grâce à l'abstraction que forme l'espace des configurations.

Bibliographie

• J. -C. Latombe, Robot Motion Planning, 1991.
• S. M. LaValle, Planning Algorithms, 2006.
• J. Cortés, L. Jaillet, T. Siméon, Molecular disassembly planning with RRT-like algorithms, IEEE Int. Conf. on Robotics and Automation, 2007.

Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Planification_de_mouvement.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 14/04/2009.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.