Software agents situated in the same environment typically need to interact with one ather in order to fulfill their objectives or improve their performance. Coalition formation is a fundamental form of interaction that has proven to be useful in a number of scenarios, including: sensor networks e-commerce distributed vehicle routing Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining which of the potential coalitions to form in order to achieve some goal. This usually requires calculating a value for every coalition, kwn as the coalition value, which indicates how beneficial that coalition would be if it was formed. Once these values are calculated, the agents need to find a combination of coalitions of which the sum of values is maximized, and in which every agent belongs to exactly one coalition. Finding an optimal, or near-optimal, solution to this coalition structure generation problem is extremely challenging due to the large number of possible solutions. To date, many algorithms have been proposed to solve this problem using different techniques - ranging from dynamic programming, to integer programming, to stochastic search - all of which suffer from major limitations relating to execution time, solution quality, and memory requirements. Against this background, this thesis presents a vel algorithm for distributing the coalition-value calculations among the agents. The algorithm is decentralized, requires communication between the agents, has minimal memory requirements, and can reflect variations in the computational speeds of the agents. We also develop an anytime algorithm for coalition structure generation. By using a vel representation of the search space, and applying branch-and-bound techniques, the algorithm is shown to significantly outperform other existing ones in the literature.
Talal Rahwan is a research fellow at the School of Electronics & Computer Science, University of Southampton where he was originally awarded an Overseas Research Scholarship to do his Ph.D, after graduating in 2003 from the University of Aleppo, Syria. His research has been published in premium artificial intelligence conferences and journals.