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.     

Scenario driven optimal sequencing under deep uncertainty

The optimal sequencing/scheduling of activities is vital in many areas of environmental and water resources planning and management. In order to account for deep uncertainty surrounding future conditions, a new optimal scheduling approach is introduced in this paper, which consists of three stages. Firstly, a portfolio of diverse sequences that are optimal under a range of plausible future conditions is generated. Next, global sensitivity analysis is used to assess the robustness of these sequences and to determine the relative contribution of future uncertain variables to this robustness. Finally, an optimal sequence is selected for implementation. The approach is applied to the optimal sequencing of additional potential water supply sources, such as desalinated-, storm- and rain-water, for the southern Adelaide water supply system, over a 40 year planning horizon at 10-year intervals. The results indicate that the proposed approach is useful in identifying optimal sequences under deep uncertainty.     

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.     

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.     

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.     

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

联盟生成是在多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.     

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.     

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.

     

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).     

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.     

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

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

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

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

A simulation‐based algorithm for optimal pricing policy under demand uncertainty

We propose a simulation‐based algorithm for computing the optimal pricing policy for a product under uncertain demand dynamics. We consider a parameterized stochastic differential equation (SDE) model for the uncertain demand dynamics of the product over the planning horizon. In particular, we consider a dynamic model that is an extension of the Bass model. The performance of our algorithm is compared to that of a myopic pricing policy and is shown to give better results. Two significant advantages with our algorithm are as follows: (a) it does not require information on the system model parameters if the SDE system state is known via either a simulation device or real data, and (b) as it works efficiently even for high‐dimensional parameters, it uses the efficient smoothed functional gradient estimator.     

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

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