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

Authors: Kaiyu Zheng, Yoonchang Sung, George Konidaris, Stefanie Tellex · IROS 2021

Licences

Open Access
Paper: CC BY 4.0

Everything below draws on the full paper under its CC BY 4.0 licence; its figure is credited to the authors.

TL;DR

3D multi-object search as a POMDP, solved online by planning at several octree resolutions in parallel; it beats flat baselines in large simulated spaces and runs on a Kinova MOVO.

Why it matters

It takes POMDP object search from 2D maps to 3D search regions while keeping online planning within a fixed time per step. The octree belief does not have to be built in full, and occlusion is handled through an UNKNOWN voxel label without geometry models of the clutter.

Problem

Household robots must find several objects on shelves, under tables and in cupboards with a limited, frustum-shaped camera view and with occlusion. POMDP-based object search is principled, but earlier work reduced the search space or robot mobility to 2D, because exact belief over large 3D state spaces is intractable and large observation spaces give planners a high branching factor.

Proposed solution

The authors define 3D-MOS, an object-oriented POMDP with 6D camera poses, MOVE, LOOK and FIND actions, and observations made of labelled voxels in the viewing frustum, factored per object. A per-voxel observation model and an octree belief give exact belief updates in O(|V| log |G|) and sampling at any resolution in O(log |G|); abstract POMDPs at coarser resolutions are each solved by POUCT in parallel and the highest-value action is executed (MR-POUCT).

Key insights

Factoring state and observation by object makes the belief space grow linearly, not exponentially, with the number of objects.
Modelling each voxel's label on its own, with occluded or out-of-view voxels uninformative, shrinks the observation space for planning and limits belief updates to voxels in view.
Storing beliefs in an octree, where each node holds the sum of its children's values, gives exact beliefs at every resolution and logarithmic-time sampling.
Planning at several resolutions in parallel and executing the best action copes with unknown object sizes and distances that a single resolution would not fit.
Particle beliefs (POMCP) suffer particle deprivation under large observation spaces and degrade to random behaviour in this domain.

Main results

In simulation over 12 settings (search space side m ∈ {4, 8, 16, 32}, n ∈ {2, 4, 6} objects, 40 trials each), MR-POUCT outperformed Exhaustive search in all test cases at m = 16 and m = 32 in discounted cumulative reward.
Exhaustive search did better in the small spaces (m = 4 and 8), where one view covers up to 17.2% and 8.8% of the grid; at m = 32 one view covers at most 2.6%.
Every method had at most 3.0 s of planning per step and 120 s to 480 s in total depending on m; POMCP performed poorly because of particle deprivation.
Under sensing noise on the (16, 2, 10) instance, MR-POUCT was consistently best for all settings tried, and β had almost no effect while β < 1. The text says 5 settings of α but lists six values (10, 100, 500, 10³, 10⁴, 10⁵).
On a Kinova MOVO, the robot found 3 of 6 objects placed at different heights in two regions of roughly 10 m² × 2 m in about 15 minutes, lowering its torso when needed to see a target.
Using k = 10 or k = 40 Monte Carlo samples for the abstract observation model gave similar search performance; k = 10 was used.

Limitations

Assuming objects are independent saves computation but can discard useful dependence between objects; searching for correlated objects is left open (stated by the authors).
The observation model does not reason over object geometry, and each object is assumed to fit in a single voxel at the planning resolution (stated by the authors).
A uniform random rollout policy was used; the authors suggest a heuristic rollout for more realistic problems at the cost of optimality.
On the real robot, objects not covered by any viewpoint of the topological map were missed; the authors propose a denser map or sampled MOVE destinations.
Objects and obstacles are assumed static, the robot state is assumed observable, and in small search spaces plain exhaustive search did better.

Field impact

It won the IROS 2021 Best RoboCup Paper Award and has 33 citations. The paper links a project page with video of the volumetric observations and octree belief updates; it does not state a code release.

Abstract

Robots operating in households must find objects on shelves, under tables, and in cupboards. In such environments, it is crucial to search efficiently at 3D scale while coping with limited field of view and the complexity of searching for multiple objects. Principled approaches to object search frequently use Partially Observable Markov Decision Process (POMDP) as the underlying framework for computing search strategies, but constrain the search space in 2D. In this paper, we present a POMDP formulation for multi-object search in a 3D region with a frustum-shaped field-of-view. To efficiently solve this POMDP, we propose a multi-resolution planning algorithm based on online Monte-Carlo tree search. In this approach, we design a novel octree-based belief representation to capture uncertainty of the target objects at different resolution levels, then derive abstract POMDPs at lower resolutions with dramatically smaller state and observation spaces. Evaluation in a simulated 3D domain shows that our approach finds objects more efficiently and successfully compared to a set of baselines without resolution hierarchy in larger instances under the same computational requirement. We demonstrate our approach on a mobile robot to find objects placed at different heights in two 10m² × 2m regions by moving its base and actuating its torso.

Open Source Robotics