Planning Algorithms - Steven M. Lavalle - Cambridge _ Cambridge University Press, 2006. - 2006.pdf

i
ii
PLANNING ALGORITHMS
Steven M. LaValle
University of Illinois
Copyright Steven M. LaValle 2006
Available for downloading at /
Published by Cambridge University Press
iii
For my wife, Tammy, and my sons, Alexander and Ethan
iv
Contents
Preface ix
I Introductory Material 1
1 Introduction 3
Planning to Plan . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
Motivational Examples and Applications . . . . . . . . . . . . . . . 5
Basic Ingredients of Planning . . . . . . . . . . . . . . . . . . . . . 17
Algorithms, Planners, and Plans . . . . . . . . . . . . . . . . . . . . 19
of the Book . . . . . . . . . . . . . . . . . . . . . . . . 24
2 Discrete Planning 27
Introduction to Discrete Feasible Planning . . . . . . . . . . . . . . 28
Searching for Feasible Plans . . . . . . . . . . . . . . . . . . . . . . 32
Discrete Optimal Planning . . . . . . . . . . . . . . . . . . . . . . . 43
Using Logic to Formulate Discrete Planning . . . . . . . . . . . . . 57
Logic-Based Planning Methods . . . . . . . . . . . . . . . . . . . . 63
II Motion Planning 77
3 Geometric Representations and Transformations 81
Geometric Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . 81
Rigid-Body Transformations . . . . . . . . . . . . . . . . . . . . . . 92
Transforming Kinematic Chains of Bodies . . . . . . . . . . . . . . 100
Transforming Kinematic Trees . . . . . . . . . . . . . . . . . . . . . 112
Nonrigid Transformations . . . . . . . . . . . . . . . . . . . . . . . 120
4 The Configuration Space 127
Basic Topological Concepts . . . . . . . . . . . . . . . . . . . . . . 127
Defining the Configuration Space . . . . . . . . . . . . . . . . . . . 145
Configuration Space Obstacles . . . . . . . . . . . . . . . . . . . . . 155
Closed Kinematic Chains . . . . . . . . . . . . . . . . . . . . . . . . 167
v
vi CONT