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