Group-Based Distributed Auction Algorithms for Multi-Robot Task Assignment

Group-Based Distributed Auction Algorithms for Multi-Robot Task Assignment

Bai, X. (TU Delft Learning & Autonomous Control; Shenzhen University)
Fielbaum, Andres (TU Delft Learning & Autonomous Control)
Kronmüller, M. (TU Delft Learning & Autonomous Control)
Knödler, L. (TU Delft Learning & Autonomous Control)
Alonso Mora, J. (TU Delft Learning & Autonomous Control)

2023

This paper studies the multi-robot task assignment problem in which a fleet of dispersed robots needs to efficiently transport a set of dynamically appearing packages from their initial locations to corresponding destinations within prescribed time-windows. Each robot can carry multiple packages simultaneously within its capacity. Given a sufficiently large robot fleet, the objective is to minimize the robots' total travel time to transport the packages within their respective time-window constraints. The problem is shown to be NP-hard, and we design two group-based distributed auction algorithms to solve this task assignment problem. Guided by the auction algorithms, robots first distributively calculate feasible package groups that they can serve, and then communicate to find an assignment of package groups. We quantify the potential of the algorithms with respect to the number of employed robots and the capacity of the robots by considering the robots' total travel time to transport all packages. Simulation results show that the designed algorithms are competitive compared with an exact centralized Integer Linear Program representation solved with the commercial solver Gurobi, and superior to popular greedy algorithms and a heuristic distributed task allocation method.

Collision avoidance
Distributed algorithms
distributed auction algorithm.
Heuristic algorithms
Multi-robot
NP-hard
Optimization
Robot sensing systems
Robots
Task analysis
task assignment
time-windows

http://resolver.tudelft.nl/uuid:32f3fba2-e81b-48e9-9381-4e71ea00d4ba

https://doi.org/10.1109/TASE.2022.3175040

2022-11-25

1545-5955

IEEE Transactions on Automation Science and Engineering, 20 (2), 1292-1303

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-care Otherwise 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.

Institutional Repository

journal article

© 2023 X. Bai, Andres Fielbaum, M. Kronmüller, L. Knödler, J. Alonso Mora