  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 paper studies the structure
of dual-arm rearrangement for 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
of 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 points and show that the scalable method can quickly compute
solutions close to the optimal for the considered setup.
