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[1]; 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 algorithmsdeveloped 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. A two-step baseline planner is developed, generating a primitive plan based on object-object collisions and selecting buffer locations. Using a “lazy” planner within a bi-directionaltree search framework, the method efficiently produces robust, high-quality solutions in simulations, outperforming existing approaches for large-scale problems. The thesis later explores lazy buffer verification for dual-arm task planning in non-monotone rearrangement tasks. Handling complex dependencies often requires moving objects multiple times and coordinating hand-offs between two arms in a shared workspace. Our task planning algorithms effectively sequence and distribute pick-and-place tasks,yielding significant time savings over greedy or single-robot approaches. For motion planning, we introduce a tightly integrated pipeline that combines novel sampling methods with advanced trajectory optimization. The proposed planner achieves superior execution times and trajectory compliance with acceleration and jerk constraints, advancing coordinationin dual-arm systems. Finally, the thesis incorporates lazy buffer verification into an A* framework (ORLA*) for time-optimal multi-object rearrangement in mobile robot tabletop setups. The proposed method applies delayed evaluation to optimize object pick-and-place sequences, factoring in both end-effector and robot base movements. With learning-based stability predictions,ORLA* can handle complex, multi-layered rearrangement tasks. Extensive simulations and ablation studies validate ORLA* ’s effectiveness, providing high-quality solutions for challenging rearrangement scenarios.