Dealing with Difficult Instances of Object Rearrangement

Rearranging multiple objects is a critical skill for robots so that they can effectively deal with clutter in human spaces. This is a challenging problem as it involves combinatorially large, continuous C-spaces involving multiple movable bodies and complex kinematic constraints. This work initially revisits an existing search-based approach, which solves monotone challenges, i.e., when objects need to be grasped only once so as to be rearranged. The first contribution is the extension of this technique to a method that addresses many non-monotone challenges. The second contribution is the use of either the monotone or of the new non-monotone method as a local planner in the context of a higher-level task planner that searches the space of object placements and which provides stronger guarantees. The paper aims to emphasize the benefit of using more powerful motion primitives in the context of task planning for object rearrangement than an individual pick-andplace. Experiments in simulation using a model of a Baxter robot arm show the capability of solving difficult instances of rearrangement problems and evaluate the methods in terms of success ratio, running time, scalability and path quality.