Task Partitioning for Distributed Assembly

This thesis addresses the problem of how to plan a strategy for a team of robots to cooperatively build a structure, henceforth referred to as the distributed assembly problem. The problem of distributed assembly requires a range of capabilities for successful completion of the task. These include accurate sensing and manipulation using a mobile robot, the ability to continuously adhere to precedence constraints on placements, and the ability to guarantee static stability at every stage of construction.;The fundamental contribution of this work is to propose methods to address task allocation problems in the presence of constraints on task ordering. Algorithms are presented to partition 2- and 3-D assembly tasks into separate subtasks that satisfy local and global precedence constraints between the assembly components. The objective is to achieve a partitioning that minimizes completion time by minimizing the workload imbalance between the robots, and maximizes assembly parallelization. Towards this objective four approaches are presented. The first is an approach where each robot runs a simultaneous Dijkstra's Algorithm with its own root. The second approach incorporates online workload balancing and error correction by adding a communication scheme and a scanning robot equipped with a visual depth sensor. The third approach addresses the task partitioning using an algorithm inspired by Ant Colony Optimization. Finally, the problem of cooperative manipulation for tasks that require close coordination is addressed. All approaches are tested in both simulation and experiment.