Le problème de la planification du mouvement a été largement étudié dans le cas de corps rigides articulés mais peu de travaux considèrent les corps déformables. En particulier, les tiges élastiques telles que cables électriques, flexibles hydrauliques et pneumatiques, apparaissent dans de nombreux contextes industriels. Du fait d'une modélisation complexe et d'un grand nombre de degrés de liberté, l'extension des méthodes de planification de mouvement à de tels corps est un problème particulièrement difficile. En se basant sur les propriétés des configurations à l'équilibre statique, cette thèse propose plusieurs approches au problème de planification de mouvement pour des tiges élastiques. / The motion planning problem has been broadly studied in the case of articulated rigid body systems but so far few work have considered deformable bodies. In particular, elastic rods such as electric cables, hydraulic or pneumatic hoses, appear in many industrial contexts. Due to complex models and high number of degrees of freedom, the extension of motion planning methods to such bodies is a difficult problem. By taking advantage of the properties of static equilibrium configurations, this thesis presents several approaches to the motion planning problem for elastic rods.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Ce travail de thèse s'inscrit dans le développement d'un véhicule autonome en milieu autoroutier. Plus précisément, il s'agit de proposer une architecture unifiée de génération de trajectoires avec une prise de décision prenant en compte les limitations de l'environnement et des informations disponibles actuellement sur un véhicule automatisé.La méthode propose d'une part de générer des trajectoires sous forme de sigmoı̈de dans une représentation spatiotemporelle continue de l'espace de navigation, préalablement réduit par la modélisation d'intervalles sans collision en conditionnominale de conduite. Les paramètres de la sigmoı̈de sont ensuite optimisés par une stratégie de recuit simulé utilisant l'algorithme de prise de décision comme fonction d'évaluation de la trajectoire générée. De cette manière, les problèmes de discrétisation et de découplage position/vitesse sont évités. D'autre part, l'agrégation des théories de logique floue etdes croyances permet une prise de décision sur des critères hétérogènes et des données incertaines. Le formalisme présenté offre la possibilité d'adapter le comportement du véhicule aux passagers, notamment selon leur perception du risque et leur souhait d'une conduite souple ou sportive.L'approche développée a finalement été évaluée et validée en environnement de simulation puis sur un véhicule de test. La brique de planification a alors été intégrée à l'architecture existante du véhicule, en aval des briques de localisation et de perception des obstacles et en amont de la brique de contrôle. / This thesis work is part of the development of a self-driving car in highway environments. More precisely, it aims to propose a unified architecture of trajectory planner and decision-maker taking into account the limitations of the environment and the available data within the current development of sensors technologies (distance limitations, uncertainties).On the one hand, the method generates sigmoid trajectories in a continuous spatiotemporal representation of the evolution space, which is reduced beforehand by modeling collision-free intervals in nominal conditions of driving. The sigmoid parameters are subsequently optimized with a simulated annealing approach that uses the decision-maker algorithm as the evaluation function for the generated trajectory. It thus makes it possible to elude both the discretization and position/speed decoupling problems. On the other hand, the aggregation of fuzzy logic and belief theory allows decision making on heterogeneous criteria and uncertain data. The proposed framework also handles personalization of the vehicle's behavior, depending on the passengers' risk perception and an aggressive or conservative driving style.The presented approach was finally evaluated and validated in a simulation environment, and then in a test vehicle. The planning block was integrated into the existing vehicle's architecture, interfaced with the localization, obstacles' perception and control blocks.

Afin que les robots humanoïdes puissent travailler avec les humains et être en mesure de résoudre des tâches répétitives, nous devons leur permettre de planifier leurs mouvements de façon autonome. La planification de mouvement est un problème de longue date en robotique, et tandis que sa fondation algorithmique a été étudiée en profondeur, la planification de mouvement est encore un problème NP-difficile et qui manque de solutions efficaces. Nous souhaitons ouvrir une nouvelle perspective sur le problème en mettant en évidence sa structure: le comportement du robot, le système mécanique du robot et l’environnement du robot. Nous allons nous intéresser à l’hypothèse que chaque composante structurelle peut être exploitée pour créer des algorithmes de planification de mouvement plus efficaces. Nous présentons trois algorithmes exploitant la structure, basés sur des arguments géométriques et topologiques: d’abord, nous exploitons le comportement d’un robot de marche en étudiant la faisabilité des transitions des traces de pas. L’algorithme qui en résulte est capable de planifier des traces de pas tout en évitant jusqu’à 60 objets situés sur une surface plane 6 mètres carrés. Deuxièmement, nous exploitons le système mécanique d’un robot humanoïde en étudiant les structures des liaisons linéaires de ses bras et de ses jambes. Nous introduisons le concept d’une trajectoire irréductible, qui est une technique de réduction de dimension préservant la complétude. L’algorithme résultant est capable de trouver des mouvements dans des environnements étroits, où les méthodes d’échantillonnage ne pouvaient pas être appliquées. Troisièmement, nous exploitons l’environnement en raisonnant sur la structure topologique des transitions de contact. Nous montrons que l’analyse de l’environnement est une méthode efficace pour pré-calculer les informations pertinentes pour une planification de mouvement efficace. En s’appuyant sur ces résultats, nous arrivons à la conclusion que l’exploitation de la structure est une composante essentielle de la planification de mouvement efficace. Il en résulte que tout robot humanoïde, qui veut agir efficacement dans le monde réel, doit être capable de comprendre et d’exploiter la structure. / If humanoid robots should work along with humans and should be able to solve repetitive tasks, we need to enable them with a skill to autonomously plan motions. Motion planning is a longstanding core problem in robotics, and while its algorithmic foundation has been studied in depth, motion planning is still an NP-hard problem lacking efficient solutions. We want to open up a new perspective on the problem by highlighting its structure: the behavior of the robot, the mechanical system of the robot, and the environment of the robot. We will investigate the hypothesis that each structural component can be exploited to create more efficient motion planning algorithms. We present three algorithms exploiting structure, based on geometrical and topological arguments: first, we exploit the behavior of a walking robot by studying the feasibility of footstep transitions. The resulting algorithm is able to plan footsteps avoiding up to 60 objects on a 6 square meters planar surface. Second, we exploit the mechanical system of a humanoid robot by studying the linear linkage structures of its arms and legs. We introduce the concept of an irreducible motion, which is a completeness-preserving dimensionality reduction technique. The resulting algorithm is able to find motions in narrow environments, where previous sampling-based methods could not be applied. Third, we exploit the environment by reasoning about the topological structure of contact transitions. We show that analyzing the environment is an efficient method to precompute relevant information for efficient motion planning. Based on those results, we come to the conclusion that exploiting structure is an essential component of efficient motion planning. It follows that any humanoid robot, who wants to act efficiently in the real world, needs to be able to understand and to exploit structure.

L'objet de cette thèse est le développement et l'étude des algorithmes de planification de mouvement pour les systèmes hautement dimensionnés que sont les robots humanoïdes et les acteurs virtuels. Plusieurs adaptations des méthodes génériques de planification de mouvement randomisées sont proposées et discutées. Une première contribution concerne l'utilisation de techniques de réduction de dimension linéaire pour accélérer les algorithmes d'échantillonnage. Cette méthode permet d'identifier en ligne quand un processus de planification passe par un passage étroit de l'espace des configurations et adapte l'exploration en fonction. Cet algorithme convient particulièrement bien aux problèmes difficiles de la planification de mouvement pour l'animation graphique. La deuxième contribution est le développement d'algorithmes randomisés 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 différents problèmes de manipulation pour robots humanoïdes. Cette contribution est généralisée à la planification de mouvements corps-complet nécessitant de la marche. 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 propres à l'objet manipulé utilisables par un planificateur de mouvement. Ce formalisme est présenté sous le nom d'« objets documentés». / This thesis deals with the development and analysis of motion planning algorithms for high dimensional systems: humanoid robots and digital actors. Several adaptations of generic randomized motion planning methods are proposed and discussed. A first contribution concerns the use of linear dimensionality reduction techniques to speed up sampling algorithms. This method identifies on line when a planning process goes through a narrow passage of some configuration space, and adapts the exploration accordingly. This algorithm is particularly suited to difficult problems of motion planning for computer animation. The second contribution is the development of randomized algorithms for motion planning under constraints. It consists in the integration of prioritized inverse kinematics tools within randomized motion planning. We demonstrate the use of this method on different manipulation planning problems for humanoid robots. This contribution is generalized to whole-body motion planning with locomotion. The last contribution of this thesis is the use of previous methods to solve complex manipulation tasks by humanoid robots. More specifically, we present a formalism that represents information specific to a manipulated object usable by a motion planner. This formalism is presented under the name of "documented object".

Le probleme aborde dans ce mémoire est celui de la planification des mouvements d'un mobile a soumis a des contraintes cinématiques et dynamiques et se déplaçant dans un espace de travail dynamique w. Ce mémoire défend la thèse selon laquelle le probleme considère, connu pour être complexe, peut entre résolu de façon efficace lorsqu'il existe une structuration de w naturelle pour a, i.e. Lorsqu'il est possible de structurer w en un ensemble de zones libres a l'intérieur desquelles a peut se déplacer. Dans ce cas, le probleme peut être aborde suivant deux directions complémentaires: 1) la planification de chemin qui prend en compte les contraintes cinématiques de a et les obstacles fixes de w, et; 2) la planification de trajectoire qui prend en compte les contraintes dynamiques de a et les obstacles mobiles de w. Ce mémoire traite le cas d'une voiture dans le réseau routier. Les zones libres sont alors définies par les voies de circulation. A est soumis a une contrainte cinématique non-holonome qui l'oblige a se déplacer dans une direction perpendiculaire a l'axe de ses roues. De plus, le rayon de braquage, l'accélération et la vitesse de a sont limites. Nous commençons par présenter deux techniques de resolution propres a chacune des deux planifications mentionnées ci-dessus et bien adaptées au contexte dans lequel nous nous plaçons. Puis, nous montrons comment intégrer ces deux techniques au sein d'un système de planification de mouvement qui permet de résoudre efficacement le probleme considéré

Contributions à la planification de mouvement.

La compréhension et la prédiction des relations structure-fonction de protéines par des approches in sillico représentent aujourd'hui un challenge. Malgré le développement récent de méthodes algorithmiques pour l'étude du mouvement et des interactions moléculaires, la flexibilité de macromolécules reste largement hors de portée des outils actuels de modélisation moléculaire. L'objectif de cette thèse est de développer une nouvelle approche basée sur des algorithmes de planification de mouvement issus de la robotique pour mieux traiter la flexibilité moléculaire dans l'étude des interactions protéiques. Nous avons étendu un algorithme récent d'exploration par échantillonnage aléatoire, ML-RRT pour le désassemblage d'objets articulés complexes. Cet algorithme repose sur la décomposition des paramètres de configuration en deux sous-ensembles actifs et passifs, qui sont traités de manière découplée. Les extensions proposées permettent de considérer plusieurs degrés de mobilité pour la partie passive, qui peut Æetre poussée ou attirée par la partie active. Cet outil algorithmique a été appliqué avec succès pour l'étude des changements conformationnels de protéines induits lors de la diffusion d'un ligand. A partir de cette extension, nous avons développé une nouvelle méthode pour la résolution simultanée du séquenc¸age et des mouvements de désassemblage entre plusieurs objets. La méthode, nommée Iterative- ML-RRT, calcule non seulement les trajectoires permettant d'extraire toutes les pièces d'un objet complexe assemblé, mais également l'ordre permettant le désassemblage. L'approche est générale et a été appliquée pour l'étude du processus de dissociation de complexes macromoléculaires en introduisant une fonction d'évaluation basée sur l'énergie d'interaction. Les résultats présentés dans cette thèse montrent non seulement l'efficacité mais aussi la généralité des algorithmes proposés.

Cette thèse a été réalisée en collaboration et cofinancement impliquant le LSI du CEA/LIST et le LBMC de l'IFSTTAR. L'objectif de thèse était d'étudier et de développer une méthode pour simuler les mouvements d'un mannequin virtuel (MV) dans un environnement encombré en s'appuyant sur des connaissances a priori. L'étude présente, dans un premier temps, des expériences de capture de mouvement (MoCap). Les données enregistrées ont été analysées afin de définir quelques principes sur les mouvements humains dans des environnements encombrés. Nous proposons ensuite un critère général d'équilibre et une marge de stabilité, sur la base d'un modèle simplifié du MV. Puis, nous présentons un framework hiérarchique pouvant générer et simuler des mouvements dynamiques du MV dans un environnement encombré en trois étapes : une trajectoire globale du centre de masse (CoM) est générée au niveau global afin d'assurer l'équilibre du MV durant son mouvement; puis au niveau local, les trajectoires des organes terminaux (OT, i.e. pieds, mains) et les postures sont générées localement sous des contraintes cinématiques et d'évitement de collisions; enfin au niveau de l'exécution, les trajectoires (CoM et OTs) et les postures sont utilisées comme références dans un contrôleur dynamique associé au MV. Enfin, ce framework est mis en œuvre dans un scenario d'entrée dans un véhicule pour évaluer ses performances et proposer des améliorations futures

Cette thèse présente une approche de modélisation inspirée par la robotique pour l'étude des changements conformationnels des protéines. Cette approche est basée sur une représentation mécanistique des protéines permettant l'application de méthodes efficaces provenant du domaine de la robotique. Elle fournit également une méthode appropriée pour le traitement " gros-grains " des protéines sans perte de détail au niveau atomique. L'approche présentée dans cette thèse est appliquée à deux types de problèmes de simulation moléculaire. Dans le premier, cette approche est utilisée pour améliorer l'échantillonnage de l'espace conformationnel des protéines. Plus précisément, cette approche de modélisation est utilisée pour implémenter des classes de mouvements pour l'échantillonnage, aussi bien connues que nouvelles, ainsi qu'une stratégie d'échantillonnage mixte, dans le contexte de la méthode de Monte Carlo. Les résultats des simulations effectuées sur des protéines ayant des topologies différentes montrent que cette stratégie améliore l'échantillonnage, sans toutefois nécessiter de ressources de calcul supplémentaires. Dans le deuxième type de problèmes abordés ici, l'approche de modélisation mécanistique est utilisée pour implémenter une méthode inspirée par la robotique et appliquée à la simulation de mouvements de grande amplitude dans les protéines. Cette méthode est basée sur la combinaison de l'algorithme RRT (Rapidly-exploring Random Tree) avec l'analyse en modes normaux, qui permet une exploration efficace des espaces de dimension élevée tels les espaces conformationnels des protéines. Les résultats de simulations effectuées sur un ensemble de protéines montrent l'efficacité de la méthode proposée pour l'étude des transitions conformationnelles.