  Multi-robot assembly systems are becoming increasingly appealing in
manufacturing due to their ability to automatically, flexibly, and quickly
construct desired structural designs. However, effectively planning for these
systems in a manner that ensures each robot is simultaneously productive, and
not idle, is challenging due to (1) the close proximity that the robots must
operate in to manipulate the structure and (2) the inherent structural partial
orderings on when each part can be installed. In this paper, we present a task
and motion planning framework that jointly plans safe, low-makespan plans for a
team of robots to assemble complex spatial structures. Our framework takes a
hierarchical approach that, at the high level, uses Mixed-integer Linear
Programs to compute an abstract plan comprised of an allocation of robots to
tasks subject to precedence constraints and, at the low level, builds on a
state-of-the-art algorithm for Multi-Agent Path Finding to plan collision-free
robot motions that realize this abstract plan. Critical to our approach is the
inclusion of certain collision constraints and movement durations during
high-level planning, which better informs the search for abstract plans that
are likely to be both feasible and low-makespan while keeping the search
tractable. We demonstrate our planning system on several challenging assembly
domains with several (sometimes heterogeneous) robots with grippers or suction
plates for assembling structures with up to 23 objects involving Lego bricks,
bars, plates, or irregularly shaped blocks.
