Efficient Task Allocation in Large-Scale Dynamic Multiagent Systems

• Fernando dos Santos UFRGS
• Ana L. C. Bazzan UFRGS

Abstract

This paper presents an algorithm for task allocation in dynamic and large-scale multiagent systems. The algorithm, called eXtreme-Ants, is inspired in the division of labor in social insects and in the process of recruitment for cooperative transport observed in ant colonies. The performance of eXtreme-Ants is compared with two other algorithms in a domain independent simulator (yielding competitive results) and in the RoboCup-Rescue (achieving superior results than the other algorithms).

References

Ferreira, Jr., P. R., Boffo, F., and Bazzan, A. L. C. (2008). Using swarm-GAP for distributed task allocation in complex scenarios. In Jamali, N., Scerri, P., and Sugawara, T., editors, Massively Multiagent Systems, number 5043 in Lecture Notes in Artificial Intelligence, pages 107–121. Springer, Berlin.

Hölldobler, B., Stanton, R. C., and Markl, H. (1978). Recruitment and food-retrieving behavior in Novomessor (formicidae, hymenoptera). Behavioral Ecology and Sociobiology, 4(2):163–181.

Kitano, H. (2000). Robocup rescue: A grand challenge for multi-agent systems. In Proc. of the 4th International Conference on MultiAgent Systems, pages 5–12, Boston, USA. Los Alamitos, IEEE Computer Society.

Robson, S. K. and Traniello, J. F. A. (1998). Resource assessment, recruitment behavior, and organization of cooperative prey retrieval in the ant Formica schaufussi (hymenoptera: Formicidae). Journal of Insect Behavior, 11(1):1–22.

Scerri, P., Farinelli, A., Okamoto, S., and Tambe, M. (2005). Allocating tasks in extreme teams. In Dignum, F., Dignum, V., Koenig, S., Kraus, S., Singh, M. P., and Wooldridge, M., editors, Proc. of the Fourth International Joint Conference on Autonomous Agents and Multiagent Systems, pages 727–734, New York, USA. ACM Press.

Theraulaz, G., Bonabeau, E., and Deneubourg, J. (1998). Response threshold reinforcement and division of labour in insect societies. In Royal Society of London Series B Biological Sciences, volume 265, pages 327–332.