Skip to content
Preprint

GARV: Graph-Aware Refinement and Safety Verification for High-Level Robot Plans

Oct 2026 · 0 citations · 13 references
Computer Science

TL;DR

Graph-Aware Refinement and Verification (GARV), which composes graph-grounded action contracts with a safety monitor to produce a model-relative certificate or counterexample and, when route choice is enforceable, a minimum-cost safe refinement.

Abstract

High-level robot actions such as goto(region) can hide intermediate traversal, allowing a monitor of the listed actions to accept a plan whose graph-level execution violates a safety rule. We present Graph-Aware Refinement and Verification (GARV), which composes graph-grounded action contracts with a safety monitor to produce a model-relative certificate or counterexample and, when route choice is enforceable, a minimum-cost safe refinement. In a 28-case controlled audit, refinement exposed all 12 targeted hidden hazards and produced the expected verdicts on 16 controls; a separate 14-case SPINE-RoboGuard instantiation yielded two false-safe cases and five action-interface errors. In standalone finite-graph simulation, all 16 designed cases met their expected outcomes, and product verification agreed with exhaustive enumeration on classification, minimum safe hop count, and witness safety in 160 comparisons across 40 graphs. Across 90 graph-contract evaluations on 30 graphs with a hazard deliberately placed on the selected shortest route, GARV found a safe refinement in 72 evaluations and no safe route within the permitted hop bound in 18. For the static forbidden-region rule, synthesis matched a simple hazard-deletion baseline in all 90 evaluations; GARV's guarantees remain conditional on the semantic graph, action contract, safety specification, and enforceability of any selected route.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.