Soutenance mémoire
Planification de mouvement
Concepts Dans cette section, nous allons décrire des concepts de planification de mouvement importants que nous utiliserons tout au long de ce mémoire.
– L’espace de travail, noté W, est l’espace dans lequel la géométrie de l’environnement et du robot est décrite.
– Le nombre de degré de liberté, noté ddl, indique le nombre de paramètres indépendants nécessaires pour caractériser les transformations à appliquer à un système pour le déplacer.
– Une configuration correspond à l’ensemble des valeurs de chaque ddl pour une situation précise du système. Elle caractérise le placement de tous les corps du système.
– L’espace des configurations, notéCS, est l’ensemble des configurations possibles pour le système. Le déplacement du système dans l’espace de travail correspond au déplacement d’un point dans l’espace des configurations..
– Une méthode de détection de collision permet de définir si le système est en collision avec un obstacle pour une configuration donnée. Collision : CS → 0,1
– L’espace des configurations libres, noté CSf ree est l’ensemble des configurations de CS qui ne sont pas en collision avec un obstacle de l’environnement. ∀qi ∈ CS : Collision(qi) → qi ∈/ CSf ree
– La méthode d’échantillonnage permet de choisir une configuration appartenant à CS.
– Un échantillon est la configuration choisie par la méthode d’échantillonnage.
– Un chemin est une fonction Chemin : [0 1] → CS qui relie deux configurations de CS.
L’ensemble des chemins de CS est noté C.
– La méthode locale est une méthode liée au système à déplacer qui permet de définir un chemin entre deux configurations de CS. ML : CS×CS → C
– Une composante connexe d’un graphe est une sous-partie CC d’un graphe G telle que (∀qi ∈ CC)∧(∀qj ∈ CC) : ∃Chemin(qi,qj) ∈ G
Le problème de la planification de mouvement D’une manière générale, planifier un mouvement revient à ordonner les positions d’un corps dans l’espace afin de lui faire atteindre une position voulue. Pour un être humain, planifier un mouvement est une action naturelle. Il peut planifier facilement ses déplacements, ainsi que ceux des objets qu’il contrôle : voitures, bateaux, avions, etc. Mais dans certaines situations, cela devient un problème complexe qui nécessite beaucoup de temps et d’efforts. L’exemple le plus représentatif est celui du problème du sofa (illustré figure 2.1), posé par Leo Moser en 1966 [Moser 1966], qui revient à chercher la plus grande taille de sofa que l’on puisse déplacer dans un couloir à angle droit, de largeur unitaire. Ce type de problème est à l’origine des travaux dans le domaine de la planification de mouvement en robotique. Plus tard, Schwarz et Sharir posent les bases du problème du déménageur de piano [Schwartz and Sharir 1987], qui consiste à déplacer un piano composé d’un seul bloc à travers une pièce encombrée d’obstacles (figure 2.2). Ce problème sera ensuite étendu par J.H. Reif comme le « problème général du déménageur ». Cette généralisation consiste à déplacer un objet quelconque, qui peut-être composé de plusieurs corps articulés entre eux (on peut prendre comme exemple une chaîne, ou un train composé de plusieurs wagons). Le déplacement d’un piano ou celui d’un corps articulé peuvent être vus comme deux problèmes totalement différents, bien qu’ils soient similaires. La question est de trouver une méthodologie permettant d’avoir une approche générique de ce type de problèmes. T. Lozano-Perez propose une solution originale. Il s’agit de présenter le problème, non pas dans l’espace de travail W, mais dans un espace qui peut rendre compte de toutes les situations possibles du corps considéré. Par exemple, pour un corps articulé, chaque articulation peut représenter un ou plusieurs degrés de liberté. Un objet « volant » (c’est-à-dire qui peut se déplacer librement dans toutes les directions), peut bouger selon ses six degrés de liberté : trois pour les translations et trois pour les rotations. La position de cet objet serait donc décrite par six paramètres, chaque paramètre étant la valeur d’un des degrés de liberté. L’ensemble de ces paramètres est appelé une configuration. Le nombre de paramètres définissant la configuration de l’objet considéré correspond à la dimension de CS. Ainsi, une configuration dans CS définit un placement de l’objet dans W. Il est possible de décrire le problème général du déménageur comme étant la recherche d’un chemin dans l’espace des configurations libres entre une configuration initiale et une configuration finale. Le passage de l’espace de travail W vers l’espace des configurations CS est illustré pour un objet simple avec deux degrés de liberté en translation sur la figure 2.3. Le problème de déplacer un système (ensemble de corps) dans un espace de travail W revient à déplacer un point dans un CS de dimension n. Chaque configuration q de dimension n contient alors la situation de tous les corps du système. Depuis lors, ce problème a été transposé dans différents domaines allant de l’industrie à la biologie. Les différentes applications que nous pouvons trouver aujourd’hui à la planification de mouvement sont aussi variées que les bras robotiques utilisés dans les usines, garer une voiture, déplacer les rovers envoyés dans l’espace ou des robots humanoïdes ou encore résoudre les problèmes de pliage de molécules. De nombreuses méthodes ont été proposées pour résoudre la problématique d’une manière générale. On peut se référer à [Latombe 1991; Choset et al. 2005] pour une description plus précise de ces méthodes. Parmi les premières méthodes proposées, on trouve les méthodes dites déterministes. Les méthodes déterministes peuvent être exactes et sont dites complètes dans ce cas, c’est-àdire que si une solution existe, elle sera trouvée, sinon la méthode pourra dire qu’il n’y a pas de solution. D’un autre côté, les méthodes déterministes dites approchées ne sont pas complètes mais possèdent certaines propriétés intéressantes, telles que la complétude en résolution (si une solution existe, elle sera trouvée en temps fini). Elles reposent sur le calcul d’une représentation de l’espace des configurations, qui permet de construire un graphe donnant la connexité de l’environnement. Parmi ces méthodes on peut trouver la décomposition en octree, les diagrammes de Voronoï ou encore les graphes de visibilité (figure 2.4). À partir du graphe construit, on peut chercher un chemin partant d’une configuration initiale jusqu’à une configuration finale quelconque, tout en évitant les obstacles. La recherche du chemin solution revient donc à la recherche d’un chemin dans le graphe. Si la configuration initiale et la configuration finale appartiennent à la même composante connexe du graphe, l’existance d’un chemin entre ces deux configurations est garantie. Mais malgré leurs propriétés, ces algorithmes ne permettent de résoudre en pratique que des problèmes simples avec des espaces des configurations de faible dimension (inférieure à six), car le temps de calcul augmente rapidement avec l’augmentation du nombre de degrés de liberté [Canny 1988]. Pour résoudre des cas pratiques, qui souvent ont un nombre de degrés de liberté supérieur ou égal à six, des algorithmes basés sur l’échantillonnage aléatoire de l’espace des configurations ont été introduits dans les années 1990. Ces méthodes perdent les propriétés des méthodes déterministes (complétude) au profit d’un meilleur temps de calcul. Néanmoins, ces méthodes dites probabilistes garantissent une complétude en probabilité : la probabilité de trouver une solution converge vers 1 quand le temps de calcul tend vers l’infini, si la solution existe. Ces algorithmes se basent donc sur une méthode d’échantillonnage qui permet de fournir une configuration (alors appelée échantillon) appartenant à l’espace des configurations de l’objet considéré pour construire un graphe représentant CSf ree. Tout l’intérêt de ces méthodes repose sur le fait qu’elles évitent de construire explicitement l’espace des configurations nonlibres. Dans le cas des méthodes déterministes, c’est cette partie qui prend le plus de temps de calcul. En fonction des algorithmes, les graphes construits permettent de capturer la connexité de CSf ree, car ils peuvent être composés de une ou plusieurs composantes connexes. Une composante connexe d’un graphe est une sous-partie de ce graphe dans laquelle on peut atteindre un nœud à partir de n’importe quel autre nœud, chaque nœud du graphe correspondant à une configuration de CSf ree. Parmi les différents algorithmes probabilistes existants, deux méthodes se sont imposées comme méthodes de base dans le domaine de la planification probabiliste. La première a été introduite dans [Kavraki et al. 1996], il s’agit de la méthode « Probabilistic RoadMap » (PRM), dont le principe est illustré sur la figure 2.5. L’idée de base de cette méthode est d’échantillonner PRM. Le graphe est d’abord construit, puis un chemin est trouvé dans ce graphe pour relier les configurations qinit et qend l’espace des configurations afin de trouver des configurations sans collisions. Chaque configuration échantillonnée est testée pour savoir si elle est libre ou en collision à l’aide d’un détecteur de collisions. Les échantillons sans collisions sont ajoutés à un graphe et la création d’une arête avec les autres nœuds du graphe est tentée. Cette connexion est réalisée grâce à une méthode locale. La méthode locale permet de relier un nœud à un autre avec un chemin libre de collisions. Une méthode locale de base peut être par exemple une simple interpolation linéaire entre les deux nœuds concernés. Lorsqu’une recherche de chemin est demandée, les configurations initiale et finale de la demande sont ajoutées au graphe et des arêtes connectant ces configurations au graphe sont créées. Celui-ci est ensuite parcouru par un algorithme de type A⋆ pour trouver le chemin entre les deux configurations. Cette méthode permet de conserver le graphe construit afin de pouvoir effectuer des planifications successives très rapidement dans le même environnement, mais pour des configurations initiale et finale différentes. L’intérêt de ce type de méthode est qu’elles ne calculent pas CS, tous les tests de collision étant faits dans W. Dans ce cas, il faut que le graphe contienne suffisamment d’informations pour avoir une couverture représentative de l’espace des configurations libres. Cette étape qui demande un certain temps est généralement effectuée hors-ligne (avant qu’une requête de planification ne soit reçue). Une construction représentative de CSf ree est très coûteuse, notamment dans le cas où le graphe n’est utilisé qu’une seule fois. Dans la section suivante est introduite la deuxième méthode de base, qui est une méthode de diffusion qui permet d’éviter la construction complète du graphe qui représente implicitement CSf ree.
Les arbres de diffusion Les méthodes de diffusion permettent de construire un graphe rapidement, à usage unique et qui ne nécessite pas forcément de couvrir la totalité de l’espace des configurations pour trouver le chemin solution. Dans cette section nous allons décrire l’une des méthodes de diffusion, les « Rapidly-exploring Random Trees » (RRT, introduite dans [LaValle 1998]), qui sera la méthode de base de tous les travaux présentés dans ce mémoire. L’objectif de l’algorithme RRT est de construire un arbre, c’est-à-dire un graphe généralement non-orienté et dont les différentes composantes connexes ne contiennent pas de boucles. Chaque nœud du graphe possède donc un seul et unique nœud parent (sauf pour la racine de l’arbre, qui est le premier nœud du graphe, en général la configuration initiale) et plusieurs nœuds fils (sauf pour les feuilles de l’arbre qui n’en ont pas). En partant d’une configuration initiale, l’algorithme RRT explore incrémentalement l’espace des configurations pour trouver un chemin atteignant la configuration finale. Ainsi, l’algorithme RRT se diffuse de proche en proche pour explorer CS et atteindre la configuration finale. L’algorithme peut se décomposer en cinq étapes (illustrées sur la figure 2.6 et l’algorithme1) :
– À l’initialisation, la configuration initiale qinit est ajoutée au graphe.
– À chaque itération, une nouvelle configuration qrand est échantillonnée (RANDOM_CONF IG).
– On recherche ensuite le nœud qnear le plus proche de qrand dans l’arbre existant (NEAREST_NODE).
– On essaie enfin d’étendre l’arbre à partir de qnear dans la direction de qrand d’une longueur ε (CONNECT).
– Si l’extension réussit, on ajoute la nouvelle configuration créée qnew dans l’arbre et on recommence à l’étape 2 jusqu’à ce que la configuration finale qgoal soit atteinte (une tentative de connexion vers qgoalpeut être effectuée à une fréquence prédéterminée).
La façon dont l’algorithme RRT se diffuse dépend en premier lieu de la méthode d’échantillonnage aléatoire. Une méthode commune est l’échantillonnage uniforme sur l’espace des configurations. Cette méthode permet d’avoir une probabilité équivalente pour chaque configuration de CS d’être choisie comme échantillon. Dans beaucoup de méthodes prenant l’algorithme RRT comme base, un biais vers la configuration finale est introduit pour diriger la recherche et ne pas effectuer uniquement une exploration aléatoire. Dans l’algorithme 1, ainsi que dans les autres algorithmes de ce document, N est un nombre d’itérations fixe décidé empiriquement qui représente la limite autorisée pour résoudre le problème (les algorithmes de diffusion aléatoire ne donnant aucune garantie quant au temps de résolution). Plusieurs variantes de cette méthode ont ensuite été développées [LaValle 2006]. Parmi celles-ci, on peut citer l’algorithme RRT bi-directionnel [LaValle and Kuffner 1999] dont le principe est de construire deux arbres de diffusion, l’un ayant sa racine à la configuration initiale et l’autre à la configuration finale. La résolution du problème est ainsi plus rapide en probabilité car les deux arbres s’étendent l’un vers l’autre. L’algorithme RRT « connect » [Kuffner and LaValle 2000] permet une exploration plus rapide de CS car l’extension de qnear vers qrand est maximisée : on étend l’arbre jusqu’à qrand ou jusqu’à rencontrer un obstacle. Ainsi l’espace libre est exploré très rapidement jusqu’aux obstacles les plus proches. Ces méthodes probabilistes ont néanmoins des limites : une couverture suffisante deCS pour trouver la solution n’est pas toujours garantie, notamment dans le cas où il y a des passages étroits dans l’environnement. De plus, ces méthodes ne permettent pas de détecter l’absence de solution et d’arrêter l’échantillonnage de CS s’il n’y en a pas.
Les murs
Dans ces tests, dont l’espace de travail est illustré sur la figure 2.17, l’espace des configurations est de dimension 6 (X,Y,Z,φ,ρ,θ) et le robot est polygonal avec 3 ddl en translation et 3 ddl en rotation. Le but est de traverser chaque mur en empruntant le passage étroit (trou) qui y est placé différemment sur chacun. Les dimensions de chaque mur sont de 100x100x5 et pour chaque passage de 25×25 à l’intérieur du mur, pour la première série de tests (nommée 5p0 dans les tableaux et figures). Pour la seconde série de tests, les passages ont une taille de 20×20. Les dimensions du robot sont de 5x5x25. Les algorithmes ont été testés sur quatre environnements qui diffèrent par leur nombre de murs (et donc de passages étroits à traverser) : 2, 4, 6 et 8 murs. On peut voir sur les tableaux 2.6 et 2.7 que la méthode V ISLT a résolu les problèmes en moins de temps et d’itérations que les autres méthodes. Le nombre de nœuds dans le graphe final (après la résolution du problème) est même inférieur pour les arbres locaux de visibilité que pour les arbres locaux basique. Pour ces tests, l’algorithme RRT à été omis car ils n’ont aucun intérêt pour cette comparaison.
Le projet AMSI
Les travaux décrits dans ce chapitre ont été réalisés dans le cadre du projet « Algorithmique du Mouvement et Simulation Interactive » (AMSI) de 2007 à 2009. Le projet AMSI est un projet financé par l’Agence Nationale de la Recherche (ANR) dans le cadre du programme « Technologies Logicielles ». Le projet portait sur l’assemblage mécanique au sein de maquettes numériques. Il s’agit de concevoir et de réaliser des solutions de recherche de chemins dans ces modèles permettant de prendre en compte les actions d’un opérateur humain en temps réel. Contrairement aux méthodes entièrement automatiques, cela permet d’imposer des contraintes « métier » sur les chemins produits, contraintes qui font partie du savoir-faire de l’utilisateur (préférer un passage moins dangereux, passer plus loin d’une certaine pièce …). L’idée de base du projet est de combiner deux approches : l’une entièrement manuelle et réalisée grâce à des bras à retour d’effort (ou bras haptiques) et des systèmes de réalité virtuelle et l’autre, entièrement automatique, est réalisée grâce à des algorithmes de planification de mouvement probabilistes. Le projet regroupait quatre partenaires : deux laboratoires (le CEA-LIST et le LAAS CNRS) et deux start-ups (Haption et Kineo CAM). Pour atteindre l’objectif, trois approches ont été envisagées :
– Un première approche séquentielle, dans laquelle l’opérateur et la partie algorithmique agissent séparément dans deux étapes distinctes et successives. L’opérateur agira alors sur le résultat fourni par l’algorithme afin de l’améliorer.
– Une seconde approche semi-interactive où l’opérateur peut influer ponctuellement sur la recherche automatique. Les parties manuelle et automatique agiraient donc alternativement, mais en étant toujours distinctes l’une de l’autre.
– Une troisième approche, dite interactive, où l’opérateur et l’algorithme coopèrent dans une même recherche, en temps réel, en même temps et sans distinctions entre les deux La méthode décrite dans ce chapitre se place dans le cadre de l’approche interactive.
Travaux précédents L’idée de prendre en compte les actions d’un utilisateur lors d’une recherche de chemin a déjà été étudiée par différents auteurs spécialisés dans le domaine de la planification de mouvement. Dans [Bayazit et al. 2000], les auteurs font travailler un opérateur en commun avec un algorithme de planification de mouvement automatique. Ils montrent que les techniques de planification probabilistes peuvent être utilisées pour transformer un chemin utilisateur approximatif en collision avec l’environnement en un chemin sans collisions. L’idée est de déformer les parties du chemin qui sont en collision en les poussant hors de l’espace obstrué. Dans [Vazquez and Rosell 2007; Rosell et al. 2008] est introduite l’utilisation d’une technique de planification de mouvement basée sur des fonctions harmoniques permettant de générer des forces de guidage qui aident l’utilisateur à se déplacer dans un environnement virtuel. L’idée de base est de calculer un tunnel solution par décomposition cellulaire de l’environnement qui connecte les configurations initiale et finale. Dans un second temps, deux fonctions harmoniques sont calculées sur l’espace des configurations pour trouver un cheminguide. Un algorithme de type RRT incluant des heuristiques basées sur l’étude de l’espace de travail est présenté dans [Ladezeve et al. 2008; Ladeveze et al. 2009]. Le but est de discrétiser l’espace de travail en utilisant un arbre de décomposition type octree non-équilibré. Ensuite les auteurs calculent un volume continu dans l’espace de travail libre entre les configurations initiale et finale en utilisant un A⋆. Dans une seconde étape, un chemin libre de collisions est calculée à partir du volume créé précédemment en utilisant une approche RRT. D’autres travaux en dehors du champs d’application de l’assemblage mécanique existent. Par exemple, dans le domaine de la biologie, des applications étudient les performances d’un planificateur de mouvement utilisant un périphérique à retour d’effort pour prendre en compte des entrées d’un utilisateur [Bayazit et al. 2001]. Dans [He and Chen 2009] les auteurs étudient l’influence d’une intervention humaine sur la vitesse de convergence d’un planificateur de mouvement de type PRM lors d’une tâche de planification. L’utilisateur indique des configurations de passage obligatoires pour le robot en utilisant un périphérique à retour d’effort. Dans tous ces travaux, on peut remarquer que l’interaction entre l’utilisateur et la recherche de chemin automatique est simplifiée en découplant l’algorithme en deux étapes distinctes : une étape où le planificateur de mouvement effectue la recherche seul et une étape ou l’utilisateur intervient seul. Dans ce chapitre, il sera question d’une méthode permettant de faire coopérer les deux parties dans une seule et même boucle d’interaction.
|
Table des matières
1 Introduction
1.1 Contribution
1.2 Organisation du document
1.3 Publications associées
2 Planification de mouvement en environnement mixte
2.1 Introduction
2.1.1 Planification de mouvement
2.2 Travaux précédents
2.2.1 Les arbres locaux
2.2.2 Graphes probabilistes de visibilité
2.3 Le planificateur Arbres Locaux de visibilité
2.3.1 Principe
2.3.2 Implémentation
2.3.3 Expérimentations
2.3.4 Résultats
2.4 Conclusion et Perspectives
3 Le planificateur de mouvement interactif
3.1 Introduction
3.1.1 Le projet AMSI
3.1.2 Travaux précédents
3.2 Le planificateur interactif
3.2.1 Périphériques interactifs
3.2.2 Principe
3.2.3 Expérimentations
3.2.4 Résultats
3.3 Conclusion et Perspectives
4 Le planificateur de locomotion interactif
4.1 Introduction
4.1.1 Travaux précédents
4.1.2 Le contrôleur de locomotion
4.2 Le planificateur de locomotion Interactif
4.2.1 Le planificateur semi-interactif
4.2.2 Le planificateur interactif
4.2.3 Quelques Exemples
4.3 Conclusion et Perspectives
5 Conclusion
5.1 Conclusion
5.2 Perspectives
6 Références
Télécharger le rapport complet
