Laboratoire d'Analyse et d'Architecture des Systemes

Juan Cortes

Description

Niveau: Supérieur, Doctorat, Bac+8
These presentee au Laboratoire d'Analyse et d'Architecture des Systemes en vue de l'obtention du Doctorat de l'Institut National Polytechnique de Toulouse Ecole Doctorale Systemes Specialite : Systemes Automatiques / Robotique par Juan Cortes Algorithmes pour la Planification de Mouvements de Mecanismes Articules avec Chaınes Cinematiques Fermees Motion Planning Algorithms for General Closed-Chain Mechanisms Soutenue le 16 December 2003 devant le Jury compose de : Lydia E. Kavraki Rice University, Houston Rapporteurs Steven M. LaValle University of Illinois, Urbana Raja Chatila LAAS-CNRS, Toulouse Examinateurs Jean-Paul Laumond LAAS-CNRS, Toulouse Jean-Pierre Merlet INRIA, Sophia Antipolis Pierre Monsan INSA, Toulouse Membre invite Thierry Simeon LAAS-CNRS, Toulouse Directeur de these

• algorithmes pour la planification de mouvements de mecanismes articules avec chaınes cinematiques


• architecture des systemes


• magalie remaud-simeon

Sujets

• Antipolis
• Renaud
• Siméon
• Thomas
• Lavalle

Informations

• Publié par: profil-zyak-2012
• Nombre de lectures: 35
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

These
presentee au
Laboratoire d’Analyse et d’Architecture des Systemes
en vue de l’obtention du
Doctorat de l’Institut National Polytechnique de Toulouse
Ecole Doctorale Systemes
Specialite : Systemes Automatiques / Robotique
par Juan Cortes
Algorithmes pour la Planification de Mouvements de
^ Mecanismes Articules avec Cha nes Cin ematiques Fermees
Motion Planning Algorithms for
General Closed-Chain Mechanisms
Soutenue le 16 December 2003
devant le Jury compose de :
Lydia E. Kavraki Rice University, Houston Rapporteurs
Steven M. LaValle University of Illinois, Urbana
Raja Chatila LAAS-CNRS, Toulouse Examinateurs
Jean-Paul Laumond T
Jean-Pierre Merlet INRIA, Sophia Antipolis
Pierre Monsan INSA, Toulouse Membre invite
Thierry Simeon LAAS-CNRS, Toulouse Directeur de theseOjal a que esta tesis pueda aportar
a la Ciencia al menos una pequena~
parte de lo que su realizaci on me ha
aportado a mi.
In memory of my grandmother Cristina.
thDead the 25 of June 2003.Acknowledgments
Three years. Three full years. Three years of experiences. Three years of learning. Three
years of contrasts: hope and despair, happiness and sadness, satisfaction and dislike,
harmony and discord. But, in the balance, three very positive years, during which I have
matured as a person, and, I hope, as a scientist. For this reason, I have to express my
sincere gratitude to the persons who made it possible and to all the people who have
helped me and have accompanied me during this period.
First of all, I have to thank to the main responsibles of this adventure. Thanks to
Thierry Simeon for being much more than an excellent advisor. Thanks to Jean-Paul
Laumond for being always there, ready to give a bit of geniality. I don’t want to forget to
Luis Montano, who made me meet them.
My gratitude to the directors of the LAAS-CNRS, Jean-Claude Laprie and Malik
Ghallab, and to the head of the group RIA, Raja Chatila, for the material support. And
thanks to people of group RIA and Sysadmin for their frequent helps.
I also thank Lydia Kavraki and Steven LaValle for the review of this thesis. Their
comments and suggestions have inestimable value for me.
A very special thanks to Llu s Ros and Angel Sappa. To see their passion for research
helped me decide to start a PhD. And also thanks to other people with whom I have
had the pleasure of collaborating or interacting, particularly: Gwenaelle Andre, Paul
Bates, Patrick Danes, Fabien Gravot, Didier Henrion, Leonard Jaillet, Jean-Pierre Merlet,
Magalie Remaud-Simeon, Marc Renaud, Vicente Ruiz, Anis Sahbani, Federico Thomas
and Vinh Tran.
Finally, I have to mention my family and friends, my main source of motivation.
Specially, thanks to Christophe for all the beautiful moments we have shared, and thanks
to Odri for the nice illustrations of this thesis, but above all, thanks for loving me.Contents
Introduction 1
I Theory & Techniques 7
1 Problem Formulation 9
1.1 Mechanical Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.1.1 Rigid Body Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.1.2 Articulated Mechanism . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2 Loop Closure Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
The Inverse Kinematics Problem . . . . . . . . . . . . . . . . . . . . 19
1.3 The Notion of Con guration-Space . . . . . . . . . . . . . . . . . . . . . . 19
The Variety of the Con gurations Satisfying Closure . . . . . . . . . 20
1.4 The Motion Planning Problem . . . . . . . . . . . . . . . . . . . . . . . . 23
1.4.1 under Holonomic Constraints . . . . . . . . . . . . 24
1.4.2 Motion Planning Di erentialts . . . . . . . . . . . . 26
2 Available Techniques 29
2.1 Motion Planning Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.1.1 Sampling-Based Approaches . . . . . . . . . . . . . . . . . . . . . . . 32
2.1.2 PRM and RRT Algorithms . . . . . . . . . . . . . . . . . . . . . . . 37
2.2 Solution Methods for Loop Closure Equations . . . . . . . . . . . . . . . . 42
2.2.1 Solutions for Non-Redundant Mechanisms . . . . . . . . . . . . . . . 43
2.2.2 Dealing with Redundancy . . . . . . . . . . . . . . . . . . . . . . . . 44
2.3 Motion Planning under Kinematic Closure Constraints . . . . . . . . . . . 45
2.3.1 Complete Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.3.2 Sampling-Based Approaches . . . . . . . . . . . . . . . . . . . . . . . 46
3 Sampling-Based Motion Planning for Closed-Chain Mechanisms 49
3.1 Overview of the Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.2 Con guration Sampling Under Closure Constraints . . . . . . . . . . . . . 58
3.2.1 Mechanical System Decomposition . . . . . . . . . . . . . . . . . . . 58
3.2.2 RLG Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.2.3 Approximated Closure Range . . . . . . . . . . . . . . . . . . . . . . 61
3.3 Extension of PRM-based Algorithms . . . . . . . . . . . . . . . . . . . . . 64
3.3.1 Generating Nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.3.2 Computing Local Paths . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.4 Extension of RRT-based Algorithms . . . . . . . . . . . . . . . . . . . . . 69
3.4.1 Tree Expansion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.4.2 Other Issues Under Analysis . . . . . . . . . . . . . . . . . . . . . . 71
3.5 Motion Planning Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 73
3.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77vi Contents
II Applications 79
4 Motion Planning for Parallel Mechanisms 81
4.1 Interest of the Application . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.1.1 Encoding the Workspace and Planning the Motions
of Parallel Manipulators . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.1.2 Solving Coordinated Manipulation Planning Problems . . . . . . . . 86
4.2 Description of Parallel Mechanisms . . . . . . . . . . . . . . . . . . . . . . 87
4.3 RLG Variant for Parallel Mec . . . . . . . . . . . . . . . . . . . . 88
4.3.1 Mechanism Decomposition - Choice of Parameters . . . . . . . . . . 89
4.3.2 RLG Parallel Algorithm . . . . . . . . . . . . . . . . . . . . . . . 89
4.3.3 Associations of Parallel Mechanism . . . . . . . . . . . . . . . . . . . 92
4.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.4.1 Parallel Manipulators . . . . . . . . . . . . . . . . . . . . . . . . . . 93
4.4.2 Coordinated Manipulation . . . . . . . . . . . . . . . . . . . . . . . . 95
4.5 Discussion and Prospects . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
5 Manipulation Planning 97
5.1 Historical Development . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
5.2 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
5.3 A General Approach to Manipulation Planning . . . . . . . . . . . . . . . 106
5.4 The Planning Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
5.5 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
5.6 Discussion and Prospects . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
6 Geometric Exploration of Molecular Motions 117
6.1 Interest in Protein Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
6.2 Molecular Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
6.2.1 Kinematics Inspired Model . . . . . . . . . . . . . . . . . . . . . . . 122
6.2.2 Van der Waals Model . . . . . . . . . . . . . . . . . . . . . . . . . . 124
6.3 Conformational Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
6.3.1 Backbone Conformation . . . . . . . . . . . . . . . . . . . . . . . . . 125
6.3.2 Side-Chain . . . . . . . . . . . . . . . . . . . . . . . . 128
6.4 Conformational Space Exploration . . . . . . . . . . . . . . . . . . . . . . 128
6.5 First Results: Loop 7 Motions of Amylosucrase from Neisseria Polysaccharea129
6.6 Discussion and Prospects . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
Conclusions 135
Bibliography 139Introduction
Motion Planning is a fundamental issue in Robotics. An intelligent machine must be
able to decide how to move in its environment. The motion planning problem consists
in nding feasible paths for a mobile system, the robot, in a physical world. The notion
of con guration-space [Lozano-Perez 83] allows a geometrical formulation of the problem
such that it is reduced to nd the connectivity of subsets of a n-dimensional manifold. A
detailed formulation of the problem and a collection of basic techniques can be found in
[Latombe 91]. This same formulation can be adopted for problems in other very di erent
domains [Latombe 99]. For instance, if virtual actors are modeled like robots, then motion
planning techniques become tools for graphic animation [Koga 95, Ku ner 99]. Questions
involving motion of objects often rise during the design of prototypes of products and their
manufacturing using CAD/CAM systems. Motion planners, as integral components of
these software packages, are capable to answer these questions [Gottschlich 92, Ferre 03].
In industrial logistics, motion planing algorithms have an application to assist di cult
ma