Über A* hinaus: Bessere Planung mit Transformern

Beyond A*: Bessere Planung mit Transformern

• Transformer-Modelle haben in vielen Anwendungsbereichen große Fortschritte erzielt, bleiben bei der Lösung komplexer Entscheidungsaufgaben jedoch hinter traditionellen symbolischen Planungsmethoden zurück.
• Forschende zeigen eine Methode, Transformer für die Lösung komplexer Planungsaufgaben zu trainieren, und entwickeln das Modell Searchformer, das zuvor ungesehene Sokoban-Rätsel in 93,7 % der Fälle optimal löst und dabei bis zu 26,8 % weniger Suchschritte als die klassische A*-Suche benötigt.
• Searchformer ist ein Encoder-Decoder-Transformer-Modell, das darauf trainiert wurde, das Suchverhalten von A* vorherzusagen, und per Expert Iteration feinabgestimmt wurde, um optimale Pläne mit weniger Suchschritten als A* zu erzeugen.

Trainingsmethode und Leistung

• In der Trainingsmethode wird das Suchverhalten von A* als Token-Sequenz dargestellt, die angibt, wann Zustände im Suchbaum der symbolischen Planung hinzugefügt und entfernt werden.
• In einer Ablationsstudie zur Labyrinthsuche übertrifft Searchformer ein Basismodell, das optimale Pläne direkt vorhersagt, deutlich, obwohl das Modell 5- bis 10-mal kleiner ist und der Trainingsdatensatz 10-mal kleiner ausfällt.
• Die Forschenden zeigen, dass Searchformer bei größeren und komplexeren Entscheidungsaufgaben wie Sokoban wirksam ist, sowohl beim Anteil gelöster Aufgaben als auch bei der Verkürzung des Suchverhaltens.

Meinung von GN⁺

• Diese Studie zeigt neue Einsatzmöglichkeiten von Transformer-Modellen im Bereich der künstlichen Intelligenz. Indem sie für die Lösung komplexer Entscheidungsaufgaben einen effizienteren Ansatz als bestehende symbolische Methoden aufzeigt, markiert sie einen wichtigen Fortschritt für die Erweiterung des Anwendungsspektrums von KI.
• Das Searchformer-Modell demonstriert schnellere und effizientere Problemlösungsfähigkeiten bei geringerem Ressourceneinsatz. Das kann insbesondere bei der Implementierung von KI in ressourcenbeschränkten Umgebungen ein großer Vorteil sein.
• Die Studie deutet darauf hin, dass Fortschritte in der KI nicht zwangsläufig nur von mehr Daten und größeren Modellen abhängen, sondern auch durch intelligentere Methoden und verbesserte Algorithmen erreicht werden können. Das ist ein sehr interessanter und nützlicher Ansatz im Hinblick auf Nachhaltigkeit und Effizienz in der KI-Forschung.

[GN⁺]

Hacker-News-Kommentare

• Es gibt interessante Forschung zum Einsatz von Transformern für die Robotik-Bewegungsplanung. Dass ein Roboterarm sich von einem Punkt zu einem anderen bewegt, ohne Gegenstände zu berühren, ist ein sehr schwieriges Problem, da es hochdimensional und kontinuierlich ist. Frühere Planungsmethoden waren rechnerisch aufwendig und nicht besonders gut. Das ist einer der Gründe, warum Roboterbewegungen „unnatürlich“ wirken und Roboter viele Aufgaben, die wir wollen, nicht gut ausführen. Dieser Ansatz scheint mit anderen Planungsmethoden konkurrenzfähig zu sein und eine schnellere optimale Pfadplanung zu bieten.
• Ich frage mich, ob vor dem Start dieses Forschungswegs der modifizierte J*-Algorithmus ausprobiert wurde, eine optimierte Version des A*-Algorithmus für Spielgraphen/Pfadsuche. Für Interessierte gibt es Informationen zu „Game AI Pro 2“.
• Planung wird bereits gut mit bestehenden Techniken wie Graphsuche, SAT-Solvern, OR, Prolog usw. gelöst. Das Problem ist meist die Optimierung zwischen mehreren ausführbaren Alternativen, und ich bezweifle, dass Transformer dafür gut geeignet sind. Die Rolle der LLM-Technik scheint eher darin zu liegen, natürlichsprachliche Beschreibungen in ausführbare Programme umzuwandeln, und Prolog ist dem sehr nahe, da es letztlich für klassisches NLP entworfen wurde.
• Maschinelle Übersetzung umfasste früher die Entschlüsselung komplexer Grammatik und Suche, aber heute werden dafür Transformer eingesetzt, mit einer viel einfacheren Dekodierung, die kaum noch Suche benötigt. Vielleicht können wir zu einem „vollständigen Bootstrapping“ gelangen, bei dem wir mithilfe der aktuell besten Vorhersagemodelle Heuristiken für die Neural Architecture Search (NAS) lernen und nach neuen neuronalen Blöcken suchen, die besser sind als Transformer und Mamba.
• Die Formulierung „26,8 % weniger Suchschritte als die Standard-A*-Suche“ zeigt eine etwas bessere Leistung als A*, reicht bei Sokoban aber nicht an den Stand der Technik (SOTA) heran. Ich frage mich, was an dieser Arbeit beeindruckend ist und warum sie auf Hacker News gelandet ist.
• Wenn Transformer planen können, braucht AGI (Artificial General Intelligence) vielleicht nur besseres Training.
• Für auditive Lerner wird eine Zusammenfassung dieser Arbeit im Hörbuchformat bereitgestellt.
• Diese Arbeit erinnert mich an die Neural-Network-Diffusion-Arbeit, die gestern auf der HN-Startseite war. In der früheren Arbeit wurde ein Modell trainiert, das SGD-Schritte umgeht, und in dieser Arbeit werden A*-Suchschritte umgangen. Andererseits ist die Wahl der A*-Heuristik für Sokoban nicht gut. Während ich die Arbeit gelesen habe, habe ich 20 Minuten Sokoban gespielt und dabei das Gefühl bekommen, dass die Suchheuristik stark unzureichend ist, weil man für den Fortschritt oft Kisten vom Zielzustand wegbewegen muss.
• Ich frage mich, ob jemand eine Liste klassischer Algorithmen oder NP-vollständiger Probleme pflegt, die inzwischen mit Deep Learning besser gelöst werden.
• Ich bin sehr optimistisch, was den Einsatz gelernter Heuristiken in diskreten Algorithmen wie A* oder Focal Search betrifft. In den meisten modernen Bibliotheken für diskrete Optimierung sind Heuristiken und Tuning – wie bei CPLEX – entscheidend für die Leistung. Ich verstehe weniger, warum man End-to-End-Lernansätze nutzen sollte, um gut verstandene Routinen für die optimale Suche zu ersetzen, aber das ist vielleicht eine übertriebene Sorge. Ich denke, die Autoren haben diese Chance verpasst.