Analyzing the dynamics of stigmergetic interactions through pheromone games

The concept of stigmergy provides a simple framework for interaction and coordination in multi-agent systems. However, determining the global system behavior that will arise from local stigmergetic interactions is a complex problem. In this paper we propose to use Game Theory to analyze stigmergetic interactions. We show that a system where agents coordinate by sharing local pheromone information can be approximated by a limiting pheromone game in which different pheromone vectors represent player strategies. This game view allows us to use established methods and solution concepts from game theory to describe the properties of stigmergy based systems. Our goal is to provide a new framework to aid in the understanding and design of pheromone interactions. We demonstrate how we can use this system to determine the long term system behavior of a simple pheromone model, by analyzing the convergence properties of the pheromone update rule in the approximating game. We also apply this model to cases where multiple colonies of agents concurrently optimize different objectives. In this case a limiting colony game can be linked to colony level interactions to characterize the global system behavior.     

Off-line synthesis of evolutionarily stable normative systems

Within the area of multi-agent systems, normative systems are a widely used framework for the coordination of interdependent activities. A crucial problem associated with normative systems is that of synthesising norms that will effectively accomplish a coordination task and that the agents will comply with. Many works in the literature focus on the on-line synthesis of a single, evolutionarily stable norm (convention) whose compliance forms a rational choice for the agents and that effectively coordinates them in one particular coordination situation that needs to be identified and modelled as a game in advance. In this work, we introduce a framework for the automatic off-line synthesis of evolutionarily stable normative systems that coordinate the agents in multiple interdependent coordination situations that cannot be easily identified in advance nor resolved separately. Our framework roots in evolutionary game theory. It considers multi-agent systems in which the potential conflict situations can be automatically enumerated by employing MAS simulations along with basic domain information. Our framework simulates an evolutionary process whereby successful norms prosper and spread within the agent population, while unsuccessful norms are discarded. The outputs of such a natural selection process are sets of codependent norms that, together, effectively coordinate the agents in multiple interdependent situations and are evolutionarily stable. We empirically show the effectiveness of our approach through empirical evaluation in a simulated traffic domain.     

Synchronization of multi-agent systems without connectivity assumptions

Multi-agent systems arise from diverse fields in natural and artificial systems, such as schooling of fish, flocking of birds, coordination of autonomous agents. In multi-agent systems, a typical and basic situation is the case where each agent has the tendency to behave as other agents do in its neighborhood. Through computer simulations, Vicsek et al. (1995) showed that such a simple local interaction rule can lead to a certain kind of cooperative phenomenon (synchronization) of the overall system, if the initial states are randomly distributed and the size of the system population is large. Since this model is of fundamental importance in understanding the multi-agent systems, it has attracted much research attention in recent years. In this paper, we will present a comprehensive theoretical analysis for this class of multi-agent systems under a random framework with large population, but without imposing any connectivity assumptions as did in almost all of the previous investigations. To be precise, we will show that for any given and fixed model parameters concerning with the interaction radius r and the agents’ moving speed v, the overall system will synchronize as long as the population size n is large enough. Furthermore, to keep the synchronization property as the population size n increases, both r and v can actually be allowed to decrease according to certain scaling rates.     

Better manufacturing process organization using multi-agent self-organization and co-evolutionary classifier systems: The multibar problem

Manufacturing processes need their entities to coordinate and discoordinate at different times of the process, in order to achieve the adequate manufacturing timing some jobs need to be done in a sequence or can be done in parallel, using different machines. This paper introduces a complex discoordination problem: the multibar problem, based on the “El Farol” bar problem, devised to test enhanced complexity for multi-agent systems. A multi-agent system that learns based on the extended classifier system (MAXCS) is used for the simulation. Different classifier population sizes are used to help agent adaptation. MAXCS adapts to the all possible configurations of the different bars tested in 20 different experiments in different ways. The first set of experiments proved that MAXCS is able to adapt to the multibar problem with the emergence of several agents switching bars (vacillating agents). The preliminary experiments yielded the hypothesis of the irrelevance of the classifiers’ rule conditions, and their evolution to influence the result. MAXCS is then compared with multi-agent Q-learning (MAQL). These experiments demonstrate the need to use evolutionary computation for better adaptation, rather than just a reinforcement learning algorithm, proving wrong the previous hypothesis. The MAXCS–MAQL comparison showed that the use of rule conditions, combined with the genetic algorithm, determines whether there is only one or several vacillating agents at the same time throughout the experiment. The solution scales when 133 agents are used for the problem. After this study, it can be concluded that the multibar problem can become an interesting benchmark for multi-agent learning and provide manufacturing processes with suitable coordination solutions.     

Designing multi-agent unit tests using systematic test design patterns-(extended version)

Software agents are the basic building blocks in many software systems especially those based on artificial intelligence methods, e.g., reinforcement learning based multi-agent systems (MASs). However, testing software agents is considered a challenging problem. This is due to the special characteristics of agents which include its autonomy, distributed nature, intelligence, and heterogeneous communication protocols. Following the test-driven development (TDD) paradigm, we present a framework that allows MAS developers to write test scenarios that test each agent individually. The framework relies on the concepts of building mock agents and testing common agent interaction design patterns. We analyze the most common agent interaction patterns including pair and mediation patterns in order to provide stereotype implementation for their corresponding test cases. These implementations serve as test building blocks and are provided as a set of ready-for-reuse components in our repository. This way, the developer can concentrate on testing the business logic itself and spare him/her the burden of implementing tests for the underlying agent interaction patterns. Our framework is based on standard components such as the JADE agent platform, the JUnit framework, and the eclipse plug-in architecture. In this paper, we present in details the design and function of the framework. We demonstrate how we can use the proposed framework to define more stereotypes in the code repository and provide a detailed analysis of the code coverage for our designed stereotype test code implementations.     

Three and higher dimensional autonomous formations: Rigidity, persistence and structural persistence

In this paper, we generalize the notion of persistence, which has been originally introduced for two-dimensional formations, to R^d for d?3, seeking to provide a theoretical framework for real world applications, which often are in three-dimensional space as opposed to the plane. Persistence captures the desirable property that a formation moves as a cohesive whole when certain agents maintain their distances from certain other agents. We verify that many of the properties of rigid and/or persistent formations established in R² are also valid for higher dimensions. Analysing the closed subgraphs and directed paths in persistent graphs, we derive some further properties of persistent formations. We also provide an easily checkable necessary condition for persistence. We then turn our attention to consider some practical issues raised in multi-agent formation control in three-dimensional space. We display a new phenomenon, not present in R², whereby subsets of agents can behave in a problematic way. When this behaviour is precluded, we say that the graph depicting the multi-agent formation has structural persistence. In real deployment of controlled multi-agent systems, formations with underlying structurally persistent graphs are of interest. We analyse the characteristics of structurally persistent graphs and provide a streamlined test for structural persistence. We study the connections between the allocation of degrees of freedom (DOFs) across agents and the characteristics of persistence and/or structural persistence of a directed graph. We also show how to transfer DOFs among agents, when the formation changes with new agent(s) added, to preserve persistence and/or structural persistence.     

An Optimal Approach to Collaborative Target Tracking with Performance Guarantees

In this paper, we present a discrete-time optimization framework for target tracking with multi-agent systems. The “target tracking” problem is formulated as a generic semidefinite program (SDP) that when paired with an appropriate objective yields an optimal robot configuration over a given time step. The framework affords impressive performance guarantees to include full target coverage (i.e. each target is tracked by at least a single team member) as well as maintenance of network connectivity across the formation. Key to this work is the result from spectral graph theory that states the second-smallest eigenvalue—λ ₂—of a weighted graph’s Laplacian (i.e. its inter-connectivity matrix) is a measure of connectivity for the associated graph. Our approach allows us to articulate agent-target coverage and inter-agent communication constraints as linear-matrix inequalities (LMIs). Additionally, we present two key extensions to the framework by considering alternate tracking problem formulations. The first allows us to guarantee k-coverage of targets, where each target is tracked by k or more agents. In the second, we consider a relaxed formulation for the case when network connectivity constraints are superfluous. The problem is modeled as a second-order cone program (SOCP) that can be solved significantly more efficiently than its SDP counterpart—making it suitable for large-scale teams (e.g. 100’s of nodes in real-time). Methods for enforcing inter-agent proximity constraints for collision avoidance are also presented as well as simulation results for multi-agent systems tracking mobile targets in both ?² and ?³.     

Dialogue games that agents play within a society

Human societies have long used the capability of argumentation and dialogue to overcome and resolve conflicts that may arise within their communities. Today, there is an increasing level of interest in the application of such dialogue games within artificial agent societies. In particular, within the field of multi-agent systems, this theory of argumentation and dialogue games has become instrumental in designing rich interaction protocols and in providing agents with a means to manage and resolve conflicts. However, to date, much of the existing literature focuses on formulating theoretically sound and complete models for multi-agent systems. Nonetheless, in so doing, it has tended to overlook the computational implications of applying such models in agent societies, especially ones with complex social structures. Furthermore, the systemic impact of using argumentation in multi-agent societies and its interplay with other forms of social influences (such as those that emanate from the roles and relationships of a society) within such contexts has also received comparatively little attention. To this end, this paper presents a significant step towards bridging these gaps for one of the most important dialogue game types; namely argumentation-based negotiation (ABN). The contributions are three fold. First, we present a both theoretically grounded and computationally tractable ABN framework that allows agents to argue, negotiate, and resolve conflicts relating to their social influences within a multi-agent society. In particular, the model encapsulates four fundamental elements: (i) a scheme that captures the stereotypical pattern of reasoning about rights and obligations in an agent society, (ii) a mechanism to use this scheme to systematically identify social arguments to use in such contexts, (iii) a language and a protocol to govern the agent interactions, and (iv) a set of decision functions to enable agents to participate in such dialogues. Second, we use this framework to devise a series of concrete algorithms that give agents a set of ABN strategies to argue and resolve conflicts in a multi-agent task allocation scenario. In so doing, we exemplify the versatility of our framework and its ability to facilitate complex argumentation dialogues within artificial agent societies. Finally, we carry out a series of experiments to identify how and when argumentation can be useful for agent societies. In particular, our results show: a clear inverse correlation between the benefit of arguing and the resources available within the context; that when agents operate with imperfect knowledge, an arguing approach allows them to perform more effectively than a non-arguing one; that arguing earlier in an ABN interaction presents a more efficient method than arguing later in the interaction; and that allowing agents to negotiate their social influences presents both an effective and an efficient method that enhances their performance within a society.     

Software agents for knowledge management: coordination in multi-agent supply chains and auctions

A fundamental question that must be addressed in software agents for knowledge management is coordination in multi-agent systems. The coordination problem is ubiquitous in knowledge management, such as in manufacturing, supply chains, negotiation, and agent-mediated auctions. This paper summarizes several multi-agent systems for knowledge management that have been developed recently by the author and his collaborators to highlight new research directions for multi-agent knowledge management systems. In particular, the paper focuses on three areas of research:

• •Coordination mechanisms in agent-based supply chains. How do we design mechanisms for coordination, information and knowledge sharing in supply chains with self-interested agents? What would be a good coordination mechanism when we have a non-linear structure of the supply chain, such as a pyramid structure? What are the desirable properties for the optimal structure of efficient supply chains in terms of information and knowledge sharing? Will DNA computing be a viable tool for the analysis of agent-based supply chains?
• •Coordination mechanisms in agent-mediated auctions. How do we induce cooperation and coordination among various self-interested agents in agent-mediated auctions? What are the fundamental principles to promote agent cooperation behavior? How do we train agents to learn to cooperate rather than program agents to cooperate? What are the principles of trust building in agent systems?
• •Multi-agent enterprise knowledge management, performance impact and human aspects. Will people use agent-based systems? If so, how do we coordinate agent-based systems with human beings? What would be the impact of agent systems in knowledge management in an information economy?

     

一种等级式的多主体仿真框架

基于多主体的建模和仿真已经被广泛地应用到了复杂系统所涉及到的各个领域，系统中智能主体的实现直接影响系统的性能和仿真结果的有效性。本文通过分析反应主体和慎思主体，指出其各自的优点和缺陷，结合复杂系统仿真的实际情况，提出融合两种主体的多主体系统框架，并对实现中的关键问题给出了详细说明。     

Cooperative Multi-Agent Learning: The State of the Art

Cooperative multi-agent systems (MAS) are ones in which several agents attempt, through their interaction, to jointly solve tasks or to maximize utility. Due to the interactions among the agents, multi-agent problem complexity can rise rapidly with the number of agents or their behavioral sophistication. The challenge this presents to the task of programming solutions to MAS problems has spawned increasing interest in machine learning techniques to automate the search and optimization process. We provide a broad survey of the cooperative multi-agent learning literature. Previous surveys of this area have largely focused on issues common to specific subareas (for example, reinforcement learning, RL or robotics). In this survey we attempt to draw from multi-agent learning work in a spectrum of areas, including RL, evolutionary computation, game theory, complex systems, agent modeling, and robotics. We find that this broad view leads to a division of the work into two categories, each with its own special issues: applying a single learner to discover joint solutions to multi-agent problems (team learning), or using multiple simultaneous learners, often one per agent (concurrent learning). Additionally, we discuss direct and indirect communication in connection with learning, plus open issues in task decomposition, scalability, and adaptive dynamics. We conclude with a presentation of multi-agent learning problem domains, and a list of multi-agent learning resources.     

Cooperative reinforcement learning in topology-based multi-agent systems

Topology-based multi-agent systems (TMAS), wherein agents interact with one another according to their spatial relationship in a network, are well suited for problems with topological constraints. In a TMAS system, however, each agent may have a different state space, which can be rather large. Consequently, traditional approaches to multi-agent cooperative learning may not be able to scale up with the complexity of the network topology. In this paper, we propose a cooperative learning strategy, under which autonomous agents are assembled in a binary tree formation (BTF). By constraining the interaction between agents, we effectively unify the state space of individual agents and enable policy sharing across agents. Our complexity analysis indicates that multi-agent systems with the BTF have a much smaller state space and a higher level of flexibility, compared with the general form of n-ary (n > 2) tree formation. We have applied the proposed cooperative learning strategy to a class of reinforcement learning agents known as temporal difference-fusion architecture for learning and cognition (TD-FALCON). Comparative experiments based on a generic network routing problem, which is a typical TMAS domain, show that the TD-FALCON BTF teams outperform alternative methods, including TD-FALCON teams in single agent and n-ary tree formation, a Q-learning method based on the table lookup mechanism, as well as a classical linear programming algorithm. Our study further shows that TD-FALCON BTF can adapt and function well under various scales of network complexity and traffic volume in TMAS domains.     

THE GAIA2JADE PROCESS FOR MULTI-AGENT SYSTEMS DEVELOPMENT

In this paper we present the Gaia2JADE process concerning how one can implement a multi-agent system with the JADE framework using the Gaia methodology for analysis and design purposes. This process is particularly dedicated to the conversion of Gaia models to JADE code. It is described using the Software Process Engineering Metamodel (SPEM) and extends the one proposed by FIPA for describing the Gaia modeling process. Thus, it proposes to potential MAS developers a process that covers the full software development lifecycle. This work is based on the experience we have acquired by applying this process for implementing a real-word multi-agent system conceived for providing e-services to mobile users. With this paper, we share this experience with future multi-agent systems (MAS) developers, who would like to follow this process, taking into account several technical issues that emerged during the implementation phase, helping them to easily model and implement their systems.     

Temporal Development Methods for Agent-Based

In this paper we overview one specific approach to the formal development of multi-agent systems. This approach is based on the use of temporal logics to represent both the behaviour of individual agents, and the macro-level behaviour of multi-agent systems. We describe how formal specification, verification and refinement can all be developed using this temporal basis, and how implementation can be achieved by directly executing these formal representations. We also show how the basic framework can be extended in various ways to handle the representation and implementation of agents capable of more complex deliberation and reasoning.This revised version was published online in August 2005 with a corrected cover date.     

Spice: a cognitive agent framework for computational crowd simulations in complex environments

Pedestrian behavior is an omnipresent topic, but the underlying cognitive processes and the various influences on movement behavior are still not fully understood. Nonetheless, computational simulations that predict crowd behavior are essential for safety, economics, and transport. Contemporary approaches of pedestrian behavior modeling focus strongly on the movement aspects and seldom address the rich body of research from cognitive science. Similarly, general purpose cognitive architectures are not suitable for agents that can move in spatial domains because they do not consider the profound findings of pedestrian dynamics research. Thus, multi-agent simulations of crowd behavior that strongly incorporate both research domains have not yet been fully realized. Here, we propose the cognitive agent framework Spice. The framework provides an approach to structure pedestrian agent models by integrating concepts of pedestrian dynamics and cognition. Further, we provide a model that implements the framework. The model solves spatial sequential choice problems in sufficient detail, including movement and cognition aspects. We apply the model in a computer simulation and validate the Spice approach by means of data from an uncontrolled field study. The Spice framework is an important starting point for further research, as we believe that fostering interdisciplinary modeling approaches will be highly beneficial to the field of pedestrian dynamics.     

Game theoretical applications for multi-agent systems

We consider game-theoretic principles for design of cooperative and competitive (non-cooperative self-interested) multi-agent systems. Using economic concepts of tâtonnement and economic core, we show that cooperative multi-agent systems should be designed in games with dominant strategies that may lead to social dilemmas. Non-cooperative multi-agent systems, on the other hand, should be designed for games with no clear dominant strategies and high degree of problem complexity. Further, for non-cooperative multi-agent systems, the number of learning agents should be carefully managed so that solutions in the economic core can be obtained. We provide experimental results for the design of cooperative and non-cooperative MAS from telecommunication and manufacturing industries.     

Modeling dynamic environments in multi-agent simulation

Real environments in which agents operate are inherently dynamic—the environment changes beyond the agents’ control. We advocate that, for multi-agent simulation, this dynamism must be modeled explicitly as part of the simulated environment, preferably using concepts and constructs that relate to the real world. In this paper, we describe such concepts and constructs, and we provide a formal framework to unambiguously specify their relations and meaning. We apply the formal framework to model a dynamic RoboCup Soccer environment and elaborate on how the framework poses new challenges for exploring the modeling of environments in multi-agent simulation.     

Applying robotic frameworks in a simulated multi-agent contest

In the Multi-Agent Programming Contest 2017 the TUBDAI team of the Technische Universität Berlin is using the complex multi-agent scenario to evaluate the application of two frameworks from the field (multi-)robot systems. In particular the task-level decision-making and planning framework ROS Hybrid Behaviour Planner (RHBP) is used to implement the execution and decision-making for single agents. The RHBP framework builds on top of the framework Robot Operating System (ROS) that is used to implement the communication and scenario specific coordination strategy of the agents. The united team for the official contest is formed by volunteering students from a project course and their supervisors.     

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.     

Shaping multi-agent systems with gradient reinforcement learning

An original reinforcement learning (RL) methodology is proposed for the design of multi-agent systems. In the realistic setting of situated agents with local perception, the task of automatically building a coordinated system is of crucial importance. To that end, we design simple reactive agents in a decentralized way as independent learners. But to cope with the difficulties inherent to RL used in that framework, we have developed an incremental learning algorithm where agents face a sequence of progressively more complex tasks. We illustrate this general framework by computer experiments where agents have to coordinate to reach a global goal. This work has been conducted in part in NICTA’s Canberra laboratory.