Multi-Resolution POMDP Planning for Multi-Object Search in 3D

Autoren: Kaiyu Zheng, Yoonchang Sung, George Konidaris, Stefanie Tellex · 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

Objektsuche nach mehreren Objekten in 3D als POMDP, online gelöst durch parallele Planung auf mehreren Octree-Auflösungen; in großen simulierten Räumen schlägt der Ansatz flache Baselines und läuft auf einem Kinova MOVO.

Warum es wichtig ist

Die Arbeit überträgt die POMDP-Objektsuche von 2D-Karten auf 3D-Suchregionen und hält die Online-Planung dabei innerhalb einer festen Zeit pro Schritt. Der Octree-Belief muss nicht vollständig aufgebaut werden, und Verdeckung wird über ein Voxel-Label UNKNOWN behandelt, ohne Geometriemodelle der umgebenden Gegenstände.

Problem

Haushaltsroboter müssen mehrere Objekte in Regalen, unter Tischen und in Schränken finden, mit einem begrenzten, kegelstumpfförmigen Kamerasichtfeld und mit Verdeckungen. POMDP-basierte Objektsuche ist prinzipienbasiert, doch frühere Arbeiten reduzierten den Suchraum oder die Mobilität des Roboters auf 2D, weil exakte Beliefs über große 3D-Zustandsräume nicht handhabbar sind und große Beobachtungsräume Planern einen hohen Verzweigungsfaktor bescheren.

Lösungsansatz

Die Autoren definieren 3D-MOS, ein objektorientiertes POMDP mit 6D-Kameraposen, den Aktionen MOVE, LOOK und FIND sowie Beobachtungen aus gelabelten Voxeln im Sichtkegelstumpf, faktorisiert pro Objekt. Ein Beobachtungsmodell pro Voxel und ein Octree-Belief liefern exakte Belief-Updates in O(|V| log |G|) und Sampling auf beliebiger Auflösung in O(log |G|); abstrakte POMDPs auf gröberen Auflösungen werden jeweils parallel mit POUCT gelöst, und die Aktion mit dem höchsten Wert wird ausgeführt (MR-POUCT).

Wichtigste Erkenntnisse

Werden Zustand und Beobachtung nach Objekten faktorisiert, wächst der Belief-Raum linear statt exponentiell mit der Anzahl der Objekte.
Wird das Label jedes Voxels für sich modelliert und gelten verdeckte oder außerhalb des Sichtfelds liegende Voxel als nicht informativ, schrumpft der Beobachtungsraum für die Planung, und Belief-Updates beschränken sich auf Voxel im Sichtfeld.
Beliefs in einem Octree zu speichern, in dem jeder Knoten die Summe der Werte seiner Kinder hält, liefert exakte Beliefs auf jeder Auflösung und Sampling in logarithmischer Zeit.
Paralleles Planen auf mehreren Auflösungen und Ausführen der besten Aktion bewältigt unbekannte Objektgrößen und Entfernungen, zu denen eine einzelne Auflösung nicht passen würde.
Partikel-Beliefs (POMCP) leiden bei großen Beobachtungsräumen unter Partikelverarmung und fallen in dieser Domäne auf zufälliges Verhalten zurück.

Hauptergebnisse

In der Simulation über 12 Konfigurationen (Seitenlänge des Suchraums m ∈ {4, 8, 16, 32}, n ∈ {2, 4, 6} Objekte, jeweils 40 Durchläufe) übertraf MR-POUCT die Exhaustive-Suche in allen Testfällen bei m = 16 und m = 32 in der diskontierten kumulativen Belohnung.
Die Exhaustive-Suche schnitt in den kleinen Räumen (m = 4 und 8) besser ab, in denen eine Ansicht bis zu 17,2 % bzw. 8,8 % des Gitters abdeckt; bei m = 32 deckt eine Ansicht höchstens 2,6 % ab.
Jede Methode hatte höchstens 3,0 s Planungszeit pro Schritt und je nach m insgesamt 120 s bis 480 s; POMCP schnitt wegen Partikelverarmung schlecht ab.
Unter Sensorrauschen auf der Instanz (16, 2, 10) war MR-POUCT in allen getesteten Einstellungen durchgehend am besten, und β hatte nahezu keinen Einfluss, solange β < 1. Der Text spricht von 5 Einstellungen für α, nennt aber sechs Werte (10, 100, 500, 10³, 10⁴, 10⁵).
Auf einem Kinova MOVO fand der Roboter in etwa 15 Minuten 3 von 6 Objekten, die in unterschiedlichen Höhen in zwei Regionen von ungefähr 10 m² × 2 m platziert waren, und senkte bei Bedarf seinen Torso, um ein Ziel zu sehen.
Mit k = 10 oder k = 40 Monte-Carlo-Samples für das abstrakte Beobachtungsmodell war die Suchleistung ähnlich; verwendet wurde k = 10.

Einschränkungen

Die Annahme unabhängiger Objekte spart Rechenaufwand, kann aber nützliche Abhängigkeiten zwischen Objekten verwerfen; die Suche nach korrelierten Objekten bleibt offen (laut den Autoren).
Das Beobachtungsmodell berücksichtigt die Objektgeometrie nicht, und es wird angenommen, dass jedes Objekt bei der Planungsauflösung in ein einzelnes Voxel passt (laut den Autoren).
Es wurde eine gleichverteilt zufällige Rollout-Policy verwendet; die Autoren schlagen für realistischere Probleme einen heuristischen Rollout vor, auf Kosten der Optimalität.
Auf dem realen Roboter wurden Objekte übersehen, die von keinem Blickpunkt der topologischen Karte erfasst wurden; die Autoren schlagen eine dichtere Karte oder gesampelte MOVE-Ziele vor.
Objekte und Hindernisse werden als statisch angenommen, der Roboterzustand als beobachtbar, und in kleinen Suchräumen schnitt die einfache erschöpfende Suche besser ab.

Wirkung auf das Fachgebiet

Die Arbeit gewann den IROS 2021 Best RoboCup Paper Award und hat 33 Zitierungen. Das Paper verlinkt eine Projektseite mit einem Video der volumetrischen Beobachtungen und der Octree-Belief-Updates; eine Code-Veröffentlichung wird nicht angegeben.

Zusammenfassung

Roboter, die in Haushalten arbeiten, müssen Objekte in Regalen, unter Tischen und in Schränken finden. In solchen Umgebungen ist es entscheidend, im 3D-Maßstab effizient zu suchen und dabei mit einem begrenzten Sichtfeld und der Komplexität der Suche nach mehreren Objekten zurechtzukommen. Prinzipienbasierte Ansätze zur Objektsuche verwenden häufig den teilweise beobachtbaren Markov-Entscheidungsprozess (POMDP) als zugrunde liegendes Rahmenwerk zur Berechnung von Suchstrategien, beschränken den Suchraum jedoch auf 2D. In diesem Beitrag stellen wir eine POMDP-Formulierung für die Suche nach mehreren Objekten in einer 3D-Region mit kegelstumpfförmigem Sichtfeld vor. Um dieses POMDP effizient zu lösen, schlagen wir einen Planungsalgorithmus mit mehreren Auflösungen vor, der auf Online-Monte-Carlo-Baumsuche basiert. In diesem Ansatz entwerfen wir eine neuartige Octree-basierte Belief-Repräsentation, um die Unsicherheit über die Zielobjekte auf verschiedenen Auflösungsstufen zu erfassen, und leiten dann abstrakte POMDPs auf niedrigeren Auflösungen mit drastisch kleineren Zustands- und Beobachtungsräumen ab. Die Evaluation in einer simulierten 3D-Domäne zeigt, dass unser Ansatz Objekte in größeren Instanzen bei gleichem Rechenaufwand effizienter und erfolgreicher findet als eine Reihe von Baselines ohne Auflösungshierarchie. Wir demonstrieren unseren Ansatz auf einem mobilen Roboter, der in zwei Regionen von 10m² × 2m Objekte in unterschiedlichen Höhen findet, indem er seine Basis bewegt und seinen Torso antreibt.

Open Source Robotics