共查询到20条相似文献,搜索用时 15 毫秒
1.
Multi-robot coalition formation 总被引:8,自引:0,他引:8
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. 相似文献
2.
针对重叠联盟的合作博弈框架(OCF games)中重叠联盟结构生成(OCSG)求解困难的问题,提出了一种基于贪心方法的有效算法。首先使用了一种带有联盟数量k约束的OCF博弈(kOCF games)模型来限制OCSG问题的规模;然后引入了一种相似度量来表示任意两个联盟结构之间的相似程度,并基于相似度量定义了单调性的性质,这意味着某一联盟结构与最优联盟结构的相似度越高,该联盟的单调性的值就越大;最后对于具有单调性质的kOCF博弈,采用了逐一插入玩家编号以逼近最优联盟结构的方法设计了联盟约束贪心(CCG)算法来求解给定的OCSG问题,并在理论上证明了CCG算法的复杂度是O(n2k+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可解的,而且拥有更好的适用性。 相似文献
3.
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. 相似文献
4.
Multi-robot coalition formation in real-time scenarios 总被引:1,自引:0,他引:1
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. 相似文献
5.
6.
《Expert systems with applications》2014,41(8):3736-3747
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. 相似文献
7.
Cuihong Li Shuchi Chawla Uday Rajan Katia Sycara 《Electronic Commerce Research and Applications》2004,3(4):341-354
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). 相似文献
8.
9.
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. 相似文献
10.
联盟生成是在多Agent系统的研究中最为重要的挑战之一。如何对Agent进行划分使所得社会福利最大化是当前面临的主要问题。假设每个Agent都具有理性和自利性的特性,为了追求自身的利益最大化而选择和其他的Agent进行联合,进而使整个系统实现利益的最大化。目前,联盟生成问题有很大的计算挑战,即使在进行联盟的时候添加了约束条件,也需要新的算法来更快更有效地解决该问题。本文主要对约束条件下的联盟生成的研究进行综述,主要包括4部分:最坏情况有限界联盟生成、动态规划联盟生成求精确最优解、联盟生成求近似最优解和约束条件下联盟生成求最优解。 相似文献
11.
Dynamic coalition formation among rational agents 总被引:1,自引:0,他引:1
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. 相似文献
12.
Muhammad Yasir Martin Purvis Maryam Purvis Bastin Tony Roy Savarimuthu 《Computational Intelligence》2018,34(2):679-712
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. 相似文献
13.
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
n
) for n agents) compared to the current anytime algorithms (O(n
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. 相似文献
14.
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. 相似文献
15.
仅采用任务性价比作为多智能体任务分配过程中的任务选择标准,会产生时间消耗大、资源利用低等问题.为此,综合任务性价比和智能体资源的特点,提出了多任务准备度的概念.根据多智能体任务分配过程的收敛性和时效性,采用Learning Automata算法动态调整任务准备度各项的权重;进而利用该方法模拟解决了低、中、高3种任务需求下多智能体任务分配问题.仿真实验结果验证了所提出方法的有效性,资源冗余可至少减少20%. 相似文献
16.
17.
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... 相似文献
18.
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. 相似文献
19.
Giuseppe De Marco Maria Romaniello 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2010,15(4):637-644
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. 相似文献
20.
Majid Ali Khan Damla Turgut Ladislau Bölöni 《Autonomous Agents and Multi-Agent Systems》2011,22(3):415-438
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. 相似文献