Abstract
Rearranging objects on a planar surface arises in a variety of robotic applications, such as product packaging. Using two arms can improve efficiency but introduces new computational challenges. This article studies the problem structure of object rearrangement using two arms in synchronous, monotone tabletop setups and develops an optimal mixed-integer model. It then describes an efficient and scalable algorithm, which first minimizes the cost of object transfers and then moves between objects. This is motivated by the fact that, asymptotically, object transfers dominate the cost of solutions. Moreover, a lazy strategy minimizes the number of motion planning calls and results in significant speedups. Theoretical arguments support the benefits of using two arms and indicate that synchronous execution, in which the two arms perform together either transfers or moves, introduces only a small overhead. Experiments support these claims and show that the scalable method can quickly compute solutions close to the optimal for the considered setup. Note to Practitioners -Monotone tabletop rearrangement challenges arise in a variety of automation scenarios, including product sorting or packing. Performing this task with two robotic manipulators introduces the overhead of coordinating them in the shared workspace, as well as an increase in the size of the underling search space. The objective of this work is to study the feasibility of such dual-arm solutions, providing both theoretical bounds, as well as a fast, and approximate solution. The approach leverages an effective algorithmic decomposition of the problem so as to take advantage of efficient motion planners and mixed-integer linear programming solvers. The proposed solution has been evaluated in settings that include delta robots as well as seven-degree-of-freedom (DOF) manipulators. Interesting extensions of this work correspond to studying the case of additional arms, nonmonotone, and general manipulation scenarios.