Planification de mouvement pour systèmes anthropomorphes

Méthodes d’échantillonnage en planification de mouvement 

Ce chapitre présente le problème de la planification de mouvement sous sa forme la plus générale. Il décrit plus précisément la classe des algorithmes basés sur l’échantillonnage aléatoire. Cette présentation s’inspire de (LaValle, 2006). Des revues complètes des problèmes et méthodes en planification de mouvement peuvent aussi être trouvées dans (Choset et al., 2005; Latombe, 1991).

 Le problème du déménageur de piano

 La robotique a pour but de concevoir des systèmes autonomes, capables de percevoir, raisonner, se déplacer et agir sur le monde qui les entoure. Un besoin fondamental pour un système robotique est la capacité à traduire des ordres donnés par un humain et exprimés à un haut niveau d’abstraction : « Va dans cette pièce, attrape cet objet », en une série de mouvements de bas niveau, qui décrivent de façon effective comment le robot va se mouvoir. La planification de mouvement, ou de trajectoire, s’efforce de répondre à ce besoin. Le problème a été présenté dans la littérature sous le nom du problème du déménageur de piano dans (Schwartz et al., 1987). Il peut s’écrire ainsi : étant donnés un environnement composé d’obstacles et un piano, est-il possible de déplacer le piano d’une position et orientation – appelées sa configuration q – à une autre, sans entrer en collision avec les obstacles. La figure 2.1 présente un acteur digital et un robot humanoïde tentant de répondre à cette question. Figure 2.1 – Le robot humanoïde HRP-2 et un personnage virtuel déménageant un piano dans un environnement encombré. 

 L’espace des configurations 

Au début des années 1980, (Lozano-Perez, 1983) a introduit le concept d’espace des configurations (noté CS dans la suite), qui est l’ensemble de toutes les configurations qu’un système peut adopter. Ce formalisme permet de traduire le problème du mouvement de corps dans le monde réel R 2 ou R 3 en celui d’un point dans un autre espace CS ⊂ R n . La dimension de la variété CS est égale au nombre de variables indépendantes ou degrés de liberté dont la donnée à un instant t décrit entièrement la configuration du système considéré. Les obstacles dans le monde réel induisent des obstacles dans CS. On définit CSobstacle ⊂ CS comme l’ensemble des configurations q telles qu’en q le robot est en collision avec un obstacle de son environnement. Le complémentaire de CSobstacle est appelé l’espace libre, et noté CSfree. Il s’agit de l’ensemble des configurations admissibles de CS. Notons qu’on exclut de CSfree les configurations au contact des obstacles, ce qui implique que CSfree est un ouvert de CS. Muni de ce formalisme, on peut reformuler le problème de la planification de mouvement ainsi : étant donnés CS, CSobstacle et deux configurations qinitial et qfinal appartenant à CSfree, existe-t-il un chemin reliant qinitial à qfinal, c’est-à-dire une fonction continue τ : [0, 1] → CSfree telle que τ (0) = qinitial et τ (1) = qfinal ? Plusieurs planificateurs ont été proposés pour répondre à cette question de manière exacte, en construisant des représentations explicites de CSobstacle. Des algorithmes de décomposition en cellules (Schwartz et al., 1987), en diagramme de Voronoi ou graphes de visibilité (Latombe, 1991) ont été proposés. Le but est de construire un graphe dans CSfree (souvent appelé roadmap en anglais et noté R dans la suite), accessible depuis tout q ∈ CSfree. Ainsi, la recherche d’un chemin entre qinitial et qfinal est ramenée à la recherche d’un chemin dans un graphe. L’algorithme de Canny (Canny, 1988) construit R de façon plus efficace, sans passer par une décomposition en cellules de CSfree, et résout le problème de la planification de mouvement en un temps simplement exponentiel en la dimension du problème. Une revue de ces planificateurs est disponible dans (Goodman & O’Rourke, 2004). Ces approches ont la propriété intéressante d’être exactes : après leur exécution, dont on peut donner un majorant en temps en fonction de la taille des données d’entrée, elles renvoient un chemin valide si et seulement s’il en existe un. On qualifiera cette propriété de complétude. Le coût algorithmique de ces méthodes les rend inutilisables en pratique sur nombre de problèmes réels, où la complexité des modèles géométriques ou la dimension des systèmes considérés rend la taille d’une représentation explicite de CSfree trop grosse pour être calculée ou utilisée sur un ordinateur usuel. Afin de dépasser les limites de ces méthodes exactes, des planificateurs randomisés ont été développés ces quinze dernières années. Bien qu’ils ne garantissent qu’une complétude plus faible, qualifiée de probabiliste, leur capacité à résoudre des problèmes complexes et hautement dimensionnés efficacement les a imposés en planification de mouvement. Le travail présenté ici s’inscrit pour l’essentiel dans le développement et l’amélioration de ces méthodes.

 Planificateurs de mouvement par échantillonnage aléatoire 

Le but de cette classe d’algorithmes est de construire un graphe aléatoire R, dont les sommets sont des configurations libres de collision et dont les arêtes traduisent l’existence d’un chemin élémentaire (par exemple une ligne droite dans CS) libre de collision entre deux configurations. On souhaite que R capture la topologie de CSfree, c’est-à-dire qu’à chaque composante connexe de CSfree corresponde une et une seule composante connexe de R. Le principe est de ne pas calculer de représentation explicite de CSfree, mais seulement de valider ou d’invalider certaines configurations à l’aide d’un détecteur de collisions. On utilise ce détecteur comme une boîte noire afin que l’implémentation des algorithmes de planification eux-mêmes ne dépende pas des caractéristiques géométriques des systèmes pour lesquels on planifie. Outre le détecteur de collision, on utilise une méthode locale qui prend en entrée deux configurations, et génère un chemin élémentaire qui les relie. Cette méthode est liée au système considéré. Il peut s’agir d’une simple interpolation en ligne droite dans CS, si le système peut se déplacer dans toutes les directions. Dans le cas de robots mobiles à roue par exemple, le robot ne peut pas se déplacer sur le côté sans manœuvrer. La méthode locale génère alors des trajectoires admissibles pour le système. La suite de la présentation sur l’échantillonnage fera l’hypothèse qu’on utilise une interpolation linéaire, la section 2.5 expliquera comment adapter ces algorithmes à d’autres méthodes locales.