Robin Glinton, Katia Sycara, Paul Scerri
Individual robots or agents will often need to form coalitions to accomplish shared tasks, e.g., in sensor networks or markets. Furthermore, in most real systems it is infeasible for entities to interact with all peers. The presence of a social network can alleviate this problem by providing a neighborhood system within which entities interact with a reduced number of peers. Previous research has shown that the topology of the underlying social network has a dramatic effect on the quality of coalitions formed and consequently on system performance. It has also been shown that it is feasible to develop agents which dynamically alter connections to improve an organization's ability to form coalitions on the network. However those studies have not analyzed the network topologies that result from connectivity adaptation strategies. In this paper the resulting network topologies were analyzed and it was found that high performance and rapid convergence were attained because scale free networks were being formed. However it was observed that organizational performance is not impacted by limiting the number of links per agent to the total number of skills available within the population, implying that bandwidth was wasted by previous approaches. We used these observations to inform the design of a token based algorithm that attains higher performance using an order of magnitude less messages for both uniform and non-uniform distributions of skills.
Subjects: 7.1 Multi-Agent Systems; 7. Distributed AI
Submitted: Apr 14, 2008