Graphics enhanced version of this site

Methods for task allocation via agent coalition formation
O. Shehory and S. Kraus
Artificial Intelligence, Vol. 101, No. 1-2, May, 1998, pp. 165-200.

Jump to: Download | Abstract | Notes | Text Reference | BibTeX Reference

Adobe portable document format (pdf) [342 KB]
Compressed postscript (ps.gz) [129 KB]

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

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.

Number of pages: 36

O. Shehory and S. Kraus, "Methods for task allocation via agent coalition formation," Artificial Intelligence, Vol. 101, No. 1-2, May, 1998, pp. 165-200.

@article{Shehory_1998_2126,
   author = "Onn Shehory and Sarit Kraus",
   title = "Methods for task allocation via agent coalition formation",
   journal = "Artificial Intelligence",
   month = "May",
   year = "1998",
   volume = "101",
   number = "1-2",
   pages = "165-200"
}