Planification de mouvement en environnement mixte

Avant de développer la partie interactive de ces travaux, il nous a semblé nécessaire d’améliorer des algorithmes de base déjà existants dans le domaine de la planification de mouvement afin de les adapter à notre thématique. Ce travail est motivé par l’utilisation de ces algorithmes dans le cadre de l’animation graphique. Il s’agira de guider manuellement un personnage virtuel dans un environnement structuré avec l’aide d’un algorithme de planification de mouvement. Ce thème sera abordé dans le dernier chapitre de ce document. Dans ce chapitre, nous étudierons comment adapter un algorithme de base pour une planification dans un environnement structuré pour la locomotion humaine. Ce type d’environnement correspond en réalité à des environnements intérieurs (maisons, usines etc.). Ils sont souvent formés d’une succession de pièces séparées par des passages étroits (portes ou couloirs). C’est donc sur des environnements de ce style que nous nous concentrerons.

Malgré l’apparente simplicité de ces environnements, l’espace de travail en trois dimensions reste assez complexe et une exploration exhaustive par l’algorithme reste hors de question car cela demande trop de ressources et de temps de calcul. La possibilité d’avoir des environnements dynamiques obligeant l’algorithme à ré-explorer certaines zones accentue encore la complexité.

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 , 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 . 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 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é . À 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.

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

Lire le rapport complet