Rearranging multiple objects is a critical skill for robots so they can effectively deal with clutter in human spaces. This is a challenging problem as it involves searching combinatorially large, continuous C-spaces with multiple movable bodies and complex kinematic constraints. This work revisits an existing search-based approach that can compute solutions for monotone problem instances using backtracking search. Monotone problem instances require each object to be moved at most once.
The first contribution is the extension of this technique to a method that addresses many non-monotone problem instances by utilizing an efficient but approximate solution to the Minimum Constraint Removal (MCR) path planning problem. The second contribution is the use of such solvers as local primitives in the context of a higher-level task planner that searches the space of object placements and achieves probabilistic completeness. This work emphasizes the benefit of using more powerful connection primitives in the context of task planning for object rearrangement than an individual pick-and-place. The third contribution is a significantly more efficient, but heuristic incremental version of the hierarchical framework. The methods make use of a dependency graph between objects given MCR paths to transfer each object to its target, which effectively guides the expansion of a bidirectional RRT in the space of object arrangements.
Experiments in simulation using a model of a robot arm show the capability of solving difficult instances of rearrangement problems and this work evaluates the methods in terms of success ratio, running time, scalability and path quality. Overall the graph-based high-level task planner has stronger guarantees, while the incremental search algorithm has higher success ratio, faster solution times, robust scalability and improved path quality relative to all the alternatives considered. The framework has also been demonstrated on a real robotic manipulator.