University of Houston

We study scalable and efficient coordination algorithms for collaborative multi-agent systems (MAS). The coordination problem we address is coalition formation in a fully decentralized, resource-bounded setting. More specifically, we analyze, simulate and optimize the Maximal Clique based Distributed Coalition Formation (MCDCF) algorithm .In this thesis we verified the theoretical claims made by the core MCDCF algorithm. Based on the simulation experiments we made design changes and improvements to the core MCDCF. One of the improvements was to add a tie breaking mechanism which addresses how an agent that is modifying its coalition choices due to a lack of consensus in the prior rounds moves down the lattice of subsets of its neighborhood list to get new coalitions. The criteria that determine whether and when is an agent to be forced to change its coalition choice in the original version of MCDCF slowed down the convergence rate of the algorithm. In the thesis using a new criteria we improved the convergence rate of the algorithm.

This thesis also reports our work on fully decentralized collaborative coalition formation on sparse underlying MAS topologies and outlines our experiments with various versions of optimized MCDCF on Erdos–Rényi random graphs and the Small world random graphs. We performed statistical analysis of MCDCF performance on random graphs in two scenarios. In one scenario, we studied performance when the graph density is held fixed and the total number of nodes is increased. In the second scenario, we fixed the total number of nodes but varied the graph density, that is, the average number of neighbors per node. The results of these simulations matched our theoretical claims when the graph structure was random. Finally, we briefly discuss what we have learned from our experiments and outline future work under consideration.