Uniform Object Rearrangement: From Complete Monotone Primitives to Efficient Non-Monotone Informed Search
It addresses a combinatorial challenge in robotics for tasks like warehouse automation, though it is incremental as it builds on existing primitives and search frameworks.
This paper tackles the problem of robot object rearrangement by minimizing the number of object transfers, using a decomposition of the configuration space and dynamic programming primitives to handle monotone and non-monotone instances. The proposed method achieves near-optimal paths with higher success rates than alternatives in experiments.
Object rearrangement is a widely-applicable and challenging task for robots. Geometric constraints must be carefully examined to avoid collisions and combinatorial issues arise as the number of objects increases. This work studies the algorithmic structure of rearranging uniform objects, where robot-object collisions do not occur but object-object collisions have to be avoided. The objective is minimizing the number of object transfers under the assumption that the robot can manipulate one object at a time. An efficiently computable decomposition of the configuration space is used to create a "region graph", which classifies all continuous paths of equivalent collision possibilities. Based on this compact but rich representation, a complete dynamic programming primitive DFSDP performs a recursive depth first search to solve monotone problems quickly, i.e., those instances that do not require objects to be moved first to an intermediate buffer. DFSDP is extended to solve single-buffer, non-monotone instances, given a choice of an object and a buffer. This work utilizes these primitives as local planners in an informed search framework for more general, non-monotone instances. The search utilizes partial solutions from the primitives to identify the most promising choice of objects and buffers. Experiments demonstrate that the proposed solution returns near-optimal paths with higher success rate, even for challenging non-monotone instances, than other leading alternatives.