Belief-Space Planning

Auch genannt: planning in belief space
Kategorie: Planning & manipulation › Motion planning
Schlagwörter: planning-under-uncertainty, pomdp, state-estimation, active-sensing, probabilistic-robotics

Planung über Wahrscheinlichkeitsverteilungen des Roboterzustands statt über eine einzelne Schätzung, sodass Aktionen gewählt werden können, die sowohl Unsicherheit verringern als auch zum Ziel führen.

Definition

Ein Roboter kennt seinen Zustand selten genau: Seine Pose, die Positionen von Objekten und das Ergebnis von Kontakten sind nur über verrauschte Sensorik bekannt. Ein Belief ist eine Wahrscheinlichkeitsverteilung über mögliche Zustände bei gegebener Historie von Aktionen und Beobachtungen, und der Belief Space ist der Raum aller solchen Verteilungen. Belief-Space-Planung (belief-space planning) wählt Aktionen, indem sie vorhersagt, wie diese den Belief verändern werden, nicht nur den nominalen Zustand. Dadurch kann der Planer den Fortschritt zum Ziel gegen die Verringerung von Unsicherheit abwägen, etwa indem er nahe an einer Landmarke vorbeifährt, um sich zu lokalisieren, bevor er eine enge Türöffnung passiert, oder indem er ein Objekt berührt, um seine Position zu ermitteln, bevor er es greift.

Formal ist Belief-Space-Planung ein Weg, teilweise beobachtbare Markov-Entscheidungsprozesse (POMDPs) zu lösen. Der POMDP ist die Problemformulierung; formuliert man ihn über Beliefs um, wird er zu einem vollständig beobachtbaren Entscheidungsproblem, in dem der Belief die Rolle des Zustands spielt. Belief Spaces sind hochdimensional, für kontinuierliche Zustände sogar unendlichdimensional, sodass exakte Lösungen für Roboter selten praktikabel sind und Verfahren approximieren. Gaußsche Belief-Space-Planer stellen den Belief durch Mittelwert und Kovarianz dar, propagieren ihn mit einem erweiterten Kalman-Filter und suchen oder optimieren dann über diese kompakten Beliefs, wie bei Belief Roadmaps und LQG-basierter Bewegungsplanung. Partikelbasierte Verfahren stellen Beliefs mit gewichteten Samples dar, und Online-POMDP-Löser durchsuchen vom aktuellen Belief aus einen Baum von Aktions- und Beobachtungsfolgen. Viele Systeme vereinfachen weiter, indem sie während der Planung die wahrscheinlichste Beobachtung annehmen und neu planen, wenn die echten Beobachtungen eintreffen.

Belief-Space-Planung unterscheidet sich von Planung auf dem mittleren Zustand mit Sicherheitsabständen, die Unsicherheit als fest behandelt. Im Belief Space können Aktionen Unsicherheit gezielt verringern, sodass Pläne informationsgewinnende Bewegungen enthalten können, die ein deterministischer Planer nie wählen würde. Der Preis ist Rechenaufwand, und die Planqualität hängt davon ab, wie genau die Sensor- und Bewegungsmodelle künftige Beliefs vorhersagen. Bei manchen Aufgaben erreichen reaktive Regler, die ohne Vorausschau auf die aktuelle Schätzung reagieren, eine vergleichbare Leistung bei viel geringeren Kosten, weshalb Belief-Space-Planer oft als Baselines für solche Verfahren dienen.

Warum es wichtig ist

Roboter, die nur auf ihrer besten Zustandsschätzung planen, können sich auf Aktionen festlegen, die scheitern, wenn diese Schätzung falsch ist, etwa dort zu greifen, wo ein Objekt vermutet wird. Belief-Space-Planung macht Unsicherheit zum Teil der Entscheidung, erzeugt Pläne, die lokalisieren, messen oder abtasten, wenn das günstiger ist als ein Fehlschlag, und bietet eine fundierte Methode, um zu entscheiden, wann zusätzliche Sensorik die Zeit wert ist.

Wichtige Anwendungen

Navigation mit aktiver Lokalisierung, wo Landmarken spärlich sind
Manipulation unter Unsicherheit der Objektpose, einschließlich berührungsbasierter Lokalisierung
Einsetzen und andere Kontaktaufgaben, bei denen der Positionsfehler das Spiel übersteigt
Suche und Exploration, die Informationsgewinn gegen Fahrtkosten abwägen
Entscheidungsfindung für Fahrzeuge, die über die Absichten anderer Agenten unsicher sind
Greifen in unaufgeräumten Umgebungen mit teilweiser Verdeckung

In der Praxis

Ein Roboter muss einen Schlüssel in ein Schloss stecken, dessen Position von einer Kamera nur auf wenige Millimeter genau bekannt ist, mehr als das Spiel beim Einsetzen. Ein Planer, der auf der mittleren Schätzung arbeitet, würde direkt zur vermuteten Position fahren und oft danebenliegen. Ein Belief-Space-Planer stellt die Schlossposition als Gaußverteilung dar, sagt vorher, wie stark jede Kandidatenbewegung und jeder Kontakt die Kovarianz verkleinern würde, und stellt fest, dass das Entlanggleiten des Schlüssels an der Schlossfläche, bis er auf die Kante trifft, die Unsicherheit entlang einer Achse kostengünstig beseitigt. Der Plan enthält daher vor dem Einsetzen eine abgesicherte Tastbewegung. Während der Ausführung aktualisiert ein erweitertes Kalman-Filter den Belief mit Kraftmesswerten, und der Planer plant vom neuen Belief aus neu, wann immer Beobachtungen von seinen Vorhersagen abweichen.

Häufige Missverständnisse

Belief-Space-Planung ist einfach Planung mit Fehlerreserven — Reserven behandeln Unsicherheit als fest, während Belief-Space-Planer Aktionen wählen können, die sie verringern
Ein Belief ist dasselbe wie eine Zustandsschätzung — eine Zustandsschätzung ist meist ein einzelner Punkt wie der Mittelwert, während der Belief die gesamte Verteilung ist, einschließlich ihrer Streuung und Form
Belief-Space-Planung erfordert, den vollständigen POMDP exakt zu lösen — praktische Verfahren stützen sich auf Näherungen wie gaußsche Beliefs, Partikel oder die Annahme der wahrscheinlichsten Beobachtung

Wer das wissen sollte

Forschende in Bewegungs- und Aufgabenplanung, die unter Unsicherheit arbeiten
Manipulationsingenieure, die mit Unsicherheit der Objektpose umgehen
Ingenieure für autonome Navigation
Studierende der probabilistischen Robotik

Open Source Robotics