Coalition formation for task allocation: theory and algorithms
This paper focuses on coalition formation for task allocation in both multiagent 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(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.
coalition formation task allocation multi-robot