Robotics: Science and Systems XVII

On Minimizing the Number of Running Buffers for Tabletop Rearrangement

Kai Gao, Siwei Feng, Jingjin Yu


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.



    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}