Afsaneh FATEMI, Kamran ZAMANIFAR, Naser NEMATBAKHSH

Capability-based task allocation in emergency-response environments: a coalition-formation approach

This paper addresses coalition formation, based on agent capabilities, centered on task allocation in emergency-response environments (EREs). EREs are environments that need fast task completion as their main requirement. We propose a team-based organization model, based on an existing organization model for adaptive complex systems. The model has some key characteristics that are beneficial for EREs: agents act in dynamic, open domains; agents collaborate in completing group tasks; agents may have similar types of capabilities, but at different levels; tasks need different agent capabilities, at collective different levels; and agents are supervised in a partially decentralized manner. We formulate task allocation as a capability-based coalition-formation problem, propose a greedy myopic algorithm to form coalitions, and compare it with F-Max-Sum, another efficient myopic algorithm. Experiments in which utility is measured show that the capability-based approach outperforms the role-based one. The numerical experiments suggest that the proposed task allocation method is possibly scalable with growing numbers of agents.

Anahtar Kelimeler:

Coalition formation, emergency-response environment, task allocation, team-based organization, capability-based task allocation

Capability-based task allocation in emergency-response environments: a coalition-formation approach

Keywords:

Coalition formation, emergency-response environment, task allocation, team-based organization, capability-based task allocation,

PDF

___

A. Campbell, A.S. Wu, “Multi-agent role allocation: issues, approaches, and multiple perspectives”, Autonomous Agents and Multi-Agent Systems, Vol. 22, pp. 317–355, 2011.
P.R. Ferreira, F.D. Santos, A.L. Bazzan, D. Epstein, S.J. Waskow, “RoboCup rescue as multiagent task allocation among teams: experiments with task interdependencies”, Autonomous Agents and Multi-Agent Systems, Vol. 20, pp. 421–443, 2010.
X. Zheng, S. Koenig, “Reaction functions for task allocation to cooperative agents”, Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems, Vol. 2, pp. 559–566, 2008.
F.D. Santos, A.L. Bazzan, “Towards efficient multiagent task allocation in the RoboCup rescue: a biologicallyinspired approach”, Autonomous Agents and Multi-Agent Systems, Vol. 22, pp. 465–486, 2011.
P. Scerri, A. Farinelli, S. Okamoto, M. Tambe, “Allocating tasks in extreme teams”, Proceedings of the 4th International Joint Conference on Autonomous Agents and Multiagent Systems, pp. 727–734, 2005.
S.D. Ramchurn, A. Farinelli, K.S. Macarthur, N.R. Jennings, “Decentralized coordination in RoboCup rescue”, The Computer Journal, Vol. 53, pp. 1–15, 2010.
S.A. DeLoach, “OMACS: a framework for adaptive, complex systems”, In: V. Dignum, Ed., Multi-Agent Systems: Semantics and Dynamics of Organizational Models, Hershey, PA, USA, IGI Global, 2009.
M. Ghijsen, W. Jansweijer, B. Wielinga, “Towards a framework for agent coordination and reorganization, AgentCoRe”, Proceedings of the International Conference on Coordination, Organizations, Institutions, and Norms in Agent Systems III, pp. 1–14, 2008.
R. Kota, N. Gibbins, N.R. Jennings, “Decentralised structural adaptation in agent organisations”, Proceedings of the AAMAS Workshop on Organized Adaptation in Multi-Agent Systems, Estoril, Portugal, pp. 54–71, 2008. M. Schwaninger, Intelligent Organizations: Powerful Models for Systemic Management, 2nd ed., Berlin, Springer, 200
A. Fatemi, K. Zamanifar, N. Nematbakhsh, O. Askari, “A team-based organizational model for adaptive multi-agent systems”, Proceedings of the 3rd International Conference on Agents and Artificial Intelligence, Vol. 2, pp. 469–472, 20 H. Mintzberg, Structures in Five: Designing Effective Organizations, 1st ed., Hoboken, NJ, USA, Prentice Hall, 19 S.D. Ramchurn, M. Polukarov, A. Farinelli, C. Truong, N.R. Jennings, “Coalition formation with spatial and temporal constraints”, Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems, Vol. 3, pp. 1181–1188, 2010.
T.C. Service, J.A. Adams, “Coalition formation for task allocation: theory and algorithms”, Autonomous Agents and Multi-Agent Systems, Vol. 22, pp. 225–248, 2011.
S.N. Givigi, H.M. Schwartz, “Swarm robot systems based on the evolution of personality traits”, Turkish Journal of Electrical Engineering and Computer Sciences, Vol. 15, pp. 257–282, 2007.
F. Bellifemine, G. Caire, A. Poggi, G. Rimassa, “JADE: A software framework for developing multi-agent applications, lessons learned”, Information and Software Technology, Vol. 50, pp. 10–21, 2008.
A. Farinelli, A. Rogers, A. Petcu, N.R. Jennings, “Decentralised coordination of low-power embedded devices using the Max-Sum algorithm”, Proceedings of the 7th International Conference on Autonomous Agents and Multi-Agent Systems, pp. 639–646, 2008.
M. Ghijsen, W. Jansweijer, B. Wielinga, “Adaptive hierarchical multi-agent organizations”, Interactive Collaborative Information Systems, Studies in Computational Intelligence, Vol. 281, pp. 375–400, 2010.