Abstract:

The coalition formation process, in which a collection of agents decide how they might group together to satisfy the tasks, is one of the important aspects in multiagent systems. Although this problem has been investigated for many years, few attentions are paid to the situation where tasks have complex interdependent relationships. To address this omission, we consider the situation where there is a logical interdependent relationship between tasks,and the transfer cost associated with tasks and agents is incurred between interdependent tasks. Based on this background, we present an efficient algorithm based on the graph theory to find the optimal coalition. Considering the tasks with normalized logical interdependent relationships, we transform the problem of finding optimal coalition to the shortest path problem in the graph. We also give the time complexity analysis of the algorithm,and the experiment results show that the algorithm has good performance.

Key words: coalition formation, logical interdependent relationship, transfer cost