Abstract
We present a fully distributed algorithm for coalition formation among autonomous agents. The algorithm is based on two main ideas. One is a distributed computation of maximal cliques (of bounded sizes) in the underlying graph that captures the interconnection communication topology of the agents. Hence, given the current configuration of the agents, the coalitions that are formed are characterized by a high degree of connectivity, and therefore a high fault tolerance with respect to the subsequent node and/or link failures. The second idea is that each agent chooses its most preferable coalition based on how highly the agent values each such coalition in terms of the coalition members’ combined resources or capabilities. Coalitions with sufficient resources for fulfilling are preferable to the coalitions with resources that suffice only for completing less valuable tasks. We envision variants of our distributed algorithm presented herein to prove themselves useful coordination subroutines in many massively multi-agent system applications where the agents may repeatedly need to form temporary groups or coalitions of modest sizes in an efficient, online and fully distributed manner.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Avouris, N.M., Gasser, L. (eds.): Distributed Artificial Intelligence: Theory and Praxis. In: Euro. Courses Comp. & Info. Sci., vol. 5. Kluwer Academic Publ., Dordrecht (1992)
Cansever, D.H.: Incentive Control Strategies For Decision Problems With Parametric Uncertainties, Ph.D. thesis, Univ. of Illinois Urbana-Champaign (1985)
Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms. MIT Press, Cambridge (1990)
Garey, M.R., Johnson, D.S.: Computers and Intractability: a Guide to the Theory of NP-completeness. W.H. Freedman & co., New York (1979)
Jang, M., Reddy, S., Tosic, P., Chen, L., Agha, G.: An Actor-based Simulation for Studying UAV Coordination. In: Proc. 15th Euro. Symp. Simul. (ESS 2003), Delft, Holland (2003)
Jang, M., Agha, G.: On Efficient Communication and Service Agent Discovery in Multi-agent Systems. In: 3rd Int’l Workshop on Software Engineering for Large-Scale Multi-Agent Systems (SELMAS 2004), Edinburgh, Scotland, May 24-25, pp. 27–33 (2004)
Lynch, N.: Distributed Algorithms. Morgan Kaufmann Publ., Wonderland (1996)
Modi, P.J., Jung, H., Shen, W., Tambe, M., Kulkarni, S.: A dynamic distributed constraint satisfaction approach to resource allocation. In: Proc. 7th Int’l Conf. on Principles & Practice of Constraint Programming (2001)
Modi, P.J., Jung, H., Shen, W.: “Distributed Resource Allocation: Formalization, Complexity Results and Mappings to Distributed CSPs”, technical report (November 2002)
Modi, P.J., Shen, W., Tambe, M., Yokoo, M.: An asynchronous complete method for distributed constraint optimization. In: Proc. 2nd AAMAS 2003, Melbourne, Australia (2003)
Rosenschein, J., Zlotkin, G.: Rules of Encounter: Designing Conventions for Automated Negotiations among Computers. The MIT Press, Cambridge (1994)
Sandholm, T., Lesser, V.: Issues in automated negotiation and electronic commerce: Extending the contract net framework. In: 1st Int’l Conf. on Multiagent Systems, San Francisco, pp. 328–335 (1995)
Sandholm, T., Lesser, V.: Coalitions among Computationally Bounded Agents. In: Artificial Intelligence, spec. issue on “Principles of MAS” (1997)
Shehory, O., Kraus, S.: Coalition formation among autonomous agents: Strategies and complexity. In: Müller, J.P., Castelfranchi, C. (eds.) MAAMAW 1993. LNCS, vol. 957, pp. 55–72. Springer, Heidelberg (1993)
Shehory, O., Kraus, S.: Task allocation via coalition formation among autonomous agents. In: Proc. 14th IJCAI 1995, Montreal (August 1995)
Simon, H.A.: Models of Man. J. Willey & Sons, New York (1957)
Smith, R.G.: The contract net protocol: high-level communication and control in a distributed problem solver. IEEE Trans. on Computers 29(12) (1980)
Tel, G.: Introduction to Distributed Algorithms, 2nd edn. Cambridge Univ. Press, Cambridge (2000)
Tosic, P., Jang, M., Reddy, S., Chia, J., Chen, L., Agha, G.: Modeling a System of UAVs on a Mission. In: Proc. SCI 2003 (invited session), Orlando, Florida (2003)
Tosic, P., Agha, G.: Modeling Agents’ Autonomous Decision Making in Multiagent, Multitask Environments. In: Proc. 1st Euro. Workshop on MAS (EUMAS 2003), Oxford (2003)
Tosic, P., Agha, G.: Maximal Clique Based Distributed Group Formation Algorithm for Autonomous Agent Coalitions. In: Proc. Workshop on Coalitions & Teams, within AAMAS 2004, New York City, July 19-23 (2004)
For more on the TRANSIMS project at the Los Alamos National Laboratory, go to, http://www-transims.tsasa.lanl.gov/ (The ’Documents’ link includes a number of papers and technical reports for the period 1995 - 2001)
Watts, D.J.: Small Worlds: The Dynamics of Networks Between Order and Randomness. Princeton Univ. Press, Princeton (1999)
Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. Nature 393 (1998)
Weiss, G. (ed.): Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence. The MIT Press, Cambridge (1999)
Wooldridge, M., Jennings, N.: Intelligent Agents: Theory and Practice. Knowledge Engin. Rev. (1995)
Yokoo, M., Hirayama, K.: Algorithms for Distributed Constraint Satisfaction: A review. AAMAS 3(2) (2000)
Yokoo, M.: Distributed Constraint Satisfaction: Foundation of Cooperation in Multi-agent Systems. Springer, Heidelberg (2001)
Zlotkin, G., Rosenschein, J.S.: Coalition, cryptography and stability: Mechanisms for coalition formation in task oriented domains. In: Proc. AAAI 1994, Seattle, Washington (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tošić, P.T., Agha, G.A. (2005). Maximal Clique Based Distributed Coalition Formation for Task Allocation in Large-Scale Multi-agent Systems. In: Ishida, T., Gasser, L., Nakashima, H. (eds) Massively Multi-Agent Systems I. MMAS 2004. Lecture Notes in Computer Science(), vol 3446. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11512073_8
Download citation
DOI: https://doi.org/10.1007/11512073_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-26974-8
Online ISBN: 978-3-540-31889-7
eBook Packages: Computer ScienceComputer Science (R0)