Coalition Formation and Scheduling for Heterogeneous Robot Swarms with Ant Colony Optimization

Babincsak, William

Student Work

Coalition Formation and Scheduling for Heterogeneous Robot Swarms with Ant Colony Optimization

Public Deposited

In this work, we tackle the problem of task scheduling in heterogeneous multi-robot systems. In our setting, the tasks require diverse skills to be fulfilled; however, the robots offer some, but not all, of the required skills. Thus, the robots must construct individual schedules that allow coalitions, i.e., dedicated teams, to be formed and disbanded dynamically. This results in cross-schedule dependencies that make generating high-quality solutions difficult, especially as the number of robots, skills, and tasks grows. First, we explore the multi-robot scheduling problem without coalition constraints. This is equivalent to a multiple traveling salesman problem (MTSP). We present a novel ant colony optimization (ACO) solution to the MTSP we call Territorial Ant Colony Optimization (TACO) that outperforms other state-of-the-art metaheuristics on the MTSP. We then extend this method to the MTSP with coalition constraints, which we term the Collab-MTSP. We call the extended method Deadlock Reversal TACO (DR-TACO). In addition to DR-TACO, we present an alternative ACO-based method for the Collab-MTSP we call Swarm Ant System (SAS). We compare both DR-TACO and SAS to baseline methods: (i) an optimal, but not scalable, formulation based on mixed-integer linear programming, and (ii) a scalable, but suboptimal, greedy algorithm. Our experiments show that our algorithms can produce solutions with costs as low as 0.5x those of the greedy algorithm at scales that are intractable to solve with the MILP baseline. Each method represents a step forward in quickly solving difficult, time-extend task allocation problems with cross-schedule dependencies.

This report represents the work of one or more WPI undergraduate students submitted to the faculty as evidence of completion of a degree requirement. WPI routinely publishes these reports on its website without editorial or peer review.

Creator