PaperlayerView exact revision on arXiv

Source-linked AI summary

Mechanical Search: Multi-Step Retrieval of a Target Object Occluded by Clutter

Michael Danielczuk, Andrey Kurenkov, Ashwin Balakrishna, Matthew Matl, David Wang, Roberto Martín-Martín, Animesh Garg, Silvio Savarese, Ken Goldberg

arXiv:1903.01588v1cs.RO

TL;DR

Robots must locate and retrieve targets that may be obscured in clutter, a task that combines perception and manipulation. The paper formalizes Mechanical Search and evaluates heuristic multi-step action-selection policies; largest-first policies retrieve targets within five or fewer actions on half of heaps in both simulation and physical trials, while a human supervisor achieves higher efficiency than the best policy.

  • Problem

    In cluttered environments, target objects may be neither visible nor accessible to grasp, so robots must interact with the environment to locate and expose them.

    Source: §I · p. 1

  • Method

    The paper formulates Mechanical Search and evaluates five policies that prioritize targets and other objects differently while selecting among grasping and pushing actions.

    Source: §I · p. 1, §V · p. 4

  • Results

    Largest-first policies retrieve within 5 or fewer actions on 50% of heaps in simulation (preempted random/random: 30%/10%) and physical trials (40%/10%).

    Source: A. Simulation Results · p. 5, B. Physical Results · p. 6

  • Takeaways & Limitations

    A human selecting low-level actions achieves 37% higher efficiency than the best action-selection method by pushing significantly more effectively and often.

    Source: §VIII · p. 6

    In physical trials, stochastic initial bin states can leave the target differently visible across policies on the same heap, contributing to variance in results.

    Source: B. Physical Results · p. 6

Abstract

from arXiv · show

When operating in unstructured environments such as warehouses, homes, and retail centers, robots are frequently required to interactively search for and retrieve specific objects from cluttered bins, shelves, or tables. Mechanical Search describes the class of tasks where the goal is to locate and extract a known target object. In this paper, we formalize Mechanical Search and study a version where distractor objects are heaped over the target object in a bin. The robot uses an RGBD perception system and control policies to iteratively select, parameterize, and perform one of 3 actions -- push, suction, grasp -- until the target object is extracted, or either a time limit is exceeded, or no high confidence push or grasp is available. We present a study of 5 algorithmic policies for mechanical search, with 15,000 simulated trials and 300 physical trials for heaps ranging from 10 to 20 objects. Results suggest that success can be achieved in this long-horizon task with algorithmic policies in over 95% of instances and that the number of actions required scales approximately linearly with the size of the heap. Code and supplementary material can be found at http://ai.stanford.edu/mech-search .

I. INTRODUCTION

Mechanical Search asks robots to locate and extract targets obscured or inaccessible in clutter, requiring visual reasoning, planning, and action execution. The paper proposes an integrated framework and situates it against prior perception, manipulation, and planning approaches.

I. INTRODUCTION

  • Mechanical Search requires a robot to locate and extract a target that may be obscured or inaccessible in clutter.The task combines visual reasoning, task, motion, and grasp planning, and action execution.Source: §I · p. 1

II. BACKGROUND AND RELATED WORK

  • Combining object segmentation and recognition with action selection can support multi-step search and extraction from clutter.The paper builds on prior segmentation, recognition, and grasp-planning methods.Source: §I · p. 1, §II · p. 2

I. INTRODUCTION

  • The paper proposes an integrated framework and contributes a generalized formulation, an implementation with five action-selection policies, and simulated and physical evaluations.The specific version retrieves occluded targets from cluttered bins using parallel-jaw grasps, suction grasps, and pushes.Source: §I · p. 1

II. BACKGROUND AND RELATED WORK

  • Prior grasping-in-clutter methods had not addressed the multi-step plans needed to grasp occluded or inaccessible targets.The paper formulates Mechanical Search as interactive search combining grasping and pushing.Source: §II · p. 2
  • Hierarchical sequential-control models can be computationally expensive to train, while search-based high-level planning requires complete domain specification and is described as applicable only to relatively uncluttered environments with few objects.Source: §II · p. 2
  • The closest cited work searches for objects on shelves using pushing and grasping, whereas this paper studies more cluttered settings and temporally extended manipulation policies.Source: §II · p. 2

III. MECHANICAL SEARCH: PROBLEM FORMULATION

The paper frames Mechanical Search as a POMDP and specifies a bin-retrieval version with RGB-D observations, parameterized manipulation actions, and a reward tied to retrieval probability. Its policies use heuristics rather than directly optimizing that reward.

III. MECHANICAL SEARCH: PROBLEM FORMULATION

  • Mechanical Search seeks to retrieve a specified target from a physical environment containing varied objects within a task horizon while minimizing time, and is framed as a POMDP.The target may be specified by images, text, a 3D model, or another representation.Source: §III · p. 2
  • The general formulation represents states, actions, transitions, rewards, and observations; reward estimates the change in probability of extracting the target within the task horizon.States include object geometry and pose, robot pose and joints, and sensor poses; observations include RGB-D sensor data.Source: §III · p. 2
  • The studied version retrieves a target specified by k RGB images from a single-bin heap while minimizing the number of actions.It uses an overhead RGB-D image and parameterized parallel-jaw grasp, suction-grasp, and push actions.Source: §III · p. 2
  • The policies do not directly optimize the proposed increase in estimated target-grasp reliability because computing it is difficult; they instead use heuristics to remove and push objects until extraction.Source: §III · pp. 2–3

IV. PERCEPTION AND DECISION SYSTEM

The system is implemented for both simulation and physical experiments through a perception and policy-execution pipeline.

IV. PERCEPTION AND DECISION SYSTEM

  • The implementation runs in simulation and on a physical system through a pipeline for perception and policy execution.Source: §IV · p. 3

A. Perception

The perception pipeline segments object instances from depth images, then compares colorized object masks with target images to identify the target when confidence is sufficient.

A. Perception

  • SD Mask R-CNN, trained exclusively on synthetic depth images, converts depth images into unclassified binary object masks and generalizes to arbitrary objects without retraining.Source: A. Perception · p. 3
  • The system combines each object mask with the RGB image and compares transformed color-mask crops against the k target images using a Siamese network.A mask receives the maximum recognition confidence across the target images.Source: A. Perception · p. 3
  • The highest-scoring mask is labeled as the target only if its recognition score exceeds threshold tr; otherwise, the system reports no target match.Source: A. Perception · p. 3

B. Search Policy

The search system separates high-level action selection from low-level action policies. The selector chooses an object and action policy, while each policy returns an action and a quality metric.

B. Search Policy

  • The hierarchical design pairs an action selector with action policies, supporting search spaces that may extend beyond bin-picking actions.The selector chooses an object and action; the policies correspond to actions in the problem formulation.Source: B. Search Policy · p. 3
  • The selector chooses a goal object and action policy from visible masks, then uses the returned quality metric to decide whether to execute the action.The policy returns an action and its associated quality metric for the selected object.Source: B. Search Policy · p. 3
  • Each action policy takes an object mask and RGBD observation as input and returns an action with a quality metric.Simulation uses ground-truth masks and depth images; physical experiments use sensor depth images and masks from the perception pipeline.Source: B. Search Policy · pp. 3–4
  • Grasp policies select the highest-quality candidate constrained to the goal object's mask, while the push policy seeks a collision-free push toward the bin's most free point.Parallel-jaw and suction grasping use separate quality models; a valid push receives quality 1, otherwise 0.Source: B. Search Policy · p. 4

V. ACTION SELECTION POLICIES

The policies vary in how they prioritize objects and whether they can push. Shared execution criteria govern grasp and push actions, while simulation heaps and action rollouts are generated through specified procedures.

V. ACTION SELECTION POLICIES

  • The policies execute a grasp when its quality exceeds the object-specific threshold; pushing policies use a higher threshold for non-target objects and push when a valid action is found.If no qualifying grasp exists, a pushing policy searches for a valid push; policies terminate when no action qualifies or after more than three consecutive pushes.Source: §V · p. 4
  • Largest-first search prioritizes the target and ranks other objects by visible area, while preempted-random prioritizes the target and random search orders objects randomly.Largest-first is intended to increase the likelihood of removing objects that may occlude an unseen target.Source: §V · p. 4

A. Simulation

  • Simulation heaps contain 1,000 heaps for each size of 10, 15, and 20 objects, with the target chosen as the most occluded object.Objects are dropped one by one into the bin using the Bullet Physics Engine.Source: A. Simulation · p. 4
  • Simulated grasps use wrench-space analysis to test liftability, while pushes are executed only when the gripper can reach the starting location without collision.A lift applies constant upward force until the object leaves the bin; a simulated push moves a gripper model along the planned path.Source: A. Simulation · p. 4

B. Physical

The evaluation compares retrieval reliability and efficiency across search policies, with simulation results favoring largest-first policies for action efficiency. Physical trials used randomized 15-object heaps and the same push and grasp primitives for policy and human-supervisor rollouts.

B. Physical

  • Physical trials used 50 heaps of 15 items drawn from 75 household objects, with each target randomized and covered by the other fourteen objects.The physical set included unusual 3D-printed shapes and uniform textures that challenged segmentation and target recognition.Source: B. Physical · p. 4, Figure 3 · p. 5
  • The ABB YuMi executed policy actions, while a human supervisor selected masks for the same push and grasp primitives.The human could use their own perceptual judgment and high-level planning but remained limited to the available action primitives.Source: B. Physical · p. 5

C. Evaluation Metrics

  • Reliability is the frequency of successful target extraction, while efficiency is the mean number of actions per successful extraction.The evaluation recorded successes, failures, and action-count statistics.Source: C. Evaluation Metrics · p. 5

A. Simulation Results

  • Mean actions needed for target extraction appeared to scale linearly with heap size, although the rate of increase varied across policies.The results also suggest extraction becomes more difficult as heap size increases.Source: A. Simulation Results · p. 5
  • 50% of simulated 15-object heaps were cleared within 5 or fewer actions by largest-first policies, versus 30% for preempted random and 10% for random policies.The figure presents policy performance across simulated and real heaps; all policies reached at least 90% success on simulated 15-object heaps.Source: A. Simulation Results · p. 5, Figure 4 · p. 6
  • Policies with pushing succeeded on at least 3% more heaps than policies without pushing, while pushes made up 5% of actions on 10-object heaps and 3% on 15-object heaps.The authors suspect pushes are rare because the primitive targets singulation rather than flattening a heap.Source: A. Simulation Results · p. 5
  • Simulation failures accounted for 6–12% of rollouts, and 85–90% of failures involved no action meeting the quality threshold.Objects moved to bin corners often made collision-free grasps difficult; pushing could also send objects over the bin wall.Source: A. Simulation Results · p. 5

B. Physical Results

In physical trials, all policies retrieved the target in at least 90% of trials, with largest-first policies extracting it more efficiently than random policies. Initial target visibility varied across trials, and most failures involved inability to plan an action.

B. Physical Results

  • At least 90% of physical trials succeeded for every policy, with success rates not statistically different; largest-first policies extracted targets within five actions on 50% of heaps, versus 40% for preempted random and 10% for random.The 300 physical experiments showed similar cumulative-success trends to simulation, with largest-first policies more efficient than random policies.Source: B. Physical Results · p. 6
  • Different initial visibility of the target across physical trials of the same heap could make policies lucky or unlucky and may explain some increased variance in results.A target could be fully covered for one policy and partially or fully visible for another.Source: B. Physical Results · p. 6
  • 93% of physical failures arose from inability to plan an action, usually because a target lying flat on the bin bottom was difficult to segment accurately or no target mask was identified.The latter issue often occurred for 3D-printed objects; only one of the 300 physical rollouts failed due to timing out.Source: B. Physical Results · p. 6

C. Action-Limited Human Supervisor

A human supervisor extracted targets more efficiently than the algorithmic policies, using pushes more often to clear clutter. The discussion identifies action selection and action primitives as areas for improvement, including future exploration of reinforcement learning and learned pushes.

C. Action-Limited Human Supervisor

  • The human supervisor required an average of 3.1 actions to extract the target, and the discussion reports 37% higher efficiency than the best action-selection policy through more effective and frequent pushing.The human chose pushes for 26% of actions, compared with 6% for the other policies that included pushing.Source: C. Action-Limited Human Supervisor · p. 6, §VIII · p. 6
  • Human pushes spread multiple objects across the bin bottom, whereas a grasp removes only one object from the top of the heap.The operator pushed more often when objects were heaped in the bin center and the target was not visible.Source: C. Action-Limited Human Supervisor · p. 6

VIII. DISCUSSION AND FUTURE WORK

  • The authors identify the grasp, suction, and push primitives as improvable and conjecture that more effective push primitives could be learned from simulation.They also plan to explore whether reinforcement learning in simulation can address the efficiency gap.Source: §VIII · p. 6

IX. APPENDIX

The appendix reports simulation and physical results for policy efficiency, success, and action selection, alongside implementation details for the Siamese network. In physical trials, policies exceeded 90% success, while human action selection outperformed the best policy in mean actions.

A. Extended Results

  • The appendix notes a difference between simulation, where pushing increased success rates, and physical trials, where the human pushed more frequently; the discrepancy is reserved for future investigation.The action-selection tables provide the respective simulation and physical breakdowns.Source: A. Extended Results · p. 6, Table II · p. 7, Table IV · p. 7
  • Largest-first policies extracted targets most efficiently in 1,000 simulated trials, while pushing showed ability to increase overall success rate.The table reports success rate and mean number of actions, with standard error of the mean, for each policy.Source: Table I · p. 6
  • Simulated policies typically attempted many more suction grasps than pushes, with pushes accounting for only a small fraction of selected actions.The action-selection breakdown covers 1,000 simulated trials.Source: Table II · p. 7
  • All policies achieved over 90% success in 50 physical trials, while the human outperformed the best policy by 37% in mean number of actions.The table reports success rate and mean actions, with standard error of the mean.Source: Table III · p. 7
  • In physical trials, the human pushed much more frequently than other policies, especially early on to clear multiple occluding objects.The table breaks down action selection across 50 physical trials.Source: Table IV · p. 7

B. Siamese Network Implementation Details

  • The Siamese network compares paired 512 × 512 RGB images using fixed pretrained ResNet-50 features and dense layers to output the probability that both images show the same object.Training used 10,000 positive and 10,000 negative image pairs for 10 epochs; physical experiments used a recognition-confidence threshold of 0.9.Source: B. Siamese Network Implementation… · p. 7

C. Simulated Heap Generation

Simulated heaps are built by dropping sampled objects into a bin, and the least-visible object is designated as the target using its modal-to-amodal mask-area ratio. Policy parameters use distinct grasp-confidence thresholds in simulation and physical experiments.

C. Simulated Heap Generation

  • A simulated heap samples objects from over 1,600 3D models, places them around the bin center, and drops them from a fixed height until they come to rest.The target is selected as the object with the smallest modal-to-amodal segmentation-mask area ratio, a proxy for least visibility.Source: C. Simulated Heap Generation · p. 7

D. Policy Parameters

  • Simulation uses grasp-confidence thresholds of 0.15 and 0.3 to decide whether to execute low-level grasp actions, balancing grasp reliability with clearing objects promptly.Physical trials use thresholds of 0.1 and 0.3; policies with pushing use a higher threshold of 0.5 to encourage pushing over low-quality grasps.Source: D. Policy Parameters · p. 7

Related papers

Loading 1903.01588v1…