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.     

Finite-time coordination in multiagent systems using sliding mode control approach

Finite-time stability in dynamical systems theory involves systems whose trajectories converge to an equilibrium state in finite time. In this paper, we use the notion of finite-time stability to apply it to the problem of coordinated motion in multiagent systems. Specifically, we consider a group of agents described by fully actuated Euler–Lagrange dynamics along with a leader agent with an objective to reach and maintain a desired formation characterized by steady-state distances between the neighboring agents in finite time. We use graph theoretic notions to characterize communication topology in the network determined by the information flow directions and captured by the graph Laplacian matrix. Furthermore, using sliding mode control approach, we design decentralized control inputs for individual agents that use only data from the neighboring agents which directly communicate their state information to the current agent in order to drive the current agent to the desired steady state. Sliding mode control is known to drive the system states to the sliding surface in finite time. The key feature of our approach is in the design of non-smooth sliding surfaces such that, while on the sliding surface, the error states converge to the origin in finite time, thus ensuring finite-time coordination among the agents in the network. In addition, we discuss the case of switching communication topologies in multiagent systems. Finally, we show the efficacy of our theoretical results using an example of a multiagent system involving planar double integrator agents.     

Infrastructures for the environment of multiagent systems

The notion of environment is receiving an increasing attention in the development of multiagent applications. This is witnessed by the emergence of a number of infrastructures providing agent designers with useful means to develop the agent environment, and thus to structure an effective multiagent application. In this paper we analyse the role and features of such infrastructures, and survey some relevant examples. We endorse a general viewpoint where the environment of a multiagent system is seen as a set of basic bricks we call environment abstractions, which (i) provide agents with services useful for achieving individual and social goals, and (ii) are supported by some underlying software infrastructure managing their creation and exploitation. Accordingly, we focus the survey on the opportunities that environment infrastructures provide to system designers when developing multiagent applications.     

On consensus protocols for high-order multiagent systems

In this paper, the static consensus problem and the dynamic consensus problem are considered for a class of high-order multiagent systems. With the proposed consensus protocols, necessary and sufficient conditions for the consensus problems are obtained. For the static consensus protocol, the desired consensus speed can be achieved by adjusting feedback gains. Simulations show the effectiveness of the proposed consensus protocols.     

Emergence of multiagent spatial coordination strategies through artificial coevolution

This paper describes research investigating the evolution of coordination strategies in robot soccer teams. Each player (viewed as an agent) is provided with a common set of skills and is assigned to perform over a delimited area inside a soccer field. The idea is to optimize the whole team behavior by means of a spatial coadaptation process in which new players are selected in such a way to comply with the already existing ones. The main results show that, through coevolution, we progressively create teams whose members act on complementary areas of the playing field, being capable of prevailing over a standard opponent team with a fixed formation.     

hGA: Hybrid genetic algorithm in fuzzy rule-based classification systems for high-dimensional problems

The aim of this work is to propose a hybrid heuristic approach (called hGA) based on genetic algorithm (GA) and integer-programming formulation (IPF) to solve high dimensional classification problems in linguistic fuzzy rule-based classification systems. In this algorithm, each chromosome represents a rule for specified class, GA is used for producing several rules for each class, and finally IPF is used for selection of rules from a pool of rules, which are obtained by GA. The proposed algorithm is experimentally evaluated by the use of non-parametric statistical tests on seventeen classification benchmark data sets. Results of the comparative study show that hGA is able to discover accurate and concise classification rules.     

Consensus of multiagent systems based on disturbance observer

The objectives of this work are the development and design of disturbance observers (DO’s) for a team of agents that accomplish consensus on agents’ states in the presence of exogenous disturbances. A pinning control strategy is designed for a part of agents of the multiagent systems without disturbances, and this pinning control can bring multiple agents’ states to reaching an expected consensus value. Under the effect of the disturbances, nonlinear disturbance observers are developed for disturbances generated by an exogenous system to estimate the disturbances. Asymptotical consensus of the multiagent systems with disturbances under the composite controller can be achieved. Finally, by applying an example of multiagent systems with switching topologies and exogenous disturbances, the design of the parameters of DO’s are illuminated.     

A familiarity-based trust model for effective selection of sellers in multiagent e-commerce systems

In electronic marketplaces, trust is modeled, for instance, in order to allow buying agents to make effective selection of selling agents. Familiarity is often considered to be an important factor in determining the level of trust. In previous research, familiarity between two agents has been simply assumed to be the similarity between them. We propose an improved familiarity measurement based on the exploration of factors that affect a human’s feelings of familiarity. We also carry out experiments to show that the trust model with our improved familiarity measurement is more effective and more stable.     

TRAMMAS: A tracing model for multiagent systems

Agent's flexibility and autonomy, as well as their capacity to coordinate and cooperate, are some of the features which make multiagent systems useful to work in dynamic and distributed environments. These key features are directly related to the way in which agents communicate and perceive each other, as well as their environment and surrounding conditions. Traditionally, this has been accomplished by means of message exchange or by using blackboard systems. These traditional methods have the advantages of being easy to implement and well supported by multiagent platforms; however, their main disadvantage is that the amount of social knowledge in the system directly depends on every agent actively informing of what it is doing, thinking, perceiving, etc. There are domains, for example those where social knowledge depends on highly distributed pieces of data provided by many different agents, in which such traditional methods can produce a great deal of overhead, hence reducing the scalability, efficiency and flexibility of the multiagent system. This work proposes the use of event tracing in multiagent systems, as an indirect interaction and coordination mechanism to improve the amount and quality of the information that agents can perceive from both their physical and social environment, in order to fulfill their goals more efficiently. In order to do so, this work presents an abstract model of a tracing system and an architectural design of such model, which can be incorporated to a typical multiagent platform.     

Improving the performance of fuzzy rule-based classification systems with interval-valued fuzzy sets and genetic amplitude tuning

Among the computational intelligence techniques employed to solve classification problems, Fuzzy Rule-Based Classification Systems (FRBCSs) are a popular tool because of their interpretable models based on linguistic variables, which are easier to understand for the experts or end-users.The aim of this paper is to enhance the performance of FRBCSs by extending the Knowledge Base with the application of the concept of Interval-Valued Fuzzy Sets (IVFSs). We consider a post-processing genetic tuning step that adjusts the amplitude of the upper bound of the IVFS to contextualize the fuzzy partitions and to obtain a most accurate solution to the problem.We analyze the goodness of this approach using two basic and well-known fuzzy rule learning algorithms, the Chi et al.’s method and the fuzzy hybrid genetics-based machine learning algorithm. We show the improvement achieved by this model through an extensive empirical study with a large collection of data-sets.     

Developing multiagent systems for design activity analysis

Engineering design is a complex socio-technical activity characterized by co-evolution of problem and solution. However, the actual design theories are not well-suited to represent and model the complexity of design activity, the co-evolution and its dynamics. Therefore, there is a need to develop design activity reasoning theories and tools, which can theorize and simulate the model of co-evolution and its dynamics. Multiagent systems have the capacity to play an important role in developing and analyzing models and theories of interactivity in socio-technical societies, particularly in design. This paper first addresses a theory for design activity reasoning. Then, it will present a multiagent system, called ADEA (Agents-based DEsign activity Analysis), in order to model, simulate and analyze this theory. The agents of the ADEA platform formalize the necessary design roles, characterizing the design activity as well as the relationship between design parameters in the design space. ADEA’s platform shows that cognitive limitation of role agents has been overcome, considering their relationship with the design space modeled as a network of design parameter agents.     

Consensus seeking in multiagent cooperative control systems with bounded control input

Consensus algorithms in multiagent cooperative control systems with bounded control input are studied in this paper.Consensus algorithms are considered for the single-integrator dynamics and double-integrator dynamics under different communication interaction topologies,and show that consensus is reached asymptotically using the algorithm proposed in this paper for the single-integrator dynamics if the undirected interaction graph is connected,and consensus is reached asymptotically if the directed interaction graph is strongly connected,respectively.In addition,the paper further shows that consensus is reached asymptotically using the algorithm proposed for the double-integrator dynamics if the directed interaction graph is strongly connected.The effectiveness of these algorithms is demonstrated through simulations.     

Goal and predictive coordination in two level hierarchical systems

The multilevel system theory applies two general methods of coordination, which influences the manner of subsystem management—goal and predictive coordinations. Both these general types of coordination perform multiple data transfer between the hierarchical levels and delay the evaluation and implementation of a global optimal solution of a control problem. The paper demonstrates a coordination policy, which decreases the information transfer in the hierarchical system, titled “noniterative” coordination. The last is developed both for goal and predictive coordination strategies. The mathematical foundations of these two noniterative coordination strategies are presented. Comparative analysis is performed to identify peculiarities and drawbacks for the real time management of two level hierarchical systems. Assessment of the computational workload and speed of the coordination, expressed as “flops” numbers is done for the case of nonlinear optimization problems. Both the noniterative coordination strategies benefit the real time operation in the multilevel system by reducing the iterative computations and the data transfer between the hierarchical levels. The predictive coordination has potential in speeding the management process and resource allocation, due to the decomposition approach, which is applied.     

Evaluating software engineering techniques for developing complex systems with multiagent approaches

Context

Multiagent systems (MAS) allow complex systems to be developed in which autonomous and heterogeneous entities interact. Currently, there are a great number of methods and frameworks for developing MAS. The selection of one or another development environment is a crucial part of the development process. Therefore, the evaluation and comparison of MAS software engineering techniques is necessary in order to make the selection of the development environment easier.

Objective

The main goal of this paper is to define an evaluation framework that will help in facilitating, standardizing, and simplifying the evaluation, analysis, and comparison of MAS development environments. Moreover, the final objective of the proposed tool is to provide a repository of the most commonly used MAS software engineering methods and tools.

Method

The proposed framework analyzes methods and tools through a set of criteria that are related to both system engineering dimensions and MAS features. Also, the support for developing organizational and service-oriented MAS is studied. This framework is implemented as an online application to improve its accessibility.

Results

In this paper, we present Masev, which is an evaluation framework for MAS software engineering. It allows MAS methods, techniques and environments to be analyzed and compared. A case study of the analysis of four methodologies is presented.

Conclusion

It is concluded that Masev simplifies the evaluation and comparison task and summarizes the most important issues for developing MAS, organizational MAS, and service-oriented MAS. Therefore, it could help developers to select the most appropriate MAS method and tools for developing a specific system, and it could be used for MAS software engineering developers to detect and deficiencies in their methods and tools. Also, developers of new tools can understand this application as a way to publish their tools and demonstrate what their contributions are to the state of the art.     

Genetic fuzzy systems to evolve interaction strategies in multiagent systems

This article suggests an evolutionary approach to designing interaction strategies for multiagent systems, focusing on strategies modeled as fuzzy rule‐based systems. The aim is to learn models evolving database and rule bases to improve agent performance when playing in a competitive environment. In competitive situations, data for learning and tuning are rare, and rule bases must jointly evolve with the databases. We introduce an evolutionary algorithm whose operators use variable length chromosomes, a hierarchical relationship among individuals through fitness, and a scheme that successively explores and exploits the search space along generations. Evolution of interaction strategies uncovers unknown and unexpected agent behaviors and allows a richer analysis of negotiation mechanisms and their role as a coordination protocol. An application concerning an electricity market illustrates the effectiveness of the approach. © 2007 Wiley Periodicals, Inc. Int J Int Syst 22: 971–991, 2007.     

Formation and obstacle avoidance control for multiagent systems

This paper considers the problems of formation and obstacle avoidance for multiagent systems.The objective is to design a term of agents that can reach a desired formation while avoiding collision with obstacles.To reduce the amount of information interaction between agents and target,we adopt the leader-follower formation strategy.By using the receding horizon control (RHC),an optimal problem is formulated in terms of cost minimization under constraints.Information on obstacles is incorporated online as sensed in a limited sensing range.The communication requirements between agents are that the followers should obtain the previous optimal control trajectory of the leader to each update time.The stability is guaranteed by adding a terminal-state penalty to the cost function and a terminal-state region to optimal problem.Finally,simulation studies are provided to verify the effectiveness of the proposed approach.     

Introduction to the special issue on normative multiagent systems

This special issue contains four selected and revised papers from the second international workshop on normative multiagent systems, for short NorMAS07 (Boella et al. (eds) Normative multiagent systems. Dagstuhl seminar proceedings 07122, 2007), held at Schloss Dagstuhl, Germany, in March 2007. At the workshop a shift was identified in the research community from a legal to an interactionist view on normative multiagent systems. In this editorial we discuss the shift, examples, and 10 new challenges in this more dynamic setting, which we use to introduce the papers of this special issue.     

MAGAD-BFS: A learning method for Beta fuzzy systems based on a multi-agent genetic algorithm

This paper proposes a learning method for Beta fuzzy systems (BFS) based on a multiagent genetic algorithm. This method, called Multi-Agent Genetic Algorithm for the Design of BFS has two advantages. First, thanks to genetic algorithms (GA) efficiency, it allows to design a suitable and precise model for BFS. Second, it improves the GA convergence by reducing rule complexity thanks to the distributed implementation by multi-agent approach. Dynamic agents interact to provide an optimal solution in order to obtain the best BFS reaching the balance interpretability-precision. The performance of the method is tested on a simulated example.     

Fully distributed consensus for fuzzy multiagent systems with jointly connected topology

This paper investigates the problem of fully distributed consensus for polynomial fuzzy multiagent systems (MASs) under jointly connected topologies. First, a polynomial fuzzy modeling method is presented to characterize the error dynamics that is constructed by one leader and multiple followers. Then, using the relative state information and the agents' dynamics, a distributed adaptive protocol is designed to guarantee that MASs under jointly connected topologies can achieve consensus in a fully distributed fashion. Utilizing the Lyapunov technique, a relaxed sufficient criterion is proposed to ensure consensus for fuzzy MASs under jointly connected topologies. Moreover, the adaptive coupling weights between neighboring agents can converge to certain values. The derived condition is transformed into a sum-of-squares form, which can be solved numerically. We provide an example to illustrate the proposed distributed adaptive consensus technique's validity.     

A layered approach to learning coordination knowledge in multiagent environments

Multiagent learning involves acquisition of cooperative behavior among intelligent agents in order to satisfy the joint goals. Reinforcement Learning (RL) is a promising unsupervised machine learning technique inspired from the earlier studies in animal learning. In this paper, we propose a new RL technique called the Two Level Reinforcement Learning with Communication (2LRL) method to provide cooperative action selection in a multiagent environment. In 2LRL, learning takes place in two hierarchical levels; in the first level agents learn to select their target and then they select the action directed to their target in the second level. The agents communicate their perception to their neighbors and use the communication information in their decision-making. We applied 2LRL method in a hunter-prey environment and observed a satisfactory cooperative behavior. Guray Erus received the B.S. degree in computer engineering in 1999, and the M.S. degree in cognitive sciences, in 2002, from Middle East Technical University (METU), Ankara, Turkey. He is currently a teaching and research assistant in Rene“ Descartes University, Paris, France, where he prepares a doctoral dissertation on object detection on satellite images, as a member of the intelligent perception systems group (SIP-CRIP5). His research interests include multi-agent systems and image understanding. Faruk Polat is a professor in the Department of Computer Engineering of Middle East Technical University, Ankara, Turkey. He received his B.Sc. in computer engineering from the Middle East Technical University, Ankara, in 1987 and his M.S. and Ph.D. degrees in computer engineering from Bilkent University, Ankara, in 1989 and 1993, respectively. He conducted research as a visiting NATO science scholar at Computer Science Department of University of Minnesota, Minneapolis in 1992–93. His research interests include artificial intelligence, multi-agent systems and object oriented data models.