Roboter werden immer fähiger, sich in der Welt zu bewegen, aber ihnen eine Liste von Anweisungen vorzugeben, was sie tun sollen, ist für die chaotische Realität eines Krankenhauses, eines Lagers oder eines fernen Planeten oft zu starr. Eine einfache Liste könnte sagen: „Gehe hierhin, dann gehe dorthin“, aber sie hat Schwierigkeiten mit den „Was-wäre-wenn“-Fragen, die das echte Leben definieren: Was, wenn der Roboter eine Verschüttung sieht und sie reinigen muss? Was, wenn zwei Aufgaben innerhalb eines bestimmten Zeitfensters stattfinden müssen, aber nicht unbedingt in einer festen Reihenfolge? Jahrelang haben Forscher eine Methode namens „timed partial orders“ (zeitgesteuerte partielle Ordnungen) verwendet, um dies zu lösen. Stellen Sie sich das wie ein Flussdiagramm vor, bei dem Pfeile zeigen, welche Aufgaben vor anderen stattfinden müssen, und Uhren sicherstellen, dass sie innerhalb bestimmter Zeitlimits erfolgen. Dieser Ansatz ist für Menschen klar verständlich und für Computer leicht zu verarbeiten, hat aber einen blinden Fleck. Er kann komplexe Zeitregeln zwischen nicht verwandten Aufgaben nicht ohne Weiteres handhaben, noch kann er leicht sagen: „Führe diesen nächsten Schritt nur aus, wenn eine bestimmte Bedingung in der Umgebung erfüllt ist.“

Ein Team von Forschern der University of Colorado Boulder hat einen neuen Weg entwickelt, um diese Lücke zu schließen, indem sie ein System namens „Conditional Timed Partial Orders“ (Bedingte zeitgesteuerte partielle Ordnungen) geschaffen haben. Dieses Framework ermöglicht es Ingenieuren, Roboter-Missionen zu schreiben, die weitaus flexibler und realistischer sind. Das neue System kann Regeln erzwingen wie: „Diese zwei Aufgaben müssen innerhalb von zwanzig Minuten nacheinander stattfinden, unabhängig davon, welches zuerst kommt“, oder: „Wenn der Roboter in die Nähe eines bestimmten Bereichs fährt, muss er sofort eine neue Reihe von Aufgaben ausführen.“ Die Forscher haben bewiesen, dass sie diese komplexen, bedingten Missionen in ein mathematisches Problem übersetzen können, das ein Computer lösen kann, um den schnellstmöglichen Pfad zu finden. Sie entdeckten jedoch auch, dass die Rechenzeit des Computers explodiert, wenn diese Missionen komplexer werden, und somit zu langsam wird, um nützlich zu sein. Um dies zu beheben, erfanden sie eine Methode, um die massive, komplizierte Mission in kleinere, unabhängige Stücke aufzuteilen. Sie lösten jedes kleine Stück separat und fügten die Antworten dann zusammen. Ihre Tests zeigten, dass dieser Ansatz den Planungsprozess um bis zu zehntausendmal beschleunigen kann, ohne die Qualität des Plans zu beeinträchtigen.

Der Kern dieser Arbeit liegt darin, wie die Forscher die Sprache erweitert haben, die verwendet wird, um mit Robotern zu kommunizieren. In ihrer bisherigen Arbeit war die Mission eines Roboters eine statische Karte von Ereignissen. Wenn eine Aufgabe auf der Karte war, musste der Roboter sie ausführen. Wenn eine Zeitregel existierte, galt sie für die gesamte Mission. Das neue System führt eine Logikschicht ein, die auf die Welt reagiert. Stellen Sie sich einen Krankenhausroboter vor, der damit beauftragt ist, Blutproben zu sammeln und Ergebnisse zu liefern. Im alten System würde der Roboter einem festen Zeitplan folgen. Im neuen System kann dem Roboter gesagt werden: „Wenn du zufällig an der Kardiologie-Abteilung vorbeiläufst, musst du auch einen Elektrokardiogramm-Bericht aufnehmen und innerhalb von fünfzehn Minuten liefern.“ Der Roboter muss nicht im Voraus wissen, wo sich die Kardiologie-Abteilung befindet; er folgt einfach dem Pfad, und wenn die Bedingung erfüllt ist, werden die zusätzlichen Aufgaben und deren strikte Zeitregeln automatisch aktiviert. Dies macht die Anweisungen an den Roboter viel näher an der Art und Weise, wie ein menschlicher Vorgesetzter Befehle geben würde, indem sie sich an das anpassen, was tatsächlich vor Ort geschieht.

Um dies zu ermöglichen, mussten die Forscher ein schwieriges mathematisches Rätsel lösen. Sie zeigten, dass das Finden des besten Pfades für einen Roboter mit diesen bedingten Regeln dasselbe ist wie das Lösen eines komplexen Routing-Problems, ähnlich wie das Finden des effizientesten Weges, um eine Reihe von Orten innerhalb spezifischer Zeitfenster zu besuchen. Sie übersetzten dies in ein Format, das Computer mithilfe einer Technik namens „Mixed-Integer Linear Programming“ lösen können. Diese Methode garantiert, dass der Roboter einen Pfad findet, der alle Regeln erfüllt, aber sie hat einen Nachteil. Wenn die Anzahl der Aufgaben und Bedingungen wächst, wird die Größe des mathematischen Problems so groß, dass selbst leistungsstarke Computer stecken bleiben können und Stunden oder Tage brauchen, um eine Antwort zu finden. Dies ist ein häufiger Flaschenhals in der Robotik: Je flexibler die Anweisungen sind, desto schwieriger ist es für den Computer, den Plan zu berechnen.

Die Lösung der Forscher bestand darin, nicht mehr zu versuchen, das gesamte Problem auf einmal zu lösen. Sie erkannten, dass viele Missionen aus kleineren, in sich geschlossenen Gruppen von Aufgaben bestehen, die eng miteinander verknüpft sind, aber nur lose mit dem Rest der Mission verbunden sind. Zum Beispiel könnte eine Sequenz von Reinigungsaufgaben, die durch eine Verschüttung ausgelöst werden, eine in sich geschlossene Einheit sein, die beginnt, wenn der Roboter die Verschüttungszone betritt, und endet, wenn er sie verlässt. Die Forscher entwickelten einen Algorithmus, um diese Gruppen oder „Sub-Aufgaben“ innerhalb der größeren Mission automatisch zu finden. Sie lösten dann die Zeitplanung und den Pfad für jede kleine Gruppe unabhängig voneinander. Sobald sie den besten Pfad für jede kleine Gruppe hatten, behandelten sie jede Gruppe als einen einzelnen Schritt in der größeren Mission und fügten die Zeit ein, die für den Abschluss dieser Gruppe benötigt wurde. Dies verwandelte ein massives, unlösbares Puzzle in eine Serie kleiner, leicht lösbarer Puzzles.

Die Ergebnisse dieses Ansatzes waren beeindruckend. In ihren Tests verglichen die Forscher ihre neue Methode mit der alten Art, die gesamte Mission auf einmal zu lösen. Bei einfachen Missionen waren beide Methoden schnell. Aber als die Missionen komplexer wurden, mit mehr Bedingungen und engeren Zeitregeln, verlangsamte sich die alte Methode dramatisch und dauerte manchmal Minuten oder sogar Stunden. Die neue Dekompositionsmethode hingegen blieb schnell und löste dieselben Probleme oft in weniger als einer Sekunde. In den schwierigsten Fällen war die neue Methode bis zu zehntausendmal schneller. Entscheidend war, dass die Forscher mathematisch bewiesen, dass diese Geschwindigkeit nicht zu Lasten der Qualität ging. Die Pläne, die durch das Aufteilen der Mission in Teile generiert wurden, waren genauso gut wie die Plätze, die durch das Lösen des Ganzen auf einmal generiert wurden. Sie fanden dieselben optimalen Pfade und erfüllten dieselben Zeitbeschränkungen.

Die Forscher demonstrierten dies anhand zweier realer Szenarien. In einem Fall musste ein Roboter in einem Lagerhaus drei Regale besuchen und zu einem Dock zurückkehren. Wenn der Roboter einen Pfad einschlug, der eine Ölverschüttung kreuzte, war er verpflichtet, drei spezifische Bereiche zu reinigen, bevor er fortfährt. Das System plante erfolgreich eine Route, die die Verschüttung nach Möglichkeit umging, aber falls der kürzeste Weg erforderte, sie zu kreuzen, fügte der Roboter die Reinigungssequenz automatisch in seinen Plan ein und stellte sicher, dass er die Reinigung innerhalb der erforderlichen Zeitlimits abschloss. In einem zweiten Szenario musste ein Mars-Rover Bodenproben analysieren. Wenn der Rover an einer bestimmten Felsformation vorbeikam, musste er zu einem neuen Standort navigieren und innerhalb eines strengen Zeitfensters eine Probe entnehmen. Das System plante eine Route, die die Felsformation nach Möglichkeit umging, aber wenn das Gelände den Rover dazu zwang, an ihr vorbeizuziehen, passte sich der Plan nahtlos an, um die zusätzliche Probenahme einzuschließen.

Diese Arbeit stellt einen bedeutenden Schritt nach vorn dar, um Roboter autonomer und anpassungsfähiger zu machen. Indem sie es den Forschern ermöglichten, Missionsspezifikationen sowohl bedingt als auch zeitlich komplex zu gestalten, haben sie Ingenieuren ein Werkzeug gegeben, um Anweisungen zu schreiben, die sich natürlicher und weniger starr anfühlen. Die Fähigkeit, diese komplexen Anweisungen in handhabbare Teile zu zerlegen, bedeutet, dass Roboter nun Missionen bewältigen können, die zuvor zu rechenintensiv für die Planung waren. Die Forscher merkten an, dass sich ihre aktuelle Arbeit auf einzelne Roboter konzentriert, der nächste Schritt jedoch darin besteht, dieses Framework auf Gruppen von Robotern auszuweiten, die zusammenarbeiten. Vorerst stellt die Methode einen robusten Weg dar, um sicherzustellen, dass ein Roboter, wenn man ihm sagt, etwas Komplexes in einer sich verändernden Welt zu tun, schnell und korrekt herausfindet, wie er es genau machen kann.