La robotique humanoïde

La robotique

On peut faire remonter la construction des premiers automates mécaniques à l’antiquité (Chapuis & Droz, 1949), que ce soit dans le but d’imiter des mouvements humains ou d’aider l’homme dans ses travaux pénibles. L’apparition des premiers ordinateurs au milieu du XXe siècle et l’essor de l’intelligence artificielle ont permis de passer de ces automatismes mécaniques à des raisonnements informatiques de haut niveau capables d’adapter le comportement des machines à leur environnement. La robotique a alors été définie comme la science qui étudie « le lien intelligent entre la perception et l’action » (Siciliano & Khatib, 2008).

La perception est la construction de représentations utilisables du robot et de son environnement. Ce processus utilise les données fournies par des capteurs : caméras, radars, capteurs de force, microphones, etc. L’action désigne les évènements que le robot peut engendrer qui ont un impact sur son environnement: l’émission de lumières, de sons ou le mouvement via l’activation de moteurs. Nous appellerons planification les raisonnements qui permettent de passer d’une représentation du monde à une ou plusieurs actions. Cette thèse a pour objet la planification de mouvement pour des systèmes anthropomorphes : robots humanoïdes ou acteurs virtuels.

La robotique humanoïde

La robotique humanoïde a pour but de concevoir et contrôler des systèmes mécaniques directement inspirés par les capacités du corps humain. Ces robots ont généralement des chaînes articulaires semblables en forme et en structure à celle de l’homme, ainsi que des capacités de perception aussi similaires que possible aux capacités humaines. Soulignons les défis mécatroniques que posent la conception de tels systèmes, défis relevés en partie, et depuis peu grâce à la miniaturisation des moteurs et ordinateurs qui ont permis la construction de machines comme les robots HRP-2 (Kawada (Kaneko et al., 2004)), Asimo (Honda (Sakagami et al., 2002)) ou Partners (Toyota (Takagi, 2006)).

Les motivations pour la construction de ces systèmes sont variées. D’un point de vue industriel, un robot humanoïde, s’il est parfois moins efficace qu’un mécanisme spécialisé dans une certaine tâche, a l’avantage d’être plus généraliste, et bien adapté à la conduction de travaux dans des environnements conçus pour des humains. Par ailleurs, d’un point de vue social, les interactions homme-robot peuvent tirer parti des similarités physiques entre un humain et un robot humanoïde. Le robot peut communiquer par des gestes, des regards ou des attitudes imitant la communication non-parlée des humains entre eux. Ces attributs sont essentiels lorsqu’un robot doit évoluer dans un milieu public, ou quand il est utilisé à des fins de divertissement. Enfin, d’un point de vue scientifique, l’étude du mouvement et du corps humains par la robotique humanoïde est source de coopérations fructueuses avec les neurosciences, la psychologie du développement ou encore la linguistique.

L’animation graphique 

Un autre champs d’application des méthodes présentées dans cette thèse est l’animation de personnages virtuels. Les applications principales de l’animation graphique sont le cinéma, les jeux vidéos et la simulation. La génération automatique de mouvement pour des acteurs virtuels a un but unique, qui prend des expressions variées : le réalisme. Dans le cas des industries de loisir, comme les films d’animation, un mouvement réaliste est tel qu’il semblera possible aux spectateurs. Dans le cas de la simulation, on exige du mouvement qu’il suive précisément les lois physiques, dans le but d’étudier le déroulement des évènements tels qu’ils se dérouleraient dans le monde réel. Parmi les techniques pour animer des personnages de façon réaliste, mentionnons la capture de mouvement, qui consiste à enregistrer dans un premier temps les données articulaires d’un humain qui exécute un mouvement pour le rejouer ensuite sur l’acteur virtuel. La qualité des résultats produits par la capture de mouvement en fait un outil de choix pour le cinéma ou les jeux vidéos.

La planification de mouvement

Au vu de la description donnée plus haut de ce qu’était la planification, on peut définir un algorithme de planification de mouvement par :
– ses entrées : les descriptions géométriques d’un système articulé et d’un environnement,
– sa sortie : une suite de mouvements qui résout une certaine tâche.

Malgré la différence de nature entre les robots humanoïdes et les acteurs virtuels, les problèmes que pose la planification de mouvement pour ces systèmes sont similaires. Le premier est la dimension des données traitées. Le corps humain possède en effet un grand nombre d’articulations, et la génération de mouvement pour le corps complet nécessite d’explorer des espaces hautement dimensionnés, souvent trop complexes pour être représentés explicitement. En contrepartie, cette complexité articulaire rend ces systèmes hautement redondants, et leur permet de réaliser de nombreuses tâches. La deuxième difficulté inhérente aux systèmes anthropomorphes est la prise en compte de contraintes de stabilité. Pour garantir qu’une posture ou un mouvement est à l’équilibre statique ou dynamique, le planificateur de mouvement doit intégrer des outils sophistiqués de cinématique inverse.

Contributions

La première contribution de cette thèse est le développement et l’étude d’une méthode générique de planification de mouvement qui utilise des techniques statistiques de réduction de dimension. Cet algorithme a été conçu pour les systèmes hautement dimensionnés et les espaces contraints, et convient bien aux problèmes difficiles d’animation graphiques.

La deuxième contribution est le développement d’algorithmes de planification sous contraintes. Il s’agit d’une intégration d’outils de cinématique inverse hiérarchisée aux algorithmes de planification de mouvement randomisés. On illustre cette méthode sur des problèmes de manipulation par un robot humanoïde.

La troisième contribution est la généralisation des méthodes de planification sous contraintes à la locomotion.

Enfin, la dernière contribution présentée dans cette thèse est l’utilisation des méthodes précédentes pour résoudre des tâches de manipulation complexes par un robot humanoïde. Nous présentons en particulier un formalisme destiné à représenter les informations utilisables par un planificateur de mouvement . Nous avons présenté ce formalisme sous le nom d’« objets documentés ».

Méthodes d’échantillonnage en planification de mouvement

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.

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 R2 ou R3 en celui d’un point dans un autre espace CS ⊂ Rn . 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.

Table des matières

1 Introduction
1.1 La robotique
1.1.1 La robotique humanoïde
1.1.2 L’animation graphique
1.1.3 La planification de mouvement
1.2 Contributions
1.3 Plan de la thèse
1.4 Publications associées à cette thèse
2 Méthodes d’échantillonnage en planification de mouvement
2.1 Le problème du déménageur de piano
2.2 L’espace des configurations
2.3 Planificateurs de mouvement par échantillonnage aléatoire
2.3.1 Proababilistic Roadmaps (PRM)
2.3.2 Rapidly-Exploring Random Trees (RRT)
2.3.3 Optimisateurs de chemins aléatoires
2.4 Complexité des méthodes d’échantillonnage
2.4.1 Espaces expansifs
2.5 Commandabilité en temps petit
2.6 Limites et adaptations des algorithmes d’échantillonnage
2.6.1 Planification pour chaînes fermées et sous contraintes
3 Génération de mouvement pour systèmes anthropomorphes
3.1 Résolution de tâches de cinématique inverse hiérarchisées
3.1.1 Cinématique inverse
3.1.2 Tâches hiérarchisées
3.2 Marche et équilibre dynamique d’un robot humanoïde
3.2.1 Zero-Moment Point (ZMP)
3.2.2 Modèle du « chariot sur une table »
3.3 Marche et manipulation
3.3.1 Décomposition fonctionnelle
3.3.2 Cinématique inverse généralisée à la marche
3.4 Prise en compte de l’évitement d’obstacles
3.4.1 Navigation
3.4.2 Planification de pas
3.4.3 Résolution de contraintes unilatérales par cinématique inverse
3.4.4 Planification sous contraintes
3.4.5 Planification au contact
3.5 Outils et logiciels utilisés dans cette thèse
4 Réduction de dimension en planification de mouvement
4.1 Motivations
4.2 Complexité locale des méthodes d’expansion aléatoire
4.2.1 Analyse d’une étape d’expansion à l’intérieur d’un passage étroit
4.3 Analyse en composantes principales (PCA)
4.4 Échantillonage controllé par la PCA
4.4.1 Précision du calcul de la PCA
4.4.2 Biais dans les espaces peu contraints
4.4.3 Estimation automatique du nombre de points nécessaires au calcul de la PCA
4.5 Complexité
4.6 Résultats expérimentaux
4.6.1 Problème de désassemblage mécanique
4.6.2 Problèmes d’animation graphique
4.6.3 L’algorithme PRM contrôlé par la PCA
4.6.4 Iterative Path Planning (IPP) contrôlé par la PCA
4.7 Discussion sur le choix de la technique de réduction de dimension
4.7.1 Méthodes locales non-linéaires
4.7.2 Description non-linéaire de CSfree
4.8 Conclusion
5 Planification de mouvement sous contraintes
5.1 Utilisation de la cinématique inverse
5.2 Planification de mouvement corps-complet pour un robot humanoïde
5.2.1 Échantillonnage de sous-variétés de CS
5.2.2 Extensions sous contraintes dans CS
5.2.3 Optimisation de posture
5.2.4 Architecture globale de l’algorithme
5.3 Comparaison avec une méthode locale d’évitement d’obstacles
5.3.1 Scénario « Table » à double support
5.3.2 Scénario « Tore » à simple support
5.3.3 Comment prendre en compte l’évitement d’obstacle ?
5.4 Résultats expérimentaux
5.4.1 Mouvements d’atteinte
5.4.2 Manipulation d’objets en translation
5.4.3 Manipulation d’objets en rotation
5.5 Conclusion
6 Planification
7 Conclusion

Lire le rapport complet