🤖 machine learning

Test-Time Graph Search for Goal-Conditioned Reinforcement Learning

Dieser Beitrag stellt Test-Time Graph Search (TTGS) vor, einen leichtgewichtigen, trainingfreien Planungs-Wrapper, der die inhärente geometrische Struktur bestehender offline zielkonditionierter RL-Richtlinien nutzt, um die Erfolgsquoten bei Aufgaben mit langem Horizont drastisch zu verbessern, ohne zusätzliche Überwachung oder Parameteraktualisierungen zu erfordern.

Ursprüngliche Autoren: Evgenii Opryshko, Junwei Quan, Claas Voelcker, Yilun Du, Igor Gilitschenski

Veröffentlicht 2026-05-26✓ Author reviewed ⓘ

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Evgenii Opryshko, Junwei Quan, Claas Voelcker, Yilun Du, Igor Gilitschenski

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. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie haben einen sehr intelligenten Roboter trainiert, um ein Labyrinth zu navigieren. Sie haben ihm Tausende verschiedener Pfade gezeigt, und er hat gelernt, wie man von Punkt A zu Punkt B gelangt, wenn diese Punkte nahe beieinander liegen. Wenn Sie ihn jedoch bitten, ein riesiges, komplexes Labyrinth von einer Seite zur anderen zu durchqueren, gerät er in Verwirrung. Er versucht, einen riesigen Sprung zu wagen, verfehlt sein Ziel, bleibt in einer Ecke stecken oder die Zeit läuft ab. Dies ist ein häufiges Problem in der Robotik und KI: Die Kurzzeitplanung funktioniert gut, aber die Langzeitplanung scheitert oft.

Dieser Artikel stellt eine clevere „Plug-and-Play"-Lösung namens Test-Time Graph Search (TTGS) vor. Sie erfordert kein erneutes Trainieren des Roboters oder das Beibringen neuer Fähigkeiten. Stattdessen erhält der Roboter direkt vor dem Start eine „Karte" und einen „Führer".

So funktioniert es, unter Verwendung einfacher Analogien:

1. Das Problem: Die Falle des „riesigen Sprungs"

Stellen Sie sich Ihren trainierten Roboter als einen Wanderer vor, der das Gelände für die nächsten 10 Schritte perfekt kennt. Wenn Sie ihm sagen, er soll 100 Schritte zu einem bestimmten Baum gehen, versucht er vielleicht, den ganzen Weg zu sprinten. Da er nicht so weit voraus klar sehen kann, könnte er über einen Stein stolpern oder in eine Sackgasse laufen. In den Begriffen des Artikels wird die „Wertfunktion" des Roboters (seine interne Einschätzung, wie gut ein Zug ist) über große Entfernungen verrauscht und unzuverlässig.

2. Die Lösung: Die „Staffellauf"-Strategie

Anstatt den Roboter zu bitten, den ganzen Marathon auf einmal zu laufen, unterteilt TTGS die Reise in eine Reihe kurzer, handhabbarer Sprints. Es verwandelt die Reise des Roboters in einen Staffellauf.

Die Karte (Der Graph): Das System betrachtet die massive Bibliothek an Trainingsläufen (den Offline-Datensatz), die der Roboter bereits absolviert hat. Es wählt wichtige „Wegpunkte" aus diesen alten Läufen aus und verbindet sie wie Punkte auf einer Karte.
Der Führer (Der kürzeste Pfad): Wenn Sie dem Roboter ein neues Ziel geben, verwendet das System einen klassischen mathematischen Algorithmus (Dijkstra-Algorithmus), um den kürzesten und sichersten Pfad zwischen Start und Ziel zu finden, unter Verwendung nur der Punkte aus den alten Trainingsläufen.
Die Übergaben (Teilziele): Der Roboter betrachtet noch nicht das endgültige Ziel. Er betrachtet nur den nächsten „Wegpunkt" auf der Karte. Sobald er diesen erreicht hat, erhält er eine neue Anweisung, zum nächsten Wegpunkt zu gehen. Er fährt damit fort, bis er das Ziel erreicht.

3. Das Geheimnis: Die „weiche Strafe"

Es gibt einen Haken: Manchmal schlägt die „Karte" eine Abkürzung vor, die kurz aussieht, aber tatsächlich gefährlich ist (wie eine Brücke, die solide aussieht, aber eigentlich kaputt ist). Die Autoren des Artikels stellten fest, dass die interne „Schätzung" des Roboters bezüglich der Entfernung falsch sein kann.

Um dies zu beheben, fügten sie eine weiche Strafe hinzu. Stellen Sie sich vor, die Karte hat eine Regel: „Wenn ein Pfad zu lang oder riskant aussieht, löschen wir ihn nicht, sondern verhängen eine enorme 'Steuer' darauf." Der Planer des Roboters wird den riskanten Pfad zwar noch sehen, aber er wird eine etwas längere, sicherere Route bevorzugen, die aus kleinen, zuverlässigen Schritten besteht. Dies verhindert, dass der Roboter versucht, über Lücken zu springen, die er tatsächlich nicht überqueren kann, während die Karte dennoch verbunden bleibt.

4. Warum es besonders ist

Kein erneutes Training: Sie müssen dem Roboter nichts Neues beibringen. Sie nehmen einfach den bereits gebauten Roboter, geben ihm diesen „Karten-Umschlag", und er funktioniert sofort besser.
Funktioniert mit „eingefrorenen" Strategien: Das Gehirn des Roboters ist „eingefroren" (es kann während des Tests nichts Neues lernen), aber diese Methode hilft ihm, das, was es bereits weiß, effektiver zu nutzen.
Es weiß, wann es aufhören soll: Wenn die Karte nicht genügend „Wegpunkte" hat, um die Lücke zwischen Start und Ziel zu überbrücken (wie der Versuch, einen Canyon ohne Trittsteine zu überqueren), ist das System klug genug zu sagen: „Ich kann dies nicht sicher planen", und lässt den Roboter einfach sein Bestes geben. Es erzwingt keinen schlechten Plan.

Die Ergebnisse

Die Forscher testeten dies an einem Benchmark namens OGBench, der komplexe Labyrinthe für Roboter wie Ameisen und Humanoiden enthält.

Davor: Bei den schwierigsten Labyrinthen scheiterten die Roboter oft vollständig (0 % Erfolgsrate).
Danach: Mit TTGS stiegen die Erfolgsraten in vielen Fällen auf über 90 %.
Vergleich: Diese Leistung entsprach oder übertraf viel komplexere Methoden, die zusätzliches Training, teure Computermodelle oder Online-Übungen erforderten, und das alles bei einer Planungszeit von weniger als einer Sekunde.

Zusammenfassung

Stellen Sie sich TTGS vor, als würden Sie einem geschickten, aber kurzsichtigen Wanderer ein GPS geben, das ihm nur die nächsten paar sicheren Schritte zeigt, basierend auf einer Karte, wo andere Wanderer zuvor erfolgreich gewandert sind. Es verwandelt eine schreckliche, langstreckige Reise in eine Reihe einfacher, selbstbewusster Schritte und ermöglicht dem Roboter, Probleme zu lösen, die er zuvor nicht einmal anzufassen vermochte.

Technische Zusammenfassung: Test-Time Graph Search für zielkonditioniertes Reinforcement Learning

Problemstellung

Offline zielkonditioniertes Reinforcement Learning (GCRL) zielt darauf ab, Agenten zu trainieren, benutzerspezifische Ziele mithilfe vorab gesammelter Datensätze zu erreichen, wodurch die Kosten und Sicherheitsrisiken einer Online-Interaktion vermieden werden. Während dies für Aufgaben mit moderater Horizontlänge effektiv ist, versagen Standard-GCRL-Richtlinien bei Aufgaben mit langem Horizont oft. In komplexen Umgebungen (z. B. großen Labyrinthen) akkumulieren sich Fehler in der Werteschätzung, was zu unzuverlässigen Richtlinien führt, die Verhaltensweisen aus unterschiedlichen Teilen des Datensatzes nicht miteinander verknüpfen können.

Bisherige Lösungen für dieses Problem haben erhebliche Komplexität eingeführt, wie rechenintensive generative Planer, das Training von Ensembles verteilter Wertfunktionen, die Nutzung spezialisierter geometrischer Darstellungen oder die Abhängigkeit von zusätzlichen Daten jenseits des Offline-Datensatzes. Diese Ansätze operieren häufig unter der Annahme, dass Standard-zielkonditionierte Wertfunktionen inhärent zu verrauscht oder unzuverlässig seien, um eine direkte Planung über lange Horizonte zu unterstützen.

Methodik: Test-Time Graph Search (TTGS)

Die Autoren schlagen Test-Time Graph Search (TTGS) vor, einen leichten, trainingfreien Planungs-Wrapper, der eingefrorene GCRL-Richtlinien erweitert. TTGS arbeitet ausschließlich zur Testzeit und erfordert keine zusätzliche Überwachung, Parameteraktualisierungen oder Online-Interaktion.

Kernkomponenten

Graphkonstruktion:
- Eine Teilmenge von Zuständen wird aus dem Offline-Datensatz gesampelt, um als Graphknoten zu dienen.
- Ein Distanzsignal wird verwendet, um Kantengewichte zwischen diesen Knoten zuzuweisen. Dieses Signal kann abgeleitet werden aus:
  - Wertbasierten Distanzen: Abbildung der vortrainierten zielkonditionierten Wertfunktion $V(s, g)$ auf eine geschätzte Schrittzahl $\hat{d}(s, g)$ . Die Arbeit liefert geschlossene Formeln für gängige Belohnungskonventionen (z. B. spärliche Endbelohnungen oder Schrittabzüge).
  - Domänenspezifischen Distanzen: Nutzung geometrischer Metriken wie der euklidischen Distanz zwischen Körperpositionen, sofern verfügbar.
- Weicher Strafmechanismus: Um das Problem zu adressieren, dass Wertfunktionen die Konnektivität überschätzen (was „Wurmlöcher" über Lücken hinweg erzeugt), setzt TTGS eine superlineare Straffunktion $p(\cdot)$ für Übergänge ein, die einen Vertrauensbereichsschwellenwert $\tau$ überschreiten. Kanten mit Distanzen $D_{ij} < \tau$ behalten ihre Rohdistanz, während jene mit $D_{ij} \ge \tau$ ein Gewicht $p(D_{ij})$ zugewiesen bekommen (z. B. $x \cdot 1000^{x/\tau}$ ). Dies bewahrt die lokale metrische Struktur, lenkt den Planer jedoch hin zu Ketten kurzer, vertrauenswürdiger Sprünge, verhindert gleichzeitig eine Fragmentierung des Graphen (wie es ein harter Schwellenwert bewirken würde) oder erlaubt keine unzulässigen langen Sprünge.
Planung zur Testzeit:
- Kürzester-Pfad-Suche: Gegeben ein Startzustand $s_0$ und ein Ziel $g$ , lokalisiert der Algorithmus die nächsten Knoten im Graphen und berechnet einen kürzesten Pfad mittels Dijkstras Algorithmus. Dieser Leitpfad wird einmal pro Episode berechnet.
- Adaptive Subziel-Auswahl: Während der Ausführung folgt der Agent dem Pfad nicht blind. Stattdessen wählt er ein Subziel aus dem vorausberechneten Pfad basierend auf einem Schrittbudget $T$ . Der Agent identifiziert den weitesten Wegpunkt auf dem Pfad, der innerhalb des Budgets $T$ vom aktuellen Zustand entfernt liegt. Existiert kein solcher Wegpunkt, wird der nächste unmittelbare Wegpunkt ausgewählt, um Fortschritte zu gewährleisten.
- Richtlinienausführung: Die eingefrorene Basisrichtlinie $\pi(a | s, \tilde{g})$ wird mit dem aktuellen Zustand und dem ausgewählten Subziel $\tilde{g}$ aufgerufen.

Diagnosewerkzeug

Die Arbeit führt eine größte Sprung-Ratio ( $\rho$ ) als rollout-freies Diagnosewerkzeug ein, um vorherzusagen, ob TTGS für eine neue Aufgabe vorteilhaft sein wird. $\rho$ ist das Verhältnis der maximalen Kantenkosten entlang des geplanten Pfades zur gesamten geschätzten Distanz. Ein niedriges $\rho$ deutet auf eine ausreichende Abdeckung durch Zwischenzustände hin (vorteilhaft für TTGS), während ein hohes $\rho$ darauf hindeutet, dass der Datensatz vermittelnde Zustände vermisst, in welchem Fall TTGS auf das Verhalten der Basisrichtlinie zurückfällt.

Hauptbeiträge

Neubewertung von Wertfunktionen: Die Autoren zeigen, dass Standard-Offline-GCRL-Wertfunktionen, die zuvor als zu unzuverlässig für die Suche galten, genügend lokale geometrische Struktur für robuste Planung über lange Horizonte kodieren, wenn sie mit einem neuartigen weichen Strafmechanismus verarbeitet werden.
Trainingfreies Framework: TTGS bietet eine Methode, um die Leistung bei langen Horizonten zu verbessern, indem bestehende Richtlinien und Wertfunktionen wiederverwendet werden, ohne die Trainingspipeline zu modifizieren, und ohne zusätzliche Überwachung oder Online-Interaktion.
Leistung mit minimalem Overhead: Empirische Ergebnisse zeigen, dass TTGS die Erfolgsquoten für State-of-the-Art-Offline-GCRL-Agenten (HIQL, QRL, GCIQL, SAW, OTA) signifikant steigert, bei vernachlässigbarem Rechenaufwand (Planungszeit < 1 Sekunde pro Episode).

Experimentelle Ergebnisse

Die Methode wurde am OGBench-Benchmark evaluiert, der Lokomotionsaufgaben (pointmaze, antmaze, humanoidmaze) und Manipulationsaufgaben abdeckt.

Lokomotionsaufgaben: TTGS erzielte erhebliche Gewinne bei lang-horizontigen „Stitch"-Aufgaben, bei denen Basisrichtlinien typischerweise versagen.
- Auf pointmaze-giant-stitch-v0 verbesserten sich die Erfolgsquoten für HIQL von 0,0 % auf 80,9 % und für GCIQL von 0,0 % auf 98,0 %.
- Auf humanoidmaze-giant-stitch-v0 verbesserte sich HIQL von 4,4 % auf 78,1 %.
- Diese Verbesserungen entsprachen oft komplexen Methoden, die zusätzliche Trainingsphasen oder generative Modelle erfordern, oder übertrafen diese.
Manipulationsaufgaben: Bei Aufgaben, bei denen Evaluierungsziele außerhalb des Datenmanifolds liegen (z. B. scene-play-v0), erzielte TTGS minimale Gewinne (0–2 Prozentpunkte), verschlechterte jedoch nicht die Leistung, sondern fiel korrekt auf das Verhalten der Basisrichtlinie zurück, wenn Zwischenzustände fehlten.
Ablationsstudien:
- Weiche vs. harte Strafen: Das Entfernen der weichen Strafe (Verwendung von Rohdistanzen) oder die Verwendung eines harten Schwellenwerts (Entfernung langer Kanten) verschlechterte die Leistung bei Stitching-Aufgaben erheblich aufgrund von Graphunterbrechungen oder unzulässigen Pfaden.
- Subziel-Auswahl: Die adaptive Strategie, den weitesten erreichbaren Wegpunkt auszuwählen, schnitt besser ab als eine einfachere Strategie, die stets den nächsten unmittelbaren Wegpunkt auswählt.
- Distanzquellen: TTGS funktionierte effektiv sowohl mit wertbasierten Distanzen als auch mit einfachen euklidischen Distanzen der Körperpositionen, was Flexibilität demonstriert.

Bedeutung und Behauptungen

Die Arbeit behauptet, dass die zusätzliche Komplexität, die oft für die Planung über lange Horizonte als notwendig erachtet wird, häufig unnötig ist. Durch die Nutzung der latenten geometrischen Struktur, die bereits in Standard-Wertfunktionen vorhanden ist, und die Anwendung einer leichten Graphensuche zur Testzeit können Praktiker die Fähigkeiten bestehender Offline-GCRL-Agenten erheblich erweitern.

Die Autoren betonen, dass TTGS ein konservatives, sicheres Planungs-Wrapper ist: Es stützt sich ausschließlich auf abgerufene Datensatzzustände und vermeidet die Synthese physikalisch unmöglicher Trajektorien, die bei generativen Ansätzen üblich sind. Wenn die Offline-Daten die notwendigen Zwischenzustände fehlen, um Start und Ziel zu verbinden, fällt TTGS elegant auf das Verhalten der Basisrichtlinie zurück, anstatt unzuverlässige Pläne zu erzeugen. Die Arbeit legt nahe, dass wertbasierte GCRL-Agenten oft eine nützliche geometrische Struktur ungenutzt lassen, und TTGS bietet ein Rezept, um diese Struktur für die Planung über lange Horizonte ohne Neutraining wiederzugewinnen.