We consider the problem of planning for pick-and-place manipulation in heavy clutter where it might be necessary to interact with and rearrange movable objects via a sequence of non-prehensile pushes in order to grasp and extract a desired object. This planning problem is computationally very challenging for several reasons. First, it requires searching over a search-space that includes the configuration of movable objects. Second, it requires prediction of the effects of all the non-prehensile interactions with objects considered by the planner, which involves forward simulating a computationally expensive physics-based model. In this paper, we make an observation that the problem of planning for Manipulation
Among Movable Objects is closely related to the Multi-Agent Pathfinding problem if we treat all movable objects as actuated robots. Using this insight, we construct a planning algorithm that iterates between (i) solving a multi-agent planning problem that reasons about the configuration of movable objects but does not forward simulate a physics model, and (ii) solving an arm motion planning problem that uses a physics-based simulator but does not search over the possible configurations of movable objects. We present the M4M algorithm, briefly analyse it from a theoretical perspective, and evaluate its performance experimentally in both simulations and on a physical PR2 robot.