# On Minimizing the Number of Running Buffers for Tabletop Rearrangement

arXiv: https://arxiv.org/abs/2105.06357 · HTML: https://mlsanity.com/paper/2105.06357/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 May 2021.

## Built on by (most cited first, 6 of 6)

- [CaTGrasp: Learning Category-Level Task-Relevant Grasping in Clutter from Simulation](https://mlsanity.com/paper/2109.09163/) (2021)
- [HANDAL: A Dataset of Real-World Manipulable Object Categories with Pose Annotations, Affordances, and Reconstructions](https://mlsanity.com/paper/2308.01477/) (2023)
- [Efficient and High-quality Prehensile Rearrangement in Cluttered and Confined Spaces](https://mlsanity.com/paper/2110.02814/) (2021)
- [Grasp, See, and Place: Efficient Unknown Object Rearrangement with Policy Structure Prior](https://mlsanity.com/paper/2402.15402/) (2024)
- [Robotic Test Tube Rearrangement Using Combined Reinforcement Learning and Motion Planning](https://mlsanity.com/paper/2401.09772/) (2024)
- [Dynamic Buffers: Cost-Efficient Planning for Tabletop Rearrangement with Stacking](https://mlsanity.com/paper/2509.22828/) (2025)

## Abstract (arXiv)

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.