Improving Plan Execution Flexibility using Block-Substitution

Diese Studie verbessert die Ausführungsflexibilität von KI-Plänen, indem sie Subpläne in Block-dekomponierten Partial-Order-Plänen durch externe Aktionen ersetzt und redundante Aktionen eliminiert, was zu einer signifikanten Steigerung der Flexibilität auf IPC-Benchmark-Problemen führt.

Das Wesentliche

Das große Problem: Der zu starre Fahrplan

Stell dir vor, du planst eine große Reise. Ein herkömmlicher Reiseplan (ein "sequenzieller Plan") ist wie ein strenger Zugfahrplan: Du musst um 8:00 Uhr am Bahnhof sein, um 8:05 Uhr einsteigen, um 8:10 Uhr abfahren. Wenn sich etwas ändert – vielleicht ist der Zug verspätet oder du hast einen Kaffee vergessen – ist dein ganzer Plan kaputt. Du musst alles neu berechnen.

In der künstlichen Intelligenz (KI) passiert genau das, wenn ein Roboter oder ein Software-Agent einen Plan erstellt. Oft sind diese Pläne zu starr. Sie sagen genau, welche Aktion vor welcher anderen passieren muss, auch wenn es eigentlich egal wäre. Das nennt man Partial-Order Planning (Teilordnungs-Planung). Die Idee dahinter ist gut: "Mach erst das, was du kannst, und entscheide dich erst später, was als Nächstes kommt." Das gibt Flexibilität. Aber die Forscher haben festgestellt: Selbst diese flexiblen Pläne sind oft noch unnötig starr.

Die Lösung: "Block-Substitution" (Der Tausch-Deal)

Die Autoren dieses Papers, Sabah Binte Noor und Fazlul Hasan Siddiqui, haben eine neue Methode entwickelt, die sie FIBS nennen. Stell dir das wie einen cleveren Umzug oder einen Tauschhandel vor.

1. Das Einpacken in Kisten (Blöcke)

Stell dir deinen Plan wie eine lange Kette von Aufgaben vor. Die Forscher packen zusammengehörige Aufgaben in Kisten (Blöcke).

• Beispiel: Wenn du einen Kaffee machst, sind "Wasser kochen" und "Tasse holen" in einer Kiste. "Kaffeebohnen mahlen" ist in einer anderen.
• Durch das Einpacken in Kisten können sie sehen: "Hey, diese ganze Kiste mit dem Kaffee muss nicht unbedingt vor dieser Kiste mit dem Toast gemacht werden. Wir können sie parallel machen!" Das macht den Plan flexibler.

2. Der Tausch (Substitution)

Das ist der geniale Teil. Normalerweise sagen Planungs-Programme: "Ich habe diese Kiste mit dem Kaffee. Ich kann sie nicht ändern."
Die neue Methode sagt: "Nein, wir können die Kiste austauschen!"

Stell dir vor, dein Plan sagt: "Nimm den alten Aufzug (Aufzug A), fahre hoch, hol den Passagier, fahre runter."
Die KI denkt sich: "Moment mal. Ich habe hier einen neuen, schnelleren Aufzug (Aufzug B) in der Nähe. Wenn ich die ganze Kiste mit dem alten Aufzug durch eine neue Kiste mit dem neuen Aufzug ersetze, kann ich vielleicht sogar den Weg abkürzen oder den alten Aufzug ganz weglassen, weil er jetzt überflüssig ist."

Das nennt man Block-Substitution. Sie tauschen einen Teil des Plans gegen einen besseren Teil aus, der von außen kommt (oder aus einem anderen Teil des Plans), um den Rest des Plans flexibler zu machen.

Warum ist das besser als die alten Methoden?

Bisher gab es zwei Hauptmethoden, um Pläne flexibler zu machen:

1. Das Löschen von Regeln: Man versucht, unnötige "Muss-davor-kommen"-Regeln zu streichen. (Wie wenn man im Zugfahrplan die Regel streicht: "Du musst den Kaffee trinken, bevor du einsteigst".)
2. Das MaxSAT-Verfahren: Das ist wie ein riesiges mathematisches Puzzle, bei dem ein Computer versucht, die perfekte Reihenfolge zu finden. Das Problem: Es dauert ewig und ist bei großen Plänen oft unmöglich zu lösen.

Der Vorteil von FIBS:

• Es ist schnell: Es schaut nicht auf den ganzen riesigen Plan gleichzeitig, sondern tauscht nur kleine Kisten aus. Das ist wie das Reparieren eines Autos, indem man nur den defekten Motor austauscht, statt das ganze Auto neu zu bauen.
• Es findet neue Wege: Während die alten Methoden nur die Reihenfolge der gleichen Aufgaben ändern durften, darf FIBS die Aufgaben selbst ersetzen. Vielleicht ist der "alte Aufzug" gar nicht nötig, wenn wir einen "neuen Aufzug" nehmen.
• Es spart Zeit: In Tests hat FIBS viel schneller bessere Ergebnisse geliefert als die mathematischen Puzzle-Lösungen, besonders bei großen, komplexen Plänen.

Ein konkretes Beispiel aus dem Papier

Stell dir ein Gebäude mit zwei Aufzügen vor.

• Der alte Plan: Der Aufzug A muss erst Person 1 holen, dann runterfahren, dann Person 2 holen. Alles streng nacheinander.
• Die neue Methode (FIBS): Die KI erkennt: "Moment, Aufzug B steht unten und ist leer. Ich tausche den Teil des Plans aus, wo Aufzug A runterfährt, gegen einen neuen Plan, bei dem Aufzug B Person 2 holt."
• Das Ergebnis: Jetzt müssen Aufzug A und Aufzug B nicht mehr warten. Sie können gleichzeitig fahren! Der Plan ist flexibler, schneller und manchmal sogar billiger, weil überflüssige Fahrten gestrichen werden.

Fazit für den Alltag

Die Forscher haben im Grunde eine Methode entwickelt, wie man einen strengen To-Do-Liste in einen flexiblen, dynamischen Spielplan verwandelt. Anstatt nur die Reihenfolge der Aufgaben zu mischen, schaut sie sich an, ob man eine ganze Aufgabe durch eine bessere ersetzen kann, um den Rest des Tages entspannter zu gestalten.

Sie nennen ihre Methode FIBS (Flexibility Improvement via Block-Substitution). Und die Ergebnisse zeigen: Wenn man Pläne so intelligent "tauscht" und "bereinigt", werden Roboter und Software viel besser darin, sich an unvorhergesehene Änderungen anzupassen, ohne dass der Computer stundenlang nachdenken muss.

Kurz gesagt: Statt starr an einem Plan festzuhalten, erlaubt diese Methode, Teile des Plans gegen bessere Alternativen zu tauschen, damit das Ganze schneller und flexibler läuft.

Technische Zusammenfassung

1. Problemstellung und Motivation

In der KI-Planung (Artificial Intelligence Planning) ist die Flexibilität eines Plans entscheidend für den Einsatz in dynamischen Umgebungen, in denen unerwartete Änderungen auftreten können. Partielle Ordnungspläne (Partial-Order Plans, POPs) bieten im Vergleich zu sequenziellen Plänen mehr Flexibilität, da sie keine feste Reihenfolge für alle Aktionen vorschreiben, sondern nur notwendige Abhängigkeiten auflösen. Dies ermöglicht parallele Ausführung und Anpassungsfähigkeit bei Ressourcenfluktuationen oder variierenden Aktionsdauern.

Bisherige Ansätze zur Maximierung dieser Flexibilität konzentrierten sich auf:

• Plan-Deordering: Das Entfernen unnötiger Ordnungsbeschränkungen innerhalb eines bestehenden Plans.
• Plan-Reordering: Das willkürliche Ändern von Ordnungen, oft unter Verwendung von MaxSAT-Encodings, um die Anzahl der Beschränkungen zu minimieren.

Ein zentrales Limit dieser traditionellen Methoden ist, dass sie die Aktionen (Operatoren) des Plans nicht verändern. Sie können keine neuen Aktionen einführen oder redundante Aktionen durch alternative, effizientere Subpläne ersetzen, die außerhalb des ursprünglichen Plans liegen. Das Paper adressiert die Frage, wie die Flexibilität eines Plans weiter gesteigert werden kann, indem nicht nur die Reihenfolge, sondern auch die Inhalte von Teilplänen (Subplans) durch andere Aktionen ersetzt werden, ohne dabei die Gültigkeit des Plans oder die Kosten zu verschlechtern.

2. Methodik: Block-Substitution und FIBS

Die Autoren schlagen einen neuen Ansatz vor, der auf der Block-Substitution basiert. Der Kern der Methode besteht darin, Teilpläne innerhalb einer hierarchischen Struktur durch alternative Subpläne zu ersetzen, um die Flexibilität zu erhöhen.

2.1 Block-Decomposed Partial-Order (BDPO) Pläne

Die Methode baut auf dem Konzept der Block-Deordering auf. Dabei werden kohärente Aktionen in einem POP zu Blöcken gruppiert. Ein BDPO-Plan ist eine 3-Tupel-Struktur $\langle O, B, \prec \rangle$, wobei $O$ Operatoren, $B$ Blöcke und $\prec$ Ordnungsbeschränkungen sind. Blöcke können verschachtelt sein, aber nicht überlappen. Dies erlaubt es, ganze Teilpläne als Einheiten zu behandeln.

2.2 Der Block-Substitution Algorithmus

Das Herzstück ist der Substitute-Algorithmus (Algorithmus 2). Er ersetzt einen Block $b_x$ in einem gültigen BDPO-Plan durch einen neuen Block $\hat{b}_x$ (der aus dem Plan stammen oder extern generiert werden kann).

• Kausalitäts-Links: Der Algorithmus stellt sicher, dass alle Präkonditionen des neuen Blocks durch Kausalitäts-Links (Causal Links) unterstützt werden und dass die Links, die der alte Block bereitstellte, nun vom neuen Block übernommen werden.
• Bedrohungen (Threats): Es wird geprüft, ob die Substitution neue Bedrohungen (z. B. durch das Löschen von Fakten) einführt. Diese werden durch Promotion/Demotion (Hochstufen/Herabstufen von Ordnungen) oder durch interne Substitutionen gelöst.
• Korrektheit: Der Algorithmus garantiert, dass das Ergebnis ein gültiger BDPO-Plan ist, wenn keine Zyklen entstehen.

2.3 Der FIBS Algorithmus (Flexibility Improvement via Block-Substitution)

Der übergeordnete FIBS-Algorithmus (Algorithmus 4) integriert diese Substitution in einen iterativen Prozess, der auf einem sequenziellen Plan aufbaut:

1. EOG (Explanation-based Order Generalization): Umwandlung des sequenziellen Plans in einen POP.
2. SD1 (Substitution-Deorder 1): Substitution von primitiven Blöcken (einzelne Operatoren), um Ordnungen zu entfernen.
3. Block-Deordering (BD): Bildung komplexer Blöcke aus kohärenten Operatoren, um weitere Ordnungen zu eliminieren.
4. SD2 (Substitution-Deorder 2): Substitution sowohl primitiver als auch komplexer Blöcke.

Kriterien für die Akzeptanz einer Substitution:
Eine Substitution wird nur akzeptiert, wenn sie die Relative Flexibility Optimization (RFO) erfüllt:

• Die Flexibilität ($flex$) des neuen Plans muss strikt höher sein als die des alten Plans.
• Die Kosten ($cost$) des neuen Plans dürfen nicht höher sein als die des alten Plans.
• Hinweis: Es wird auch eine Variante mit Relative Cost Optimization (RCO) untersucht, die Kosten priorisiert, um redundante Aktionen zu entfernen.

2.4 Redundanzreduktion

Zusätzlich zur Substitution wendet FIBS Strategien zur Planreduktion an (Backward Justification und Greedy Justification), um redundante Operatoren oder Blöcke zu identifizieren und zu entfernen, was die Plankosten senkt.

3. Wichtige Beiträge

1. Neue Paradigmen: Einführung der Block-Substitution, die über traditionelles Deordering/Reordering hinausgeht, indem sie den Inhalt von Plänen (Subpläne) durch externe oder alternative interne Lösungen ersetzt.
2. BDPO-Struktur: Nutzung von Block-Decomposed Partial-Order Plänen als flexible Hierarchie, die Substitutionen ermöglicht, ohne die Planvalidität zu gefährden.
3. Algorithmische Korrektheit: Beweis der Korrektheit des Substitute-Algorithmus (Theorem 1) und Nachweis der Unvollständigkeit (Theorem 2), da der Algorithmus aufgrund der Wahl des "frühesten Produzenten" (earliest candidate producer) nicht alle möglichen Lösungen findet, aber effizient ist.
4. Integration von Redundanzreduktion: Kombination von Substitution mit Justification-Methoden, um sowohl Flexibilität als auch Kosten zu optimieren.
5. Umfassende Evaluation: Experimente auf 32 Domänen der International Planning Competitions (IPC) mit 3826 Plänen.

4. Experimentelle Ergebnisse

Die Autoren verglichen FIBS mit etablierten Methoden:

• EOG (Basis-Deordering).
• MR (MaxSAT Reordering, Muise et al.).
• MRR (MaxSAT Reordering mit Reinstatement, Waters et al.).

Ergebnisse:

• Flexibilität: FIBS erreicht eine durchschnittliche Flexibilität von 0,32, während MR bei 0,23 und MRR bei 0,25 liegt. FIBS verbessert die Flexibilität in 30 von 32 Domänen signifikant.
• Laufzeit und Skalierbarkeit:
  • MaxSAT-Methoden (MR/MRR) haben eine sehr hohe Laufzeit (Durchschnitt ~242s für MR, ~1039s für MRR) und eine geringere Abdeckung (Coverage), besonders bei großen Plänen (>200 Operatoren), da die Encodings exponentiell wachsen.
  • FIBS erreicht eine volle Abdeckung (100%) mit einer durchschnittlichen Laufzeit von nur 106 Sekunden.
  • FIBS skaliert linear mit der Plangröße, während MR/MRR schnell an die Zeitgrenze (1800s) stoßen.
• Kombination mit MaxSAT: Die Anwendung von FIBS auf die Ergebnisse von MR und MRR (z. B. MR+FIBS) führt zu weiteren Verbesserungen der Flexibilität, zeigt aber, dass FIBS allein oft effizienter ist.
• Kostenreduktion: Durch die Anwendung von Greedy Justification (FIBS_GJ) konnte die Plankosten im Durchschnitt um 5,91% reduziert werden, was mit der Minimal Plan Reduction (MPR) Methode vergleichbar ist, aber oft schneller berechnet wird.

5. Bedeutung und Fazit

Das Paper demonstriert, dass die Substitution von Subplänen ein mächtigeres Werkzeug zur Flexibilisierung von Plänen ist als das reine Umordnen oder Entfernen von Beschränkungen.

• Praktische Relevanz: FIBS bietet einen Anytime-Algorithmus, der auch bei begrenzter Rechenzeit gute Ergebnisse liefert und in dynamischen Umgebungen eingesetzt werden kann, wo schnelle Anpassungen nötig sind.
• Effizienz: Im Gegensatz zu rechenintensiven globalen Optimierungen (wie MaxSAT) nutzt FIBS lokale Suchstrategien innerhalb einer hierarchischen Struktur, was es für große Planungsprobleme skalierbar macht.
• Zukunftsausblick: Die Autoren schlagen vor, die Suche nach Substitutionskandidaten zu erweitern (z. B. durch zufällige Blockbildung) und andere Planer als LAMA zu testen, um die Robustheit weiter zu erhöhen.

Zusammenfassend stellt FIBS einen signifikanten Fortschritt dar, der die Lücke zwischen der Effizienz sequenzieller Pläne und der Flexibilität partieller Ordnungspläne schließt, indem es die Möglichkeit eröffnet, Pläne strukturell durch bessere Alternativen zu ersetzen, anstatt sie nur neu zu ordnen.