Robots That Plan: The Piano Mover's Problem

Why motion planning is a discipline with theorems rather than a bag of heuristics — the piano mover, Choset's taxonomy of planners, a complete planner in forty lines, and the one idea the whole book rests on, that a robot is a point in the right space.

The problem

Below, a point robot with nothing but a contact sensor is crawling toward a goal it cannot see past. Its entire strategy is two sentences long: walk toward the goal; if you bump into something, go around it. Watch it arrive.

This is a provably complete planner, and it fits in forty lines.

"Complete" is a technical word and the whole book is careful about it: the planner finds a path whenever one exists and reports failure in finite time when none does. It needs no map. It never plans ahead. It has a theorem — the counter under the canvas never exceeds the bound printed beside it, and the bound is a formula, not a measurement. Drag the goal behind the larger obstacle: the walk around it gets longer and the bound grows with it, exactly as the formula says it must. Switch to Bug2, the greedy sibling that leaves an obstacle the first time it can, and the two totals tell you something that is true of search in general: greed is usually faster and sometimes disastrous. The "comb" preset is a world built so that greed loses.

Everything in this chapter is a first look at something a later chapter proves. The Bugs are Chapter 3's. The deeper claim — that the robot's shape can be made to disappear — is Chapter 4's, and it comes next.

Building intuition

The piano is a point

Choset's opening problem is the piano mover's problem: a rigid body, a known set of stationary obstacles, a start and a goal; find a collision-free path. In the plane it becomes the sofa mover's problem, and a sofa is enough to make the point.

On the left is the room: a wall with a doorway, and a sofa you can drag and turn. On the right is something you have probably never looked at before. It is the same sofa, drawn as a single dot, in a space whose axes are the sofa's position — and the amber shapes around the dot are the sofa's configurations that would put it through a wall, at the heading it currently has.

Drag the sofa into the wall. The dot touches amber at the same instant. Not before, not after: the two pictures are the same fact drawn twice. Now turn the sofa and watch the amber reshape itself. The walls did not move. The robot changed, and the obstacle the planner fights changed with it. At one heading the doorway is a wide channel between two amber blobs; turn the sofa broadside and the channel closes. A sofa that only fits diagonally has a channel that exists at some headings and not at others — your first sighting of a narrow passage, the thing that makes Part III hard.

Three vocabulary words have just been used informally, and the Foundation section pins them down. A configuration is a complete description of where every point of the robot is: for the sofa, its position and heading, $(x, y, \theta)$. The configuration space $\Q$ is the set of all of them. A C-obstacle is the set of configurations at which the robot overlaps a workspace obstacle. The right-hand pane shows one slice of $\Q$ — fixed $\theta$ — because $\Q$ is three-dimensional and the screen is not. Toggle "stack all θ-slices" to see the slices pile into the translucent block of Choset's figure F.8, and notice the channel twisting as it climbs.

Choset's gallery

Choset's Chapter 1 opens with a gallery of problems, and each one carries a definition this book will need. The piano mover is the pure geometric problem: obstacles known and stationary, execution exact, planning finished before the robot moves — offline planning. NASA's Mini AERCam, a free-flying inspection camera with twelve cold-gas thrusters, is the same problem with one word changed: because it moves by applying forces, it needs not just a path but the speed along the path — a trajectory, and with it dynamics (Part V). The CyCab and the Segway, small vehicles that must parallel park, look like the sofa mover's problem until you notice that a car cannot slide sideways; that velocity constraint is called nonholonomic, the car is called nonholonomic too, and Chapters 20 and 21 are about it. Demining — passing a sensor over every point of a field — is the first time completeness is the whole point: a planner that might miss a mine is not a planner. The painting arm wants its coverage to be time-optimal, because robots in factories cost money by the second. Snake robots have more joints than their task needs — redundant, or hyper-redundant — and non-Euclidean configuration spaces of high dimension. The surgical robots, the digital actors, and the protein-folding problem each get a paragraph in Choset and a pointer here: Chapter 14 picks up the molecule as an articulated linkage.

Two of Choset's examples are handed to the sister book, which tells them properly. RHINO, the museum tour guide, is a localization story — a robot comparing its sensors against a stored map because exact execution is a fiction — and Sojourner on Mars is a mapping story. Probabilistic Robotics via Rust owns both; this book borrows their estimation only as far as a planner needs it, in Part IV.

The cast

Choset's protagonists were the robots of 2005. This book's are built in Chapter 2 and used until the end. Rusty is a disc-shaped differential-drive rover, shared with the sister book, whose home is the Apartment — five rooms off a long corridor. Its configuration is a planar pose, and for collision purposes a point of $\R^2$. Reach is a planar two-link arm, with a three-link variant for redundancy, bolted to the Workbench; its configuration is two angles, a point on a torus. Hitch is a car that may pull one trailer, living in the Lot; its configuration is a pose in $\SEtwo$, plus one more circle for the trailer. Three robots, three configuration spaces of three different shapes, so that when the book says "a point in $\Q$" it can mean three concretely different things.

The planner's taxonomy

What kind of thing is a planner? Choset's Table 1.1 answers with three axes, and the board below is that table with the chapters of this book placed on it.

The task comes first: navigate (one configuration to another), cover (a tool over every point), localize (a map and sensors to a configuration), map (an unknown environment to a representation). Then the robot: how many degrees of freedom and what the configuration space looks like; whether it can move instantaneously in any direction of $\Q$ (omnidirectional) or is subject to velocity constraints (nonholonomic); whether velocities are its controls (kinematic) or forces are (dynamic). Then the algorithm: optimal or merely feasible; its computational complexity; which of three kinds of completeness it has; online or offline; sensor-based or working from a model.

Hover "Optimal" and count. Most of this book — most of the field — is not about shortest paths. It is about finding a path, with a guarantee about when you will find one, for a robot whose shape and constraints make "a path" hard to define. Hover "Complete" and notice that two of its chapters, 3 and 9, are sensor-based planners with no map at all. A planner without a map is not a heuristic. The hook above was one.

The mathematics

This chapter's mathematics is deliberately light, and nothing in it is retracted later. The symbols below are the book's global notation, making their first appearance; each is formalized in the chapter named.

Definitions

The robot is a point

The algorithm

Bug1 is stated informally here and formally as Choset's Algorithm 1 in Chapter 3. Two behaviors, one memory, one test.

Line 5 is the exhaustive search: Bug1 walks the whole perimeter before committing to a leave point, which is why its leave point is optimal and its cost is a full $p_i$. Bug2, Choset's Algorithm 2, replaces lines 5–6 with a greedy exit: fix the m-line from $\qstart$ to $\qgoal$ once, and leave the boundary the first time the robot is back on the m-line, closer to the goal than the hit point, and able to step toward the goal. Bug2 is quick when obstacles are simple and can be arbitrarily worse than Bug1 when they are not.

The worked example, by hand

The book's first "numeric example equals unit test". A text world, nine columns by five rows, origin at the top left, 4-connected unit moves, a point robot that occupies one cell and whose contact sensor reports whether the next cell is #:

.........
...###...
S..###..G
...###...
.........

$\qstart = (0, 2)$, $\qgoal = (8, 2)$, one $3 \times 3$ obstacle in columns 3–5, rows 1–3. Its perimeter, measured as the ring of free cells the robot walks when going round it, is $p_1 = 16$.

1. Motion-to-goal along row 2: $(1, 2)$, $(2, 2)$ — 2 steps. The next cell $(3, 2)$ is #, so $q^H_1 = (2, 2)$.
2. Circumnavigate the ring back to $(2, 2)$ with the obstacle on the right hand: 16 steps, recording $d(\cdot, \qgoal)$ at every cell. The unique minimum is $(6, 2)$, at distance 2.
3. Walk to the leave point $q^L_1 = (6, 2)$ the shorter way round. The ring is symmetric about row 2, so both ways are 8 steps; the code breaks the tie clockwise. 8 steps.
4. Motion-to-goal: $(7, 2)$, $(8, 2)$ — 2 steps.

Total $L_{\mathrm{Bug1}} = 2 + 16 + 8 + 2 = \mathbf{28}$ steps. The bound: $d + 1.5\, p_1 = 8 + 24 = 32 \ge 28$. For contrast, Bug2 on the same world leaves the ring the first time it is back on row 2 and closer to the goal — at $(6, 2)$, after 8 steps of boundary following — for $2 + 8 + 2 = \mathbf{12}$, which here is also the shortest 4-connected path.

The grid-specific footnote promised above. On a 4-connected grid "move straight toward the goal" is a staircase whose length is $|\Delta x| + |\Delta y|$, not the Euclidean $d$. The bound the Bug Preview prints, and the one the library checks on random worlds, is Choset's inequality with that grid distance $d_1$ in place of $d$; on the worked example the m-line is a row, so $d_1 = d = 8$ and the two bounds coincide. Chapter 3 does the continuous version, where the footnote disappears.

Implementation in Rust

The first program is a dependency-free Rust binary, edition 2024, by design: your first build must finish in seconds and cannot fail on a native dependency. The workspace Cargo.toml already pins the book's stack (nalgebra 0.35, parry2d 0.30, rand 0.9, petgraph 0.8, pathfinding 4.15), but nothing in this chapter touches it.

Setup (CI-tested on Linux, macOS, Windows): install rustup and the stable toolchain (edition 2024 needs 1.85 or later); clone the book's repository; then

cargo run -p ch01_hello
cargo test -p ch01_hello

Optional, and deferred to Chapter 2: rustup target add wasm32-unknown-unknown for the browser cross-check, and Node 20.9 or later for the site in web/.

The world and the sensor

//! Bug1 on a text world. Zero dependencies, edition 2024.

/// '#' is obstacle, everything else is free. 4-connected unit moves.
struct TextWorld { rows: Vec<Vec<u8>> }

#[derive(Clone, Copy, PartialEq, Eq, Debug)]
struct Cell { x: i32, y: i32 }

/// Headings in screen coordinates (y grows downward): E, S, W, N. Turning right adds one.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
enum Dir { E, S, W, N }

/// The index into STEP back to a heading: 0 → E, 1 → S, 2 → W, 3 → N.
impl From<usize> for Dir {
    fn from(i: usize) -> Dir { [Dir::E, Dir::S, Dir::W, Dir::N][i % 4] }
}

impl Dir {
    fn right(self) -> Dir { Dir::from(self as usize + 1) }
    fn left(self) -> Dir { Dir::from(self as usize + 3) }
    fn back(self) -> Dir { Dir::from(self as usize + 2) }
}

impl Cell {
    /// One unit move; STEP is defined with the behaviors below.
    fn step(self, d: Dir) -> Cell {
        let (dx, dy) = STEP[d as usize];
        Cell { x: self.x + dx, y: self.y + dy }
    }
}

impl TextWorld {
    /// The contact sensor: is the cell blocked — or outside the bounded workspace?
    /// Choset assumes W is bounded; here the border is simply a wall the sensor feels.
    fn blocked(&self, c: Cell) -> bool {
        if c.y < 0 || c.x < 0 { return true; }
        match self.rows.get(c.y as usize).and_then(|r| r.get(c.x as usize)) {
            Some(b'#') => true,
            Some(_) => false,
            None => true,
        }
    }

    /// Parse a map; S and G are the query.
    fn parse(s: &str) -> (Self, Cell, Cell) {
        let rows: Vec<Vec<u8>> = s.lines().filter(|l| !l.is_empty()).map(|l| l.bytes().collect()).collect();
        let find = |ch: u8| rows.iter().enumerate()
            .find_map(|(y, r)| r.iter().position(|&b| b == ch).map(|x| Cell { x: x as i32, y: y as i32 }))
            .expect("the map marks S and G");
        let (s, g) = (find(b'S'), find(b'G'));
        (TextWorld { rows }, s, g)
    }
}

/// Euclidean distance d(x, y) — Bug1 may measure it, by assumption (Choset §2.1).
fn dist(a: Cell, b: Cell) -> f64 {
    (((a.x - b.x).pow(2) + (a.y - b.y).pow(2)) as f64).sqrt()
}

The two behaviors

const STEP: [(i32, i32); 4] = [(1, 0), (0, 1), (-1, 0), (0, -1)]; // E, S, W, N

/// One step of motion-to-goal: the 4-neighbor that most reduces d(·, goal).
/// `Err(dir)` when that neighbor is blocked — the robot has hit the obstacle,
/// pushing in direction `dir`.
fn motion_to_goal(w: &TextWorld, x: Cell, goal: Cell) -> Result<Cell, Dir> {
    let (best, dir) = (0..4)
        .map(|d| (Cell { x: x.x + STEP[d].0, y: x.y + STEP[d].1 }, d))
        .min_by(|a, b| dist(a.0, goal).total_cmp(&dist(b.0, goal)))
        .expect("four neighbors");
    if w.blocked(best) { Err(Dir::from(dir)) } else { Ok(best) }
}

/// One step of boundary following with the obstacle on the robot's right hand —
/// the grid analogue of the surface-normal rule of Choset §2.3.1. O(1) sensing.
///
/// Try to turn toward the wall (it may have turned away), else go straight,
/// else turn away, else reverse. On the ring around a block this traces the
/// 8-neighborhood of the obstacle, which is the perimeter the bound counts.
fn follow_boundary(w: &TextWorld, x: Cell, heading: Dir) -> (Cell, Dir) {
    for h in [heading.right(), heading, heading.left(), heading.back()] {
        let n = x.step(h);
        if !w.blocked(n) { return (n, h); }
    }
    (x, heading) // boxed in on all four sides: cannot happen from a free start
}

/// Walk the whole boundary from the hit point until it is re-encountered.
/// Returns the cells visited after the hit, ending with the hit itself —
/// so the length is the perimeter p_i as the robot measures it.
fn circumnavigate(w: &TextWorld, hit: Cell, toward: Dir) -> Vec<Cell> {
    let (mut cell, mut heading, mut ring) = (hit, toward.left(), Vec::new());
    loop {
        (cell, heading) = follow_boundary(w, cell, heading);
        ring.push(cell);
        if cell == hit { return ring; }
    }
}

Bug1 and the program

enum Outcome { Reached(Vec<Cell>), Unreachable { at: Cell } }

/// Bug1, Choset Algorithm 1: motion-to-goal; on contact circumnavigate fully,
/// remembering the perimeter point closest to the goal; return to it the shorter
/// way; repeat. If leaving the leave point toward the goal would re-enter the
/// obstacle, the goal is unreachable.
fn bug1(w: &TextWorld, start: Cell, goal: Cell) -> (Outcome, Vec<usize>) {
    let (mut path, mut perimeters, mut x) = (vec![start], Vec::new(), start);
    while x != goal {
        match motion_to_goal(w, x, goal) {
            Ok(next) => { x = next; path.push(x); }
            Err(dir) => {
                let hit = x;
                let ring = circumnavigate(w, hit, dir);
                perimeters.push(ring.len());
                path.extend(&ring);
                // The leave point: closest to the goal; the first wins a tie.
                let (i, _) = ring.iter().enumerate()
                    .min_by(|a, b| dist(*a.1, goal).total_cmp(&dist(*b.1, goal))).unwrap();
                // The shorter way round; a tie goes forward (clockwise).
                if i + 1 <= ring.len() - 1 - i { path.extend(&ring[..=i]); }
                else { path.extend(ring[i..ring.len() - 1].iter().rev()); }
                x = ring[i];
                if motion_to_goal(w, x, goal).is_err() {
                    return (Outcome::Unreachable { at: x }, perimeters);
                }
            }
        }
    }
    (Outcome::Reached(path), perimeters)
}

/// The map with the executed path marked `·`, and S and G on top.
fn render(w: &TextWorld, s: Cell, g: Cell, path: &[Cell]) -> String {
    let mut rows: Vec<Vec<char>> = w.rows.iter()
        .map(|r| r.iter().map(|&b| if b == b'#' { '#' } else { '.' }).collect())
        .collect();
    for c in path { rows[c.y as usize][c.x as usize] = '·'; }
    rows[s.y as usize][s.x as usize] = 'S';
    rows[g.y as usize][g.x as usize] = 'G';
    rows.iter().map(|r| r.iter().collect::<String>()).collect::<Vec<_>>().join("\n")
}

const WORLD: &str = "\
.........
...###...
S..###..G
...###...
.........
";

fn main() {
    let (w, s, g) = TextWorld::parse(WORLD);
    match bug1(&w, s, g) {
        (Outcome::Reached(path), perimeters) => {
            let steps = path.len() - 1;
            let p: usize = perimeters.iter().sum();
            println!("{}", render(&w, s, g, &path));
            println!("steps: {steps}  straight-line: {}  bound d + 1.5·Σp: {}", dist(s, g), dist(s, g) + 1.5 * p as f64);
        }
        (Outcome::Unreachable { at }, _) => println!("goal unreachable; detected at {at:?}"),
    }
}

..·····..
..·###·..
S··###··G
..·###·..
..·····..
steps: 28  straight-line: 8  bound d + 1.5·Σp: 32

(The rendering marks the executed path with ·: out along row 2, once around the block, then the shorter way back to the leave point. The Bug Preview above also marks the hit point H at $(2, 2)$ and the leave point L at $(6, 2)$.) The tests lock the number, and lock the failure mode:

#[test]
fn worked_example_ch01() {
    let (w, s, g) = TextWorld::parse(WORLD);
    let (Outcome::Reached(path), perimeters) = bug1(&w, s, g) else { panic!("reachable") };
    assert_eq!(path.len() - 1, 28);
    assert_eq!(perimeters, vec![16]);
    assert!(28.0 <= 8.0 + 1.5 * 16.0);
}

#[test]
fn unreachable_is_detected() {
    let (w, s, g) = TextWorld::parse(".........\n.....###.\nS....#G#.\n.....###.\n.........\n");
    let (outcome, perimeters) = bug1(&w, s, g);
    assert!(matches!(outcome, Outcome::Unreachable { .. }));
    assert_eq!(perimeters.len(), 1, "one circumnavigation, then give up");
}

/// Exercise 6: implement `bug2`, then `cargo test --features exercise-bug2`.
#[cfg(feature = "exercise-bug2")]
#[test]
fn bug2_text_world() {
    // Chapter 3 derives Bug2 properly; the expected count on this world is 12.
    let (w, s, g) = TextWorld::parse(WORLD);
    assert_eq!(bug2(&w, s, g).len() - 1, 12);
}

Putting it together

The integration lab is your own machine. Clone the workspace, build, reproduce the 28. Then edit WORLD to the $4 \times 4$ block of the exercise above, predict the new length and the new bound before running, run, and check. The point is not the number; it is that you have just watched a guarantee stay true while the world changed under it, and that a test will tell you if a future edit ever breaks it.

Two conventions begin here and never change. Every worked number in this book is reproduced by a test: a Rust test in the crate and an invariant in the browser library, so that the prose, the program, and the animation cannot drift apart without the build going red. And every chapter runs the same rhythm, in the same colors.

The color code is not decoration. Hover a tinted term in an equation on any page — try the $\htmlClass{term-cobstacle}{\QO_i}$ in the first derivation above — and every figure on the page fades every other role. The amber in the Piano Mover, the amber term-cobstacle in the definition of $\QO_i$, and a // --rm-cobstacle comment in a Rust listing are the same object seen three ways. Green is where you start, red is where you are going (and, in Chapter 2's simulator, the flash of a collision — a collision is where a plan ends), slate is a wall, amber hatched is a wall seen from configuration space, blue is a roadmap or tree, purple is the path a planner found, orange is the robot and the path it actually drove.

A map of what comes next, by cell of the taxonomy board. Chapter 2 builds the cast and the collision checker that every planner asks its four questions of. Chapter 3 proves what this chapter only checked: Bug1, Bug2, and Tangent Bug, with their bounds. Chapters 4 and 5 are configuration space done properly — the amber computed exactly, the torus and $\SEtwo$ as manifolds. Part II is the classical planners for a point in $\Qfree$: search, potentials, roadmaps, cells. Part III trades completeness for speed and gets probabilistic completeness back. Part IV is what a planner must know about not knowing where it is. Part V puts time, dynamics, and Hitch's constraint back in. Part VI closes the loop the hook above opened: three robots, one planning stack, running live.

Exercises

1. Foundation exerciseFDifficulty 1 of 3Classify the gallery

   Classify each of Choset's motivating examples — the piano mover, the Mini AERCam, the CyCab and Segway, RHINO, Sojourner, demining, the painting arm, snake robots, surgical robots, digital actors, protein folding — on all three axes of the taxonomy board. Which cells of Table 1.1 does the gallery leave empty? Name one robot deployed since 2020 that fills each empty cell.

2. Foundation exerciseFDifficulty 2 of 3Count the degrees of freedom

   The sofa in the Piano Mover has $\dim \Q = 3$. Count the degrees of freedom of (a) two sofas in the same room, (b) two sofas tied by a rope of fixed length pulled taut, (c) one sofa on casters that cannot roll sideways. For each, say whether the constraint changes $\dim \Q$, and why — this is the holonomic versus nonholonomic distinction of Choset §3.3, met early.

   Stuck? Get a hint
3. Conceptual exerciseCDifficulty 1 of 3Predict the leave side

   In the Bug Preview, set the goal directly behind the larger of the two obstacles.

   Predict first

   Before pressing play: which side will Bug1 leave the obstacle from, and will the counter land closer to d or to the bound?

   The side it hits on; closer to d

   The far side, nearest the goal; closer to the bound

   Whichever side is shorter to walk; closer to d
4. Conceptual exerciseCDifficulty 2 of 3The widest channel

   In the Piano Mover, shorten the sofa until it fits the doorway nose-first. Predict how the amber slice changes as you rotate the sofa by $90°$, then verify. Which heading gives the widest channel through the doorway, and why is that heading not $\theta = 0$ when the doorway is in a side wall?

   Stuck? Get a hint
5. Practical exercisePDifficulty 2 of 3A C-shaped obstacle and a lying sensor

   Modify ch01_hello so the obstacle is a C shape opening toward the start. Predict the path length and the bound before running. Then make the contact sensor lie with probability $0.05$, using a fixed seed and a tiny hand-rolled linear congruential generator — still zero dependencies — and report what breaks: the length, the guarantee, or both.

6. Practical exercisePDifficulty 3 of 3Bug2, and a world where it loses

   Implement Bug2 in ch01_hello by changing only the exit condition of boundary following: leave when back on the fixed m-line, closer to the goal than the hit point, and able to step toward it. Make bug2_text_world pass with 12 — it compiles only when you ask for it, with cargo test --features exercise-bug2. Then construct a text world where Bug2's count exceeds Bug1's. The comb preset in the Bug Preview is one answer — a hook whose nearest-to-goal point sits high above the m-line, so that Bug1 leaves from there on a fresh line over a row of teeth that Bug2, welded to the m-line, must climb one by one. You have just drawn Choset's figure 2.4.

References

1. Choset, H., Lynch, K. M., Hutchinson, S., Kantor, G., Burgard, W., Kavraki, L. E., and Thrun, S. (2005) Principles of Robot Motion: Theory, Algorithms, and Implementations. MIT Press.link to Principles of Robot Motion: Theory, Algorithms, and Implementations (opens in a new tab)

   Chapter 1 is the source of the gallery, Table 1.1, eq. (1.1), and the notation this book adopts; §2.1 is the source of Bug1, Bug2, and the bound checked here. Lumelsky and Stepanov's 1987 Algorithmica paper, 'Path-planning strategies for a point mobile automaton moving amidst unknown obstacles of arbitrary shape', is the Bug algorithms' original, cited there as [301].

2. Lozano-Pérez, T. (1983) Spatial Planning: A Configuration Space Approach. IEEE Transactions on Computers C-32(2), 108–120.doi:10.1109/TC.1983.1676196 (opens in a new tab)

   The paper that made 'the robot is a point' an algorithm: C-obstacles computed for polygons, the ancestor of the Piano Mover's amber.

3. Latombe, J.-C. (1991) Robot Motion Planning. Kluwer Academic Publishers (The Springer International Series in Engineering and Computer Science, vol. 124).doi:10.1007/978-1-4615-4022-9 (opens in a new tab)

   The reference text for the decade before Choset, and the source of the piano-mover framing of configuration space that Chapter 1 inherits; its author wrote Choset's foreword.

4. Kavraki, L. E., Švestka, P., Latombe, J.-C., and Overmars, M. H. (1996) Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation 12(4), 566–580.doi:10.1109/70.508439 (opens in a new tab)

   Where 'probabilistically complete' — the third kind of completeness on the taxonomy board — enters the field. Chapter 11.

5. Karaman, S. and Frazzoli, E. (2011) Sampling-based Algorithms for Optimal Motion Planning. International Journal of Robotics Research 30(7), 846–894.doi:10.1177/0278364911406761 (opens in a new tab)

   The modern occupant of the board's 'Optimal' cell: asymptotic optimality for sampling-based planners. Chapter 13.

6. Şucan, I. A., Moll, M., and Kavraki, L. E. (2012) The Open Motion Planning Library. IEEE Robotics & Automation Magazine 19(4), 72–82.doi:10.1109/MRA.2012.2205651 (opens in a new tab)

   What a planner is today: infrastructure, not a research artifact. The systems framing behind the taxonomy board's chapter links.