多智能体联盟形成算法的探讨与研究

Agents联盟形成是分布人工智能DAI中一种重要的协作方法.本文简要分析了Agents联盟的结构、形式以及联盟结构问题的数学模型.对于可分解的任务,且子任务之间没有优先关系,Agents要形成多个联盟(联盟结构),文中研究了基于遗传算法的联盟结构形成算法,并对这种算法的并行化作了探讨.     

面向任务的重叠联盟结构生成计算复杂性

传统的重叠联盟形成问题大都聚焦智能体, 鲜有从任务视角出发. 为此, 本文首先构建了一种面向任务的 重叠联盟结构生成模型, 并分析了其解空间和相关决策问题的计算复杂性. 此外, 基于流网络分别设计了相应的孤 立联盟、重叠联盟、重叠联盟结构成功性判别算法和最优重叠联盟结构生成算法. 分析结果表明, 判别孤立联 盟、重叠联盟、重叠联盟结构的成功性的时间复杂度均与智能体数和任务数呈多项式关系, 而搜索最优重叠联盟结 构的时间复杂度与智能体数和任务数呈指数关系. 最后, 通过仿真实验验证了上述结果.     

基于遗传算法的多智能体联盟形成机制

针对动态开放式多智能体系统中联盟的形成问题,提出“按能力分配”的联盟报酬划分规则和联盟报酬率等概念及相关命题,讨论Agent之间的协商机制和协商原则,在此基础上建立基于多智能体遗传算法的联盟形成机制。仿真计算结果表明,该联盟形成机制能够减少系统的通信量,保证所得联盟的稳定性和全局最优性,提高系统的结盟效率。     

Agent long-term coalition credit

Agent trust researches become more and more important because they will ensure good interactions among the software agents in large-scale open systems. Moreover, individual agents often interact with long-term coalitions such as some E-commerce web sites. So the agents should choose a coalition based on utility and trust. Unfortunately, few studies have been done on agent coalition credit and there is a need to do it in detail. To this end, a long-term coalition credit model (LCCM) is presented. Furthermore, the relationship between coalition credit and coalition payoff is also attended. LCCM consists of internal trust based on agent direct interactions and external reputation based on agent direct observation. Generalization of LCCM can be demonstrated through experiments applied in both cooperative and competitive domain environment. Experimental results show that LCCM is capable of coalition credit computation efficiently and can properly reflect various factors effect on coalition credit. Another important advantage that is a useful and basic property of credit is that LCCM can effectively filter inaccurate or lying information among interactions.     

基于强化学习的多任务联盟并行形成策略

Agent coalition is an important manner of agents' coordination and cooperation. Forming a coalition, agents can enhance their ability to solve problems and obtain more utilities. In this paper, a novel multi-task coalition parallel formation strategy is presented, and the conclusion that the process of multi-task coalition formation is a Markov decision process is testified theoretically. Moreover, reinforcement learning is used to solve agents' behavior strategy, and the process of multi-task coalition parallel formation is described. In multi-task oriented domains, the strategy can effectively and parallel form multi-task coalitions.     

An approach for community detection in social networks based on cooperative games theory

Detecting communities is of great importance in social network analysis. However it is an issue that has not yet been satisfactorily solved, despite the efforts made by interdisciplinary research communities over the past few years, because of the nature of complexity in deciding how community structures should be recognized. In this paper we propose an approach based on cooperative game theory for community detection in social networks. We regard individuals as players, and regard communities as coalitions formed by players, and model community detection problem as the formation and optimization of coalitions. Furthermore, we define coalition profile for players to indicate coalitions that players joined, the order of a coalition profile is defined as the number of coalitions in a coalition profile, and we introduce a utility function to measure preference of coalition profiles. Accordingly, we propose an algorithm to detect a coalition profile with maximal utility function values. We have implemented the algorithms developed in this study and experimental results demonstrate the effectiveness of our approaches.     

一种云间合作博弈资源提供方法

为了满足云资源消费者的需求,并有效扩展云资源的服务能力,设计基于云间合作博弈的资源联盟形成算法。以联盟总体利益最大化为目标,将多个云资源提供者间的合作行为建模为联盟博弈模型,从而得到最优联盟结构满足用户方的虚拟机实例请求;设计一种联盟的合并与分裂规则,使得最终联盟结构是稳定不变的;设计基于联盟成员贡献能力的标准化估计Banzhaf值法实现联盟总体利益的个体分割。实验结果表明,在不同虚拟机请求类型测试条件下,云联盟形成算法不仅可以确保更高的联盟总体利益,而且使利益分割更加公平,其算法执行效率也更高。     

Coalition formation mechanism in multi-agent systems based on genetic algorithms

As an important coordination and cooperation mechanism in multi-agent systems, coalition of agents exhibits some excellent characteristics and draws researchers’ attention increasingly. Cooperation formation has been a very active area of research in multi-agent systems. An efficient algorithm is needed for this topic since the numbers of the possible coalitions are exponential in the number of agents. Genetic algorithm (GA) has been widely reckoned as a useful tool for obtaining high quality and optimal solutions for a broad range of combinatorial optimization problems due to its intelligent advantages of self-organization, self-adaptation and inherent parallelism. This paper proposes a GA-based algorithm for coalition structure formation which aims at achieving goals of high performance, scalability, and fast convergence rate simultaneously. A novel 2D binary chromosome encoding approach and corresponding crossover and mutation operators are presented in this paper. Two valid parental chromosomes are certain to produce a valid offspring under the operation of the crossover operator. This improves the efficiency and shortens the running time greatly. The proposed algorithm is evaluated through a robust comparison with heuristic search algorithms. We have confirmed that our new algorithm is robust, self-adaptive and very efficient by experiments. The results of the proposed algorithm are found to be satisfactory.     

Searching for overlapping coalitions in multiple virtual organizations

Coalition formation is an active and essential component for multi-agent systems (MAS) in task-oriented domains in which tasks can be too complicated to be accomplished by a single agent with insufficient resources. By forming a coalition, agents are able to cooperate and combine resources to complete tasks that are impossible to accomplish alone within a given time bound. For example, in virtual enterprises, small and agile enterprises can provide more services and make more profits than an individual can. In many multi-task environments, especially in parallel multi-task environments, an individual abundant in resources is inclined to undertake more than one task to make more profits and participate in multiple virtual organizations (MVOs) at the same time, where every member has to decide how to allocate different parts of its resources to serve multiple different project tasks. Such overlapping property is a very intractable problem in practical decision making, and to the best of our knowledge, current coalition formation algorithms typically exclude the possibility of having overlapping coalitions, that is an agent can only be a member of one coalition at any given time, leading to waste of resources, preventing the system from efficiently allocating all agents’ resources, and limiting the scope of their applications in real-world scenarios. Indeed, overlapping coalition formation (OCF) is an important research question, because MVOs are very crucial and beneficial in parallel multi-task domains where only a few selected individuals have rare, but highly demanded, resources. With this in mind, we develop a discrete particle swarm optimization based algorithm to solve the OCF problem in MVOs, applicable for more complex virtual enterprises environments. We introduce a two-dimensional binary encoding scheme and propose a novel repairing strategy for resolving conflicts over the usage of joint resources among overlapping coalitions. With this novel strategy for cooperative conflict resolution, any invalid encoding can be adjusted into a valid one without any resource conflict. Finally, simulations are conducted to show the efficiency of the proposed algorithm.     

Sequentially optimal repeated coalition formation under uncertainty

Coalition formation is a central problem in multiagent systems research, but most models assume common knowledge of agent types. In practice, however, agents are often unsure of the types or capabilities of their potential partners, but gain information about these capabilities through repeated interaction. In this paper, we propose a novel Bayesian, model-based reinforcement learning framework for this problem, assuming that coalitions are formed (and tasks undertaken) repeatedly. Our model allows agents to refine their beliefs about the types of others as they interact within a coalition. The model also allows agents to make explicit tradeoffs between exploration (forming “new” coalitions to learn more about the types of new potential partners) and exploitation (relying on partners about which more is known), using value of information to define optimal exploration policies. Our framework effectively integrates decision making during repeated coalition formation under type uncertainty with Bayesian reinforcement learning techniques. Specifically, we present several learning algorithms to approximate the optimal Bayesian solution to the repeated coalition formation and type-learning problem, providing tractable means to ensure good sequential performance. We evaluate our algorithms in a variety of settings, showing that one method in particular exhibits consistently good performance in practice. We also demonstrate the ability of our model to facilitate knowledge transfer across different dynamic tasks.     

Distributed event-triggered generalized Nash equilibrium seeking in multi-coalition noncooperative games with coupling constraints

This paper is concerned with a multi-coalition noncooperative game with coupling equality constraints. Each coalition is a player consisted of multiple agents in noncooperative games and desire to minimize its own objective function based on local information. Each agent as actual decision maker in the same coalition is to optimize the objective function of the coalition cooperately. To seek a generalized Nash equilibrium (GNE) of the multi-coalition game, a distributed continuous-time algorithm is developed. Moreover, to further reduce the communication among agents and coalitions, an event-triggered mechanism (ETM) is introduced for the multi-coalition game. By using ETM, a novel distributed GNE seeking algorithm is proposed, where agents and coalitions are allowed to exchange estimation information with neighbors only when the triggering condition is satisfied. Remarkably, the proposed event-triggered scheme introduces internal variables to regulate its threshold dynamically, which excludes Zeno behavior. By Lyapunov analysis, it is proved that the coalitions' decision variables converge to a GNE in both algorithms. Finally, the effectiveness of the proposed methods is validated by numerical simulations.     

基于联盟构造博弈的认知无线电网络分布式多目标协作感知算法

协作感知技术可提高认知无线电网络中的频谱资源利用率,但网络节点在形成协作感知联盟的同时也不可避免地引入了额外开销,联盟内节点总希望用较少的额外能量开销达到较大的吞吐量期望.为此,文中提出了协作感知系统的多目标非线性优化问题,然后基于联盟博弈理论为该问题构建了一个不可转移支付的联盟构造博弈模型,在其核心的支付函数的设计中,采用线性加权和的方法同时考虑了节点吞吐最期望和能量消耗两个优化目标.基于该函数,提出了一种分布式多目标联盟构造算法DMCF,其核心是根据优超算子所定义的联盟的帕累托顺序,循环地对联盟进行合并和分裂操作.此外,还证明了DMCF的收敛性和最终联盟划分的稳定性.仿真实验的结果表明,DMCF可有效解决提出的多目标优化问题,与一种分布式随机联盟构造算法DRCF相比,DMCF总能使节点消耗较少能量却达到相对较大的吞吐量期望.在不同网络规模下,DMCF可获得的节点平均吞吐量期望可提升约7.5％,而节点平均能量消耗却可降低约70％.     

Non-additive multi-objective robot coalition formation

Manifold increase in the complexity of robotic tasks has mandated the use of robotic teams called coalitions that collaborate to perform complex tasks. In this scenario, the problem of allocating tasks to teams of robots (also known as the coalition formation problem) assumes significance. So far, solutions to this NP-hard problem have focused on optimizing a single utility function such as resource utilization or the number of tasks completed. We have modeled the multi-robot coalition formation problem as a multi-objective optimization problem with conflicting objectives. This paper extends our recent work in multi-objective approaches to robot coalition formation, and proposes the application of the Pareto Archived Evolution Strategy (PAES) algorithm to the coalition formation problem, resulting in more efficient solutions. Simulations were carried out to demonstrate the relative diversity in the solution sets generated by PAES as compared to previously studied methods. Experiments also demonstrate the relative scalability of PAES. Finally, three different selection strategies were implemented to choose solutions from the Pareto optimal set. Impact of the selection strategies on the final coalitions formed has been shown using Player/Stage.     

Access network synthesis game in next generation networks

In next generation communication networks, multiple access networks will coexist on a common service platform. In cases where network resource planning indicates that individual access network resources are insufficient to meet service demands, these networks can cooperate and combine their resources to form a unified network that satisfies these demands. We introduce and study the Network Synthesis game, in which individual access networks with insufficient resources form coalitions in order to satisfy service demands. The formation of stable coalitions in the core of the game is investigated, in both cases where payoffs are transferable or are attributed in proportion to the contribution of each member of the coalition. We also consider an alternative payoff allocation approach, according to the value of the well-known Shapley–Shubik, Banzhaf and Holler–Packel power indices, which represent the relative power each player has in the formation of coalitions. Using the knowledge attained from the coalition game analysis, we propose a new power index, called Popularity Power Index, which is based on the number of stable coalitions an access network would participate in if payoffs were assigned in a fair manner.     

Coalitions in coordinated multi-agent production scheduling: A computational study

This paper studies distributed production scheduling where agents control dispersed information and decentralized decision authority. Using the classical job shop scheduling model, the effects of coalition formation and local communication in an iterative auction are studied. The case is investigated where job agents are allowed to form coalitions, where coalition members share private information and resolve resource conflicts among themselves, while intercoalition communication is limited to bidding. The computational study shows that when the size, type, and timing of the coalitions are properly determined, it is possible to produce a high-quality schedule with a reasonable number of iterations. The results show further improvement in convergence and in solution quality when coalition size and update frequency increase. However, these improvements show diminishing return; thus, it is concluded that a high-quality schedule can be achieved with manageable coalition sizes and a moderate level of information sharing.     

动态约束下的联盟形成

联盟形成是多Agent系统中一种重要的合作方式。人们设计了一系列联盟形成框架,较好地解决了联盟值最大化、任务分配、组合拍卖等问题。已有关于联盟形成的研究,较多地从效用、任务等角度来考虑问题。在一些情况下,仅从这些角度考虑联盟形成是不够的,于是我们从约束的角度来研究联盟形成。首先深刻分析了联盟形成时的约束问题,采用命题逻辑来描述对Agent的约束,给出了联盟偏好语言及其语义描述;接着给出了它的一些性质;最后将动态约束下的联盟形成机制与常见的一些联盟形成机制作了对比,体现了动态约束下联盟形成机制的特点。     

Soft cooperation systems and games

A cooperative game for a set of agents establishes a fair allocation of the profit obtained for their cooperation. In order to obtain this allocation, a characteristic function is known. It establishes the profit of each coalition of agents if this coalition decides to act alone. Originally players are considered symmetric and then the allocation only depends on the characteristic function; this paper is about cooperative games with an asymmetric set of agents. We introduced cooperative games with a soft set of agents which explains those parameters determining the asymmetry among them in the cooperation. Now the characteristic function is defined not over the coalitions but over the soft coalitions, namely the profit depends not only on the formed coalition but also on the attributes considered for the players in the coalition. The best known of the allocation rules for cooperative games is the Shapley value. We propose a Shapley kind solution for soft games.     

基于溢出性原理的联盟结构生成算法

联盟结构的生成问题中由于搜索空间的联盟结构数目太大,因而搜索联盟结构的最底两层建立一个最坏情况下的边界值是必要的,边界值将最优的联盟结构限制在某个限界内,通过进一步的搜索可以在任意时间内得到一个较优值。根据联盟的溢出性质,文中提出了一种新的建立边界值的方法,即对任意不相交的联盟集合计算其上下边界的值,通过搜索特定的联盟结构集合建立最坏情况下的边界值。联盟的边界值建立以后,可以在任意时间内得到一个较优值,通过搜索剩余的联盟结构集合,可以对边界值和返回的联盟结构进一步优化。在此基础上文中提出了基于溢出性质的任意时间算法。实验结果表明,采用新的方法建立边界值,使得算法的收敛速度更快,效率更高。     

一种任一时间联盟结构生成算法

联盟形成是多Agent系统中的一个关键问题.人们寻求能极大化联盟值的总和的联盟结构,但通常情况下可能的联盟结构的数目太大,以致不允许进行穷尽搜索而找出最优解.给出了一个算法,可在最小搜索量内保证找到一个与最优解相距在一个限界内的联盟结构.然后,这个任一时间算法进一步搜索,渐进地给出越来越低的限界,并急剧地降低这个限界,在这一阶段,此算法明显地优于由Sandholm等人给出的算法.     

Combining bundle search with buyer coalition formation in electronic markets: A distributed approach through explicit negotiation

In electronic markets, both bundle search and buyer coalition formation are profitable purchasing strategies for buyers who need to buy small amount of goods and have no or limited bargaining power. In this paper, we present a distributed mechanism that allows buyers to use both purchasing strategies. The mechanism includes a heuristic bundle search algorithm and a distributed coalition formation scheme, which is based on an explicit negotiation protocol with low communication cost. The resulting coalitions are stable in the core in terms of coalition rationality. The simulation results show that this mechanism is very efficient. The resulting cost to buyers is close to the optimal cost.