Compiling Temporal Numeric Planning into Discrete PDDL+: Extended Version

Diese Arbeit stellt eine praktische, polynomielle Kompilierung vor, die zeitliche numerische Planung mit dauerhaften Aktionen vollständig in die Sprache PDDL+ übersetzt und dabei die Semantik erhält sowie die Planlänge nur um einen konstanten Faktor erhöht.

Das Wesentliche

Stell dir vor, du bist der Chef eines riesigen, chaotischen Küchen-Teams. Deine Aufgabe ist es, einen perfekten Kochplan zu erstellen, damit am Ende ein festliches Dinner serviert wird.

Das ist im Grunde das Problem, das diese Forscher lösen wollen: Wie plant man komplexe Aufgaben, bei denen Dinge Zeit brauchen und sich Zahlen (wie Zutatenmengen) ständig ändern?

Hier ist die einfache Erklärung der Forschung, übersetzt in eine Geschichte:

1. Das Problem: Zwei verschiedene Sprachen

In der Welt der Robotik und künstlichen Intelligenz gibt es zwei verschiedene "Sprachen" (oder Werkzeuge), um solche Pläne zu beschreiben:

• Sprache A (PDDL 2.1): Das ist wie ein Kochbuch mit genauen Zeitangaben. Es sagt: "Schneide die Zwiebeln für 30 Sekunden" oder "Koche die Soße, während du den Salat schneidest". Es ist sehr gut für Dinge, die eine bestimmte Dauer haben. Aber es ist manchmal etwas starr, wenn es um komplexe Zahlen oder verzögerte Effekte geht.
• Sprache B (PDDL+): Das ist wie ein lebendiges Ökosystem. Hier gibt es keine festen "Aktionen", sondern eher Prozesse (wie ein Wasserhahn, der ständig läuft), Ereignisse (wie ein Alarm, der losgeht, wenn der Topf kocht) und sofortige Aktionen. Diese Sprache ist extrem mächtig und flexibel, aber viele moderne Planungs-Programme (die "Köche") können mit Sprache A besser umgehen als mit Sprache B.

Das Dilemma: Bisher gab es keine praktische Möglichkeit, einen Plan aus Sprache A (Kochbuch) so umzuwandeln, dass er in Sprache B (Ökosystem) funktioniert, ohne dabei Details zu verlieren. Es war wie zu versuchen, ein Rezept in eine andere Sprache zu übersetzen, aber dabei die genauen Gramm-Mengen zu verlieren.

2. Die Lösung: Der "Übersetzer"

Die Autoren (Andrea, Enrico und Alessandro) haben einen cleveren Übersetzer entwickelt. Sie zeigen, wie man jeden "Kochvorgang" aus dem alten Kochbuch (Sprache A) in das lebendige Ökosystem (Sprache B) übersetzen kann, ohne dass etwas schiefgeht.

Stell dir vor, du willst einen Vorgang wie "Den Ofen 10 Minuten lang vorheizen" übersetzen.

• Im alten System: Du sagst einfach: "Mache 'Ofen an' für 10 Minuten."
• Im neuen System (die Übersetzung):
  1. Du startest einen Prozess: "Ein Timer läuft jetzt."
  2. Du stellst eine Wache auf: "Solange der Timer läuft, darf niemand den Ofen berühren oder etwas anderes tun, das den Timer stört."
  3. Du setzt einen Alarm (Ereignis): "Wenn der Timer bei 10 Minuten ist, schalte den Ofen aus."

3. Das Geheimnis: Die "Schloss-und-Schlüssel"-Methode

Das Schwierigste bei solchen Plänen ist, dass zwei Dinge nicht gleichzeitig an derselben Sache rumhantieren dürfen (z. B. darf niemand den Ofen ausschalten, während er gerade aufheizt).

Die Forscher nutzen eine geniale Schloss-Metapher:

• Jede wichtige Sache (eine Zutat, ein Timer) hat drei Schlösser:
  • Ein Schloss für das Lesen (jemand schaut nur nach).
  • Ein Schloss für das Ändern (jemand schneidet etwas).
  • Ein Schloss für das Hinzufügen (jemand gibt etwas hinzu).
• Bevor jemand etwas tun darf, muss er alle relevanten Schlösser öffnen.
• Sobald er etwas tut, verriegelt er die Schlösser sofort wieder.
• Erst wenn die Zeit weiterläuft (ein neuer "Takt" beginnt), werden alle Schlösser automatisch wieder geöffnet, damit der nächste Schritt beginnen kann.

Das verhindert, dass zwei "Köche" gleichzeitig an derselben Schüssel arbeiten und Chaos verursachen.

4. Warum ist das toll? (Die Experimente)

Die Forscher haben diesen Übersetzer getestet. Sie haben schwierige Probleme genommen, bei denen Zeit und Zahlen (wie Wasserstand, Batterieladung, Temperatur) eng miteinander verflochten sind.

Das Ergebnis war überraschend:

• Die alten, spezialisierten Planer (die nur Sprache A sprachen) waren oft langsam oder steckten fest.
• Die neuen Planer, die die übersetzten Pläne (in Sprache B) lasen, waren schneller und besser.

Es ist so, als hättest du einen alten, komplizierten Bauplan für ein Haus. Du übersetzt ihn in eine neue, modernere Bauanleitung. Und plötzlich können die neuen, super-schnellen Baumaschinen das Haus viel effizienter bauen als die alten Werkzeuge, die den Originalplan kannten.

Zusammenfassung

Die Forscher haben bewiesen, dass man Zeitpläne mit Dauer (wie "Koche 5 Minuten") perfekt in ein System aus Prozessen und Ereignissen übersetzen kann. Sie haben die Regeln dafür erfunden, damit nichts durcheinandergerät (die Schloss-Methode).

Der große Gewinn: Man kann jetzt die mächtigen Werkzeuge von PDDL+ nutzen, um Probleme zu lösen, die bisher nur schwer zu knacken waren. Es ist ein Brückenschlag zwischen zwei Welten, der zeigt, dass manchmal der Umweg über eine komplexere Sprache den schnellsten Weg zum Ziel ist.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papers „Compiling Temporal Numeric Planning into Discrete PDDL+: Extended Version" auf Deutsch:

1. Problemstellung

Das Paper adressiert die Herausforderung, temporale Planungsprobleme (speziell im PDDL 2.1 Level 3) in das ausdrucksstärkere Modellierungssprache PDDL+ zu übersetzen.

• Hintergrund: PDDL 2.1 modelliert zeitliche Aktionen als „durative actions" (Aktionen mit Dauer), die Bedingungen zu Beginn, am Ende und während der Ausführung haben. PDDL+ modelliert Systeme hingegen durch eine Kombination aus instantanen Aktionen, Ereignissen (Events) und Prozessen (differentialgleichungsbasierte kontinuierliche Änderungen).
• Lücke: Obwohl theoretisch bekannt war, dass PDDL 2.1 in PDDL+ kompiliert werden kann, fehlte bisher eine praktische, formale und vollständige Kompilierungsmethode, die die Semantik exakt abbildet und für numerische Probleme geeignet ist.
• Ziel: Eine polynomielle Kompilierung zu entwickeln, die die Semantik von temporalen Planen (inkl. numerischer Variablen, verzögerter Effekte und zeitlicher Initial-Literale) vollständig erfasst und dabei die Bedingung der Nicht-Selbst-Überlappung (non-self-overlapping) von Aktionen sicherstellt.

2. Methodik und Kompilierungsansatz

Die Autoren stellen einen formalen Algorithmus vor, der ein temporales Planungsproblem $\Pi$ in ein äquivalentes PDDL+-Problem $\bar{\Pi}$ transformiert. Der Kern der Methode liegt in der Emulation von dauerhaften Aktionen durch eine Triade aus Aktion, Prozess und Ereignis.

A. Erweiterter Zustandsraum

Zusätzlich zu den ursprünglichen Fluents (Prädikaten und numerischen Variablen) werden Hilfsvariablen eingeführt:

• ok: Ein boolesches Flag, das den Plan als gültig markiert. Wird auf false gesetzt, wenn Constraints verletzt werden (z. B. Verletzung von Invarianten).
• oc (open count): Zählt die Anzahl der gestarteten, aber noch nicht beendeten Aktionen.
• gc (global clock): Ein Zähler, der den Zeitfortschritt zwischen diskreten Schritten misst und zur Synchronisation von Sperren dient.
• ra: Ein Flag pro dauerhafter Aktion, das anzeigt, ob diese gerade läuft.
• ca: Eine numerische Variable pro dauerhafter Aktion, die die verstrichene Zeit seit dem Start misst.
• Lock-Prädikate (rlf, alf, ilf): Für jedes Fluent werden drei Sperren eingeführt (Read-Lock, Assignment-Lock, Increment-Lock), um Interferenzen zu verhindern.

B. Transformation der Aktionen

• Instantane Aktionen: Werden direkt in PDDL+-Aktionen übersetzt, ergänzt um die ok-Bedingung und die Lock-Prä-/Effekte.
• Dauerhafte Aktionen (Fixe Dauer): Werden in einen Start-Snap (Aktion), einen laufenden Prozess (der ca inkrementiert) und ein terminierendes Ereignis zerlegt. Das Ereignis wird ausgelöst, wenn ca die feste Dauer erreicht.
• Dauerhafte Aktionen (Variable Dauer): Werden ähnlich behandelt, aber die Terminierung erfolgt durch eine PDDL+-Aktion (a⊣), die explizit geprüft, ob die Dauer im zulässigen Intervall liegt.

C. Mechanismen zur Sicherung der Semantik

1. Verhinderung von Interferenzen (Locking):
   Um sicherzustellen, dass keine zwei Aktionen gleichzeitig auf dasselbe Fluent schreiben oder lesen/schreiben (die „No-Interference"-Bedingung), nutzt das System die Lock-Prädikate.

   • Beim Lesen eines Fluents wird rlf auf false gesetzt.
   • Beim Zuweisen wird alf auf false gesetzt.
   • Beim Inkrementieren wird ilf auf false gesetzt.
   • Diese Sperren werden nur durch das Ereignis eE zurückgesetzt, welches ausgelöst wird, sobald gc > 0 ist (d. h., Zeit ist vergangen). Da gc durch einen Prozess kontinuierlich erhöht wird, aber sofort nach dem Start eines Zeitintervalls auf 0 zurückgesetzt wird, erzwingt dies eine strikte Reihenfolge innerhalb eines Zeitpunkts (Superdense Time), die Interferenzen im selben Moment unmöglich macht.

2. Invarianten und Bedingungen:

   • Start/Ende: Werden durch Snap-Aktionen modelliert.
   • Laufzeitbedingungen (Overall Conditions): Ein Prozess überwacht die Invariante $\gamma_a$. Wenn sie verletzt wird, wird ok auf false gesetzt, was den Plan ungültig macht.
   • Maximale Dauer: Ein Ereignis setzt ok auf false, wenn eine variable Aktion ihre Obergrenze überschreitet, ohne beendet worden zu sein.

3. Diskretisierung:
   Die Kompilierung setzt eine diskrete Zeitquantisierung $\delta$ voraus. Dies ist notwendig, um das Zeno-Verhalten (unendlich viele Ereignisse in endlicher Zeit) zu vermeiden, das in kontinuierlicher Zeit auftreten würde, wenn das Reset-Ereignis eE sofort nach jedem Schritt triggern würde.

3. Wichtige Beiträge

• Erste vollständige formale Spezifikation: Das Paper liefert den ersten rigorosen formalen Beweis und die detaillierte Spezifikation für die Kompilierung von PDDL 2.1 (Level 3) in PDDL+.
• Vollständigkeit und Korrektheit: Es wird bewiesen, dass die Kompilierung sound (jeder gefundene PDDL+-Plan entspricht einem gültigen temporalen Plan) und vollständig (für jeden temporalen Plan existiert ein entsprechender PDDL+-Plan bei hinreichend kleinem $\delta$) ist.
• Polynomielle Komplexität: Die Größe des kompilierten Problems wächst nur polynomiell zur Eingabe, und die Planlänge wird höchstens um einen konstanten Faktor erhöht.
• Erweiterbarkeit: Die Methode unterstützt numerische Variablen, verzögerte Effekte und zeitliche Initial-Literale, was viele existierende temporale Planer nicht oder nur eingeschränkt können.

4. Experimentelle Ergebnisse

Die Autoren führten Experimente auf einer Reihe von temporalen numerischen Domänen durch (z. B. MatchCellar, MAJSP, T-Sailing, T-Plant-Watering).

• Vergleich: Der kompilierte Ansatz (gelöst mit dem PDDL+-Planer ENHSP, Varianten LG und WA*) wurde gegen state-of-the-art temporale Planer (ARIES, NextFLAP, TFLAP, OPTIC, TAMER, Patty) getestet.
• Ergebnisse:
  • ENHSP-WA erzielte die höchste Abdeckung (Anzahl gelöster Instanzen) über alle Domänen hinweg.
  • Bei rein temporalen Domänen waren native temporale Planer oft schneller.
  • Bei temporal-numerischen Problemen war der kompilierte Ansatz (ENHSP-WA) den spezialisierten temporalen Planern überlegen.
  • Die Ergebnisse deuten darauf hin, dass die Schwierigkeit bei temporal-numerischen Problemen oft in der Kombination von Zeit und Numerik liegt, für die PDDL+ mit seinen Prozessen und Ereignissen besser geeignet ist als reine temporale Suchalgorithmen.

5. Bedeutung und Ausblick

• Praktische Relevanz: Die Arbeit zeigt, dass die Übersetzung von temporalen Problemen in PDDL+ nicht nur theoretisch möglich, sondern praktisch vorteilhaft ist, insbesondere für komplexe numerische Szenarien. Sie ermöglicht es, fortgeschrittene PDDL+-Planer für Probleme zu nutzen, die ursprünglich als PDDL 2.1 formuliert wurden.
• Theoretischer Beitrag: Die Arbeit klärt die Semantik der „No-Moving-Target"-Regel und der Nicht-Überlappung in einem diskreten Rahmen präzise.
• Zukünftige Arbeiten: Die Autoren planen, die Kompilierung auf PDDL 2.1 Level 4 (kontinuierliche Änderungen) zu erweitern und alternative Kompilierungen für PDDL+ mit kontinuierlicher Zeitsemantik zu untersuchen.

Zusammenfassend stellt das Paper einen Meilenstein dar, der die Lücke zwischen der Modellierung temporaler Aktionen und der Ausdruckskraft von PDDL+ schließt und nachweist, dass diese Übersetzung ein leistungsfähiges Werkzeug für das Lösen schwerer Planungsprobleme ist.