Planning Algorithms (Google eBook)

Front Cover
Cambridge University Press, May 29, 2006 - Computers
1 Review
Planning algorithms are impacting technical disciplines and industries around the world, including robotics, computer-aided design, manufacturing, computer graphics, aerospace applications, drug design, and protein folding. This coherent and comprehensive book unifies material from several sources, including robotics, control theory, artificial intelligence, and algorithms. The treatment is centered on robot motion planning, but integrates material on planning in discrete spaces. A major part of the book is devoted to planning under uncertainty, including decision theory, Markov decision processes, and information spaces, which are the 'configuration spaces' of all sensor-based planning problems. The last part of the book delves into planning under differential constraints that arise when automating the motions of virtually any mechanical system. This text and reference is intended for students, engineers, and researchers in robotics, artificial intelligence, and control theory as well as computer graphics, algorithms, and computational biology.
  

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

91 Preliminary concepts
361
92 A game against nature
368
93 Twoplayer zerosum games
378
94 Nonzerosum games
386
95 Decision theory under scrutiny
393
Sequential Decision Theory
408
102 Algorithms for computing feedback plans
419
103 Infinitehorizon problems
430

23 Discrete optimal planning
36
24 Using logic to formulate discrete planning
48
25 Logicbased planning methods
53
Motion Planning
63
Geometric Representations and Transformations
66
32 Rigidbody transformations
76
33 Transforming kinematic chains of bodies
83
34 Transforming kinematic trees
93
35 Nonrigid transformations
99
The Configuration Space
105
42 Defining the configuration space
120
43 Configuration space obstacles
129
44 Closed kinematic chains
139
SamplingBased Motion Planning
153
51 Distance and volume in Cspace
154
52 Sampling theory
161
53 Collision detection
173
54 Incremental sampling and searching
180
55 Rapidly exploring dense trees
189
56 Roadmap methods for multiple queries
196
Combinatorial Motion Planning
206
62 Polygonal obstacle regions
208
63 Cell decompositions
218
64 Computational algebraic geometry
232
65 Complexity of motion planning
247
Extensions of Basic Motion Planning
257
72 Multiple robots
263
73 Mixing discrete and continuous spaces
270
74 Planning for closed kinematic chains
279
75 Folding problems in robotics and biology
287
76 Coverage planning
292
77 Optimal motion planning
295
Feedback Motion Planning
304
82 Discrete state spaces
306
83 Vector fields and integral curves
314
84 Complete methods for continuous spaces
328
85 Samplingbased methods for continuous spaces
340
DecisionTheoretic Planning
357
Basic Decision Theory
360
104 Reinforcement learning
435
105 Sequential game theory
442
106 Continuous state spaces
455
Sensors and Information Spaces
462
111 Discrete state spaces
463
112 Derived information spaces
472
113 Examples for discrete state spaces
480
114 Continuous state spaces
487
115 Examples for continuous state spaces
494
116 Computing probabilistic information states
507
117 Information spaces in game theory
512
Planning Under Sensing Uncertainty
522
121 General methods
523
122 Localization
528
123 Environment uncertainty and mapping
540
124 Visibilitybased pursuitevasion
564
125 Manipulation planning with sensing uncertainty
570
Planning Under Differential Constraints
587
Differential Models
590
132 Phase space representation of dynamical systems
606
133 Basic NewtonEuler mechanics
615
134 Advanced mechanics concepts
630
135 Multiple decision makers
645
SamplingBased Planning Under Differential Constraints
651
141 Introduction
652
142 Reachability and completeness
660
143 Samplingbased motion planning revisited
670
144 Incremental sampling and searching methods
678
145 Feedback planning under differential constraints
693
146 Decoupled planning approaches
696
147 Gradientbased trajectory optimization
707
System Theory and Analytical Techniques
712
152 Continuoustime dynamic programming
720
153 Optimal paths for some wheeled vehicles
728
154 Nonholonomic system theory
736
155 Steering methods for nonholonomic systems
753
Bibliography
767
Index
811
Copyright

Common terms and phrases

Popular passages

Page 789 - K. Kant and SW Zucker. Toward efficient trajectory planning: The path-velocity decomposition.

References to this book

All Book Search results »

About the author (2006)

Steven M. LaValle is Associate Professor of Computer Science at the University of Illinois at Urbana-Champaign. He has worked in motion planning and robotics for over a decade and is a leading researcher who has published dozens of articles in the field. He is the main developer of the Rapidly-exploring Random Tree (RRT) algorithm, which has been used in numerous research labs and industrial products around the world. He has taught material on which the book is based at Stanford University, Iowa State University, the Tec de Monterrey, and the University of Illinois.

Bibliographic information