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

Research output: Contribution to journalArticleScientificpeer-review

2 Citations (Scopus)

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.

Original languageEnglish
Number of pages12
JournalIEEE Transactions on Automation Science and Engineering
DOIs
Publication statusAccepted/In press - 25 May 2022

Keywords

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

Fingerprint

Dive into the research topics of 'Group-Based Distributed Auction Algorithms for Multi-Robot Task Assignment'. Together they form a unique fingerprint.

Cite this