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

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.

arXiv comment7 pages, 2 figures, 1 algorithm, 4 tables