Multi-robot coalition formation

As the community strives towards autonomous multi-robot systems, there is a need for these systems to autonomously form coalitions to complete assigned missions. Numerous coalition formation algorithms have been proposed in the software agent literature. Algorithms exist that form agent coalitions in both super additive and non-super additive environments. The algorithmic techniques vary from negotiation-based protocols in multi-agent system (MAS) environments to those based on computation in distributed problem solving (DPS) environments. Coalition formation behaviors have also been discussed in relation to game theory. Despite the plethora of MAS coalition formation literature, to the best of our knowledge none of the proposed algorithms have been demonstrated with an actual multi-robot system. There exists a discrepancy between the multi-agent algorithms and their applicability to the multi-robot domain. This paper aims to bridge that discrepancy by unearthing the issues that arise while attempting to tailor these algorithms to the multi-robot domain. A well-known multi-agent coalition formation algorithm has been studied in order to identify the necessary modifications to facilitate its application to the multi-robot domain. This paper reports multi-robot coalition formation results based upon simulation and actual robot experiments. A multi-agent coalition formation algorithm has been demonstrated on an actual robot system.     

单调重叠联盟下的最优联盟结构生成

针对重叠联盟的合作博弈框架（OCF games）中重叠联盟结构生成（OCSG）求解困难的问题,提出了一种基于贪心方法的有效算法。首先使用了一种带有联盟数量k约束的OCF博弈（kOCF games）模型来限制OCSG问题的规模;然后引入了一种相似度量来表示任意两个联盟结构之间的相似程度,并基于相似度量定义了单调性的性质,这意味着某一联盟结构与最优联盟结构的相似度越高,该联盟的单调性的值就越大;最后对于具有单调性质的kOCF博弈,采用了逐一插入玩家编号以逼近最优联盟结构的方法设计了联盟约束贪心（CCG）算法来求解给定的OCSG问题,并在理论上证明了CCG算法的复杂度是O（n2^k+1）。通过实验分析和验证了不同参数和联盟值分布对所提算法性能的影响,并把该算法与Zick等提出的算法（ZICK Y,CHALKIADAKIS G,ELKIND E,et al. Cooperative games with overlapping coalitions： charting the tractability frontier. Artificial Intelligence,2019,271：74-97）在约束条件等方面进行了对比,得出了当联盟最大数量k被常数约束时所提算法的搜索次数随agent的个数基本呈线性增长的结果。可见CCG算法是固定参数k可解的,而且拥有更好的适用性。     

Hedonic coalition formation for optimal deployment

This paper presents a distributed algorithmic solution, termed Coalition formation and deployment algorithm , to achieve network configurations where agents cluster into coincident groups that are distributed optimally over the environment. The motivation for this problem comes from spatial estimation tasks executed with unreliable sensors. We propose a probabilistic strategy that combines a repeated game governing the formation of coalitions with a spatial motion component governing their location. For a class of probabilistic coalition switching laws, we establish the convergence of the agents to coincident groups of a desired size in finite time and the asymptotic convergence of the overall network to the optimal deployment, both with probability 1. We also investigate the algorithm’s time and communication complexity. Specifically, we upper bound the expected completion time of executions that use the proportional-to-number-of-unmatched-agents coalition switching law under arbitrary and complete communication topologies. We also upper bound the number of messages required per timestep to execute our strategy. The proposed algorithm is robust to agent addition and subtraction. From a coalitional game perspective, the algorithm is novel in that the players’ information is limited to the neighboring clusters. From a motion coordination perspective, the algorithm is novel because it brings together the basic tasks of rendezvous (individual agents into clusters) and deployment (clusters in the environment). Simulations illustrate the correctness, robustness, and complexity results.     

Multi-robot coalition formation in real-time scenarios

Task allocation is one of the main issues to be addressed in multi-robot systems, especially when the robots form coalitions and the tasks have to be fulfilled before a deadline. In general, it is difficult to foresee the time required by a coalition to finish a task because it depends, among other factors, on the physical interference. Interference is a phenomenon produced when two or more robots want to access the same point simultaneously. This paper presents a new model to predict the time to execute a task. Thanks to this model, the robots needed to carry out a task before a deadline can be determined. Within this framework, the robots learn the interference and therefore, the coalition’s utility, from their past experience using an on-line Support Vector Regression method (SVR). Furthermore, the SVR model is used together with a new auction method called ’Double Round auction’ (DR). It will be demonstrated that by combining the interference model and the DR process, the total utility of the system significantly increases compared to classical auction approaches. This is the first auction method that includes the physical interference effects and that can determine the coalition size during the execution time to address tasks with deadlines. Transport like tasks run on a simulator and on real robots have been used to validate the proposed solutions.     

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.     

Mechanism design for coalition formation and cost sharing in group-buying markets

We study the mechanism design problem of coalition formation and cost sharing in a group-buying electronic marketplace, where buyers can form coalitions to take advantage of volume based discounts. The desirable mechanism properties include stability (in the core), and incentive compatibility with good efficiency. We show the impossibility to simultaneously satisfy efficiency, budget balance and individual rationality at a Bayesian–Nash equilibrium, and propose a mechanism in the core of the game. We then present and evaluate a group of reasonable mechanisms. Empirical results show positive correlation between stability and incentive compatibility (which is in turn related to efficiency).     

多任务联盟形成中的Agent行为策略研究

Agent联盟是多Agent系统中一种重要的合作方式,联盟形成是其研究的关键问题.本文提出一种串行多任务联盟形成中的Agent行为策略,首先论证了Agent合作求解多任务的过程是一个Markov决策过程,然后基于Q-学习求解单个Agent的最优行为策略.实例表明该策略在面向多任务的领域中可以快速、有效地串行形成多个任务求解联盟.     

A knowledge-based approach to coalition formation

Establishing coalitions among humanitarian aid organizations is a challenge. The CPlanT (Coalition Planning Tool) system uses a multi-agent knowledge-based approach to reduce complexity and communication traffic, while also protecting stakeholder privacy.     

约束条件下联盟生成研究进展

联盟生成是在多Agent系统的研究中最为重要的挑战之一。如何对Agent进行划分使所得社会福利最大化是当前面临的主要问题。假设每个Agent都具有理性和自利性的特性，为了追求自身的利益最大化而选择和其他的Agent进行联合，进而使整个系统实现利益的最大化。目前，联盟生成问题有很大的计算挑战，即使在进行联盟的时候添加了约束条件，也需要新的算法来更快更有效地解决该问题。本文主要对约束条件下的联盟生成的研究进行综述，主要包括4部分:最坏情况有限界联盟生成、动态规划联盟生成求精确最优解、联盟生成求近似最优解和约束条件下联盟生成求最优解。     

Dynamic coalition formation among rational agents

Dynamic coalition formation (DCF) promises to be well suited for applications of ubiquitous and mobile computing. This article proposes a simulation-based DCF scheme designed to let rational agents form coalitions in dynamic environments.     

Complementary‐based coalition formation for energy microgrids

In recent years, the notion of electrical energy microgrids (MGs), in which communities share their locally generated power, has gained increasing interest. Typically, the energy generated comes from renewable resources, which means that its availability is variable, ie, sometimes there may be energy surpluses and at other times energy deficits. This energy variability can be ameliorated by trading energy with a connected electricity grid. However, since main electricity grids are subject to faults or other outages, it can be advantageous for energy MGs to form coalitions and share their energy among themselves. In this work, we present our model for the dynamic formation of such MG coalitions. In our model, MGs form coalitions on the basis of complementary weather patterns. Our agent‐based model, which is scalable and affords autonomy among the MGs participating in the coalition (agents can join and depart from coalitions at any time), features methods to reduce overall “discomfort” so that, even when all participating MGs in a coalition experience deficits, they can share energy so that their overall discomfort is reduced. We demonstrate the efficacy of our model by showing empirical studies conducted with real energy production and consumption data.     

Constant factor approximation algorithms for coalition structure generation

Coalition structure generation is a central problem in characteristic function games. Most algorithmic work to date can be classified into one of three broad categories: anytime algorithms, design-to-time algorithms and heuristic algorithms [5]. This paper focuses on the former two approaches. Both design-to-time and anytime algorithms have pros and cons. While design-to-time algorithms guarantee finding an optimal solution, they must be run to completion in order to generate any solution. Anytime algorithms; however, permit premature termination while providing solutions of ever increasing quality along with quality guarantees. Design-to-time algorithms have a better worst case runtime (O(3 ⁿ ) for n agents) compared to the current anytime algorithms (O(n ⁿ ) for n agents), but do not provide the flexibility of anytime algorithms. In this paper we present the first design-to-time constant factor approximation algorithms for coalition structure generation that guarantee high quality solutions quickly. We show how our approach can be used as an anytime algorithm, which combines both the worst case runtime of the design-to-time algorithms and the flexibility of the anytime algorithms. This results in the first anytime algorithm for coalition structure generation which has the same worst case time complexity of the current best design-to-time algorithms.     

Hybrid mission planning with coalition formation

The increase in robotic capabilities and the number of such systems being used has resulted in opportunities for robots to work alongside humans in an increasing number of domains. The current robot control paradigm of one or multiple humans controlling a single robot is not scalable to domains that require large numbers of robots and is infeasible in communications constrained environments. Robots must autonomously plan how to accomplish missions composed of many tasks in complex and dynamic domains; however, mission planning with a large number of robots for such complex missions and domains is intractable. Coalition formation can manage planning problem complexity by allocating the best possible team of robots for each task. A limitation is that simply allocating the best possible team does not guarantee an executable plan can be formulated. However, coupling coalition formation with planning creates novel, domain-independent tools resulting in the best possible teams executing the best possible plans for robots acting in complex domains.     

一种改进的多agent分布式联盟形成算法

仅采用任务性价比作为多智能体任务分配过程中的任务选择标准,会产生时间消耗大、资源利用低等问题.为此,综合任务性价比和智能体资源的特点,提出了多任务准备度的概念.根据多智能体任务分配过程的收敛性和时效性,采用Learning Automata算法动态调整任务准备度各项的权重;进而利用该方法模拟解决了低、中、高3种任务需求下多智能体任务分配问题.仿真实验结果验证了所提出方法的有效性,资源冗余可至少减少20%.     

基于Agent的电子市场结伴购买算法

以电子商务市场中买方Agent的结伴购买为背景,研究了自利主体的动态结盟问题。基于博弈论,考虑协商花费为常数情况,若所有Agent都采用“底线”策略,存在唯一的纳什平衡解。最后给出了计算底线值的方法及算法。     

Scalable hedonic coalition formation for task allocation with heterogeneous robots

Intelligent Service Robotics - Tasks in the real world are complex and often require multiple robots to collaborate to be serviced. In many cases, a task might require different sensory inputs and...     

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.     

A dynamic game of coalition formation under ambiguity

In a previous paper, we generalized to the mixed strategy case the γ model of coalition formation (introduced by Hart and Kurz in Econometrica 51(4):1047–1064, 1983) for situations in which players have ambiguous expectations about the formation of the coalitions in which they are not involved; then we analyzed the corresponding evolutionary games. In this paper, we embody into the model rationality of the players; it follows that allowing for mixed strategies makes it impossible to construct unequivocally a von Neumann–Morgestein expected utility function coherent (in the sense of de Finetti B in Sul Significato Soggettivo della Probabilità, Fundamenta Mathematicae, T, vol XVIII, pp 298–329, 1931) to every strategy profile. We find out that if the multiplicity of coherent beliefs problem is approached by considering “ambiguity loving” players then existence results for classical static equilibria can be obtained in this model. Moreover, we provide conditions for the game to be dynamically playable and we find how the coalition structure beliefs might evolve coherently (according) to the evolution of the strategies.     

Optimizing coalition formation for tasks with dynamically evolving rewards and nondeterministic action effects

We consider a problem domain where coalitions of agents are formed in order to execute tasks. Each task is assigned at most one coalition of agents, and the coalition can be reorganized during execution. Executing a task means bringing it to one of the desired terminal states, which might take several time steps. The state of the task evolves even if no coalition is assigned to its execution and depends nondeterministically on the cumulative actions of the agents in the coalition. Furthermore, we assume that the reward obtained for executing a task evolves in time: the more the execution of the task is delayed, the lesser the reward. A representative example of this class of problems is the allocation of firefighters to fires in a disaster rescue environment. We describe a practical methodology through which a problem of this class can be encoded as a Markov Decision Process. Due to the three levels of factoring in the resulting MDP (the states, actions and rewards are composites of the original features of the problem) the resulting MDP can be directly solved only for small problem instances. We describe two methods for parallel decomposition of the MDP: the MDP RSUA approach for random sampling and uniform allocation and the MDP REUSE method which reuses the lower level MDP to allocate resources to the parallel subproblems. Through an experimental study which models the problem domain using the fire simulation components of the Robocup Rescue simulator, we show that both methods significantly outperform heuristic approaches and MDP REUSE provides an overall higher performance than MDP RSUA.