A Formal Analysis and Taxonomy of Task Allocation in Multi-Robot Systems

By Brian P. Gerkey, Maja J. Mataric. 2004

1,858 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Industrial and Manufacturing Engineering, Mechanical Engineering

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Industrial and Manufacturing Engineering

In Mechanical Engineering

Citations in the corpus

Learning to Communicate to Solve Riddles with Deep Distributed Recurrent Q-Networks (2016, background): “Such problems arise naturally in a variety of settings, such as multi-robot systems and sensor networks (Matari, 1997; Fox et al., 2000; Gerkey & Matari, 2004; Olfati-Saber et al., 2007; Cao et al., 2013).”
A comprehensive taxonomy for multi-robot task allocation (2013, methodology): “As described previously (Gerkey and Matarić, 2004), it can be represented by the linear assignment problem (Votaw and Orden, 1952) from the combinatorial optimization literature: Maximize ∑ i∈N ∑ j∈M uijxij (6) Subject to: ∑ i∈N xij = 1 ∀i ∈ N ∑ j∈M xij = 1 ∀j ∈ M xij ∈ {0, 1} (7) where N is the…”
Distributed Intelligence: Overview of the Field and Its Application in Multi-Robot Systems (2008, background): “The general task allocation problem is known to be NP-hard (Gerkey & Matari´c 2004), meaning that optimal solutions cannot be found quickly for large problems.”
Swarm Robotics: Past, Present, and Future (2021, background): “A complex task is made of several subtasks that might require cooperation and that have mutual dependencies and time constraints [66], [67].”
Consensus-Based Decentralized Auctions for Robust Task Allocation (2009, methodology): “Auction algorithms [26]–[29] are another method for task assignment that have been shown to efficiently produce suboptimal solutions [30].”
A Survey and Analysis of Multi-Robot Coordination (2013, neutral): “[107] [15] gave a formal analysis and domain-independent taxonomy of MRTA problems, in which the MRTA problems have been classified into seven categories according to the ability of the robot to perform tasks, the number of robots required for a task, and the manner of the task assignment.”
Market-Based Multirobot Coordination: A Survey and Analysis (2006, methodology): “Gerkey and Mataric ´ [ 6 ] provide a taxonomy for some variants of the task allocation problem, distinguishing between: single-task (ST) and multitask (MT) robots; single-robot (SR) and multirobot (MR) tasks; and instantaneous (IA) and time-extended (TA) assignment.”
Multi-robot coalition formation (2006, background): “This paper addresses the more difficult multiple robot-multiple task problem (MR-MT) [10] where the objective is to assign a robot team to a task so that the system's overall utility is maximized.”