2006 PlanningAlgorithms

• (LaValle, 2006) ⇒ Steven M. LaValle. (2006). “Planning Algorithms.” Cambridge University Press. ISBN:0521862051

Subject Headings: Planning Algorithm, Planning Under Uncertainty, Discrete Planning.

Notes

• It has a dedicated website at http://planning.cs.uiuc.edu/
• It has an HTML version at http://planning.cs.uiuc.edu/book.html

Cited By

• http://scholar.google.com/scholar?q=%222006%22+Planning+Algorithms
• http://dl.acm.org/citation.cfm?id=1213331&preflayout=flat#citedby

Quotes

Abstract

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.

Table of Contents

  PART I: INTRODUCTORY MATERIAL
  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.

  PART II: MOTION PLANNING
  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.

  PART III: DECISION-THEORETIC PLANNING
  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.

  PART IV: PLANNING UNDER DIFFERENTIAL CONSTRAINTS
  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.
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.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2006 PlanningAlgorithms	Steven M. LaValle			Planning Algorithms						2006