CARVE：基于合作包络对交互式驾驶中被否决机动进行认证式可负担修复 CARVE: Certified Affordable Repair of Vetoed Maneuvers via Envelopes for Interactive Driving
提出可审计修复证书框架，解决自动驾驶硬规则门控导致的误否决问题
前置知识
硬规则门控与右行权
自动驾驶决策栈中的规则层通过硬约束（间距裕度、TTC、信号灯等）将不安全的机动直接否决。右行权（Right-of-Way, RoW）描述不同道路参与方在交叉口、合流等场景下的优先权顺序，是判断谁应让行的规范基础。
本文的核心矛盾是硬规则门控在交互场景下过于保守，会把合法但需要他人小幅度配合的机动错误否决，必须理解规则与右行权的张力才能看懂CARVE为何要引入协作包络。
合作包络与合作算子
CARVE将可向其他车辆请求的'让行幅度'建模为物理可达性上限 $\alpha_j^{max}(s)$ 与右行权缩放系数 $\beta(\pi_j)$ 的乘积 $B_j(s)$；合作算子是参数化的离散战术动作（如减速、调整时距），按拥有者分为自车与对方车辆。
这是CARVE把物理可达性和规范可允许性分开建模的关键机制——包络让系统可以向让行方请求小幅配合，同时结构性禁止向优先权方发出任何请求。
TTC与间距裕度
时间到碰撞（Time-to-Collision, TTC）是当前运动趋势下两车预计相撞的时间，间距裕度（gap margin）刻画相对距离与速度差是否允许安全合流或穿越。这些是规则层最常用的硬约束量，本文沿用为缺口修复对象。
CARVE的修复目标就是把负裕度通过自车或对方的算子集合填补为非负，理解这两个指标才能看懂修复证书的对象是什么。
分支限界搜索
分支限界（Branch-and-Bound）通过系统枚举候选解的分支并利用可采纳下界剪枝，在有限离散空间内可证明地找到最优解。本文用于在算子-参数格点上以最低成本满足修复目标。
CARVE-Exact的最小性定理依赖分支限界，本文也借此给出可形式审计的全局最优修复结果而不是贪心近似。
Lanelet2与INTERACTION数据集
Lanelet2是自动驾驶常用的高精地图抽象格式，将道路元素组织为带方向和拓扑关系的车道单元；INTERACTION数据集是国际对抗与协作驾驶数据集，提供无人机视角下的多车轨迹及语义地图，是CARVE所用的回放评测基准。
实验在INTERACTION回放上跑出589个硬规则被否决的真实交互场景，地图层由Lanelet2承载，没有这两个数据集就无法做出误否决恢复率等关键指标。
研究动机
现代自动驾驶栈在规则层用硬裕度（间距、时间到碰撞等）对候选机动做二元门控。这类门控在交互式驾驶中会出现'误否决'：当自车候选动作在对方当前时距下不满足硬规则时，系统直接拒绝，但现实中人类驾驶员经常通过微小、合法的让行（如对方稍微减速、自车略等）化解冲突。具体表现为：在589个Lanelet2几何回放场景中，硬规则门控将全部589个交互式机动否决，其中378个场景里人类驾驶员后来通过这种小幅度配合成功化解冲突。现有替代方案各有致命缺陷：纯自车轨迹修复（如基于SMT的方法）只能修改自车轨迹，无法向对方发出有界请求；交互预测式规划依赖行为模型的正确性，无法给出可审计的安全论证；纯硬剪枝规则本又丢弃了所有可恢复的交互。
本文的目标是本文把误否决恢复重新形式化为交互式修复认证问题，目标是为一个被硬规则否定的机动生成一个修复证书——该证书是一个紧凑的可审计对象，记录被违反的具体规则、选取的修复算子集合（自车拥有和对方拥有两类）、按右行权分配的责任加权成本、以及当对方未配合时的自车后备方案。证书必须证明：(1)修复后所有硬规则裕度非负；(2)每个对对方的请求都在合作包络 $B_j(s)=\beta(\pi_j)\alpha_j^{max}(s)$ 内；(3)右行权被结构性尊重——优先权方永远不会被请求非零配合。
与已有工作不同的是，CARVE的独特切入角度是把修复他人动作建模为合作包络内的有界请求，而不是轨迹预测。物理可达性上限 $\alpha_j^{max}(s)$ 给出对方最大可合法减速幅度，右行权缩放 $\beta(\pi_j)\in\{0,0.5,0.8\}$ 把这个幅度按规范角色折扣——优先权方 $\beta=0$ 从结构上封锁任何请求，让行方 $\beta=0.8$ 给出较大但不超出物理可达性的预算。这样证书的合法性只依赖声明的包络与算子格点，不依赖对方是否真的会配合，从而把交互恢复从预测问题转化为边界内的可负担决策问题。与CBF/shielding相比，CARVE工作于离散战术决策层并发出人类可读的多智能体证书，不是连续控制修正。
核心方法
CARVE的核心思想是把误否决转写为有限算子格点上的修复搜索问题。对每个被硬规则否决的机动 $m$，先定位最高优先级的违反规则 $h^\star$，计算需要补回的缺口 $d=-g_{h^\star}(m,s)$；然后在由自车算子和对方算子组成的有限格点上搜索修复集 $A^\star$，使修复后所有硬规则裕度非负，且对方请求满足 $0\le\Delta_j\le B_j(s)$。作者提出两种求解路径：贪心路径（CARVE-Greedy）按 $\Delta g/\rho$ 比率依次选取可负担算子，作为在线快速启发式；精确路径（CARVE-Exact）使用基于可采纳分数松弛的分支限界，在有限格点上证明最小成本修复。两者输出同一个六元组证书 $C=(\kappa, h^\star, A^\star, \rho_{ego}, \{\rho_j\}, A_{fb})$，其中 $\kappa$ 是证书类别（ego-only / elicited / joint / over-budget refusal），$A_{fb}$ 是对方不配合时的自车后备方案。
最关键的创新是合作包络 $B_j(s)=\beta(\pi_j)\alpha_j^{max}(s)$ 这一公式。它做了两件事：(1)用物理可达性上界 $\alpha_j^{max}(s)=\min(|a_{min}^j|T,\|v_j\|_2)$（闭式速度减小的内界）把对方能合法配合多少限制在物理可达范围内，与行为预测模型解耦；(2)用右行权缩放 $\beta(\pi_j)\in[0,1]$ 把规范上允许多少按优先权/平权/让行三档分开编码——优先权方 $\beta=0$ 使包络严格为零，从结构上不可被发出请求，等价于定理2结构性右行权尊重的证明机制。这一分离让证书的合法性完全建立在声明的有限格点和包络上，不需要学习另一个驾驶员的响应，区分于现有的交互预测式和纯自车式修复方法。
方法步骤详情
Algorithm 1共8步：(1)输入机动 $m$、场景 $s$、规则 $H$、算子 $O$、模式；(2)若全部硬裕度非负输出satisfied证书；(3)否则定位违反规则 $h^\star$ 与缺口 $d$；(4)遍历算子筛正增益可负担赋值入池 $P$；(5)精确模式以分数松弛下界 $LB$ 跑分支限界按 $\Phi+LB$ 剪枝；贪心模式按 $\Delta g/\rho$ 比率最大化逐步加入；(6)若无修复返回over-budget或non-repairable；(7)若存在则搜ego后备 $A_{fb}$；(8)输出证书 $(\kappa, A^\star, \rho_{split}, A_{fb})$。成本 $\Phi(A)=\sum_{(o,\theta)\in A_{ego}}\rho_o(\theta)+\sum_j w(\pi_j)\sum_{(o,\theta)\in A_j}\rho_o(\theta)$；自车预算 $B_{ego}$ 与对方预算 $B_j$ 单位独立、不互换。
技术新颖性
技术新颖性体现在三方面：第一，问题重新定义——把交互式误否决从轨迹预测重铸为有限格点上的有界请求认证，证书是证明对象而不是预测轨迹或置信度，这是与Wang等人2024年交互感知轨迹修复最本质的区别。第二，合作包络 $B_j(s)$ 用闭式物理可达上界乘以右行权折扣，将物理可达性和规范可允许性在同一公式内解耦，对优先权方结构性禁止请求，无需额外的硬编码规则列表。第三，可证明性——五个定理覆盖声音性、结构性右行权尊重、有限格点最小性、ego后备存在性、多智能体责任一致性，其中责任一致性定理用交换论证证明精确求解器不会把更多原始配合量分配给低优先级方；这些是相对窄但深的理论贡献，与依赖行为模型正确性的方法形成对照。
实验结果
在589个Lanelet2几何接地的INTERACTION回放片段上，CARVE-Greedy接受率98.64%、在378个人类化解的ego-only否决中恢复370个（FVRR=97.88%），而剥离对方算子的EgoOnly-Greedy/Exact仅接受35.82%（211个），证明恢复能力主要来自合法的多拥有者协作而非更弱的搜索；CARVE-Exact给出98.64%接受、97.88% FVRR、2.67/11.61ms p50/p99延迟，与贪心一致但能给出最小成本证书。右行权尊重率589/589=100%、优先权方误报数（Prio. FP）为0、BCR=100%（574/574），证明恢复不靠牺牲规范。8个未恢复误否决都属于只能通过请求优先权方或超出 $B_j$ 才能修复，系统主动拒绝而非静默失败。证书分类为7个ego-only、563个elicited、11个joint、8个over-budget refusal。负向压力测试400/400全部正确否决，完整性脚本零失败，17个单元测试通过。
查看结构化数据
| 任务 | 指标 | 本文 | 基线 | 提升 |
|---|---|---|---|---|
| 误否决恢复（INTERACTION回放，589场景） | Accept / FVRR | CARVE-Greedy 98.64% / 97.88% (370/378)；CARVE-Exact 98.64% / 97.88% | EgoOnly-Greedy/Exact 仅 35.82%（FVRR未定义因ego-only版本不发出agent-owned请求）；HardPrune 0% | FVRR绝对提升约62个百分点，恢复几乎所有ego-only无法化解的人类交互冲突 |
| 右行权结构性尊重 | RoW-respect / Prio. FP | 100.00% (589/589) / 0 | EgoOnly-Greedy/Exact 100% / 0；AlphaOnly-CARVE（移除 $\beta$）仅 97.62% / 14 | 在引入对方算子后仍保持100%右行权尊重与零优先权误报，相对AlphaOnly减少14例优先权违规 |
| 合作包络合规性诊断 | CPA(Bj) = 在合格证书中观测配合落在Bj内的比例 | CARVE-Greedy 66.20%；CARVE-Exact 66.49% | AlphaOnly-CARVE 83.36%（但产生14个优先权误报）；UnivYield-UB 未定义（无规范约束的上界） | CPA是诊断而非越高越好，更高CPA伴随规范违规；CARVE以66%换取100%右行权尊重 |
| 责任一致性（多智能体） | BCR | 100% (574/574)；合成 distinct-duty 压力648/648场景通过、2304/2304配对检查通过 | EgoOnly不涉及agent-owned成本，无BCR；AlphaOnly-CARVE 100%（但无 $\beta$ 区分） | 在引入责任权重 $w(\pi_j)$ 后仍100%满足Theorem 5的交换论证不变量 |
| 运行时延迟（4核8线程笔记本CPU） | p50 / p99 ms | CARVE-Greedy 1.76 / 2.99；CARVE-Exact 2.67 / 11.61 | EgoOnly-Greedy/Exact延迟未列出但结构等价 | 贪心<3ms满足在线战术层要求；精确<12ms可作审计模式偶发调用 |
| 负向压力与完整性 | Negative veto / Integrity replay | 400/400负向场景全部正确否决；完整性脚本零主集/负集失败；17单元测试通过 | AlphaOnly会在负向集中通过本应拒绝的案例（破坏100%否决） | 在CARVE-Greedy上同时维持高接受率与100%安全压力通过 |
局限与改进
作者明确指出几个限制：当前算子格点针对1–3辆冲突车辆设计，密集场景需要分层冲突聚类；超出声明战术本体（finite tactical ontology）的修复不可达；INTERACTION回放中只有极小部分片段含有显式右行权元数据，其余143个被标记为all-way-stop元数据、198/204个为几何导出代理标签，因此右行权标签的可靠性是研究外部依赖；闭环验证（在CommonRoad或CARLA中接入反应式智能体）是未来工作；UniversalYield上界是不可部署的诊断，不构成对外基线。从观察看：合作包络 $B_j(s)$ 用闭式 $\min(|a_{min}^j|T,\|v_j\|_2)$ 简化了动力学，未建模转向让出、坡度、刹车系统响应延迟；CPA≈66%意味着约三分之一观测配合超出保守规范包络，说明真实人类配合幅度比规范假设更激进，作者将此归为保守包络的代价而非预测失败；RHA（修复-人类一致率）按类型164/581、按幅度更低，说明最小证书比人类典型操作更紧凑，这是设计选择但限制了行为拟人性。
独立分析的弱点
独立分析可见四点可改进方向：(1)封闭形式合作包络 $\alpha_j^{max}(s)=\min(|a_{min}^j|T,\|v_j\|_2)$ 假设匀减速度且忽略横向让出，对低速或转向场景偏保守，改进方向是引入状态相关的运动基元（转向让出、停车让行）。(2)右行权标签严重依赖几何代理，198个geometry-arrival proxy与204个geometry-equal proxy可能把信号灯优先权或停车让行标记错误归类，可改进方向是与OpenStreetMap或当地交通法规数据库交叉验证。(3)CPA≈66%意味着证书比真实人类配合保守约三分之一，会在以恢复人类决策为目标的评估下吃亏，可改进方向是引入基于大量自然驾驶数据的统计先验（仍保持可负担上界但提高命中率）。(4)算子格点对1–3辆冲突手工枚举，密集十字路口多个潜在配合对象组合爆炸，改进方向是用分层冲突聚类（先做冲突图分组再在组内枚举）。此外，当 $A_{fb}$ 不存在（35%证书无后备）时系统只能监控并重认证，没有给出延迟保证或重认证预算。
未来方向
作者提出的未来工作包括：闭环验证（在CommonRoad或CARLA中接入反应式智能体，测量CARVE在社会反馈下的行为）；密集场景的分层冲突聚类；将证书层接入学习型行为规划器或规则候选生成器作为外层审计；与V2X、UI提示或监控假设三种实现路径的实证对比。基于成果可延伸的方向包括：把证书格式标准化为可机器校验的证明对象（如SMT-LIB片段）以支持第三方审计；将合作包络与RSS（Responsibility-Sensitive Safety）责任模型结合，使可负担性同时编码规范与责任；扩展到行人/骑行者异质参与者；将ego后备 $A_{fb}$ 编码为可达性集合而非单一轨迹，从而在监控-重认证循环中给出更紧的安全边界；探索在5G-V2X下把请求/确认/拒绝形成实时协议。
复现评估
代码被声明为可获取的artifact，但论文未提供具体GitHub链接（作者仅说supplement and code artifact），建议读者搜索arXiv版本或作者McGill页面。复现所需资源包括INTERACTION数据集（公开，需注册下载）、Lanelet2地图（公开）以及自定义算子格点声明文件。算力要求极低：4核8线程笔记本CPU即可，CARVE-Greedy<3ms p99、Exact<12ms p99，无需GPU。复现难度评估为中等偏下——核心算法约30–50行可实现，分支限界+分数松弛是经典组合优化模式；但需要复现完整的INTERACTION→Lanelet2冲突挖掘管线（589个场景的几何接地、右行权标注、ego-only否决筛选、人类化解标签）以及17个单元测试，这些工程细节在主文中仅给出粗略描述，关键的声明算子格点、$\beta$表、阈值等超参数需在补充材料中查找。
论文图表