Evaluating fault tolerance approaches in multi-agent systems

A multi-agent system (MAS) is a distributed system that consists of multiple agents working together to solve mutual problems. Even though MASs are well suited for the development of complex distributed systems, the number of real-world usages is still small. One of the main reasons for this is that MASs are very fragile. In a typical, large-scale MAS, the rate of failure grows with the number of hosts, the number of deployed agents, and the duration of the agent’s task execution. For this reason, numerous approaches have been introduced to deal with aspects of failure handling. However, the absence of centralized control and a large number of individual intelligent components makes it difficult to detect and treat errors. The risk of uncontrollable fault propagation is high and can seriously impact on system performance. There are two important factors that limit the usage of MASs: (1) existing fault tolerance (FT) approaches are not generic, as they focus on and improve specific issues of FT; and (2) despite the plethora of available FT approaches and theories, there is a remarkable lack of general metrics, tools, benchmarks, and experimental methods for formal validation and comparison of existing or newly developed FT approaches. As FT approaches in MASs become a well-established field, the need for generalized, standardized evaluation of FT approaches emerges as imperative. In this paper, we first present a detailed overview of existing FT solutions, approaches, and techniques in agent platform hosted MASs. From that overview, we derive the commonalities in existing research. Next, we present the main contribution of our paper: an evaluation methodology, with a set of metrics, for comparing FT approaches in MASs. We adopt an engineering perspective on the problem, defining a methodology and metrics that are both implementation- and domain-independent. The metrics are formalized with an acyclic directed graph. By using our methodology, evaluators can select an appropriate FT approach for targeted MAS application, thus improving MAS usability, stability, and development speed. In order to show the viability of our approach, a case study that compares two FT approaches for a targeted MAS is presented. The case study results show that our methodology can be used for selecting an appropriate FT approach for the targeted MAS.     

Robust design of multi-agent system interactions: A testing approach based on pattern matching

The definition of protocols between agents is not enough for guaranteeing the absence of undesirable communication in organizations and the presence of desirable ones in large multi-agent systems (MASs). This is a consequence of the complex system nature of MASs, which cause sophisticated behaviors to arise out of a multiplicity of relatively simple interactions among the independent agents composing them. With this motivation, this paper presents an approach for testing communication in MAS architectures. In this approach, designers are not only recommended to specify the desired communication protocols, but also the undesired patterns and organization structures in the agents’ communications, allowing designers to define robust communication structures. For this purpose, this work presents (1) a language to define such patterns; (2) a set of already defined desired and undesired patterns which usually appear in general MASs; (3) a tool that allows developers to automatically detect these patterns in logs of MAS executions; and (4) a guideline that takes developers through the testing of the communications in MASs. The current approach is experienced with a case study, and the results show that the application of the current approach and the suppression of detected undesired patterns improve the effectiveness and efficiency of the corresponding MAS.     

A recursive genetic framework for evolutionary decision-making in problems with high dynamism

Communication and coordination are the main cores for reaching a constructive agreement among multi-agent systems (MASs). Dividing the overall performance of MAS to individual agents may lead to group learning as opposed to individual learning, which is one of the weak points of MASs. This paper proposes a recursive genetic framework for solving problems with high dynamism. In this framework, a combination of genetic algorithm and multi-agent capabilities is utilised to accelerate team learning and accurate credit assignment. The argumentation feature is used to accomplish agent learning and the negotiation features of MASs are used to achieve a credit assignment. The proposed framework is quite general and its recursive hierarchical structure could be extended. We have dedicated one special controlling module for increasing convergence time. Due to the complexity of blackjack, we have applied it as a possible test bed to evaluate the system’s performance. The learning rate of agents is measured as well as their credit assignment. The analysis of the obtained results led us to believe that our robust framework with the proposed negotiation operator is a promising methodology to solve similar problems in other areas with high dynamism.     

A values‐driven self‐organization mechanism for automating multiagent coordination

In distributed and open environments, MASs (multiagent systems) generally have no mechanisms for prior coordination and self‐organization has been believed to be the necessary selection to achieve the coordination of agents. This paper first presents a values‐driven model for self‐organization in which the expected emergent properties of a system are specified as the social values while the social values are realized via implicitly inducing members to regulate their individual values and adjust their behaviors to fit the expectations of the system. Based on the values‐driven self‐organization, this paper proposes an automated coordination mechanism for decentralized MASs. In this mechanism, by indirectly changing the difficulties in acquiring resources (which may be delegated to some special agents since MASs generally do not have substantial bodies), MASs can lead agents to regulate their values to be consistent with the social values of MASs so that the coordination of MASs can spontaneously emerge from the local behaviors of agents. Finally, this paper implements a simulation traffic system using the coordination mechanism based on values‐driven self‐organization to validate the emergence of coordination among multiple agents.     

Agents in object‐oriented software engineering

Software engineers of multi‐agent systems (MASs) are faced with different concerns such as autonomy, adaptation, interaction, collaboration, learning, and mobility, which are essentially different from classical concerns addressed in object‐oriented software engineering. MAS developers, however, have relied mostly on object‐oriented design techniques and programming languages, such as Java. This often leads to a poor separation of MAS concerns and in turn to the production of MASs that are difficult to maintain and reuse. This paper discusses software engineering approaches for MASs, and presents a new method for integrating agents into object‐oriented software engineering from an early stage of design. The proposed approach encourages the separate handling of MAS concerns, and provides a disciplined scheme for their composition. Our proposal explores the benefits of aspect‐oriented software development for the incorporation of agents into object‐oriented systems. We also illustrate our aspect‐oriented approach through the Portalware multi‐agent system, a Web‐based environment for the development of e‐commerce portals. Copyright © 2004 John Wiley & Sons, Ltd.     

Software experience when using ontologies in a multi‐agent system for automated planning and scheduling

The main aim of this paper is to present the software experience when using multi‐agent systems (MASs) and ontologies in the development of a sample application. In particular, the authors have implemented a MAS for the planning and scheduling of a University Research Group. This MAS, called MASplan, should help group members to find the best possible time frames to hold a meeting and to designate the use of common resources. Copyright © 2006 John Wiley & Sons, Ltd.     

Predicting the Expected Behavior of Agents that Learn About Agents: The CLRI Framework

We describe a framework and equations used to model and predict the behavior of multi-agent systems (MASs) with learning agents. A difference equation is used for calculating the progression of an agent's error in its decision function, thereby telling us how the agent is expected to fare in the MAS. The equation relies on parameters which capture the agent's learning abilities, such as its change rate, learning rate and retention rate, as well as relevant aspects of the MAS such as the impact that agents have on each other. We validate the framework with experimental results using reinforcement learning agents in a market system, as well as with other experimental results gathered from the AI literature. Finally, we use PAC-theory to show how to calculate bounds on the values of the learning parameters.     

Distributed problem solving in multiagent systems: a spring net approach

This paper presents a new spring net approach for distributed problem solving in MAS. Distributed artificial intelligence consists of distributed problem solving and multi-agent systems. We extend such specialized DPS and MASs to a general MAS, such that an agent may make a trade-off between selfishness and unselfishness, thus adjusting its own personality and autonomy. This alternative to traditional approaches can deal with a variety of complicated social interactions and autonomous behaviors occurring in multiagent systems.     

Development of a peer-to-peer information sharing system using ontologies

Most existing agent-oriented methodologies ignore system extensibility, interoperability and reusability issues. Ontologies have been found to play a significant role in facilitating interoperability, reusability, MAS development activities (including MAS analysis and agent knowledge modeling) and MAS run-time operation (including agent communication and reasoning). However, most of the existing AOSE methodologies do not provide support for ontology-based MAS development. We present software engineering requirements for ontology-based development for MAS and examine an existing methodology, MOBMAS – a “Methodology for Ontology-Based MASs”, which makes use of ontologies as a modeling tool. In this examination, we highlight how MOBMAS can be extended to utilizing ontology roles in facilitating interoperability, reusability and verification. This will be based on using MOBMAS to develop peer-to-peer (P2P) community-based information sharing application which lead us to identify ontology related steps that can be added to enhance MOBMAS. MOBMAS is used by two experienced software developers who were not authors of the methodology, to guide the development of the P2P application.     

A systematic approach to evaluating domain-specific modeling language environments for multi-agent systems

Multi-agent systems (MASs) include multiple interacting agents within an environment to provide a solution for complex systems that cannot be easily solved with individual agents or monolithic systems. However, the development of MASs is not trivial due to the various agent properties such as autonomy, responsiveness, and proactiveness, and the need for realization of the many different agent interactions. To support the development of MASs various domain-specific modeling languages (DSMLs) have been introduced that provide a declarative approach for modeling and supporting the generation of agent-based systems. To be effective, the proposed DSMLs need to meet the various stakeholder concerns and the related quality criteria for the corresponding MASs. Unfortunately, very often the evaluation of the DSML is completely missing or has been carried out in idiosyncratic approach. If the DSMLs are not well defined, then implicitly this will have an impact on the quality of the MASs. In this paper, we present an evaluation framework and systematic approach for assessing existing or newly defined DSMLs for MASs. The evaluation is specific for MAS DSMLs and targets both the language and the corresponding tools. To illustrate the evaluation approach, we first present SEA_ML, which is a model-driven MAS DSML for supporting the modeling and generation of agent-based systems. The evaluation of SEA_ML is based on a multi-case study research approach and provides both qualitative evaluation and quantitative analysis. We report on the lessons learned considering the adoption of the evaluation approach as well as the SEA_ML for supporting the generation of agent-based systems.     

Beast methodology: An agile testing methodology for multi-agent systems based on behaviour driven development

This paper presents a testing methodology to apply Behaviour Driven Development (BDD) techniques while developing Multi-Agent Systems (MASs), termed BEhavioural Agent Simple Testing (BEAST) Methodology. This methodology is supported by the open source framework (BEAST Tool) which automatically generates test cases skeletons from BDD scenarios specifications. The developed framework allows the testing of MASs based on JADE or JADEX platforms. In addition, this framework offers a set of configurable Mock Agents with the aim of being able to execute tests while the MAS is under development. The BEAST Methodology presents transparent traceability from user requirements to test cases. Thus, the stakeholders can be aware of the project status. The methodology and the associated tool have been validated in the development of a MAS for fault diagnosis in FTTH (Fiber To The Home) networks. The results have been measured in quantifiable way obtaining a reduction of the tests implementation time.     

面向涌现的多Agent系统研究及其进展

在多Agent系统研究领域,涌现现象越来越引起人们的注意.面向涌现的多Agent系统研究正成为多Agent系统研究中值得注意的一个新方向.它关注的是多Agent系统宏观层面的涌现性问题以及系统涌现的宏观与微观层面的联系机制,并最终希望发展出一套面向涌现的多Agent系统的设计和控制方法.该文在介绍涌现的概念和特征之后,考察了多Agent系统宏观特征的面向涌现描述方法;然后对多Agent系统涌现的微-宏观机制进行了总结,比较分析了面向涌现的多Agent系统设计方法和设计模式;最后分析讨论了该领域研究存在的问题和进一步的研究方向.     

A study of evolutionary multiagent models based on symbiosis.

Multiagent Systems with Symbiotic Learning and Evolution (Masbiole) has been proposed and studied, which is a new methodology of Multiagent Systems (MAS) based on symbiosis in the ecosystem. Masbiole employs a method of symbiotic learning and evolution where agents can learn or evolve according to their symbiotic relations toward others, i.e., considering the benefits/losses of both itself and an opponent. As a result, Masbiole can escape from Nash Equilibria and obtain better performances than conventional MAS where agents consider only their own benefits. This paper focuses on the evolutionary model of Masbiole, and its characteristics are examined especially with an emphasis on the behaviors of agents obtained by symbiotic evolution. In the simulations, two ideas suitable for the effective analysis of such behaviors are introduced; "Match Type Tile-world (MTT)" and "Genetic Network Programming (GNP)". MTT is a virtual model where tile-world is improved so that agents can behave considering their symbiotic relations. GNP is a newly developed evolutionary computation which has the directed graph type gene structure and enables to analyze the decision making mechanism of agents easily. Simulation results show that Masbiole can obtain various kinds of behaviors and better performances than conventional MAS in MTT by evolution.     

Model checking temporal knowledge and commitments in multi-agent systems using reduction

Though modeling and verifying Multi-Agent Systems (MASs) have long been under study, there are still challenges when many different aspects need to be considered simultaneously. In fact, various frameworks have been carried out for modeling and verifying MASs with respect to knowledge and social commitments independently. However, considering them under the same framework still needs further investigation, particularly from the verification perspective. In this article, we present a new technique for model checking the logic of knowledge and commitments (CTLKC⁺). The proposed technique is fully-automatic and reduction-based in which we transform the problem of model checking CTLKC⁺ into the problem of model checking an existing logic of action called ARCTL. Concretely, we construct a set of transformation rules to formally reduce the CTLKC⁺ model into an ARCTL model and CTLKC⁺ formulae into ARCTL formulae to get benefit from the extended version of NuSMV symbolic model checker of ARCTL. Compared to a recent approach that reduces the problem of model checking CTLKC⁺ to another logic of action called GCTL¹, our technique has better scalability and efficiency. We also analyze the complexity of the proposed model checking technique. The results of this analysis reveal that the complexity of our reduction-based procedure is PSPACE-complete for local concurrent programs with respect to the size of these programs and the length of the formula being checked. From the time perspective, we prove that the complexity of the proposed approach is P-complete with regard to the size of the model and length of the formula, which makes it efficient. Finally, we implement our model checking approach on top of extended NuSMV and report verification results for the verification of the NetBill protocol, taken from business domain, against some desirable properties. The obtained results show the effectiveness of our model checking approach when the system scales up.     

Quadratic stabilisability of multi-agent systems under switching topologies

This paper addresses the stabilisability of multi-agent systems (MASs) under switching topologies. Necessary and/or sufficient conditions are presented in terms of graph topology. These conditions explicitly reveal how the intrinsic dynamics of the agents, the communication topology and the external control input affect stabilisability jointly. With the appropriate selection of some agents to which the external inputs are applied and the suitable design of neighbour-interaction rules via a switching topology, an MAS is proved to be stabilisable even if so is not for each of uncertain subsystem. In addition, a method is proposed to constructively design a switching rule for MASs with norm-bounded time-varying uncertainties. The switching rules designed via this method do not rely on uncertainties, and the switched MAS is quadratically stabilisable via decentralised external self-feedback for all uncertainties. With respect to applications of the stabilisability results, the formation control and the cooperative tracking control are addressed. Numerical simulations are presented to demonstrate the effectiveness of the proposed results.     

Integrating skills into multi-agent systems

Currently, an important topic of robotic research is the design and development of multi-agent robot systems (MASs). In these a number of autonomous robots cooperate and coordinate themselves in order to pursue given goals. The agents of an MAS not only have to work autonomously or in cooperation with other agents, but in dynamic, relatively unstructured environments. Therefore, the agents require agent-specific but flexible skills to cope with their tasks and the environment's variability. On the other hand, the actions to be performed by agents in an MAS have to meet certain requirements imposed by the MAS's structure. The representation of actions has to support planning, inter-agent communication, task negotiation etc. In this paper, we describe a method of combining the agent-specific nature of skills with the requirements for a general action knowledge representation inherent to MASs, by presenting elementary operations (EOs) that provide an appropriate interface.     

Robust scalable stabilisability conditions for large-scale heterogeneous multi-agent systems with uncertain nonlinear interactions: towards a distributed computing architecture

Large-scale dynamic systems are becoming highly pervasive in their occurrence with applications ranging from system biology, environment monitoring, sensor networks, and power systems. They are characterised by high dimensionality, complexity, and uncertainty in the node dynamic/interactions that require more and more computational demanding methods for their analysis and control design, as well as the network size and node system/interaction complexity increase. Therefore, it is a challenging problem to find scalable computational method for distributed control design of large-scale networks. In this paper, we investigate the robust distributed stabilisation problem of large-scale nonlinear multi-agent systems (briefly MASs) composed of non-identical (heterogeneous) linear dynamical systems coupled by uncertain nonlinear time-varying interconnections. By employing Lyapunov stability theory and linear matrix inequality (LMI) technique, new conditions are given for the distributed control design of large-scale MASs that can be easily solved by the toolbox of MATLAB. The stabilisability of each node dynamic is a sufficient assumption to design a global stabilising distributed control. The proposed approach improves some of the existing LMI-based results on MAS by both overcoming their computational limits and extending the applicative scenario to large-scale nonlinear heterogeneous MASs. Additionally, the proposed LMI conditions are further reduced in terms of computational requirement in the case of weakly heterogeneous MASs, which is a common scenario in real application where the network nodes and links are affected by parameter uncertainties. One of the main advantages of the proposed approach is to allow to move from a centralised towards a distributed computing architecture so that the expensive computation workload spent to solve LMIs may be shared among processors located at the networked nodes, thus increasing the scalability of the approach than the network size. Finally, a numerical example shows the applicability of the proposed method and its advantage in terms of computational complexity when compared with the existing approaches.     

Agent-oriented modeling and development of a system for crisis management

The management of crisis situations has been a challenging problem from different points of views, such as communication efficiency and avoiding casualties. This paper presents a novel approach that includes an interaction organization pattern for Multi-agent Systems (MASs) in crisis management, abstracted from several existing case studies in which the agents follow a sequence of interactions and the organization must optimize the use of human resources. The pattern considers an emergent organization of peers that adopt different roles according to the circumstances. The key features of the organization are its robustness, scalability (in terms of both agents and roles), flexibility to deal with a changing environment, and the efficient use of resources. In order to validate the organization, the paper presents its modeling and development with the Ingenias methodology, conforming the corresponding MAS. This development follows a model-driven approach, which allows a smooth transition from the specification to the code, and a low-cost testing of the system with different settings. Another key aspect is the application of metrics for validating and improving the MAS in terms of response time. The MAS has been tested with 600 agents representing 200 citizens, showing its performance.     

基于学习的线性多智能体系统弹性最优协同容错控制

针对一类线性多智能体系统,研究其在网络间歇性拒绝服务攻击下的最优同步控制问题.首先,在时变非对称通讯网络拓扑结构下,提出一种弹性最优协同容错控制策略,并优化多智能体的合作二次性能指标,然后证明全局跟踪误差在出现执行器故障和网络攻击时仍然渐进收敛.进一步,当考虑多智能体子系统模型参数未知,同时系统发生执行器故障的情况下,提出利用局部系统状态和输入信息的自学习迭代算法求解代数Riccati方程,计算子系统的反馈控制器增益,实现弹性协同容错控制目标.最后,通过Chua电路网络仿真算例验证所提出的控制方法的有效性.