Certified Edges for Learned Motion Graphs: Calibrating Plans Where the Planner Chooses Them

A motion graph turns a hard continuous planning problem into a search over a network. Each node is a short motion snippet, such as a turn, a hop, or a landing. Each edge says that one snippet can safely follow another. Graphs built this way now drive real robots: a quadruped can plan a recovery from a 0.5-meter drop in under 50 ms (Robust Locomotion on Legged Robots through Planning on Motion Primitive Graphs). The weak point is the edge. In practice, edges are either checked by expensive simulation or predicted cheaply by a learned model. A learned model works naturally in a latent space, meaning a compressed, learned coordinate system in which nearby snippets behave alike. These predicted edges are then evaluated on a handful of hand-built scenes. We propose to give learned motion graphs a statistical certificate that survives the planner's own choices. The method accepts a plan only when a calibrated score says it will succeed with probability at least $1-\alpha$ under real execution noise. The certificate is validated on hundreds of procedurally generated problems rather than five or ten.

The core observation is that a planner searching over predicted edges does not sample edges at random. It deliberately picks the edges the predictor is most optimistic about, so per-edge error rates measured on random edges understate how often the chosen path fails. This is a planning-specific version of the winner's curse. It is also exactly the kind of gap between a stated guarantee and deployed behavior that the empirical-validation literature keeps finding. We fix it by calibrating the whole plan-then-execute pipeline at the level of tasks, not edges. The same pipeline also produces a measurement study: how often published-style small evaluations of graph planners would have ranked methods wrongly.

Core Claim

Fix the planning procedure $\pi$: latent encoder, edge predictor, graph search, and any internal replanning. Draw tasks independently from a task distribution. Then $\pi$'s output on each task is a deterministic function of that task. Its execution outcomes on calibration tasks are therefore exchangeable with its outcome on a new task, which is the condition conformal prediction needs. Conformal prediction is a distribution-free method that turns held-out errors into finite-sample guarantees.

For each returned plan, $\pi$ emits a score $s$, for example the minimum predicted edge margin along the path. From $n$ calibration tasks with observed execution outcomes, we choose the smallest threshold $\tau$ such that

$$\Pr\big(\text{execution fails} \mid s \ge \tau\big) \le \alpha,$$

where $\alpha$ is the user's tolerated failure rate among accepted plans. The threshold is chosen with a finite-sample upper confidence bound on the failure rate among calibration plans scoring above $\tau$. Plans below threshold trigger abstention or a fallback such as verified replanning.

This guarantee holds no matter how the planner chooses paths, because the choice happens inside $\pi$. It also avoids the union bound over path edges. A union bound makes per-edge certificates shrink as $\alpha/k$ for a $k$-edge path, which mirrors the horizon-dependent conservatism reported for conformal MPC in Safe Planning in Dynamic Environments Using Conformal Prediction.

The claim we will test is threefold. First, edge-level calibration of a learned latent edge model is measurably violated once a planner selects paths. Second, task-level calibration restores the target rate. Third, it does so while accepting far more plans than per-edge certification at the same rollout budget.

Relation to Prior Work

Three lines of work motivate the gap. The safety oracles of Verifying Safe Transitions between Dynamic Motion Primitives on Legged Robots and its follow-up classify transitions using regions of attraction checked in simulation. The test is sufficient but not necessary, so valid edges get pruned. It also assumes a nominal, disturbance-free model. We keep their primitive-graph structure but replace a conservative yes/no test with a calibrated probability that accounts for disturbances.

Discontinuity-bounded search, in db-A* and iDb-RRT, lets primitives join with small gaps and repairs the result by trajectory optimization. The output is dynamically feasible under the nominal model, but it is validated only in noise-free simulation. These methods supply our strongest baseline and our benchmark systems. They do not learn latent edges or certify execution under noise.

MotionBenchMaker shows that comparisons on 5 to 10 problems produce rankings that invert at 100 problems. It also shows that sensed obstacle maps break planners tuned on clean meshes. We adopt its methodology: procedural scene sampling, sensed-map variants, and 100+ verified problems. MotionBenchMaker itself is kinematic and contains no motion graphs.

Conformal prediction for planning (Safe Planning in Dynamic Environments Using Conformal Prediction) supplies the statistical tool. That work calibrates trajectory predictions of other agents inside a continuous MPC and reports 498 of 500 test trajectories covered. It does not involve graphs, and it calibrates a predictor rather than a planner's own selected output. We move calibration from the predictor to the full planning procedure, which is what makes the guarantee robust to selection.

On the latent side, Bringing Motion Taxonomies to Continuous Domains via GPLVM on Hyperbolic manifolds shows that latent geometry matters for interpolation: jerkiness was 27.15 for hyperbolic versus 210.08 for Euclidean interpolation. Its evaluation is offline and kinematic. Dynobench primitives are not obviously hierarchical, so we treat latent geometry as a secondary ablation rather than the core.

Research Program

We build the graph from primitive libraries of the kind used in iDb-RRT. An encoder maps each primitive's state trajectory to a latent vector. An edge predictor takes the pair of latent codes, plus the relative state gap and local obstacle features. It outputs the probability that executing primitive A then primitive B succeeds under closed-loop tracking with process noise, model-parameter perturbation, and obstacle maps built from simulated depth sensing.

The predictor is trained on a budget of simulated rollouts on sampled edge pairs. Its purpose is to avoid exhaustively simulating the quadratically many edges. Search runs A* over predicted edges with a cost penalizing low predicted margin. The returned plan is executed in the noisy simulator, and its outcome is recorded.

The research has three parts. The first measures selection bias: we compare the predictor's failure rate on uniformly sampled edges with its failure rate on edges the planner actually selects, across noise levels and library sizes. The second implements task-level calibration with abstention and checks its coverage on held-out tasks. The third is a ranking-stability study. For every pair of methods, we estimate how often a ranking computed from a random 10-task subset disagrees with the ranking computed on 500 tasks. This quantifies the wrong-hypotheses risk specifically for motion-graph planners.

Baselines

The naive reference point plans on the learned latent graph and accepts every returned plan. It reports the predictor's nominal edge confidence as if it were a success probability. Success means its realized failure rate on held-out noisy executions matches the claimed rate. We expect it not to, and the size of the mismatch is itself a result.

The strongest existing method is iDb-RRT-C. According to iDb-RRT, it was the fastest planner on 19 of 30 Dynobench problems, reached nearly 100% success, and was 10 to 20 times faster than iDb-A* in complex scenes. Those figures are for nominal, noise-free feasibility. For execution success under noise, no reported result was found on Lacuna. We run it on the same tasks, the same noisy executor, the same tracking controller, and the same wall-clock budget. We give it a matched tuning budget, including an obstacle-inflation margin tuned on the calibration split. Our method beats it if, at equal compute, it achieves a higher fraction of tasks that are both accepted and successful, while keeping failure among accepted plans at or below $\alpha$. iDb-RRT has no abstention mechanism, so we compare against its raw failure rate and against iDb-RRT wrapped in the same task-level calibration on its own cost score.

The exhaustive per-edge baseline simulates every candidate edge with Monte Carlo rollouts. It assigns each edge a Clopper–Pearson upper bound on failure and plans only over edges whose bound passes $\alpha/k$. It uses the same total rollout budget we spend on predictor training plus calibration. It is the honest stand-in for a statistical version of the Ubellacker oracle. We also run a deterministic sufficient-only oracle in that style, which checks nominal rollouts against a contraction margin, to quantify spurious pruning.

The key ablation keeps our learned predictor and graph search but calibrates at the edge level, on random held-out edges, instead of at the task level. If this ablation matches our coverage, selection bias is not real in this regime and the core claim fails. A second ablation replaces latent codes with raw endpoint-state features. A third swaps a Euclidean latent for a hyperbolic one.

Why not just…?

Why not just simulate every edge and use binomial confidence bounds? This is the strongest alternative, and for small libraries it may win outright. Its costs grow with the number of edges times the rollouts per edge. The union bound over a $k$-edge path also forces per-edge thresholds of $\alpha/k$, which prunes heavily on long plans. The same horizon effect makes conformal MPC infeasible over long horizons in Safe Planning in Dynamic Environments Using Conformal Prediction. We vary library size at a fixed rollout budget and report the crossover point. If exhaustive certification dominates at every library size we can afford, we will say so.

Why not just run iDb-RRT and trust trajectory optimization? Repair by differential dynamic programming guarantees nominal feasibility, not robustness to disturbances or sensed-map errors. MotionBenchMaker found exactly this failure mode when moving from meshes to sensed maps (MotionBenchMaker). Our noisy-execution benchmark measures how much of iDb-RRT's nominal near-100% success survives. If inflating obstacles closes the gap, the useful contribution reduces to wrapping iDb-RRT in task-level calibration, and we report that outcome as such.

Why not just report success on a large held-out test set? A held-out binomial estimate gives a marginal success rate for the whole method. It does not tell the robot, at query time, whether this particular plan is trustworthy. The selective threshold on $s$ does: it lets the system abstain or fall back on low-confidence queries. That is valuable only if scores discriminate. We therefore report how acceptance rate trades against failure rate, and compare against a score-free method that accepts all plans at the marginal rate.

Proposed Experiments

The benchmark extends the Dynobench systems (unicycle, car with trailer, quadrotor) with bugtrap, kink, and narrow-window maps. Following MotionBenchMaker, maps are procedurally sampled to 500 verified tasks per system. Each task has a clean-geometry version and a sensed-map version, and execution includes process noise and mass/inertia perturbation. Tasks are split into training, calibration, and test sets. The splits are disjoint and separated by scene seed.

Metrics are as follows. The first is realized failure rate among accepted test plans versus target $\alpha \in \{0.05, 0.1\}$, with Clopper–Pearson intervals. The second is acceptance rate, meaning the fraction of tasks certified. The third is accepted-and-successful rate at matched wall-clock time. The fourth is the selection-bias gap: failure on selected edges minus failure on random edges. The fifth is ranking-inversion probability under 10-task subsampling.

The decisive checks are three. First, edge-level calibration must exceed $\alpha$ on planner-selected paths while task-level calibration does not. If both are calibrated, the selection-bias claim is falsified. Second, at a matched rollout budget, our method must accept more tasks than exhaustive per-edge certification on the largest library. Third, the sensed-map condition must show nonzero ranking inversions among the baselines at 10 tasks. That would confirm that the evaluation protocol, not only the method, changes conclusions for motion-graph planners.