Robotics: Science and Systems XVII
On Minimizing the Number of Running Buffers for Tabletop Rearrangement
Kai Gao, Siwei Feng, Jingjin YuAbstract:
For tabletop rearrangement problems with overhand grasps; storage space outside the tabletop workspace; or buffers; can temporarily hold objects which greatly facilitates the resolution of a given rearrangement task. This brings forth the natural question of how many running buffers are required so that certain classes of tabletop rearrangement problems are feasible. In this work; we examine the problem for both the labeled (where each object has a specific goal pose) and the unlabeled (where goal poses of objects are interchangeable) settings. On the structural side; we observe that finding the minimum number of running buffers (MRB) can be carried out on a dependency graph abstracted from a problem instance; and show that computing MRB on dependency graphs is NP-hard. We then prove that under both labeled and unlabeled settings; even for uniform cylindrical objects; the number of required running buffers may grow unbounded as the number of objects to be rearranged increases; we further show that the bound for the unlabeled case is tight. On the algorithmic side; we develop highly effective algorithms for finding MRB for both labeled and unlabeled tabletop rearrangement problems; scalable to over a hundred objects under very high object density. Employing these algorithms; empirical evaluations show that random labeled and unlabeled instances; which more closely mimics real-world setups; have much smaller MRB.
Bibtex:
@INPROCEEDINGS{GaoK-RSS-21, AUTHOR = {Kai Gao AND Siwei Feng AND Jingjin Yu}, TITLE = {{On Minimizing the Number of Running Buffers for Tabletop Rearrangement}}, BOOKTITLE = {Proceedings of Robotics: Science and Systems}, YEAR = {2021}, ADDRESS = {Virtual}, MONTH = {July}, DOI = {10.15607/RSS.2021.XVII.033} }