By Steven M. LaValle, Copyright 2006
   Cambridge University Press, 842 pages
   To buy: Cambridge   Amazon

   Cover art by James Kuffner
   Art on the first page of each part by Odri

   The whole book in HTML
   Courses that use the book
   BibTeX file for all 1005 references (edited by J. O'Kane)
   Errata (First Printing)

This book presents a unified treatment of many different kinds of planning algorithms. The subject lies at the crossroads between robotics, control theory, artificial intelligence, algorithms, and computer graphics. The particular subjects covered include motion planning, discrete planning, planning under uncertainty, sensor-based planning, visibility, decision-theoretic planning, game theory, information spaces, reinforcement learning, nonlinear systems, trajectory planning, nonholonomic planning, and kinodynamic planning.

Download the whole book

[pdf file] -- Two pages per one. Recommended for printing on US Letter paper.
[pdf file] -- Two pages per one. Recommended for printing on A4 paper
[pdf file] -- One page per one (larger print). May be easier for on-line viewing.
[epub file] -- An ePub version for e-readers (thanks to Aris Synodinos)

These files were uploaded on Fri Apr 20 16:07:06 CDT 2012

Download individual parts and chapters

In these files, only the references that are cited in that chapter are included (unfortunately, they are renumbered). The page numbers, however, should match the complete book copies.

Chapter 1: Introduction
Motivation, examples, applications, high-level planning concepts, overview of the book.
Chapter 2: Discrete Planning
Feasible planning, optimal planning, search algorithms, A*, Dijkstra's algorithm, forward search, backward search, bidirectional search, value iteration, logic-based planning, STRIPS, plan graph, planning as satisfiability.
Chapter 3: Geometric Representations and Transformations
Polygonal, polyhedral, and semi-algebraic models. Rigid-body transformations, 3D rotations, kinematic chains, Denavit-Hartenberg parameters, kinematic trees, nonrigid transformations.
Chapter 4: The Configuration Space
Topological spaces, manifolds, paths. The C-space of rigid bodies, chains of bodies, and trees of bodies. Configuration space. Quaternions. C-space obstacles, closed kinematic chains, algebraic varieties.
Chapter 5: Sampling-Based Motion Planning
Metric spaces, measure, random sampling, low-discrepancy sampling, low-dispersion sampling, grids, lattices, collision detection, Rapidly-exploring Random Trees (RRTs), Probabilistic Roadmaps (PRMs), randomized potential fields.
Chapter 6: Combinatorial Motion Planning
Vertical cell decomposition, shortest-path roadmaps, maximum-clearance roadmaps, cylindrical algebraic decomposition, Canny's algorithm, complexity bounds, Davenport-Schinzel sequences.
Chapter 7: Extensions of Basic Motion Planning
Time varying problems, velocity tuning, multiple-robot coordination, hybrid systems, manipulation planning, protein folding, unknotting, closed chains, Random Loop Generator (RLG), coverage planning, optimal motion planning.
Chapter 8: Feedback Motion Planning
Navigation functions, smooth manifolds, vector fields, numerical potential functions, optimal navigation functions, compositions of funnels, dynamic programming on continuous spaces.
Chapter 9: Basic Decision Theory
Optimization and probability review, games against nature, Bayesian classification, zero-sum games, nonzero-sum games, Nash equilibria, utility theory, criticisms of decision theory.
Chapter 10: Sequential Decision Theory
Sequential games against nature, value iteration, policy iteration, infinite-horizon planning, discounted cost, average cost, reinforcement learning, sequential games.
Chapter 11: Sensors and Information Spaces
Information spaces and information mappings, sensing uncertainty, discrete and continuous sensors, POMDPs, Kalman filtering, particle filtering, information spaces in games.
Chapter 12: Planning Under Sensing Uncertainty
Value iteration for planning under sensing uncertainty. Robot localization, mapping, navigation, searching, visibility-based pursuit-evasion, manipulation with sensing uncertainty.
Chapter 13: Differential Models
Kinematic constraints, Dubins car, Reeds-Shepp car, differential drives, a car pulling trailers, phase space, rigid-body dynamics, dynamics of a chain of bodies, Newtonian mechanics, Euler-Lagrange equation, variational principles, Hamilton's equations, differential games.
Chapter 14: Sampling-Based Planning Under Differential Constraints
Phase-space obstacles, nonholonomic planning, kinodynamic planning, trajectory planning, reachability analysis, motion primitives, sampling-based planning, Barraquand-Latombe nonholonomic planner, RRTs, feedback planning, plan-and-transform method, path-constrained trajectory planning, gradient-based trajectory optimization.
Chapter 15: System Theory and Analytical Techniques
System properties, stability, Lyapunov functions, controllability, STLC, Hamilton-Jacobi-Bellman equation, Pontryagin's maximum principle, Dubins curves, Reeds-Shepp curves, Balkcom-Mason curves, affine control systems, distributions, Frobenius theorem, Chow-Rashevskii theorem, Lie brackets, control Lie algebra, P. Hall basis, steering with piecewise constant inputs, steering with sinusoids.