A Self-Organized Algorithm for Distributed Task Allocation in Complex Scenarios..

Abstract

This paper addresses distributed task allocation in complex scenarios modeled using the distributed constraint optimization problem (DCOP) formalism. We see a complex scenario in distributed task alloca- tion as the one in which small instances formalized as a DCOP generate large problems with exponentially growing parameters. Such scenarios are becoming more and more ubiquitous in real-world applications. We propose and evaluate a novel self-organized algorithm for distributed task allocation based on theoretical models of division of labor in social insect colonies, called Swarm-GAP. Our algorithm uses a probabilistic decision model, based on the social insects tendency of performing certain tasks. Swarm-GAP was experimented in an abstract centralized simulation en- vironment. We show that Swarm-GAP achieves similar results as other recent proposed algorithm with a dramatic reduction in communication and computation. Thus, our approach is highly scalable regarding both the number of agents and tasks.