Anytime Motion Planning

Auch genannt: anytime planning, anytime planner
Kategorie: Planning & manipulation › Motion planning
Schlagwörter: motion-planning, sampling-based-planning, optimal-planning, real-time, bounded-computation

Bewegungsplanung, die schnell einen gültigen Pfad liefert und ihn dann verbessert, solange die Zeit es zulässt, sodass eine brauchbare Antwort vorliegt, wann immer der Planer angehalten wird.

Definition

Ein Anytime-Bewegungsplaner (anytime motion planner) liefert so früh wie möglich eine erste zulässige, kollisionsfreie Lösung und nutzt die verbleibende Zeit, um sie zu verbessern, typischerweise durch Verringern der Pfadlänge, der Ausführungszeit oder anderer Kosten. Nach der ersten Lösung hält er zu jedem Zeitpunkt eine bisher beste Antwort bereit, die bei einer Unterbrechung zurückgegeben werden kann. Die Idee stammt aus dem allgemeineren Begriff der Anytime-Algorithmen in der künstlichen Intelligenz, den Dean und Boddy Ende der 1980er-Jahre einführten: Die Lösungsqualität wird gegen die Rechenzeit abgewogen, und der Zusammenhang zwischen beiden wird durch ein Leistungsprofil (performance profile) beschrieben.

Bei der Graphsuche erreicht man Anytime-Verhalten meist, indem man zuerst mit einer gewichteten, überhöhten Heuristik sucht und dann das Gewicht verringert, wobei früherer Suchaufwand wiederverwendet wird, wie bei Anytime Repairing A (ARA). In der samplingbasierten Planung sind asymptotisch optimale Planer wie RRT und die PRM-Variante der Probabilistic Roadmaps von Natur aus anytime: Sie sampeln nach der ersten Lösung weiter und verbinden den Baum neu, und die Kosten des besten Pfades streben mit wachsender Zahl an Samples gegen das Optimum. Informed RRT und Batch Informed Trees (BIT) beschleunigen die Verbesserungsphase, indem sie die Samples auf den Bereich beschränken, der noch einen besseren Pfad enthalten könnte. Ein einfacher Rapidly-exploring Random Tree** ist in diesem Sinne nicht anytime, da er anhält, sobald das Ziel verbunden ist, obwohl man Neustarts oder Nachbearbeitung um ihn herum legen kann.

Die Verbesserung über die Zeit verläuft selten gleichmäßig. Die Kosten fallen oft in Stufen, besonders wenn der Planer eine Route durch eine andere Lücke zwischen Hindernissen findet, also einen Pfad in einer neuen Homotopieklasse, und lange Abschnitte können fast keinen Gewinn bringen. Damit wird die Entscheidung, wann man aufhört, zu einem eigenen Problem: Zu frühes Aufhören verschenkt Qualität, zu spätes Aufhören verschenkt Zeit, in der sich der Roboter bewegen könnte. Feste Zeitbudgets sind die übliche Praxis, während Methoden des Meta-Reasoning lernen oder schätzen, wann weitere Rechenzeit sich nicht mehr lohnt.

Warum es wichtig ist

Roboter haben selten eine feste, bekannte Zeit zum Planen. Ein Anytime-Planer liefert fast sofort eine sichere Rückfalllösung und verwandelt jede übrige Zeit in bessere Bewegungen. Das passt zu Systemen, die zu einer Frist handeln müssen, denen Pfadqualität, Energie oder Taktzeit aber trotzdem wichtig sind.

Wichtige Anwendungen

Bewegungsplanung für Roboterarme mit Zeitbudget pro Anfrage in Manipulationspipelines
Neuplanung für mobile Roboter und Fahrzeuge, die in einem festen Regelzyklus handeln müssen
Pfadplanung für Flugroboter, bei denen kürzere Pfade Akku sparen
Heuristische Graphsuche auf Rastern und Gittern mit Gewichtsreduktion im Stil von ARA*
Forschung zum Meta-Reasoning über die Entscheidung, wann das Planen endet und das Handeln beginnt

In der Praxis

Ein mobiler Manipulator plant Armbewegungen mit einem asymptotisch optimalen samplingbasierten Planer aus einer Bibliothek wie OMPL. Jede Anfrage erhält ein Zeitbudget: Der Planer findet meist früh innerhalb dieses Budgets einen ersten Pfad und verkürzt ihn dann weiter. Das Team protokolliert die besten Kosten über der verstrichenen Zeit für viele aufgezeichnete Anfragen und sieht, dass der größte Teil des Gewinns früh eintritt, mit gelegentlichen großen Sprüngen nach unten, wenn spät eine kürzere Route um ein Hindernis gefunden wird. Statt immer das volle Budget zu nutzen, hört es auf, wenn sich die Kosten über ein festgelegtes Intervall nicht verbessert haben, oder nutzt eine gelernte Abbruchregel, und wendet dann Shortcutting und Zeitparametrisierung auf das Ergebnis an, bevor es an den Regler geht.

Häufige Missverständnisse

Anytime bedeutet, dass die erste Lösung nahezu optimal ist — die erste Lösung ist oft weit vom Optimum entfernt, und die Qualität hängt davon ab, wie lange der Planer läuft
Die Kosten verbessern sich gleichmäßig mit der Zeit — sie fallen typischerweise in ungleichmäßigen Stufen, mit langen Plateaus dazwischen
Asymptotische Optimalität garantiert einen guten Pfad innerhalb des Zeitbudgets — sie beschreibt nur den Grenzwert bei unbegrenzt wachsender Rechenzeit und sagt nichts über eine endliche Frist aus
Das ganze Zeitbudget zu nutzen ist immer am besten — Zeit zum Planen ist Zeit, in der sich der Roboter nicht bewegt, daher ist frühes Aufhören oft der bessere Kompromiss

Wer das wissen sollte

Ingenieure für Bewegungsplanung, die samplingbasierte oder suchbasierte Planer konfigurieren
Entwickler für mobile Manipulation und Navigation, die unter Echtzeitgrenzen arbeiten
Robotikforscher, die Planung mit begrenzter Rechenzeit untersuchen
Studierende, die optimale Bewegungsplanung lernen

Open Source Robotics