Abstract
We study the problem of selecting a fleet of robots to service spatially distributed tasks with diverse requirements within time-windows. The problem of allocating tasks to a fleet of potentially heterogeneous robots and finding an optimal sequence for each robot is known as multi-robot task assignment (MRTA). Most state-of-the-art methods focus on the problem when the fleet of robots is fixed. In contrast, we consider that we are given a set of available robot types and requested tasks, and need to assemble a fleet that optimally services the tasks while the cost of the fleet remains under a budget limit. We characterize the complexity of the problem and provide a Mixed-Integer Linear Program (MILP) formulation. Due to poor scalability of the MILP, we propose a heuristic solution based on a Large Neighbourhood Search (LNS). In simulations, we demonstrate that the proposed method requires substantially lower budgets than a greedy algorithm to service all tasks.
Original language | English |
---|---|
Title of host publication | Proceedings of the International Symposium on Multi-Robot and Multi-Agent Systems (MRS) |
Publisher | IEEE |
Pages | 156-162 |
Number of pages | 7 |
ISBN (Print) | 979-8-3503-7076-8 |
DOIs | |
Publication status | Published - 2024 |
Event | International Symposium on Multi-Robot and Multi-Agent Systems (MRS) - Boston, United States Duration: 4 Dec 2023 → 5 Dec 2023 |
Conference
Conference | International Symposium on Multi-Robot and Multi-Agent Systems (MRS) |
---|---|
Country/Territory | United States |
City | Boston |
Period | 4/12/23 → 5/12/23 |
Bibliographical note
Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-careOtherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.