Complexity Results and Fast Methods for Optimal Tabletop Rearrangement with Overhand Grasps

Shuai D. Han, Nicholas M. Stiffler, Athanasios Krontiris, Kostas E. Bekris, Jingjin Yu

Research output: Contribution to journalArticle

2 Scopus citations


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. Although 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.

Original languageEnglish (US)
Pages (from-to)1775-1795
Number of pages21
JournalInternational Journal of Robotics Research
Issue number13-14
StatePublished - Dec 1 2018

All Science Journal Classification (ASJC) codes

  • Software
  • Modeling and Simulation
  • Mechanical Engineering
  • Artificial Intelligence
  • Electrical and Electronic Engineering
  • Applied Mathematics


  • Object rearrangement
  • path planning
  • robot manipulation

Fingerprint Dive into the research topics of 'Complexity Results and Fast Methods for Optimal Tabletop Rearrangement with Overhand Grasps'. Together they form a unique fingerprint.

  • Cite this