Research Of Transitive Dependence Based Coalition Formation In MAS

Socially intelligent agents are autonomous problem solvers that have to achieve their objectives by interacting with other similarly autonomous entities. Social reasoning mechanisms have been successfully used to design and build such intelligent agents. Dependence relations allow an agent to know which of its goals are achievable and which of its plans are feasible at any moment. Coalition formation methods allow autonomous agents to join together in order to act as a coherent group in which they increase their individual gains by collaborating with each other. Dependence relations have been believed to be the foundation of coalition formation.The work has investigated transitive dependence theory and transitive dependence based coalition formation, and the main tasks and contributions of the work include:(1) This work proposes a formal theory of direct dependence in MAS. From the perspective of dependence property, direct dependence relations are classified into strong dependence and weak dependence. In order to differentiate dependence relations in a quantitative way, this research gives a definition of dependence degree, which is used to define dependence intensity. Dependence degree is a quantitative characteristic of dependence relations, which can be used in quantitative social reasoning.(2) The transitive dependence is an important and useful phenomenon in the field of multi-agent systems, but it's ignored in the related work. To meet this gap, this work identifies, defines and models a novel dependence relationship called transitive dependence relation. It extends the related research work on dependence based social reasoning by considering transitivity in dependence relations. Transitive dependence helps to agents' representing and reasoning social relations in MAS. Moreover, transitive dependency can help agents to reach a goal faster with less cost since agents are goal oriented.(3) Based on the novel social reasoning theory namely transitive dependence theory, this work proposes two dynamic coalition formation algorithms for coalition formation: 1) without and-action dependence and 2) with and-action dependence respectively. This paper doesn't address the problem of finding the optimal division of agents into coalitions such that the total of the payoffs to all the coalitions is maximized, but aims to propose efficient coalition formation algorithms for specific goals pursuit. When there is no and-action dependence, the proposed algorithm is of polynomial...