  This paper studies the underlying combinatorial structure of a class of
object rearrangement problems, which appear frequently in applications. The
problems involve multiple, similar-geometry objects placed on a flat,
horizontal surface, where a robot can approach them from above and perform
pick-and-place operations to rearrange them. The paper considers both the case
where the start and goal object poses overlap, and where they do not. For
overlapping poses, the primary objective is to minimize the number of
pick-and-place actions and then to minimize the distance traveled by the
end-effector. For the non-overlapping case, the objective is solely to minimize
the travel distance of the end-effector. While such problems do not involve all
the complexities of general rearrangement, they remain computationally hard in
both cases. This is shown through reductions from well-understood, hard
combinatorial challenges to these rearrangement problems. The reductions are
also shown to hold in the reverse direction, which enables the convenient
application on rearrangement of well studied algorithms. These algorithms can
be very efficient in practice despite the hardness results. The paper builds on
these reduction results to propose an algorithmic pipeline for dealing with the
rearrangement problems. Experimental evaluation, including hardware-based
trials, shows that the proposed pipeline computes high-quality paths with
regards to the optimization objectives. Furthermore, it exhibits highly
desirable scalability as the number of objects increases in both the
overlapping and non-overlapping setup.
