Planning Algorithms Steven M. LaValle — RSF Specialist Shelf · Book S4 of 6

1. At a Glance

Official page (lavalle.pl, verified 2026-07-25):
https://lavalle.pl/planning/

2. Why This Book

Every Robotics Service Framework fault case that involves “where should this robot go next” is a planning problem, and Planning Algorithms is the reference that treats planning as a subject in its own right rather than a feature of one robot form. Siegwart’s Introduction to Autonomous Mobile Robots (No.3) covers mobile-robot planning as part of a broader AMR curriculum — enough to build and operate a working robot. LaValle’s book is what a Specialist-tier engineer reaches for when the planning problem itself is the hard part: a manipulator that needs a feasible reach trajectory around obstacles, a fleet of AMRs that keep blocking each other, or a robot that has to plan under sensor uncertainty rather than with full state knowledge.

A Professional-tier engineer does not need this book — the planning logic inside a commercial robot controller is a black box at that stage of training. A Specialist-tier engineer troubleshooting a scheduling or navigation failure that a vendor’s support team cannot fully explain needs the underlying algorithm family: sampling-based, combinatorial, or decision-theoretic, and this book is the standard place to find it, organized by the specific planning question rather than by robot form.

3. What’s Inside

At over 800 pages, this is a modular reference rather than a linear textbook — LaValle designed it to be consulted chapter by chapter for the planning question in front of you, not read start to finish. It opens with an introduction to motion planning and the configuration-space formalism that everything else builds on: representing a robot’s possible positions and orientations as a single point in an abstract space, which turns “plan a path” into “find a path through a space.”

From there it branches into the major algorithm families. Sampling-based planning covers probabilistic roadmaps (PRM) and rapidly-exploring random trees (RRT), the workhorse algorithms behind most practical motion planners today. Combinatorial planning covers exact, complete methods — cell decomposition, roadmap methods — that guarantee a solution exists to find, at higher computational cost. Feedback motion planning and sensor-based planning address the case where a robot cannot fully see its configuration space and has to plan around what it can currently sense.

Later chapters move into differential constraints (planning for systems that cannot move in every direction instantaneously, such as a car or a fixed-wing aircraft), planning under uncertainty (partially observable Markov decision processes, POMDPs), and decision-theoretic and game-theoretic planning — the chapters most relevant to multi-robot coordination and conflict. The book assumes no single reader needs every chapter; its structure is closer to an encyclopedia of planning than a course sequence, which is also why it has remained the standard reference in the field for two decades without needing a second edition.

4. The RSF Perspective

M7.4’s fault case “fleet deadlock from RCS scheduling race condition” — two AMRs blocking each other’s path with no conflict resolution — is, in this book’s terms, a multi-robot planning problem with no coordination mechanism. It is not a hardware fault and it is not a single-robot planning failure; each robot may have planned a perfectly correct individual path, and the deadlock still happens because neither path accounts for the other. The decision-theoretic and game-theoretic planning chapters are where this problem actually lives: two agents with independent objectives and shared space is exactly the setup those chapters formalize. The “deadlock detection algorithm + priority reassignment” fix that M7.4 names as the resolution is a direct, practical instance of the coordination and conflict-resolution ideas in this literature — a detection mechanism plus a rule for breaking the tie.

Beyond M7.4, this book underwrites two other Robotics Service Framework touchpoints. Module 3’s motion-planning material draws on the sampling-based planning chapters (PRM, RRT) as the algorithmic foundation for whatever planning capability a robot control stack exposes. Module 6’s diagnostic work benefits from the configuration-space formalism specifically: a service engineer who can describe a stuck or oscillating robot’s problem in configuration-space terms — is it a planning failure, a local-minimum trap, or a sensor gap — is diagnosing at the right layer instead of guessing at symptoms.

The right way to use this book is as a dictionary, not a syllabus. For an AMR fleet deadlock, go to the multi-robot and game-theoretic chapters. For a manipulator that cannot find a reach path around an obstacle, go to sampling-based planning. For a robot navigating with incomplete sensor coverage, go to sensor-based planning and the uncertainty chapters. Reading the book cover to cover is neither necessary nor how it was designed to be used; treat the table of contents as the primary navigation tool and read a chapter only when a specific fault or design question sends you to it.

5. Difficulty & Audience

Difficulty carries two ratings, the same dual-rating logic the Springer Handbook (No.10) uses for the same reason: 4 of 5 to read a chapter deeply enough to derive and implement the algorithms in it, 2 of 5 to use the book as a reference — look up the right chapter, extract the algorithm outline and the relevant theorem, move on. Most Specialist-tier engineers will use it the second way most of the time. Budget 3–5 hours per chapter for a deep read, or 30–60 minutes to extract what a specific fault or design question needs.

Not required at Robotics Service Framework Professional tier. Read individual chapters when a Module 3 planning question, a Module 6 diagnostic case, or an M7.4 fleet-coordination fault sends you looking for the underlying algorithm family.

6. Companions & Alternatives

Pairs with Siegwart’s Introduction to Autonomous Mobile Robots (No.3) for the applied mobile-robot context this book treats abstractly, and with Siciliano, Sciavicco, Villani & Oriolo’s Robotics: Modelling, Planning and Control (Specialist Shelf S6) for the manipulator side of planning. The full text is free as HTML and PDF from the author’s site, alongside a Cambridge University Press print edition for readers who want a physical reference. It remains the standard citation in the planning literature — most later planning papers, including the ones behind commercial AMR fleet schedulers, use this book’s terminology and problem formulations as their starting point.