Tabletop Object Rearrangement: Structure, Complexity, and Efficient Combinatorial Search-Based Solutions

This thesis aims to provide a complete structural analysis and efficient algorithmic solutions to tabletop object rearrangement with overhand grasps (TORO). This problem captures a common task that we solve on a daily basis and is essential in enabling truly intelligent robotic manipulation. When rearranging many objects in a confined workspace, on the one hand, action sequencing with the least pick-n-places in TORO is NP-hard[han2018complexity]; on the other hand, temporarily relocating objects to some free space ("buffer poses") may be necessary but highly challenging in a cluttered environment. Focusing on these two challenges, the thesis covers TORO in four different setups, including varied workspace assumptions (with/without external buffers) and manipulator settings (single/dual-arms or a mobile manipulator). The thesis first explores TORO with external buffers (TORE), addressing the size of needed space for temporary object relocation ("running buffers"). This study shows that finding the maximum running buffers (MRB) is NP-hard and that MRB can grow unbounded with an increasing number of objects, even with uniform shapes. Exact algorithms developed for both labeled and unlabeled settings can scale to over 100 objects. The thesis further extends the TORE algorithms to tabletop rearrangement with internal buffers (TORI), where all temporary object placements need to be inside the workspace.