170 Pages
English

# Laboratoire d'Analyse et d'Architecture des Systemes

-

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

Subjects

##### Lavalle

Informations

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
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
maintenance operations [Simeon 01c] or the transport of large objects [Lamiraux 03]. In
medical applications, nding a minimally-invasive path of a surgical tool, given a 3D model
of the patient’s body, can also be seen as a motion planning problem [Tombropoulos 99].
There is a clear resemblance between the structural representation of robots an molecules
[Parsons 94, Kavraki 97]. Motion planing strategies can be used to solve complex
problems in computational Chemistry and Biology [Finn 98, LaValle 00, Apaydin 02]. With
slight variations, the formulation of the motion planning problem can be enlarged to more
complex problems such as manipulation planning [Alami 95, Simeon 03] and kinodymamic
planning [Donald 93, Fraichard 99, LaValle 01b]. Then, extensions of motion planners can
be studied to solve them.
The motion planning problem was rst formulated for a single rigid objects whose
only motion constraints arise from the presence of static obstacles. It is usually referred
to as the piano mover’s problem [Schwartz 83, Schwartz 84]. Solving this basic instance
is already a challenging task which has attracted the interest of many scientists over
the last two decades. The development of motion planning algorithms began with this
particular case, and some planners have been proposed that provide an exact solution (e.g.
[Canny 88]). Nevertheless, most of the above mentioned practical applications require
to deal with much more complex instances of the problem that such exact methods are
unable to treat. The di culty of motion planning depends on the complexity of the mobile
system and on the intrinsic and extrinsic motion constraints. Practical motion planning
algorithms, able to handle such di culties, have been developed in the last ten years
(e.g. [Kavraki 96, LaValle 98]). These planners use sampling techniques combined with
e cient geometric tools to construct data structures that encode the connectivity of the
feasible subsets in the search-space. The e cacy and generality of sampling-based motion
planning algorithms have been demonstrated by the several research groups working on2 Introduction
Figure 1: A \robotized" version of the piano mover’s problem. The situation
of the piano in the room is changed by cooperating mobile manipulators.