Non-linear protocols for optimal distributed consensus in networks of dynamic agents

We consider stationary consensus protocols for networks of dynamic agents with fixed topologies. At each time instant, each agent knows only its and its neighbors’ state, but must reach consensus on a group decision value that is function of all the agents’ initial state. We show that the agents can reach consensus if the value of such a function is time-invariant when computed over the agents’ state trajectories. We use this basic result to introduce a non-linear protocol design rule allowing consensus on a quite general set of values. Such a set includes, e.g., any generalized mean of order p of the agents’ initial states. As a second contribution we show that our protocol design is the solution of individual optimizations performed by the agents. This notion suggests a game theoretic interpretation of consensus problems as mechanism design problems. Under this perspective a supervisor entails the agents to reach a consensus by imposing individual objectives. We prove that such objectives can be chosen so that rational agents have a unique optimal protocol, and asymptotically reach consensus on a desired group decision value. We use a Lyapunov approach to prove that the asymptotical consensus can be reached when the communication links between nearby agents define a time-invariant undirected network. Finally we perform a simulation study concerning the vertical alignment maneuver of a team of unmanned air vehicles.     

分布式自利agent任务分配算法

在有自利agent参与的任务分配情形中,由于agent的自利性,导致各agent不能有效合作,影响agent的个体收益和系统总收益.解决该问题的一个途径是对agent所得的收益进行合理分配.文中基于分布式自利agent联盟技能博弈模型,提出自利agent的任务分配算法.模型中提供技能的服务agent和管理任务的agent都是自利的,分别处于不同的地理位置,具有不同的视野范围.算法为任务agent设计效益分配策略,合理分配自己的收益给所需的技能,任务分配结果在保证个体自利性的前提下获得较高的系统收益.仿真结果验证文中算法的有效性,并考察自利agent的视野范围对自利agent的个体收益和系统总收益的影响.     

Fitness function shaping in multiagent cooperative coevolutionary algorithms

Coevolution is a promising approach to evolve teams of agents which must cooperate to achieve some system objective. However, in many coevolutionary approaches, credit assignment is often subjective and context dependent, as the fitness of an individual agent strongly depends on the actions of the agents with which it collaborates. In order to alleviate this problem, we introduce a cooperative coevolutionary algorithm which biases the evolutionary search as well as shapes agent fitness functions to promote behavior that benefits the system-level performance. More specifically, we bias the search using a hall of fame approximation of optimal collaborators, and shape the agent fitness using the difference evaluation function. Our results show that shaping agent fitness with the difference evaluation improves system performance by up to 50 %, and adding an additional fitness bias improves performance by up to 75 % in our experiments. Finally, an analysis of system performance as a function of computational cost demonstrates that this algorithm makes extremely efficient use of computational resources, having a higher performance as a function of computational cost than any other algorithm tested.     

一种基于分布式强化学习的多智能体协调方法

多智能体系统研究的重点在于使功能独立的智能体通过协商、协调和协作,完成复杂的控制任务或解决复杂的问题。通过对分布式强化学习算法的研究和分析,提出了一种多智能体协调方法,协调级将复杂的系统任务进行分解,协调智能体利用中央强化学习进行子任务的分配,行为级中的任务智能体接受各自的子任务,利用独立强化学习分别选择有效的行为,协作完成系统任务。通过在Robot Soccer仿真比赛中的应用和实验,说明了基于分布式强化学习的多智能体协调方法的效果优于传统的强化学习。     

Hierarchical multi-agent reinforcement learning

In this paper, we investigate the use of hierarchical reinforcement learning (HRL) to speed up the acquisition of cooperative multi-agent tasks. We introduce a hierarchical multi-agent reinforcement learning (RL) framework, and propose a hierarchical multi-agent RL algorithm called Cooperative HRL. In this framework, agents are cooperative and homogeneous (use the same task decomposition). Learning is decentralized, with each agent learning three interrelated skills: how to perform each individual subtask, the order in which to carry them out, and how to coordinate with other agents. We define cooperative subtasks to be those subtasks in which coordination among agents significantly improves the performance of the overall task. Those levels of the hierarchy which include cooperative subtasks are called cooperation levels. A fundamental property of the proposed approach is that it allows agents to learn coordination faster by sharing information at the level of cooperative subtasks, rather than attempting to learn coordination at the level of primitive actions. We study the empirical performance of the Cooperative HRL algorithm using two testbeds: a simulated two-robot trash collection task, and a larger four-agent automated guided vehicle (AGV) scheduling problem. We compare the performance and speed of Cooperative HRL with other learning algorithms, as well as several well-known industrial AGV heuristics. We also address the issue of rational communication behavior among autonomous agents in this paper. The goal is for agents to learn both action and communication policies that together optimize the task given a communication cost. We extend the multi-agent HRL framework to include communication decisions and propose a cooperative multi-agent HRL algorithm called COM-Cooperative HRL. In this algorithm, we add a communication level to the hierarchical decomposition of the problem below each cooperation level. Before an agent makes a decision at a cooperative subtask, it decides if it is worthwhile to perform a communication action. A communication action has a certain cost and provides the agent with the actions selected by the other agents at a cooperation level. We demonstrate the efficiency of the COM-Cooperative HRL algorithm as well as the relation between the communication cost and the learned communication policy using a multi-agent taxi problem.     

基于中性进化、自组织和自然选择的进化算法

生物的进化同时在基因层、个体层和种群层进行。基因层上的进化是随机、均匀、无方向性的；个体层的随机行为通过自组织作用形成种群的复杂行为；种群的进化则是一个以环境为参考的自然选择过程。基于此，本文提出了一种基于中性进化，自组织和自然选择的进化算法．该算法同时考虑基因层、个体层和种群层上的进化过程以及三个层次间的相互作用和映射关系。提出了个体能力评估函数f(xi)的概念，分析了个体能力评估函数f(xi)与种群适应度函数fit(X)间的关系。时该算法的性能进行了仿真研究．仿真结果表明该算法相对于传统的进化算法具有更好的全局收敛性，更快的收敛速度和更强的参数鲁棒性。     

From insect to Internet: Situated control for networked robot teams

Ant-like systems take advantage of agents' situatedness to reduce or eliminate the need for centralized control or global knowledge. This reduces the need for complexity of individuals and leads to robust, scalable systems. Such insect-inspired situated approaches have proven effective both for task performance and task allocation. The desire for general, principled techniques for situated interaction has led us to study the exploitation of abstract situatedness – situatedness in non-physical environments. The port-arbitrated behavior-based control approach provides a well-structured abstract behavior space in which agents can participate in situated interaction. We focus on the problem of role assumption, distributed task allocation in which each agent selects its own task-performing role. This paper details our general, principled Broadcast of Local Eligibility (BLE) technique for role-assumption in such behavior-space-situated systems, and provides experimental results from the CMOMMT target-tracking task. This revised version was published online in August 2006 with corrections to the Cover Date.     

Simulated environments with animated agents: effects on visual attention,emotion, performance,and perception

This research assessed how emotive animated agents in a simulation‐based training affect the performance outcomes and perceptions of the individuals interacting in real time with the training application. A total of 56 participants consented to complete the study. The material for this investigation included a nursing simulation in which participants interacted with three animated agents. The results of this investigation indicated that both experienced and novice participants focused more visual attention time on the body of the animated agent than the other defined areas of interest in the simulated environment. The results also indicated that novice participants conveyed more neutral facial expressions during the interaction with the animated agents than experience participants. The results of the simulation performance scores indicated that novice participants achieved higher simulation performance scores on the simulation task than experienced participants. Lastly, the results of the agent persona instrument showed that experienced and novice participants perceived the animated agents as facilitators of learning, credible, human‐like and engaging.     

English outside the academic sphere: A mobile-based context-aware comparison study on collaborative and individual learning

Context-aware ubiquitous learning (CAUL) technology provides language learners with interactive learning environments and has been found to increase learning effectiveness and self-efficacy due to student interaction, discussion and evaluation of the entire learning process. This study used a mobile-based ubiquitous learning system combined with a collaborative learning approach to develop Fitness-specific English listening and reading, and fitness knowledge. The researchers recruited two groups of participants, an individual learning group (N = 31) and a collaborative learning group (N = 30), and evaluated their learning performance via pre-and post-tests. In addition, a questionnaire explored the perceived usefulness, usability, follow-up intention of using the system and self-efficacy regarding fitness-specific English. The results show that both groups improved fitness-specific English in terms of listening and reading comprehension. Moreover, collaborative learning was found to facilitate fitness-specific knowledge, and those in the collaborative learning group improved their self-efficacy more than those in the individual learning group.     

Limited benefit of joint estimation in multi‐agent iterative learning

This paper studies iterative learning control (ILC) in a multi‐agent framework, wherein a group of agents simultaneously and repeatedly perform the same task. Assuming similarity between the agents, we investigate whether exchanging information between the agents improves an individual's learning performance. That is, does an individual agent benefit from the experience of the other agents? We consider the multi‐agent iterative learning problem as a two‐step process of: first, estimating the repetitive disturbance of each agent; and second, correcting for it. We present a comparison of an agent's disturbance estimate in the case of (I) independent estimation, where each agent has access only to its own measurement, and (II) joint estimation, where information of all agents is globally accessible. When the agents are identical and noise comes from measurement only, joint estimation yields a noticeable improvement in performance. However, when process noise is encountered or when the agents have an individual disturbance component, the benefit of joint estimation is negligible. Copyright © 2011 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

Performance analysis of a mobile agent prototype system based on VIRGO P2P protocols

The mobile agent technique has been broadly used in next generation distributed systems. The system performance measurement and simulation are required before the system can be deployed on a large scale. In this paper, we address performance analysis on a finite state mobile agent prototype on the basis of Virtual Hierarchical Tree Grid Organizations (VIRGO). The finite states refer to the migration, execution, and searching of the mobile agent. We introduce a novel evaluation model for the finite state mobile agent. The experimental results based on this evaluation model show that the finite mobile agents can perform well under multiple agent conditions and are superior to the traditional client/server approach. Copyright © 2013 John Wiley & Sons, Ltd.     

Tropism-based cognition: a novel software architecture for agents in colonies

A novel architecture for agents in colonies has been developed in order to investigate certain forms of group interaction. Specifically, we are interested in the extent to which overall goals for a colony can be achieved when each agent is only aware of limited local goals, whether the architecture allows for emergence of unexpected behaviour, and whether explicit communication among agents facilitates or hinders task performance. The architecture supports several forms of learning. Large colonies of agents (as many as 100) have been studied in simulation experiments, where they carried out fetch-and-carry tasks in the presence of predators and with limited energy reserves. In addition, a physical colony of four agents has been fabricated with the same architecture, to ensure that the behaviours observed in simulation were also present in the hardware implementations.     

Fitness functions in evolutionary robotics: A survey and analysis

This paper surveys fitness functions used in the field of evolutionary robotics (ER). Evolutionary robotics is a field of research that applies artificial evolution to generate control systems for autonomous robots. During evolution, robots attempt to perform a given task in a given environment. The controllers in the better performing robots are selected, altered and propagated to perform the task again in an iterative process that mimics some aspects of natural evolution. A key component of this process–one might argue, the key component–is the measurement of fitness in the evolving controllers. ER is one of a host of machine learning methods that rely on interaction with, and feedback from, a complex dynamic environment to drive synthesis of controllers for autonomous agents. These methods have the potential to lead to the development of robots that can adapt to uncharacterized environments and which may be able to perform tasks that human designers do not completely understand. In order to achieve this, issues regarding fitness evaluation must be addressed. In this paper we survey current ER research and focus on work that involved real robots. The surveyed research is organized according to the degree of a priori knowledge used to formulate the various fitness functions employed during evolution. The underlying motivation for this is to identify methods that allow the development of the greatest degree of novel control, while requiring the minimum amount of a priori task knowledge from the designer.     

Evolving team behaviors with specialization

This article evaluates Collective Neuro-Evolution (CONE), a cooperative co-evolutionary method for solving collective behavior tasks and increasing task performance via facilitating behavioral specialization in agent teams. Specialization is used as a problem solving mechanism, and its emergence is guided and regulated by CONE. CONE is comparatively evaluated with related methods in a simulated evolutionary robotics pursuit-evasion task. This task required multiple pursuer robots to cooperatively capture evader robots. Results indicate that CONE is appropriate for evolving specialized behaviors. The interaction of specialized behaviors produces behavioral heterogeneity in teams and collective prey capture behaviors that yield significantly higher performances compared to related methods.     

A swarm system design based on a modified particle swarm algorithm for a self-organizing scheme

In this paper, an attempt has been made to incorporate some special features in the conventional particle swarm optimization (PSO) technique for decentralized swarm agents. The modified particle swarm algorithm (MPSA) for the self-organization of decentralized swarm agents is proposed and studied. In the MPSA, the update rule of the best agent in a swarm is based on a proportional control concept and the fitness of each agent is evaluated on-line. The virtual zone is developed to avoid conflict among the agents. In this scheme, each agent self-organizes to flock to the best agent in a swarm and migrate to a moving target while avoiding obstacles and collision among agents. Aided by these advantages such as cooperative group behaviors, flexible formation and scalability, the proposed approach enables large-scale swarm agents to distribute themselves optimally for a given task. The simulation results have shown that the proposed scheme effectively constructs a self-organized swarm system with the capability of flocking and migration.     

双目标推动下群体行为的元胞自动机模拟

采用元胞自动机对自推动粒子改进模型进行模拟,在此基础上分别探讨无目标与双目标群体行为的演化特征。无目标条件下群体行为的元胞模拟结果显示低密度环境下大部分个体处于动态均衡,高密度环境下大部分个体处于静态均衡,中等密度下两种均衡均存在。基于双目标吸引力的群体行为模拟结果显示当智能体的理性程度较低时系统演化能够产生一定的集聚效应,处于吸引源以外的智能体与吸引源保持一定距离并呈湍流式运动,而当智能体具备小概率全局理性判断能力时,群体行为的演化结果为大部分智能体都聚集在吸引源附近。     

Finite‐Time Consensus Problem for Second‐Order Multi‐Agent Systems Under Switching Topologies

This paper investigates the finite‐time consensus problem for multi‐agent systems with second‐order individual dynamics under switching topologies. A distributed continuous‐time protocol is designed to guarantee finite‐time consensus for homogeneous agents without predetermined leaders, i.e., it ensures agents asymptotically converge to an average consensus within finite time, even if the interaction topology among them is time‐varying but stepwise jointly‐connected. In particular, it introduces a distributed continuous‐time protocol to reach consensus in finite time and reduce the chattering together. Finally, the simulation results are also given to validate the proposed approach.     

AGENT COORDINATION CONTEXTS IN A MAS COORDINATION INFRASTRUCTURE

In order to harness complexity in multi-agent systems (MAS), first-class entities that mediate interaction between agents and environment are required, which can encapsulate control over MAS behavior and evolution. To this end, MAS infrastructures should provide mediating artifacts, both enabling and constraining agent interactions, and possibly representing admissible agent perceptions and actions over the environment.

Along this line, in this paper, we take the notion of agent coordination context (ACC) as a means to model agent-environment interactions, and show how it can be embedded within a MAS infrastructure in terms of model and runtime structures. Then, we take the TuCSoN coordination infrastructure as a reference, and extend it with the ACC abstraction to integrate the support for coordination with organization and security.     

Mutation systems

We propose mutation systems as a model of the evolution of a string subject to the effects of mutations and a fitness function. One fundamental question about such a system is whether knowing the rules for mutations and fitness, we can predict whether it is possible for one string to evolve into another. To explore this issue, we define a specific kind of mutation system with point mutations and a fitness function based on conserved strongly k-testable string patterns. We show that for any k greater than 1, such systems can simulate computation by both finite state machines (FSMs) and asynchronous cellular automata. The cellular automaton simulation shows that in this framework, universal computation is possible and the question of whether one string can evolve into another is undecidable. We also analyse the efficiency of the FSM simulation assuming random point mutations.