Task Allocation and Simultaneous Coalition Formation in Multi-robot Systems Using Centralized and Decentralized Methods
Abstract: Heterogeneous multi-robot systems enable complex missions that involve tasks requiring diverse skills and interdependent actions. Potential applications include space exploration, construction, underwater and subterranean operations, and nano-surgery. In this thesis, I focus on a general and rarely studied variant of task allocation in which tasks require the dynamic formation of dedicated teams (coalitions) of heterogeneous robots. In particular, I tackle the problem of simultaneously forming these coalitions, while creating an individual task schedule for each robot. My work encompasses both centralized and decentralized approaches. I will present an optimal centralized solver based on mixed-integer linear programming, a massively scalable heuristic centralized solver, and two decentralized algorithms that ensure deadlock-free schedules while enabling robots to collaborate independently. I conducted extensive evaluations to validate the scalability and effectiveness of these approaches across various scenarios, including extreme task demands, clustered task locations, and large-scale problems.
Advisor: Professor Carlo Pinciroli
Committee: Professor Emanuele Garone, Professor Kevin Leahy, Professor Guanrui Li
Zoom Link: https://wpi.zoom.us/j/96648979605