Learning When to Quit: Meta-Reasoning for Motion Planning

Autoren: Yoonchang Sung, Leslie Pack Kaelbling, Tomás Lozano-Pérez · IROS 2021

Lizenzen

Open Access
Paper: CC BY 4.0

Alles Folgende stützt sich auf das vollständige Paper unter seiner Lizenz CC BY 4.0; die Abbildung wird mit Nennung der Autoren gezeigt.

Kurz gesagt

Lernt aus früheren Planerläufen, wann ein Anytime-Bewegungsplaner (RRT, PRM, Lazy PRM*) gestoppt werden soll, sodass der Kompromiss zwischen Pfadqualität und Planungszeit maximiert wird.

Warum es wichtig ist

Jeder Roboter, der mit RRT oder PRM plant, muss ein Planungszeitbudget wählen, und eine feste Zeit oder eine feste Qualitätsschwelle verschwendet entweder Zeit oder Pfadqualität. Die Methode umschließt einen unveränderten Anytime-Planer und lässt sich daher auf bestehende Planer im Stil von OMPL aufsetzen, solange Trainingsprobleme aus der Zielverteilung der Umgebungen verfügbar sind.

Problem

Anytime-Bewegungsplaner verkürzen einen Pfad immer weiter, je länger sie laufen, doch es gibt keinen gut charakterisierten Zusammenhang zwischen Lösungsqualität und Rechenzeit, sodass unklar ist, wann man mit dem Planen aufhören und losfahren soll. Ihre Leistungsprofile sind stark unstetig, weil kürzere Pfade in plötzlichen Sprüngen auftreten, wenn der Planer eine neue Homotopieklasse findet, was eine einfache Online-Extrapolation der künftigen Qualität ausschließt.

Lösungsansatz

Die Autoren lernen eine Abbruch-Policy aus Leistungsprofilen früherer Planungsprobleme aus derselben Verteilung und maximieren dabei einen vom Nutzer gewichteten Nutzen U(q, t) = wq − (1 − w)t. Eine modellbasierte Variante lernt einen Markow-Entscheidungsprozess über diskretisierter Qualität und Zeit und löst ihn mit Wertiteration; zwei modellfreie Varianten (ein Feedforward-Klassifikator auf handentworfenen Merkmalen und ein RNN-Sequence-to-Sequence-Modell) imitieren nachträglich berechnete Orakel-Abbruchentscheidungen. Ein CNN sagt die optimale Pfadlänge aus einem 2D-Arbeitsraumbild vorher, damit Profile von Problemen unterschiedlicher Schwierigkeit normalisiert und verglichen werden können.

Wichtigste Erkenntnisse

Optimale Abbruchzeitpunkte lassen sich für jeden Trainingslauf nachträglich berechnen, wodurch das Problem des Policy-Lernens zu überwachtem Imitation Learning statt zu bestärkendem Lernen wird.
Zur Normalisierung der Pfadqualität braucht man die unbekannte optimale Pfadlänge; ein CNN, das sie aus einem 2D-Arbeitsraumbild vorhersagt, macht Profile über Probleme hinweg vergleichbar, und ein schlechter Normalisierer (eine gerade Linie vom Start zum Ziel) senkt den Nutzen deutlich.
Reichhaltigere Verlaufsmerkmale (Steigung, Flachheit) machen das modellbasierte Übergangsmodell weit genauer, doch sein Schätzaufwand wächst von Sekunden auf mehr als einen Tag, ein direkter Fall des Fluchs der Dimensionalität.
Das RNN lernt seine eigenen zeitlichen Merkmale aus der rohen Nutzenfolge und lieferte über Planer und Nutzengewichte hinweg am verlässlichsten gute Ergebnisse.

Hauptergebnisse

Genauigkeit des CNN-Prädiktors für die optimale Pfadlänge auf 200 zurückgehaltenen Arbeitsräumen: 88,21 %, 96,23 % und 94,25 % in drei Umgebungsverteilungen.
Mit dem CNN-Normalisierer ergaben sich in diesen drei Umgebungen Nutzenwerte von 0,58, 0,65 und 0,66, gegenüber 0,63, 0,70 und 0,67 mit den tatsächlichen optimalen Längen und 0,39, 0,40 und 0,60 mit einem Geradenlinien-Normalisierer.
Der Verlust des Übergangsmodells auf zurückgehaltenen Daten sank von 1,84 (ohne Merkmale) auf 0,22 mit (t, q) und 0,10 mit (t, q, Steigung), während die Schätzzeit von 0,41 s auf 10,64 s und 11.933,72 s stieg.
RRT* bei w = 0,8: Orakel-Nutzen 0,677, RNN 0,670, modellbasiert 0,663, Klassifikator 0,658, gegenüber 0,634 für die Baseline mit fester Qualität und 0,575 für die Baseline mit fester Zeit.
PRM* bei w = 0,8: Orakel 0,718, modellbasiert 0,702, RNN 0,698, Klassifikator 0,697, feste Qualität 0,674, feste Zeit 0,662.
Bei w = 0,2 wurde die Baseline mit fester Qualität negativ (−0,283 für RRT, −0,344 für PRM, −0,367 für Lazy PRM*), während die gelernten Methoden positiv blieben.

Einschränkungen

Der CNN-Prädiktor für die optimale Lösung nimmt ein 2D-Arbeitsraumbild entgegen, was die Methoden auf Probleme mit ebenen Arbeitsräumen beschränkt; eine Erweiterung auf 3D über Voxelgitter oder Punktwolken wird vorgeschlagen, aber nicht umgesetzt.
Es wird angenommen, dass ein neues Problem aus derselben Verteilung stammt wie die Trainingsprobleme, und das Training erfordert viele lange Planerläufe auf repräsentativen Problemen.
Das Hinzufügen von Verlaufsmerkmalen zur modellbasierten Methode war für die größeren Experimente rechnerisch nicht machbar, daher wurde nur (q, q_prev, t) verwendet.
Die gesamte Evaluation erfolgt in der Simulation mit einem starren Roboter mit drei Freiheitsgraden in 2D-Arbeitsräumen; kein physischer Roboter wurde getestet.
Untersucht wurde nur ein linearer Nutzen U(q, t) = wq − (1 − w)t.

Wirkung auf das Fachgebiet

Die Arbeit war Finalistin für den IROS 2021 Best Paper Award on Cognitive Robotics und hat 14 Zitierungen. Eine Veröffentlichung von Code oder Daten wird nicht angegeben.

Zusammenfassung

Anytime-Bewegungsplaner sind in der Robotik weit verbreitet. Der Zusammenhang zwischen ihrer Lösungsqualität und der Rechenzeit ist jedoch nicht gut verstanden, und daher ist unklar, wann man mit dem Planen aufhören und mit der Ausführung beginnen soll. In dieser Arbeit behandeln wir das Problem, unter begrenzter Rechenkapazität zu entscheiden, wann das Abwägen beendet werden soll, sogenanntes Meta-Reasoning, für die Anytime-Bewegungsplanung. Wir schlagen datengetriebene Lernverfahren vor, modellbasiertes und modellfreies Meta-Reasoning, die auf verschiedene Umgebungsverteilungen anwendbar und von der Wahl des Anytime-Bewegungsplaners unabhängig sind. Als Teil des Frameworks entwerfen wir einen auf einem Convolutional Neural Network basierenden Prädiktor für die optimale Lösung, der die optimale Pfadlänge aus einem gegebenen 2D-Arbeitsraumbild vorhersagt. Wir evaluieren die Leistung der vorgeschlagenen Methoden empirisch in der Simulation im Vergleich mit Baselines.

Open Source Robotics