💻 computer science

EvoPlan: Evolutionary Neuro-Symbolic Robot Planning with Spatio-Temporal Guarantees

This paper introduces EvoPlan, a neuro-symbolic framework that integrates evolutionary search to mine spatio-temporal constraints from demonstrations and combines them with an evolutionary PDDL planner and constrained execution loop to enable LLM-based robots to generate safe, executable plans with formal guarantees in open-world environments.

Original authors: Bhavya Sai Nukapotula, Samin Moosavi, Haoze Wang, Luke Duncan, Diya Shakkottai, Varun Murali, Srinivas Shakkottai

Published 2026-07-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Bhavya Sai Nukapotula, Samin Moosavi, Haoze Wang, Luke Duncan, Diya Shakkottai, Varun Murali, Srinivas Shakkottai

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 robot to navigate a busy world, like a delivery bot in a factory or a self-driving car in a city. You have two main tools to help it, but both have a major flaw:

The "Creative Writer" (AI/LLM): This is a smart AI that can read your instructions ("Go to the cafeteria") and come up with a clever plan. It's great at understanding context and fixing mistakes. The problem: It's a bit reckless. It might come up with a plan that sounds good but is physically impossible, or it might accidentally drive through a red light because it didn't "think" about the rules.
The "Strict Accountant" (Classical Planners): This is a rigid, rule-based system. It only works if you give it a perfect, mathematical description of the world. The problem: It's terrible at understanding natural language or fixing its own mistakes. If the world changes slightly, it freezes.

EvoPlan is a new framework that combines the best of both worlds. It uses the "Creative Writer" to dream up plans and the "Strict Accountant" to make sure they are safe and executable. Here is how it works, broken down into three simple steps:

1. The "Shadow Coach" (Learning the Rules)

Before the robot ever moves, the system needs to learn the "unwritten rules" of the road or the factory floor.

The Problem: The researchers only have videos of good behavior (experts driving safely or people walking politely). They don't have videos of bad behavior to show the robot what not to do.
The Solution: The system acts like a creative writing coach. It takes a video of a good drive and asks the AI: "What if the driver sped up? What if they ran a red light?" It invents these "bad" scenarios (counterfactuals) to create a contrast.
The Result: By comparing the "good" videos against the invented "bad" ones, the system learns a single, universal rulebook (called an STL constraint). Think of this as a "Shadow Coach" that whispers in the robot's ear: "Never go faster than X," or "Always stay Y meters away from people." This rulebook applies to every move the robot makes.

2. The "Evolutionary Editor" (Building the Plan)

Now, the robot needs a plan to get from Point A to Point B.

The Process: The "Creative Writer" (AI) proposes a plan. But instead of just accepting it, the system puts it through a rigorous editing process.
The Loop:
1. The AI writes a draft plan.
2. A "Validator" (the accountant) checks it. If the plan is broken (e.g., "You can't open a door that doesn't exist"), the validator marks the specific error.
3. The AI reads the error, fixes that specific part, and tries again.
4. This happens over and over, like a writer refining a story until it's perfect.
The Magic: The system keeps the "good parts" of the plan that have already been checked and only rewrites the broken parts. Over time, the plan grows longer and more reliable until it is fully valid.

3. The "Safety Gatekeeper" (Real-Time Execution)

Finally, the robot starts moving. This is where the "Shadow Coach" and the "Safety Gatekeeper" take over.

The Check: The robot doesn't just execute the plan blindly. Before it takes a single step (or turns a wheel), the system checks that specific movement against the rulebook learned in Step 1.
The Safety Net:
- Scenario A: The robot plans to turn left. The Gatekeeper checks: "Is there a pedestrian there? Is the speed safe?" Yes. The robot moves.
- Scenario B: The robot plans to turn left. The Gatekeeper checks: "Wait, a pedestrian is too close!" No. The robot stops immediately.
The Re-Plan: If the Gatekeeper says "No," the robot doesn't crash. It locks in all the safe steps it has already taken, updates its current location, and asks the "Evolutionary Editor" to write a new plan for the rest of the journey.

Why This Matters

The paper shows that this system works better than using just the AI or just the rules.

In Driving: When tested on driving data, the system reduced collisions and red-light violations significantly without needing to retrain the driver AI. It just added a "guardrail" that stopped bad moves.
In Navigation: When tested in complex, open-world puzzles (like finding objects in a house), the system solved more tasks than other AI planners, even when the words used in the instructions didn't perfectly match the robot's vocabulary.

In short: EvoPlan is a robot planning system that uses AI to be creative and flexible, but forces it to wear a "safety helmet" (learned from data) and a "rulebook" (checked by code) to ensure it never does anything dangerous or impossible. It's like having a brilliant but impulsive driver who is constantly guided by a very strict, very smart co-pilot.

Technical Summary: EvoPlan

Problem Definition

The paper addresses the challenge of executing natural-language robot tasks in partially known, dynamic environments while satisfying implicit norms (e.g., safety rules, social preferences) that are not explicitly stated in the task prompt. The authors identify three core difficulties that render standard solutions ineffective:

Partial Observability and Dynamics: The world model is incomplete, and agent trajectories must be tracked online, causing planners relying on fully specified environments to fail.
Prompt Underspecification: Natural language tasks often omit normative requirements. A planner optimizing solely for the explicit goal may satisfy the prompt while violating implicit norms (e.g., reaching a destination by running a red light).
One-Class Data: The only available prior data consists of unannotated operation logs where every recorded trace is "acceptable." There are no labeled violations, preference pairs, or symbolic specifications of the norms, rendering standard reward shaping, behavior cloning, or preference-based RL inapplicable.

Methodology: The EvoPlan Framework

EvoPlan is a neuro-symbolic framework that integrates Large Language Models (LLMs) with formal verification and evolutionary search. It operates in three distinct stages:

1. Offline Constraint Mining (Evolutionary STL Fitting)

The system learns a single global Signal Temporal Logic (STL) constraint, $\Phi_{mob}$ , from unannotated demonstration data.

Counterfactual Synthesis: Since the data is one-class (all acceptable), the system generates a negative class ( $D^-$ ) using procedural perturbations (e.g., speeding, crowding) and an LLM-based violation generator. This transforms the problem into a supervised classification task.
Evolutionary Search: An LLM-driven evolutionary search (inspired by AlphaEvolve) evolves STL formulas over a grammar of signal atoms (speed, clearance, time-to-collision, etc.). The fitness function maximizes robustness on the positive set ( $D^+$ ) while minimizing satisfaction on the negative set ( $D^-$ ), penalizing complexity.
Versatility: This single procedure recovers both codified rules (e.g., "stop at red lights" from nuPlan logs) and population preferences (e.g., social spacing from SCAND teleoperation data).

2. Evolutionary PDDL Plan Synthesis

The system employs an Evolutionary PDDL Planner to generate discrete action sequences.

LLM as Proposal Mechanism: Instead of a standalone planner, the LLM proposes and repairs PDDL plans against a fixed domain and problem.
Validator Cascade: A programmatic cascade (PDDL syntax check, VAL simulation, goal reachability, and STL robustness check) scores candidates.
Iterative Repair: The LLM conditions its next mutation on the specific feedback from the validator (e.g., "action X failed precondition Y"). This allows the "verified prefix" of the plan to grow monotonically over iterations.
Robustness to Misalignment: The system handles open-world scenarios and vocabulary misalignment (e.g., goal "heated" vs. action "toast") by using an LLM to derive a predicate-symbol map before validation.

3. Constrained Execution Loop

At runtime, the system bridges the discrete PDDL plan and continuous robot execution.

Waypoint Expansion: Each PDDL action is dispatched to a navigation layer (e.g., Nav2) which generates a waypoint sequence.
Shielding: The waypoint sequence is checked against the mined global STL constraint $\Phi_{mob}$ .
Replanning on Violation: If the sequence violates $\Phi_{mob}$ , the action is rejected. The system commits the verified prefix of the plan, updates the initial state based on the current world state, and re-invokes the planner to generate a new suffix. This creates a closed-loop system where the planner is re-activated only when safety or feasibility is compromised.

Key Contributions

Data-Driven STL Mining: A method to extract a single global mobility constraint from one-class demonstration data by synthesizing counterfactual negatives, applicable to both rule-based and preference-based domains.
Evolutionary PDDL Solver: A planner that uses LLMs for proposal and repair within a formally verified loop, demonstrating robustness to vocabulary misalignment and open-world belief growth.
Constrained Execution Architecture: A runtime loop that compiles PDDL plans into waypoints, validates them against learned STL constraints, and triggers replanning upon violation, ensuring safety without retraining the underlying policy.
Local Deployment: The entire pipeline, including all LLM calls, runs on a locally hosted open-weight model (Qwen3-32B), enabling on-robot deployment without cloud dependency.

Experimental Results

The authors evaluate the framework across three benchmarks:

STL Constraint Transfer (Shielding):
- Driving (nuPlan $\to$ Bench2Drive): The mined rule-based constraint reduced red-light infractions by 77% and collisions by 71% on a Qwen2.5-VL driving policy, improving the overall Driving Score.
- Social Navigation (SCAND $\to$ HA-VLN-CE): The mined preference-based constraint reduced avoidable contacts by 82% (PointNav) and 93% (MLP) on indoor navigation tasks, effectively compressing the "unsafe tail" of safety distributions.
Planning Performance (ALFWorld Text):
- On the open-world ALFText benchmark, EvoPlan achieved 98.5% success rate on unseen tasks, outperforming strong baselines (e.g., NL-PDDL at 94%, Direct LLMs at ~20%).
- Crucially, it maintained this performance (98.5%) even when the goal vocabulary did not match the action-model vocabulary, whereas other methods dropped significantly.
- It solved tasks with optimal plans exceeding depth 10, where fixed-horizon planners failed.
End-to-End Execution (Gazebo):
- In a simulated factory environment with 9–15 pedestrians, the system completed pick-and-drop missions with graceful degradation. While one mission failed due to extreme density, the system maintained low personal-space exposure and avoided collisions in four out of five runs by replanning when clearance floors were violated.

Significance and Claims

The paper claims that EvoPlan offers a "best-of-both-worlds" approach: it leverages the fluency and context-awareness of LLMs for plan generation and repair while relying on symbolic validation and data-derived temporal logic to guarantee executability and safety.

The authors emphasize that the system treats neural models as generators of candidates rather than sources of unchecked authority. By learning constraints directly from unannotated operational logs, the framework avoids the need for manually written safety specifications or labeled violation data. The results suggest that this neuro-symbolic loop is robust to open-world dynamics and vocabulary misalignment, providing a pathway for deploying safe, adaptive robot planners that do not require cloud infrastructure.