Interleaving Scheduling and Motion Planning with Incremental Learning of Symbolic Space-Time Motion Abstractions

Diese Arbeit stellt einen neuartigen Rahmen vor, der durch ein inkrementelles Lernverfahren Scheduler und Bewegungsplaner miteinander verzahnt, um in geteilten Arbeitsräumen zeitlich und räumlich konfliktfreie Ausführungspläne für die Multi-Objekt-Navigation zu generieren.

Das Wesentliche

Stell dir vor, du bist der Chef in einer riesigen, geschäftigen Lagerhalle. Deine Aufgabe: Du hast eine Liste von Aufträgen (z. B. „Hol Paket A von Regal 1", „Bringe Paket B zur Tür"). Das ist das Scheduling (die Planung).

Aber hier ist das Problem: Du hast nicht nur eine Liste, sondern auch echte, sich bewegende Roboter. Diese Roboter sind nicht wie Geister, die durch Wände gehen können. Sie haben eine Größe, sie brauchen Zeit zum Beschleunigen, und sie können sich nicht gleichzeitig durch dieselbe enge Gasse quetschen. Das ist das Motion Planning (die Bewegungsplanung).

Bisher haben Computer diese beiden Dinge oft getrennt betrachtet. Der Planer sagte: „Roboter 1 macht das um 10:00 Uhr, Roboter 2 macht das um 10:01 Uhr." Der Bewegungsplaner sagte dann: „Moment mal! Wenn Roboter 1 um 10:00 Uhr losfährt, blockiert er die Tür, und Roboter 2 kommt nicht durch!"

Die Autoren dieses Papers haben eine Lösung gefunden, die diese beiden Welten zusammenbringt. Hier ist die Erklärung, wie sie das machen, mit ein paar einfachen Bildern:

1. Das Problem: Der „Blinde" Planer und der „Zögernde" Roboter

Stell dir vor, du hast einen sehr klugen, aber blinden Architekten (den Scheduler). Er zeichnet einen perfekten Zeitplan auf Papier. Er weiß, was getan werden muss, aber er sieht nicht, wie es im echten Raum aussieht. Er plant, dass zwei Roboter gleichzeitig durch eine enge Tür laufen sollen.

Dann hast du einen sehr vorsichtigen, aber langsamen Testfahrer (den Motion Planner). Er nimmt den Plan des Architekten und sagt: „Das geht nicht! Wenn sie gleichzeitig durch die Tür wollen, stoßen sie zusammen."

Früher mussten sie sich streiten: Der Architekt änderte den Plan, der Testfahrer prüfte ihn wieder, der Architekt änderte ihn wieder... das dauerte ewig.

2. Die Lösung: Ein lernendes Team (Interleaving)

Die Autoren haben ein neues System erfunden, bei dem der Architekt und der Testfahrer zusammenarbeiten, während sie den Plan erstellen. Es funktioniert wie ein Tanz mit einem Spiegel:

1. Der Architekt macht einen Vorschlag: Er sagt: „Roboter 1 geht jetzt los, Roboter 2 wartet kurz."
2. Der Testfahrer prüft sofort: Er schaut sich an, ob das im echten Raum funktioniert.
   • Szenario A (Alles gut): „Super! Hier ist der genaue Weg, den sie fahren müssen." -> Der Plan ist fertig.
   • Szenario B (Es klemmt): „Nein, das geht nicht. Roboter 1 ist zu breit für diesen Weg, oder Roboter 2 steht ihm im Weg."
3. Der Rückkopplungs-Effekt (Symbolisches Lernen): Das ist der geniale Teil. Der Testfahrer gibt dem Architekten nicht nur ein „Nein" zurück. Er gibt ihm eine symbolische Anweisung, wie er den Plan ändern muss.
   • Beispiel: „Hey Architekt, wenn du willst, dass Roboter 1 durchkommt, muss Roboter 2 erst die Tür öffnen (oder warten), bevor Roboter 1 losfährt."
   • Der Architekt lernt daraus: „Aha! Ich darf diese beiden Aktionen nicht mehr gleichzeitig planen." Er merkt sich diese Regel für die Zukunft.

3. Die zwei Arten von „Lernhinweisen"

Der Testfahrer schickt zwei Arten von Nachrichten zurück, damit der Planer den Tanz besser tanzen kann:

• Geometrische Hinweise (Der Raum): „Hey, dieser Weg ist blockiert! Du musst einen anderen Roboter bewegen, damit der Weg frei wird." (Wie wenn du sagst: „Rück den Stuhl weg, bevor du durch die Tür gehst.")
• Zeitliche Hinweise (Der Takt): „Der Weg ist frei, aber du hast zu wenig Zeit eingeplant! Roboter 1 braucht 5 Sekunden länger, um durch die Kurve zu kommen, sonst kracht er." (Wie wenn du sagst: „Warte 2 Sekunden, bevor du startest, damit der andere vorbei ist.")

4. Warum ist das so clever? (Die Schichten)

Stell dir vor, du willst eine große Party organisieren.

• Schicht 1 (Einfach prüfen): Zuerst schaut man nur auf einzelne Gäste: „Kann dieser eine Gast durch die Tür?" Wenn nein, sofort korrigieren. Das ist schnell.
• Schicht 2 (Komplex prüfen): Erst wenn alle Einzel-Gäste passen, schaut man, wie sie sich alle zusammen bewegen. „Können diese drei Gäste gleichzeitig tanzen, ohne sich zu berühren?"

Das System der Autoren macht genau das: Es prüft erst die einfachen Dinge (einzelne Roboter), bevor es sich mit dem schwierigen Tanz (alle Roboter gleichzeitig) beschäftigt. Das spart enorm viel Zeit und Rechenleistung.

Zusammenfassung in einem Satz

Dieses Papier beschreibt ein System, bei dem ein Zeitplaner und ein Roboter-Steuerer nicht mehr gegeneinander arbeiten, sondern wie ein Lernpaar: Der eine schlägt vor, der andere korrigiert mit konkreten Regeln („Warte länger!" oder „Mach Platz!"), bis der Plan sowohl auf dem Papier als auch in der realen Welt perfekt funktioniert.

Das Ergebnis: Roboter in Lagern können jetzt viel effizienter und sicherer arbeiten, ohne ständig aneinander zu stoßen oder unnötig zu warten, weil der Computer lernt, die richtigen Regeln für den Raum und die Zeit zu finden.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papers „Interleaving Scheduling and Motion Planning with Incremental Learning of Symbolic Space-Time Motion Abstractions" auf Deutsch.

1. Problemstellung: Scheduling and Motion Planning (SAMP)

Das Paper adressiert das Problem der Scheduling- und Bewegungsplanung (SAMP) für mehrere Objekte (z. B. mobile Roboter) in einem gemeinsamen Arbeitsraum. Im Gegensatz zum klassischen Task-and-Motion-Planning (TAMP), bei dem oft erst entschieden wird, welche Aufgaben ausgeführt werden sollen, geht es bei SAMP von einer vordefinierten Menge von Aufgaben aus. Die Herausforderung liegt darin, zu bestimmen, ob, wann und wie diese Aufgaben sicher und effizient unter Berücksichtigung von Ressourcen-, Zeit- und Bewegungsbeschränkungen ausgeführt werden.

Das Problem vereint zwei Ebenen:

1. Scheduling (Hohe Ebene): Bestimmung der Reihenfolge und des Zeitpunkts für jede Aktivität (z. B. Transport, Greifen, Ablegen) unter Einhaltung von Präzedenz- und Ressourcenbedingungen.
2. Motion Planning (Niedrige Ebene): Berechnung dynamisch und kinematisch machbarer, kollisionsfreier Trajektorien im kontinuierlichen physikalischen Raum.

Ein zentrales Merkmal ist die Notwendigkeit einer synchronisierten Bewegung: Roboter müssen in engen Räumen (z. B. Lagerhallen) warten, ihre Reihenfolge ändern oder Bewegungen synchronisieren, um Konflikte und Deadlocks zu vermeiden. Dies erfordert eine direkte Reasoning-Fähigkeit in kontinuierlichen Konfigurationsräumen unter expliziten kinodynamischen Constraints.

2. Methodik: Ein Framework mit inkrementellem Lernen

Die Autoren schlagen ein Framework vor, das kommerzielle Scheduler (off-the-shelf) und Bewegungsplaner in einer Schleife des inkrementellen Lernens symbolischer Bewegungsabstraktionen miteinander verknüpft (interleaved).

Kernkomponenten des Frameworks:

• Iterativer Prozess:

  1. Der Scheduler generiert einen Kandidatenplan (Zeitplan), der die Bewegungsgeometrie noch nicht berücksichtigt.
  2. Der Bewegungsplaner (als Black-Box behandelt) prüft die Machbarkeit dieses Plans unter Berücksichtigung der Kinematik und Dynamik der Objekte.
  3. Feedback-Schleife: Wenn der Plan nicht machbar ist, liefert der Bewegungsplaner symbolisches Feedback zurück an den Scheduler. Dieser Plan wird dann mit neuen Constraints versehen und erneut geplant.

• Symbolische Abstraktionen (Refinements):
  Das System lernt Abstraktionen, um den Suchraum des Schedulers einzuschränken:

  • Geometrische Verfeinerungen (Geometric Refinements): Identifizierung von nicht erreichbaren Zielen oder blockierenden Hindernissen. Der Scheduler erhält Constraints, die erzwingen, dass blockierende Objekte vor der Ausführung einer Bewegung umpositioniert werden müssen.
  • Zeitliche Verfeinerungen (Temporal Refinements): Anpassung von Aktivitätsdauern oder Startverzögerungen, um eine kollisionsfreie Synchronisation paralleler Bewegungen zu ermöglichen.

• Architektur (Layering):
  Um die Rechenkosten zu senken, wird der Plan in parallele Bewegungsgruppen (Sets von Aktivitäten, die sich gegenseitig beeinflussen können) zerlegt. Das Framework nutzt eine zweischichtige Architektur:

  • Layer 1: Geprüft jede einzelne Aktivität auf geometrische Machbarkeit (einfacher Pfadfinder).
  • Layer 2: Geprüft die Synchronisation ganzer Gruppen (komplexer ST-RRT*).
    Dies vermeidet teure Gruppenprüfungen, wenn bereits einzelne Aktivitäten unmöglich sind.

• Formale Definition:
  Das Problem wird als Tupel $\psi = \langle \phi, O, W, Q, u, i, mc \rangle$ definiert, wobei $\phi$ ein optionales Scheduling-Problem (OS) ist, das um bewegliche Objekte ($O$), den Arbeitsraum ($W$), Konfigurationsräume ($Q$) und Bewegungsconstraints ($mc$) erweitert wird.

3. Wichtige Beiträge

1. Formale Definition von SAMP: Das Paper definiert erstmals das SAMP-Problem für mehrere Objekte in einem geteilten Raum, das Scheduling und kontinuierliche Bewegungsplanung explizit integriert.
2. Domain-unabhängiges Framework: Das System ist nicht an eine spezifische Domäne gebunden. Es erlaubt die Kombination verschiedener Scheduler (z. B. Aries, OR-Tools) und Bewegungsplaner (z. B. RRT, ST-RRT*).
3. Inkrementelles Lernen von Constraints: Anstatt alle Constraints im Voraus zu berechnen (was oft unmöglich ist), werden Constraints dynamisch basierend auf den Fehlern des Bewegungsplaners gelernt. Dies verbessert die Skalierbarkeit in komplexen, dynamischen Umgebungen.
4. Flexibilität bei Fluents: Das Framework unterstützt sowohl Scheduling-Modelle mit Fluents (Zustandsvariablen) als auch reine Präzedenz-Modelle, was die Kompatibilität mit verschiedenen Solvern erhöht.

4. Experimentelle Ergebnisse

Die Autoren evaluierten das Framework an zwei Benchmark-Szenarien, die um Navigationsaufgaben erweitert wurden:

• Logistik: Roboter transportieren Güter von Regalen zu einer Ausgabestation in engen Gängen (mit/ohne blockierende Türen).
• Job-Shop Scheduling (JSP): Roboter bewegen Teile zwischen Maschinen, wobei Türen geöffnet werden müssen.

Ergebnisse:

• Erfolgsrate: Das Framework löste erfolgreich Instanzen mit bis zu 3 Robotern in komplexen Umgebungen. Alle getesteten Solver-Kombinationen konnten mindestens eine Instanz mit 3 Robotern lösen.
• Parallelisierung: Im Vergleich zu rein sequenziellen Plänen (keine Parallelisierung) erreichte das Framework eine durchschnittliche Verbesserung der Makespan (Gesamtzeit) um 41%.
• Effizienz: Durch die Layering-Architektur (Layer 1 vor Layer 2) wurden die Rechenzeit und die Anzahl der teuren ST-RRT*-Aufrufe drastisch reduziert. Ohne Layer 1 sank die Lösungsrate von 359 auf 140 Instanzen.
• Rolle der Fluents: Die Verwendung von Fluents (z. B. im Solver Aries) führte zu besseren Ergebnissen (87,7 gelöste Instanzen vs. weniger ohne Fluents), da sie den Scheduler besser bei der Verfeinerung leiten.
• Kosten: Die Bewegungsplanung nahm bis zu 92% der Gesamtplanungszeit ein, was die Notwendigkeit effizienter Verfeinerungsstrategien unterstreicht.

5. Bedeutung und Ausblick

Dieses Paper ist signifikant, da es die Lücke zwischen diskretem Scheduling und kontinuierlicher Bewegungsplanung schließt, insbesondere in Szenarien, in denen Aufgaben feststehen, aber deren zeitliche und räumliche Koordination kritisch ist.

• Praktische Relevanz: Das Framework ist direkt anwendbar in automatisierten Lagern und Fertigungsstraßen, wo Roboter in engen Räumen zusammenarbeiten müssen.
• Robustheit: Die Fähigkeit, mit optionalen Aufgaben und dynamischen Hindernissen (wie geschlossenen Türen) umzugehen, macht es für reale Anwendungen geeignet.
• Zukünftige Arbeit: Die Autoren planen, das Framework um Multi-Agent Path Finding (MAPF) zu erweitern, um eine noch effizientere Koordination in diskretisierten Räumen zu ermöglichen, während die kinodynamischen Constraints erhalten bleiben.

Zusammenfassend stellt das Paper einen robusten Ansatz dar, der durch die iterative Verfeinerung symbolischer Constraints komplexe SAMP-Probleme löst, die mit rein sequenziellen oder monolithischen Methoden nicht handhabbar wären.