Un robot humanoïde est un système complexe doté de nombreux degrés de liberté, et dont le comportement est sujet aux équations non linéaires du mouvement. Par conséquent, la planification de mouvement pour un tel système est une tâche difficile d'un point de vue calculatoire. Dans ce mémoire, nous avons pour objectif de développer une méthode permettant d'utiliser la puissance de calcul des GPUs dans le contexte de la planification de mouvement corps-complet basée sur de l'optimisation. Nous montrons dans un premier temps les propriétés du problème d'optimisation, et des pistes d'étude pour la parallélisation de ce dernier. Ensuite, nous présentons notre approche du calcul de la dynamique, adaptée aux architectures de calcul parallèle. Cela nous permet de proposer une implémentation de notre problème de planification de mouvement sur GPU: contraintes et gradients sont calculés en parallèle, tandis que la résolution du problème même se déroule sur le CPU. Nous proposons en outre une nouvelle paramétrisation des forces de contact adaptée à notre problème d'optimisation. Enfin, nous étudions l'extension de notre travail au contrôle prédictif. / A humanoid robot is a complex system with numerous degrees of freedom, whose behavior is subject to the nonlinear equations of motion. As a result, planning its motion is a difficult task from a computational perspective.In this thesis, we aim at developing a method that can leverage the computing power of GPUs in the context of optimization-based whole-body motion planning. We first exhibit the properties of the optimization problem, and show that several avenues can be exploited in the context of parallel computing. Then, we present our approach of the dynamics computation, suitable for highly-parallel processing architectures. Next, we propose a many-core GPU implementation of the motion planning problem. Our approach computes the constraints and their gradients in parallel, and feeds the result to a nonlinear optimization solver running on the CPU. Because each constraint and its gradient can be evaluated independently for each time interval, we end up with a highly parallelizable problem that can take advantage of GPUs. We also propose a new parametrization of contact forces adapted to our optimization problem. Finally, we investigate the extension of our work to model predictive control.

Utilisation du raisonnement géométrique pour la planification de mouvements en robotique. Utilisation de l'intelligence artificielle et de la modélisation géométrique pour la programmation automatique des robots. Cas des mouvements fins correspondants a un assemblage

L'interaction Homme-Robot est un domaine de recherche qui se développe de manière expo-nentielle durant ces dernières années, ceci nous procure de nouveaux défis au raisonnement géométrique du robot et au partage d'espace. Le robot pour accomplir une tâche, doit non seulement raisonner sur ses propres capacités, mais également prendre en considération la perception humaine, c'est à dire "Le robot doit se placer du point de vue de l'humain". Chez l'homme, la capacité de prise de perspective visuelle commence à se manifester à partir du 24ème mois. Cette capacité est utilisée pour déterminer si une autre personne peut voir un objet ou pas. La mise en place de ce genre de capacités sociales améliorera les capacités cognitives du robot et aidera le robot pour une meilleure interaction avec les hommes. Dans ce travail, nous présentons un mécanisme de raisonnement spatial de point de vue géométrique qui utilise des concepts psychologiques de la "prise de perspective" et "de la rotation mentale" dans deux cadres généraux: - La planification de mouvement pour l'interaction homme-robot: le robot utilise "la prise de perspective égocentrique" pour évaluer plusieurs configurations où le robot peut effectuer differentes tâches d'interaction. - Une interaction face à face entre l'homme et le robot : le robot emploie la prise de point de vue de l'humain comme un outil géométrique pour comprendre l'attention et l'intention humaine afin d'effectuer des tâches coopératives.

Un système robotique agit par le mouvement dans un monde physique. La capacité deplanification de mouvement est donc une composante essentielle de l'autonomie du système et constitue un domaine de recherche très actif en Robotique. Le champ d'application de ces méthodes dépasse aujourd'hui le cadre de la Robotique et intéresse des domaines aussi diversifiés que la CAO, la logistique industrielle, l'animation graphique ou la biologie moléculaire. Dans tous ces domaines on est confronté au mouvement de systèmes complexes contenant des chaînes cinématiques fermées. Cette thèse traite de la planification de mouvement pour de tels systèmes. La première partie présente notre contribution théorique et technique. Après avoir proposé une formulation générale de la planification de mouvement sous contrainte de fermeture cinématique, nous décrivons une méthode qui s'inscrit dans le cadre des techniques d'exploration par échantillonnage. Les outils algorithmiques que nous proposons permettent une application efficace de ces techniques à des systèmes mécaniques complexes. La deuxième partie traite de l'utilisation de ces outils pour la résolution de divers problèmes. En Robotique, nos algorithmes ont été appliqués à la synthèse de mouvement de mécanismes parallèles, à la manipulation coordonnée ainsi qu'à la planification de tâches de manipulation d'objets. Enfin, nous abordons une application originale à la biologie structurale pour l'étude des capacités de mobilité de boucles protéiques. Les résultats obtenus à travers ces applications montrent l'efficacité et la généralité de notre approche.

Dans cette thèse nous nous intéressons à deux types d'approches pour la planification de pas pour robots humanoïdes : d'une part les approches discrètes où le robot n'a qu'un nombre fini de pas possibles, et d'autre part les approches où le robot se base sur des zones de faisabilité continues. Nous étudions ces problèmes à la fois du point de vue théorique et pratique. En particulier nous décrivons deux méthodes originales, cohérentes et efficaces pour la planification de pas, l'une dans le cas discret (chapitre 5) et l'autre dans le cas continu (chapitre 6). Nous validons ces méthodes en simulation ainsi qu'avec plusieurs expériences sur le robot HRP-2.

La planification du mouvement connait une utilisation croissante dans le contexte industriel. Qu'elle soit destinée à la programmation des robots dans l'usine ou au calcul de l'assemblage d'une pièce mécanique, la planification au travers des algorithmes probabilistes est particulièrement efficace pour résoudre des problèmes complexes et difficiles pour l'opérateur humain. Cette thèse CIFRE, effectuée en collaboration entre le laboratoire de recherche LAAS-CNRS et la jeune entreprise Kineo CAM, s'attache à résoudre la problématique de planification de mouvement dans l'usine numérique. Nous avons identifié trois domaines auxquels s'intéressent les partenaires industriels et nous apportons des contributions dans chacun d'eux: la détection de collision, le volume balayé et le mouvement en collision. La détection de collision est un opérateur critique pour analyser des maquettes numériques. Les algorithmes de planification de mouvement font si souvent appel à cet opérateur qu'il représente un point critique pour les performances. C'est pourquoi, il existe une grande variété d'algorithmes spécialisés pour chaque type de géométries possibles. Cette diversité de solutions induit une difficulté pour l'intégration de plusieurs types de géométries dans la même architecture. Nous proposons une structure algorithmique rassemblant des types géométriques hétérogènes pour effectuer les tests de proximité entre eux. Cette architecture distingue un noyau algorithmique commun entre des approches de division de l'espace, et des tests spécialisés pour un couple de primitives géométriques donné. Nous offrons ainsi la possibilité de facilement ajouter des types de données nouveaux sans pénaliser la performance. Notre approche est validée sur un cas de robot humanoïde qui navigue dans un environnement inconnu grâce à la vision. Concernant le volume balayé, il est utilisé pour visualiser l'étendue d'un mouvement, qu'il soit la vibration d'un moteur ou le geste d'un mannequin virtuel. L'app roche la plus innovante de la littérature repose sur la puissance du matériel graphique pour approximer le volume balayé très rapidement. Elle est toutefois limitée en entrée à un seul objet, qui lui-même doit décrire un volume fermé. Afin d'adapter cet algorithme au contexte de la conception numérique, nous modifions son comportement pour traiter des " soupes de polygones " ainsi que des trajectoires discontinues. Nous montrons son efficacité sur les mouvements de désassemblage pour des pièces avec un grand nombre de polygones. Une soupe de polygones est plus difficile à manipuler qu'un volume bien formé. Le calcul du volume balayé introduit des opérateurs d'agrandissement et de rétrécissement des objets discrétisés. Le rétrécissement peut être utilisé pour d'autres applications dans la planification du mouvement à condition que la topologie de l'objet soit conservée pendant la transformation. Afin de préserver celle-ci, nous définissons le calcul du squelette qui préserve l'équivalence topologique. En gardant le squelette, nous employons l'opérateur de rétrécissement pour chercher les passages étroits des problèmes difficiles de planification de mouvement. Enfin, nous abordons le problème de la planification de mouvement en collision. Cette antilogie exprime la capacité d'autoriser une collision bornée pendant la recherche de trajectoire. Ceci permet de résoudre certains problèmes d'assemblage très difficiles. Par exemple, lors du calcul des séquences de désassemblage, il peut être utile de permettre à des "pièces obstacles" telles que les vis de se déplacer pendant la planification. De plus, en autorisant la collision, nous sommes capables de résoudre des problèmes de passage en force. Cette problématique se pose souvent dans la maquette numérique où certaines pièces sont " souples " ou si le problème consiste à identifier la trajectoire "la moins pire" quand aucun chemin sans collision n'existe. Nous apportons dans ce travail plusieurs contributions qui s'appliq uent à la conception numérique pour la robotique industrielle. Nous essayons de marier une approche scientifique avec des critères de fonctionnalités strictes pour mieux s'adapter aux utilisateurs de la conception numérique. Nous cherchons à exposer les avantages et les inconvénients de nos approches tout au long du manuscrit.

Ce manuscrit met en avant la capacité d'un robot humanoïde à effectuer une tâche difficilement réalisable par d'autres types de robots. On s'intéresse ici à la manipulation d'objets dits encombrants. De telles tâches de manipulation s'effectuent avec beaucoup de difficultés et font appel à plusieurs aptitudes, telles la prise en compte du mouvement du corps dans son ensemble (ou mouvement corps complet) et une parfaite synchronisation entre les différents membres, bras et jambes. Nous introduisons ici un planificateur de mouvements corps complet qui donne à un robot humanoïde la capacité de mettre en place, automatiquement, une stratégie de déplacement d'objets encombrants par pivotement, tout en prenant en compte un certain nombre de contraintes : évitement de collisions, coordination des membres, bras et jambes, et contrôle de la stabilité pendant tout le déplacement. Basé sur des résultats formels, définis en amont, prouvant la contrôlabilité en temps petit d'un système se déplaçant par pivotement. Le planificateur hérite aussi de la complétude probabiliste des méthodes d'échantillonnage aléatoire de planification sur lesquelles il est construit. Les capacités géométriques et cinématiques du planificateur proposé sont aussi démontrées à travers des simulations et des expérimentations réelles. Nous nous intéressons ensuite à résoudre des problèmes plus complexes, en offrant au robot la possibilité de lâcher et de reprendre l'objet à manipuler si celui-ci est bloqué dans un passage étroit.

L'objectif de cette thèse est d'étendre l'utilisation des modèles de calcul de la dynamique du véhicule en proposant de nouvelles méthodologies inspirées du domaine de la planification de mouvements. Les modèles de dynamique du véhicule que nous considérons sont de nature industrielle : ils sont complexes, non linéaires et disponibles en règle générale sous forme de boîte noire uniquement. Ils sont utilisés traditionnellement avec des techniques de simulations qui partent d'une définition précise d'un état de départ et des sollicitations venant du conducteur. Les méthodes que nous proposons visent à prendre en compte une description plus "réelle" de la manoeuvre ou du test qu'effectue le véhicule : un certain domaine initial dont part le véhicule, un couloir à suivre sans sortir des limites, et un domaine d'arrivée. Outre la recherche d'une solution à ce problème de réalisation d'une certaine manoeuvre, on traite également les deux problèmes suivants : produire un échantillon représentatif de l'ensemble des manières de réaliser la man÷uvre ; trouver la valeur limite d'un paramètre (par exemple la vitesse initiale) au-delà de laquelle il n'y a plus de solution. Différentes techniques ont été mises en oeuvre avec succès, citons notamment : des méthodes exploratoires, un outil de contrôle optimal et un algorithme modifié de déformation de trajectoire. Ces outils génériques sont tous capables de s'adapter sans peine à toutes sortes de véhicules ou d'obstacles. Chacun présente cependant des avantages et des contraintes spécifiques. Ces méthodes ont été appliquées aux cas particuliers de manoeuvres standardisées de véhicules de tourisme. Les méthodes proposées permettent de déterminer de manière robuste et cohérente les limites physiques des véhicules sur ces tests.

Les protéines sont des macromolécules participant à d’importants processus biophysiques de la vie des organismes. Or, il a été démontré que des variations de leur structure peuvent conduire à des changements de fonction en lien avec certaines maladies telles que celles associées à des processus neurodégénératifs. Ainsi, tant pour la communauté scientifique que pour l’industrie médicale, il est capital d’avoir une meilleure compréhension de la structure de ces protéines, ainsi que de leurs interactions avec d’autres molécules, ce en vue d’inventer et d’évaluer de nouveaux médicaments.Au cours de ces travaux de thèse, nous nous sommes particulièrement intéressés au développement de nouvelles méthodes de recherche de chemins biologiquement faisables entre deux états connus pour un système composé d’une protéine ou d’une protéine et d’un ligand. Au cours des dernières décennies, une grande quantité d’approches algorithmiques ont été proposées pour faire face à ce problème. Pourtant, les méthodes développées sont encore aujourd’hui confrontées à deux grands défis : d’une part la haute dimension des espaces de recherche, associée au grand nombre d’atomes impliqués, d’autre part la complexité des interactions entre ces atomes.Cette dissertation propose deux nouvelles méthodes pour obtenir de manière efficace des chemins pertinents pour des systèmes moléculaires. Ces méthodes sont rapides et génèrent des solutions qui peuvent ensuite être analysées ou améliorées à l’aide de méthodes d’avantage spécialisées. La première approche proposée produit des chemins d’interpolation pour systèmes biomoléculaires, à l’aide des approches dites aussi-rigides-que-possible, (ARAP) utilisées en animation graphique. Cette méthode est robuste et génère des solutions préservant au mieux la rigidité du système d’origine. Une extension de cette méthode basée sur des critères énergétiques a également été proposée et s’est avérée capable d’améliorer de manière significative les chemins solution. Cependant, pour les scénarios nécessitant de complexes déformations, cette approche géométrique peut conduire à des chemins solution non naturels. Nous avons donc proposé une seconde méthode appelée ART-RRT, qui utilise l’approche ARAP pour réduire la dimensionalité de l’espace et la combine avec les arbres d’exploration RRT (Rapidely-exploring Random Tree) issus de la Robotique, afin d’explorer efficacement les chemins possibles de l’espace.En plus de fournir une variété de solutions en temps raisonnable, cette ART-RRT produit des chemins de faible énergie, sans collision et dont la rigidité est préservée autant que possible. Des versions monodirectionnelles de bidirectionelles de cette méthode ont été proposées et appliquées respectivement à la recherche de chemin d’extraction d’un ligand hors du site actif d’une protéine, ainsi qu’a la recherche de chemin de transition conformationnelle pour protéine seule. Les solutions trouvées se sont avérées être en accord avec les données expérimentales ainsi qu’avec les solutions issues de l’état de l’art. / Proteins are macromolecules participating in important biophysical processes of living organisms. It has been shown that changes in protein structures can lead to changes in their functions and are found linked to some diseases such as those related to neurodegenerative processes. Hence, an understanding of their structures and interactions with other molecules such as ligands is of major concern for the scientific community and the medical industry for inventing and assessing new drugs.In this dissertation, we are particularly interested in developing new methods to find for a system made of a single protein or a protein and a ligand, the pathways that allow changing from one state to another. During past decade, a vast amount of computational methods has been proposed to address this problem. However, these methods still have to face two challenges: the high dimensionality of the representation space, associated to the large number of atoms in these systems, and the complexity of the interactions between these atoms.This dissertation proposes two novel methods to efficiently find relevant pathways for such biomolecular systems. The methods are fast and their solutions can be used, analyzed or improved with more specialized methods. The first proposed method generates interpolation pathways for biomolecular systems using the As-Rigid-As-Possible (ARAP) principle from Computer Graphics. The method is robust and the generated solutions preserve at best the local rigidity of the original system. An energy-based extension of the method is also proposed, which significantly improves the solution paths. However, in scenarios requiring complex deformations, this geometric approach may still generate unnatural paths. Therefore, we propose a second method called ART-RRT, which combines the ARAP principle for reducing the dimensionality, with the Rapidly-exploring Random Trees from Robotics for efficiently exploring possible pathways. This method not only gives a variety of pathways in reasonable time but the pathways are also low-energy and clash-free, with the local rigidity preserved as much as possible. The mono-directional and bi-directional versions of the ART-RRT method were applied for finding ligand-unbinding and protein conformational transition pathways, respectively. The results are found to be in good agreement with experimental data and other state-of-the-art solutions.

Cette thèse traite de deux problèmes qui ont leur origine dans la théorie du contrôle géométrique, et qui concernent les systèmes de contrôle avec dérive, c'est-à-dire de la forme $\dot q= f_0(q)+\sum_{j=1}^m u_j f_j(q)$. Dans la première partie de la thèse, on généralise le concept de complexité de courbes non-admissibles, déjà bien compris pour les systèmes sous-riemanniens, au cas des systèmes de contrôle avec dérive, et on donne des estimations asymptotiques de ces quantités. Ensuite, dans la deuxième partie, on considère une famille de systèmes de contrôle sans dérive en dimension 2 et on s'intéresse à l'operateur de Laplace-Beltrami associé et à l'évolution de la chaleur et des particules quantiques qu'il définit. On étudie plus particulièrement l'effet qu'a l'ensemble où les champs de vecteurs contrôlés deviennent colinéaires sur ces évolutions.