Robust rendezvous for mobile autonomous agents via proximity graphs in arbitrary dimensions

This paper presents coordination algorithms for networks of mobile autonomous agents. The objective of the proposed algorithms is to achieve rendezvous, that is, agreement over the location of the agents in the network. We provide analysis and design results for multiagent networks in arbitrary dimensions under weak requirements on the switching and failing communication topology. The novel correctness proof relies on proximity graphs and their properties and on a general LaSalle invariance principle for nondeterministic discrete-time dynamical systems.     

Coordinated learning by exploiting sparse interaction in multiagent systems

Multiagent learning provides a promising paradigm to study how autonomous agents learn to achieve coordinated behavior in multiagent systems. In multiagent learning, the concurrency of multiple distributed learning processes makes the environment nonstationary for each individual learner. Developing an efficient learning approach to coordinate agents’ behavior in this dynamic environment is a difficult problem especially when agents do not know the domain structure and at the same time have only local observability of the environment. In this paper, a coordinated learning approach is proposed to enable agents to learn where and how to coordinate their behavior in loosely coupled multiagent systems where the sparse interactions of agents constrain coordination to some specific parts of the environment. In the proposed approach, an agent first collects statistical information to detect those states where coordination is most necessary by considering not only the potential contributions from all the domain states but also the direct causes of the miscoordination in a conflicting state. The agent then learns to coordinate its behavior with others through its local observability of the environment according to different scenarios of state transitions. To handle the uncertainties caused by agents’ local observability, an optimistic estimation mechanism is introduced to guide the learning process of the agents. Empirical studies show that the proposed approach can achieve a better performance by improving the average agent reward compared with an uncoordinated learning approach and by reducing the computational complexity significantly compared with a centralized learning approach. Copyright © 2012 John Wiley & Sons, Ltd.     

Lyapunov-Based Approach to Multiagent Systems With Switching Jointly Connected Interconnection

This note addresses a coordination problem of a multiagent system with jointly connected interconnection topologies. Neighbor-based rules are adopted to realize local control strategies for these continuous-time autonomous agents described by double integrators. Although the interagent connection structures vary over time and related graphs may not be connected, a sufficient condition to make all the agents converge to a common value is given for the problem by a proposed Lyapunov-based approach and related space decomposition technique     

Opportunities for multiagent systems and multiagent reinforcement learning in traffic control

The increasing demand for mobility in our society poses various challenges to traffic engineering, computer science in general, and artificial intelligence and multiagent systems in particular. As it is often the case, it is not possible to provide additional capacity, so that a more efficient use of the available transportation infrastructure is necessary. This relates closely to multiagent systems as many problems in traffic management and control are inherently distributed. Also, many actors in a transportation system fit very well the concept of autonomous agents: the driver, the pedestrian, the traffic expert; in some cases, also the intersection and the traffic signal controller can be regarded as an autonomous agent. However, the “agentification” of a transportation system is associated with some challenging issues: the number of agents is high, typically agents are highly adaptive, they react to changes in the environment at individual level but cause an unpredictable collective pattern, and act in a highly coupled environment. Therefore, this domain poses many challenges for standard techniques from multiagent systems such as coordination and learning. This paper has two main objectives: (i) to present problems, methods, approaches and practices in traffic engineering (especially regarding traffic signal control); and (ii) to highlight open problems and challenges so that future research in multiagent systems can address them.     

GRADIS – The multiagent environment supported by graph transformations

The specification and simulation of a complex multiagent system needs an abstract representation that is powerful enough to describe a solved problem and sufficiently abstract to understand and illustrate its behavior. Complementary graphs concept enables the distribution of a graph representation of a system knowledge and allows its independent modifications by agents, in such a way that this representation remains consistent. A problem representation from the centralized and distributed point of view makes the partial graphs the useful tool for a multiagent system designer. It also creates an environment capable of verifying the features of multiagent systems (represented by graph metrics) by simulation of a multiagent system behavior.     

Zeus: A toolkit for building distributed multiagent systems

The multiagent systems approach of knowledge- level cooperation between autonomous agents promises significant benefits to distributed systems engineering, such as enhanced interoperability, scalability, and reconfigurability. However, thus far, because of the innate difficulty of constructing multiagent systems, this promise has been largely unrealized. Hence there is an emerging desire among agent developers to move away from developing point solutions to point problems in favor of developing methodologies and toolkits for building distributed multiagent systems. This philosophy led to the development of the ZEUS Agent Building Toolkit, which facilitates the rapid development of collaborative agent applications through the provision of a library of agent- level components and an environment to support the agent-building process. The ZEUS toolkit is a synthesis of established agent technologies with some novel solutions to provide an integrated collaborative agent-building environment.     

LEARNING AND COORDINATION FOR AUTONOMOUS INTERSECTION CONTROL

Future urban road traffic management is an example of a socially relevant problem that can be modeled as a large-scale, open, distributed system, composed of many autonomous interacting agents, which need to be controlled in a decentralized manner. In this context, advanced, reservation-based, intersection control—where autonomous vehicles controlled entirely by agents interact with a coordination facility that controls an intersection, to avoid collisions and minimize delays—will be a possible scenario in the near future. In this article, we seize the opportunities for multiagent learning offered by such a scenario, studying i) how vehicles, when approaching a reservation-based intersection, can coordinate their actions in order to improve their crossing times, and therefore, speed up the traffic flow through the intersection, and ii) how a set of reservation-based intersections can cooperatively act over an entire network of intersections in order to minimize travel times.     

Adaptive architectures for resilient control of networked multiagent systems in the presence of misbehaving agents

Control algorithms of networked multiagent systems are generally computed distributively without having a centralised entity monitoring the activity of agents; and therefore, unforeseen adverse conditions such as uncertainties or attacks to the communication network and/or failure of agent-wise components can easily result in system instability and prohibit the accomplishment of system-level objectives. In this paper, we study resilient coordination of networked multiagent systems in the presence of misbehaving agents, i.e. agents that are subject to exogenous disturbances that represent a class of adverse conditions. In particular, a distributed adaptive control architecture is presented for directed and time-varying graph topologies to retrieve a desired networked multiagent system behaviour. Apart from the existing relevant literature that make specific assumptions on the graph topology and/or the fraction of misbehaving agents, we show that the considered class of adverse conditions can be mitigated by the proposed adaptive control approach that utilises a local state emulator – even if all agents are misbehaving. Illustrative numerical examples are provided to demonstrate the theoretical findings.     

Modeling Agent Systems with Distributed Transformation Units

Agent systems have become more and more important in computer science. They allow to implement complex distributed systems composed of communicating autonomous entities. Transformation units constitute a structuring principle for graph transformation systems which split up large sets of rules, but still graphs are transformed as a whole. Recently, distributed transformation units have been introduced as an extension of transformation units to distributed graphs and distributed graph transformation. In this paper it is illustrated how different features of agent systems can be smoothly modeled in a uniform way by distributed graph transformation systems. For this purpose an agent system case study with simple agents communicating via blackboards and message passing is presented.     

Decentralized MDPs with sparse interactions

Creating coordinated multiagent policies in environments with uncertainty is a challenging problem, which can be greatly simplified if the coordination needs are known to be limited to specific parts of the state space. In this work, we explore how such local interactions can simplify coordination in multiagent systems. We focus on problems in which the interaction between the agents is sparse and contribute a new decision-theoretic model for decentralized sparse-interaction multiagent systems, Dec-SIMDPs, that explicitly distinguishes the situations in which the agents in the team must coordinate from those in which they can act independently. We relate our new model to other existing models such as MMDPs and Dec-MDPs. We then propose a solution method that takes advantage of the particular structure of Dec-SIMDPs and provide theoretical error bounds on the quality of the obtained solution. Finally, we show a reinforcement learning algorithm in which independent agents learn both individual policies and when and how to coordinate. We illustrate the application of the algorithms throughout the paper in several multiagent navigation scenarios.     

Learning Coordination Strategies for Cooperative Multiagent Systems

A central issue in the design of cooperative multiagent systems is how to coordinate the behavior of the agents to meet the goals of the designer. Traditionally, this had been accomplished by hand-coding the coordination strategies. However, this task is complex due to the interactions that can take place among agents. Recent work in the area has focused on how strategies can be learned. Yet, many of these systems suffer from convergence, complexity and performance problems. This paper presents a new approach for learning multiagent coordination strategies that addresses these issues. The effectiveness of the technique is demonstrated using a synthetic domain and the predator and prey pursuit problem.     

CAMAS: A cluster-aware multiagent system for attributed graph clustering

Attributed graphs describe nodes via attribute vectors and also relationships between different nodes via edges. To partition nodes into clusters with tighter correlations, an effective way is applying clustering techniques on attributed graphs based on various criteria such as node connectivity and/or attribute similarity. Even though clusters typically form around nodes with tight edges and similar attributes, existing methods have only focused on one of these two data modalities. In this paper, we comprehend each node as an autonomous agent and develop an accurate and scalable multiagent system for extracting overlapping clusters in attributed graphs. First, a kernel function with a tunable bandwidth factor δ is introduced to measure the influence of each agent, and those agents with highest local influence can be viewed as the “leader” agents. Then, a novel local expansion strategy is proposed, which can be applied by each leader agent to absorb the most relevant followers in the graph. Finally, we design the cluster-aware multiagent system (CAMAS), in which agents communicate with each other freely under an efficient communication mechanism. Using the proposed multiagent system, we are able to uncover the optimal overlapping cluster configuration, i.e. nodes within one cluster are not only connected closely with each other but also with similar attributes. Our method is highly efficient, and the computational time is shown that nearly linearly dependent on the number of edges when δ ∈ [0.5, 1). Finally, applications of the proposed method on a variety of synthetic benchmark graphs and real-life attributed graphs are demonstrated to verify the systematic performance.     

ANOMALY DETECTION IN DISTRIBUTED COMPUTER COMMUNICATION SYSTEMS

Anomaly detection is a basic functionality of intrusion detection systems. The aim of such systems in distributed computer communication systems is to recognize and notify about various events that influence a system's security. In a gain to assure efficiency, flexibility, and a quality of detection of systems security violation in a distributed environment, required detection systems should be responsive, adaptive, proactive, and less centralized than those currently deployed. Such required properties are offered by agents and multiagent systems, i.e., agent-based technology has the continuously increasing potential to offer a solution to the growing problem of designing intelligent, efficient, and flexible management systems. An agent-based approach offers the potential to develop advanced and effective distributed, network-based strategies replacing traditional node-based approaches by more perspective network-based approaches.

This article is devoted to present various architectures of anomaly detection systems, which may be implemented as multiagent systems supporting the classification of observed activities as normal or abnormal. Some simple example presents hierarchical architecture of a distributed anomaly detection system, which may be implemented in the form of a multiagent decision supporting system.     

Distributed nonlinear control algorithms for network consensus

In this paper, we develop a thermodynamic framework for addressing consensus problems for nonlinear multiagent dynamical systems with fixed and switching topologies. Specifically, we present distributed nonlinear static and dynamic controller architectures for multiagent coordination. The proposed controller architectures are predicated on system thermodynamic notions resulting in controller architectures involving the exchange of information between agents that guarantee that the closed-loop dynamical network is consistent with basic thermodynamic principles.     

Biotope: an integrated framework for simulating distributed multiagent computational systems

The study of distributed computational systems issues, such as heterogeneity, concurrency, control, and coordination, has yielded a number of models and architectures, which aspire to provide satisfying solutions to each of the above problems. One of the most intriguing and complex classes of distributed systems are computational ecosystems, which add an "ecological" perspective to these issues and introduce the characteristic of self-organization. Extending previous research work on self-organizing communities, we have developed Biotope, which is an agent simulation framework, where each one of its members is dynamic and self-maintaining. The system provides a highly configurable interface for modeling various environments as well as the "living" or computational entities that reside in them, while it introduces a series of tools for monitoring system evolution. Classifier systems and genetic algorithms have been employed for agent learning, while the dispersal distance theory has been adopted for agent replication. The framework has been used for the development of a characteristic demonstrator, where Biotope agents are engaged in well-known vital activities-nutrition, communication, growth, death-directed toward their own self-replication, just like in natural environments. This paper presents an analytical overview of the work conducted and concludes with a methodology for simulating distributed multiagent computational systems.     

Computational-mechanism design: a call to arms

Computational-mechanism design has an important role to play in developing complex distributed systems comprising multiple interacting agents. Game theory has developed powerful tools for analyzing, predicting, and controlling the behavior of self-interested agents and decision making in systems with multiple autonomous actors. These tools, when tailored to computational settings, provide a foundation for building multiagent software systems. This tailoring gives rise to the field of computational-mechanism design, which applies economic principles to computer systems design.     

基于特定角色上下文的多智能体Q学习

One of the main problems in cooperative multiagent learning is that the joint action space grows exponentially with the number of agents. In this paper, we investigate a sparse representation of the coordination dependencies between agents to employ roles and context-specific coordination graphs to reduce the joint action space. In our framework, the global joint Q-function is decomposed into a number of local Q-functions. Each local Q-function is shared among a small group of agents and is composed of a set of value rules. We propose a novel multiagent Q-learning algorithm which learns the weights in each value rule automatically. We give empirical evidence to show that our learning algorithm converges to the same optimal policy with a significantly faster speed than traditional multiagent learning techniques.     

Online algorithms supporting emergence in distributed CAD systems

The rule-based approach from traditional AI and the conventional constraint satisfaction algorithms are not adequate to cope with the unpredictable events and interactive computations in distributed CAD environments. This paper claims that the problems faced by distributed CAD systems require solutions based on the concepts of emergence, reactivity, and online algorithms. The present paper presents Extended Constraints Graphs (ECGs) as online algorithms supporting emergence in a network of reactive agents. ECGs represent an effective solution for the nonlinear constraint problem in cyclic graphs, which are distributed over a heterogeneous computer network. The relationships between agents in an ECG are generic, distributed, recursive and nonlinear — a problem not solved in the literature. Also this paper presents a CORBA model integrated with a Geometry Bus to support distributed virtual prototype whose variables can be defined in terms of ECGs.     

Autonomous Agents that Learn to Better Coordinate

A fundamental difficulty faced by groups of agents that work together is how to efficiently coordinate their efforts. This coordination problem is both ubiquitous and challenging, especially in environments where autonomous agents are motivated by personal goals.Previous AI research on coordination has developed techniques that allow agents to act efficiently from the outset based on common built-in knowledge or to learn to act efficiently when the agents are not autonomous. The research described in this paper builds on those efforts by developing distributed learning techniques that improve coordination among autonomous agents.The techniques presented in this work encompass agents who are heterogeneous, who do not have complete built-in common knowledge, and who cannot coordinate solely by observation. An agent learns from her experiences so that her future behavior more accurately reflects what works (or does not work) in practice. Each agent stores past successes (both planned and unplanned) in their individual casebase. Entries in a casebase are represented as coordinated procedures and are organized around learned expectations about other agents.It is a novel approach for individuals to learn procedures as a means for the group to coordinate more efficiently. Empirical results validate the utility of this approach. Whether or not the agents have initial expertise in solving coordination problems, the distributed learning of the individual agents significantly improves the overall performance of the community, including reducing planning and communication costs.     

Learning in groups of traffic signals

Computer science in general, and artificial intelligence and multiagent systems in particular, are part of an effort to build intelligent transportation systems. An efficient use of the existing infrastructure relates closely to multiagent systems as many problems in traffic management and control are inherently distributed. In particular, traffic signal controllers located at intersections can be seen as autonomous agents. However, challenging issues are involved in this kind of modeling: the number of agents is high; in general agents must be highly adaptive; they must react to changes in the environment at individual level while also causing an unpredictable collective pattern, as they act in a highly coupled environment. Therefore, traffic signal control poses many challenges for standard techniques from multiagent systems such as learning. Despite the progress in multiagent reinforcement learning via formalisms based on stochastic games, these cannot cope with a high number of agents due to the combinatorial explosion in the number of joint actions. One possible way to reduce the complexity of the problem is to have agents organized in groups of limited size so that the number of joint actions is reduced. These groups are then coordinated by another agent, a tutor or supervisor. Thus, this paper investigates the task of multiagent reinforcement learning for control of traffic signals in two situations: agents act individually (individual learners) and agents can be “tutored”, meaning that another agent with a broader sight will recommend a joint action.