An interactive book · Foundation · Conceptual · Practical
A robot that knows where it is still has to decide how to move.
This book takes that problem seriously: it derives the geometry and the algorithms of motion planning in full, makes every hard idea something you can play with in the page, and implements all of it in Rust.
Twenty-three chapters take three robots — Rusty the rover, Reach the planar arm, and Hitch the car with a trailer — from a bug crawling around an obstacle to a complete planning stack: configuration space, roadmaps, sampling-based and optimal planners, dynamics and time-optimal trajectories, and the differential geometry of systems that cannot move sideways.
A rapidly-exploring random tree, growing live. Every step samples a random configuration, finds the nearest node of the tree, and extends toward it — so the tree is pulled into the largest unexplored regions first. Within seconds it threads the apartment and finds the goal. That bias is what Chapter 12 explains; Chapter 13 shows what it costs in path quality, and how to fix it.
The method
Three passes over every idea
Foundation
The full mathematics: configuration spaces as manifolds, completeness and optimality stated precisely, proofs sketched in the text and carried through in collapsible blocks.
Conceptual
Every hard idea becomes something you can manipulate. Drag an obstacle and watch a C-obstacle deform, grow a tree, scrub a phase-plane trajectory, parallel-park with a Lie bracket.
Practical
Then you build it in Rust, with the crates the field actually uses — nalgebra, parry, petgraph — and code you could lift into a real planner.
Contents
Six parts, twenty-three chapters
Foundations — Robots, Worlds, and Configuration Space
- CH.01Robots That Plan: The Piano Mover's ProblemWhy motion planning is hard and worth it: the piano mover, the taxonomy of planners, and the three robots of this book.
- CH.02The Lab: Three Robots, Three Worlds, One SimulatorRusty, Reach, and Hitch; the Apartment, the Workbench, and the Lot; collision queries and the deterministic simulator every chapter runs in.
- CH.03Bug Algorithms: Planning with a Contact SensorBug1, Bug2, and Tangent Bug: provable sensor-based planning from almost no mathematics, and boundary following as curve tracing.
- CH.04Configuration Space I: Obstacles in the Space of ConfigurationsConfigurations, C-obstacles, the torus of a two-joint arm, Minkowski sums, and what a collision checker actually computes.
- CH.05Configuration Space II: Topology, Manifolds, and Rigid BodiesHomeomorphisms, manifolds, rigid-body configuration spaces, metrics, and the Manifold trait every planner is generic over.
Classical Planners — Search, Potentials, Roadmaps, Cells
- CH.06Graph Search for PlannersBFS, Dijkstra, A* with its proofs, D* for replanning, universal plans, and what complete and optimal really mean.
- CH.07Potential FunctionsAttractive and repulsive potentials, brushfire and wave-front, the local-minimum disease, and navigation functions that cure it.
- CH.08Roadmaps I: Visibility Graphs and the Generalized Voronoi DiagramVisibility graphs and the generalized Voronoi diagram as a deformation retract, with the preimage theorem behind it.
- CH.09Roadmaps II: Sensor-Based Roadmaps and SilhouettesThe generalized Voronoi graph built from range data, hierarchical and rod variants, and Canny's silhouette roadmap.
- CH.10Cell Decompositions and CoverageTrapezoidal and Morse decompositions, boustrophedon coverage, sensor-based coverage, and pursuit-evasion as a coda.
Sampling-Based Planning
- CH.11Probabilistic RoadmapsProbabilistic roadmaps: samplers, kd-trees, local planners, narrow passages, and probabilistic completeness stated precisely.
- CH.12Tree Planners: EST, RRT, and FriendsEST, RRT and its Voronoi bias, RRT-Connect, SBL, SRT, and KPIECE: single-query planning as tree growth.
- CH.13Optimal Sampling-Based PlanningRRT*, PRM*, Informed RRT*, BIT*, FMT*: why RRT never improves and what asymptotic optimality costs.
- CH.14Planning for Many Bodies: Multi-Robot, Manipulation, and Kinodynamic PreviewsComposite configuration spaces, conflict-based search, manipulation modes, and a first forward-propagation planner for Hitch.
Planning with Uncertainty
- CH.15Kalman Filtering: The Geometric ObserverThe Luenberger observer, the Kalman filter as its optimal gain, observability, and EKF localization through Choset's geometric lens.
- CH.16Bayesian Localization and MappingRecursive Bayesian localization, grid and particle posteriors, mapping with known poses, and replanning on a belief.
Dynamics, Trajectories, and Constraints
- CH.17Robot DynamicsLagrangian dynamics of Reach, Christoffel symbols, Pfaffian constraints, and rigid-body rotation.
- CH.18Trajectory PlanningPath-velocity decomposition, the phase plane and its velocity-limit curve, zero-inertia points, and TOPP-RA.
- CH.19Trajectory Optimization and MPCCHOMP, STOMP, TrajOpt, iLQR and MPC: trajectory optimization as the modern descendant of direct methods.
- CH.20Nonholonomic Systems I: ControllabilityVector fields, distributions, Lie brackets, Chow's theorem, and controllability tests for cars and mechanical systems.
- CH.21Nonholonomic Systems II: Steering Cars, Trailers, and Underactuated SystemsDubins and Reeds-Shepp, chained forms, differential flatness, trailers, kinodynamic trees, state lattices and hybrid A*.
Frontiers and Integration
- CH.22Learning and PlanningLearned samplers, learned heuristics, neural and diffusion planners, benchmarked honestly against the classical baselines.
- CH.23Capstone: A Planning Stack from Sensor to MotionThree robots, one planning stack: sensor-based navigation, time-optimal arm trajectories, and trailer parking, running live.
Sister volume
Where am I? is the other book.
This book shares its robot, its simulator, and its method with Probabilistic Robotics via Rust, which treats estimation — Bayes filters, Kalman and particle filters, SLAM — in twenty-six chapters. Part IV here covers exactly as much of that as a planner needs, and links there for the rest.