On Minimizing the Number of Running Buffers for Tabletop Rearrangement

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.