Improving Execution Concurrency in Partial-Order Plans via Block-Substitution

Diese Arbeit stellt notwendige und hinreichende Bedingungen für Nicht-Konkurrenz-Bedingungen zwischen Aktionen oder Teilplänen vor und führt einen Algorithmus ein, der die Ausführungskonkurrenz in Partial-Order-Plänen durch Block-Substitution und Ressourcenoptimierung signifikant verbessert.

Das Wesentliche

🚀 Der Plan, der nicht starr ist: Wie KI-Aufgaben schneller erledigt werden

Stellen Sie sich vor, Sie sind der Chef einer großen Baustelle oder ein Dirigent eines Orchesters. Ihr Ziel ist es, eine komplexe Aufgabe zu erledigen – sagen wir, ein Haus zu bauen oder ein Konzert aufzuführen.

In der Welt der Künstlichen Intelligenz (KI) nennt man diese Aufgaben „Pläne". Ein Plan ist eine Liste von Schritten (Aktionen), die durchgeführt werden müssen, um ein Ziel zu erreichen.

Das Problem: Der starre Fahrplan

Früher waren diese Pläne wie ein starrer Zugfahrplan. Wenn Schritt A vor Schritt B kommen muss, dann muss er das. Und wenn Schritt C vor Schritt D kommt, dann auch das.
Das Problem dabei: Wenn Sie zwei Schritte haben, die eigentlich nichts miteinander zu tun haben (z. B. „Mauer mauern" und „Fenster putzen"), zwingt der Plan Sie oft trotzdem, sie nacheinander zu machen. Das ist ineffizient. Es ist, als würde ein Maurer warten, während der Fensterputzer auf eine Leiter wartet, obwohl beide eigentlich gleichzeitig arbeiten könnten.

In der KI-Forschung nennt man das einen Partial-Order-Plan (POP). Das ist schon etwas flexibler als ein starrer Fahrplan, aber er hat immer noch viele unnötige „Wartezeiten" oder Regeln, die verhindern, dass Dinge parallel laufen.

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

Die Autoren dieses Papers (Sabah Binte Noor und Fazlul Hasan Siddiqui) haben sich gefragt: „Wie können wir diesen Plan noch flexibler machen, damit mehr Dinge gleichzeitig passieren können, ohne dass das Haus einstürzt?"

Ihre Idee lässt sich mit einem Koch-Rezept vergleichen:

1. Der ursprüngliche Plan: Sie müssen erst den Teig kneten, dann den Ofen vorheizen, dann den Kuchen backen. Aber warten Sie mal! Das Vorheizen des Ofens kann eigentlich während des Knetens passieren.
2. Block-Deordering (Das Gruppieren): Die Forscher gruppieren zusammengehörige Schritte zu „Blöcken". Statt jeden einzelnen Schritt zu betrachten, sagen sie: „Dieser ganze Block 'Teig vorbereiten' muss vor dem Block 'Kuchen backen' kommen." Das entfernt viele unnötige Regeln.
3. Das eigentliche Problem (Ressourcen-Konflikte): Manchmal können zwei Blöcke trotzdem nicht parallel laufen, weil sie denselben „Werkzeugkasten" brauchen.
   • Beispiel aus dem Paper: Stellen Sie sich zwei Aufzüge vor. Ein Aufzug muss Leute von der 1. in die 3. Etage bringen, ein anderer von der 2. in die 1. Etage. Wenn es nur einen Aufzug gibt, müssen sie warten. Der Aufzug kann nicht gleichzeitig oben und unten sein. Das ist ein Konflikt.

Der geniale Trick: Block-Substitution (Der Tausch)

Hier kommt die eigentliche Innovation ins Spiel. Anstatt zu sagen: „Okay, wir müssen warten", fragen die Forscher: „Gibt es eine andere Möglichkeit, diesen Teil der Aufgabe zu erledigen, die keinen Konflikt verursacht?"

• Die Analogie:
  Stellen Sie sich vor, Sie müssen zwei schwere Kisten transportieren.
  • Plan A: Ein einziger Lieferwagen muss beide Kisten nacheinander fahren (weil er nur eine Ladefläche hat). Das dauert lange.
  • Der Trick (Substitution): Die KI schaut sich den Plan an und sagt: „Moment, wir haben doch noch einen zweiten Lieferwagen im Park!"
  • Sie ersetzen den Teil des Plans, der den ersten Wagen benutzt, durch einen neuen Teil, der den zweiten Wagen benutzt.
  • Ergebnis: Jetzt können beide Kisten gleichzeitig transportiert werden! Der Plan ist schneller, ohne dass das Ziel (die Kisten am Zielort) verändert wurde.

Was die Forscher genau gemacht haben

1. Regeln aufgestellt: Sie haben mathematisch bewiesen, wann zwei Dinge wirklich nicht gleichzeitig gemacht werden können (z. B. wenn sie denselben Aufzug oder denselben Roboterarm brauchen).
2. Algorithmus entwickelt (CIBS): Sie haben einen Computer-Algorithmus gebaut, der:
   • Erst den Plan in Blöcke packt.
   • Dann prüft: „Können diese Blöcke parallel laufen?"
   • Wenn nein: „Können wir einen der Blöcke durch eine andere Variante ersetzen, die einen anderen 'Aufzug' benutzt?"
3. Ergebnis: In Tests mit echten KI-Herausforderungen (wie Logistikaufgaben oder Elevator-Simulationen) konnten sie die Pläne so optimieren, dass sie viel schneller fertig waren.

Warum ist das wichtig?

Stellen Sie sich vor, Sie planen eine große Hochzeit.

• Ohne diese Methode: Der Gärtner wartet, bis der Florist fertig ist, obwohl sie eigentlich unabhängig voneinander arbeiten könnten. Der Koch wartet auf den Teller, obwohl er schon kochen könnte.
• Mit dieser Methode: Der Algorithmus erkennt: „Aha, der Florist braucht die Vase, aber der Gärtner braucht die Schaufel. Kein Problem!" Oder noch besser: „Der Gärtner braucht die Vase? Kein Problem, wir leihen uns eine zweite Vase und lassen beide gleichzeitig arbeiten."

Zusammenfassend:
Die Forscher haben eine Methode entwickelt, um KI-Pläne nicht nur zu „entwirren" (weniger starre Regeln), sondern sie auch intelligent zu „tauschen". Wenn ein Schritt einen Engpass verursacht (wie einen einzigen Aufzug), suchen sie automatisch nach einer Alternative (einem zweiten Aufzug), damit alles gleichzeitig ablaufen kann. Das macht Prozesse schneller, effizienter und flexibler.

Technische Zusammenfassung

1. Problemstellung

In der KI-Planung (AI Planning) werden Partial-Order-Pläne (POP) verwendet, um Aktionen nicht strikt sequenziell, sondern mit flexiblen Ordnungsbeziehungen darzustellen. Dies ermöglicht eine höhere Ausführungsflexibilität und erleichtert Aufgaben wie Plan-Wiederverwendung oder -Modifikation.

Ein zentrales Ziel ist jedoch die Reduzierung der gesamten Ausführungszeit durch parallele Ausführung von Aktionen. Während die Flexibilität bezüglich der Reihenfolge von Aktionen (Flexibilität) gut erforscht ist (durch Deordering und Reordering), gibt es weniger Forschung zur Concurrency (Parallelisierbarkeit).

• Das Problem: Selbst wenn Aktionen in einem POP keine Ordnungsbeschränkungen zueinander haben, können sie oft nicht parallel ausgeführt werden, da sie dieselben Ressourcen nutzen (z. B. derselbe Lift in einem Elevator-Domain).
• Konzept: Um dies zu modellieren, werden Nicht-Konkurrenz-Bedingungen (Non-Concurrency Constraints, #) eingeführt. Diese spezifizieren, welche Aktionen oder Blöcke nicht parallel laufen dürfen.
• Herausforderung: Bestehende Methoden wie Block-Deordering können Ordnungsbeschränkungen entfernen, aber die daraus resultierenden Blöcke behalten oft Nicht-Konkurrenz-Bedingungen bei, da sie dieselben Ressourcen beanspruchen. Eine reine Umordnung reicht hier nicht aus; es ist notwendig, die zugrundeliegenden Ressourcenkonflikte durch Substitution zu lösen.

2. Methodik

Die Autoren schlagen einen mehrstufigen Ansatz vor, der auf Finite Domain Representation (FDR) und Block-Substitution basiert.

A. Semantische Grundlagen

• FDR & DTG: Die Planungsaufgaben werden als Finite Domain Representation modelliert, wobei Zustandsvariablen und deren Übergänge durch Domain Transition Graphs (DTG) dargestellt werden. Dies erlaubt eine präzise Analyse von Ressourcenkonflikten.
• Parallel Block Decomposed (PBD) Plan: Die Autoren definieren einen PBD-Plan als Tupel $\langle O, B, \prec, \# \rangle$, der neben Aktionen ($O$), Blöcken ($B$) und Ordnungsbeschränkungen ($\prec$) auch explizite Nicht-Konkurrenz-Bedingungen ($\#$) enthält.
• Bedingungen für Nicht-Konkurrenz: Es werden notwendige und hinreichende Bedingungen für Nicht-Konkurrenz zwischen zwei Operatoren oder Blöcken hergeleitet. Zwei Aktionen sind nicht konkurrenzfähig, wenn sie unterschiedliche Vorbedingungen oder Effekte auf derselben Variablen haben (z. B. ein Lift kann nicht gleichzeitig auf Etage 1 und Etage 2 sein).

B. Der CIBS-Algorithmus (Concurrency Improvement via Block-Substitution)

Der Kern der Arbeit ist der CIBS-Algorithmus, der in drei Phasen abläuft:

1. EOG (Explanation-based Order Generalization): Ein sequenzieller Plan wird in einen POP umgewandelt, indem unnötige Ordnungsbeschränkungen entfernt werden.
2. Block-Deordering (BD): Zusammenhängende Aktionen werden zu Blöcken (Subplänen) gruppiert. Dies eliminiert weitere Ordnungsbeschränkungen und erzeugt einen BDPO-Plan (Block Decomposed Partial-Order).
3. Substitution für Concurrency (SC): Dies ist die innovative Phase.
   • Erweiterung von Blöcken (EXTEND): Bevor ein Block ersetzt wird, wird er ggf. um seine Vorgänger oder Nachfolger erweitert. Dies ist notwendig, um sicherzustellen, dass der neue Subplan die gleichen Vorbedingungen erfüllt und die gleichen Effekte erzielt wie der ursprüngliche Block (basierend auf dem DTG).
   • Substitution: Der Algorithmus sucht nach alternativen Subplänen (unter Verwendung eines externen Planers wie LAMA), die die gleiche Aufgabe lösen, aber andere Ressourcen verwenden.
   • Ziel: Ein Block, der z. B. Lift $e_1$ nutzt, wird durch einen Subplan ersetzt, der Lift $e_2$ nutzt. Dadurch entfällt die Nicht-Konkurrenz-Bedingung zwischen diesem Block und anderen Blöcken, die $e_1$ nutzen.
   • Validierung: Die Substitution wird nur durchgeführt, wenn der resultierende Plan gültig bleibt, die Kosten nicht steigen und die Concurrency (gemessen durch $cflex$) steigt.

3. Wichtige Beiträge

1. Formalisierung: Herleitung notwendiger und hinreichender Bedingungen für Nicht-Konkurrenz-Bedingungen zwischen Aktionen und Subplänen in FDR-Umgebungen.
2. PBD-Plan: Einführung des Konzepts des Parallel Block Decomposed Plans mit expliziten Nicht-Konkurrenz-Bedingungen.
3. Block-Erweiterung: Ein Verfahren, um Blöcke zu erweitern, damit sie als Substitutionskandidaten für Ressourcenkonflikte geeignet sind.
4. CIBS-Algorithmus: Ein neuer Algorithmus, der Block-Deordering mit Block-Substitution kombiniert, um Nicht-Konkurrenz-Bedingungen aktiv zu eliminieren.
5. Metrik $cflex$: Einführung einer normalisierten Metrik ($cflex$), die das Verhältnis paralleler Aktionspaare zur Gesamtzahl der Paare misst. Die Autoren zeigen eine starke negative Korrelation zwischen $cflex$ und der minimalen Ausführungsdauer.

4. Ergebnisse

Die Methode wurde an 3303 Plänen aus 33 verschiedenen Domänen der International Planning Competitions (IPC) getestet.

• Verbesserung der Concurrency: Der CIBS-Algorithmus konnte die $cflex$-Werte signifikant verbessern.
  • Der Durchschnittswert für $cflex$ stieg von 0,237 (nach EOG) auf 0,241 (nach Block-Deordering) und 0,242 (nach Substitution).
  • In spezifischen Domänen wie Logistics, Elevator und Rovers waren die Verbesserungen besonders deutlich.
• Korrelation mit Laufzeit: Es wurde eine starke negative Korrelation (-0,96) zwischen $cflex$ und der minimalen Ausführungsdauer festgestellt. Ein höherer $cflex$-Wert bedeutet also eine kürzere theoretische Mindestlaufzeit.
• Vergleich mit MaxSAT: Im Vergleich zu MaxSAT-basierten Ansätzen (MR, MRR), die versuchen, Ordnungen zu minimieren, bietet CIBS eine bessere Balance zwischen Rechenzeit und Ergebnisqualität. MaxSAT-Ansätze benötigen deutlich mehr Zeit und haben oft eine geringere Abdeckung (Coverage) bei großen Problemen. CIBS liefert schnell gute Ergebnisse.
• Skalierbarkeit: Die Methode funktioniert besonders gut bei Planen mittlerer Größe (50–300 Operatoren). Bei sehr großen Plänen (>350 Operatoren) nimmt die Verbesserung aufgrund der Rechenzeitbegrenzung ab.

5. Bedeutung

Die Arbeit ist bedeutend, da sie über die reine Umordnung von Aktionen hinausgeht. Sie erkennt an, dass Ressourcenkonflikte oft die eigentliche Barriere für Parallelität sind und nicht nur fehlende Ordnungsbeschränkungen.

• Durch die Substitution von Ressourcen (z. B. Nutzung eines zweiten Roboters oder Lifts) wird eine echte Parallelisierung ermöglicht, die durch reine Deordering nicht erreichbar wäre.
• Der Ansatz ist effizienter als globale Optimierungsmethoden (wie MaxSAT), da er lokal auf Blöcken operiert und die Struktur des Plans nutzt.
• Die Einführung von $cflex$ als Metrik bietet ein neues, aussagekräftiges Werkzeug zur Bewertung der Parallelisierbarkeit von Plänen, das besser mit der tatsächlichen Ausführungszeit korreliert als die reine Flexibilitätsmetrik ($flex$).

Zusammenfassend bietet das Paper einen robusten Rahmen, um Partial-Order-Pläne nicht nur flexibler in der Reihenfolge, sondern auch effektiver in der parallelen Ausführung zu gestalten, indem es Ressourcenkonflikte durch intelligente Substitution auflöst.