On Sample-Efficient Generalized Planning via Learned Transition Models

Diese Arbeit zeigt, dass die Formulierung von generalisierter Planung als Lernproblem für explizite Übergangsmodelle, die Weltzustände autoregressiv vorhersagen, im Vergleich zu direkten Aktionssequenzvorhersagen eine bessere Out-of-Distribution-Generalisierung bei deutlich geringerem Daten- und Modellbedarf ermöglicht.

Das Wesentliche

Stell dir vor, du möchtest einem Roboter beibringen, wie man ein Haus aufräumt.

Das alte Problem: Auswendiglernen statt Verstehen
Bisherige KI-Methoden (wie die im Papier erwähnten "Transformer") funktionieren eher wie ein Schüler, der nur die Lösungen für bestimmte Hausaufgaben auswendig gelernt hat.

• Wenn der Schüler 5 Blöcke aufräumen muss, kennt er die Lösung.
• Aber wenn du ihn vor 20 Blöcke stellst, gerät er in Panik. Er versucht, die Reihenfolge der Bewegungen zu erraten, ohne wirklich zu verstehen, was passiert, wenn er einen Block bewegt.
• Das nennt man "Zustands-Drift": Der Roboter glaubt, der Block sei woanders, als er es tatsächlich ist, weil er die physikalischen Regeln der Welt nicht wirklich verstanden hat, sondern nur Muster in den Befehlslisten erkannt hat. Er braucht dafür riesige Datenmengen und extrem große "Gehirne" (Modelle).

Die neue Lösung: Den Roboter zum "Welt-Versteher" machen
Die Autoren dieses Papiers schlagen einen anderen Weg vor. Statt dem Roboter nur zu sagen: "Mach jetzt Schritt 1, dann Schritt 2", lassen sie ihn lernen, wie die Welt sich verändert.

Stell dir das so vor:

1. Der alte Weg (Aktion-zentriert): Der Roboter lernt eine Liste: "Wenn ich den Ball nehme, muss ich ihn in die Box legen." Er lernt die Befehle.
2. Der neue Weg (Zustands-zentriert): Der Roboter lernt die Physik. Er lernt: "Wenn ich den Ball nehme, verschwindet er von der Hand und erscheint in der Box." Er lernt, wie sich der Zustand der Welt verändert.

Wie funktioniert das genau? (Die Analogie)

Stell dir vor, du hast einen sehr klugen Assistenten, der ein Wettervorhersage-Modell ist.

• Der alte Ansatz: Der Assistent sagt dir einfach: "Morgen regnet es, nimm einen Regenschirm. Übermorgen scheint die Sonne, zieh T-Shirt an." Er sagt dir nur, was du tun sollst, basierend auf dem, was er in der Vergangenheit gesehen hat.
• Der neue Ansatz (dieses Papier): Der Assistent lernt, wie sich das Wetter entwickelt. Er sagt: "Wenn es heute 20 Grad sind und die Luftfeuchtigkeit steigt, wird es morgen wahrscheinlich regnen." Er simuliert die Zukunft im Kopf, bevor er dir einen Ratschlag gibt.

In der KI heißt das:

1. Lernen der Übergänge: Das Modell lernt eine Funktion, die vorhersagt: "Wenn ich mich in Zustand A befinde und Aktion X ausführe, lande ich in Zustand B."
2. Rollout (Durchspielen): Anstatt sofort einen Befehl zu geben, "rollt" das Modell die Zukunft im Kopf durch. Es sagt: "Okay, wenn ich das mache, sieht die Welt so aus. Wenn ich dann das mache, sieht sie so aus..."
3. Der Sicherheits-Check (Neuro-Symbolisch): Hier kommt der Clou. Das Modell ist nicht perfekt. Es könnte sich irren. Deshalb gibt es einen strengen "Korrektor" (einen klassischen Symbol-Planer).
   • Das KI-Modell sagt: "Ich denke, der Block ist jetzt hier."
   • Der Korrektor prüft: "Stimmt das? Ja, das ist physikalisch möglich." -> Okay, führe die Aktion aus.
   • Der Korrektor prüft: "Nein, das ist unmöglich." -> Ignoriere die KI, suche einen anderen Weg.

Warum ist das so toll?

• Sparsamkeit: Das neue Modell ist winzig (wie ein Taschenrechner) im Vergleich zu den alten Riesen (wie einem Supercomputer). Es braucht viel weniger Daten zum Lernen.
• Größen-Unabhängigkeit: Das ist der wichtigste Punkt.
  • Stell dir vor, du hast gelernt, wie man mit 3 Lego-Steinen baut.
  • Die alten Modelle scheitern, wenn du 100 Steine hast, weil sie die Liste der 3 Steine auswendig gelernt haben.
  • Das neue Modell hat gelernt, wie Steine aufeinander liegen. Es ist egal, ob es 3 oder 300 Steine sind. Die Regel "Stein A liegt auf Stein B" gilt immer. Das nennt man "Größen-Invarianz".
• Bessere Generalisierung: Weil es die Regeln der Welt (die "Physik") lernt und nicht nur die Antworten, kann es Probleme lösen, die es noch nie gesehen hat (z. B. viel größere Räume oder mehr Objekte).

Das Ergebnis
Die Autoren haben gezeigt, dass dieser Ansatz in vielen Fällen (wie beim Aufräumen von Blöcken oder beim Navigieren in einem Raum) viel besser funktioniert als die riesigen, teuren Modelle, die nur Befehle auswendig lernen. Sie erreichen fast die gleiche Leistung wie ein klassischer, perfekter Planer, aber mit einem winzigen, effizienten Modell, das auf wenigen Beispielen lernt.

Zusammenfassung in einem Satz:
Statt einem Roboter eine lange Liste von Befehlen auswendig zu lernen, geben wir ihm ein kleines Gehirn, das versteht, wie die Welt funktioniert, damit er sich jede neue Situation selbst ausdenken kann – egal wie groß sie ist.

Technische Zusammenfassung

1. Problemstellung

Das Paper adressiert das Problem des generalisierten Planens (Generalized Planning, GP). Ziel ist es, Strategien zu entwickeln, die nicht nur für ein einzelnes Problem, sondern für ganze Familien von Planungsproblemen innerhalb einer Domäne funktionieren, unabhängig von der Anzahl der Objekte (Größeninvarianz).

• Herausforderung: Klassische Ansätze nutzen symbolische Abstraktionen, während neuere lernbasierte Methoden (wie PlanGPT, Plansformer) oft als aktionszentrierte Sequenzvorhersage formuliert werden. Diese Transformer-basierten Modelle sagen direkt die nächste Aktion voraus, ohne den Weltzustand explizit zu modellieren.
• Schwächen bestehender Ansätze:
  • Sie benötigen riesige Datensätze und sehr große Modelle (Milliarden von Parametern).
  • Sie leiden unter Zustandsdrift (State Drift) in langfristigen Szenarien, da sie keine explizite Weltzustandsentwicklung verfolgen.
  • Ihre Generalisierungsfähigkeit auf Out-of-Distribution (OOD) Instanzen (z. B. deutlich mehr Objekte als im Training) ist oft gering.

2. Methodik: Zustandszentriertes Lernen von Übergangsmodellen

Die Autoren schlagen einen Paradigmenwechsel vor: Statt Aktionen direkt vorherzusagen, formulieren sie GP als Lernproblem für ein Übergangsmodell (Transition Model).

Kernkonzept

Anstatt $p(\pi | \Pi)$ (Wahrscheinlichkeit eines Plans gegeben das Problem) zu modellieren, lernt das System eine zielbedingte neuronale Übergangsfunktion $T_\theta(s_t, g) \approx \hat{s}_{t+1}$.

1. Vorhersage: Das Modell sagt den nächsten Weltzustand voraus, basierend auf dem aktuellen Zustand und dem Ziel.
2. Planung: Ein Plan wird generiert, indem die vorhergesagte Zustandsbahn (Rollout) simuliert wird.
3. Neuro-symbolische Decodierung: Da das neuronale Modell nur einen Embedding-Vektor vorhersagt, wird dieser mit allen gültigen symbolischen Nachfolgern (basierend auf den Domänenoperatoren) verglichen. Der symbolische Nachfolger, dessen Embedding dem Vorhersagevektor am nächsten liegt, wird ausgewählt. Dies garantiert die symbolische Validität jedes Schritts.

Technische Details

• Zustandsrepräsentation (Size-Invariance): Um Probleme mit variabler Objektanzahl zu lösen, werden Weisfeiler-Leman (WL) Graph-Embeddings verwendet. Diese wandeln relationale Zustandsgraphen in festdimensionale Vektoren um, die invariant gegenüber Permutationen und der Größe des Objektsatzes sind.
• Residuelle Modellierung: Da STRIPS-Übergänge oft spärlich sind (die meisten Prädikate bleiben gleich), wird ein Delta-Ansatz gewählt: $\hat{\phi}(s_{t+1}) = \phi(s_t) + f_\theta(\phi(s_t), \phi(g))$. Das Modell lernt nur die Änderung ($\Delta$), was die Lernstabilität und Sample-Effizienz erhöht.
• Architekturen: Es werden zwei Klassen von Modellen verglichen:
  • Parametrisch: Ein 2-Schichten LSTM (für sequenzielle Abhängigkeiten).
  • Nicht-parametrisch: XGBoost (Gradient Boosting), um zu testen, ob lokale Approximationen ausreichen.

3. Wichtige Beiträge

1. Formulierung: Eine neue Formulierung des generalisierten Planens als Problem des Lernens von Übergangsmodellen mit zielbedingter Nachfolgezustandsvorhersage.
2. Systematische Evaluation: Eine umfassende Analyse verschiedener Zustandsrepräsentationen (WL vs. Fixed-Size Factored) und Architekturen hinsichtlich Größeninvarianz und Sample-Effizienz.
3. Empirischer Nachweis: Der Nachweis, dass kompakte Modelle (mit deutlich weniger Parametern und Trainingsdaten) die Leistung von großen Transformer-Modellen übertreffen oder gleichziehen können, wenn sie explizite Übergangsdynamiken lernen.

4. Ergebnisse

Die Experimente wurden auf vier IPC-Domänen durchgeführt: Blocksworld, Gripper, Logistics und VisitAll.

• Extrapolationsfähigkeit (OOD):
  • Aktionszentrierte Baselines (Plansformer, PlanGPT, SymT): Versagen fast vollständig bei strikter Extrapolation (z. B. 0% Erfolg in Logistics und Gripper bei großen Instanzen).
  • Zustandszentrierte Modelle (WL + XGBoost/LSTM): Erreichen signifikant höhere Erfolgswerte.
    • Blocksworld: 45% Erfolg (WL-XGB Delta) vs. 13% (SymT).
    • VisitAll: 87% Erfolg (WL-XGB Delta) vs. 64% (SymT).
• Ressourceneffizienz:
  • Die vorgestellten Modelle haben nur ~1 Million Parameter (LSTM) bzw. ~115.000 Bäume (XGBoost).
  • Im Vergleich dazu nutzen Transformer-Baselines 25–220 Millionen Parameter.
  • Die Modelle wurden auf den ursprünglichen, kleinen Trainingssets trainiert (ohne Daten-Augmentierung durch Symmetrie-Erweiterung, die bei SymT genutzt wird).
• Einfluss der Repräsentation:
  • WL-Embeddings sind entscheidend für die Generalisierung auf größere Instanzen.
  • Fixed-Size Factored (FSF) Encodings (die eine feste maximale Objektzahl voraussetzen) scheitern bei Extrapolation komplett (0% Erfolg in den meisten Fällen).
• Domänenspezifische Einschränkungen:
  • In der Logistics-Domäne scheitern alle gelernten Modelle bei strikter Extrapolation (0% Erfolg). Dies liegt an der tiefen kausalen Kopplung über mehrere Ebenen hinweg, die durch einen einstufigen Übergangsvorhersage-Ansatz nicht erfasst werden kann.

5. Bedeutung und Fazit

Das Paper demonstriert, dass explizites Lernen von Weltmodellen (Transition Models) eine stärkere induktive Verzerrung für die Generalisierung bietet als reine Skalierung von Architekturgrößen oder Daten-Augmentierung.

• Paradigmenwechsel: Der Ansatz beweist, dass man für erfolgreiches generalisiertes Planen nicht zwingend riesige LLMs oder Transformer benötigt, sondern dass kompakte Modelle mit der richtigen relationalen Abstraktion (WL) und expliziter Zustandsverfolgung überlegen sind.
• Robustheit: Durch die neuro-symbolische Decodierung wird sichergestellt, dass jeder Schritt des Plans symbolisch gültig ist, was den Zustand drift verhindert.
• Zukunftsperspektive: Die Methode ist besonders effektiv in Domänen mit lokalen, spärlichen Übergängen. Für Domänen mit komplexen, hierarchischen Abhängigkeiten (wie Logistics) müssen zukünftige Arbeiten mehrstufige oder abstrakte Übergänge untersuchen.

Zusammenfassend bietet das Paper einen effizienten, datensparsamen und robusten Weg für generalisiertes Planen, der die Lücke zwischen symbolischer Planung und maschinellem Lernen schließt, ohne auf massive Rechenressourcen angewiesen zu sein.