Planification de mouvement
La planification de mouvement (en anglais motion planning) est un ensemble de techniques mathématiques et informatiques permettant de calculer des trajectoires pour un système 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 est composée de méthodes dites déterministes, appelé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 est composée 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 forcément le même chemin à chaque exécution, même avec des conditions initiales similaires. 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é, afin de 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 nommé un planificateur de mouvement (en anglais path planner).
Utilisations
La planification de mouvement est un domaine de recherche très 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 (notamment les jeux vidéo), le calcul de trajectoires plausibles pour un personnage ou un véhicule.
Théorie
Espace des configurations
La plupart des techniques de planification de mouvement ont recours au même outil mathématique afin de représenter la position d'un système articulé à corps rigides : l’espace des configurations. Il s'agit d'un espace vectoriel de dimension finie dont chaque dimension représente un paramètre cinématique — ou degré de liberté — du système (angle d'une rotation, déplacement d'une translation, etc.). Ainsi, à chaque vecteur de l'espace des configurations correspond une position du système. Autrement dit, le système 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 exactement la position de chacun de ses éléments dans l'espace réel (appelé espace de travail).
Par 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 particulier de système articulé avec trois translations et trois rotations (généralement roulis, tangage et lacet, mais d'autres représentations sont possibles). Son espace des configurations est donc de dimension six.
Ainsi, sauf cas particulier d'optimisation pour un système spécifique, les algorithmes de planification de mouvement s'appliquent aussi facilement à un free-flyer qu'à un système articulé complexe grâce à l'abstraction que constitue 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.