GenePlan: Evolving Better Generalized PDDL Plans using Large Language Models

Das Paper stellt GenePlan vor, ein Framework, das große Sprachmodelle mit evolutionären Algorithmen kombiniert, um effiziente und generalisierbare PDDL-Planer zu entwickeln, die in Benchmarks mit dem Stand der Technik mithalten und deutlich besser abschneiden als andere LLM-basierte Ansätze.

Das Wesentliche

Stellen Sie sich vor, Sie müssen einem sehr klugen, aber manchmal etwas chaotischen Assistenten beibringen, wie man komplexe Aufgaben löst – zum Beispiel, wie man in einem riesigen Lagerhaus die richtigen Pakete findet und verpackt, ohne dabei gegen Regale zu laufen.

Das ist im Grunde das, was die Forscher von J.P. Morgan mit ihrer neuen Methode namens GenePlan getan haben. Hier ist die Erklärung, wie das funktioniert, ohne den technischen Fachjargon:

1. Das Problem: Der Assistent ist schlau, aber nicht perfekt

Große Sprachmodelle (wie die KI, die Sie gerade lesen) sind genial im Schreiben von Texten oder Code. Aber wenn es darum geht, logische Pläne zu erstellen (z. B. "Geh zuerst hierhin, dann nimm das, dann geh dorthin"), machen sie oft Fehler oder finden sehr lange, ineffiziente Wege. Es ist, als würde man einem Menschen sagen: "Bringe mir ein Glas Wasser", und er läuft erst durch das ganze Haus, macht einen Umweg durch den Garten und kommt dann zurück, nur um festzustellen, dass er das Glas schon in der Hand hatte.

2. Die Lösung: Ein evolutionärer "Trainingscamp"-Ansatz

GenePlan nutzt eine Idee aus der Biologie: Evolution. Statt dem KI-Assistenten einfach nur eine Aufgabe zu geben und zu hoffen, dass er sie richtig macht, lassen die Forscher ihn in einem digitalen Trainingscamp durchlaufen.

Stellen Sie sich das wie einen Talent-Show-Wettbewerb vor:

• Die Kandidaten (Die Pläne): Die KI generiert viele verschiedene Python-Programme (das sind die "Pläne"). Jeder Kandidat versucht, ein Problem zu lösen.
• Der Trainer (Die Bewertung): Jedes Programm wird getestet. Wenn es einen Plan findet, der zu kurz ist (wenige Schritte), bekommt es eine hohe Punktzahl. Wenn es scheitert oder zu viele Schritte braucht, bekommt es eine schlechte Note.
• Die Züchtung (Evolution): Die schlechtesten Kandidaten werden rausgeworfen. Die besten Kandidaten werden "gekreuzt". Das bedeutet, die KI nimmt die besten Teile von Programm A und die besten Teile von Programm B und mischt sie zu einem neuen, noch besseren Programm C.
• Die Mutation: Manchmal fügt die KI auch zufällige kleine Änderungen hinzu, um neue, kreative Lösungen zu finden (wie eine zufällige Genmutation in der Natur).

Dieser Prozess wiederholt sich Generation für Generation. Am Ende bleibt nur der "Super-Kandidat" übrig – ein Programm, das die Aufgabe extrem effizient löst.

3. Der Clou: Es lernt eine "Regel", nicht nur eine Antwort

Frühere Methoden haben oft versucht, für ein spezifisches Problem eine Antwort zu finden. GenePlan ist anders. Es lernt eine allgemeine Regel (einen "General Planner").

• Analogie:
  • Alte Methode: Der Assistent lernt auswendig: "Wenn ich im Zimmer A bin und das Ziel im Zimmer B ist, gehe ich links." Das funktioniert nur für dieses eine Zimmer.
  • GenePlan: Der Assistent lernt das Prinzip: "Wenn ich ein Ziel habe, suche ich den kürzesten Weg dorthin und vermeide Hindernisse." Damit kann er jedes neue Zimmer meistern, das er noch nie gesehen hat, und zwar sofort.

4. Warum ist das so cool?

• Geschwindigkeit: Sobald das "Super-Programm" einmal trainiert ist (was ein paar Minuten dauert und nur wenige Dollar kostet), kann es neue Probleme in weniger als einer halben Sekunde lösen. Das ist wie ein Rennwagen, der nach dem Startschuss sofort losfährt, während andere erst den Motor anlassen müssen.
• Qualität: Die Ergebnisse sind so gut wie die der besten menschlichen Experten, die jahrelang an solchen Algorithmen gearbeitet haben.
• Verständlichkeit: Da das Ergebnis ein Python-Code ist, können Menschen ihn lesen und verstehen. Man sieht genau, warum die KI so entschieden hat. Es ist keine "Black Box".

Zusammenfassung in einem Satz

GenePlan ist wie ein digitaler Darwin, der Tausende von KI-Vorschlägen durchlässt, die schlechten eliminiert und die besten kombiniert, bis ein perfekter, schneller und verständlicher "Meister-Planer" übrig bleibt, der jede neue Herausforderung in einem bestimmten Bereich meistern kann.

Es ist der Beweis dafür, dass man KI nicht nur fragen, sondern sie durch gezieltes "Training" und "Selektion" zu einem echten Problemlöser machen kann.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papers „GenePlan: Evolving Better Generalized PDDL Plans using Large Language Models" auf Deutsch:

1. Problemstellung

Das Paper adressiert die Herausforderung der generalisierten Planung (Generalized Planning) im Kontext klassischer Planungsaufgaben, die in der PDDL (Planning Domain Definition Language) definiert sind.

• Hintergrund: Während Large Language Models (LLMs) in vielen Bereichen erfolgreich sind, zeigen sie bei sequenziellen Entscheidungsaufgaben wie der Planung oft suboptimale Ergebnisse. Bisherige Ansätze, die LLMs nutzen, um Python-Planner für generalisierte Planung zu generieren (z. B. mittels Chain-of-Thought-Prompting), konzentrieren sich oft nur auf die Erzeugung gültiger Lösungen („satisficing"), ohne die Qualität (z. B. Planlänge) zu optimieren.
• Ziel: Es soll ein generalisierter Planer (ein Python-Programm) entwickelt werden, der für eine Domäne nicht nur eine Lösung für ein spezifisches Problem findet, sondern eine Strategie generiert, die über viele verschiedene Probleminstanzen hinweg minimale Planlängen (optimale Kosten) erzielt.
• Herausforderung: Die Suche nach einem optimalen Python-Code, der als Heuristik oder Strategie dient, ist ein komplexer Suchraum, der für traditionelle Optimierungsmethoden schwer zugänglich ist.

2. Methodik: GenePlan

Die Autoren stellen GenePlan (GENeralized Evolutionary Planner) vor, ein Framework, das evolutionäre Algorithmen mit LLMs kombiniert, um generalisierte Planer zu optimieren.

• Formulierung als Optimierungsproblem:
  Das Problem wird als Minimierung der durchschnittlichen Planlänge über einen Trainingsdatensatz von PDDL-Instanzen definiert:
  $$\arg \min_{\Phi} \frac{1}{|\Pi_{train}|} \sum_{\Pi \in \Pi_{train}} |\Phi(\Pi)|$$
  wobei $\Phi$ der zu findende Python-Planner ist.

• Evolutionärer Zyklus:
  GenePlan nutzt einen evolutionären Ansatz, bei dem eine Population von Kandidaten-Plannern (Python-Methoden) iterativ verbessert wird:

  1. Initialisierung: Die Population wird mit einem Seed-Planner (z. B. generiert durch Chain-of-Thought) oder zufälligem Code initialisiert.
  2. Bewertung (Fitness): Jeder Kandidat wird auf den Trainingsinstanzen ausgeführt. Die Fitness-Funktion berechnet die durchschnittliche Planlänge. Ungültige Pläne erhalten eine hohe Strafpunktzahl.
  3. Selektion: Basierend auf der Fitness werden Eltern-Planner ausgewählt. GenePlan verwendet eine temperaturbasierte Boltzmann-Selektion, bei der die Temperatur $T$ im Laufe der Generationen hyperbolisch abnimmt. Dies fördert zu Beginn die Exploration (Vielfalt) und später die Exploitation (Verfeinerung der besten Lösungen).
  4. Crossover & Mutation durch LLM: Anstatt traditioneller bitweiser Operatoren nutzt GenePlan das LLM, um neue Kandidaten zu generieren. Das LLM erhält einen Prompt, der die besten aktuellen Planner (Eltern), deren Code, Fehlermeldungen und die Domänenbeschreibung enthält. Das LLM wird angewiesen, durch „Crossover" (Kombination von Komponenten) und „Mutation" (strategische Änderungen) einen besseren Heuristik-Code zu erzeugen.
  5. Validierung & AST-Parsing: Der vom LLM generierte Code wird vor der Ausführung durch einen AST-Parser (Abstract Syntax Tree) validiert, um sicherzustellen, dass nur erlaubte Bibliotheken und Funktionen verwendet werden (Safety Guardrails).
  6. Ersetzung (Replacement): Nach Erreichen einer maximalen Anzahl an Nachkommen ($\lambda$) wird die Population aktualisiert. Es wird eine elitäre Ersetzungsstrategie ($\mu + \lambda$) verwendet: Die besten $\mu$ Planner aus der Kombination der alten und neuen Generation bilden die nächste Generation.

• Output: Am Ende des Prozesses wird der beste gefundene Python-Planner extrahiert, der dann neue, unbekannte PDDL-Instanzen in Echtzeit lösen kann.

3. Wichtige Beiträge

• Neues Framework: GenePlan ist das erste Framework, das evolutionäre Optimierung mit LLMs kombiniert, um generalisierte PDDL-Planer zu erzeugen, die explizit auf Planqualität (Länge) optimiert sind.
• Interpretierbarkeit: Im Gegensatz zu reinen Black-Box-LLM-Antworten erzeugt GenePlan interpretierbaren Python-Code, der die Logik der Strategie offenlegt.
• Effizienz: Der einmalige Generierungsaufwand (ca. 645 Sekunden pro Domäne) wird durch extrem schnelle Inferenzzeiten (ca. 0,49 Sekunden pro neuer Instanz) kompensiert.
• Kosten-Nutzen-Analyse: Die Methode ist kosteneffizient (durchschnittlich 1,82 $ pro Domäne mit GPT-4o) und übertrifft reine Prompting-Methoden deutlich.

4. Ergebnisse

Die Autoren evaluierten GenePlan auf 8 Domänen (6 bekannte Benchmarks + 2 neue Domänen: Trading und Research) und verglichen sie mit 10 Baselines, darunter:

• State-of-the-Art-Planer (Fast Downward mit verschiedenen Zeitlimits: 300s, 1800s, optimal).
• LLM-Baselines (Chain-of-Thought mit GPT-4 und GPT-4o).
• Ablationsstudien (z. B. ohne Evaluierung, mit abstrahierten Namen).

Kernergebnisse:

• Planqualität: GenePlan erreichte eine durchschnittliche SAT-Score von 0,91. Dies ist nahezu gleichauf mit dem State-of-the-Art-Planer Fast Downward (30-min-Limit, Score 0,93) und deutlich besser als Chain-of-Thought-Prompting (Score 0,64).
• Lösungsrate: GenePlan löste in allen getesteten Domänen 100 % der Testinstanzen (im Gegensatz zu Fast Downward Optimal, das in komplexen Domänen oft scheiterte, da es innerhalb der Zeitlimits keine optimale Lösung fand).
• Geschwindigkeit: Die generierten Python-Planner lösen neue Instanzen im Durchschnitt in 0,49 Sekunden, was signifikant schneller ist als die Suche durch Fast Downward.
• Kosten: Die Generierung eines Planers kostete durchschnittlich nur 1,82 $ pro Domäne.
• Ablationsstudien:
  • Die Verwendung von natürlichen Domänenzusammenfassungen statt des vollständigen PDDL-Domänen-Textes führte in komplexen Domänen zu schlechteren Ergebnissen (Bedeutung des Kontexts).
  • Das Entfernen spezifischer Namen (Ablation) führte zum kompletten Scheitern, was die Abhängigkeit von semantischem Kontext für LLMs unterstreicht.
  • Ohne Evaluierung (konstante Scores) konnte keine Optimierung stattfinden.

5. Bedeutung und Ausblick

• Paradigmenwechsel: Das Paper zeigt, dass LLMs nicht nur als direkte Problemlöser, sondern als Optimierer innerhalb evolutionärer Schleifen eingesetzt werden können, um hochleistungsfähige, domänenspezifische Algorithmen zu synthetisieren.
• Praktische Anwendbarkeit: Da die einmalige Generierung eines Planers kostengünstig ist und dieser dann extrem schnell neue Probleme löst, eignet sich GenePlan ideal für Szenarien mit wiederkehrenden Planungsaufgaben in derselben Domäne.
• Grenzen: In Domänen ohne einfache generalisierbare Strategie (z. B. Sokoban, wo irreversible Zustände vermieden werden müssen) scheitert der Ansatz, da er keine vollständige Suche durchführt. Hier bleibt die Integration von LLMs als Orchestrierungsschicht für traditionelle Suchalgorithmen ein wichtiger Ausweg.
• Zukunft: Die Autoren schlagen vor, frühe Stoppkriterien zu entwickeln, um die Generierungskosten weiter zu senken, und die Methode zur Generierung von Heuristiken für existierende Suchalgorithmen zu nutzen.

Zusammenfassend demonstriert GenePlan, dass die Kombination aus evolutionärer Suche und LLMs einen vielversprechenden Weg darstellt, um interpretierbare, hochwertige und effiziente Planer für klassische KI-Planungsaufgaben zu automatisieren.