信任和效用关系约束的联盟结构生成

联盟结构生成是分布式人工智能的重要研究内容,一般仅依据智能体效用生成任意数量的联盟,这导致最优联盟结构生成的计算复杂度NP难.实际上,信任是合作的基础,信任关系对最终效用有直接的影响,应该综合考虑信任和效用关系.针对以上问题,该文扩展效用约束为信任和效用约束,用信任和效用二元组表示,以此作为联盟结构生成的依据.借鉴图割...

Coalition Structure Generation Constrained by Trust and Utility Relationship

The coalition structure generation is an important domain of distributed artificial intelligence. Most coalition formation models are only based on the utility, and any number of coalitions are permitted, which makes it be NP complexity difficult to generate the optimal coalition structure. Actually, Trust is the base of cooperation and has direct effect on the final utility. So, not only utility but also trust relationship should be seriously considered. To this end, the utility constraint is extended to trust and utility constraint, a two-tuples is used to represent utility and trust, which is the base of coalition structure generation. Inspired by the classic s-t-cut algorithm for graph cut, coalition structure generation constrained by trust and utility relationship is investigated. Assuming that individual rationality of agents and the stability of coalition (there is no block) is satisfied, the network is cut by the relationship of utility and trust to formation coalitions. The proposed algorithms of coalition structure generation named MT-s-t-cut and MTU-s-t-cut (Trust s-t-cut) can output the optimal coalition structure in polynomial time. The results of simulated experiments show that the social utility increases with the number of agents, and the running time of the algorithms are far less than that of Dynamic Programming (DP) and Optimal Dynamic Programming and Integer Partition (ODP-IP) algorithms.