Partielle Grounding-Strategie verbessert SAT-Planung linear

In der klassischen Planungsforschung werden Probleme üblicherweise mit hochrangigen, first‑order‑repräsentierten Modellen beschrieben. Diese kompakte Darstellung wird von den meisten Planern jedoch vollständig „grounded“, also in konkrete Instanzen übersetzt, was häufig zu einem exponentiellen Anstieg der Problemgröße führt. Neuere Ansätze versuchen, das Grounding zu vermeiden und direkt auf dem hochrangigen Niveau zu arbeiten.

Die neue Arbeit schlägt einen Mittelweg vor: Drei SAT‑Encodings werden vorgestellt, die Aktionen unverändert hochrangig lassen, aber die Prädikate teilweise grounden. Dadurch bleibt die Modellgröße deutlich kleiner, während gleichzeitig die Vorteile eines SAT‑Backends genutzt werden. Im Gegensatz zu bisherigen Encodings, deren Komplexität quadratisch mit der Planlänge wächst, skaliert die neue Methode linear. Das bedeutet, dass längere Pläne effizienter verarbeitet werden können.

Experimentelle Ergebnisse zeigen, dass das beste Encoding die aktuelle Spitzenleistung in der Längen‑optimierten Planung übertrifft – besonders in Domänen, die sich schwer vollständig grounden lassen. Diese Fortschritte markieren einen wichtigen Schritt, um SAT‑basierte Planer für komplexere, realweltliche Aufgaben einzusetzen.