💻 computer science

Learning Lifted Action Models from Traces with Minimal Information About Actions and States

Dieser Beitrag stellt Algorithmen und Vollständigkeitsergebnisse für das Lernen von STRIPS+-Aktionsdomänen aus Spuren mit partiellen Informationen über sowohl Aktionen als auch Zustände vor und adressiert dabei frühere Einschränkungen, indem Szenarien betrachtet werden, die von keiner Zustandsbeobachtbarkeit bis hin zur vollständigen oder lokalen Beobachtbarkeit spezifischer Zustandsprädikate reichen.

Ursprüngliche Autoren: Jonas Gösgens, Niklas Jansen, Hector Geffner

Veröffentlicht 2026-05-19

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Jonas Gösgens, Niklas Jansen, 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, die Regeln eines komplexen Brettspiels wie Schach oder eines Schiebepuzzles herauszufinden, aber Sie haben ein sehr seltsames Problem: Sie können das Brett nicht sehen.

Sie können nur die Züge der Spieler sehen. Sie sehen, wie eine Figur von „A" nach „B" bewegt wird oder wie ein Spieler einen Token aufnimmt. Aber Sie wissen nicht, welche Figur bewegt wurde, wo sie startete oder wie das Brett vor oder nach dem Zug aussah. Sie versuchen, das Regelbuch des Spiels allein durch das Beobachten einer Reihe von Aktionen zu rekonstruieren.

Dies ist die Kernherausforderung, die in dem Papier „Learning Lifted Action Models from Traces with Minimal Information" (Lernen von gehobenen Aktionsmodellen aus Spuren mit minimalen Informationen) behandelt wird.

Hier ist eine Aufschlüsselung dessen, was die Autoren mit einfachen Analogien getan haben.

Das Problem: Die „Zu viel Information"-Falle

In der Vergangenheit versuchten Informatiker, KI beizubringen, diese Regeln zu lernen. Sie hatten zwei Hauptansätze, aber beide hatten Mängel:

Der „Vollständiges Brett"-Ansatz: Der KI wurde der gesamte Brettzustand (die Position jedes einzelnen Teils) sowie der Zug gegeben.
- Der Mangel: In der realen Welt sehen wir selten das gesamte Brett. Außerdem verlangen die Regeln oft zu viele Details. Um beispielsweise eine Kachel in einem Puzzle zu bewegen, erforderten die alten Regeln, dass Sie den aktuellen Ort der Kachel, ihren neuen Ort und die leere Stelle angeben. Um jedoch zu entscheiden, sich zu bewegen, müssen Sie wirklich nur wissen: „Nach links bewegen". Die zusätzlichen Details sind für den Entscheidungsträger nur Rauschen.
Der „Nur Aktion"-Ansatz: Der KI wurde nur die Liste der Züge gegeben (z. B. „Nach links bewegen", „Aufnehmen").
- Der Mangel: Ohne das Brett zu sehen, konnte die KI nicht herausfinden, was sie bewegte. Sie wusste nicht, ob „Nach links bewegen" bedeutete, einen Roboter, ein Auto oder einen Kasten zu bewegen.

Die Lösung: Eine neue Sprache (STRIPS+)

Die Autoren stellten einen Mittelweg namens STRIPS+ vor. Betrachten Sie dies als einen intelligenteren Weg, die Regeln zu schreiben.

Auf die alte Weise (STRIPS) sah eine Regel vielleicht wie ein strenges Formular aus:

Move(Robot, CurrentCell, NextCell)

Auf die neue Weise (STRIPS+) ist die Regel eher wie ein Rätsel:

Move()

Die Regel besagt: „Wenn sich ein Roboter in einer Zelle befindet und eine Zelle rechts davon existiert, können Sie sich bewegen." Der Computer muss herausfinden, welcher Roboter und welche Zellen zu dieser Beschreibung passen. Es ist wie ein Detektiv, der ein Verbrechen aufklärt, bei dem der Verdächtige nur als „die Person mit dem roten Hut" beschrieben wird, anstatt mit Namen „John Smith" genannt zu werden.

Die neuen Algorithmen: SIFT+ und SYNTH+

Das Papier stellt zwei neue „Detektive" (Algorithmen) vor, um dieses Rätsel zu lösen, wenn Informationen fehlen.

1. SIFT+ (Der „Nur-Aktion"-Detektiv)

Was er tut: Er lernt die Regeln allein durch das Beobachten einer Liste von Zügen, mit keiner Sicht auf das Brett.
Wie er funktioniert: Er verwendet einen Trick namens „Mutex Features" (gegenseitig ausschließende Merkmale).
- Die Analogie: Stellen Sie sich vor, Sie sehen einen Spieler, der eine Tasse aufnimmt. Sie sehen die Tasse nicht, aber Sie wissen, dass ein Spieler nur eine Tasse gleichzeitig halten kann. Wenn der Spieler eine Tasse aufnimmt, muss er diejenige, die er hielt, abgestellt haben.
- SIFT+ sucht nach diesen „gegenseitig ausschließenden" Mustern. Es erkennt: „Ah, immer wenn diese Aktion passiert, muss etwas über das gehaltene Objekt wahr sein." Es erfindet neue „Prädikate" (Konzepte wie is_holding [hält]), um die fehlenden Lücken zu füllen.
Das Ergebnis: Es kann das vollständige Regelbuch lernen, selbst wenn die Aktionsnamen fast alle ihre Details verloren haben.

2. SYNTH+ (Der „Teilweise Sicht"-Detektiv)

Was er tut: Er lernt, wenn er einige Teile des Bretts sehen kann, aber nicht alle.
Wie er funktioniert: Er kombiniert das „Rätsellösen" der neuen STRIPS+-Sprache mit den „Erfindungs"-Fähigkeiten von SIFT+.
- Die Analogie: Stellen Sie sich vor, Sie beobachten einen Lieferfahrer. Sie können den Standort des Fahrers sehen (den „vollständig beobachtbaren" Teil), aber Sie können die Pakete im Truck nicht sehen. Allerdings wissen Sie, dass der Fahrer nur ein Paket gleichzeitig tragen kann.
- SYNTH+ verwendet den sichtbaren Standort, um das unsichtbare Paket zu ermitteln. Es fragt: „Wenn der Fahrer an der Tür ist und gerade etwas ‚abgelegt' hat, was muss dann in seiner Hand gewesen sein?"
Die Wendung: Das Papier führt „Lokale Beobachtbarkeit" ein. Das bedeutet, Sie müssen nicht das gesamte Brett sehen. Sie müssen nur die Teile sehen, die für die aktuelle Aktion relevant sind.
- Beispiel: Wenn ein Roboter „Nach links" bewegt, müssen Sie nur die Zelle links von ihm sehen. Sie müssen nicht die Zelle auf der anderen Seite der Karte sehen. Dies macht das Lernen viel realistischer.

Der „Abhängigkeitsgraph" (Die Wegkarte)

Um sicherzustellen, dass diese Detektive nicht in einer Schleife stecken bleiben, erstellten die Autoren eine Karte namens Dependency Graph (Abhängigkeitsgraph).

Denken Sie daran wie an ein Flussdiagramm. Um „Regel A" zu lernen, müssen Sie vielleicht „Fakt B" kennen. Um „Fakt B" zu lernen, benötigen Sie vielleicht „Regel C".
Das Papier beweist, dass der Algorithmus die Regeln schrittweise lernen kann, solange dieser Flussgraph keinen kreisförmigen Loop enthält (wo A B braucht, B C braucht und C A braucht), beginnend bei den Dingen, die Sie sehen können, und rückwärts arbeitend zu den Dingen, die Sie nicht sehen können.

Die Ergebnisse: Hat es funktioniert?

Die Autoren testeten diese Detektive an klassischen Puzzles wie Blocksworld (Stapel von Blöcken), Delivery (Bewegen von Paketen) und Sokoban (Schieben von Kisten).

Der Test: Sie fütterten die Algorithmen mit Spuren, bei denen 50 % bis 90 % der Informationen verborgen waren.
Das Ergebnis:
- SIFT+ lernte die Regeln erfolgreich allein aus Aktionslisten und stellte die fehlenden Details (wie „welcher Block oben liegt") wieder her, indem er einfach Muster bemerkte.
- SYNTH+ lernte die Regeln, selbst wenn das „Brett" größtenteils verborgen war, solange die kritischen Teile (wie der Standort des Agenten) sichtbar waren.
- In fast jedem Test erreichten die Algorithmen eine Genauigkeit von 100 % und rekonstruierten die verborgenen Regelbücher korrekt.

Zusammenfassung

Dieses Papier handelt davon, Computern beizubringen, die „Regeln des Spiels" zu lernen, wenn ihnen sehr wenig Informationen gegeben werden.

Alter Weg: „Hier ist das Brett, hier ist der Zug. Lernen Sie die Regeln." (Zu viele Informationen benötigt).
Neuer Weg: „Hier ist eine Liste von Zügen. Sie können den Standort des Spielers sehen, aber nicht die Objekte. Finden Sie die Regeln heraus."
Der Durchbruch: Durch die Verwendung einer intelligenteren Sprache (STRIPS+) und einer klugen Methode des „Erfindens" fehlender Fakten basierend darauf, was wahr sein muss (Mutex Features), kann die KI die Lücken füllen und die vollständige Logik eines Bereichs lernen, ohne eine vollständige Sicht auf die Welt zu benötigen.

Das Papier behauptet, dies sei ein wichtiger Schritt hin zu einer KI, die aus natürlichen, unvollkommenen Beobachtungen lernen kann, ähnlich wie Menschen durch das Beobachten anderer lernen, anstatt ein perfektes, datenreiches Handbuch zu benötigen.

Technische Zusammenfassung: Lernen von gehobenen Aktionsmodellen aus Spuren mit minimalen Informationen

Problemstellung

Neuere Arbeiten haben gezeigt, dass gehobene STRIPS-Modelle effizient allein aus Aktionsspuren gelernt werden können (SIFT-Algorithmus) und dass STRIPS+-Modelle (die implizite Aktionsargumente zulassen) aus vollständig beobachtbaren Zustands-Aktions-Spuren gelernt werden können (SYNTH-Algorithmus). Diese Ansätze stoßen jedoch auf praktische Grenzen:

SIFT erfordert vollständige STRIPS-Aktionsspuren, bei denen Argumente explizit sind, was oft unnötige Parameter einschließt, die für die Aktionsauswahl nicht benötigt werden (z. B. bei Schiebepuzzle muss die aktuelle Position eines Steins explizit übergeben werden, selbst wenn die Aktion „nach links bewegen" lautet).
SYNTH geht von der vollständigen Beobachtbarkeit aller Zustandsprädikate aus, was für Agenten, die in teilweise beobachtbaren Umgebungen operieren, unrealistisch ist.

Dieser Beitrag adressiert das Problem des Lernens von STRIPS+-Aktionsdomänen aus Spuren, bei denen sowohl Aktionsargumente als auch Zustandsinformationen teilweise beobachtbar sind. Konkret untersuchen die Autoren die Bedingungen, unter denen eine äquivalente Domäne gelernt werden kann, wenn Spuren minimale Informationen tragen: einige Aktionsargumente werden weggelassen, und Zustandsprädikate sind entweder vollständig unbeobachtbar, vollständig beobachtbar oder nur lokal beobachtbar (nur für Objekte beobachtbar, die für den aktuellen Zustand relevant sind).

Methodik

Die vorgeschlagene Lösung, SYNTH+, ist ein einheitlicher Algorithmus, der die Fähigkeiten von SIFT und SYNTH erweitert und kombiniert. Er operiert auf erweiterten Spuren (Sequenzen von Aktionen und partiellen Zustandsbeobachtungen) und stützt sich auf zwei Kernmechanismen:

1. Mutex-Features (Erweiterung von SIFT)

Um fehlende Aktionsargumente ohne Zustandsbeobachtbarkeit zu handhaben, führen die Autoren Mutex-Features ein.

Konzept: Ein Mutex-Feature $f = \langle k, A, D \rangle$ stellt ein Prädikat der Stelligkeit $k$ dar, wobei das $k$ -te Argument implizit durch die ersten $k-1$ Argumente bestimmt wird.
Mechanismus: Im Gegensatz zu Standard-Features, bei denen Add- und Delete-Muster die gleiche Stelligkeit haben, erlauben Mutex-Features, dass Delete-Muster die Stelligkeit $k-1$ haben. Dies erfasst die Einschränkung, dass eine Aktion (z. B. drop()) ein Prädikat (z. B. holding(o)) basierend auf dem aktuell gehaltenen Objekt löscht, ohne dieses Objekt in der Aktionsspur explizit zu benennen.
Konsistenz: Ein Mutex-Feature ist konsistent, wenn im Spurgraphen jedes Ground-Atom $f(o)$ einen einzigen Wahrheitswert erhält und für zwei wahre Atome $f(o)$ und $f(o')$ im selben Zustand, falls die letzten Argumente differieren ( $o_k \neq o'_k$ ), mindestens ein vorhergehendes Argument ebenfalls differieren muss ( $o_i \neq o'_i$ für ein $i < k$ ).

2. Query-Synthese und Integration (Erweiterung von SYNTH)

SYNTH+ integriert die „Erfindung" von Prädikaten (via SIFT) mit der Inferenz impliziter Argumente (via SYNTH) in einer iterativen Schleife:

Eingabe: Ein beschrifteter Graph erweiterter Spuren und eine Menge vollständig beobachtbarer Prädikate $P_\omega$ .
Iteration:
- SIFT+-Schritt: Verwendet Aktionsmuster über explizite und aktuell bekannte implizite Argumente, um neue Mutex-Features und einfache Features zu erfinden. Diese Features repräsentieren neue Prädikate und deren Effekte.
- SYNTH-Schritt: Verwendet die neu erfundenen Prädikate (und alle beobachtbaren Prädikate), um Queries (Teilqueries $Q_i$ ) zu definieren, die implizite Variablen ( $z_i$ ) an eindeutige Objekte im Zustand binden.
- Update: Der Graph wird mit den neuen impliziten Argumenten und ihren definierenden Queries aktualisiert.
Terminierung: Der Prozess läuft weiter, bis ein Fixpunkt erreicht ist oder eine maximale Tiefenschranke ( $d_{max}$ ) überschritten wird.

3. Lokale Beobachtbarkeit

Das Framework wird um LOCAL SYNTH+ erweitert, das lokale Beobachtbarkeit handhabt. In diesem Setting ist ein Prädikat nur für „lokale" Objekte beobachtbar (jene, die als Argumente in der aktuellen Aktion auftreten). Der Algorithmus modifiziert das Konsistenztestverfahren (TEST*), um anzunehmen, dass nicht-lokale Atome falsch sind, wenn Vorbedingungen getestet werden, wodurch sichergestellt wird, dass unbeobachtete Teile des Zustands das Lernen impliziter Argumente nicht ungültig machen.

Hauptbeiträge

SYNTH+-Algorithmus: Ein allgemeiner Algorithmus zum Lernen von STRIPS+-Domänen aus Spuren mit partieller Beobachtbarkeit sowohl von Aktionen als auch von Zuständen. Er vereinigt die Prädikaterfindung von SIFT mit der Auflösung impliziter Argumente von SYNTH.
Mutex-Features: Eine neuartige Formalisierung, die das Lernen von Prädikaten ermöglicht, bei denen das letzte Argument funktional von den anderen abhängt, was die Wiederherstellung weggelassener Aktionsargumente ohne vollständige Zustandsbeobachtung erlaubt.
Vollständigkeitsresultate: Theoretische Bedingungen werden etabliert, unter denen die Algorithmen vollständig sind:
- SIFT+ (Keine Zustandsbeobachtbarkeit): Erfordert, dass die verborgene STRIPS+-Domäne wohlgeformt, stark zusammenhängend und in ihrem Abhängigkeitsgraphen azyklisch ist (wobei Knoten Prädikate und implizite Variablen sind).
- SYNTH+ (Partielle Zustandsbeobachtbarkeit): Erfordert, dass der auf nicht-beobachtbare Prädikate eingeschränkte Abhängigkeitsgraph azyklisch ist.
- LOCAL SYNTH+: Bewiesen vollständig unter lokaler Beobachtbarkeit für Schlüsselprädikate (Prädikate in Vorbedingungen, die nur implizite Argumente enthalten), sofern diese vollständig beobachtbar sind und andere Prädikate lokal beobachtbar sind.
Generalisierung: Die Arbeit zeigt, dass SIFT und SYNTH Spezialfälle von SYNTH+ sind (wobei $P_\omega = \emptyset$ bzw. $P_\omega = P$ ).

Experimentelle Ergebnisse

Die Autoren bewerteten SIFT+ und SYNTH+ an einer Suite standardisierter Planungsdomänen (z. B. Blocks, Delivery, Grid, Sokoban, Logistics) unter Verwendung erweiterter Spuren, die aus verborgenen STRIPS+-Modellen generiert wurden.

SIFT+-Leistung: Lernerte erfolgreich korrekte Domänen (100 % Verifikationsrate) allein aus Aktionsspuren über alle getesteten Domänen hinweg und stellte durchschnittlich 55 % der Aktionsargumente wieder her, die aus den Spuren weggelassen worden waren.
SYNTH+-Leistung: Lernete korrekte Domänen unter Verwendung deutlich weniger beobachtbarer Prädikate als SYNTH.
- In Delivery lernte SYNTH+ die Domäne unter Beobachtung nur der Agentenposition (at(x)) und statischer Adjazenz, während SYNTH alle fluente Prädikate benötigte.
- In Sokoban und Logistics* lernte SYNTH+ Domänen mit nur beobachteten statischen Prädikaten, ein Szenario, in dem weder SYNTH noch SIFT+ erfolgreich sein konnten.
Effizienz: Die Algorithmen liefen effizient (Sekunden bis Minuten) auf Standardhardware und skalierten auf Domänen mit Tausenden von Spur-Schritten.

Bedeutung und Behauptungen

Die Arbeit behauptet, dass SYNTH+ eine praktische, gehobene Alternative zum modellbasierten Reinforcement Learning bietet, indem es das Lernen dynamischer Modelle aus „natürlichen" Spuren ermöglicht. Diese Spuren erfordern minimale Informationen:

Sie müssen nicht jedes Argument auflisten, das eine formale STRIPS-Kodierung erfordert (z. B. die aktuelle Position eines Blocks, der abgestapelt wird).
Sie erfordern keine vollständige Zustandsbeobachtbarkeit; eine partielle oder lokale Beobachtbarkeit spezifischer Prädikate ist ausreichend.

Die Autoren betonen, dass ihr Ansatz die Lücke zwischen theoretischem Modelllernen (das oft vollständige Beobachtbarkeit annimmt) und praktischer Anwendung (wo Agenten eine begrenzte Wahrnehmung haben) schließt. Durch die Charakterisierung der exakten Bedingungen (Azyklizität von Abhängigkeitsgraphen), unter denen Lernen möglich ist, etabliert die Arbeit einen rigorosen Rahmen für das Lernen gehobener Aktionsmodelle in teilweise beobachtbaren Settings. Die Ergebnisse deuten darauf hin, dass komplexe Domänen aus Spuren rekonstruiert werden können, die nur die Informationen vermitteln, die zur Auswahl von Aktionen notwendig sind, anstatt die vollständige Zustandsbeschreibung.