Planning Algorithms

by Steven M. LaValle

• ISBN13: 9780521862059
• ISBN10: 0521862051
• eBook ISBN(s): 9780511239342
• Format: Hardcover
• Copyright: 2006-05-29
• Publisher: Cambridge University Press
• More Book Details

Summary

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.

Author Biography

Steven M. Lavalle is Associate Professor of Computer Science at the University of Illinois at Urbana-Champaign

Table of Contents

Preface	xi
I Introductory Material	1	(62)
Introduction	3	(20)
Planning to plan	3	(1)
Motivational examples and applications	4	(10)
Basic ingredients of planning	14	(2)
Algorithms, planners, and plans	16	(4)
Organization of the book	20	(3)
Discrete Planning	23	(40)
Introduction to discrete feasible planning	24	(3)
Searching for feasible plans	27	(9)
Discrete optimal planning	36	(12)
Using logic to formulate discrete planning	48	(5)
Logic-based planning methods	53	(10)
II Motion Planning	63	(294)
Geometric Representations and Transformations	66	(39)
Geometric modeling	66	(10)
Rigid-body transformations	76	(7)
Transforming kinematic chains of bodies	83	(10)
Transforming kinematic trees	93	(6)
Nonrigid transformations	99	(6)
The Configuration Space	105	(48)
Basic topological concepts	105	(15)
Defining the configuration space	120	(9)
Configuration space obstacles	129	(10)
Closed kinematic chains	139	(14)
Sampling-Based Motion Planning	153	(53)
Distance and volume in C-space	154	(7)
Sampling theory	161	(12)
Collision detection	173	(7)
Incremental sampling and searching	180	(9)
Rapidly exploring dense trees	189	(7)
Roadmap methods for multiple queries	196	(10)
Combinatorial Motion Planning	206	(51)
Introduction	206	(2)
Polygonal obstacle regions	208	(10)
Cell decompositions	218	(14)
Computational algebraic geometry	232	(15)
Complexity of motion planning	247	(10)
Extensions of Basic Motion Planning	257	(47)
Time-varying problems	257	(6)
Multiple robots	263	(7)
Mixing discrete and continuous spaces	270	(9)
Planning for closed kinematic chains	279	(8)
Folding problems in robotics and biology	287	(5)
Coverage planning	292	(3)
Optimal motion planning	295	(9)
Feedback Motion Planning	304	(53)
Motivation	304	(2)
Discrete state spaces	306	(8)
Vector fields and integral curves	314	(14)
Complete methods for continuous spaces	328	(12)
Sampling-based methods for continuous spaces	340	(17)
III Decision-Theoretic Planning	357	(230)
Basic Decision Theory	360	(48)
Preliminary concepts	361	(7)
A game against nature	368	(10)
Two-player zero-sum games	378	(8)
Nonzero-sum games	386	(7)
Decision theory under scrutiny	393	(15)
Sequential Decision Theory	408	(54)
Introducing sequential games against nature	408	(11)
Algorithms for computing feedback plans	419	(11)
Infinite-horizon problems	430	(5)
Reinforcement learning	435	(7)
Sequential game theory	442	(13)
Continuous state spaces	455	(7)
Sensors and Information Spaces	462	(60)
Discrete state spaces	463	(9)
Derived information spaces	472	(8)
Examples for discrete state spaces	480	(7)
Continuous state spaces	487	(7)
Examples for continuous state spaces	494	(13)
Computing probabilistic information states	507	(5)
Information spaces in game theory	512	(10)
Planning Under Sensing Uncertainty	522	(65)
General methods	523	(5)
Localization	528	(12)
Environment uncertainty and mapping	540	(24)
Visibility-based pursuit-evasion	564	(6)
Manipulation planning with sensing uncertainty	570	(17)
IV Planning Under Differential Constraints	587	(180)
Differential Models	590	(61)
Velocity constraints on the configuration space	590	(16)
Phase space representation of dynamical systems	606	(9)
Basic Newton-Euler mechanics	615	(15)
Advanced mechanics concepts	630	(15)
Multiple decision makers	645	(6)
Sampling-Based Planning Under Differential Constraints	651	(61)
Introduction	652	(8)
Reachability and completeness	660	(10)
Sampling-based motion planning revisited	670	(8)
Incremental sampling and searching methods	678	(15)
Feedback planning under differential constraints	693	(3)
Decoupled planning approaches	696	(11)
Gradient-based trajectory optimization	707	(5)
System Theory and Analytical Techniques	712	(55)
Basic system properties	712	(8)
Continuous-time dynamic programming	720	(8)
Optimal paths for some wheeled vehicles	728	(8)
Nonholonomic system theory	736	(17)
Steering methods for nonholonomic systems	753	(14)
Bibliography	767	(44)
Index	811