🤖 AI

Learning to Search and Searching to Learn for Generalization in Planning

Dieser Beitrag stellt einen selbstverbessernden Rahmen vor, der ein relationales Graph-Neuronales Netzwerk mit einer $\mathrm{WA}^\star$ -Suche integriert, um Deep-Reinforcement-Learning-Agenten eine starke Zero-Shot-Verallgemeinerung in Planungsdomänen mit spärlichen Belohnungen zu ermöglichen und damit signifikant größere Probleminstanzen ohne Suche oder Experten-Demonstrationen zu lösen.

Ursprüngliche Autoren: Michael Aichmüller, Yannik Hesse, Hector Geffner

Veröffentlicht 2026-05-26

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Michael Aichmüller, Yannik Hesse, 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 versuchen einem Roboter beizubringen, ein komplexes Puzzle zu lösen, wie etwa ein riesiges Spiel Sokoban (bei dem Sie Kisten zu bestimmten Stellen schieben) oder Blocksworld (das Stapeln von Blöcken in einer bestimmten Reihenfolge).

Die große Herausforderung besteht nicht darin, ein Puzzle zu lösen, sondern dem Roboter beizubringen, jede Variante dieses Puzzles zu lösen, selbst solche, die er noch nie gesehen hat, mit mehr Kisten, anderen Startpositionen oder größeren Zielen. Dies wird als Generalisierung bezeichnet.

Hier ist, wie der Artikel „Learning to Search and Searching to Learn" dieses Problem angeht, einfach erklärt:

1. Das Problem: Im Labyrinth verloren gehen

Beim Standard-Training von KI (Deep Reinforcement Learning) lernt der Roboter normalerweise, indem er einen Schritt macht, sieht, was passiert, und dann einen weiteren Schritt macht. Das ist wie das Gehen durch ein dunkles Labyrinth, bei dem man die Wand mit der Hand ertastet.

Das Problem: Bei diesen Planungspuzzles sind „Belohnungen" (das Finden der Lösung) sehr selten. Wenn der Roboter einfach ziellos umherwandert, könnte es eine Million Jahre dauern, bis er den Ausgang findet. Er bleibt in Sackgassen oder Schleifen stecken.
Der alte Weg: Einige Methoden versuchen, dem Roboter die Lösung zuerst zu zeigen (wie ein Lehrer, der den Lösungsschlüssel zeigt), aber das ist betrügerisch. Andere versuchen, durch das Gehen vom Ziel rückwärts zu lernen, was bei diesen spezifischen Arten von Logikpuzzles nicht immer funktioniert.

2. Die Lösung: Die „intelligente Karte" und die „selbstverbessernde Schleife"

Die Autoren schlagen eine neue Methode vor, die GSP (Generalized Search for Planning) genannt wird. Anstatt blind zu wandern, geben sie dem Roboter zwei Superkräfte, die sich gegenseitig unterstützen:

A. Die „intelligente Karte" (Die Heuristik)

Stellen Sie sich vor, der Roboter besitzt eine magische Karte (ein neuronales Netzwerk), die das aktuelle Puzzle betrachtet und schätzt: „Wenn ich diese Kiste hierhin schiebe, wie nah werde ich am Ziel sein?"

Diese Karte rät nicht nur; sie lernt aus Erfahrung.
Entscheidend ist, dass diese Karte mit Relationalen Graph-Neuronalen Netzwerken erstellt wird. Stellen Sie sich die Puzzleteile (Blöcke, Kisten) als Charaktere in einer Geschichte vor. Die Karte versteht die Beziehungen zwischen ihnen (z. B. „Kiste A liegt auf Kiste B"), anstatt sie nur als Pixel zu sehen. Dies ermöglicht der Karte, die Regeln zu verstehen, selbst wenn das Puzzle riesig wird.

B. Die „intelligente Suche" (Der Entdecker)

Anstatt einen Schritt nach dem anderen zu machen, verwendet der Roboter eine Best-First-Suche (speziell ein Algorithmus namens WA*).

Die Analogie: Stellen Sie sich vor, Sie suchen einen verlorenen Hund in einem Wald.
- Standard-RL (Echtzeitsuche): Sie wählen einen zufälligen Pfad, gehen 10 Schritte, prüfen, ob der Hund dort ist. Wenn nicht, gehen Sie zurück und versuchen einen anderen zufälligen Pfad. Sie verschwenden viel Energie.
- GSP (Best-First-Suche): Sie schauen auf Ihre intelligente Karte. Sie zeigt Ihnen die 5 vielversprechendsten Pfade. Sie erkunden diese Pfade alle gleichzeitig in Ihrem Kopf und prüfen, welcher am besten aussieht. Sie verpflichten sich nur dem Pfad, von dem die Karte sagt, dass er am wahrscheinlichsten zum Hund führt.

3. Der magische Kreislauf: „Lernen zu suchen, Suchen zu lernen"

Dies ist die Kerninnovation. Die beiden oben genannten Teile speisen sich in einem Zyklus gegenseitig:

Suchen zum Lernen: Der Roboter verwendet seine aktuelle, unvollkommene intelligente Karte, um eine intelligente Suche auf einem Puzzle durchzuführen. Er findet eine Lösung (oder kommt ihr nahe).
Die Daten: Der Suchprozess erzeugt einen Schatz an Daten: „Als ich in dieser Situation war, führte diese Aktion zu einer Lösung."
Lernen zum Suchen: Der Roboter verwendet diese neuen Daten, um die intelligente Karte zu aktualisieren und zu verbessern. Die Karte wird besser darin zu erraten, welche Züge gut sind.
Wiederholen: Jetzt kann der Roboter mit einer besseren Karte sogar schwierigere Puzzles effizienter durchsuchen. Die Suche findet bessere Daten, was die Karte noch schlauer macht.

Es ist ein sich selbst verbessernder Kreislauf: Die Suche lehrt die Karte, und die Karte führt die Suche.

4. Die Ergebnisse: Das Unmögliche lösen

Der Artikel testete dies an einigen sehr harten Benchmarks:

Blocksworld: Der Roboter wurde an Puzzles mit weniger als 30 Blöcken trainiert. Als er an einem Puzzle mit 488 Blöcken getestet wurde (ein massiver Sprung in der Größe), löste er es, ohne überhaupt suchen zu müssen. Er sah einfach auf die Karte und wusste genau, was zu tun war. Dies wird als „Zero-Shot-Generalisierung" bezeichnet.
Sokoban & The Witness: Es löste fast 100 % dieser komplexen Puzzles und fand oft viel schneller Lösungen (mit weniger Schritten) als andere Top-KI-Methoden.
PushWorld: Es bewältigte neue, schwierigere Level, die es noch nie gesehen hatte, und übertraf dabei die Standard-KI, die auf zufällige Exploration angewiesen ist.

Zusammenfassung

Der Artikel stellt ein System vor, bei dem eine KI Logikpuzzles löst, indem sie eine intelligente, lernbasierte Karte verwendet, um eine systematische Suche zu leiten.

Anstatt blind umherzuwandern, nutzt sie die Karte, um die besten Pfade auszuwählen.
Anstatt nur ein Puzzle auswendig zu lernen, lernt sie die Beziehungen zwischen Objekten, sodass sie Puzzles jeder Größe lösen kann.
Die Suche und das Lernen stärken sich gegenseitig und schaffen einen Roboter, der besser darin wird, neue, ungesehene Probleme zu lösen, indem er einfach an alten übt.

Kurz gesagt: Sie lehrten die KI aufzuhören zu raten und zu beginnen zu planen, und dann lehrten sie den Planer, aus seinem eigenen Planen zu lernen.

Technische Zusammenfassung: Lernen zum Suchen und Suchen zum Lernen für Generalisierung in der Planung

Problemstellung

Kombinatorische Generalisierung bleibt eine zentrale Herausforderung im Deep Reinforcement Learning (DRL), bei der Policies oder Wertfunktionen auf Szenarien außerhalb der Trainingsverteilung generalisieren müssen, die durch eine gemeinsame Problemstruktur definiert sind. Klassische Planung bietet einen idealen Testfall für dieses Problem, da die zugrundeliegende relationale Struktur (Prädikate und Aktionsschemata) fest und explizit ist, während die Instanzen in der Anzahl der Objekte, den Anfangszuständen und den Zielen variieren.

Standard-DRL-Ansätze haben jedoch Schwierigkeiten in Planungsdomänen mit spärlichen Belohnungen. Echtzeitsuche (iterative Zustands-zu-Zustands-Übergänge), wie sie typischerweise in RL-Algorithmen wie LRTA* oder RTDP verwendet wird, ist in diesen Umgebungen ineffektiv, um Pläne zu finden. Im Gegensatz dazu verwenden klassische Planer Best-First-Suche (z. B. A*, WA*), verlassen sich jedoch auf handgefertigte Heuristiken. Obwohl jüngste Arbeiten versucht haben, allgemeine Policies oder Heuristiken zu lernen, stützen sich bestehende Methoden oft auf Echtzeitsuche, überwachtes Lernen aus Experten-Demonstrationen oder Hindsight-Umdeklarierung. Dabei scheitern sie daran, einen selbstverbessernden Kreislauf zu etablieren, in dem Suche und Lernen sich gegenseitig verstärken, um Zero-Shot-Generalisierung über verschiedene Problemgrößen hinweg zu erreichen.

Methodik: Generalisierte Suche für Planung (GSP)

Die Autoren schlagen GSP vor, einen selbstverbessernden Rahmen, der Best-First-Suche mit Q-Learning kombiniert, um allgemeine Aktionswertfunktionen ( $Q_\theta$ ) zu lernen.

Kernschleife

Suche-gesteuertes Lernen: Anstelle von Echtzeitsuche verwendet GSP Weighted A (WA)**, um Trainingsinstanzen zu lösen. Die Suche wird durch die aktuell gelernten $Q_\theta(s, a)$ -Werte geleitet.
Datengenerierung: Während WA* Knoten erweitert, generiert es einen Replay-Puffer von Übergängen. Entscheidend ist, dass die Suche Überwachungssignale liefert, die dem Standard-RL fehlen:
- Zielpfade: Wenn ein Ziel erreicht wird, führt der Algorithmus eine Rückverfolgung durch, um den Paaren auf dem Lösungspfad tatsächliche Return-to-go-Werte zuzuweisen.
- Sackgassen: Wenn ein Zustand eine Sackgasse ist (keine anwendbaren Aktionen), wird dem übergeordneten Paar ein fester Straf-Return zugewiesen.
- Untere Schranken: Die Suche liefert eine untere Schranke für den optimalen Return für jedes Zustands-Aktions-Paar, das auf einem Lösungspfad angetroffen wird.
Q-Learning-Update: Das $Q_\theta$ -Netzwerk wird unter Verwendung dieser suchbasierten Ziele aktualisiert. Für Zielpfad-Paare ist das Ziel $\max(R, \hat{y})$ , wobei $R$ die suchbasierte untere Schranke und $\hat{y}$ das Standard-Bootstrap-Ziel ist. Dies verhindert, dass die Werteschätzungen unter das Niveau fallen, das die Suche bereits als erreichbar nachgewiesen hat.
Instanzauswahl: Um die Lerneffizienz zu optimieren, verwaltet der Rahmen drei Pools von Instanzen (unlösbar, gelöst und zufriedenstellend gelöst) und sampelt daraus mit exponentiell steigenden Gewichten, wobei Instanzen priorisiert werden, die die informativsten Updates liefern (z. B. solche mit suboptimalen Lösungen).

Repräsentation: Relationale GNNs

Um eine Generalisierung über verschiedene Anzahlen von Objekten und Zielen hinweg zu gewährleisten, wird $Q_\theta$ durch ein Relationales Graph-Neuronales Netzwerk (R-GNN) repräsentiert.

Eingang: Ein Zustand $s$ und ein Ziel $g$ werden als Menge von Ground-Atomen kodiert. Anwendbare Aktionen werden explizit repräsentiert, indem Hilfs-"Aktionsobjekte" und Atome eingeführt werden, was es dem Netzwerk ermöglicht, spezifische Aktionswahlen im Kontext des Zustands zu bewerten.
Architektur: Das Netzwerk verwendet Message Passing über die relationale Struktur. Prädikatspezifische MLPs generieren Nachrichten basierend auf Argumentrollen, die durch permutationsinvariante Funktionen aggregiert werden.
Ausgang: Ein gemeinsames Readout-MLP kombiniert die Einbettung des spezifischen Aktionsobjekts mit einer gepoolten Zusammenfassung des Zustands und des Ziels, um den Q-Wert zu erzeugen. Diese Architektur stellt sicher, dass das Modell ein gemeinsames Bewertungsprinzip für verankerte Aktionen lernt, anstatt separate Prädiktoren für jedes Schema.

Hauptbeiträge

Selbstverbessernder Such-Lern-Zyklus: Die Arbeit stellt einen Rahmen vor, bei dem Best-First-Suche (WA*) hochwertige Trainingsdaten (einschließlich unterer Schranken und Sackgassen-Signale) generiert, um eine gelernte Heuristik zu aktualisieren, die wiederum effizientere zukünftige Suchen leitet.
Zero-Shot-Generalisierung: Die gelernten Q-Funktionen fungieren als allgemeine Policies, die Instanzen mit deutlich mehr Objekten und anderen Zielen als während des Trainings gesehen, lösen können, ohne in vielen Fällen eine Suche zur Testzeit zu erfordern.
Einheitlicher Rahmen: Der Ansatz wird einheitlich auf diverse Domänen angewendet, von den Benchmarks des International Planning Competition (IPC) 2023 bis hin zu kombinatorischen Puzzles (Sokoban, The Witness) und der PushWorld-Domäne, unter Verwendung einer einzigen Architektur und eines einzigen Hyperparameter-Sets.
Überlegenheit gegenüber Echtzeitsuche: Die Arbeit zeigt, dass der Ersatz von Echtzeitsuche durch Best-First-Suche im Lernzyklus entscheidend für den Erfolg in Planungsdomänen mit spärlichen Belohnungen und hohem Verzweigungsfaktor ist.

Experimentelle Ergebnisse

Die Autoren evaluierten GSP auf drei Kategorien von Benchmarks:

2023 IPC Learning Track:
- Greedy Execution ( $GSP_\pi$ ): Erzielte 100% Abdeckung bei Blocksworld, Miconic und Spanner und übertraf Baselines wie Lifted HER, LAMA und AlphaZero-artige Policies.
- Search-Guided ( $GSP_{WA^*}$ ): Zeigte gemischte Ergebnisse; während es die Abdeckung bei Puzzles wie Sokoban verbesserte (14% $\to$ 32%), reduzierte es die Abdeckung manchmal in Domänen mit massiven Verzweigungsfaktoren (z. B. Blocksworld), wo die gelernte Heuristik, obwohl gut für das lokale Ranking, eine globale Kalibrierung vermisste.
- Skalierung: Heuristiken, die auf Blocksworld-Instanzen mit <30 Blöcken trainiert wurden, lösten erfolgreich Instanzen mit 488 Blöcken ohne Suche.
Kombinatorische Puzzles (Sokoban, The Witness, 24-Puzzle):
- Bei Sokoban löste $GSP_{WA^*}$ 100% der Instanzen mit durchschnittlich 207 Erweiterungen und übertraf damit WA* mit Standardheuristiken (3298 Erweiterungen) und DeepCubeA (1050 Erweiterungen) signifikant.
- Bei The Witness löste die Methode alle Instanzen und demonstrierte den Wert des Trainings an Sackgassen-Zuständen.
- Bei 24-Puzzle gelang es der Methode nicht, während des Trainings Lösungen zu finden. Dies unterstreicht, dass der Ansatz die Fähigkeit benötigt, mindestens eine Lösung zu finden, um das Lernen zu bootstrappen, was in extrem schwierigen festgelegten Puzzles ohne initiale informierte Heuristiken schwierig ist.
PushWorld:
- Trainiert auf Level 0 generalisierte das Modell auf Level 1. $GSP_{WA^*}$ löste 48/63 Level-1-Instanzen mit kürzeren Plänen und etwa 30-mal weniger Erweiterungen als der klassische Planer LAMA.
- Als greedy Policy übertraf es signifikant model-freie RL-Baselines (DQN, PPO).

Bedeutung und Behauptungen

Die Arbeit behauptet, dass Best-First-Suche ein überlegener Explorationsmechanismus für generalisiertes Reinforcement Learning ist, wenn das Übergangsmodell bekannt ist, insbesondere in Domänen mit spärlichen Belohnungen, in denen Echtzeitsuche versagt, informative Trajektorien zu entdecken.

Die primäre Bedeutung liegt in der Demonstration eines sich selbst verstärkenden Zyklus: Die Suche liefert die Trainingsziele (untere Schranken, Sackgassen), die es der Heuristik ermöglichen, sich zu verbessern, und die verbesserte Heuristik macht nachfolgende Suchen effizienter. Dies ermöglicht dem System, allgemeine Policies zu lernen, die Probleme beliebiger Größe und Komplexität ohne Suche lösen können, oder hoch effiziente Heuristiken, die die Suche zu optimalen Lösungen führen.

Die Autoren vermerken bescheiden Einschränkungen: Die gelernte Q-Funktion fungiert oft als starker lokaler Aktions-Ranking-Mechanismus, kann jedoch eine globale Kalibrierung über die gesamte Suchfront hinweg vermissen, was zu suboptimaler Leistung bei WA* in Domänen mit extrem großen Verzweigungsfaktoren führen kann. Sie schlagen vor, dass zukünftige Arbeiten sich auf die Verbesserung der Wertgeneralisierung über Zustände hinweg konzentrieren und Best-First-Suche mit den komplementären Stärken von Echtzeitsuche und Hindsight-Erfahrungs-Umdeklarierung kombinieren könnten.