Skip to content

CARVE: Certified Affordable Repair of Vetoed Maneuvers via Envelopes for Interactive Driving

🕒 Published (v1): 2026-05-31 00:00 UTC · Source: HuggingFace · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

CARVE is a prediction-free certificate layer for interactive autonomous driving that converts a vetoed (infeasible) maneuver into a bounded, attribution-aware repair proof object — specifying which rule binds, which finite tactical edits fix it, who owns each edit, and whether every requested accommodation is right-of-way affordable. On 589 INTERACTION replay episodes it recovers 370/378 human-resolved false vetoes while maintaining 100% right-of-way respect and zero priority-agent false positives.

Problem

Existing AV safety stacks (rulebooks, shields, CBF filters) are good at binary vetoes but produce no positive witness explaining how a rejected maneuver could be repaired. Interaction-aware planners can predict that another agent will yield, but safety then depends on the correctness of a learned behavior model. Neither approach provides a runtime proof object that jointly answers: which rule binds, which finite multi-agent edit repairs the violation, who is responsible for each edit, whether the requested accommodation is right-of-way affordable, and what ego fallback exists if the request is unobserved.

Method

CARVE operates as a certificate layer over a finite multi-owner tactical lattice. An operator \(o = (\text{owner}, \text{type}, \Theta_o, \rho_o, \Delta g_o)\) defines a finite parameter grid \(\Theta_o\), normalized effort \(\rho_o(\theta)\), and margin gain \(\Delta g_o(\theta)\). A repair set \(A\) is a subset of operator-parameter assignments; the lattice is ordered by set inclusion.

The key mechanism is the cooperation envelope: $\(B_j(s) = \beta(\pi_j)\,\alpha_j^{\max}(s)\)$ where \(\alpha_j^{\max}(s) = \min(|a_j^{\min}|T, \|v_j\|_2)\) is a kinematic speed-reduction bound (horizon \(T=5\,\text{s}\)) and \(\beta(\pi_j) \in \{0, 0.5, 0.8\}\) for priority, equal-duty, and yielding agents respectively. Priority agents receive \(\beta=0\), making any nonzero request structurally impossible.

CARVE minimizes: $\(\Phi(A) = \sum_{(o,\theta)\in A_{\text{ego}}} \rho_o(\theta) + \sum_j w(\pi_j)\sum_{(o,\theta)\in A_j} \rho_o(\theta)\)$ subject to hard-rule feasibility (\(g_\ell \geq 0\) for all rules) and affordability (\(0 \leq \Delta_j \leq B_j(s)\)). Two search modes: Exact (branch-and-bound with admissible fractional lower bound; exponential worst case, heavily pruned) and Greedy (anytime, \(O(D|P|)\)). The returned certificate \(C = (\kappa, h^\star, A^\star, \rho_{\text{ego}}, \{\rho_j\}, A_{\text{fb}})\) records the repair category, binding rule, selected repair, cost split, and ego fallback.

Key Contributions

  • Formalizes interactive repair certification as a distinct problem class, separate from trajectory prediction and hard vetoing.
  • Introduces the right-of-way-scaled cooperation envelope \(B_j = \beta(\pi_j)\alpha_j^{\max}\) that structurally enforces priority: \(\beta=0\) makes priority-agent requests impossible by construction, not by soft penalty.
  • Proves five formal properties: certificate soundness, structural right-of-way respect, finite-lattice minimality (exact mode), fallback contingency boundary, and multi-agent blame consistency.
  • Provides both exact (auditable) and greedy (online) procedures with sub-3 ms p99 latency on a laptop CPU.
  • Evaluates on 589 Lanelet2-grounded INTERACTION replay episodes with ablations, negative stress tests (400 unsafe cases), and synthetic blame-consistency stress (648/648 BCR scenes).

Results

  • CARVE-Greedy: Accept 98.64%, FVRR 370/378 (97.88%), RoW-respect 589/589 (100%), priority false positives 0, BCR 574/574 (100%), latency p50/p99 = 1.76/2.99 ms.
  • EgoOnly-Greedy (same rules, no agent operators): Accept 35.82%, confirming that the missing recovery capacity is lawful multi-owner cooperation, not search configuration.
  • HardPrune: Accept 0.00% (terminal veto baseline).
  • AlphaOnly-CARVE (removes \(\beta\) scaling): FVRR 100% but 14 priority-agent false positives — structural envelope is necessary.
  • Negative stress: 400/400 unsafe cases correctly vetoed (200 unrepairable collisions + 200 priority-over-budget).
  • RHA (repair-human agreement): broad repair type matches 359/581; full type+magnitude matches 164/581 — humans choose larger/later maneuvers than the minimal certificate.
  • Sensitivity sweep over gain, cost, TTC-threshold, and \(\beta\)-table: RoW-respect and priority false positives remain at 100%/0 across all non-priority envelope variants.

Limitations

  • Guarantees are relative to the declared finite tactical lattice and declared margins; no global continuous optimality or closed-loop safety under unmodeled rules.
  • Does not assume or require another agent's compliance; certificate asserts admissibility of a request, not that the request will be observed.
  • No closed-loop validation; only open-loop replay against observed human resolutions — closed-loop evaluation with CommonRoad/CARLA is future work.
  • Most right-of-way labels are geometry-derived proxies, not explicit regulatory metadata (only 44/589 episodes have explicit or partial RoW metadata).
  • Current lattice targets 1–3 conflict agents; dense scenes require hierarchical conflict clustering.
  • The 8 unrecovered false vetoes represent cases where repair would require exceeding \(B_j\) — a safe refusal, but a coverage gap.

Relevance to Agentic AI / LLM Agents

CARVE demonstrates a pattern directly applicable to agentic AI: a certificate layer that wraps arbitrary black-box proposers (learned planners, LLM action generators) and audits proposed actions for bounded, attribution-aware, normatively admissible execution — returning a human-readable proof object rather than a scalar confidence score. The blame-consistency and fallback contingency theorems operationalize concepts central to multi-agent coordination: who owns which action, how burden is allocated across agents under role constraints, and what the principal can do if a requested sub-action is not performed. For LLM agent systems where a model proposes tool calls or multi-step plans, the analogy is direct: CARVE's certificate layer decouples generation (propose) from verification (certify), enabling trustworthy and explainable AI pipelines where responsibility is formally attributable.