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.

本文介绍了一种基于多智能体路径规划和非抓取式推动规划的机器人操纵方法，该方法可以在混乱和受限的三维工作空间中移动物体，并利用刚体物理模拟器检查路径是否满足物理约束，通过改进后的算法在实际机器人操作和模拟操作中优于其他现有算法。