High-Quality Tabletop Rearrangement with Overhand Grasps: Hardness Results and Fast Methods


Authors: Shuai Han, Nicholas Stiffler, Athanasios Krontiris, Kostas Bekris, Jingjin Yu

This paper studies the underlying combinatorial structure of a class of object rearrangement problems that appear frequently in applications. This class consider multiple, similar-geometry objects placed on a flat, horizontal surface, where a robot can approach them with overhand grasps 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 end-effector distance. While this class of problems does not involve all the complexities of general rearrangement, it remains a computationally hard challenge for both cases. This is shown by reducing well understood combinatorial challenges that are hard to these rearrangement problems. The benefit of this reduction is that there are well studied algorithms for solving the combinatorial challenges. These algorithms can be very efficient in practice despite the hardness results. The paper builds on top of these reduction results to propose an algorithmic pipeline for dealing with the rearrangement problem. Experimental evaluation shows that the proposed pipeline achieves high-quality paths in terms of the optimization objective(s) and exhibits highly desirable scalability as the number of objects increases in both overlapping and non-overlapping setups.