PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Yifan Wang

arXiv:2606.02641v1cs.ROcs.AI

TL;DR

Interactive driving lacks a runtime certificate for repairing vetoed but lawfully recoverable maneuvers through bounded, attributable, right-of-way-affordable edits. CARVE provides this prediction-free certificate layer and, on INTERACTION replay episodes, recovers most human-resolved false vetoes while preserving right-of-way respect and stress-case vetoes.

  • Problem

    Existing rule gates veto unsafe or infeasible maneuvers, while prediction-based planners model likely responses, but neither jointly certifies the binding rule, bounded repair, edit ownership, right-of-way affordability, and fallback.

  • Method

    CARVE is a prediction-free repair layer over a finite multi-owner tactical lattice, restricting agent-owned requests with a cooperation envelope that scales kinematic accommodation by right-of-way status.

  • Results

    CARVE-Greedy accepts 98.64% of mined interactive conflicts and recovers 370/378 false vetoes while preserving 589/589 RoW-respect and zero priority-agent false positives.

  • Takeaways & Limitations

    CARVE makes repairability an auditable decision object that identifies whose bounded action would make a maneuver allowed under a declared normative envelope, without predicting another agent’s response.

  • Takeaways & Limitations

    The guarantees are relative to a finite tactical lattice, declared margins, and conservative envelopes; evaluation uses open-loop replay and does not establish closed-loop safety or compliance.

Abstract

from arXiv · show

Interactive driving exposes a failure mode that is easy to miss in rule-aware autonomous-driving stacks: a hard-rule margin can be negative for an ego candidate even though a small lawful accommodation by a non-priority agent would restore feasibility. Existing rulebooks, shields, and reachability filters are strong at vetoing unsafe actions, while prediction-based planners model likely responses. Neither returns a runtime proof object that states which bounded multi-agent edit repairs the maneuver, who owns the edit, whether the request is right-of-way affordable, and what ego fallback remains if the request is not observed. We formulate this missing object as *interactive repair certification* and introduce *CARVE*, a prediction-free certificate layer over a finite lattice of ego-owned and agent-owned tactical operators. Agent-owned requests are admissible only inside \(B_j(s) = β(π_j)α_j^{\max}(s)\), a cooperation envelope that separates kinematic reachability from normative priority. The resulting certificate records the binding rule, repair category, repair set, responsibility-weighted cost split, and fallback. On 589 Lanelet2-geometry-grounded INTERACTION replay episodes, CARVE-Greedy accepts 98.64% of initially vetoed maneuvers and recovers 370/378 human-resolved false vetoes, while preserving 589/589 right-of-way respect, zero priority-agent false positives, and 400/400 negative-stress vetoes. We prove certificate soundness, structural right-of-way respect, exact finite-lattice minimality, fallback contingency, and blame-consistency conditions. CARVE does not predict or require another driver's compliance; it certifies whether a proposed interaction is bounded, attributable, and normatively admissible under declared assumptions.

1 Introduction

Interactive driving needs a post-veto mechanism for maneuvers that can be repaired by bounded, lawful multi-agent accommodations. CARVE provides a prediction-free certificate that identifies the binding rule, repair, owner, affordability, and fallback.

  • Motivation: Negative hard-rule margins can represent recoverable interactions when a non-priority vehicle yields or the ego makes a small tactical adjustment.Binary vetoes can therefore create unnecessary conservatism by treating repairable conflicts as terminal.
  • Motivation: Existing rule gates, ego-only repair, and prediction-based planners do not jointly provide a bounded, attributable, right-of-way-affordable repair witness.The missing runtime object must identify the binding rule, finite repair, owner, and affordability of requested accommodation.
  • Certificate formulation: An interactive repair certificate records the binding rule, selected operators, ownership, costs, request bounds, and ego fallback without being a predicted trajectory or learned confidence score.It makes interactive recovery an auditable decision layer over proposed maneuvers.
  • CARVE approach: CARVE uses a prediction-free finite multi-owner tactical lattice with a right-of-way-scaled cooperation envelope that permits bounded requests to non-priority agents and blocks requests to priority agents.The envelope separates kinematic accommodation from normative admissibility, while certificate validity depends on declared bounds and operators rather than a response model.
  • CARVE approach: CARVE provides exact and greedy certificate procedures with soundness, finite-lattice minimality, right-of-way respect, fallback contingency, and blame-consistency conditions.These guarantees define the certificate’s formal properties over the declared operator lattice and envelopes.
  • Evaluation: CARVE is evaluated on Lanelet2-geometry-grounded INTERACTION replay episodes with ablations, negative stress tests, integrity checks, and multi-agent blame-consistency stress.The evaluation targets false-veto recovery while checking priority-agent behavior and certificate integrity.

2 Related Work

CARVE complements rule-aware planning, reachability, trajectory repair, and interaction-aware prediction by certifying bounded multi-agent tactical repairs. It is evaluated on INTERACTION replay data as a certificate layer rather than a trajectory generator or learned predictor.

  • Rule-aware planning and safety filters: Rulebooks, temporal logic, control-barrier filters, and shields enforce prioritized specifications or runtime safety, whereas CARVE emits a human-readable tactical certificate with ownership and affordability.CARVE operates at the tactical decision layer and complements these safety mechanisms.
  • Trajectory repair and reachability: Reachability tools bound participant behavior and ego-only repair methods repair violating ego trajectories, while CARVE searches a discrete lattice that includes bounded agent-owned accommodations.CARVE allocates repair burden across agents rather than restricting repair to ego actions.
  • Prediction and interaction-aware planning: Forecasting and interaction-aware planners model or predict responses, while CARVE audits whether a proposed maneuver has a bounded, attributable, right-of-way-affordable repair witness.The approaches are complementary rather than interchangeable.
  • Capability comparison: Table 1 defines “bounded” as explicit certification of agent-owned requests inside a cooperation envelope.This capability distinguishes bounded requests from merely modeling or allowing interaction.
  • Recent AAAI decision-making context: CARVE is complementary to recent regulation-aware driving, vehicle-planning, and scenario-generation work because it certifies proposed interactive maneuvers instead of generating trajectories or scenarios.Its role is certification of a bounded, attributable, right-of-way-respecting repair witness.
  • Datasets and map grounding: INTERACTION supplies the replay test set and Lanelet2 supplies the map abstraction; CARVE learns no parameters from the dataset.The dataset is used for evaluation rather than training.

3 Problem Formulation

CARVE formulates interactive repair as a finite, multi-owner search that combines hard-rule margins, bounded cooperation envelopes, responsibility-weighted costs, and fallback contingencies.

  • Problem Formulation: A maneuver is hard feasible only when every prioritized hard-rule margin is nonnegative.CARVE identifies the highest-priority rule with a negative margin as the binding rule for repair.
  • Operator lattice: CARVE searches a finite operator lattice whose assignments specify owners, tactical types, parameter grids, efforts, and binding-rule margin gains.Exact search selects a minimum-cost feasible repair under set inclusion over assignments.
  • Overview: Figure 1 contrasts CARVE’s bounded-request certification and fallback with prediction-based repair and hard-prune rulebooks.The overview presents false-veto recovery through right-of-way-affordable interaction as the purpose of the repair search.
  • Objective and affordability: Agent-owned requests must remain within a right-of-way-scaled cooperation envelope, while ego edits use a separate normalized effort budget.Priority agents receive zero request budget; equal-duty and yielding agents receive partial envelopes.
  • Certificate: The certificate records the binding rule, selected repair, responsibility-weighted cost allocations, and an ego-only fallback when available.The fallback supports contingency planning if an elicited accommodation is not observed.

4 The CARVE Algorithm

CARVE combines an exact branch-and-bound solver with a greedy online heuristic, while explicitly limiting its certificate claims to declared margins, lattices, and cooperation envelopes.

  • The CARVE Algorithm: The exact solver uses an admissible fractional relaxation as an optimistic lower bound for branch-and-bound pruning.Greedy is the online anytime path, while exact search retains soundness under the stated lower-bound construction.
  • What CARVE certifies: CARVE certificates prove selected-repair hard-rule feasibility and affordability under declared assumptions, not global continuous optimality or driver compliance.They also do not infer legal ground truth from geometry proxies.

5 Guarantees

CARVE’s guarantees are relative to declared margins, envelopes, and a finite tactical lattice: accepted repairs satisfy hard rules, bounded affordability, fallback, and responsibility conditions without predicting compliance.

  • Accepted certificates satisfy every declared hard rule, remain within ego cost budget, and keep each accommodation within 0 ≤∆j ≤Bj(s).
  • Priority agents receive no positive accommodation requests because β(πj) = 0 makes their cooperation envelope zero.
  • Exact CARVE returns a minimum-Φ affordable repair over the finite operator lattice or reports that none exists.
  • Certificates with an ego fallback provide an executable contingency when an elicited accommodation is not observed.
  • The guarantee is a runtime boundary rather than a prediction of another driver’s compliance.
  • Blame consistency prevents exact CARVE from assigning more raw accommodation to a lower-duty agent than to a higher-duty agent under stated exchangeability and capacity assumptions.

6 Evaluation Protocol

The evaluation mines deterministic, human-resolved false-veto episodes from INTERACTION and Lanelet2 geometry, then compares CARVE with controlled operator and envelope baselines using certificate-specific metrics.

  • 589 replay episodes are mined under conflict, ego-unilateral veto, later human resolution, and unambiguous-track criteria, without learning or tuning on INTERACTION.
  • HardPrune, ego-only variants, UniversalYield-UpperBound, AlphaOnly-CARVE, and NoElicit isolate terminal vetoes, ownership, normative scaling, and agent-owned repair effects.
  • FVRR measures recovery over 378 human-resolved ego-only vetoes, while CPA, BCR, fallback, and RHA diagnose envelope fit, agent-side responsibility, contingency availability, and behavior agreement.
  • Algorithm 1 selects the highest-priority negative-margin rule, searches operator choices, checks feasibility and budgets, and returns a repair category, cost split, and ego fallback when available.

7 Results

CARVE substantially improves recovery over ego-only repair while preserving right-of-way and negative-stress safety properties; remaining failures reflect declared envelope limits, and naturalistic multi-agent evidence is limited.

  • 98.64% acceptance and 370/378 FVRR show CARVE-Greedy recovers substantially more interactive conflicts than ego-only repair’s 35.82%.
  • 589/589 RoW-respect, zero priority false positives, and 574/574 BCR preserve priority and responsibility properties.
  • AlphaOnly reaches 100% FVRR but produces 14 priority-agent false positives, while CARVE vetoes 400/400 negative-stress cases.
  • Across non-priority envelope sweeps, RoW-respect remains 100.00% and priority false positives remain zero; strict and permissive β tables trade FVRR against CPA.
  • The eight unrecovered false vetoes require repairs outside declared budgets, and fallback exists for 204/574 eligible elicited or joint certificates.
  • Synthetic distinct-duty stress passes 648/648 BCR scenes and 2304/2304 pairwise checks, whereas naturalistic evidence provides 24 eligible real pairwise checks.

8 Discussion and Limitations

CARVE audits proposed maneuvers with an explainable certificate naming the binding rule, responsible party, request bound, and fallback. Its guarantees and evaluation are bounded by declared assumptions, finite tactical coverage, and open-loop replay rather than universal planner superiority.

  • CARVE wraps learned, trajectory-generating, or rule-based planners and returns an auditable decision object naming the binding rule, responsible party, request bound, and fallback.
  • The guarantees rely on a finite tactical lattice, declared margins, and conservative envelopes, not global continuous optimality or compliance by another driver.
  • Open-loop replay tests certificate logic against observed human resolutions but does not measure closed-loop social feedback; reactive-agent validation remains future work.
  • The evaluation isolates whether initially vetoed maneuvers admit bounded, attributable, right-of-way-respecting repairs rather than claiming superiority over all interaction-aware planners.

9 Conclusion

CARVE makes repairability an auditable decision object for interactive driving, specifying whose bounded action can restore feasibility and under what normative envelope. On INTERACTION replays, it recovers most human-resolved false vetoes while preserving right-of-way respect and vetoing unsafe stress cases.

  • CARVE turns infeasibility into a minimal, affordable, blame-consistent repair object without predicting another agent’s response.
  • The certificate records whose bounded action would make a maneuver allowed and the normative envelope governing that action.
  • CARVE recovers most human-resolved false vetoes while preserving structural right-of-way respect and vetoing unsafe stress cases.
Loading 2606.02641v1…