Name
Abstract | ||
|---|---|---|
This paper focuses on coalition formation for task allocation in both multi-agent and multi-robot domains. Two different problem formalizations are considered, one for multi-agent domains where agent resources are transferable and one for multi-robot domains. We demonstrate complexity theoretic differences between both models and show that, under both, the coalition formation problem, with m tasks, is NP-hard to both solve exactly and to approximate within a factor of $${O(m^{1-\epsilon})}$$ for all $${\epsilon 0}$$ . Two natural restrictions of the coalition formation problem are considered. In the first situation agents are drawn from a set of j types. Agents of each type are indistinguishable from one another. For this situation a dynamic programming based approach is presented, which, for fixed j finds the optimal coalition structure in polynomial time and is applicable in both multi-agent and multi-robot domains. We then consider situations where coalitions are restricted to k or fewer agents. We present two different algorithms. Each guarantees the generated solution to be within a constant factor, for fixed k, of the optimal in terms of utility. Our algorithms complement Shehory and Kraus' algorithm (Artif Intell 101(1---2):165---200, 1998), which provides guarantee's on solution cost, as ours provides guarantees on utility. Our algorithm for general multi-agent domains is a modification of and has the same running time as Shehory and Kraus' algorithm, while our approach for multi-robot domains runs in time $${O(n^{\frac{3}{2}}m)}$$ , much faster than Vig and Adams (J Intell Robot Syst 50(1):85---118, 2007) modifications to Shehory and Kraus' algorithm for multi-robot domains, which ran in time O(n k m), for n agents and m tasks. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/s10458-010-9123-8 | Autonomous Agents and Multi-Agent Systems |
Keywords | DocType | Volume |
Coalition formation,Task allocation,Multi-robot | Journal | 22 |
Issue | ISSN | Citations |
2 | 1387-2532 | 15 |
PageRank | References | Authors |
0.78 | 16 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Travis C. Service | 1 | 39 | 5.18 |
| Julie A. Adams | 2 | 392 | 53.75 |