A robot that copies human demonstrations can only be as good as its demonstrators. Offline value learning gets past this limit by "stitching": it joins the good half of one flawed demonstration to the good half of another, producing routes nobody actually drove. The catch is that every stitch is a move nobody performed, and today nothing checks that it is physically safe. Checking such moves the usual way, by testing the robot's geometry against obstacles at many small time steps along each candidate move, is also the dominant cost in motion planning. We propose to certify stitches with a mathematical proof instead of a dense geometric search. A safety condition proven once, offline, in a theorem prover reduces the safety of a whole continuous-time move to one inequality per control cycle. That certificate then decides which stitches the value learner may use and which recorded demonstrator actions count as mistakes.
In two sentences: we take a closed-form braking-distance invariant, already proven correct for mobile robots under acceleration bounds and sensor delay, and use it as a cheap, sound edge validator inside offline trajectory stitching. The learner can exceed suboptimal demonstrators, every stitched transition it relies on comes with a proof-backed safety guarantee, and the planner does far fewer obstacle queries than discretized collision checking.
Core Claim
Formal verification of obstacle avoidance and navigation of ground robots used differential dynamic logic (a proof system for programs that mix discrete control decisions with continuous physics) in the KeYmaera X prover to verify ground-robot obstacle avoidance under actuator disturbance and sensor delay. Its static safety result says that if, at the start of every control cycle, the following holds, then no collision occurs during the continuous motion until the next cycle, for any controller that respects the acceleration and braking bounds:
$$\|p - o\|_{\infty} > \frac{s^2}{2b} + \left(\frac{A}{b} + 1\right)\left(\frac{A}{2}\epsilon^2 + \epsilon s\right)$$
Here $p$ is robot position, $o$ the nearest obstacle point, $s$ speed, $b$ guaranteed braking deceleration, $A$ maximum acceleration, and $\epsilon$ the maximum cycle duration. That paper used the invariant to verify hand-designed controllers and to build runtime monitors. It never used it as a learning signal or as a planning primitive.
Our claim is that this invariant can serve as an edge validator for offline stitching, and that it does three jobs a plain geometric check cannot.
First, it is sound in continuous time with one nearest-obstacle query per cycle. Discretized collision checking is unsound between samples and needs many intersection tests per edge. The collision-checking literature motivates this choice: up to 99% of planning time goes to such checks (Robot Motion Planning on a Chip).
Second, it covers dynamics, not just geometry. A stitch can pass through free space and still be unsafe, because the robot arrives too fast to stop before an obstacle that appears in the next segment. A pure geometric check misses this.
Third, it gives a principled, reward-free label for demonstrator mistakes. A recorded transition that leaves the certified envelope is a mistake, whatever the demonstrator intended.
The value learner then stitches only over certified transitions. Its value estimates therefore reflect only moves that will actually be allowed at run time.
The scope is deliberately low-dimensional: planar point-mass and mobile-robot navigation, where the proof exists. Quantifier elimination, the decision procedure provers use for real arithmetic, is doubly exponential in the number of variables (Combining Deduction and Algebraic Constraints for Hybrid System Analysis). We do not claim to reach 7-DoF arms, and we treat high-dimensional extension as out of scope.
Research Program
The first component is fitting the model to the simulator and checking that the fit holds. We pick $A$, $b$ and $\epsilon$ for each environment from the actuator limits and control rate. We then run a model-compliance monitor in the style of ModelPlex over every recorded transition, flagging any transition whose observed state change is not explained by the verified hybrid model. This step matters because the proof only transfers if the simulator stays inside the model's allowed nondeterminism. We report the fraction of compliant transitions as a first-class result rather than assuming it.
The second component labels demonstrator mistakes. Each recorded transition receives a binary certified/uncertified label from the invariant. Uncertified transitions are excluded from the behavior-cloning target, and they are also excluded as stitching anchors. This replaces the learned confidence scores of Confidence-Aware Imitation Learning from Demonstrations with Varying Optimality and the learned per-demonstrator expertise of Imitation Learning by Estimating Expertise of Demonstrators with a physical criterion, but only for the safety dimension of quality. Inefficiency is still handled by value.
The third component builds a certified stitching graph. Nodes are demonstration states. Candidate edges join nearby states drawn from different demonstrations. An edge is admitted only if a short sequence of controls within the bounds connects the two states, found by a small trajectory search, and the invariant holds at every cycle start along it. We count obstacle-distance queries per admitted edge and compare them against the number of intersection tests a discretized checker needs at matched resolution.
The fourth component learns a policy past the ceiling. On the union of certified recorded transitions and certified stitch edges, we train an offline value function. We then extract a policy by advantage-weighted behavior cloning in the style of Exponentially Weighted Imitation Learning for Batched Historical Data: each certified state-action target is weighted by the exponential of its estimated advantage. That paper names misestimated advantages as a failure mode, and certification limits it in one specific way: the value function never assigns credit to a stitch that would later be vetoed. Stitch edges are taught to the policy as synthetic action targets.
At deployment, the same invariant runs as a runtime monitor with a verified braking fallback. Safety therefore holds even when the network acts off-graph, and we measure how often that fallback fires.
Baselines
The naive reference point is behavior cloning on all demonstrations, plus a filtered variant that drops any trajectory containing a collision. This represents "just clean the data." IRIS shows this kind of approach collapses when the data contain fumbles: behavior cloning reached 13.7% success on Robosuite Lift against 81.3% for IRIS. That number comes from manipulation, not our navigation benchmarks, so we re-run behavior cloning on our own data rather than borrowing the figure.
The strongest existing method for stitching from flawed data is IRIS itself. It has a low-level behavior-cloned controller, a high-level goal proposer, and a batch-constrained value function that selects among reachable subgoals. We also include conservative Q-learning, which D4RL (D4RL: Datasets for Deep Data-Driven Reinforcement Learning) identifies as the strongest performer on its stitching tasks; no reported Maze2D number was found on Lacuna for it.
For learning from explicitly bad data we include DualCOIL (DualCOIL: Offline Imitation Learning from Contrasting Demonstrations), which pulls the policy toward expert data and pushes it away from bad trajectories. We feed it the colliding demonstrations as its "bad" set. It reports a 94.1 average normalized score across 18 dataset combinations that include SafetyPointGoal and SafetyPointButton, against 78.8 for its variant that ignores bad data. No per-task SafetyPoint number appears in the file.
To keep the comparison fair, all methods use the same demonstrations, the same network sizes and the same number of gradient steps. Each gets an equal hyperparameter sweep, for example 20 configurations, tuned on held-out start-goal pairs. Every baseline is evaluated both bare and wrapped in the same runtime monitor we deploy, so our method cannot win safety by virtue of the monitor alone.
Two ablations isolate the key ingredient. The first replaces the invariant with a discretized geometric check that tests positions only (call it "geometric stitching"). The second keeps the invariant only as a runtime monitor and stitches without certification (call it "shield-only").
Beating the baselines means three things together. Our method must achieve higher success than monitored IRIS and monitored conservative Q-learning at zero observed collisions. It must have fewer monitor interventions and deadlocks than shield-only. And it must use fewer obstacle queries per validated edge than geometric stitching, with no collisions between samples that geometric stitching misses.
Why not just…?
Why not just train IRIS or conservative Q-learning and wrap it in a runtime safety monitor? This is the real threat, and it is exactly the shield-only ablation. The monitor makes execution safe, but the value function was trained believing in stitches the monitor will veto. Our prediction is that vetoes land precisely on the high-value shortcuts, where the robot is fast and close to walls, causing braking stops, oscillation or deadlock, and lower success. If shield-only matches our success and intervention rates, then certification during training adds nothing, and the honest conclusion is that a monitor suffices. The experiment is designed so that this outcome is reportable.
Why not just collision-check stitched edges with a standard geometric checker? In geometry-only terms this is cheap enough offline. However, it validates where the robot is, not whether it can stop, and it is unsound between samples. We expect it to admit stitches that end in unavoidable collisions at the speeds the demonstrators actually drove. The geometric-stitching ablation measures this as collisions under the bare policy, and the query counts measure the cost side. If speeds in a benchmark are so low that stopping distance is negligible, the two should coincide. We report that case rather than hide it.
Why not just learn from colliding demonstrations as negatives, as DualCOIL does? DualCOIL's own analysis notes that pushing away from recorded failures can drive the policy into unvisited states that are equally hazardous. Pushing away certifies nothing about where the policy ends up. We test this by measuring collisions in regions absent from the bad set, using held-out obstacle layouts.
Proposed Experiments
The benchmarks are planar navigation tasks where the verified model plausibly applies: D4RL Maze2D, PointMaze from the APC-RL suite, IRIS's Graph Reach, and Safety Gymnasium's SafetyPointGoal as used by DualCOIL. For each, we build flawed demonstration sets by running scripted planners with injected action noise, added control delay and occasional speeding past the braking envelope, at controlled corruption rates of 10%, 30% and 50%. This gives ground truth about which transitions are mistakes. APC-RL's reported 100% PointMaze success in 0.5M steps uses online interaction, so it is a ceiling reference rather than a comparable offline baseline.
The metrics are success rate, normalized return, path length relative to the best single demonstration (a direct measure of passing the ceiling), collisions per thousand episodes for bare and monitored policies, monitor interventions and deadlocks per episode, and obstacle queries plus wall-clock time per validated edge.
Three checks decide the outcome. First, does certified stitching produce paths shorter than every demonstration while recording zero collisions, when uncertified stitching on the same graph does produce collisions? Second, does shield-only lose success or gain interventions relative to our method as the corruption rate and demonstrator speed rise? This is where the claim lives or dies. Third, does the model-compliance rate stay high enough, say above 95% of transitions, for the proof's assumptions to be credible in each simulator? If it does not, the certificate's guarantee does not transfer, and we report that failure mode as a finding about using deductive proofs with learned systems.
References
- Formal Verification of Obstacle Avoidance and Navigation of Ground Robots
- Robot Motion Planning on a Chip
- Combining Deduction and Algebraic Constraints for Hybrid System Analysis
- Confidence-Aware Imitation Learning from Demonstrations with Varying Optimality
- Imitation Learning by Estimating Expertise of Demonstrators
- Exponentially Weighted Imitation Learning for Batched Historical Data
- IRIS: Implicit Reinforcement without Interaction at Scale for Learning Control from Offline Robot Manipulation Data
- D4RL: Datasets for Deep Data-Driven Reinforcement Learning.
- DualCOIL: Offline Imitation Learning from Contrasting Demonstrations
- APC-RL: Exceeding data-driven behavior priors with adaptive policy composition