arXiv:2505.22982cs.ROcs.SE2025-05

用结构抽象加速机器人安全验证,自动修复错误并提升效率。

Structural Abstraction and Selective Refinement for Formal Verification

  • 以体素环境为背景,采用结构抽象生成简化模型。
  • 在高分辨率场景中数分钟内发现反例,直接验证会崩溃。
  • 适合需要快速可靠验证的复杂机器人系统设计者。

机器人应用的安全验证因环境复杂而极具挑战性。基于模型检测的正式验证虽能提供保证,但对复杂环境模型常耗时过长甚至失败。传统方法多采用行为抽象,本文提出新的结构抽象方法,结合体素表示的环境建模。该方法生成抽象体素,并构建完整自动化验证流程,受反例引导抽象精化(CEGAR)启发:先进行初始抽象,再根据反例逐步引入精化,与模型检测器运行交替进行。通过选择性地精化结构抽象,显著提升模型检测效率。所实现的全自动流程在真实高分辨率场景中仅用几分钟即发现反例,而直接模型检测在数天后仍无法完成,反而崩溃,证明了方法的可行性。

原文摘要 · Abstract (English)

Safety verification of robot applications is extremely challenging due to the complexity of the environment that a robot typically operates in. Formal verification with model-checking provides guarantees but it may often take too long or even fail for complex models of the environment. A usual solution approach is abstraction, more precisely behavioral abstraction. Our new approach introduces structural abstraction instead, which we investigated in the context of voxel representation of the robot environment. This kind of abstraction leads to abstract voxels. We also propose a complete and automated verification workflow, which is based on an already existing methodology for robot applications, and inspired by the key ideas behind counterexample-guided abstraction refinement (CEGAR) - performing an initial abstraction and successively introducing refinements based on counterexamples, intertwined with model-checker runs. Hence, our approach uses selective refinement of structural abstractions to improve the runtime efficiency of model-checking. A fully-automated implementation of our approach showed its feasibility, since counterexamples have been found for a realistic scenario with a fairly high (maximal) resolution in a few minutes, while direct model-checker runs led to a crash after a couple of days.

形式化验证机器人安全抽象精化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。