Learning and Planning

Where machine learning belongs in a motion planner, said without hype. Learned samplers, learned heuristics, neural planners and diffusion models all replace the proposal and never the verifier, so completeness and optimality are inherited from the classical stage and speed is bought from the learner at a measurable exchange rate.

The problem: a sampler that learned the bench

Chapter 11's PRM draws configurations uniformly from Reach's torus. On a cluttered Workbench most of those samples land where the eventual path never goes, and each costs a collision check plus a dozen more for every edge tried. Someone who has watched a thousand roadmaps grow knows roughly where paths go; Chapter 11's Gaussian, bridge and OBPRM samplers were three attempts to write that knowledge down as a rule.

The modern move is not to write it down at all. Generate six hundred random Workbenches, run Chapter 11's planner on three queries in each, record every node of every path it found, and train a small network to predict, from the table's occupancy raster and the query's two endpoints, where on the torus the path nodes will be. Then sample from the network. The data is real: every recorded node passed Chapter 2's collision checker, every path was certified edge by edge. Nothing in the planner changes except the line that draws the next sample.

Here is what that buys, measured on thirty solvable queries on fresh Workbenches from the same random generator, every planner stopped at a fixed number of collision checks. At a budget of 100 checks the learned proposal — mixed with ten percent uniform, for a reason the mathematics will make non-negotiable — solves 60% of the queries and the uniform PRM solves 47%. At 400 checks the order reverses: the learned sampler solves 77% and uniform 90%. At 12,800 checks both solve every one. The paths the learned sampler finds are shorter (1.28 times the best known path against uniform's 1.33), and every millisecond of that is spent on a network that took 241 seconds of data generation and training before the first query, which no realistic number of queries on this suite pays back.

That is the chapter in miniature: the learner moved where the samples fell, could not change what the planner was able to find, and whether the move paid depends on budget, world and bookkeeping.

Building intuition: the scout and the surveyor

The chapter's picture in one line: the learner is a scout who says "look here"; the planner is the surveyor who still measures every edge. Each widget below puts a different scout in front of the same surveyor. Read them as a set — they are four instances of one design and one honest scoreboard.

Where the samples fall

Two Chapter 11 PRMs grow side by side on the same randomized Workbench, seed and query. The left pane draws uniformly; the middle pane draws from the learned proposal $\hat p_\theta(q \mid \mathcal{E}, \qstart, \qgoal)$ — the grey heat under the amber C-obstacle raster — mixed with uniform at weight $\lambda$; the right pane is the Workbench.

On the default world the learned pane joins start and goal after about half the collision checks the uniform pane spends: the heat sits on the band of the torus the path actually uses, and the samples follow it. Now press held-out generator. The world is replaced by one built from long thin bars at arbitrary angles — a family of shapes the training generator never produced — and on this seed the learned pane needs more than twice the checks uniform does. The heat still lands in confident blobs; they are just in the wrong place, because the network learned what blocks do to Reach's torus and is now looking at bars. Three things to notice, in order of importance.

Both panes connect. Slide the sample budget up and both roadmaps join on every solvable query you try, on both generators, at every $\lambda$ the slider allows. The learner moves where the planner looks. It does not move what the planner can find — that is the content of Derivation 1, and the reason the $\lambda$ slider stops at 0.02 instead of reaching zero.

The currency is collision checks. On Reach's torus a query is usually joined within a handful of nodes, so "samples until the join" hides the difference. The check count — the book's cost unit since Chapter 11 — shows it. The success-at-budget curves below the canvas accumulate over further seeds in the background, and they are the honest summary: on some worlds the learner wins big, on others it loses, and the curve is the average of both.

The bar chart is the chapter's first formula. It prints $D_{\KL}(\hat p \,\|\, u)$ on the four quadrants of the torus, live: how concentrated the proposal is — not whether the concentration is in the right place, which takes a second divergence. The four-cell example computes both by hand.

A heuristic that knows too much

Chapter 6's A* on a 24 × 24 lattice of Reach's torus, with the admissible octile distance, a learned cost-to-go $\hat h_\theta$, or $\hat h_\theta / (1 + \epsilon_{val})$. Left: explored set (blue), path (purple), a red mark wherever $\hat h$ exceeds the true cost-to-go $h^*$ from backward Dijkstra. Right: every reachable cell at $(h^*(v), \hat h(v))$ against the diagonal.

On the default world the learned heuristic does exactly what the folklore says a better heuristic does: it expands fewer nodes than octile. And it returns a longer path — the cost-ratio tile reads above one. The scatter shows why: a cloud of red points above the diagonal, cells where the net guessed high. The measured $\epsilon$ is the worst of those ratios on this world, and the fourth tile prints the guarantee $(1 + \epsilon)\,C^*$ that Derivation 3 proves the realized cost can never exceed. It never does — on this world, on any world you re-roll to, at any scale.

Then try the other two settings. Slide the scale above 1 and even the octile heuristic becomes inadmissible (that is weighted A*, which Chapter 6 introduced): expansions fall, the path stays at or above $C^*$, and the bound line rises with the scale. Switch to the deflated heuristic and the red cloud vanishes, the path becomes optimal again — and the expansion count balloons to nearly three times octile's. Dividing by $1 + \epsilon_{val}$ buys admissibility on the validation worlds by throwing away most of what the net knew.

Across many worlds the summary is less flattering: on the audit worlds the learned heuristic and octile expand almost the same number of nodes (ratio 0.994). Octile is already good on this lattice — its mean ratio to $h^*$ on the validation worlds is 0.917, against the net's 0.959. What does not vary is the bound: the learned heuristic cannot hurt you by more than its measured $\epsilon$.

The net that hops

An MPNet-style policy proposes Reach's next configuration a hop $\eta = 0.35$ rad away. Each hop goes to the verifier — Chapter 11's Steer, fulfilled by Chapter 2's sound swept check — and is drawn blue if certified, red and dashed if not. Rejected stretches are bridged by Chapter 12's RRT-Connect (the thin blue mini-tree); if local repairs run out, RRT-Connect runs on the whole original query.

On the training tab most of the hops pass. The policy learned the shape of paths on block-shaped Workbenches, and on this one it walks most of the way by itself; one short repair splices over the stretch where it clipped a block. Switch to the held-out tab: fewer than two-thirds of the hops pass, and the tile that splits the path into by net and by repair tips the other way — the repair planner supplies most of the length. Now turn repair off. The tile labelled net alone reads failed on both tabs. A path is only a path if every hop is certified and the last one reaches the goal; one clipped corner is enough to have nothing. The network did not learn to plan; it learned the training distribution of paths — valuable, since on a good day it proposes most of the answer — and with the repair planner behind it the composition is exactly as complete as RRT-Connect (Derivation 4).

Noise into paths

Diffusion models generate by running a noising process backward. The smallest example: a trajectory $\tau \in \mathbb{R}^{16}$ is a configuration per time step, pinned to 0 at both ends; a slab blocks $\lvert q \rvert < 0.3$ during steps 5 through 10; demonstrations swing around it, half above and half below. Thirty-two samples start as pure noise and are denoised for $K = 40$ steps by a small net, then checked: purple is clear, red went through the slab.

Scrub the step slider slowly from 0. For the first half of the steps nothing recognizable happens; then the swing appears, both swings, as the samples commit to going over or under. At step 40 a good fraction are red: plausible-looking trajectories that dip into the slab for a time step or two. Turn on cost guidance — each step also descends the gradient of a smooth cost that penalizes coming near the slab — and the red fraction drops a great deal. It does not reach zero, on any seed you try. A soft penalty is not a hard constraint, which is why Chapter 2's checker runs on every sample and why a diffusion planner is a proposal in exactly the sense of the sampler above.

The board

Seven planners — four hand-designed PRM samplers, the learned sampler at $\lambda = 0.1$, RRT-Connect, and the MPNet-style planner — on thirty solvable queries from each generator, same world, query and seed, stopped at 12,800 collision checks; smaller budgets are read off the same runs.

Toggle the suite and move the budget. The learned rows (tinted orange) win at the smallest budgets in distribution and then fall behind; their first paths are consistently shorter; their wall-clock is worse. RRT-Connect, which nobody trained, beats every PRM row at almost every budget on both suites. Drag the amortization slider to $10^4$ queries and the learned rows still do not overtake uniform on wall-clock: they were never faster per query. Putting it together reads this board line by line.

The mathematics

Proposals and verifiers

Everything in this chapter is an instance of two definitions and one composition.

The constant in Definition 22.2 is the constant in the failure bound. The shipped sampler's raw softmax leaves 188 of 3,456 cells, across 24 audited worlds, below a thousandth of the uniform mass: positive, and useless as a guarantee. The mixture replaces that unknowable minimum by $\lambda$.

Completeness survives a floor

Recall Chapter 11's statement of Choset's Theorem 7.4.3: if PRM with local planner relation $R$ and sampling measure $\mu$ is probabilistically complete, there are $\ell$ sets $A_1, \dots, A_\ell \subset \Qfree$, each of positive measure, such that any choice $x_j \in A_j$ chains into a path $x \mathrel{R} x_1 \mathrel{R} \cdots \mathrel{R} x_\ell \mathrel{R} y$; and with $p = \min_j \mu(A_j)$ the failure probability after $n$ samples is at most $\ell(1-p)^n \le \ell e^{-pn}$. Choset introduces the section by saying the framework covers "sampling from arbitrary distributions", and the proof bears it out: the only property of $\mu$ it uses is a lower bound on the mass of each tile.

Hitting times, divergences, and maximum likelihood

Derivation 1 is a worst-case statement — the learner can only lose a factor $1/\lambda$. What it can win is a statement about where its mass is.

The four-cell example, by hand

Coarsen Reach's torus on one Workbench into its four quadrants. Two hundred draws of the raw learned sampler ($\lambda = 0$) fall $(100, 60, 30, 10)$, so $\hat p = (0.50, 0.30, 0.15, 0.05)$ against $u = (0.25, 0.25, 0.25, 0.25)$:

Equivalently $\ln 4 - H(\hat p)$; the check asserts the identity to $10^{-12}$. Now the aim. The same world's roadmap paths put their nodes at $p^* = (0.55, 0.30, 0.10, 0.05)$, and only two terms survive because the other two ratios are one:

The learned proposal is about $27\times$ closer to the path distribution than uniform is. Finally the floor: at $\lambda = 0.1$ the mixture is $p_\lambda = 0.9\,\hat p + 0.025 = (0.475, 0.295, 0.160, 0.070)$, whose smallest cell, $0.070$, is above $\lambda/4 = 0.025$ — Definition 22.2 holds, with room to spare, on the cell the raw sampler nearly ignored. The w22.1 bar chart runs this computation live on the current world.

Heuristics that overestimate

The three-node audit. A chain $a \xrightarrow{2} b \xrightarrow{2} c \xrightarrow{1} \text{goal}$ has true costs-to-go $h^* = (5.0, 3.0, 1.0)$, and a net outputs $\hat h = (4.6, 3.4, 0.8)$. The ratios are $\hat h/h^* = (0.92, 1.1333, 0.80)$: admissible at $a$ and $c$, violated at $b$, where $3.4 > 3.0$. Consistency fails at $b$ too, since $\hat h(b) = 3.4 > c(b, c) + \hat h(c) = 2.8$. So

The audit is one function, admissibility_audit, and the check asserts the violation set $\{b\}$, the inconsistency set $\{b\}$, $\epsilon$ and the bound.

The audit of the shipped heuristic. The net predicts $\ln(h^*/h_{oct})$, the factor by which obstacles stretch the empty-torus octile distance, so $\hat h = h_{oct}\,e^{\hat y}$ is inadmissible wherever the net guesses high. It was trained on 71,848 backward-Dijkstra labels from 240 worlds, with overestimates weighted six times in the squared loss. Auditing every reachable cell of 16 validation worlds, three goals each: 5,584 of 12,830 cells over, $\epsilon_{val} = 0.662$. On 16 held-out bar worlds, $\epsilon = 0.387$ — smaller: a sample maximum moves around. The check ch22 ε audit repeats this on eight fresh worlds ($\epsilon = 0.327$) and runs 43 searches: every one returned an optimal path. Derivation 3 is a ceiling, not a forecast.

Neural planners and what they inherit

The check ch22 proposal + verifier runs the planner on 16 queries, eight from each generator, drawn without asking whether they have an answer: 12 returned a path, all 12 passed an independent dense recheck at a step of 0.005 rad, and 4 queries went to the whole-query fallback. The network alone solved 0 of the 8 in-distribution queries and 4 of the 8 held-out ones. Eight queries are too few to say more than that the success rate without repair is not a number anyone should plan on.

Diffusion planners, at the level of statements

On 64 samples the toy diffuser produces 58% valid trajectories unguided — 30 swinging above the slab, 34 below — and 83% with guidance. Both numbers are high, both modes survive, and neither is one. That last fact is the entire practical content of the section.

What an honest benchmark is

For (iii) the Rust harness uses RRT*'s incumbent after ten seconds; the web port uses the shortest path any method found, including a dense reference PRM — weaker (1.0 means "as good as anything we tried"), but every ratio is at least one by construction, as ch22 Board invariants asserts.

The algorithm

Five boxes, one per learned component and one for the board. Each is a classical algorithm from an earlier chapter with one line replaced; the replaced line is marked.

Implementation in Rust

The learn crate trains with candle and infers without it. Training is native-only (candle-core and candle-nn build the networks, losses and optimizer); each trained network is exported to safetensors and evaluated by infer.rs, a forty-line forward pass on nalgebra, so the WebAssembly widgets and the native planner run identical arithmetic — a test asserts candle and infer.rs agree to $10^{-6}$ on a thousand inputs. The TypeScript port that runs this page goes one step further and hand-rolls a tiny MLP, backpropagation included, in lib/learn/mlp.ts — two layers, tanh, Adam — so the checks can train small networks from scratch (XOR, a one-dimensional function, the toy denoiser) and the whole story runs with no dependency. The check ch22 MLP backprop compares its gradients to central differences on three architectures; the worst relative discrepancy is $3 \times 10^{-8}$. The crate imports and never re-defines Chapter 11's Sampler, Hybrid, Uniform and Steer, Chapter 12's RrtConnect and Chapter 6's astar.

use nalgebra::{DMatrix, DVector};

/// A dense tanh MLP as exported from candle: layers (W, b), tanh between, linear out.
/// This is the *only* inference path — native planner, WASM widgets and the TS port agree.
pub struct MlpWeights { pub layers: Vec<(DMatrix<f32>, DVector<f32>)> }

impl MlpWeights {
    pub fn from_safetensors(bytes: &[u8]) -> Result<Self, LearnError> { /* names l0.w, l0.b, … */ }

    pub fn forward(&self, x: &DVector<f32>) -> DVector<f32> {
        let last = self.layers.len() - 1;
        self.layers.iter().enumerate().fold(x.clone(), |h, (i, (w, b))| {
            let z = w * h + b;
            if i == last { z } else { z.map(f32::tanh) }
        })
    }
}

pub fn softmax(z: &DVector<f32>) -> DVector<f64> {
    let m = z.max();                                   // shift: exp never overflows
    let e = z.map(|v| f64::from(v - m).exp());
    let s = e.sum();
    e / s
}

/// Counts on N cells and the two divergences of Derivation 2 (nats).
pub struct CoarseHistogram<const N: usize>(pub [u64; N]);

impl<const N: usize> CoarseHistogram<N> {
    pub fn probabilities(&self) -> [f64; N] {
        let t = self.0.iter().sum::<u64>() as f64;
        self.0.map(|c| c as f64 / t)
    }
    /// D_KL(p̂ ‖ u) = ln N − H(p̂): concentration, not aim.
    pub fn kl_to_uniform(&self) -> f64 {
        let u = [1.0 / N as f64; N];
        kl(&self.probabilities(), &u)
    }
    /// D_KL(target ‖ p̂): aim. Infinite if p̂ misses a cell the target uses — the failure that matters.
    pub fn kl_from(&self, target: &[f64; N]) -> f64 { kl(target, &self.probabilities()) }
    /// p_λ = (1 − λ) p̂ + λ u, cell by cell (Definition 22.2).
    pub fn mixture(&self, lambda: f64) -> [f64; N] {
        self.probabilities().map(|p| (1.0 - lambda) * p + lambda / N as f64)
    }
}

pub fn kl(p: &[f64], q: &[f64]) -> f64 {
    p.iter().zip(q).filter(|(pi, _)| **pi > 0.0).map(|(pi, qi)| {
        if *qi <= 0.0 { f64::INFINITY } else { pi * (pi / qi).ln() }       // 0 · ln 0 = 0
    }).sum()
}

The sampler is a categorical over a 12 × 12 coarsening of the torus, conditioned on the 8 × 8 raster and on $(\cos, \sin)$ of the four query angles — the wrap-aware encoding Chapter 5 recommends for $S^1$ factors. It implements Chapter 11's Sampler and nothing else; the free-space test inside sample is the one every other sampler runs. The safe version is not a new type: it is Chapter 11's Hybrid, and the constructor is where Derivation 1 is enforced.

use candle_core::{DType, Device, Tensor};
use candle_nn::{linear, loss::cross_entropy, AdamW, Module, Optimizer, ParamsAdamW, VarBuilder, VarMap};
use manifold::{Manifold, T2};
use rand::{rngs::SmallRng, Rng};
use sampling::{FreeSpace, Hybrid, Sampler, Uniform};
use crate::{encode::{query_features, EnvEncoding}, infer::{softmax, MlpWeights}, LearnError};

pub const CELLS_N: usize = 12;
pub const CELLS: usize = CELLS_N * CELLS_N;
type Q = <T2 as Manifold>::Point;

/// D22.1. The raw proposal p̂_θ(· | 𝓔, q_start, q_goal): draw a cell, then a uniform point in it.
pub struct LearnedSampler { probs: Vec<f64>, cdf: Vec<f64> }

impl LearnedSampler {
    /// One forward pass per query — the cell masses do not depend on the samples drawn.
    pub fn new(net: &MlpWeights, env: &EnvEncoding, start: &Q, goal: &Q) -> Self {
        let probs: Vec<f64> = softmax(&net.forward(&query_features(env, start, goal))).iter().copied().collect();
        let cdf = probs.iter().scan(0.0, |acc, p| { *acc += p; Some(*acc) }).collect();
        Self { probs, cdf }
    }
    pub fn draw_raw(&self, rng: &mut SmallRng) -> Q {
        let u: f64 = rng.random();
        let c = self.cdf.partition_point(|&f| f < u).min(CELLS - 1);
        let (i, j) = (c % CELLS_N, c / CELLS_N);
        let w = std::f64::consts::TAU / CELLS_N as f64;
        T2::from_angles([-std::f64::consts::PI + (i as f64 + rng.random::<f64>()) * w,
                         -std::f64::consts::PI + (j as f64 + rng.random::<f64>()) * w])
    }
}

impl Sampler<T2> for LearnedSampler {
    fn sample(&mut self, _: &T2, free: &dyn FreeSpace<T2>, rng: &mut SmallRng) -> Option<Q> {
        let q = self.draw_raw(rng);
        free.is_free(&q).then_some(q)                  // the verifier is Chapter 11's, untouched
    }
}

/// D22.2 by construction: Chapter 11's `Hybrid` with `Uniform` as the floor at weight λ.
/// Derivation 1 needs λ > 0, so λ = 0 is an error here, not a warning in a README.
pub fn safe_learned_sampler(learned: LearnedSampler, lambda: f64) -> Result<Hybrid<T2>, LearnError> {
    if !(lambda > 0.0 && lambda <= 1.0) { return Err(LearnError::NoUniformFloor(lambda)); }
    Ok(Hybrid { parts: vec![(Box::new(learned), 1.0 - lambda), (Box::new(Uniform), lambda)] })
}

/// Maximum likelihood on path-node cells = min D_KL(p* ‖ p̂_θ) (Derivation 2). Native only.
pub fn train_sampler(x: &[Vec<f32>], cells: &[u32], epochs: usize) -> candle_core::Result<VarMap> {
    let dev = Device::Cpu;
    let vars = VarMap::new();
    let vb = VarBuilder::from_varmap(&vars, DType::F32, &dev);
    let (l0, l1) = (linear(x[0].len(), 64, vb.pp("l0"))?, linear(64, CELLS, vb.pp("l1"))?);
    let mut opt = AdamW::new(vars.all_vars(), ParamsAdamW { lr: 2e-3, ..Default::default() })?;
    let xs = Tensor::from_vec(x.concat(), (x.len(), x[0].len()), &dev)?;
    let ys = Tensor::from_slice(cells, cells.len(), &dev)?;
    for _ in 0..epochs {
        let logits = l1.forward(&l0.forward(&xs)?.tanh()?)?;
        opt.backward_step(&cross_entropy(&logits, &ys)?)?;   // full batch for brevity; the crate mini-batches
    }
    Ok(vars)                                                  // → safetensors → MlpWeights
}

The heuristic is a closure, because that is all Chapter 6's astar ever asked of a heuristic. The $\epsilon$ is a field that starts as None and is filled only by an audit — the type makes it impossible to quote a bound that was never measured.

use search::{astar, Trace};
use cspace::TorusGrid;                                // Ch. 4's raster, 8-connected with wraparound
use crate::{encode::{heuristic_features, EnvEncoding}, infer::MlpWeights};

/// Learned cost-to-go. ĥ = h_oct · exp(ŷ): at least the admissible baseline where ŷ ≥ 0.
pub struct HeuristicNet<'a> { net: &'a MlpWeights, env: &'a EnvEncoding, grid: &'a TorusGrid,
                              goal: usize, pub epsilon: Option<f64> }

impl HeuristicNet<'_> {
    pub fn h(&self, v: usize) -> f64 {
        let base = self.grid.octile(v, self.goal);
        if base == 0.0 { return 0.0; }
        let y = self.net.forward(&heuristic_features(self.env, self.grid, v, self.goal))[0];
        base * f64::from(y).clamp(-1.0, 3.0).exp()   // clamp: one wild guess cannot overflow
    }
}

/// Derivation 3's hypothesis, measured: max over every reachable cell of ĥ/h* − 1.
pub fn measure_epsilon(h: &HeuristicNet, h_star: &[f64]) -> (f64, usize) {
    h_star.iter().enumerate()
        .filter(|(_, hs)| hs.is_finite() && **hs > 0.0)
        .fold((0.0, 0), |(eps, over), (v, hs)| {
            let r = h.h(v) / hs;
            if r > 1.0 + 1e-9 { (eps.max(r - 1.0), over + 1) } else { (eps, over) }
        })
}

/// Ch. 6's A*, which reopens; the bound below is Derivation 3 and holds only where ε was audited.
pub fn a_star_eps(grid: &TorusGrid, s: usize, g: usize, h: &HeuristicNet) -> Option<(Trace<usize>, f64)> {
    let eps = h.epsilon.expect("measure ε before quoting a bound");
    let t = astar(grid, s, g, |v| h.h(v))?;
    let bound = (1.0 + eps) * grid.cost_to_go(g)[s];
    debug_assert!(t.cost <= bound + 1e-9, "Derivation 3 violated on an audited world");
    Some((t, bound))
}

pub struct Audit { pub ratios: Vec<f64>, pub violated: Vec<char>, pub inconsistent: Vec<char>,
                   pub epsilon: f64, pub bound: f64 }

/// §3(b): a chain v₀ → v₁ → … → goal with edge costs c; both heuristics are 0 at the goal.
pub fn admissibility_audit(labels: &[char], h_star: &[f64], h_hat: &[f64], c: &[f64]) -> Audit {
    let ratios: Vec<f64> = h_hat.iter().zip(h_star).map(|(a, b)| a / b).collect();
    let violated = labels.iter().zip(&ratios).filter(|(_, r)| **r > 1.0 + 1e-12).map(|(l, _)| *l).collect();
    let inconsistent = (0..labels.len())
        .filter(|&i| h_hat[i] > c[i] + h_hat.get(i + 1).copied().unwrap_or(0.0) + 1e-12)
        .map(|i| labels[i]).collect();
    let epsilon = (ratios.iter().copied().fold(f64::MIN, f64::max) - 1.0).max(0.0);
    Audit { ratios, violated, inconsistent, epsilon, bound: (1.0 + epsilon) * h_star[0] }
}

The neural planner holds its repair planner as a field, not an Option: Derivation 4 says the guarantee lives there, and a planner without one has only a success rate.

use manifold::T2;
use rand::{rngs::SmallRng, Rng};
use sampling::{tree::{Extend, RrtConnect}, FreeSpace, Steer};
use crate::{encode::EnvEncoding, infer::MlpWeights, Q};

pub struct MpnetLike<E: Extend<T2>> { policy: MlpWeights, env: EnvEncoding, repair: E,
                                      eta: f64, max_hops: usize, local: usize, fallback: usize }

pub struct NeuralPlan { pub waypoints: Vec<Q>, pub hops_ok: Vec<bool>,
                        pub fell_back: bool, pub path: Option<Vec<Q>> }

impl<E: Extend<T2> + Clone> MpnetLike<E> {
    pub fn plan(&self, free: &dyn FreeSpace<T2>, s: &Q, g: &Q, rng: &mut SmallRng) -> NeuralPlan {
        // D22.1: ≤ max_hops of q + η·tanh(π_θ), re-proposed with jitter where the endpoint collides.
        let waypoints = self.propose(free, s, g, rng);
        let hops_ok: Vec<bool> = waypoints.windows(2)          // the verifier, one hop at a time
            .map(|w| self.repair.steer(&T2, free, &w[0], &w[1]).is_some()).collect();
        let mut out = vec![*s];
        let (mut i, mut failed) = (0, false);
        let last = waypoints.len() - 1;
        while i < last {
            if hops_ok[i] { out.push(waypoints[i + 1]); i += 1; continue; }
            let j = (i + 1..last).find(|&j| free.is_free(&waypoints[j])).unwrap_or(last);
            match self.connect(free, &waypoints[i], &waypoints[j], self.local, rng) {
                Some(bridge) => { out.extend_from_slice(&bridge[1..]); i = j; }
                None => { failed = true; break; }
            }
        }
        // Derivation 4: the last resort answers the *original* query, so its guarantee is ours.
        let (path, fell_back) = if failed { (self.connect(free, s, g, self.fallback, rng), true) }
                                else { (Some(out), false) };
        let path = path.filter(|p| p.windows(2).all(|w| self.repair.steer(&T2, free, &w[0], &w[1]).is_some()));
        NeuralPlan { waypoints, hops_ok, fell_back, path }
    }

    fn connect(&self, free: &dyn FreeSpace<T2>, a: &Q, b: &Q, iters: usize, rng: &mut SmallRng) -> Option<Vec<Q>> {
        RrtConnect::new(T2, a.clone(), b.clone(), self.repair.clone(), self.eta, rng.random()).merge(free, iters)
    }
}

The worked example prints the two micro-examples exactly — they are arithmetic, and the test asserts them — and then trains on randomized Workbenches.

use learn::{admissibility_audit, data, CoarseHistogram};

fn main() -> anyhow::Result<()> {
    // §3(a): 200 raw draws on four quadrants of one Workbench's torus.
    let hat = CoarseHistogram([100u64, 60, 30, 10]);
    let target = [0.55, 0.30, 0.10, 0.05];
    println!("counts {:?}  KL(p_hat||u) = {:.4} nats ({:.3} bits)  KL(p*||p_hat) = {:.4}  KL(p*||u) = {:.4}",
             hat.0, hat.kl_to_uniform(), hat.kl_to_uniform() / std::f64::consts::LN_2,
             hat.kl_from(&target), learn::kl(&target, &[0.25; 4]));
    println!("p_lambda(0.1) = {:.3?}", hat.mixture(0.1));

    // §3(b): a →2→ b →2→ c →1→ goal.
    let a = admissibility_audit(&['a', 'b', 'c'], &[5.0, 3.0, 1.0], &[4.6, 3.4, 0.8], &[2.0, 2.0, 1.0]);
    println!("h* [5.0 3.0 1.0]  h_hat [4.6 3.4 0.8]  violated {:?}  inconsistent {:?}  epsilon {:.4}  bound {:.3}",
             a.violated, a.inconsistent, a.epsilon, a.bound);

    // The pipeline: 600 random Workbenches × 3 queries → paths → sampler, policy; Dijkstra → heuristic.
    let seed = std::env::args().skip_while(|a| a != "--seed").nth(1).map_or(Ok(7), |s| s.parse())?;
    let ds = data::generate_dataset(data::Generator::Blocks, 600, 3, seed);
    println!("{}/{} PRM queries solved · {} sampler targets · {} policy targets",
             ds.solved, ds.attempted, ds.sampler.len(), ds.policy.len());
    Ok(())
}

counts [100, 60, 30, 10]  KL(p_hat||u) = 0.2442 nats (0.352 bits)  KL(p*||p_hat) = 0.0119  KL(p*||u) = 0.3162
p_lambda(0.1) = [0.475, 0.295, 0.160, 0.070]
h* [5.0 3.0 1.0]  h_hat [4.6 3.4 0.8]  violated ['b']  inconsistent ['b']  epsilon 0.1333  bound 5.667
954/1800 PRM queries solved · 21508 sampler targets · 44553 policy targets

The first three lines are exact and are what the tests below assert. The last is the TypeScript port's run of the same pipeline (lib/learn/__train__.ts, seed 7), which the page's numbers come from; a Rust run reproduces the pattern, not the digits, because the random streams differ. As recorded there: the sampler's cross-entropy fell to 3.393 nats in 50 epochs (uniform: 4.970); generating the paths took 147 s and training the sampler 93 s — 241 s in all, the number the Board amortizes.

use learn::*;

#[test]
fn kl_four_cell_matches_hand_computation() {
    let h = CoarseHistogram([100u64, 60, 30, 10]);
    assert!((h.kl_to_uniform() - 0.2442).abs() < 1e-4);
    let entropy = -h.probabilities().iter().map(|p| p * p.ln()).sum::<f64>();
    assert!((h.kl_to_uniform() - (4f64.ln() - entropy)).abs() < 1e-12);       // ln N − H(p̂)
    assert!((h.kl_from(&[0.55, 0.30, 0.10, 0.05]) - 0.0119).abs() < 1e-4);
}

#[test]
fn eps_admissibility_three_nodes() {
    let a = admissibility_audit(&['a', 'b', 'c'], &[5.0, 3.0, 1.0], &[4.6, 3.4, 0.8], &[2.0, 2.0, 1.0]);
    assert_eq!(a.violated, vec!['b']);
    assert_eq!(a.inconsistent, vec!['b']);
    assert!((a.epsilon - 0.13333).abs() < 1e-4 && (a.bound - 5.6667).abs() < 1e-3);
}

#[test]
fn mixture_never_below_lambda_uniform() {
    let h = CoarseHistogram([100u64, 60, 30, 10]);
    for lambda in [0.05, 0.1, 0.3] { assert!(h.mixture(lambda).iter().all(|&m| m >= lambda / 4.0 - 1e-12)); }
    assert!(safe_learned_sampler(LearnedSampler::uniform_stub(), 0.0).is_err());
}

The crate's fourth test, a_star_eps_cost_within_bound, runs Derivation 3 as a property on 500 seeded lattices with $\hat h = h^*(1 + 0.3\,r)$, $r \sim U[0, 1]$. The web port's checks are the same tests in TypeScript — its property test saw a worst realized ratio of 1.0711 over 30 searches, with 13 reopenings — plus the mixture floor with 100,000 empirical draws, the $\epsilon$ audit, the proposal-plus-verifier recheck, the toy diffuser, and the Board's invariants.

Putting it together: reading the board

The integration lab is the Honest Benchmark Board above, read the way Definition 22.6 says to: thirty solvable queries per suite, from the training generator (axis-aligned blocks, like the real Workbench's block, post and shelf) and the held-out one (thin bars at arbitrary angles), budgets from 100 to 12,800 collision checks, the same world, query and seed for every planner.

Success at budget. In distribution, at 100 checks, the learned sampler at $\lambda = 0.1$ solves 60% against uniform's 47%; RRT-Connect solves 57%. At 400 checks the learned sampler has fallen behind: 77% against uniform's 90%, the bridge sampler's 80% and RRT-Connect's 93%. That shape — ahead early, behind later — is Derivation 2's cap in action. When the proposal aims right, it hits the corridor sooner than uniform; when it aims wrong, only the $\lambda$ floor keeps it searching, at up to ten times uniform's waiting time, and by 400 checks those queries are what the column counts. At 12,800 checks the learned and uniform rows both solve every query in both suites — Derivation 1, on the board.

The held-out suite. We expected the learned sampler to lose its edge on the other generator. At $\lambda = 0.1$ it did not lose more than it had: held-out at 100 checks it solves 63% against uniform's 60%, and at 400 checks both solve 90% (bridge 80%, RRT-Connect 100%). Single worlds show the reversal — w22.1's default held-out seed costs the learner more than twice uniform's checks — but over thirty queries the bars were not harder for it than the blocks. Thirty queries is a small suite, and "did not degrade on one other generator" is not "generalizes".

Path cost. The learned sampler's first paths are consistently shorter: 1.28 times the incumbent in distribution against uniform's 1.33, and 1.23 against 1.43 held-out. That is Derivation 2's aim paying off in a currency nobody optimized for — the targets were nodes on shortest roadmap paths, so the proposal concentrates where short paths go. RRT-Connect, at 1.07 in distribution, beats every PRM row on cost as well.

Wall-clock. Here the learned row loses outright. A query's forward pass costs about 0.10 ms, so inference is not what makes the learned PRM's mean wall-clock in distribution 12 ms against uniform's 10 ms; the difference is in the planning loop itself. Amortizing the 241 s of data generation and training over $k$ queries can only make that worse, and the break-even against uniform is never. The MPNet-style planner pays 1.1 ms of inference per query and 53 ms of wall-clock, most of it in repairs, and reaches 93% at the full budget in both suites; on the remaining queries the fallback either ran out of iterations or overran the check budget.

What a fair reading concludes. On Reach's two-dimensional torus, with these small networks, a learned proposal buys a better first path and a head start at the smallest budgets, and it costs wall-clock and four minutes of offline work before the first query. A hand-designed single-query planner, RRT-Connect, is better than all of it. None of that is a verdict on learning in planning — the literature's wins are in seven-dimensional arms and repeated queries on similar scenes, where uniform sampling is hopeless and a training run is amortized over many queries — but it is a verdict on this setting, and the board's purpose is that such verdicts are possible at all.

What is principled, and what is still alchemy

The chapter closes with a ledger, because the field needs one more than it needs another leaderboard.

Principled. Any completeness-preserving proposal keeps Choset's guarantee with its constant multiplied by $\lambda$ (Derivation 1), and a constructor that refuses $\lambda = 0$ makes that a property of the code. Maximum-likelihood training of a sampler is minimization of the forward KL divergence from the path distribution (Derivation 2), so "the sampler is aimed well" has a definition and a number. A heuristic's overestimate bounds the path cost exactly (Derivation 3), provided $\epsilon$ is measured, and provided one says aloud that a validation $\epsilon$ is a guarantee on the validation worlds and an estimate elsewhere — on this chapter's worlds the held-out $\epsilon$ happened to be smaller than the validation one, which is luck, not a law. A proposal behind a sound verifier and a fallback on the original query inherits the fallback's guarantee (Derivation 4). And a benchmark that includes inference time, training time and held-out worlds (Definition 22.6) can falsify a claim, which is the only kind of benchmark worth running.

Still alchemy in 2026. Generalization across world generators: our held-out suite is one other generator, and no theorem says what the next one does. Validation $\epsilon$ as a deployment guarantee: it is not one. Neural planners' success rates without repair: an empirical rate on a distribution of worlds, and the check that runs the net alone saw 0 of 8 in one suite and 4 of 8 in the other. Diffusion guidance through a non-differentiable constraint: collision is a set, not a cost; guidance raised the toy's valid fraction from 58% to 83% and no setting makes it one. The circularity: the sampler is trained on paths from the very PRM it is benchmarked against, so at best it reproduces PRM-with-a-large-budget, faster — it cannot find a passage the teacher never found. And amortization: a training run is paid for only by enough queries on similar worlds, and on this board the break-even never arrives.

Chapter 23's planning stack will carry a "learned sampler" toggle in Reach's panel, wired through exactly the Hybrid constructor above, and cite this board in its retrospective. The sister book's Chapter 25 applies the same principled-or-alchemy discipline to learning inside an estimator, where the verifier is a likelihood rather than a collision checker and the inheritance argument has a different shape.

Exercises

1. Foundation exerciseFDifficulty 2 of 3λ through the whole of Chapter 11

   Carry $\lambda$ through Chapter 11's $(\epsilon, \alpha, \beta)$-expansiveness proof (Theorem 7.4.2), not only through the tiling bound of Derivation 1. Every volume in that proof is a uniform measure of a reach set or a lookout; under $p_\lambda$ each is bounded below by $\lambda$ times itself. Name the constant of the theorem that absorbs the change. Then show that a proposal with $\hat p(A) = 0$ on one tile $A$ makes the failure probability of Derivation 1 bounded below by a positive constant independent of $n$.

   Chapter 11's ball-tiling example (path length 1.2, clearance 0.1, unit square) needs 892 uniform samples for an exponential-form failure bound of 1%. With the same tiles and a mixture at λ = 0.1, how many samples does the same bound require?

   Check Reveal

   Stuck? Get a hint
2. Foundation exerciseFDifficulty 2 of 3The additive bound, and A* without reopening

   Prove the additive form of Derivation 3: if $\hat h \le h^* + \delta$ everywhere, A* with reopening returns $C \le C^* + \delta$. Then build a four-node graph — start, two intermediate nodes, goal — with an admissible but inconsistent heuristic on which A* without reopening returns a suboptimal path, and explain which step of the derivation breaks.

   Stuck? Get a hint
3. Conceptual exerciseCDifficulty 1 of 3Predict the held-out sampler, then verify
   Predict first

   In Learned Sampler vs Uniform, set λ to its minimum, 0.02, and switch to the held-out generator. Before pressing play: across the seeds the success-at-budget curve accumulates, what happens to the learned curve compared with uniform's at the largest budgets?

   It never reaches uniform's level — with a tiny floor some held-out queries stay unsolved

   It reaches the same level, later on the worlds where the net aims wrong

   It is identical to uniform's — the net is useless on worlds it never saw
4. Conceptual exerciseCDifficulty 2 of 3The deflated heuristic
   Predict first

   In Heuristic Calibration, switch from the learned ĥ to ĥ / (1 + ε_val), with ε_val = 0.662 from the validation worlds. Compared with the admissible octile heuristic, the deflated one will expand…

   Fewer nodes — it is the learned heuristic made safe

   About as many nodes

   Several times as many nodes, and return an optimal path
5. Practical exercisePDifficulty 2 of 3A learned sampler for Rusty

   Implement Sampler on Rusty's $\mathbb{R}^2$ configurations in the Apartment for a LearnedSampler conditioned on a $64 \times 64$ occupancy raster, trained on 500 randomized floorplans (move interior walls and doorways; keep the outer walls). Wrap it with safe_learned_sampler and add its row to the Board, with a held-out generator that moves doors to walls the training generator never opened. Does the held-out gap shrink or grow with the larger raster? Report success at three budgets and the break-even $k$, and say which of the two you believe more.

6. Practical exercisePDifficulty 3 of 3Stretch: a learned heuristic for hybrid A*

   Train a heuristic for Chapter 21's hybrid A* on the Lot, with labels from backward Dijkstra on the $(x, y, \theta)$ lattice for Hitch. Measure $\epsilon$ on held-out Lots (different parking-row layouts) with measure_epsilon, run the planner, and compare the realized cost ratio to the bound $(1 + \epsilon)$ and to the classical $\max(h_{RS}, h_{holonomic})$ — the Reeds–Shepp distance and the obstacle-aware 2-D distance. Which of the three heuristics expands the fewest nodes, and which would you ship?