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.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

Infrastructures and tools for multiagent systems for the new generation of distributed systems

In order for multiagent systems to be included in real domains (media and Internet, logistics, e-commerce, and health care), infrastructures and tools for multiagent systems should provide efficiency, scalability, security, management, monitoring, and other features related to building real applications. Thus, infrastructures and tools that support multiagent systems are needed, especially those that promote the adoption of agent-based systems by designers and programmers in both academia and industry. This special issue is a selection of contributions whose preliminary versions were presented at the ITMAS 2010 workshop, which was held in conjunction with the International Conference on Autonomous Agents and Multi-agent Systems.     

Simple models of coevolutionary genetic algorithms

The use of evolutionary computing techniques in coevolutionary/multiagent systems is becoming increasingly popular. This paper presents some simple models of the genetic algorithm in such systems, with the aim of examining the effects of different types of interdependence between individuals. Using the models, it is shown that for a fixed amount of interdependence between homogeneous coevolving individuals, the existence of partner gene variance, gene symmetry, and the level at which fitness is applied can have significant effects. Similarly, for heterogeneous coevolving systems with fixed interdependence, partner gene variance and fitness application are also found to have a significant effect, as is the partnering strategy used.     

An optimization method for designing type-2 fuzzy inference systems based on the footprint of uncertainty using genetic algorithms

This paper proposes an optimization method for designing type-2 fuzzy inference systems based on the footprint of uncertainty (FOU) of the membership functions, considering three different cases to reduce the complexity problem of searching the parameter space of solutions. For the optimization method, we propose the use of a genetic algorithm (GA) to optimize the type-2 fuzzy inference systems, considering different cases for changing the level of uncertainty of the membership functions to reach the optimal solution at the end.     

Locality-sensitive task allocation and load balancing in networked multiagent systems: Talent versus centrality

With the development of large scale multiagent systems, agents are always organized in network structures where each agent interacts only with its immediate neighbors in the network. Coordination among networked agents is a critical issue which mainly includes two aspects: task allocation and load balancing; in traditional approach, the resources of agents are crucial to their abilities to get tasks, which is called talent-based allocation. However, in networked multiagent systems, the tasks may spend so much communication costs among agents that are sensitive to the agent localities; thus this paper presents a novel idea for task allocation and load balancing in networked multiagent systems, which takes into account both the talents and centralities of agents. This paper first investigates the comparison between talent-based task allocation and centrality-based one; then, it explores the load balancing of such two approaches in task allocation. The experiment results show that the centrality-based method can reduce the communication costs for single task more effectively than the talent-based one, but the talent-based method can generally obtain better load balancing performance for parallel tasks than the centrality-based one.     

Sliding mode coordination control for multiagent systems with underactuated agent dynamics

In this paper, we develop a new integrated coordinated control and obstacle avoidance approach for a general class of underactuated agents. We use graph-theoretic notions to characterise communication topology in the network of underactuated agents as determined by the information flow directions and captured by the graph Laplacian matrix. Obstacle avoidance is achieved by surrounding the stationary as well as moving obstacles by elliptical or other convex shapes that serve as stable periodic solutions to planar systems of ordinary differential equations and using transient trajectories of those systems to navigate the agents around the obstacles. Decentralised controllers for individual agents are designed using sliding mode control approach and are only based on data communicated from the neighbouring agents. We demonstrate the efficacy of our theoretical approach using an example of a system of wheeled mobile robots that reach and maintain a desired formation. Finally, we validate our results experimentally.     

A genetic fuzzy expert system for automatic question classification in a competitive learning environment

Intelligent tutoring systems are efficient tools to automatically adapt the learning process to the student’s progress and needs. One of the possible adaptations is to apply an adaptive question sequencing system, which matches the difficulty of the questions to the student’s knowledge level. In this context, it is important to correctly classify the questions to be presented to students according to their difficulty level. Many systems have been developed for estimating the difficulty of questions. However the variety in the application environments makes difficult to apply the existing solutions directly to other applications. Therefore, a specific solution has been designed in order to determine the difficulty level of open questions in an automatic and objective way. This solution can be applied to activities with special temporal and running features, as the contests developed through QUESTOURnament, which is a tool integrated into the e-learning platform Moodle. The proposed solution is a fuzzy expert system that uses a genetic algorithm in order to characterize each difficulty level. From the output of the algorithm, it defines the fuzzy rules that are used to classify the questions. Data registered from a competitive activity in a Telecommunications Engineering course have been used in order to validate the system against a group of experts. Results show that the system performs successfully. Therefore, it can be concluded that the system is able to do the questions classification labour in a competitive learning environment.     

Detection of doors using a genetic visual fuzzy system for mobile robots

Doors are common objects in indoor environments and their detection can be used in robotic tasks such as map-building, navigation and positioning. This work presents a new approach to door-detection in indoor environments using computer vision. Doors are found in gray-level images by detecting the borders of their architraves. A variation of the Hough Transform is used in order to extract the segments in the image after applying the Canny edge detector. Features like length, direction, or distance between segments are used by a fuzzy system to analyze whether the relationship between them reveals the existence of doors. The system has been designed to detect rectangular doors typical of many indoor environments by the use of expert knowledge. Besides, a tuning mechanism based on a genetic algorithm is proposed to improve the performance of the system according to the particularities of the environment in which it is going to be employed. A large database of images containing doors of our building, seen from different angles and distances, has been created to test the performance of the system before and after the tuning process. The system has shown the ability to detect rectangular doors under heavy perspective deformations and it is fast enough to be used for real-time applications in a mobile robot.     

Optimization of fuzzy partitions for inductive reasoning using genetic algorithms

Fuzzy Inductive Reasoning (FIR) is a data-driven methodology that uses fuzzy and pattern recognition techniques to infer system models and to predict their future behavior. It is well known that variations on fuzzy partitions have a direct effect on the performance of the fuzzy-rule-based systems. The FIR methodology is not an exception. The performance of the model identification and prediction processes of FIR is highly influenced by the discretization parameters of the system variables, i.e. the number of classes of each variable and the membership functions that define its semantics. In this work, we design two new genetic fuzzy systems (GFSs) that improve this modeling and simulation technique. The main goal of the GFSs is to learn the fuzzification parameters of the FIR methodology. The new approaches are applied to two real modeling problems, the human central nervous system and an electrical distribution problem.     

Application and development of biologically plausible neural networks in a multiagent artificial life system

The present article introduces the system BioAnt, which is a computational simulation of a small colony of ants (up to 99 members) in which every ant relies on a biologically more plausible artificial neural networks as control mechanism for guidance. The environment, in which the ants are placed, is three-dimensional, consisting of the anthill, sugar, water, earth elevations, walls and predators. The ants’ foraging behavior was successfully implemented as well as some basic defense mechanisms. Typical sensors and actuators of ants were modeled and the efficiency of the connectionist approach has been validated by the comparison with a simple symbolical approach. Apart from several surprising results on technical details, which are reported, the present approach clearly demonstrates the feasibility of such an implementation with connectionist and biologically more plausible principles, offering promising perspectives as a basis for further artificial life systems.