  We are interested in pick-and-place style robot manipulation tasks in
cluttered and confined 3D workspaces among movable objects that may be
rearranged by the robot and may slide, tilt, lean or topple. A recently
proposed algorithm, M4M, determines which objects need to be moved and where by
solving a Multi-Agent Pathfinding MAPF abstraction of this problem. It then
utilises a nonprehensile push planner to compute actions for how the robot
might realise these rearrangements and a rigid body physics simulator to check
whether the actions satisfy physics constraints encoded in the problem.
However, M4M greedily commits to valid pushes found during planning, and does
not reason about orderings over pushes if multiple objects need to be
rearranged. Furthermore, M4M does not reason about other possible MAPF
solutions that lead to different rearrangements and pushes. In this paper, we
extend M4M and present Enhanced-M4M (E-M4M) -- a systematic graph search-based
solver that searches over orderings of pushes for movable objects that need to
be rearranged and different possible rearrangements of the scene. We introduce
several algorithmic optimisations to circumvent the increased computational
complexity, discuss the space of problems solvable by E-M4M and show that
experimentally, both on the real robot and in simulation, it significantly
outperforms the original M4M algorithm, as well as other state-of-the-art
alternatives when dealing with complex scenes.
