Planification du mouvement pour les systèmes anthropomorphes
Les robots humanoïdes, ainsi que les acteurs digitaux, sont des systèmes complexes et hautement redondants. Leur grand nombre de degrés de liberté leur permet de se déplacer, en marchant et de résoudre de nombreuses tâches de manipulation : attraper et déplacer des objets, ouvrir des portes ou des tiroirs, etc.
L’utilisation de ces vastes capacités, qu’on souhaiterait équivalentes aux capacités physiques du corps humain, sont un défi posé aux planificateurs de mouvement. La taille des structures utilisées par un planificateur suit de façon exponentielle le nombre de degrés de liberté du système pour lequel on planifie. S’ajoutent à ce coût certaines contraintes spécifiques aux systèmes anthropomorphes. On n’attend pas d’un robot humanoïde qu’il atteigne une certaine configuration, mais plutôt qu’il résolve une tâche, exprimée dans son espace de travail (et pas dans CS).
Proababilistic Roadmaps (PRM)
La planification de mouvement par échantillonnage aléatoire été présentée pour lapremière fois dans (Kavraki et al., 1996) sous le nom de Probabilistic Roadmaps (noté PRM dans la suite). L’algorithme PRM procède en deux phases :
1. Dans un premier temps, on génère des configurations aléatoires uniformément dans CS, qu’on passe au détecteur de collisions. Si une configuration est valide, on l’ajoute à R. On essaye ensuite de la relier par des lignes droites aux configurations déjà dans R. Si un tel chemin est valide, on ajoute l’arête correspondante
dans R.
2. Afin d’échantillonner plus spécifiquement les passages contraints de CSfree, on échantillonne ensuite des configurations aléatoires dans les voisinages des configurations de R présumées « difficiles ». La mesure de cette difficulté pour une configuration q est proportionnelle au nombre de fois qu’on a essayé de relier q à une autre configuration sans y parvenir. La deuxième phase de cet algorithme, qui consiste à faire des hypothèses sur la frontière de la zone visible depuis R et à essayer d’étendre cette frontière en adaptant l’échantillonnage, est communément appelée dans la littérature une phase d’expansion de R.
L’utilisation de ces vastes capacités, qu’on souhaiterait équivalentes aux capacités physiques du corps humain, sont un défi posé aux planificateurs de mouvement. La taille des structures utilisées par un planificateur suit de façon exponentielle le nombre de degrés de liberté du système pour lequel on planifie. S’ajoutent à ce coût certaines contraintes spécifiques aux systèmes anthropomorphes. On n’attend pas d’un robot humanoïde qu’il atteigne une certaine configuration, mais plutôt qu’il résolve une tâche, exprimée dans son espace de travail (et pas dans CS).
Proababilistic Roadmaps (PRM)
La planification de mouvement par échantillonnage aléatoire été présentée pour lapremière fois dans (Kavraki et al., 1996) sous le nom de Probabilistic Roadmaps (noté PRM dans la suite). L’algorithme PRM procède en deux phases :
1. Dans un premier temps, on génère des configurations aléatoires uniformément dans CS, qu’on passe au détecteur de collisions. Si une configuration est valide, on l’ajoute à R. On essaye ensuite de la relier par des lignes droites aux configurations déjà dans R. Si un tel chemin est valide, on ajoute l’arête correspondante
dans R.
2. Afin d’échantillonner plus spécifiquement les passages contraints de CSfree, on échantillonne ensuite des configurations aléatoires dans les voisinages des configurations de R présumées « difficiles ». La mesure de cette difficulté pour une configuration q est proportionnelle au nombre de fois qu’on a essayé de relier q à une autre configuration sans y parvenir. La deuxième phase de cet algorithme, qui consiste à faire des hypothèses sur la frontière de la zone visible depuis R et à essayer d’étendre cette frontière en adaptant l’échantillonnage, est communément appelée dans la littérature une phase d’expansion de R.
Construction de R par l’algorithme PRM. Les obstacles sont représentés par les zones de couleur grise. Le graphe est composé de deux composantes connexes, qui devront être reliées pour capturer la topologie de Csfree.
Le but de l’algorithme PRM est de construire R dans un premier temps pour pouvoir répondre à des requêtes multiples de planification de mouvement dans le même environnement dans un deuxième temps. La figure 2.2 présente un algorithme PRM en cours d’exécution. CSobstacle est représenté par les zones grises. CSfree ne contient qu’une seule composante connexe, et R deux, donc l’algorithme n’est pas encore arrivé à une description satisfaisante de CSfree.
Rapidly-Exploring Random Trees (RRT)
Suite au succès des PRM pour planifier des mouvements dans des espaces hautement dimensionnés, une classe d’algorithmes a donné lieu à d’importantes et fructueuses recherches : les stratégies d’expansion d’arbres aléatoires, présentées à la fois dans (Kuffner & LaValle, 2000) et (Hsu et al., 1999), parmi lesquelles les Rapidly-Exploring Random Trees (notés RRT dans la suite). Dans ces algorithmes, R est un arbre, qu’on fait grossir dans CSfree. À chaque itération de l’algorithme, on échantillonne une configuration aléatoire qrand dans CS, on cherche le noeud de R le plus proche de qrand : qnear et on étend l’arbre aussi loin que possible depuis qnear dans la direction de qrand tout en restant dans CSfree. La figure 2.3 présente une étape d’extension de R.
Le but de l’algorithme PRM est de construire R dans un premier temps pour pouvoir répondre à des requêtes multiples de planification de mouvement dans le même environnement dans un deuxième temps. La figure 2.2 présente un algorithme PRM en cours d’exécution. CSobstacle est représenté par les zones grises. CSfree ne contient qu’une seule composante connexe, et R deux, donc l’algorithme n’est pas encore arrivé à une description satisfaisante de CSfree.
Rapidly-Exploring Random Trees (RRT)
Suite au succès des PRM pour planifier des mouvements dans des espaces hautement dimensionnés, une classe d’algorithmes a donné lieu à d’importantes et fructueuses recherches : les stratégies d’expansion d’arbres aléatoires, présentées à la fois dans (Kuffner & LaValle, 2000) et (Hsu et al., 1999), parmi lesquelles les Rapidly-Exploring Random Trees (notés RRT dans la suite). Dans ces algorithmes, R est un arbre, qu’on fait grossir dans CSfree. À chaque itération de l’algorithme, on échantillonne une configuration aléatoire qrand dans CS, on cherche le noeud de R le plus proche de qrand : qnear et on étend l’arbre aussi loin que possible depuis qnear dans la direction de qrand tout en restant dans CSfree. La figure 2.3 présente une étape d’extension de R.
L’algorithme 1 présente l’architecture d’un RRT. Une étape d’extension depuis qnear vers qrand correspond à une expansion de R selon la terminologie utilisée pour les PRM. Nous utiliserons indifféremment l’un ou l’autre de ces termes dans la suite. Parce qu’il n’utilise que des extensions aléatoires, au lieu d’un échantillonnage uniforme de CS, l’algorithme RRT est mieux adapté que PRM à la planification dans certains espaces contraints, typiquement aux problèmes de désassemblage mécanique. Les chapitres suivant s’attarderont sur les différences entre ces deux algorithmes.
L’algorithme présenté résout le problème de l’exploration de CSfree. Toutefois, il ne répond pas précisément au problème de la planification de mouvement, c’est-à-dire à la recherche d’un chemin entre qinitial et qfinal. La méthode la plus simple pour résoudre une requête de planification en utilisant l’algorithme RRT consiste à faire grossir un arbre enraciné en qinitial et à vérifier à chaque itération de l’algorithme si on peut relier qnew à qfinal par un chemin élémentaire. Une approche souvent plus efficace consiste à faire grossir deux arbres dans CSfree enracinés respectivement en qinitial et qfinal, et à vérifier régulièrement si on peut connecter ces deux arbres entre eux.
Optimisateurs de chemins aléatoires
Les chemins générés par ces algorithmes comportent beaucoup de « détours » à cause de la randomisation, et nécessitent généralement d’être optimisés avant de pouvoir être suivis par le système. L’optimisation la plus courante repose sur une méthode dite de raccourcis, qui consiste à échantillonner des couples de points sur le chemin et à construire un chemin élémentaire les reliant. Si ce chemin élémentaire est plus court - ou moins coûteux, pour une fonction de coût associée au système - et sans collision, on remplace la partie correspondante du chemin de départ. La figure 2.4 illustre le déroulement d’une telle optimisation. Cette méthode est assez sommaire, et facile à implémenter. Dans de nombreux cas, les résultats qu’elle donne sont suffisants. Les résultats expérimentaux présentés dans les chapitres suivants ont été générés avec cette technique. Récemment, des techniques plus sophistiquées d’optimisation ont été utilisées en planification de mouvement pour l’optimisation de trajectoires, par exemple dans (Ratliff et al., 2009). Au prix de calculs plus compliqués - et souvent plus coûteux - ces méthodes peuvent fournir des solutions mieux optimisées. Un autre axe de recherche récent est l’adaptation des méthodes aléatoires pour garantir que les chemins générés sont quasi-optimaux. (Karaman & Frazzoli, 2010) présente l’algorithme RRT, qui au prix d’une complexité asymptotiquement équivalente à celle du RRT - à une constante près - converge presque-sûrement vers un chemin optimal.
De nombreux outils et formalismes spécifiques ont été développés pour résoudre les problèmes propres aux systèmes anthropomorphes. Il existe donc le formalisme de la cinématique inverse hiérarchisée, qui répond au besoin de générer un mouvement résolvant une tâche plutôt qu’atteignant une configuration donnée. Ces algorithmes permettent aussi de générer des postures respectant des contraintes d’équilibre, un modèle utilisé pour générer des mouvements de marche à l’équilibre dynamique et les possibilités de couplage de la locomotion et de la manipulation. Attention tous ces algorithmes ne permettent pas en tant que tel de résoudre le problème de l’évitement d’obstacles.
La figure ci-dessous présente un exemple de résultat d’un algorithme de cinématique inverse. Les contraintes à respecter sont l’équilibre statique, et la tâche consiste à amener la main droite à la position indiquée par le cube rouge.
Réalisation d’une tâche d’atteinte pour la main droite en conservant l’équilibre statique, c’est-à-dire, les deux pieds au sol et le centre de masse projeté au centre
de son polygone de sustentation.
L’algorithme présenté résout le problème de l’exploration de CSfree. Toutefois, il ne répond pas précisément au problème de la planification de mouvement, c’est-à-dire à la recherche d’un chemin entre qinitial et qfinal. La méthode la plus simple pour résoudre une requête de planification en utilisant l’algorithme RRT consiste à faire grossir un arbre enraciné en qinitial et à vérifier à chaque itération de l’algorithme si on peut relier qnew à qfinal par un chemin élémentaire. Une approche souvent plus efficace consiste à faire grossir deux arbres dans CSfree enracinés respectivement en qinitial et qfinal, et à vérifier régulièrement si on peut connecter ces deux arbres entre eux.
Optimisateurs de chemins aléatoires
Les chemins générés par ces algorithmes comportent beaucoup de « détours » à cause de la randomisation, et nécessitent généralement d’être optimisés avant de pouvoir être suivis par le système. L’optimisation la plus courante repose sur une méthode dite de raccourcis, qui consiste à échantillonner des couples de points sur le chemin et à construire un chemin élémentaire les reliant. Si ce chemin élémentaire est plus court - ou moins coûteux, pour une fonction de coût associée au système - et sans collision, on remplace la partie correspondante du chemin de départ. La figure 2.4 illustre le déroulement d’une telle optimisation. Cette méthode est assez sommaire, et facile à implémenter. Dans de nombreux cas, les résultats qu’elle donne sont suffisants. Les résultats expérimentaux présentés dans les chapitres suivants ont été générés avec cette technique. Récemment, des techniques plus sophistiquées d’optimisation ont été utilisées en planification de mouvement pour l’optimisation de trajectoires, par exemple dans (Ratliff et al., 2009). Au prix de calculs plus compliqués - et souvent plus coûteux - ces méthodes peuvent fournir des solutions mieux optimisées. Un autre axe de recherche récent est l’adaptation des méthodes aléatoires pour garantir que les chemins générés sont quasi-optimaux. (Karaman & Frazzoli, 2010) présente l’algorithme RRT, qui au prix d’une complexité asymptotiquement équivalente à celle du RRT - à une constante près - converge presque-sûrement vers un chemin optimal.
De nombreux outils et formalismes spécifiques ont été développés pour résoudre les problèmes propres aux systèmes anthropomorphes. Il existe donc le formalisme de la cinématique inverse hiérarchisée, qui répond au besoin de générer un mouvement résolvant une tâche plutôt qu’atteignant une configuration donnée. Ces algorithmes permettent aussi de générer des postures respectant des contraintes d’équilibre, un modèle utilisé pour générer des mouvements de marche à l’équilibre dynamique et les possibilités de couplage de la locomotion et de la manipulation. Attention tous ces algorithmes ne permettent pas en tant que tel de résoudre le problème de l’évitement d’obstacles.
- Cinématique inverse
La figure ci-dessous présente un exemple de résultat d’un algorithme de cinématique inverse. Les contraintes à respecter sont l’équilibre statique, et la tâche consiste à amener la main droite à la position indiquée par le cube rouge.
Réalisation d’une tâche d’atteinte pour la main droite en conservant l’équilibre statique, c’est-à-dire, les deux pieds au sol et le centre de masse projeté au centre
de son polygone de sustentation.
- Modèle utilisé pour générer des mouvements de marche à l’équilibre dynamique
Le principe fondamental de la dynamique stipule que le torseur dynamique du système est égal au torseur d’action des forces appliquées au système. Nous nous intéressons à des mouvements de marche sur sol plan et horizontal où le robot n’est en contact avec le sol qu’avec ses pieds. Les mouvements ne contiennent pas de sauts et sont sans glissements. Les forces de contact du sol sur les pieds sont dirigées vers le haut. Nous qualifierons ces conditions de conditions de marche. Lorsque cette condition est vérifiée, la projection verticale de ce point sur le sol est appelée en robotique le Zero Moment Point (noté ZMP dans la suite). Cette notion a été présentée dans (Vukobratovi´c et al., 1990).
- Modèle du « chariot sur une table »
Une accélération horizontale du centre de masse fait que le ZMP est bien défini à l’intérieur du polygone support, ce qui garantit un équilibre dynamique. L’expression simple de l’équation 3.5 permet de contrôler le ZMP via la position du centre de masse du robot. (Kajita et al., 2003) propose une méthode basée sur la commande prédictive. Muni d’un contrôleur de ZMP, on peut planifier une trajectoire de marche à l’équilibre dynamique comme suit :
1. On planifie des empreintes de pas, paramétrées en temps.
2. On construit une trajectoire de ZMP en fonction de ces empreintes pour garantir l’équilibre dynamique. Pendant les phases de simple support, on fixe le ZMP au centre du pied de support, pendant les phases de double support, on déplace le ZMP d’un pied à l’autre.
3. On passe cette trajectoire de ZMP au contrôleur qui génère une trajectoire articulaire corps-complet réalisant le mouvement de marche souhaité.
La figure 2 ci-dissous présente une suite d’empreintes de pas et la trajectoire planifiée du ZMP correspondante.
1. On planifie des empreintes de pas, paramétrées en temps.
2. On construit une trajectoire de ZMP en fonction de ces empreintes pour garantir l’équilibre dynamique. Pendant les phases de simple support, on fixe le ZMP au centre du pied de support, pendant les phases de double support, on déplace le ZMP d’un pied à l’autre.
3. On passe cette trajectoire de ZMP au contrôleur qui génère une trajectoire articulaire corps-complet réalisant le mouvement de marche souhaité.
La figure 2 ci-dissous présente une suite d’empreintes de pas et la trajectoire planifiée du ZMP correspondante.
Figure 1 – Modèle simplifié du chariot sur une table. Le chariot représente le centre de masse du robot, qui peut se déplacer librement dans un plan horizontal. Le pied de la table représente le contact du robot avec le sol. Le système n’est pas à l’équilibre statique, mais la condition d’équilibre dynamique du ZMP est vérifiée.
Figure 2 – Planification du ZMP pour qu’il reste à l’intérieur du polygone support. Les disques verts représentent une position fixe pendant une phase de simple support, les lignes rouges représentent le chemin parcouru par le ZMP d’un pied à l’autre pendant les phases de double support.
- Marche et manipulation
- Décomposition fonctionnelle
Décomposition fonctionnelle d’un système anthropomorphe. L’ensemble des degrés de liberté du système est décomposé en trois groupes : locomotion, manipulation et adaptabilité. Figures tirées de (Esteves Jaramillo, 2007).
Munie de cette représentation, la planification commence par résoudre le problème de manipulation avec le haut du corps, puis anime les degrés de liberté liés à la locomotion pour suivre le mouvement. L’intérêt d’une telle représentation est qu’elle rend la planification de mouvement rapide en réduisant sa complexité algorithmique. Cette simplification a un prix puisqu’elle ne permet pas de résoudre les problèmes de manipulation où l’ensemble des degrés de liberté sont nécessaires à la réalisation de la tâche. Ainsi, si le personnage doit attraper un objet sur le sol, la distinction entre les degrés de liberté utiles à la locomotion et ceux utiles à la manipulation n’est pas pertinente, car les degrés de liberté des jambes servent à atteindre l’objet avec la main.
– position du centre de masse,
– position et orientation du pied en vol.
Viennent ensuite les tâches concernant la manipulation.
Munie de cette représentation, la planification commence par résoudre le problème de manipulation avec le haut du corps, puis anime les degrés de liberté liés à la locomotion pour suivre le mouvement. L’intérêt d’une telle représentation est qu’elle rend la planification de mouvement rapide en réduisant sa complexité algorithmique. Cette simplification a un prix puisqu’elle ne permet pas de résoudre les problèmes de manipulation où l’ensemble des degrés de liberté sont nécessaires à la réalisation de la tâche. Ainsi, si le personnage doit attraper un objet sur le sol, la distinction entre les degrés de liberté utiles à la locomotion et ceux utiles à la manipulation n’est pas pertinente, car les degrés de liberté des jambes servent à atteindre l’objet avec la main.
- Cinématique inverse généralisée à la marche
– position du centre de masse,
– position et orientation du pied en vol.
Viennent ensuite les tâches concernant la manipulation.
Cinématique inverse hiérarchisée généralisée à la marche. La réalisation de la tâche d’atteinte nécessite que le robot fasse un pas. La position de ce pas est décidée de façon heuristique. Ensuite un même algorithme de résolution de tâches de cinématique inverse génère le mouvement d’atteinte et garantit l’équilibre dynamique. Figure tirée de (Yoshida et al., 2006).
La figure ci-dessus tirée de (Yoshida et al., 2006) illustre un schéma global de génération de mouvement de manipulation qui nécessite un pas. La génération de mouvement comprend :
– une heuristique pour déterminer la position du pas nécessaire à la réalisation de la tâche,
– la résolution de tâche de cinématique inverse hiérarchisée, qui inclut un contrôleur de ZMP.
Dans (Kanoun et al., 2010), une extension de ce travail propose un placement automatique des empreintes de pas, en intégrant au calcul de cinématique inverse une chaîne articulaire virtuelle composée des emplacements des empreintes de pas. La figure ci-dessous présente un exemple de posture d’atteinte calculée conjointement avec les empreintes de pas qui y mènent.
La figure ci-dessus tirée de (Yoshida et al., 2006) illustre un schéma global de génération de mouvement de manipulation qui nécessite un pas. La génération de mouvement comprend :
– une heuristique pour déterminer la position du pas nécessaire à la réalisation de la tâche,
– la résolution de tâche de cinématique inverse hiérarchisée, qui inclut un contrôleur de ZMP.
Dans (Kanoun et al., 2010), une extension de ce travail propose un placement automatique des empreintes de pas, en intégrant au calcul de cinématique inverse une chaîne articulaire virtuelle composée des emplacements des empreintes de pas. La figure ci-dessous présente un exemple de posture d’atteinte calculée conjointement avec les empreintes de pas qui y mènent.
Calcul automatique des empreintes de pas nécessaires à la réalisation d’une tâche d’atteinte. Le calcul se fait en intégrant la position des pas comme une chaîne articulaire virtuelle dans le calcul de cinématique inverse. Figure tirée de (Kanoun et al.,2010).
Un robot évoluant en présence de l’Homme doit modifier en ligne ses mouvements pour s’adapter aux mouvements des humains tout en respectant les contraintes cinématiques de limitation de la vitesse, de l’accélération et du jerk. Cependant les planificateurs de trajectoire sont limites au calcul des mouvements entre deux états avec conditions initiales quelconques en vitesse et accélération et des conditions finales en vitesse quelconques, mais nulle en accélération. Ils ne permettent donc pas de respecter les contraintes demandées.