💻 computer science

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

Dieses Paper stellt EvoPlan vor, ein neuro-symbolisches Framework, das die evolutionäre Suche integriert, um raum-zeitliche Nebenbedingungen aus Demonstrationen zu extrahieren, und diese mit einem evolutionären PDDL-Planer sowie einer kontrollierten Ausführungsschleife kombiniert, um LLM-basierten Robotern die Generierung sicherer, ausführbarer Pläne mit formalen Garantien in Open-World-Umgebungen zu ermöglichen.

Ursprüngliche Autoren: Bhavya Sai Nukapotula, Samin Moosavi, Haoze Wang, Luke Duncan, Diya Shakkottai, Varun Murali, Srinivas Shakkottai

Veröffentlicht 2026-07-09

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Bhavya Sai Nukapotula, Samin Moosavi, Haoze Wang, Luke Duncan, Diya Shakkottai, Varun Murali, Srinivas Shakkottai

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie versuchen, einem Roboter beizubringen, in einer geschäftigen Welt zu navigieren, wie etwa einem Lieferbots in einer Fabrik oder einem selbstfahrenden Auto in einer Stadt. Sie haben zwei Hauptwerkzeuge, um ihm zu helfen, aber beide haben einen entscheidenden Mangel:

Der „Kreative Autor“ (KI/LLM): Dies ist eine kluge KI, die Ihre Anweisungen lesen kann („Gehe zum Cafeteria“) und einen geschickten Plan entwerfen kann. Sie ist großartig darin, Kontext zu verstehen und Fehler zu korrigieren. Das Problem: Sie ist etwas leichtsinnig. Sie erstellt vielleicht einen Plan, der zwar gut klingt, aber physisch unmöglich ist, oder sie fährt versehentlich über eine rote Ampel, weil sie nicht über die Regeln nachgedacht hat.
Der „Strenge Buchhalter“ (Klassische Planer): Dies ist ein starres, regelbasiertes System. Es funktioniert nur, wenn Sie ihm eine perfekte, mathematische Beschreibung der Welt geben. Das Problem: Es ist schrecklich darin, natürliche Sprache zu verstehen oder seine eigenen Fehler zu korrigieren. Wenn sich die Welt auch nur geringfügig verändert, friert es ein.

EvoPlan ist ein neues Framework, das das Beste aus beiden Welten kombiniert. Es nutzt den „Kreativen Autor“, um Pläne zu träumen, und den „Strengen Buchhalter“, um sicherzustellen, dass diese sicher und ausführbar sind. So funktioniert es, unterteilt in drei einfache Schritte:

1. Der „Schatten-Coach“ (Das Lernen der Regeln)

Bevor der Roboter sich überhaupt bewegt, muss das System die „ungeschriebenen Regeln“ der Straße oder des Fabrikbodens lernen.

Das Problem: Die Forscher verfügen nur über Videos von gutem Verhalten (Experten, die sicher fahren, oder Menschen, die höflich gehen). Sie haben keine Videos von schlechtem Verhalten, um dem Roboter zu zeigen, was er nicht tun soll.
Die Lösung: Das System agiert wie ein kreativer Schreibcoach. Es nimmt ein Video einer guten Fahrt und fragt die KI: „Was wäre, wenn der Fahrer beschleunigt hätte? Was wäre, wenn er über eine rote Ampel gefahren wäre?“ Es erfindet diese „schlechten“ Szenarien (Kontrafaktuale), um einen Kontrast zu schaffen.
Das Ergebnis: Durch den Vergleich der „guten“ Videos mit den erfundenen „schlechten“ Szenarien lernt das System ein einziges, universelles Regelwerk (eine sogenannte STL-Constraint). Betrachten Sie dies als einen „Schatten-Coach“, der dem Roboter ins Ohr flüstert: „Fahre niemals schneller als X“ oder „Halte immer Y Meter Abstand zu Menschen“. Dieses Regelwerk gilt für jede Bewegung, die der Roboter macht.

2. Der „Evolutionäre Editor“ (Den Plan erstellen)

Nun muss der Roboter einen Plan erstellen, um von Punkt A nach Punkt B zu gelangen.

Der Prozess: Der „Kreative Autor“ (KI) schlägt einen Plan vor. Aber anstatt ihn einfach zu akzeptieren, durchläuft der Plan einen strengen Editierungsprozess.
Die Schleife:
1. Die KI schreibt einen Entwurf des Plans.
2. Ein „Validator“ (der Buchhalter) prüft ihn. Wenn der Plan fehlerhaft ist (z. B. „Du kannst eine Tür nicht öffnen, die nicht existiert“), markiert der Validator den spezifischen Fehler.
3. Die KI liest den Fehler, korrigiert diesen spezifischen Teil und versucht es erneut.
4. Dies geschieht immer wieder, wie ein Autor, der eine Geschichte verfeinert, bis sie perfekt ist.
Die Magie: Das System behält die „guten Teile“ des Plans, die bereits überprüft wurden, und schreibt nur die defekten Teile um. Mit der Zeit wird der Plan länger und zuverlässiger, bis er vollständig gültig ist.

3. Der „Sicherheits-Gatekeeper“ (Echtzeit-Ausführung)

Schließlich beginnt der Roboter sich zu bewegen. Hier übernehmen der „Schatten-Coach“ und der „Sicherheits-Gatekeeper“ das Kommando.

Die Prüfung: Der Roboter führt den Plan nicht einfach blind aus. Bevor er einen einzigen Schritt macht (oder ein Rad dreht), prüft das System diese spezifische Bewegung gegen das in Schritt 1 gelernte Regelwerk.
Das Sicherheitsnetz:
- Szenario A: Der Roboter plant, nach links abzubiegen. Der Gatekeeper prüft: „Ist dort ein Fußgänger? Ist die Geschwindigkeit sicher?“ Ja. Der Roboter bewegt sich.
- Szenario B: Der Roboter plant, nach links abzubiegen. Der Gatekeeper prüft: „Warte, ein Fußgänger ist zu nah!“ Nein. Der Roboter stoppt sofort.
Die Neuplanung: Wenn der Gatekeeper „Nein“ sagt, stürzt der Roboter nicht ab. Er fixiert alle bereits unternommenen sicheren Schritte, aktualisiert seinen aktuellen Standort und bittet den „Evolutionären Editor“, einen neuen Plan für den Rest der Reise zu schreiben.

Warum das wichtig ist

Die Arbeit zeigt, dass dieses System besser funktioniert, als wenn man nur die KI oder nur die Regeln verwenden würde.

Beim Fahren: Bei Tests mit Fahrdaten reduzierte das System Kollisionen und Rotlichtverstöße signifikant, ohne dass die KI des Fahrers neu trainiert werden musste. Es fügte lediglich ein „Leitplanken“-System hinzu, das schlechte Manöver stoppte.
Bei der Navigation: Bei Tests in komplexen Open-World-Rätseln (wie dem Finden von Objekten in einem Haus) löste das System mehr Aufgaben als andere KI-Planer, selbst wenn die Wörter in den Anweisungen nicht perfekt mit dem Vokabular des Roboters übereinstimmten.

Kurz gesagt: EvoPlan ist ein Roboter-Planungssystem, das KI nutzt, um kreativ und flexibel zu sein, aber den Roboter dazu zwingt, einen „Schutzhelm“ (gelernt aus Daten) und ein „Regelwerk“ (geprüft durch Code) zu tragen, um sicherzustellen, dass er niemals etwas Gefährliches oder Unmögliches tut. Es ist wie ein brillanter, aber impulsiver Fahrer, der ständig von einem sehr strengen, aber sehr klugen Co-Piloten geleitet wird.

Technisches Resümee: EvoPlan

Problemdefinition

Die Arbeit adressiert die Herausforderung, Aufgaben in natürlicher Sprache in teilweise bekannten, dynamischen Umgebungen auszuführen und dabei implizite Normen (z. B. Sicherheitsregeln, soziale Präferenzen) zu erfüllen, die nicht explizit im Aufgaben-Prompt enthalten sind. Die Autoren identifizieren drei Kernschwierigkeiten, die Standardlösungen ineffektiv machen:

Partielle Beobachtbarkeit und Dynamik: Das Weltmodell ist unvollständig, und Agenten-Trajektorien müssen online verfolgt werden, was Planer, die auf vollständig spezifizierten Umgebungen basieren, scheitern lässt.
Unterspezifikation des Prompts: Aufgaben in natürlicher Sprache lassen oft normative Anforderungen aus. Ein Planer, der ausschließlich auf das explizite Ziel optimiert, erfüllt zwar den Prompt, verletzt aber möglicherweise implizite Normen (z. B. das Ziel erreichen, indem man eine rote Ampel missachtet).
One-Class-Daten: Die einzigen verfügbaren Primärdaten bestehen aus unannotierten Einsatzprotokollen, in denen jede aufgezeichnete Spur als „akzeptabel“ gilt. Es gibt keine gelabelten Verstöße, Präferenzpaare oder symbolische Spezifikationen der Normen, was Standardverfahren wie Reward Shaping, Behavior Cloning oder präferenzbasiertes RL unanwendbar macht.

Methodik: Das EvoPlan-Framework

EvoPlan ist ein neuro-symbolisches Framework, das Large Language Models (LLMs) mit formaler Verifizierung und evolutionärer Suche integriert. Es operiert in drei distinkten Phasen:

1. Offline-Constraint-Mining (Evolutionäre STL-Anpassung)

Das System lernt eine einzige globale Signal Temporal Logic (STL)-Constraint, $\Phi_{mob}$ , aus unannotierten Demonstrationsdaten.

Kontrafaktische Synthese: Da die Daten eine One-Class-Struktur aufweisen (alle sind akzeptabel), generiert das System eine negative Klasse ( $D^-$ ) mittels prozeduraler Perturbationen (z. B. überhöhte Geschwindigkeit, Drängeln) und eines LLM-basierten Generator für Verstöße. Dies transformiert das Problem in eine überwachte Klassifikationsaufgabe.
Evolutionäre Suche: Eine LLM-gesteuerte evolutionäre Suche (inspiriert von AlphaEvolve) entwickelt STL-Formeln über eine Grammatik von Signal-Atomen (Geschwindigkeit, Abstand, Kollisionszeit, etc.). Die Fitnessfunktion maximiert die Robustheit auf dem positiven Datensatz ( $D^+$ ) bei gleichzeitiger Minimierung der Erfüllung auf dem negativen Datensatz ( $D^-$ ) und bestraft Komplexität.
Vielseitigkeit: Dieses einzelne Verfahren extrahiert sowohl kodifizierte Regeln (z. B. „Stopp bei roten Ampeln“ aus nuPlan-Logs) als auch populationsbasierte Präferenzen (z. B. sozialer Abstand aus SCAND-Teleoperationsdaten).

2. Evolutionärer PDDL-Plan-Synthese

Das System verwendet einen evolutionären PDDL-Planer, um diskrete Aktionssequenzen zu generieren.

LLM als Vorschlagsmechanismus: Anstatt eines eigenständigen Planers schlägt das LLM PDDL-Pläne vor und repariert diese gegen eine feste Domäne und ein festes Problem.
Validator-Kaskade: Eine programmatische Kaskade (PDDL-Syntaxprüfung, VAL-Simulation, Zielerreichbarkeit und STL-Robustheitsprüfung) bewertet die Kandidaten.
Iterative Reparatur: Das LLM konditioniert seine nächste Mutation auf das spezifische Feedback des Validators (z. B. „Aktion X verletzte Vorbedingung Y“). Dies ermöglicht es, dass der „verifizierte Präfix“ des Plans über Iterationen hinweg monoton wächst.
Robustheit gegenüber Fehlalignments: Das System handhabt Open-World-Szenarien und Vokabular-Fehlstellungen (z. B. Ziel „erhitzt“ vs. Aktion „rösten“) durch die Verwendung eines LLMs zur Ableitung einer Prädikat-Symbol-Map vor der Validierung.

3. Constrained Execution Loop (Eingeschränkte Ausführungsschleife)

Zur Laufzeit überbrückt das System den diskreten PDDD-Plan und die kontinuierliche Robotersteuerung.

Waypoint-Expansion: Jede PDDL-Aktion wird an eine Navigationsschicht (z. B. Nav2) übergeben, welche eine Wegpunkt-Sequenz generiert.
Shielding (Abschirmung): Die Wegpunkt-Sequenz wird gegen die extrahierte globale STL-Constraint $\Phi_{mob}$ geprüft.
Replaning bei Verstößen: Wenn die Sequenz $\Phi_{mob}$ verletzt, wird die Aktion abgelehnt. Das System führt den verifizierten Präfix des Plans aus, aktualisiert den Anfangszustand basierend auf dem aktuellen Weltzustand und ruft den Planer erneut auf, um einen neuen Suffix zu generieren. Dies schafft ein Closed-Loop-System, in dem der Planer nur dann reaktiviert wird, wenn Sicherheit oder Durchführbarkeit gefährdet sind.

Kernbeiträge

Datengetriebenes STL-Mining: Eine Methode zur Extraktion einer einzigen globalen Mobilitäts-Constraint aus One-Class-Demonstrationsdaten durch Synthese kontrafaktischer Negativbeispiele, anwendbar auf regelbasierte sowie präferenzbasierte Domänen.
Evolutionärer PDDL-Solver: Ein Planer, der LLMs für Vorschläge und Reparaturen innerhalb einer formal verifizierten Schleife nutzt und dabei robust gegenüber Vokabular-Fehlstellungen und dem Wachstum von Open-World-Beliefs ist.
Constrained Execution Architektur: Eine Laufzeitschleife, die PDDL-Pläne in Wegpunkte kompiliert, sie gegen gelernte STL-Constraints validiert und bei Verstößen ein Re-Planning auslöst, wodurch Sicherheit gewährleistet wird, ohne die zugrunde liegende Policy neu trainieren zu müssen.
Lokale Bereitstellung: Die gesamte Pipeline, einschließlich aller LLM-Aufrufe, läuft auf einem lokal gehosteten Open-Weight-Modell (Qwen3-32B), was den Einsatz auf dem Roboter ohne Cloud-Abhängigkeit ermöglicht.

Experimentelle Ergebnisse

Die Autoren evaluieren das Framework über drei Benchmarks hinweg:

STL-Constraint-Transfer (Shielding):
- Fahren (nuPlan $\to$ Bench2Drive): Die extrahierte regelbasierte Constraint reduzierte Ampelverstöße um 77 % und Kollisionen um 71 % bei einer Qwen2.5-VL Fahr-Policy, was den Driving Score verbesserte.
- Soziale Navigation (SCAND $\to$ HA-VLN-CE): Die extrahierte präferenzbasierte Constraint reduzierte vermeidbare Kontakte um 82 % (PointNav) und 93 % (MLP) bei Indoor-Navigationsaufgaben und komprimierte effektiv den „unsicheren Schwanz“ der Sicherheitsverteilungen.
Planungsleistung (ALFWorld Text):
- Auf dem Open-World ALFText-Benchmark erreichte EvoPlan eine Erfolgsrate von 98,5 % bei ungesehenen Aufgaben und übertraf damit starke Baselines (z. B. NL-PDDL mit 94 %, direkte LLMs mit ~20 %).
- Entscheidend ist, dass es diese Leistung (98,5 %) beibehielt, selbst wenn das Ziel-Vokabular nicht mit dem Aktions-Modell-Vokabular übereinstimmte, während andere Methoden signifikant abfielen.
- Es löste Aufgaben mit optimalen Plänen, deren Tiefe 10 überschreitet, wo Fixed-Horizon-Planer versagten.
End-to-End Ausführung (Gazebo):
- In einer simulierten Fabrikumgebung mit 9–15 Fußgängern schloss das System Pick-and-Drop-Missionen mit kontrollierter Degradierung ab. Während eine Mission aufgrund extremer Dichte fehlschlug, hielt das System in vier von fünf Durchläufen eine geringe Exposition gegenüber dem persönlichen Raum auf und vermied Kollisionen durch Re-Planning, sobald die Clearance-Grenzwerte verletzt wurden.

Bedeutung und Behauptungen

Das Paper behauptet, dass EvoPlan einen „Best-of-Both-Worlds“-Ansatz bietet: Es nutzt die Flüssigkeit und Kontextsensitivität von LLMs für die Generierung und Reparatur von Plänen, während es sich auf symbolische Validierung und aus Daten abgeleitete temporale Logik verlässt, um Ausführbarkeit und Sicherheit zu garantieren.

Die Autoren betonen, dass das System neuronale Modelle als Generatoren von Kandidaten behandelt und nicht als unkontrollierte Autoritäten. Durch das Lernen von Constraints direkt aus unannotierten Einsatzprotokollen vermeidet das Framework die Notwendigkeit manuell geschriebener Sicherheits-Spezifikationen oder gelabelter Verstöße. Die Ergebnisse legen nahe, dass dieser neuro-symbolische Kreislauf robust gegenüber Open-World-Dynamiken und Vokabular-Fehlstellungen ist und einen Pfad für den Einsatz sicherer, adaptiver Roboter-Planer eröffnet, die keine Cloud-Infrastruktur benötigen.