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

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. Note to Practitioners—This work presents two group-based distributed auction algorithms for a sufficiently large fleet of robots to efficiently transport a set of dynamically appearing dispersed packages from their initial locations to corresponding destinations within prescribed time-windows. Each robot can carry multiple packages simultaneously within its capacity, and the objective is to minimize the robots’ total travel time to transport all the packages within the prescribed time-windows. The paper’s practical contributions are threefold: First, the multi-robot task assignment problem is formulated through a robot-group assignment strategy, which enables complex logistic scheduling for tasks grouped according to their distributions and time-windows. Second, we theoretically show that the multi-robot task assignment problem is an NP-hard problem, which implies the necessity for designing approximate task assignment algorithms. Third, the proposed group-based distributed auction algorithms are efficient and can be adapted for real scenarios.