Constrained task partitioning for distributed assembly

Abstract

We address the distributed assembly of a structure by a team of homogeneous robots. We present an algorithm to partition 2- and 3-D assembly tasks into N separate subtasks that satisfy local and global precedence constraints between the assembly components. The objective is to achieve a partitioning that minimizes the workload imbalance between the robots and maximizes assembly parallelization. The algorithm consists of three phases: 1) an initial allocation of the subtasks to each robot via a variant of Dijkstra's algorithm; 2) a component trading protocol to balance each robot's workload without violating any constraints; and 3) the creation of an assembly plan for each robot that minimizes conflicts during execution. We present simulation results for three variants of the algorithm and experiments using our multi-robot testbed.