作者：Dhruv Saxena Maxim Likhachev
We are interested in pick-and-place style robot manipulation tasks incluttered and confined 3D workspaces among movable objects that may berearranged by the robot and may slide, tilt, lean or topple. A recentlyproposed algorithm, M4M, determines which objects need to be moved and where bysolving a Multi-Agent Pathfinding MAPF abstraction of this problem. It thenutilises a nonprehensile push planner to compute actions for how the robotmight realise these rearrangements and a rigid body physics simulator to checkwhether the actions satisfy physics constraints encoded in the problem.However, M4M greedily commits to valid pushes found during planning, and doesnot reason about orderings over pushes if multiple objects need to berearranged. Furthermore, M4M does not reason about other possible MAPFsolutions that lead to different rearrangements and pushes. In this paper, weextend M4M and present Enhanced-M4M (E-M4M) — a systematic graph search-basedsolver that searches over orderings of pushes for movable objects that need tobe rearranged and different possible rearrangements of the scene. We introduceseveral algorithmic optimisations to circumvent the increased computationalcomplexity, discuss the space of problems solvable by E-M4M and show thatexperimentally, both on the real robot and in simulation, it significantlyoutperforms the original M4M algorithm, as well as other state-of-the-artalternatives when dealing with complex scenes.