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

Journal article (2023)

Authors

X. Bai Shenzhen University, Learning & Autonomous Control - Mechanical, Maritime and Materials Engineering
Andres Fielbaum Learning & Autonomous Control - Mechanical, Maritime and Materials Engineering
M. Kronmüller Learning & Autonomous Control - Mechanical, Maritime and Materials Engineering
L. Knödler Learning & Autonomous Control - Mechanical, Maritime and Materials Engineering
J. Alonso-Mora Learning & Autonomous Control - Mechanical, Maritime and Materials Engineering
Research Group
Learning & Autonomous Control (Mechanical, Maritime and Materials Engineering) (TU Delft)
Copyright: © 2023 X. Bai, Andres Fielbaum, M. Kronmüller, L. Knödler, J. Alonso-Mora
DOI
help_outline
https://doi.org/10.1109/TASE.2022.3175040
Optimization Robots NP-hard Collision avoidance Heuristic algorithms Distributed algorithms Robot sensing systems Task analysis Distributed auction algorithm. Multi-robot Task assignment Time-windows
More Info
expand_more

Published Date

2023

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Mechanical, Maritime and Materials Engineering

Department

Cognitive Robotics

Research Group

Learning & Autonomous Control

Abstract

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.