  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.
