🤖 AI

VeriGraph: Scene Graphs for Execution Verifiable Robot Planning

VeriGraph is a novel framework that integrates vision-language models with scene graph-based verification to iteratively refine and validate robot action sequences, significantly improving task completion rates across diverse manipulation scenarios compared to baseline methods.

Original authors: Daniel Ekpo, Mara Levy, Saksham Suri, Chuong Huynh, Archana Swaminathan, Abhinav Shrivastava

Published 2026-04-20

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Daniel Ekpo, Mara Levy, Saksham Suri, Chuong Huynh, Archana Swaminathan, Abhinav Shrivastava

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a very smart, but slightly clumsy, robot how to clean up a messy kitchen. You give it a simple command: "Put the tomato can on the bean can and move the apple into the bowl."

If you ask a standard AI robot to do this, it might look at the picture, guess what to do, and try to grab the apple. But if the apple is sitting on top of a plate that is currently on a jar, the robot might try to grab the jar first, causing the plate to crash and the apple to roll away. It's like trying to move a stack of books without realizing the top one is loose; you knock the whole thing over.

VeriGraph is a new system designed to stop these accidents before they happen. Think of it as giving the robot a mental blueprint and a strict safety inspector before it even touches anything.

Here is how it works, broken down into simple steps:

1. The "Mental Blueprint" (The Scene Graph)

Instead of just looking at a blurry photo of the kitchen, VeriGraph translates the image into a structured list of facts, like a social network for objects.

The Analogy: Imagine the robot doesn't just see "a red can." It sees a card that says: "Tomato Can is ON TOP OF Bean Can." Another card says: "Bowl is ON TOP OF Plate."
This list is called a Scene Graph. It strips away the confusing details (like the color of the tablecloth) and focuses only on the relationships that matter: What is touching what?

2. The "Architect" (The Planner)

Once the robot has this list of facts, it asks a super-smart AI (the Architect) to write a to-do list.

The Analogy: The Architect says, "Okay, to move the tomato can, I first need to move the bean can out of the way."
Without VeriGraph, the Architect might just guess the order. With VeriGraph, the Architect is forced to look at the "Mental Blueprint" to see what is physically possible.

3. The "Safety Inspector" (The Verifier)

This is the magic part. Before the robot actually moves its arm, VeriGraph acts as a strict safety inspector.

The Analogy: Imagine the Architect writes down a plan: "Pick up the Bowl."
The Safety Inspector looks at the Mental Blueprint and shouts: "STOP! You can't pick up the Bowl yet! There is a Plate sitting on top of it!"
The Inspector then sends the plan back to the Architect and says, "Fix this. You need to move the Plate first."
The Architect rewrites the plan, the Inspector checks it again, and then the robot is allowed to move.

4. The "Loop of Correction"

If the robot tries to do something and the Inspector catches a mistake, the system doesn't just give up. It loops back, fixes the plan, and tries again.

The Analogy: It's like playing a video game where you can't die. If you try to jump off a cliff, the game pauses, tells you "That's a bad idea," and lets you try a different path. You keep trying until you find the safe route.

Why is this a big deal?

Previous robot planners were like dreamers: they had great ideas but often forgot the laws of physics (like gravity or stacking). They would try to grab a book that was underneath a heavy vase, causing a mess.

VeriGraph is like a pragmatic engineer:

It creates a clear map of the world (Scene Graph).
It checks every single step against that map.
It fixes its own mistakes automatically without needing a human to yell at it.

The Results

In tests, this system was 58% better at following instructions than previous methods. Whether the robot was asked to arrange puzzle pieces (Tangrams), stack blocks, or organize a kitchen, VeriGraph rarely made the "physics-breaking" mistakes that other robots made.

In short: VeriGraph gives robots a "checklist" and a "safety net," ensuring they understand how things are connected before they try to move them. It turns a clumsy guesser into a careful, reliable helper.

1. Problem Statement

Robotic manipulation in real-world environments requires understanding complex spatial relationships and physical constraints (e.g., an object cannot be moved if another object is resting on top of it). While recent Vision-Language Models (VLMs) and Large Language Models (LLMs) show promise in task planning, they suffer from two critical limitations:

Lack of Physical Reasoning: Planning directly from raw pixel data often leads to hallucinations or sequences that violate physical constraints (e.g., trying to pick up a book while a cup is on top of it).
Execution Failure: VLMs frequently generate incorrect action sequences that require multiple prompting iterations or human intervention to correct, making them inefficient for long-horizon tasks.

Existing methods either rely on restrictive symbolic representations (like PDDL) that lack generalization or attempt to reason directly from noisy pixel data, failing to explicitly model object relationships.

2. Methodology: VeriGraph Framework

VeriGraph is a modular framework that integrates VLMs for planning with Scene Graphs as an intermediate representation to ensure execution verifiability. The system operates through the following pipeline:

A. Scene Graph Generation

Instead of processing raw images directly for planning, VeriGraph first converts the visual input (initial scene and goal state) into a structured Scene Graph ( $G = \{V, E\}$ ).

Vertices ( $V$ ): Represent objects in the scene.
Edges ( $E$ ): Represent spatial relationships (e.g., on, in, under).
Generator: A VLM (specifically GPT-4V in experiments) generates the graph based on the input image and a global dictionary of object names to handle naming variations.
Goal Specification: The system supports flexible goal inputs, including natural language instructions or reference images. It generates a target scene graph from these inputs.

B. Constraint Validation

Before an action is executed, VeriGraph validates it against the current scene graph state.

Pre-conditions: Checks if an object is accessible (e.g., no other objects are on top of it).
Post-conditions: Ensures the action results in a valid state (e.g., the moved object is supported by a surface).
Graph Operations: Actions are treated as graph edits (removing an edge representing the old support and adding a new one). If an action violates constraints, it is flagged immediately.

C. Iterative Planning with Feedback

The core innovation is an iterative planning loop that replaces single-shot generation:

Proposal: An LLM-based planner proposes a sequence of high-level actions to transform the initial graph ( $G_i$ ) to the goal graph ( $G_g$ ).
Verification: The system simulates the actions on the graph. If a constraint violation is detected, the system generates specific feedback (error message) regarding the violation.
Correction: The feedback is fed back to the planner, which replans the sequence.
Termination: The loop continues until the plan is valid, the goal is reached, or an error threshold is exceeded to prevent infinite loops.

3. Key Contributions

Unified Scene Graph Representation: The paper proposes using scene graphs as both the planning representation and the verification mechanism. This abstracts raw pixels into symbolic relationships, making reasoning about spatial constraints robust and efficient.
Execution-Verifiable Iterative Loop: Unlike prior works that rely on human-in-the-loop or post-hoc visual checks, VeriGraph uses the scene graph to perform real-time constraint validation. This allows the system to automatically detect and correct invalid plans without human intervention.
Flexible Goal Specification: The framework unifies task definition, accepting goals via natural language or reference images, and converting both into a unified scene graph format for planning.
Modular Architecture: The separation of the Scene Graph Generator, Planner, and Verifier allows for the use of different models (e.g., a high-capability VLM for graph generation and a local LLM for planning) to optimize cost and performance.

4. Experimental Results

The authors evaluated VeriGraph on four task groups: Stacking, Language Instruction, Reference Image Instruction, and Tangram Puzzles, across diverse environments (kitchen, tableware, blocks).

Performance Gains:
- Language Tasks: Outperformed the baseline (SayCan) by 58%.
- Tangram Puzzles: Outperformed the baseline (VILA) by 56%.
- Image-Based Tasks: Outperformed baselines by 30%.
Ablation Studies:
- Iterative vs. Direct: The iterative planner with verification significantly outperformed a single-shot ("Direct") planner, proving the value of the feedback loop.
- Error Threshold: An error threshold of 5 provided the best balance between accuracy and computational cost.
- Graph Quality: The system's success is highly correlated with the accuracy of the initial scene graph. When provided with ground-truth graphs, the iterative planner achieved near-perfect success rates, indicating that the planning logic is sound but currently limited by perception errors.

5. Significance and Future Work

Significance:
VeriGraph addresses a fundamental bottleneck in robotic autonomy: the gap between high-level semantic reasoning and low-level physical feasibility. By decoupling visual perception from planning via scene graphs, it enables robots to "think" about spatial constraints before acting, significantly reducing failure rates in complex manipulation tasks. It demonstrates that structured intermediate representations are superior to end-to-end pixel-to-action approaches for tasks requiring logical reasoning.

Limitations & Future Directions:

Perception Dependency: The system's performance is currently bounded by the accuracy of the scene graph generator. Errors in object detection or relationship inference (hallucinations) propagate to the planning stage.
Future Work: Improving the robustness of scene graph generation from monocular images is identified as the primary direction for future research. Additionally, the authors suggest a hybrid deployment strategy where a powerful cloud-based VLM generates the graph, while a local LLM handles the iterative planning to reduce latency and cost.