Ant Colony Optimization for Heterogeneous Coalition Formation and Scheduling with Multi-Skilled Robots

摘要

In this paper, 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. We propose two centralized algorithms that extend the well-known ant colony optimization metaheuristic. We compare both extensions to existing 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.