Robot Motion Planning and Control.pdf

发布时间：2022-05-31 发布人：admin 分类：说明书资料大小：3.57M 资料格式：pdf 举报版权申诉

lizhensheng1993-10763454-4744302543454737651.pdf-第1页.png

第1页 / 共355页

lizhensheng1993-10763454-4744302543454737651.pdf-第2页.png

第2页 / 共355页

lizhensheng1993-10763454-4744302543454737651.pdf-第3页.png

第3页 / 共355页

lizhensheng1993-10763454-4744302543454737651.pdf-第4页.png

第4页 / 共355页

lizhensheng1993-10763454-4744302543454737651.pdf-第5页.png

第5页 / 共355页

lizhensheng1993-10763454-4744302543454737651.pdf-第6页.png

第6页 / 共355页

lizhensheng1993-10763454-4744302543454737651.pdf-第7页.png

第7页 / 共355页

lizhensheng1993-10763454-4744302543454737651.pdf-第8页.png

第8页 / 共355页

book

Foreword

List of Contributors

Table of Contents

chap1

Foreword

Table of Contents

Introduction

Controllabilities of mobile robots

Controllabilities

Mobile robots: from dynamics to kinematics

Kinematic model of mobile robots with trailers

Admissible paths and trajectories

Path planning and small-time controllability

Steering methods

From vector fields to effective paths

Nilpotent systems and nilpotentization

Steering chained form systems

Steering flat systems

Steering with optimal control

Nonholonomic path planning for small-time controllable systems

Toward steering methods accounting for small-time controllability

Steering methods and topological property

Approximating holonomic paths: a two step approach

Probabilistic approaches

An approach using optimization techniques

A multi-level approach

On the computational complexity of nonholonomic path planning

Other approaches, other systems

Conclusions

chap2

Foreword

Table of contents

Symmetric control systems: an introduction

Control systems and motion planning

Definitions. Basic problems

The control distance

Accessibility. The theorems of Chow and Sussmann

The shape of the accessible set in time

Regular and singular points

Distance estimates and privileged coordinates

Ball-Box Theorem

Application to complexity of nonholonomic motion planning

The car with n trailers

Introduction

Equations and notations

Examples: the car with 1 and 2 trailers

Controllability

Regular points

Bound for the degree of nonholonomy

Form of the singular locus

Polynomial systems

Introduction

Contact between an integral curve and an algebraic variety in dimension 2

The case of dimension n

Bound for the degree of nonholonomy in the plane

The general case

chap3

Foreword

Table of contents

Introduction

Models and optimization problems

Dubins' and Reeds-Shepp's car

Dubins' car with inertial angular velocity

The robot HILARE

Some results from Optimal Control Theory

Definitions

Existence of optimal paths

Necessary conditions: Pontryagin's Maximum Principle

Boltyanskii's sufficient conditions

Shortest paths for the Reeds-Shepp car

The pioneer works by Dubins and Reeds and Shepp

Characterization of a sufficient family: A local approach

A geometric approach: construction of a synthesis of optimal paths

An example of regular synthesis

Shortest paths for Dubins' Car

Symmetry and reduction properties

Construction of domains

Construction of the partition

Description of the partition

Related works

Dubins model with inertial control law

Existence of an optimal solution

Necessary conditions for a solution to be optimal

Conclusion

Related works

Time-optimal trajectories for Hilare-like mobile robots

Conclusions

chap4

Foreword

Table of contents

Introduction

Problem classification

Control issues

Open-loop vs. closed-loop control

Organization of contents

Modeling and analysis of the car-like robot

Kinematic modeling

Controllability analysis

Chained forms

Trajectory tracking

Reference trajectory generation

Control via approximate linearization

Control via exact feedback linearization

Path following and point stabilization

Control via smooth time-varying feedback

Control via nonsmooth time-varying feedback

About exponential convergence

Conclusions

Further reading

chap5

Foreword

Table of contents

Introduction

The Probabilistic Path Planner

The roadmap construction phase

The query phase

Using a directed graph

Smoothing the paths

Application to holonomic robots

Filling in the details

Simulation results

Application to nonholonomic robots

Some previous work on nonholonomic motion planning

Description of the car-like and tractor-trailer robots

Application to general car-like robots

Application to forward car-like robots

Application to tractor-trailer robots

On probabilistic completeness of probabilistic path planning

The general local topology property

Probabilistic completeness with the used local planners

On the expected complexity of probabilistic path planning

The visibility volume assumption

The path clearance assumption

The -complexity assumption

A multi-robot extension

Discretisation of the multi-robot planning problem

The super-graph approach

Retrieving the coordinated paths

Application to car-like robots

Discussion of the super-graph approach

Conclusions

chap6

Foreword

Table of contents

Introduction

Interference detection

Focusing on relevant regions

Basic interference tests

Collision detection

Four main approaches

Strategies for space and time bounding

Collision detection in motion planning

Global planners

Incremental planners

Local planners

Conclusions

Jean-Paul Laumond (Editor) Robot Motion Planning and Control Laboratoire d’Analye et d’Architecture des Systemes Centre National de la Recherche Scientique LAAS report 97438 Previoulsy published as: Lectures Notes in Control and Information Sciences 229. Springer, ISBN 3-540-76219-1, 1998, 343p.

Foreword How can a robot decide what motions to perform in order to achieve tasks in the physical world ? The existing industrial robot programming systems still have very limited motion planning capabilities. Moreover the eld of robotics is growing: space exploration, undersea work, intervention in hazardous environments, servicing robotics : : : Motion planning appears as one of the components for the neces- sary autonomy of the robots in such real contexts. It is also a fundamental issue in robot simulation software to help work cell designers to determine collision free paths for robots performing specic tasks. Robot Motion Planning and Control requires interdisciplinarity The research in robot motion planning can be traced back to the late 60’s, during the early stages of the development of computer-controlled robots. Nev- ertheless, most of the eort is more recent and has been conducted during the 80’s (Robot Motion Planning, J.C. Latombe’s book constitutes the reference in the domain). The position (conguration) of a robot is normally described by a number of variables. For mobile robots these typically are the position and orientation of the robot (i.e. 3 variables in the plane). For articulated robots (robot arms) these variables are the positions of the dierent joints of the robot arm. A motion for a robot can, hence, be considered as a path in the conguration space. Such a path should remain in the subspace of congurations in which there is no collision between the robot and the obstacles, the so-called free space. The motion planning problem asks for determining such a path through the free space in an ecient way. Motion planning can be split into two classes. When all degrees of freedom can be changed independently (like in a fully actuated arm) we talk about holonomic motion planning. In this case, the existence of a collision-free path is characterized by the existence of a connected component in the free cong- uration space. In this context, motion planning consists in building the free conguration space, and in nding a path in its connected components. Within the 80’s, Roboticians addressed the problem by devising a variety of heuristics and approximate methods. Such methods decompose the cong- uration space into simple cells lying inside, partially inside or outside the free space. A collision-free path is then searched by exploring the adjacency graph of free cells.

VI In the early 80’s, pioneering works showed how to describe the free cong- uration space by algebraic equalities and inequalities with integer coecients (i.e. as being a semi-algebraic set). Due to the properties of the semi-algebraic sets induced by the Tarski-Seidenberg Theorem, the connectivity of the free conguration space can be described in a combinatorial way. From there, the road towards methods based on Real Algebraic Geometry was open. At the same time, Computational Geometry has been concerned with combinatorial bounds and complexity issues. It provided various exact and ecient meth- ods for specic robot systems, taking into account practical constraints (like environment changes). More recently, with the 90’s, a new instance of the motion planning problem has been considered: planning motions in the presence of kinematic constraints (and always amidst obstacles). When the degrees of freedom of a robot sys- tem are not independent (like e.g. a car that cannot rotate around its axis without also changing its position) we talk about nonholonomic motion plan- ning. In this case, any path in the free conguration space does not necessarily correspond to a feasible one. Nonholonomic motion planning turns out to be much more dicult than holonomic motion planning. This is a fundamental issue for most types of mobile robots. This issue attracted the interest of an increasing number of research groups. The rst results have pointed out the necessity of introducing a Dierential Geometric Control Theory framework in nonholonomic motion planning. On the other hand, at the motion execution level, nonholonomy raises an- other diculty: the existence of stabilizing smooth feedback is no more guaran- teed for nonholonomic systems. Tracking of a given reference trajectory com- puted at the planning level and reaching a goal with accuracy require non- standard feedback techniques. Four main disciplines are then involved in motion planning and control. However they have been developed along quite dierent directions with only little interaction. The coherence and the originality that make motion plan- ning and control a so exciting research area come from its interdisciplinarity. It is necessary to take advantage from a common knowledge of the dierent theoretical issues in order to extend the state of the art in the domain. About the book The purpose of this book is not to present a current state of the art in motion planning and control. We have chosen to emphasize on recent issues which have been developed within the 90’s. In this sense, it completes Latombe’s book published in 1991. Moreover an objective of this book is to illustrate the necessary interdisciplinarity of the domain: the authors come from Robotics,

VII Computational Geometry, Control Theory and Mathematics. All of them share a common understanding of the robotic problem. The chapters cover recent and fruitful results in motion planning and con- trol. Four of them deal with nonholonomic systems; another one is dedicated to probabilistic algorithms; the last one addresses collision detection, a critical operation in algorithmic motion planning. Nonholonomic Systems The research devoted to nonholonomic systems is mo- tivated mainly by mobile robotics. The rst chapter of the book is dedicated to nonholonomic path planning. It shows how to combine geometric algorithms and control techniques to account for the nonholonomic constraints of most mobile robots. The second chapter develops the mathematical machinery nec- essary to the understanding of the nonholonomic system geometry; it puts emphasis on the nonholonomic metrics and their interest in evaluating the combinatorial complexity of nonholonomic motion planning. In the third chap- ter, optimal control techniques are applied to compute the optimal paths for car-like robots; it shows that a clever combination of the maximum principle and a geometric viewpoint has permitted to solve a very dicult problem. The fourth chapter highlights the interactions between feedback control and motion planning primitives; it presents innovative types of feedback controllers facing nonholonomy. Probabilistic Approaches While complete and deterministic algorithms for mo- tion planning are very time-consuming as the dimension of the conguration space increases, it is now possible to address complicated problems in high di- mension thanks to alternative methods that relax the completeness constraint for the benet of practical eciency and probabilistic completeness. The fth chapter of the book is devoted to probabilistic algorithms. Collision Detection Collision checkers constitute the main bottleneck to con- ceive ecient motion planners. Static interference detection and collision detec- tion can be viewed as instances of the same problem, where objects are tested for interference at a particular position, and along a trajectory. Chapter six presents recent algorithms beneting from this unied viewpoint. The chapters are self-contained. Nevertheless, many results just mentioned in some given chapter may be developed in another one. This choice leads to repetitions but facilitates the reading according to the interest or the back- ground of the reader.

VIII On the origin of the book All the authors of the book have been involved in PROMotion. PROMotion was a European Project dedicated to robot motion planning and control. It has progressed from September 1992 to August 1995 in the framework of the Basic Research Action of ESPRIT 3, a program of research and development in In- formation Technologies supported by the European Commission (DG III). The work undertaken under the project has been aimed at solving concrete prob- lems. Theoretical studies have been mainly motivated by a practical eciency. Research in PROMotion has then provided methods and their prototype im- plementations which have the potential of becoming key components of recent programs in advanced robotics. In few numbers, PROMotion is a project whose cost has been 1.9 MEcus1 (1.1 MEcus supported by European Community), for a total eort of more than 70 men-year, 179 research reports (most them have been published in international conferences and journals), 10 experiments on real robot platforms, an International Spring school and 3 International Workshops. This project has been managed by LAAS{CNRS in Toulouse; it has involved the \Universitat Politecnica de Catalunya" in Barcelona, the \Ecole Normale Superieure" in Paris, the University \La Sapienza" in Roma, the Institute INRIA in Sophia- Antipolis and the University of Utrecht. J.D. Boissonnat (INRIA, Sophia-Antipolis), A. De Luca (University \La Sapienza" of Roma), M. Overmars (Utrecht University), J.J. Risler (Ecole Nor- male Superieure and Paris 6 University), C. Torras (Universitat Politecnica de Catalunya, Barcelona) and the author make up the steering committee of PRO- Motion. This book benets from contributions of all these members and their co-authors and of the work of many people involved in the project. On behalf of the project committee, I thank J. Wejchert (Project ocier of PROMotion for the European Community), A. Blake (Oxford University), H. Chochon (Alcatel) and F. Wahl (Braunschweig University) who acted as reviewers of the project during three years. Finally I thank J. Som for her ecient help in managing the project and M. Herrb for his help in editing this book. Jean-Paul Laumond LAAS-CNRS, Toulouse August 1997 1 US $ 1 1 Ecu

List of Contributors A. Bella¨che Departement de Mathematiques Universite de Paris 7 2 Place Jussieu 75251 Paris Cedex 5 France abellaic@mathp7.jussieu.fr J.D. Boissonnat INRIA Centre de Sophia Antipolis 2004, Route des Lucioles BP 93 06902 Sophia Antipolis Cedex, France boissonn@sophia.inria.fr A. De Luca Dipartimento di Informatica e Sistemistica Universita di Roma \La Sapienza" Via Eudossiana 18 00184 Roma Italy adeluca@giannutri.caspur.it F. Jean Institut de Mathematiques Universite Pierre et Marie Curie Tour 46, 5eme etage, Boite 247 4 Place Jussieu 75252 Paris Cedex 5 France jean@math.jussieu.fr P. Jimenez Institut de Robotica i Informatica Industrial Gran Capita, 2 08034-Barcelona Spain jimenez@iri.upc.es J.P. Laumond LAAS-CNRS 7 Avenue du Colonel Roche 31077 Toulouse Cedex 4 France jpl@laas.fr F. Lamiraux LAAS-CNRS 7 Avenue du Colonel Roche 31077 Toulouse Cedex 4 France lamiraux@laas.fr G. Oriolo Dipartimento di Informatica e Sistemistica Universita di Roma \La Sapienza" Via Eudossiana 18 00184 Roma Italy oriolo@giannutri.caspur.it

X M. H. Overmars Department of Computer Science, Utrecht University P.O.Box 80.089, 3508 TB Utrecht, the Netherlands markov@cs.ruu.nl J.J. Risler Institut de Mathematiques Universite Pierre et Marie Curie Tour 46, 5eme etage, Boite 247 4 Place Jussieu 75252 Paris Cedex 5 France risler@math.jussieu.fr C. Samson INRIA Centre de Sophia Antipolis 2004, Route des Lucioles BP 93 06902 Sophia Antipolis Cedex, France Claude.Samson@sophia.inria.fr S. Sekhavat LAAS-CNRS 7 Avenue du Colonel Roche 31077 Toulouse Cedex 4 France sepanta@laas.fr P. Soueres LAAS-CNRS 7 Avenue du Colonel Roche 31077 Toulouse Cedex 4 France soueres@laas.fr F. Thomas Institut de Robotica i Informatica Industrial Gran Capita, 2 08034-Barcelona Spain thomas@iri.upc.es P. Svestka Department of Computer Science, Utrecht University P.O.Box 80.089, 3508 TB Utrecht, the Netherlands petr@cs.ruu.nl C. Torras Institut de Robotica i Informatica Industrial Gran Capita, 2 08034-Barcelona Spain torras@iri.upc.es

分享到：

赞收藏

资料库

Robot Motion Planning and Control.pdf

相关推荐

人工智能

热门标签

最新资料