《International Journal of Approximate Reasoning》：Exploiting the Impossible: Improving Resilience of Critical Decision Making Against Misperceptions
编辑推荐：
摘要翻译：
网络物理系统（CPSes）是经由传感器和执行器将信息技术与物理过程紧密集成的系统，通过主动的嵌入式监督与控制来改变固有物理行为。此类自主网络物理系统（ACPSes）是当前向独立行动的“智能”技术物品（如自主飞机、船舶和汽车，智能健康系统，或智能能源
摘要翻译：
网络物理系统（CPSes）是经由传感器和执行器将信息技术与物理过程紧密集成的系统，通过主动的嵌入式监督与控制来改变固有物理行为。此类自主网络物理系统（ACPSes）是当前向独立行动的“智能”技术物品（如自主飞机、船舶和汽车，智能健康系统，或智能能源与供水系统）发展的关键技术。由于既具有自主性又嵌入具有显著能量的物理过程，ACPSes内部的信息技术必须持续地对可能影响健康、生命和环境的操纵做出决策。此类安全关键决策不再纯粹基于相对低维的物理量测量向量（如位置、速度、温度、辐射等），而是日益依赖于环境成像及随后对图像的解释。与物理量测量类似，基于光学感知的情境解释也受到不确定性的影响；但不同于那些标量测量，当涉及空间态势感知时，这些不确定性的类型及其通过控制架构和被控过程的传播极为多样且尚未被充分理解。广义上，这些不确定性可分为三类：存在性不确定性、分类不确定性和状态不确定性。虽然状态不确定性的成因和传播已较为清楚，其描述与分析模型亦是如此，但另外两类不确定性因对关键操纵决策产生通常不连续的影响而较少明确。更不成熟且未被充分理解的是控制和建设性地将这些不确定性及其引发的安全风险降低到社会可接受水平的方法，从而使ACPSes具有严密的安全性。尽管对更好、更可靠的计算机视觉（CV）算法的投入有助于提高目标检测、定位和分类的正确率，并降低错误检测率等，但CV的实际可靠性数据与ACPSes的严格定量安全目标及其对环境感知和解释所隐含的故障率之间的差距仍然很大。本研究认为，如果考虑保护关键操纵的复合条件的语义内容，而不只是优化单个感知的可靠性，这一差距可显著缩小。研究人员提出的机制利用了运行域的不变量来重写这些守护条件，从而在保持其语义的同时降低误评估率。乍看这似乎矛盾：如果语义（即评估）保持不变，误评估率又如何改变？关键在于设计域的不变量（如环境中任何汽车的最小尺寸）提供了“无关项情形”：这些情形在真实世界中不可能出现，而只能由感知错误产生。通过重写守护条件（本质上是连接关于感知断言的布尔表达式），这些错误感知可被重新映射，而不会改变守护条件在任何可能的真实情形下的语义（即真值）。然而，这种重写应当有效或等价地说，应当算法化：它应构成一种机制，自动将安全关键守护条件重写为更鲁棒的变体，该变体保留原条件的逻辑内容，并在不确定性下提供韧性评估，即使误报率（可能导致危险操纵的异常采纳率）低于社会接受阈值，同时最大化真报率，即系统性能。Fig. 1 描绘了正报率与社会期望之间的关系：那里的守护条件保护一个带有正面碰撞风险的规避操纵；误报可能诱发此类碰撞，而真报则通过避免不必要的紧急停车使系统保持运行。Fr?nzle 和 Hein 在参考文献[2]中证明，关键守护条件的最优重写可精确形式化为线性算术中的优化问题，即线性规划，但其规模随守护条件中的变量数（即条件所依据的感知数）呈指数增长。这实际上阻碍了任何实际应用，因为守护条件往往相当庞大。从上述重写目标描述中可看出，守护条件的重写过程是布尔表达式无关项优化的一个特例。在本文中，研究人员采纳这一观点，提出一种通过约简有序决策图（ROBDDs，参考文献[3]）对问题进行编码，并给出与故障率相对应的概率解释。随后，研究人员在ROBDD上实现一种无关项优化变体，以实现期望的优化，但在真报率和误报率的最优解搜索中以穷尽性换取效率，因为无关项优化和变量重排这两个ROBDD核心操作的最优解均为NP完全问题（参考文献[4]、[5]、[6]）。优化感知的可能应用领域包括高度自动化或自主系统（如智能汽车，参见Fig. 1）安全关键操纵的守护条件，以及其他形式的运行时验证，如出于责任原因对自主系统进行在线监控。在所有这些应用中，环境感知精度的提高可改善运行时验证结论的可靠性。
论文解读：
### 研究背景与问题
自主网络物理系统（ACPSes）是信息技术与物理过程深度融合的产物，其典型代表包括自动驾驶汽车、自主船舶、智能健康系统等。这类系统需要在动态、非合作的物理环境中做出安全关键决策，例如是否执行紧急避让、是否触发故障安全模式。传统上，此类决策基于对物理量（位置、速度、温度等）的低维测量；而现代ACPSes日益依赖光学感知（摄像头、激光雷达等）对环境进行成像与语义解释，以获取空间态势感知。然而，光学感知链路的误感知率远高于社会对安全关键系统的定量安全目标（例如高度自动化车辆的安全要求）。感知不确定性可分为三类：存在性不确定性（是否检测到相关物体）、分类不确定性（物体类别是否判断正确）和状态不确定性（物体速度、距离等物理量是否精确）。其中状态不确定性的传播模型已较成熟，而存在性与分类不确定性因对操纵决策产生不连续影响，其建模与控制手段尚不完善。已有工作通常通过提升计算机视觉算法性能或调节分类器阈值来降低误感知率，但感知错误率与安全目标之间仍存在数量级差距。Fr?nzle 和 Hein 的前期研究指出，关键操纵的守护条件（通常为布尔表达式）的误评估率不仅取决于单个感知的可靠性，还取决于守护条件的布尔结构。他们曾提出一种基于线性规划的精确重写算法，可优化守护条件的真报率与误报率，但其线性规划规模随感知变量数量指数增长，无法应用于实际问题。因此，需要一种可扩展的符号化方法，在保持守护条件语义的前提下，利用运行域不变量提供的“无关项”来重写条件，从而提升其对错误感知的韧性。
### 研究内容与结论
本论文提出了一种基于约简有序二元决策图（ROBDD）的守护条件重写算法，系统性地提升自主系统安全关键决策在感知不确定性下的韧性。该算法将守护条件与运行域不变量编码为ROBDD，并结合概率解释以计算真报率（TPR）与误报率（FPR），通过类似ROBDD无关项优化的路径重定向（兄弟替换）机制，将真实世界中不可能出现但可能由感知错误导致的“无关项”情形重新映射，从而在不改变守护条件在任何真实情形下语义的前提下，降低误报率并最大化真报率。由于无关项优化和变量重排均为NP完全问题，算法采用启发式策略（如sifting变量重排）在效率与最优性间取得平衡。论文通过一个交通场景示例（自动车避让障碍物）验证了方法的有效性：在保持误报率低于社会接受阈值（0.2）的前提下，优化后的守护条件将真报率从0.191提升至约0.272，相对提升超过42%，而误报率仅从0.172增至0.19。该结果表明，利用领域不变量进行守护条件重写可显著改善安全关键决策的可靠性，且其符号化表示具有良好的可扩展潜力。论文发表于《International Journal of Approximate Reasoning》。
### 关键技术方法
研究人员主要采用了以下关键技术方法：（1）将守护条件与运行域不变量表示为ROBDD，利用其规范性与共享子图特性实现紧凑符号操作；（2）构建地面真值变量与感知变量的联合变量序，将感知错误概率编码为联合概率分布，从而通过ROBDD路径枚举计算守护条件的真报率与误报率；（3）借鉴ROBDD无关项优化中的兄弟替换技术，但将优化目标从“减小ROBDD规模”改为“最大化真报率且误报率低于阈值”，并采用奖励函数指导替换选择；（4）使用sifting启发式进行变量重排，以近似处理变量序对匹配过程的影响。样本队列来源为人工构造的交通场景与玩具示例，无临床或真实数据集。
### 研究结果
本节按原文小标题概括研究结果（各小节基于相应章节内容）：
**“重写守护条件（Rewriting guard conditions）”**：研究人员形式化定义了基于ROBDD的守护条件重写问题。给定地面真值守护条件\(g_B\)、感知副本\(g_C\)及运行域不变量\(\iota\)，重写目标为构造\(g^*_B\)，使其在\(\iota\)约束的所有真实情形下与\(g_B\)等价，但在\(\iota\)之外可自由偏离。通过识别不变量ROBDD中通往假叶的路径（即无关项部分赋值），在守护条件ROBDD中匹配相应路径并将其末端重定向至兄弟子节点，实现局部消除对特定感知变量的依赖，从而提升对错误感知的韧性。该过程同步应用于不变量ROBDD以跟踪处理进度，直至不变量ROBDD化简为恒真。
**“优化的效果（Effect of the optimisation）”**：研究人员通过一个三变量玩具示例（变量\(x,y,z\)及其感知副本\(\hat{x},\hat{y},\hat{z}\)，感知可靠性设为90%）验证了算法效果。给定条件概率分布后，初始守护条件的真报率为0.191、误报率为0.172；经算法优化后，真报率提升至约0.272（相对增加超过42%），误报率升至0.19，但仍低于预设的社会接受阈值0.2。这表明算法能在控制误报风险的同时显著提升安全关键动作的正确触发率，并减少对物体存在性及状态估计的依赖。
### 讨论与结论
讨论部分指出，将自主系统“变得比感知更安全”是必要的。前期工作中，文献[10]从分析角度证明复杂布尔守护条件评估的定量可靠性，文献[2]提出理论重写框架但指数复杂度不可扩展。本文的ROBDD方法改进了可扩展性，但实现仍为原型，未来需借助成熟BDD包中的优化技术。此外，利用占据栅格的空间几何性质（如小位移比大位移更常见且更不易改变守护条件真值）以及时间维度上真阳性和真阴性比假阳性/假阴性更持久的特性，有望进一步提升搜索效率。在时间域，真阳性和真阴性的时间持久性通常高于假阳性和假阴性，但复杂时空条件的守护评估特性与原子误感知滤波不同，这仍需研究。结论部分（翻译）：自主网络物理系统的安全性和性能是其社会接受的先决条件。这要求对此类系统的安全与性能指标给出严格保证，且由于系统直接物理影响显著能量过程而对健康、生命和环境构成风险，定量安全目标很高。对于涉及对非合作环境进行光学感知的系统（如正常交通速度下的自动驾驶车辆），由于技术感知链（如计算机视觉系统）的误感知率相对较高，难以达到所需的定量安全水平。因此，需要对安全关键操纵可能因误感知而被错误采纳的可能性进行严格评估，且该评估必须提供比任何单个误感知更紧的错误操纵采纳界限。本文将前期分析推向深入，给出一种采用ROBDD类数据结构的改进重写算法以提升可扩展性。该算法利用ROBDD表示地面真值事实与其不可靠感知的可能组合，并同步评估守护条件，旨在找到原始守护条件对误感知更具韧性且保持语义的重写。具体地，寻找满足以下条件的公式重写：（1）在所有地面真值实例上与原守护条件等价；（2）达到社会给定的安全目标，即误报率（在不该触发时建议关键操纵）保持低于社会接受阈值；（3）优化性能，即获得高真报率，在应当触发时确实启用关键操纵。重写关键在于利用应用域的地面真值不变量来识别无关项情形，即不对应于任何真实情形的感知，从而可根据原守护条件的（在无关项情形下任意的）真值进行重新映射。算法上，其工作方式类似于ROBDD上的无关项优化，但针对完全不同的优化目标——高真报率和可接受的低误报率而非ROBDD规模——需要实质性的补充和修改：第一，它建立在ROBDD类数据结构的合适概率扩展之上，其中路径携带概率属性，并在ROBDD操作（如sifting变量重排）中一致更新这些属性；第二，兄弟替换被改进的替换原则取代，该原则不是将无关项匹配到任意定义情形，而是基于反映特定误感知概率的奖励函数进行匹配。ROBDD推理的实现仍是原型，未来工作将利用当代BDD包中的算法与数据结构增强进行优化实现，并利用栅格结构引发的拓扑与几何性质以及动力学引发的时间相关性来细化分析。
