Ant Colony Optimization for Online Planning of Heterogeneous Multi-Agent Systems
Abstract: In this thesis, I tackle the problem of task scheduling in heterogeneous multi-robot systems. In our setting, tasks require diverse skills to be completed; 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. I propose two centralized algorithms that extend the well-known ant colony optimization (ACO) metaheuristic to solve the offline scheduling problem. These algorithms are called Territorial Ant Colony Optimization (TACO) and Swarm Ant System (SAS). We compare both algorithms to two existing methods: an optimal, but not scalable, formulation based on mixed-integer linear programming, and a scalable, but suboptimal, greedy algorithm. Our experiments show that both TACO and SAS can produce solutions up to twice as efficient as the greedy baseline at scales that are intractable to solve with the MILP approach. Additionally, I present an extension of SAS to address online replanning caused by a dynamic environment. This extension is called Pheromone-Augmentation SAS (PA-SAS). Experimental results show this method allocates tasks up to 20% more efficiently than a greedy baseline. To conclude this work, I present an extended problem formulation that considers stochastic skill degradation, ultimately leading to skill failure, and discuss the potential broader impacts of this work.