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.     

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.     

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.     

Simulating engineering systems under uncertainty and optimal decision making

A new technology (technique) that helps construct a mathematical model of a complex engineering system by optimal decision making based on it is given. To construct the model of an engineering system, methods of regressive analysis are used to transform the initial (experimental) data into a vector (multiobjective) mathematical programming problem. To solve it, methods are presented that rely on criteria normalization and principle of guaranteed result. The technique of constructing models of engineering systems, methods of solving the vector mathematical programming problem and optimal decision making are demonstrated by the test examples in Matlab.     

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.     

Behavior monitoring under uncertainty using Bayesian surprise and optimal action selection

The increasing trend towards delegating tasks to autonomous artificial agents in safety–critical socio-technical systems makes monitoring an action selection policy of paramount importance. Agent behavior monitoring may profit from a stochastic specification of an optimal policy under uncertainty. A probabilistic monitoring approach is proposed to assess if an agent behavior (or policy) respects its specification. The desired policy is modeled by a prior distribution for state transitions in an optimally-controlled stochastic process. Bayesian surprise is defined as the Kullback–Leibler divergence between the state transition distribution for the observed behavior and the distribution for optimal action selection. To provide a sensitive on-line estimation of Bayesian surprise with small samples twin Gaussian processes are used. Timely detection of a deviant behavior or anomaly in an artificial pancreas highlights the sensitivity of Bayesian surprise to a meaningful discrepancy regarding the stochastic optimal policy when there exist excessive glycemic variability, sensor errors, controller ill-tuning and infusion pump malfunctioning. To reject outliers and leave out redundant information, on-line sparsification of data streams is proposed.     

Simulation-based conjoint ranking for optimal decision support process under aleatory uncertainty

Design chain management requires many decision makers throughout the product development process. It is critical to reduce complexity and uncertainty of the design process by correctly modeling subjective data associated with decision makers’ preferences. This paper aims at using decision support to find optimal designs by modeling respondent preferences and trade-offs with consideration of uncertainty. Specifically, a simulation-based ranking methodology is implemented and incorporated with traditional conjoint analysis. This process facilitates a schematic decision support process by alleviating user fatigue. In addition, incorporation of uncertainty in the ranking process provides the capability of producing robust and reliable products. The efficacy and applicability of simulation-based conjoint ranking is demonstrated with a case study of a power-generating shock absorber design.     

Robust stability considerations in optimal design of dynamic systems under uncertainty

This paper presents a method for the incorporation of robust stability criteria in the design of dynamic systems under uncertainty. Process systems are modelled via dynamic mathematical models, variations include both uncertain parameters and time-varying disturbances, while control structure selection and controller design is considered as part of the design optimization problem. Stability criteria are included, based on the concept of the measure of a matrix, to maintain desired dynamic characteristics, in a multiperiod design formulation. A combined flexibility-stabiluty analysis step is also introduced to ensure feasible and stable operation of the dynamic system in the presence of parametric uncertainties and process disturbances. The potential of the proposed approach is illustrated with a ternary distillation column design and control problem (featuring a rigorous tray-by-tray model).     

A quadratic-cost dual control-based approach for optimal trajectory planning under uncertainty

This paper presents a dual control-based approach for optimal trajectory planning under uncertainty. The method approximately converts a nonlinear stochastic optimal control problem whose objective function is a combination of quadratic stage and/or terminal costs, with additive Gaussian process and measurement noises, into a deterministic optimal control problem by augmenting the uncertainty state defined by the square-root of the estimation error covariance matrix. The open-loop solution to the resulting deterministic optimal control reformulation is obtained using an existing pseudo-spectral method. The effectiveness of the proposed dual control-based approach is verified with two numerical examples of trajectory planning for two-dimensional robot motion with lack of observability for localization, which highlights the impact of the dual effect on the shape of designed paths.

     

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.     

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部分:最坏情况有限界联盟生成、动态规划联盟生成求精确最优解、联盟生成求近似最优解和约束条件下联盟生成求最优解。     

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的电子市场结伴购买算法

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

Power and welfare in bargaining for coalition structure formation

We investigate a noncooperative bargaining game for partitioning n agents into non-overlapping coalitions. The game has n time periods during which the players are called according to an exogenous agenda to propose offers. With probability \(\delta \), the game ends during any time period \(t<n\). If it does, the first t players on the agenda get a chance to propose but the others do not. Thus, \(\delta \) is a measure of the degree of democracy within the game (ranging from democracy for \(\delta =0\), through increasing levels of authoritarianism as \(\delta \) approaches 1, to dictatorship for \(\delta =1\)). We determine the subgame perfect equilibrium (SPE) and study how a player’s position on the agenda affects his bargaining power. We analyze the relation between the distribution of power of individual players, the level of democracy, and the welfare efficiency of the game. We find that purely democratic games are welfare inefficient and that introducing a degree of authoritarianism into the game makes the distribution of power more equitable and also maximizes welfare. These results remain invariant under two types of player preferences: one where each player’s preference is a total order on the space of possible coalition structures and the other where each player either likes or dislikes a coalition structure. Finally, we show that the SPE partition may or may not be core stable.     

制造/再制造集成物流网络的优化设计研究

考虑到闭环物流系统中不同周期内各消费区域的产品需求数量、回收产品质量的不确定性,建立了多周期、有能力限制、正逆向物流集成运作的混合整数非线性规划模型。以总运营成本最少为目标,确定了制造/再制造集成物流系统中各种设施的数量、规模、位置以及各设施间的物流量分以配。通过算例验证了模型的有效性。     

基于人工免疫系统的异构多机器人联盟形成

对动态环境下多机器人联盟形成问题进行了研究,提出了一种基于人工免疫系统的异构多机器人联盟形成方法.该方法在对比人工免疫系统与多机器人系统相似关系的基础上,利用人工免疫系统的隐喻机制为面向动态感知任务的异构多机器人联盟形成问题提供了一种新的思路和解决方法.进行了未知非结构化环境下的多机器人协作搜集仿真实验,仿真结果表明所提方法可以使多机器人系统自主地形成机器人联盟以完成动态感知任务,提高了多机器人系统执行任务的效率.     

Global optimal attitude estimation using uncertainty ellipsoids

A deterministic attitude estimation problem for a rigid body in a potential field, with bounded attitude and angular velocity measurement errors is considered. An attitude estimation algorithm that globally minimizes the attitude estimation error is obtained. Assuming that the initial attitude, the initial angular velocity and measurement noise lie within given ellipsoidal bounds, an uncertainty ellipsoid that bounds the attitude and the angular velocity of the rigid body is obtained. The center of the uncertainty ellipsoid provides point estimates, and the size of the uncertainty ellipsoid measures the accuracy of the estimates. The point estimates and the uncertainty ellipsoids are propagated using a Lie group variational integrator and its linearization, respectively. The attitude and angular velocity estimates are optimal in the sense that the sizes of the uncertainty ellipsoids are minimized.     

Exogenous coalition formation in the e-marketplace based on geographical proximity

This paper considers a model for exogenous coalition formation in e-marketplaces. Using its informational advantage, an e-retailer creates coalitions of customers based on geographical proximity. Most of the literature regards this process as endogenous: a coalition leader among the buyers bundles eventual purchases together in order to obtain a better bargaining position. In contrast – and in response to what is typically observed in business practice – we analyse a situation in which an existing e-retailer exogenously forms customers’ coalitions. Results of this study are highly encouraging. Namely, we demonstrate that even under highly imperfect warehouse management schemes leading to contagion effects, the proposed combined delivery service may offer significant efficiency gains as well as opportunities for Pareto improvement.