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

1 Citation (Scopus)

Abstract

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
Volume37
Issue number13-14
DOIs
StatePublished - Dec 1 2018

Fingerprint

Tabletop
Rearrangement
End effectors
Pipelines
Minimise
Overlapping
Scalability
Hardness
Robots
Hardware
Experimental Evaluation
Geometry
Overlap
Reverse
Horizontal
Robot
Path
Object
Optimization

All Science Journal Classification (ASJC) codes

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

Keywords

  • Object rearrangement
  • path planning
  • robot manipulation

Cite this

Han, Shuai D. ; Stiffler, Nicholas M. ; Krontiris, Athanasios ; Bekris, Kostas E. ; Yu, Jingjin. / Complexity Results and Fast Methods for Optimal Tabletop Rearrangement with Overhand Grasps. In: International Journal of Robotics Research. 2018 ; Vol. 37, No. 13-14. pp. 1775-1795.
@article{a8edaf210d36483dba2976f6f3df4606,
title = "Complexity Results and Fast Methods for Optimal Tabletop Rearrangement with Overhand Grasps",
abstract = "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.",
keywords = "Object rearrangement, path planning, robot manipulation",
author = "Han, {Shuai D.} and Stiffler, {Nicholas M.} and Athanasios Krontiris and Bekris, {Kostas E.} and Jingjin Yu",
year = "2018",
month = "12",
day = "1",
doi = "10.1177/0278364918780999",
language = "English (US)",
volume = "37",
pages = "1775--1795",
journal = "International Journal of Robotics Research",
issn = "0278-3649",
publisher = "SAGE Publications Inc.",
number = "13-14",

}

Complexity Results and Fast Methods for Optimal Tabletop Rearrangement with Overhand Grasps. / Han, Shuai D.; Stiffler, Nicholas M.; Krontiris, Athanasios; Bekris, Kostas E.; Yu, Jingjin.

In: International Journal of Robotics Research, Vol. 37, No. 13-14, 01.12.2018, p. 1775-1795.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Han, Shuai D.

AU - Stiffler, Nicholas M.

AU - Krontiris, Athanasios

AU - Bekris, Kostas E.

AU - Yu, Jingjin

PY - 2018/12/1

Y1 - 2018/12/1

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

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

KW - Object rearrangement

KW - path planning

KW - robot manipulation

UR - http://www.scopus.com/inward/record.url?scp=85050319790&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85050319790&partnerID=8YFLogxK

U2 - 10.1177/0278364918780999

DO - 10.1177/0278364918780999

M3 - Article

AN - SCOPUS:85050319790

VL - 37

SP - 1775

EP - 1795

JO - International Journal of Robotics Research

JF - International Journal of Robotics Research

SN - 0278-3649

IS - 13-14

ER -