💻 computer science

Efficient Lookahead Encoding and Abstracted Width for Learning General Policies in Classical Planning

Dieser Beitrag stellt eine effiziente ganzheitliche Kodierung und einen abstrahierten IW(1)-Ansatz vor, die Relational GNNs nutzen, um Skalierbarkeits- und Ausdruckskraftbeschränkungen in der generalisierten Planung zu überwinden, und erzielt damit auf dem IPC-2023-Benchmark State-of-the-Art-Leistung, indem sie frühere Methoden einschließlich des klassischen Planers LAMA übertreffen.

Ursprüngliche Autoren: Michael Aichmüller, Simon Ståhlberg, Martin Funkquist, Hector Geffner

Veröffentlicht 2026-05-19

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Michael Aichmüller, Simon Ståhlberg, Martin Funkquist, Hector Geffner

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 lehren einen Roboter, ein riesiges, sich ständig veränderndes Labyrinth zu lösen. Das Labyrinth ändert sich bei jedem Spiel: Manchmal gibt es 10 Räume, manchmal 10.000. Das Ziel ist es, dem Roboter ein einziges „Regelwerk" (eine Policy) beizubringen, das für jede Version des Labyrinths funktioniert, egal wie groß es wird.

Dieser Artikel stellt eine neue Methode vor, um diesen Roboter zu unterrichten, und löst dabei zwei Hauptprobleme, die frühere Methoden bisher gebremst haben: Speicherüberlastung und langames Denken.

Hier ist die Aufschlüsselung ihrer Lösung unter Verwendung einfacher Analogien:

1. Das Problem: Die „Bibliothek von Babel"

In der Vergangenheit, wenn der Roboter versuchte, seinen nächsten Zug zu planen, betrachtete er jeden möglichen zukünftigen Schritt einzeln.

Der alte Weg: Stellen Sie sich vor, Sie befinden sich in einer Bibliothek mit einer Million Büchern. Um zu entscheiden, welches Buch Sie als Nächstes lesen sollen, müssen Sie zu jedem einzelnen Buch gehen, die erste Seite lesen, eine Notiz schreiben und dann zurückgehen. Wenn Sie 1.000 Bücher haben, sind das 1.000 Gänge. Wenn Sie eine Million haben, werden Sie niemals fertig werden.
Die Grenze: Je größer das „Labyrinth" (das Planungsproblem) wird, desto mehr explodiert die Anzahl der „Bücher" (mögliche Züge). Frühere KI-Methoden würden den Computerspeicher erschöpfen oder zu lange zum Nachdenken benötigen, insbesondere wenn die Anzahl der Objekte (wie Blöcke oder Autos) die Tausende erreichte, die in jüngsten Wettbewerben vorkamen.

2. Die erste Innovation: Der „Delta-Schnappschuss" (Aggregated-Delta-Encoding)

Die Autoren erkannten, dass sie nicht jedes Mal die gesamte Bibliothek neu lesen mussten. Sie mussten nur wissen, was sich geändert hatte.

Die Analogie: Anstatt jedes Mal, wenn Sie ein Buch verschieben, ein Foto der gesamten Bibliothek zu machen, kleben Sie einfach eine winzige „Haftnotiz" auf, auf der steht: „Buch A wurde vom Regal 1 zum Regal 2 verschoben."
Wie es funktioniert: Die neue Methode, genannt Aggregated-Delta (AD), behandelt den Planungsbaum des Roboters wie eine einzige, verbundene Karte. Anstatt jeden zukünftigen Zustand als separates, schweres Bild zu verarbeiten, kodiert sie nur die Unterschiede (die „Deltas") zwischen dem aktuellen Zustand und dem nächsten.
Das Ergebnis: Der Roboter kann die gesamte Karte der Möglichkeiten in einem einzigen Blick (ein „Forward Pass") betrachten, anstatt sie einzeln zu überprüfen. Dies reduzierte den benötigten Speicher um mehr als das Zehnfache und ermöglichte dem Roboter, massive Probleme zu bewältigen, die zuvor den Computer zum Absturz gebracht hätten.

3. Die zweite Innovation: Die „unscharfe Linse" (Abstrahierte Breite)

Selbst mit dem neuen Speichertrick musste der Roboter noch prüfen, ob ein bestimmter Zug „neu" oder „novell" war. In einer Welt mit Tausenden von Objekten ist das Überprüfen jedes einzelnen spezifischen Details langsam.

Die Analogie: Stellen Sie sich vor, Sie suchen in einem Parkplatz nach einem bestimmten roten Auto.
- Der alte Weg: Sie überprüfen jedes Auto einzeln: „Ist das der rote Ford? Ist das der rote Toyota? Ist das der rote Honda?"
- Der neue Weg (Abstrahierte IW): Sie setzen eine „unscharfe Linse" auf. Sie hören auf, die spezifischen Automodelle zu überprüfen. Stattdessen fragen Sie einfach: „Gibt es hier ein rotes Auto?" Sie behandeln alle roten Autos als denselben „Typ" von Objekt.
Wie es funktioniert: Sie führten Abstracted IW (AIW) ein. Beim Prüfen, ob ein Zug neu ist, ignoriert die KI die spezifische Identität der Objekte (wie „Block #452") und betrachtet nur ihren allgemeinen Typ (wie „Block").
Das Ergebnis: Dies verwandelt eine Suche, die mit der Anzahl der Objekte exponentiell wächst, in eine, die linear wächst. Es ist wie das Überprüfen einer Liste von 100 Autotypen anstelle von 10.000 einzelnen Autos. Es ist viel schneller, findet aber immer noch die wichtigen „Teilziele", die zur Lösung des Rätsels benötigt werden.

4. Das Ergebnis: Ein Super-Planer

Durch die Kombination des „Haftnotiz"-Speichertricks mit dem Denkstil der „unscharfen Linse" schufen die Autoren einen Planer, der:

Skaliert: Er kann Probleme mit Hunderten von Objekten (wie einem 488-Block-Turm) lösen, die frühere KI-Systeme in die Knie gezwungen hatten.
Übertrifft die Besten: Beim International Planning Competition 2023 (ein wichtiger Test für KI-Planer) schlug ihre Methode die bisherigen Champions, einschließlich eines sehr starken klassischen Planers namens LAMA.
Bewältigt schwierige Rätsel: Er löste komplexe Domänen (wie „Satellite" und „Rovers"), die eine Logik erfordern, die über das hinausgeht, was die meisten KI-Modelle normalerweise bewältigen können.

Zusammenfassung

Der Artikel handelt davon, einer KI beizubringen, aufzuhören, jedes einzelne Detail einer riesigen, sich verändernden Welt auswendig zu lernen. Stattdessen lehrt es die KI:

Nur zu merken, was sich geändert hat (was enorme Mengen an Speicher spart).
Ähnliche Dinge zusammenzufassen (was durch das Ignorieren unnötiger Details schnelleres Denken ermöglicht).

Das Ergebnis ist eine allgemeine Policy, die riesige, komplexe Labyrinthe effizient navigieren kann und Probleme löst, die zuvor für Computer zu groß waren.

Technische Zusammenfassung: Effiziente Lookahead-Codierung und abstrahierte Breite für das Erlernen allgemeiner Strategien in der klassischen Planung

Problemstellung

Das Erlernen allgemeiner Strategien (Generalized Planning) zielt darauf ab, Strategien zu entwickeln, die sich über große Sammlungen von Planungsinstanzen innerhalb einer einzigen Domäne verallgemeinern lassen und sich lediglich in den Anfangszuständen, Zielen und Objektanzahlen unterscheiden. Während neuere Ansätze mit Graph Neural Networks (GNNs) vielversprechend sind, stoßen sie bei der Anwendung auf großskalige Instanzen, wie sie im International Planning Competition (IPC) 2023 vorkommen, auf erhebliche Einschränkungen hinsichtlich Skalierbarkeit und Ausdruckskraft.

Insbesondere nutzen vorherige Arbeiten zu Iterated Width (IW)-Strategien IW(1)-Lookahead-Suchen, um „Sprünge" über mehrere Übergänge hinweg zu definieren und die Problemstruktur zu vereinfachen. Die bestehenden Implementierungen leiden jedoch unter zwei Hauptengpässen:

Rechnerische Ineffizienz: Die individuelle Bewertung jedes Nachfolgezustands führt zu einer redundanten Codierung gemeinsamer Zustandsbeschreibungen, wodurch Speicher- und Rechenkosten mit zunehmender Anzahl von Objekten und Atomen schlecht skalieren.
Grenzen der Ausdruckskraft und Skalierung: Standard-IW(1)-Neuheitsprüfungen skalieren linear mit der Anzahl der instanziierten Atome. In Domänen mit Tausenden von Objekten wächst die Anzahl der instanziierten Atome polynomial, was die Lookahead-Suche ineffizient macht. Darüber hinaus fehlt Modellen, die auf unmittelbare Nachfolger beschränkt sind, oft die Ausdruckskraft, um notwendige Merkmale für komplexe Domänen abzuleiten (z. B. solche, die Logik jenseits des C2-Fragments erfordern).

Methodik

Der Artikel schlägt einen einheitlichen Ansatz vor, der zwei Schlüsselinnovationen kombiniert: eine neuartige Aggregated-Delta (AD)-Codierung für Relational GNNs (R-GNNs) und Abstracted IW(1) (AIW(1)) für die Lookahead-Suche.

1. Aggregated-Delta (AD)-Codierung

Anstatt den aktuellen Zustand $s$ und jeden Nachfolgezustand $s'$ unabhängig voneinander zu verarbeiten, führen die Autoren eine ganzheitliche Codierung ein, die den gesamten Lookahead-Baum als einen einzigen relationalen Graphen darstellt.

Gemeinsame Repräsentation: Der Wurzelzustand $s$ wird implizit über seine Relationenmenge codiert. Nachfolgezustände werden nicht durch ihre vollständigen Zustandsbeschreibungen repräsentiert, sondern durch Zustands-Objektknoten ( $o_{s'}$ ), die nur die Unterschiede (hinzugefügte und gelöschte Prädikate) relativ zum Wurzelzustand codieren.
Baumstruktur: Die Codierung enthält explizite Atome, die Übergänge zwischen Nachfolgern darstellen, sowie Tiefenknoten, um die Suchtiefe zu erfassen. Dies ermöglicht es dem R-GNN, Informationen direkt zwischen Nachfolgerknoten auszutauschen und Einbettungen für alle Zustände in einem einzigen Vorwärtspass zu berechnen.
Effizienz: Dieser Ansatz vermeidet die erneute Codierung gemeinsamer Zustandsbeschreibungen, reduziert den Speicherverbrauch um mehr als eine Größenordnung (von >24 GB auf <4 GB VRAM in getesteten Szenarien) und ermöglicht die gleichzeitige Bewertung aller Übergänge.

2. Abstracted IW(1) (AIW(1))

Um den Skalierungsengpass bei Neuheitsprüfungen zu adressieren, schlagen die Autoren eine gelockerte Variante von IW(1) vor, die Zustandsatome während der Neuheitsprüfung abstrahiert.

Relationale Abstraktion: Anstatt vollständig instanziierte Atome zu testen, ersetzt AIW(1) iterativ alle Argumente eines $n$ -stelligen Atoms bis auf eines durch seinen spezifischsten Typ (z. B. Ersetzen des Objekts $o$ durch $type(o)$). Ein Atom gilt als neu, wenn irgendeine seiner abstrahierten Formen neu ist.
Komplexitätsverschiebung: Diese Modifikation verschiebt die Worst-Case-Komplexität der Neuigkeitssuche von linear in der Anzahl der instanziierten Atome auf linear in der Anzahl der Objekte.
Zielerhaltung: Atome, die im Ziel erwähnt werden, werden nicht abstrahiert, um sicherzustellen, dass die Zielerkennung präzise bleibt.
Vorteil: Dies ermöglicht es der Lookahead-Suche, mit Instanzen mit Tausenden von Objekten zu skalieren, während gleichzeitig bedeutungsvolle Teilzielstrukturen erfasst und die Kostenstruktur für den lernenden Agenten vereinfacht werden.

Trainingsverfahren

Das R-GNN wird mit Deep Q-Learning und einer gehobenen Variante von Hindsight Experience Replay (HER) trainiert. Die Belohnung wird als -1 pro Schritt definiert, sodass der Q-Wert die negative erwartete Anzahl von Übergängen zum Ziel darstellt. Eine zusätzliche Ranking-Verlustfunktion wird eingeführt, um die Tiefenordnung im Lookahead-Baum durchzusetzen und sicherzustellen, dass der Agent lernt, Sackgassen zu vermeiden, die durch zu weit voraus springen entstehen (z. B. in der Domäne Spanner).

Hauptbeiträge

Aggregated-Delta (AD)-Codierung: Eine neuartige Eingabecodierung für R-GNNs, die gesamte Lookahead-Bäume gemeinsam über Zustandsunterschiede darstellt. Dies ermöglicht die Bewertung aller Nachfolger in einem einzigen Durchlauf und reduziert den Speicherbedarf sowie die Trainingszeit drastisch.
Abstracted IW(1) (AIW(1)): Ein skalierbarer Lookahead-Mechanismus, der die Komplexität der Neuigkeitssuche von polynomial in Atomen auf linear in Objekten reduziert, indem eine typbasierte Abstraktion genutzt wird.
State-of-the-Art-Leistung: Die Kombination aus AIW und AD erreicht neue Leistungsbenchmarks auf dem IPC 2023 Learning Track und in anderen Domänen und übertrifft sowohl frühere gelernte Strategien als auch starke klassische Planer wie LAMA.

Experimentelle Ergebnisse

Die Autoren bewerteten ihren Ansatz am IPC 2023-Benchmark (900 Instanzen über 10 Domänen) und einem erweiterten Satz von Domänen (einschließlich Grid und Logistics).

IPC 2023-Leistung: Die AIW–AD-Methode erreichte eine Gesamtabdeckung von 74% (668/900 Instanzen) und übertraf damit signifikant:
- IW–AD (59%): Demonstriert den Wert der Abstraktion.
- AIW–Ext (51%) und IW–Ext (51%): Demonstriert den Wert der AD-Codierung.
- LAMA (65%): Die starke klassische Baseline.
- Flat AA (58%): Flache Strategien ohne Lookahead.
Domänenspezifika:
- Satellite: AIW–AD löste 98% der Instanzen und löste die Domäne vollständig, in der andere gelernte Methoden Schwierigkeiten hatten.
- Rovers & Childsnack: Es wurden signifikante Verbesserungen beobachtet, obwohl harte Instanzen in Childsnack aufgrund massiver Verzweigungsfaktoren (Millionen von Aktionen) weiterhin herausfordernd bleiben.
- Sokoban & Floortile: Die Leistung blieb niedrig, was mit der bekannten Schwierigkeit dieser PSPACE-vollständigen oder strukturell komplexen Domänen für suchfreie Strategien übereinstimmt.
Skalierbarkeit: Die Methode bewältigte erfolgreich Instanzen mit bis zu 488 Blöcken (Blocksworld) und über 290.000 Atomen (Rovers), bei denen vorherige IW-Strategie-Formulierungen aufgrund von Speicherbeschränkungen versagten.
Ausdruckskraft: Der Ansatz verallgemeinerte erfolgreich auf Domänen, die Merkmale jenseits des C2-Logikfragments erfordern (z. B. Satellite, Rovers, Grid, Logistics), was darauf hindeutet, dass der Lookahead-Mechanismus die expressive Belastung der neuronalen Architektur reduziert.

Bedeutung und Behauptungen

Der Artikel behauptet, dass eine effiziente breitengestützte Lookahead-Suche ein entscheidender Enabler für die Skalierung allgemeinen Planens ist. Die Bedeutung der Arbeit liegt in zwei Hauptbereichen:

Skalierbarkeit: Durch die Entkopplung der Komplexität der Lookahead-Suche von der Anzahl der instanziierten Atome (via AIW) und der Komplexität der neuronalen Codierung von der Anzahl der Übergänge (via AD) macht der Ansatz das Erlernen von Strategien für massive Planungsinstanzen möglich, die für gelernte Methoden zuvor unlösbar waren.
Reduzierte Anforderungen an die Ausdruckskraft: Der Lookahead-Mechanismus vereinfacht die Problemstruktur für den lernenden Agenten. Indem er über Sequenzen primitiver Entscheidungen „springt", muss die Strategie nur hochlevelige Entscheidungen lernen. Dies ermöglicht es Modellen mit begrenzter Ausdruckskraft (Standard-R-GNNs), Domänen zu lösen, die andernfalls komplexe Merkmale jenseits des C2-Logikfragments erfordern würden.

Die Autoren schließen, dass ihr Ansatz einen neuen State-of-the-Art im allgemeinen Planen darstellt und zeigt, dass die Kombination von prinzipieller Suche (Lookahead) mit effizienter neuronaler Codierung es gelernten Strategien ermöglicht, effektiv zu skalieren und gleichzeitig hohe Leistung in diversen und komplexen Domänen zu bewahren.