  Real-world manipulation problems in heavy clutter require robots to reason
about potential contacts with objects in the environment. We focus on
pick-and-place style tasks to retrieve a target object from a shelf where some
`movable' objects must be rearranged in order to solve the task. In particular,
our motivation is to allow the robot to reason over and consider non-prehensile
rearrangement actions that lead to complex robot-object and object-object
interactions where multiple objects might be moved by the robot simultaneously,
and objects might tilt, lean on each other, or topple. To support this, we
query a physics-based simulator to forward simulate these interaction dynamics
which makes action evaluation during planning computationally very expensive.
To make the planner tractable, we establish a connection between the domain of
Manipulation Among Movable Objects and Multi-Agent Pathfinding that lets us
decompose the problem into two phases our M4M algorithm iterates over. First we
solve a multi-agent planning problem that reasons about the configurations of
movable objects but does not forward simulate a physics model. Next, an arm
motion planning problem is solved that uses a physics-based simulator but does
not search over possible configurations of movable objects. We run simulated
and real-world experiments with the PR2 robot and compare against relevant
baseline algorithms. Our results highlight that M4M generates complex 3D
interactions, and solves at least twice as many problems as the baselines with
competitive performance.
