Vidal's library
Title: Methods for Task Allocation via Agent Coalition Formation
Author: Onn Shehory and Sarit Kraus
Journal: Artificial Intelligence
Volume: 101
Number: 1-2
Pages: 165--200
Month: May
Year: 1998
Abstract: Task execution in multi-agent environments may require cooperation among agents. Given a set of agents and a set of tasks which they have to satisfy, we consider situations where each task should be attached to a group of agents that will perform the task. Task allocation to groups of agents is necessary when tasks cannot be performed by a single agent. However it may also be beneficial when groups perform more efficiently with respect to the single agents' performance. In this paper we present several solutions to the problem of task allocation among autonomous agents, and suggest that the agents form coalitions in order to perform tasks or improve the efficiency of their performance. We present efficient distributed algorithms with low ratio bounds and with low computational complexities. These properties are proven theoretically and supported by simulations and an implementation in an agent system. Our methods are based on both the algorithmic aspects of combinatorics and approximation algorithms for NP-hard problems. We first present an approach to agent coalition formation where each agent must be a member of only one coalition. Next, we present the domain of overlapping coalitions. We proceed with a discussion of the domain where tasks may have a precedence order. Finally, we discuss the case of implementation in an open, dynamic agent system. For each case we provide an algorithm that will lead agents to the formation of coalitions, where each coalition is assigned a task. Our algorithms are any-time algorithms, they are simple, efficient and easy to implement.

Cited by 224  -  Google Scholar

@Article{	  shehory98a,
  author =	 {Onn Shehory and Sarit Kraus},
  title =	 {Methods for Task Allocation via Agent Coalition
                  Formation},
  googleid =	 {Wo06V_P7nWsJ:scholar.google.com/},
  journal =	 {Artificial Intelligence},
  year =	 1998,
  volume =	 101,
  number =	 {1-2},
  pages =	 {165--200},
  month =	 {May},
  abstract =	 {Task execution in multi-agent environments may
                  require cooperation among agents. Given a set of
                  agents and a set of tasks which they have to
                  satisfy, we consider situations where each task
                  should be attached to a group of agents that will
                  perform the task. Task allocation to groups of
                  agents is necessary when tasks cannot be performed
                  by a single agent. However it may also be beneficial
                  when groups perform more efficiently with respect to
                  the single agents' performance. In this paper we
                  present several solutions to the problem of task
                  allocation among autonomous agents, and suggest that
                  the agents form coalitions in order to perform tasks
                  or improve the efficiency of their performance. We
                  present efficient distributed algorithms with low
                  ratio bounds and with low computational
                  complexities. These properties are proven
                  theoretically and supported by simulations and an
                  implementation in an agent system. Our methods are
                  based on both the algorithmic aspects of
                  combinatorics and approximation algorithms for
                  NP-hard problems. We first present an approach to
                  agent coalition formation where each agent must be a
                  member of only one coalition. Next, we present the
                  domain of overlapping coalitions. We proceed with a
                  discussion of the domain where tasks may have a
                  precedence order. Finally, we discuss the case of
                  implementation in an open, dynamic agent system. For
                  each case we provide an algorithm that will lead
                  agents to the formation of coalitions, where each
                  coalition is assigned a task. Our algorithms are
                  any-time algorithms, they are simple, efficient and
                  easy to implement. },
  keywords =     {multiagent coalitions},
  comment =	 {Gives a greedy-style algorithm, mostly based on a
                  classic set covering (partitioning) algorithm, for
                  coalition formation, which is the same as task
                  allocation. The algorithm only considers coalition
                  of size $k$ or smaller. They also study overlapping
                  coalitions. Algorithms are anytime.},
  url =		 {http://jmvidal.cse.sc.edu/library/shehory98a.pdf},
  created =	 1001877526,
  cluster = 	 {7754631155960941914}
}
Last modified: Wed Mar 9 10:14:25 EST 2011