Planning Algorithms / Motion Planning

   By Steven M. LaValle, Copyright 2006
   Cambridge University Press, 842 pages
   To buy: Cambridge ($63) Amazon ($46.40)

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.

These files were uploaded on Fri Aug 14 09:05:02 EEST 2020

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.

PART I: INTRODUCTORY MATERIAL
[pdf]

Chapter 1: Introduction
[pdf] Motivation, examples, applications, high-level planning concepts, overview of the book.

Chapter 2: Discrete Planning
[pdf] 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.

PART II: MOTION PLANNING
[pdf]

Chapter 3: Geometric Representations and Transformations
[pdf] 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
[pdf] 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
[pdf] 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
[pdf] 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
[pdf] 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
[pdf] Navigation functions, smooth manifolds, vector fields, numerical potential functions, optimal navigation functions, compositions of funnels, dynamic programming on continuous spaces.

PART III: DECISION-THEORETIC PLANNING
[pdf]

Chapter 9: Basic Decision Theory
[pdf] 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
[pdf] 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
[pdf] 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
[pdf] Value iteration for planning under sensing uncertainty. Robot localization, mapping, navigation, searching, visibility-based pursuit-evasion, manipulation with sensing uncertainty.

PART IV: PLANNING UNDER DIFFERENTIAL CONSTRAINTS
[pdf]

Chapter 13: Differential Models
[pdf] 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
[pdf] 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
[pdf] 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.

PART I: INTRODUCTORY MATERIAL [pdf]
Chapter 1: Introduction [pdf]	Motivation, examples, applications, high-level planning concepts, overview of the book.
Chapter 2: Discrete Planning [pdf]	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.
PART II: MOTION PLANNING [pdf]
Chapter 3: Geometric Representations and Transformations [pdf]	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 [pdf]	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 [pdf]	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 [pdf]	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 [pdf]	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 [pdf]	Navigation functions, smooth manifolds, vector fields, numerical potential functions, optimal navigation functions, compositions of funnels, dynamic programming on continuous spaces.
PART III: DECISION-THEORETIC PLANNING [pdf]
Chapter 9: Basic Decision Theory [pdf]	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 [pdf]	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 [pdf]	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 [pdf]	Value iteration for planning under sensing uncertainty. Robot localization, mapping, navigation, searching, visibility-based pursuit-evasion, manipulation with sensing uncertainty.
PART IV: PLANNING UNDER DIFFERENTIAL CONSTRAINTS [pdf]
Chapter 13: Differential Models [pdf]	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 [pdf]	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 [pdf]	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.