Simultaneous Task Scheduling and Coalition Formation in Multi-robot Systems Using Centralized and Decentralized Methods
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 (WPI)
Committee: Professor Kevin Leahy (WPI); Guanrui Li (WPI); and Professor Emanuele Garone (Université libre de Bruxelles)
Zoom: Zoom meeting has ended.