Spectrum-Based Fault Diagnosis in Multi-Agent Systems

Lúcio Sanchez Passos Spectrum-Based Fault Diagnosis in Multi-Agent Systems December, 2015 Spectrum-Based Fault Diagnosis in Multi-Agent Systems Lúcio Sanchez Passos A dissertation submitted to the Faculty of Engineering, University of Porto in partial fulfillment of the requirements for the degree of Doctor of Philosophy Supervisor: Rosaldo J. F. Rossetti Co-supervisor: Joaquim G. M. Mendes Copyright c 2015 by Lúcio Sanchez Passos The work presented in this thesis was supported by the Fundação para a Ciência e a Tecnologia (FCT) - grant SFRH/BD/66717/2009, by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) under the Ciência Sem Fronteiras programme - grant BEX 9382-13-5, by the Doctoral Programme in Informatics Engineering (ProDEI), by the Artificial Intelligence and Computer Science Laboratory (LIACC), and by the Institute of Science and Innovation in Mechanical and Industrial Engineering (INEGI). Abstract Spectrum-Based Fault Diagnosis in Multi-Agent Systems Lúcio Sanchez Passos Multi-Agent Systems (MASs) have been reshaping how complex problems are decomposed into distributed and decentralised solutions in different sectors. On the academic side, MASs open up many research opportunities to various existing fields by either experimentally exploring pre-established theories or bringing new abstraction paradigms that expand usage of current tools. On the industry side, the community stresses on the immense potential of MASs in real-world problems due to their pro-activeness, scalability, and reconfigurability through active entities with local perspective. However, the lack of reliability is pointed out as one of the reasons to the under deployment of such systems in real-world large-scale complex problems. The community therefore has particular interest in studying manners to ensure nominal MAS performance with maximum coverage. A variety of methods and ideas have been proposed to ensure nominal performance of agentbased applications. This thesis provides a comprehensive survey of such techniques applied to improving reliability in MASs, starting by an overview of threats that can jeopardise the correct functioning of agents. These techniques usually focus on one part of the agentoriented development life cycle. Hence, the relevant literature is deeply discussed regarding the topics of testing MASs, design validation based on simulation, and fault-tolerance in MASs. This review analyses aspects related to the designer perspective such as maturity level, MAS feature support, ease of use, and fault coverage in order to better ground our research. Diagnosing unwanted behaviour in MASs is crucial to ascertain correct operation of agents. Current techniques assume a priori knowledge to identify unexpected behaviour. However, designing MAS’ model is both error-prone and time consuming as it exponentially increases with the number of agents and their interactions. This thesis overcomes such dependency models by taking advantage of spectrum-based diagnosis techniques. We discuss the limitations of applying spectrum-based diagnosis in time persistent and autonomous entities such as agents and therefore propose the Extended Spectrum-based Fault Localization for MAS (ESFL-MAS). ESFL-MAS localises faulty agents in the system that may jeopardise iii Abstract the overall performance through the computation of suspiciousness values. Aiming at assessing the fundamental ESFL-MAS dependencies, we perform empirical evaluations using an exhaustive set of similarity coefficients. Experiments investigate how changing both the amount of collected data and the precision in detecting agent errors will affect ESFL-MAS’ diagnostic quality. Assessments yield prominent results, giving a good prospect for the ESFL-MAS application to localise faulty agents. Results show that Accuracy, Coverage, Jaccard, Laplace, Least Contradiction, Ochiai, Rogers and Tanimoto, Simple-Matching, Sorensen-Dice, and Support coefficients give the best diagnostic accuracy (96.26% on average) in the boundaries of our experimental setup and are stable when varying either error detection precision and quantity of observations. This thesis demonstrates that fault diagnosis in agent-based application can have high accuracy even relying on minimal information about the system, suggesting interesting challenges in the matter of detection and diagnosis processes being agnostic to programming language, agent architecture, and application domain. Keywords:Multi-Agent Systems, Spectrum-based Fault Localisation, Fault Diagnosis, Software Reliability. iv Resumo Diagnóstico de Falhas Baseado em Espectro para Sistemas Multiagente Lúcio Sanchez Passos Os Sistemas Multiagente (SMAs) tem vindo a reformular como problemas complexos são decompostos em soluções distribuídas e decentralizadas em diferentes setores. No lado acadêmico, SMAs abrem diversas oportunidades de investigação para vários campos existentes através da exploração experimental de teorias pré-estabalecidas e trazendo novos paradigmas de abstração que podem expandir o uso de ferramentas atuais. No lado da indústria, a comunidade recalta o imenso potencial dos SMAs em problemas reais devido a sua proatividade, escalabilidade e reconfigurabilidade através de entidades ativas com perspectiva local. Todavia, a falta de confiabilidade é apontada como uma das razões para a inferior implantação desses sistemas em problemas complexos, reais e de larga escala. Dessa maneira, a comunidade tem um interesse em particular no estudo de maneiras de certificar a performance do SMA com uma certa abrangência. Uma variedade de métodos e idéias tem sido propostas para assegurar a performance normal das aplicações baseadas em agentes. Esta tese provê uma revisão abrangente de tais técnicas aplicadas para a melhora de confiabilidade nos SMAs, a começar por uma visão global das ameaças que podem prejudicar o funcionamento correto dos agentes. Essas técnicas concentram-se geralmente em uma das partes do ciclo de desenvolvimento orientado à agentes. Portanto, a literatura relevante é discutida profundamente no que diz respeito aos tópicos de teste em SMAs, validação de desenho baseado em simulação e SMAs tolerantes à falhas. Este estudo analísa aspectos relacionados ao ponto de vista do desenvolvedor, assim como o nível de maturidade, o escopo de suporte em relação das características dos SMAs, a facilidade de uso e a cobertura dos tipos de falhas, tudo isso para fundamentar melhor esta tese. v Contents 2.6.1 MaturityLevel .............................. 28 2.6.2 MAS Feature Support . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.6.3 EaseofUse................................ 34 2.6.4 FaultCoverage .............................. 36 2.7 Summary ..................................... 38 3 Spectrum-Based Fault Localisation for MASs 39 3.1 Spectrum-based Fault Localisation . . . . . . . . . . . . . . . . . . . . . . . 40 3.2 Concepts and Definitions for SFL in MAS . . . . . . . . . . . . . . . . . . . 45 3.3 LimitationsofSFL................................ 48 3.3.1 TimePersistence............................. 49 3.3.2 Agent’sAutonomy............................ 50 3.4 Extending SFL for Multi-Agent Systems . . . . . . . . . . . . . . . . . . . . 51 3.5 Summary ..................................... 57 4 Empirical Evaluation of Similarity Coefficients for ESFL-MAS 59 4.1 ExperimentalSetup ............................... 60 4.1.1 TestSuite................................. 60 4.1.2 DataAcquisition ............................. 63 4.1.3 Evaluation Metric . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 4.1.4 List of Similarity Coefficients . . . . . . . . . . . . . . . . . . . . . . 66 4.2 ExperimentalResults............................... 69 4.2.1 On the Impact of Observation Quantity . . . . . . . . . . . . . . . . 72 4.2.2 On the Impact of Error Detection Precision . . . . . . . . . . . . . . 75 4.2.3 Discussion................................. 78 4.3 Summary ..................................... 79 5 Conclusion 81 5.1 MainContributions................................ 82 5.2 Further Developments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 5.3 Research Trends and Challenges . . . . . . . . . . . . . . . . . . . . . . . . . 87 A Marginal Research Efforts 91 A.1 A Multi-Agent Platform to Support Ubiquitous Transportation Systems . . 91 A.2 A Platform for the Development of Quadcopter MASs . . . . . . . . . . . . 93 References 97 xii List of Tables 2.1 The maturity level of the reviewed literature taking into account the amount of experiments. Note that only the most relevant publication of the respective project was selected to appear in the legend. . . . . . . . . . . . . . . . 30 2.2 Comparison of proposals with respect to the MAS Features Support. Note that only the most relevant publication of the respective project appear below. 32 2.3 The required information from the MAS so the surveyed approach may properly work. Note that only the most relevant publication of the respective projectappearbelow. .............................. 35 2.4 The fault coverage using Wagner [2000]’s taxonomy. Note that only the most relevant publication of the respective project appear below. . . . . . . 37 3.1 Faulty Java method for binary search. The input for test cases is composed by collection ={1,2,3,4,5}and target as presented below. . . . . . . . . . 41 3.2 The values of dichotomy terms for SFL example. . . . . . . . . . . . . . . . 44 3.3 The Jaccard similarity coefficient values and ranking for SFL example. . . . 44 3.4 Dichotomy table for performance spectrum . . . . . . . . . . . . . . . . . . 54 3.5 The Jaccard similarity coefficient values and diagnostic report for the runningexample.................................... 55 4.1 Description of type of faults - Highlighted rows represent the hand-seeded faulty versions and the others are generated through mutation operators. . . 62 4.2 Example diagnostic report. . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 4.3 Similarity Coefficients and their formulae. . . . . . . . . . . . . . . . . . . . 67 4.4 Definitions of the probabilities used by coefficients in the context of this chapter. ...................................... 68 4.5 Mean accuracy for each similarity coefficient. . . . . . . . . . . . . . . . . . 69 xiii List of Figures 2.1 Error Propagation (Adapted from Avižienis et al. [2004]) . . . . . . . . . . . 14 2.2 A taxonomy of approaches that intend to increase reliability of MASs with its life cycle. The main techniques are reviewed in Section 2.3 - 2.5. . . . . . 17 3.1 Work-flow of the Java code in Table 3.1 with the execution flow of two test cases. It outputs the expected result in (a), whereas it has unexpected outputin(b).................................... 42 3.2 Goldminers example used as the illustrative example throughout this chapter. ........................................ 46 3.3 A small version of Goldminers to demonstrate the time-related limitations. 50 3.4 A small version of Goldminers to demonstrate the autonomy-related limitation. One can see that a single initial configurations (i.e., test case) may derive multiple time lines, two time lines in this specific example. . . . . . 51 3.5 Collection of Performance Spectra for both Test Cases 1 and 2 (I= 2) with J= 2 ....................................... 53 3.6 Dichotomy tables for the running example . . . . . . . . . . . . . . . . . . . 54 4.1 Jason’s view of the MAPC Goldminers scenario (screenshot). . . . . . . . . 61 4.2 ExperimentalPhases............................... 64 4.3 Similarity coefficients grouped by their quality of diagnosis: each node corresponds to a group; edges indicate relationships between groups such that A→B means “group A requires less effort to diagnose than group B”; those with the same horizontal alignment present less than 1% difference in the mean quality of diagnosis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 4.4 Observation quantity impact of NCNO MASs. . . . . . . . . . . . . . . . . . 73 4.5 Observation quantity impact of CO MASs. . . . . . . . . . . . . . . . . . . . 74 4.6 EDP for Non-Coordinated MAS versions. . . . . . . . . . . . . . . . . . . . 76 4.7 EDP for Coordinated MAS versions. . . . . . . . . . . . . . . . . . . . . . . 77 A.1 The proposed framework for Quadcopter MASs. . . . . . . . . . . . . . . . . 94 xv List of Acronyms AAA Adaptive Agent Architecture ACL Agent Communication Language ADELFE Atelier de Développement de Logiciels à Fonctionnalité Emergente AI Artificial Intelligence AOSE Agent-Oriented Software Engineering ARCHON Architecture for Cooperative Heterogeneous On-line Systems ARMOR Adaptive, Reconfigurable, and Mobile Object for Reliability AUML Agent Unified Modeling Language BDI Belief, Desire and Intention CNet Contract Net CNO Coordinated and Non-Organised CO Coordinated and Organised DaAgent Dependable Agent-based computing system DAI Distributed Artificial Intelligence DARX Dynamic Agent Replication eXtension eCAT environment for the Continuous Agent Testing EDP Error Detection Precision xvii List of Acronyms ESFL-MAS Extended Spectrum-based Fault Localisation for Multi-Agent Systems FACET Future ATM Concepts Evaluation Tool FIPA Foundation for Intelligent Physical Agents GOST Goal-Oriented Software Testing IDE Integrated Development Environment IDE-eli Integrated Development Environment for Electronic Institutions IDK INGENIAS Development Kit JADE Java Agent Development Framework JAT Jade Agent Testing Framework MAS Multi-Agent System MAPC Multi-Agent Programming Contest MASON Multi-Agent Simulator Of Neighborhoods MASSIMO Multi-Agent System SIMulation framewOrk MCMAS Model Checker for Multi-Agent Systems NASA National Aeronautics and Space Administration NCNO Non-Coordinated and Non-Organised NCO Non-Coordinated and Organised NP-hard Non-deterministic Polynomial-time hard OCA Orbital Communications Adapter OMAS Open Multi-Agent System OO Object-Oriented PASSI Process for Agent Societies Specification and Implementation PASSIM Process for Agent Specification, Simulation and Implementation PDP Pick-up and Delivery Problem PDT Prometheus Design Tool xviii List of Acronyms RatKit Repeatable Automated Testing Toolkit for Agent-Based Modeling and Simulation REPAST Recursive Porous Agent Simulation Toolkit SACI Simple Agent Communication Infrastructure SaGE Système avancé de Gestion d’Exceptions SeSAm Shell for Simulated Agent Systems SFL Spectrum-based Fault Localisation SG-ARP Server Group based Agent Recovery Protocol SMA Sistema Multiagente TAOM4E Tool for Agent Oriented visual Modeling for the Eclipse platform TFG Technical Forum Group TuCSoN Tuple Centres Spread over the Network UIOLTS Utility Input-Output Labeled Transition System VEPR Virtual Electronic Patient Record XP Extreme Programming xix Chapter 1 Introduction Multi-Agent Systems (MASs) have been proposed in early 1980’s as a promising software paradigm for complex distributed systems. It derives from an Artificial Intelligence (AI) sub-field concerned with concurrency of multiple intelligent problem-solvers, named Distributed Artificial Intelligence (DAI) [Bond and Gasser, 1988]. According to Gasser [1987], MAS “is concerned with coordinated intelligent behaviour among a collection of (possibly pre-existing) autonomous intelligent ‘agents:’ how they can coordinate their knowledge, goals, skills, and plans jointly to take action or solve (possibly multiple, independent) problems.” Since then, the autonomous agent concept has been broadly studied in diverse fields [Demazeau et al., 2015]. On the academic side, MASs open up many research opportunities by either experimentally exploring pre-established theories or bringing new abstraction paradigms that expand usage of current tools. Modelling of complex systems has greatly improved, by considering autonomous entities (as agents) and their interactions, bringing to light holistic and microscopic phenomena once hidden within differential equations. More concretely, MAS is the state-of-the-art metaphor to model extremely heterogeneous societies [Dignum et al., 2002], automatises gathering and processing of huge amount of data from various domains [Cao et al., 2009], and provides a testing ground to areas demanding large number of entities such as game theory [Parsons and Wooldridge, 2002]. On the industry side, the community stresses the immense potential of MASs in real-world problems due to their pro-activeness, scalability, and reconfigurability through active entities with local perspective [Parunak, 1996, Leitão et al., 2012, Bazzan and Klügl, 2013]. Several successful deployments take advantage of these features such as well-known examples: the ARCHON [Wittig, 1992], the NASA’s OCA Mirroring System [Sierhuis et al., 2009], the VEPR system [Cruz-Correia et al., 2005, Vieira-Marques et al., 2006], the work of Carrera and his colleagues [Carrera et al., 2012], the OMAS platform [Tacla and Barthès, 2003], the FACET simulations [Agogino and Tumer, 2012], and the software package MASSIVE1. These cases only scratch the surface on the subject and further examples might be found in the literature [Parunak, 2000, Manvi and Venkataram, 2004, Pěchouček and Mařík, 2008, Isern et al., 2010, Leitão and Vrba, 2011, Smith and Korsmeyer, 2012]. 1MASSIVE (Multiple Agent Simulation System in Virtual Environment) is a high-end computer animation and artificial intelligence software package which has the ability to create thousands of agents that all act as individuals as well as react to its surroundings, including other agents. These reactions affect the agent’s behaviour changing how they act by controlling pre-recorded animation clips. 1 1 Introduction cles retrieving and delivering a set of items, based on the AgentSpeak implementation presented in the Multi-Agent Programming Contest. We improved this implementation from two perspectives: first, implemented variants of the original version in order to create different levels of organisation and coordination; second, we inserted both hand-seeded and mutation-based fault in the agents. This experimental setup is sufficiently solid and sound to be used by the community as an initial benchmark to fault diagnosis in MASs. 5. Finally, we survey the research efforts building a consultation guide within the scope of this thesis. It extensively covers techniques to improve MAS reliability (except those based on formal verification), including namely: agent-oriented testing, simulation-based design validation, and fault tolerance approaches to agent-based applications. We also provide a classification based on the agent development cycle that assist newcomers to understand state of the art in each branch. More importantly, we assess the reviewed literature focusing on the (presumably) most important aspect for designers/developers, such as: maturity level, MAS feature support, ease of use, and fault coverage. 1.4 Thesis Outline The five contributions outlined in the previous section are described in terms of three chapters. Chapter 2 overviews threats that can jeopardize correct agent functioning and then surveys the current literature on testing in MASs, simulation-based design validation, and fault-tolerant MAS. It also analyses aspects of the reviewed literature related to the designer perspective such as maturity level, MAS feature support, ease of use, and fault coverage. Chapter 3 describes a light-weight, automatic debugging-based technique, coined ESFL-MAS, that shortens the diagnostic process, while only relying on minimal information about the system. Chapter 4 presents experimental evaluation by varying (1) the amount of information and (2) the precision of error detection mechanisms while determining the best heuristics for ESFL-MAS. Finally, in Chapter 5 we draw conclusions, present recommendations for future work, and identify research trends and avenues for reliable MASs. 1.5 Origin of Chapters The following list gives an overview of the publications that originated each chapter: Chapter 2 has been submitted in ACM Computing Surveys. An earlier version of the chapter appeared in the Encyclopedia of Information Science and Technology, 3rd ed., as a book chapter [Passos et al., 2015c]. 8 1.5 Origin of Chapters Chapter 3 and Chapter 4 has been accepted in IEEE Transactions on Systems, Man, and Cybernetics: Systems. An earlier version of this work appeared in the Proceedings of the 24th AAAI International Joint Conference on Artificial Intelligence (IJCAI’15) [Passos et al., 2015a], in the Proceedings of the 25th International Workshop on Principles of Diagnosis (DX’14) (Best Paper Award) [Passos et al., 2014], and in the Proceedings of the 11th European Workshop on Multi-Agent Systems (EUMAS 2013) [Passos et al., 2013b]. 9 10 Chapter 2 Survey on Increasing Reliability in Multi-Agent Systems Since the early 1980’s, the advent of computer networks and the introduction of MultiAgent Systems (MASs) have been reshaping how complex problems are decomposed into distributed and decentralised solutions in different sectors [Wooldridge, 2009]. MASs are concerned with coordinated behaviour among a collection of autonomous, distributed, and intelligent entities, called agents [Gasser, 1987]. Many applications are taking advantage of MAS inherent features, such as entities dispersion, parallel reasoning, ill-structureness, and complexity [Parunak, 1996, Stone and Veloso, 2000]. Differently from objects, agents exercise control over their own actions and might pro-actively interact with other entities to achieve a determined goal [Jennings and Wooldridge, 1995]. At the same time, MASs are software and as such should respect the software development life cycle aiming at ensuring from requirement fulfilment to system validation. On the one hand, such unique and specific characteristics of MASs give rise to software faults not observed in any other type of software, exhibiting collective and individual unanticipated behaviours. On the other hand, they have encouraged researchers to endeavour in the development of more reliable real-world agent-based applications. At the corporate level, techniques to ensure reliable MASs have become a fundamental component to agent-oriented software engineering methods. As the Technical Forum Group showed, the industry’s conservatism regarding MAS emergent behaviour without any central decision unit is one of the issues that constrains the extensive deployment of MASs in real complex (distributed) domains [Pěchouček and Mařík, 2008]. Fortunately, there are no registered cases in which MAS failures have led to hazards or huge financial losses; however, unfortunately, there are such examples in software history [Charette, 2005, Wong et al., 2010]. Hence, reliable MASs from components to system perspectives have become of particular interest to researches and practitioners. A designer/developer or software company which is able to provide a tool that ensures nominal MAS performance with a certain coverage can help to improve acceptance of agent-based applications for solving complex problems. In this chapter, we survey the various techniques used to increase reliability of every agentbased application levels. The more limited field of fault tolerance for mobile agents (in which agents are able to safely migrate within a network and continue execution even 11 2 Survey on Increasing Reliability in Multi-Agent Systems is the presence of failure) is not discussed though1, mainly because it involves a set of watchdogs and check-pointing procedures that are simply not applicable to non-mobile agents. Furthermore, although the certification sought by both model-checking and formal verification indeed contributes for more reliable MASs2, this survey concentrates on testing and fault tolerance techniques inherent to the agent-oriented development life cycle. There are existing surveys on testing techniques for MASs [Nguyen et al., 2011], agent-based modelling and simulation [Fortino and North, 2013, Michel et al., 2009], and fault tolerance mechanisms [Passos et al., 2015c]. However, none of these do the profound discussion we intend to present in this survey. The primary contributions of this chapter are as follows. 1. Coverage. The survey gathers publication efforts, covering techniques to improve MAS reliability with the aforementioned scope from its early origins to the state of the art. It includes testing and simulation-based new approaches and updates from the past recent years that were not discussed in the previous surveys. Moreover, this chapter extensively details research efforts of fault tolerance designed to suit agent-based applications. 2. Classification and assessment. The classification of approaches based on the development life cycle allows us to identify gaps in the literature, indicating possible MAS development phases that could benefit from further research and/or application of existing mechanisms. Similarly, the analysis of surveyed publications from the designer’s/developer’s point of view allows the community to identify some aspects that have yet to receive significant attention so such techniques are adopted by practitioners. The remainder of the chapter is structured as follows: Section 2.1 provides an overview of fault-related concepts, with emphasis on how these concepts need to be changed to encompass particular MAS features; Section 2.2 outlines a taxonomy to approaches aiming at ensuring nominal MAS service; Section 2.3 describes various methods that are used to test and debug different levels of agent-based applications; Section 2.4 explains design validation mechanisms that benefit from simulation tools; Section 2.5 examines several advances in the area of fault-tolerant MAS; Section 2.6 analyses the reviewed literature mainly focusing on adoption aspects seen by designers; and Section 2.7 summaries the survey. 1Readers interested in the broader picture of how fault tolerance techniques are applied in mobile agents can refer to Isong and Bekele [2013]. Mobile agent had also been extensively used as fault tolerance providers and Qu et al. [2005] introduce several of these approaches. 2Readers seeking for deeper information about formal verification and model checking for MAS can consult Dennis et al. [2012] and Bordini et al. [2004] 12 2.1 Threats to Multi-Agent Systems 2.1 Threats to Multi-Agent Systems Before presenting and discussing the advances in reliable MASs, it is essential to explain the general terminology adopted across several domains. A system is an entity (which can be holonic3) that interacts with an external environment. It originates three major concepts: function,behaviour, and service. The former is what the system is intended to do. The second is what the system does to implement its function. And the latter is the perceived system behaviour. Chiefly, the correct behaviour is delivered when the service meets the system function. When the delivered service deviates from the specification (i.e., the correct service), a failure event had occurred [Lee and Anderson, 1990, Avižienis et al., 2004]. This deviation may have different degrees of severity (a.k.a. failure modes). An error is a system state which is liable to lead to a failure. It is important to note that many errors do not reach the system’s external state causing a failure. A fault is the adjudged or hypothesised cause of an error. It is active when it effectively causes an error, otherwise it is dormant. Faults might also be transient (those that cause temporary malfunction), or permanent (those in which, once it happens, the component fails permanently) [Laprie et al., 1992]. Fault, error, and failure are not isolated episodes. They have a deep connection that starts with the activation of either an internal previously dormant fault or an external fault. This now active fault causes an error in a given component state, which may propagate within the component (i.e., internal propagation) or from one component to another (i.e., external propagation). A failure effectively happens when the error propagates and reaches the service interface, provoking an incorrect delivered service. Figure 2.1 illustrates this fundamental chain of threats [Avižienis et al., 2004]. A known term also found in many publications regarding reliable MASs is exception. On its most general definition, “(exception) indicates that something unusual has occurred, and even this may be misleading" [Liskov and Snyder, 1979]. Hence, exception are anomalous conditions that change the normal software execution flow and requires handling processes. This term mainly refers to specialised programming language constructors or hardware mechanisms. It should be noticed that we use the terms failure and exception interchangeably throughout this thesis. Now that basic terms to indicate general characteristics and failure-related events have been defined, we can discuss how an agent-oriented perspective tune each of them. The system term may be applied to different abstraction levels from the agent to high-level organisations (including hardware and/or legacy systems). Moreover, the vast majority of MAS research employs function, behaviour, and service terms interchangeably, meaning by them what the system does to implement its function. This might prevent a newcomer to fully understand the mechanisms to increase reliability and how to correctly explore them in different MASs. 3Aholon is a self-similar structure that consists of sub-structures [Koestler, 1967]. In MASs, the vision of holons is usually related to the notion of composed agents. A holon encompasses both local and global, both individual and collective perspectives [Cossentino et al., 2010]. Readers interested in a thorough discussion on Holonic MASs can consult Fischer [1999] for a theoretical foundation and Leitão et al. [2012] for recent applications. 13 2 Survey on Increasing Reliability in Multi-Agent Systems Service status of component A Incorrect Service Correct Service Failure Component A Service Interface Internal Dormant Fault Error Input Error Propagation Error Error Propagation Activation External Fault Component B Service Interface Error Propagation Error PropagationPropagation Boundary Service status of component B Incorrect Service Correct Service Failure Figure 2.1: Error Propagation (Adapted from Avižienis et al. [2004]) Regarding the terms related to anomalous services, several endeavours extend the systemic view given by the failure definition to encompass the agent-oriented perspective. For instance, Tripathi and Miller [2001] define: “an exception is an event that is caused by a program using a language construct, or raised by the underlying virtual machine”, which is also used by Souchon et al. [2004]. Complementarily, Xu and Deters [2004a] describe a fault as “the defect in the program that, when executed under particular conditions, causes a failure.” Despite such endeavours, part of the MAS community states that these definitions do not completely comply with the agent paradigm [Platon et al., 2007], lacking allusion to issues of both autonomy and social interactions, as well as considering only non-social events as sources to unexpected situations. Even though autonomy is an inherent feature of software agents, the aforementioned definitions disregard autonomous decisions by always considering an external source as origin of irregular events. Moreover, social interactions are a natural overlay of agent-based systems, where the “social fabric” may assist different system stages, e.g., to format its organization and/or exchange new methods to achieve optimal solution. Even in a fixed organization (i.e., defined by rules), informal associations can appear due to evolving interaction forms [Huberman and Hogg, 1996]. Aforementioned definitions also do not take social aspects into account as interaction violations focus only in low-level failures such as package loss. Thus, simply adapting definitions to cover agent faults restricts them to single threads and linear information/control flow; additionally, they do not cover the interactive nature of agent societies where faults encompass group of agents, themselves being multi-threaded software. Seeking to overcome these constraints, some approaches define threats to MASs in rupture with traditional basis. Their main breakthrough is to consider faults as systemic matters. Klein et al. [2003] describe that “all (...) departures from the ‘ideal’ MAS behaviour can be called exceptions.” Authors refer to “MAS behaviour” as a global conduct and thus, similarly to traditional approaches, a deviation from the “ideal” is a failure. The definition rises the term to a system level because MAS faults may spread throughout, affecting the whole system. Hence, the treatment dimension is not constrained to linear flow. Klein et al. [2003] focus on the subject of autonomy; however, disregard any social dynamism. The majority of works on dependable interaction among agents aims to improve protocol robustness, but no publication explicitly discusses an agent-oriented fault definition focusing on social aspects. Furthermore, Platon et al. [2007] assert that the essential different between agent-related 14 2.1 Threats to Multi-Agent Systems and traditional failures is their source. Sources are not restricted to simple operational invocations because agents, owning autonomy, play a paramount role in determining execution status. So an event in either observable actions or system states should be comprehended in a broader sense whereas unexpected events are those that agents do not foreseen in a particular context. Authors propose five properties to agent failures: (1) the anomalous character of an event depends on how each agent interprets it; failures are broader than only programming or crash errors which implies in a neutral connotation for faults (Mallya and Singh [2005b] share this perspective and suggest distinguishing them between ‘negative exceptions’ from desirable ones, named ‘opportunities’); (3) agents should have an internal knowledge to determine exceptional situations; (4) errors in MASs spread non-linearly, demanding for the asynchronous feature in exception-management mechanisms; and (5) an agent fault can exist without underlying programming exception, whereas programming exception implies an agent exception. Another set of publications concerns less about what are failures in MASs and more on how classify them to better understand the state of the art. As seen above, a diversity of agent fault definitions may be found in the literature, in some cases complementary to each other and in other cases divergent. The same situation can be observed for the agent fault classification. Faci et al. [2006] extend the generally accepted taxonomy of Powell et al. [1988], designed for general distributed applications, in which failures are classified based on the output produced by faulty components. This extension classify failures in four types. (1) The crash failure where the component stopped producing output. (2) The omission failure where a component suddenly ceases to output results. (3) When a result is delivered after a required time frame, it is called the timing failure. (4) The arbitrary (or Byzantine) failure relates to the event of generating random output values. Many endevours in the MAS literature use sub-groups or similar classifications to the above. Albeit this taxonomy encompasses various aspects of failures, it does not embody neither autonomy nor social interactions. Similarly, Potiron et al. [2008] propose an extension of Avižienis et al. [2004]’s taxonomy, aiming to include autonomy as a new branch in the original taxonomy. New fault classes combine autonomy as an attribute to “phase of creation or occurrence” of faults. Authors also assemble faults into groups according to their origin. They divide behavioural faults in (1) development faults that are internal and (2) interaction faults that are external; both can yield catastrophic failure in the agent. This multi-level approach improves the accuracy of classifying a fault and goes further in this discussion, however it is complex for practical use. In a simpler approach, Mellouli et al. [2004]’s taxonomy takes into consideration two aspects: the communication state and agent capability of performing actions. According to authors, if the communication is down, the agent may be fully capable of performing its tasks, partially capable, or incapable. Contrarily, if communication is up, the agent can only be partially capable or incapable of performing its tasks. This taxonomy neglects the real origin of the failure and concentrates on determining the functionality level of an agent. Wagner [2000] presents a taxonomy for social order problems induced by software agents; 15 2 Survey on Increasing Reliability in Multi-Agent Systems he applies an econometric theory, called liberal order, to the agent metaphor. According to this taxonomy, faults in agents can be: (1) program bugs, errors in the source code that go undetected through system testing; (2) unforeseen states, omission flaws in design/implementation; (3) processor faults, system or resources crash; (4) communication faults, various failures of communication links; (5) emerging unwanted behaviour, a system behaves differently from expected, which may be beneficial or harmful. 2.2 Overview of Approaches to Increase Reliability of MAS Nearly all review and work publications in the area offer their own classification of the various approaches that have been developed for increasing reliability of agent-based systems. As this survey deals with complementary parts of the MAS life cycle, we have taken the classification of Moreno et al. [2009] as a starting point, with five levels of testing activities. Without loss of generality, we alter the Platon et al. [2008]’s taxonomy by combining the first groups in a larger class (because both of them basically rely on sentinel-like entities), excluding the stigmergic systems branch (as we consider that most of this research relates to swarm intelligence, which has been extensively surveyed by Qin et al. [2014]), and add a branch regarding replication-based architectures (due to the increasing popularity of these methods). We then merge these two modified taxonomies resulting in the classification that encompasses the scope of this chapter: •Testing in MASs (unit level,agent level,integration level, and testing frameworks) works, which evaluate different MAS operational levels through predetermined cases during design phase, and provide tools to designers/programmers to better understand both behaviours and information flow during the implementation phase. •Simulation-based design validation methods, which understand the system behaviour and/or assess various implemented strategies facing operational situations by modelling a limited set of both environmental features and dynamics. •Fault-Tolerant MASs (on-line monitoring and error detection,exception handling systems,sentinel-based architectures, and replication-based architectures) approaches, which identify anomalous event origins (internal and/or external to agents), attempt to maintain minimal and consistent system services, and then recover from the faulty state aiming to return to nominal service. Finally, we should mention that many of the testing approaches considered in the literature are components of frameworks, combining mechanisms from two or more levels. These frameworks will be described as a whole so the reader can perceive their progresses. We illustrate the proposed taxonomy in Figure 2.2. The main techniques will be reviewed in Sections 2.3 - 2.5. 16 2.3 Testing in MAS Testing Framework Unit Level Agent Level Integration Level System Level Acceptance Level Testing in MAS Simulation-based Design Validation Exception Handling Systems On-line Monitoring and Error Detection Replication-based Architectures Fault-Tolerant MAS Reliable MAS Approaches Sentinel-based Architectures Figure 2.2: A taxonomy of approaches that intend to increase reliability of MASs with its life cycle. The main techniques are reviewed in Section 2.3 - 2.5. 2.3 Testing in MAS Testing is a paramount activity in the software development life cycle that is dedicated to evaluate software quality, improve it by detecting implementation flaws, as well as assess the correspondence between delivered services and requirements. Testing in MASs is especially challenging given their distribution, decentralised decision-making, lack of structure, and so forth. As a result, MASs demand for new set of testing techniques that can deal with their unique features while ensuring highly reliable MAS with minimal costs and time spent. MAS body of knowledge spans techniques to test various system levels, being these: unit,agent,integration,system, and acceptance. Seeking clearness and balance, we present together unit and agent levels and separate integration level approaches. Additionally, we group works related to multi-level testing frameworks so the reader can easily follow their evolution. 2.3.1 Unit and Agent Levels Agents are internally composed by modules with specific functions depending on their architecture. These modules may be a set of goals and plans, a knowledge base, several varieties of reasoning algorithms, and so forth, down to code methods and blocks. Unit testing makes sure that each of these aforementioned components independently delivers the expected output. Well-known unit testing techniques for sequential and Object-Oriented (OO) programming can be used in MASs to a certain extent. 17 2 Survey on Increasing Reliability in Multi-Agent Systems a lightweight comparison to determine any deviation. It has a predefined set of diagnosis rules and, according to the fault characteristics, specific set of rules are triggered. An interesting point of this work is the evaluation made to examine the effects of detection and diagnosis sensibility in the overall efficiency. However, the recovery strategy focus solely on finding a new task path and not on treating the existing fault. Some research efforts focus on the fault localisation in agent plans, Roos and Witteveen [2009] introduce the primary plan diagnosis as the self-analysis of an agent’s plan and a further endeavour [Jonge et al., 2009] extended this view with the definition of secondary plan diagnosis. Root causes of the plan failure are underlined by the latter whereas the former isolates the faulty set of actions. Moreover, Micalizio [2009] suggests an extended action model that might be used to identify and recover plans under partial observable situations. Recent efforts [Micalizio, 2013, Micalizio and Torasso, 2014] merge both modelbased plan diagnosis and recovery schemes, ensuring a backup plan whenever possible. These techniques rely on prior agent plan model (that constraint their use in system testing) and mainly assume collaborative and non-malicious MASs. 2.5.2 Exception Handling Systems Exception handing is a process inherited by MASs from software programming and hardware design. Handlers, by usually knowing the conditions that the exception occurred, can (depending on the error severity) either change the execution flow or resume the execution sending a report to designers. In the MAS context, exception management encompasses higher level concerns such as semantic inconsistencies and commitment violation. Rustogi et al. [1999]’s approach handles semantic exception in a team of agents covering from the specification to execution of a MAS. In their view, an agent has two essential properties: interaction in a high level (commitments) and persistence. They develop a dependable interaction metamodel, which correlates the task definition with resource, capabilities, and so forth. In addition, they devise commitment patterns, enclosing the most common interactions. Any deviation on normal system flow is treated as a interaction problem only. This approach essentially addresses the issue of task disruption; however, the proposed treatment is to completely redesign the agent. Xu and Deters [2004a] propose an event-based fault management that relies on agents’ event reports and entities named event managers. Agents inform internal states and an event manager, which is equipped with event patterns, detects any faulty states. These managers correct agents via state-transition sequences whenever necessary. Authors apply the approach to a travel agency [Xu and Deters, 2004b] and in a third-party MAS [Xu and Deters, 2005]; concluding that (1) building event patterns is a laborious task, and (2) the approach has a scalability issue because, as every agent must report taken actions, the communication network is flooded with unnecessary messages. SaGE (Système avancè de Gestion d’Exceptions, in English Advanced System of Exception Management) framework [Souchon et al., 2004, 2003] enhances the Java exception handling mechanisms to include particular features of agent-based systems. It combines exception handlers with a concerted exception mechanism, which gathers (and maintains history 24 2.5 Fault-Tolerant MAS of) fault information to handlers. SaGE complies with the agent paradigm preserving its autonomy and internal states. However, it does not support heterogeneous and open MASs as it assumes agents are always benevolent. Nevertheless, the approach suggests a set of novel techniques for MAS exception handling, namely handler search propagation and the concerted exceptions. Platon et al. [2008] propose a multi-agent architecture that embeds exception management facilities for MAS deployment. It uses a twofold perspective. First, the exception-ready agent model extends beyond a basic agent architecture (composed by internal mechanisms and representations, actuators, and sensors), and encompasses exception handling logic within agents. Second, the environment is tailored to support specific exception types (e.g. agent death). Such functionality only notifies agents about environmental changes respecting their autonomy. The proposal depends on designers to provide information about the application domain, including specific data types and expected services, so agents can report exceptions. Mallya and Singh [2005b]’s approach incorporates fault tolerance in commitment protocols to set how agents interact in an (error-prone) open system. When an agent detects an event that does not follow the protocol specification, it signalises an exception. The mechanism distinguishes the signalised exception between expected and unexpected. Excepted exceptions occur frequently and their treatment can be incorporated within the system. Unexpected exceptions are not modelled and hence require to dynamically handle them. Mallya and Singh [2005a] suggest an exception database that contains specific handlers with proper protocols (similar to Klein and Dellarocas [1999]’s model). Main issues of this work are that handler selection and assembly processes have high computational complexity and, at the same time, it is mainly theoretical and lacks performance evaluations. 2.5.3 Sentinel-based Architectures The next class of work, known as sentinel-based architectures, tries to endow MASs with fault tolerance features through external software entities: the sentinels. Each sentinel assists an agent or a group of agents by inspecting interactions and actions. Additionally, many of the sentinel-based approaches considered in the literature have specialised sentinels to detect and recover an agent. A major issue with sentinels is that they do not respect agent encapsulation and therefore agent autonomy, as they are able to access agent’s internal modules. Despite this fact, sentinel-based approaches have been the most used architecture for fault tolerant MASs. Hägg [1997] introduces the use of sentinels to handle faults in MASs. According to the author, a sentinel is an agent whose mission is to guard a specific function or to avoid some states in the society. Their sentinel applies a twofold strategy to expand its judgement boundaries (responsible for detecting exceptions) and thus early detecting and treating agent inconsistency. First, it internally assembles its own world model by monitoring communications and interacting with other agents. Second, through an item checkpointing mechanism, some parts of other agents’ model (expressed as beliefs) are integrated into the sentinel’s world model. Albeit sentinels have recognised benefits, they are error-prone 25 2 Survey on Increasing Reliability in Multi-Agent Systems entities that restrict agent autonomy to reduce the MAS space state. Klein and Dellarocas [1999] propose a domain-independent exception handling in agentbased systems. The system uses expert sentinels to either (1) detect or (2) treat faults. They achieve generic behaviour through predefined strategies, to detect delays, low performance, and interaction or plan failures in agents. Yet, agents must register their complete behavioural model, so experts map failure modes and know a priori the possible faults. Generic diagnosis and recovery strategies are stored in a knowledge base. Communication with experts, as argued by the authors, are easily combined into the agent architecture. The approach was assessed using a simple error-prone Contract Net (CNet) domain with only one induced fault and, within this experimental boundaries, yielded good results [Klein et al., 2003, Dellarocas and Klein, 2000]. Adaptive Agent Architecture (AAA) [Kumar et al., 2000] is a fault-tolerant brokered multiagent system architecture that aims to improve the robustness of communication among agents. Brokers form up a team with a joint commitment to support any registered agent, allowing that brokers substitute each other whenever required. The system maintains a minimal number of brokers despite failures in a subset of them. Their results suggest that the brokerage layer is fault tolerant [Kumar and Cohen, 2000]; however, it is not scalable due to the implied overhead that depends on the system size. This approach focuses on the recovery of brokers rather than on agents themselves, and does not show any assessment of how it increases reliability and availability of functional agents. DaAgent (Dependable Agent-based computing System) [Mishra and Huang, 2000] improves agent-based computing dependability, mainly for Internet applications. Similarly to sentinels, an agent watchdog ensures that agents are able to (reliably) reach their destinations [Mishra, 2001]. In the presence of a (communication or node) failure, the agent rolls back to a checkpointed state done by its watchdog. A paramount contribution of this sequence of efforts is the identification of guidelines for an agent fault-tolerant protocol. This discussion culminates in the SG-ARP (Server Group based Agent Recovery Protocol) implementation and evaluation [Mishra and Xie, 2003]. Chameleon [Kalbarczyk et al., 1999] is an adaptive infrastructure that allows different availability levels in a networked domain. It is built upon ARMORs (Adaptive, Reconfigurable, and Mobile Objects for Reliability), which embodies specialised agents [Iyer et al., 1997]. ARMOR can be (1) managers (including fault tolerance manager), (2) daemons, and (3) commons. The approach is designed to recover mainly from hardware faults. Extensive evaluation is carried out and, according to the authors, the overhead and response time is acceptable [Kalbarczyk et al., 1999]. The ARMOR middleware offers a high-dependability services to application and has been deployed in several fields [Kalbarczyk et al., 2005]. The concept of adapting the fault treatment technique according to the system needs is an appealing feature. Moreover, the system is not necessarily specific to MAS, therefore it neither diagnose nor treat every agent failure. The Guardian model [Miller and Tripathi, 2004] extends sequential exception handling models to distributed (including agent-based) applications. It centres on sentinel, called guardian, that monitors interaction among agents and uses predefined models to detect and treat a fault. An agent can notify and send an exception to its guardian. They deploy the Guardian in the Ajanta mobile agent programming system [Tripathi and Miller, 2001]. The 26 2.5 Fault-Tolerant MAS Guardian model usage is limited to open MASs, given the agent benevolence assumption where agents must not hide an exception from its guardian. 2.5.4 Replication-based Architectures Redundancy is a key concept for fault tolerance as it includes additional resources that will only be activated in the presence of failure. Replication-based architectures has borrowed this concept and applied it to the agent level. However, to simply copy the information of an agent before its failure and then pass it to a replica might not be enough to bring the system to error-free state. These architectures demand for check-pointing and replica creation strategies without affecting nominal services. Fedoruk and Deters [2002] introduce the use of dynamic proxies to manage groups of agent replicas. They deal with key challenges of agent replication, such as: synthesis of agent interaction and outcomes, state synchronization, and read/write consistency. In the conceptual architecture, a replica group is composed by a given number of host agents, each equipped with a message proxy, a replica agent, and a group manager [Fedoruk and Deters, 2003]. Experiments done with FIPA-OS20 reveal that the system was effective in improving multi-agent reliability and demonstrate the potential of redundancy in a faulttolerant scheme. DARX21 [Guessoum et al., 2010] is an adaptive replication-based framework for increasing reliability of distributed applications, which provides schemes to ensure nominal system functioning agnostic to agent architectures. DARX architecture applies three strategies: (1) dynamically manage replica membership, (2) provide the infrastructure so replication groups are able to internally communicate, and (3) agent interactions (external to the replication group) are gathered by individual replica and transmitted in cases of recovery procedures. Moreover, authors integrate DARX with a multi-agent platform (named DIMA [Guessoum and Briot, 1999]) resulting in DimaX [Faci et al., 2006]. Several pieces of work [Guessoum et al., 2003, Marin et al., 2007, Almeida et al., 2008] were implemented as improvements to this framework; however, to describe them all it is outside the scope of this review. Some recent endeavours [Dony et al., 2008, 2011] aim to combine exception handling and agent replication by adding a new level to the architecture. In this level, authors have incorporated the SaGE framework as the exception handling tool. This approach is perhaps the most complete from the reliability point of view as it provides preventive and corrective solutions; however, its resource usage will always be doubled regardless any optimisation given that every agent must have at least one replica. 20http://fipa-os.sourceforge.net 21http://pages.lip6.fr/Olivier.Marin/DARX.startup 27 2 Survey on Increasing Reliability in Multi-Agent Systems 2.6 Analysis of Techniques Aiming at Reliable MAS Different schemes, mechanisms, and architectures have been proposed aiming at ensuring nominal service of agent-based applications from the design phase with testing and simulation-based validation, to the operational phase with fault tolerance support. After classifying and describing the relevant literature in Sections 2.3 - 2.5, it is essential to analyse advances reported in the literature so as to identify tendencies and better understand paths chosen by researchers as they deal with faulty events. A few publications in the literature have analysed approaches within the scope of this chapter. For instance, Nguyen et al. [2011] assess testing techniques in terms of their maturity level and classify them as usable, in progress, and concept. From the fault tolerance perspective, Xu and Deters [2005] make a broad multi-dimensional study that emphasizes five key features: (1) time of intervention of the mechanism, (2) roles of system and agent, (3) required information, (4) required changes, and (5) scope of support. Both of these studies highlight interesting aspects, however they disregard the fact that designers demand additional time to analyse and choose a proper solution. Designers consider both usefulness and ease of use to be important factors while choosing or adopting information systems [Keil et al., 1995]. The former is related to “the degree to which a person believes that using a particular system would enhance his or her job performance.” The latter is rather related to “the degree to which a person believes that using a particular system would be free from effort.” We derive four adoption-related features from both usefulness and ease to use concepts as this chapter intends to assess the surveyed literature considering the viewpoint of the designer. Techniques and tools proposed by the community have different maturity levels as they might be either in progress or solely be an exploratory study. MAS Feature Support inspects every set of publication regarding the major MAS features. Ease of Use aims at discussing which modifications must be done and/or information must be offered so an approach can properly work. Fault Coverage uses Wagner [2000]’s fault classification presented in Section 2.1 to comprehend their scope. 2.6.1 Maturity Level As we can see throughout this chapter, there are several proposals that try to ensure correct agent functioning by either avoiding failures or overcoming them. These proposals are not in the same level of development due to factors such as (1) the number of members involved in the project, (2) achievement regarding performance and/or publication results, and so forth. Therefore, designers must take into consideration the maturity level of the chosen approach as this may require more implementation to obtain the desired results. Maturity level can be: usable (these have published results, available material to experiments reproduction, and have been applied to medium to large projects), in progress (these have published results, available material to experiments reproduction, and have been assessed using small or academic projects), or concept (these have published results but are in the theoretical level) [Nguyen et al., 2011]. 28 2.6 Analysis of Techniques Aiming at Reliable MAS Table 2.1 shows the distribution of research efforts with respect to their maturity level. Those near the Concept line were minimally experimented; proposals near the In Progress line were experimented using toy problems and/or small applications. Research efforts above the Usable line had various medium-size assessments, but lack trials in more realistic/large problems; whereas those below are indeed usable within their scope of MAS feature support. It is important to highlight that, for the sake of clearness, we used only the more relevant publications in the legend. One may notice that testing frameworks and simulation-based approaches are current hot topics to the community given the major number of relevant publications in the past recent years. Another interesting aspect is that these projects produce usable tools, which confirms the need for such readiness-orientation of the research on reliable MASs. Still, this high number of usable approaches may lead to the false sense that both of these branches have already developed “silver bullets” to guarantee the nominal agent service. Actually, these proposals use the strategy of restricting their focus to a particular type of MAS and consequently better defining usage boundaries; further discussion about this topic will be given in the next analysis. Furthermore, although ACLAnalyser [Serrano et al., 2012] is the only technique for integration testing, it provides a robust API to support verification of ACL-based communication to such an extent that it was included in IDK [Gómez-Sanz et al., 2009] and might be integrated in any testing tool. This approach should be seriously considered to perform integration testing MASs relying on ACL-based interactions. Concerns regarding fault tolerance in MASs have boosted publications between early to mid 2000’s, but most of them were ad-hoc techniques because they used toy problems as experimental setup and since then no other means of validation was provided or was any of these works followed up. Nevertheless, these approaches laid the foundations to more complete and recent work such as Chameleon [Kalbarczyk et al., 2005] and SaGE [Souchon et al., 2004]. The former is more recently designated as ARMOR middleware and has been deployed to domains outside the MAS arena. The latter as mentioned in Section 2.5.4 was incorporated in the most robust fault tolerance architecture, namely DARX [Guessoum et al., 2010], to provide support to low-level exceptions. In conclusion, although exception handling systems for MASs had achieved great results in the last decade, sentinel-based and replication-based architectures better meet distribution and decentralisation aspects of agent-based applications with lower maintenance costs. 29 2 Survey on Increasing Reliability in Multi-Agent Systems Table 2.1: The maturity level of the reviewed literature taking into account the amount of experiments. Note that only the most relevant publication of the respective project was selected to appear in the legend. Concept Usable In Progress Fault-Tolerant MASs Testing in MAS Simulation- -based Design Validation 13 12 10 TF 9 8 7 UAL 1 IL 5 14 OMED EHS SbA 33 32 31 RbA 35 4 2 3 6 11 17 15 16 18 20 21 23 24 27 25 26 29 30 28 34 Maturity Level 19 22 Legend (1) −[Knublauch, 2002] (2) JAT [Coelho et al., 2007] (3) −[Lam and Barber, 2005a] (4) −[Pardo et al., 2010] (5) ACLAnalyser [Serrano et al., 2012] (6) SEAUnit [Çakirlar et al., 2009] (7) IDK [Gómez-Sanz et al., 2009] (8) PDT [Padgham et al., 2013] (9) eCAT [Nguyen et al., 2012] (10) IDE-eli [Sierra et al., 2004] (11) −[Bernon et al., 2007] (12) ELDAMeth [Fortino et al., 2014] (13) −[De Wolf et al., 2006] (14) PASSIM [Cossentino et al., 2008] (15) RatKit [Çakirlar et al., 2015] (16) −[Gardelli et al., 2008] (17) −[Sudeikat and Renz, 2011] (18) −[Kaminka et al., 2002] (19) −[Kalech, 2012] (20) −[Chia et al., 1998] (21) −[Horling et al., 2000] (22) −[Micalizio and Torasso, 2014] (23) −[Rustogi et al., 1999] (24) −[Xu and Deters, 2005] (25) SaGE [Souchon et al., 2004] (26) −[Platon et al., 2008] (27) −[Mallya and Singh, 2005a] (28) −[Hägg, 1997] (29) −[Klein et al., 2003] ∗UAL: Unit and Agent Levels; IL: Integration (30) AAA [Kumar et al., 2000] Level; TF: Testing Frameworks. (31) DaAgent [Mishra and Xie, 2003] ∗∗ OMED: On-line Monitoring and Error Detection; (32) Chameleon [Kalbarczyk et al., 2005] EHS: Exception Handling Systems; (33) Guardian [Miller and Tripathi, 2004] SbA: Sentinel-based Architectures; (34) −[Fedoruk and Deters, 2003] RbA: Replication-based Architecture. (35) DARX [Guessoum et al., 2010] 30 2.6 Analysis of Techniques Aiming at Reliable MAS 2.6.2 MAS Feature Support MAS field have been extensively investigated to solve complex problems present in several applications. As a result, a vast range of technologies and techniques have been envisioned to build such systems. There are four main MAS features that designers should observe while electing a validation, testing, and/or fault tolerance approach: (1) agent architecture, (2) type of organisation, (3) openness, and (4) heterogeneity. Agent architecture dictates how the abstract concept of agent is actually implemented in source code. This influences many aspects from possible information to be monitored to time responsiveness. Type of organisation defines the social fabric of agents and thus, in the presence of an error, it can help to discover the faulty component and prevent an overall failure by communication structures. Horling and Lesser [2004] extensively describe MAS organizational paradigms. Openness of a MAS regards its numbers of agents; if new agents can be created and/or enter the system, the MAS is open, otherwise, it is close. Heterogeneity relates to the uniformity of the agent architecture present in a MAS, being homogeneous when all agents have the same architecture and heterogeneous otherwise. By the comparison showed in Table 2.2, it is important to note that: 1. Knublauch [2002] is the only testing proposal that can handle faults in every agent architecture, because it deals with low-level component within agents. 2. No approach concentrates purely on simple reflex (also called reactive) agents. A possible reason stems from the swarm intelligence field, which studies the usage of these type of agents to conceive emergent behaviour for solving complex problems. They state that reactive agents are inherently robust as a failure in a small set of them does not harm the system evolution. 3. Regarding those approaches that clearly declare the type of agent architecture/programming language, more than half uses JADE or Java to implement MASs; although they are generalist, JADE and Java demand for longer development time, which may affect the rapid prototyping philosophy that grows in the AOSE methods. Complementing the discussion about boundaries of usable approaches of both testing frameworks and simulation-based validation, on the one hand, PDT [Padgham et al., 2013] and eCAT [Nguyen et al., 2012] support goal-oriented (specifically BDI) architectures. De Wolf et al. [2006] and IDE-eli [Sierra et al., 2004] are designed to assess only teamoriented MASs and electronic institutions respectively. On the other hand, IDK [GómezSanz et al., 2009], ELDAMeth [Fortino et al., 2014], and PASSIM [Cossentino et al., 2008] comfort a wide range of agent architectures yet in a closed and heterogeneous MAS. Hence, designers/developers must know in advance the MAS features before choosing such tool. We propose the following reflection to justify the predominance of work that deal solely with close MASs. Suppose that the proposal is able to improve its agent models over time, for homogeneous MASs, it can guarantee that in certain point in the future the identification and/or response to faulty events is going to be optimal. As there is only one kind of agent, it will be able to precisely model the agent functioning. Analogously to heterogeneity, when the MAS is close (new agents cannot enter), the system can also ensure 31 2 Survey on Increasing Reliability in Multi-Agent Systems Table 2.2: Comparison of proposals with respect to the MAS Features Support. Note that only the most relevant publication of the respective project appear below. Proposed Approach AA AF/PL ToO Op He Testing in MAS −[Knublauch, 2002] SR, RS, Gb, Ub 1 Any 4 JAT [Coelho et al., 2007] SR, RS, Ub 2 Any 4 −[Lam and Barber, 2005a] Gb 1,5,8 Any 4 −[Pardo et al., 2010] Ub − − − − ACLAnalyser [Serrano et al., 2012] SR, RS, Ub 2 Any 4 SEAUnit [Çakirlar et al., 2009] RS, Gb 8 −4 IDK [Gómez-Sanz et al., 2009] SR, RS, Ub 2 Any 4 PDT [Padgham et al., 2013] Gb 4 Any 4 eCAT [Nguyen et al., 2012] Gb 2,3 Any 4 Simulation-based Design Validation IDE-eli [Sierra et al., 2004] SR, RS, Gb 1 EI 5 4 −[De Wolf et al., 2006] SR, RS, Gb −T −[Gardelli et al., 2008] SR, RS, Ub 7 C  −[Bernon et al., 2007] SR, RS 6 C  PASSIM [Cossentino et al., 2008] SR, RS, Gb, Ub 2 Any 4 −[Sudeikat and Renz, 2011] Gb 3 Any 4 ELDAMeth [Fortino et al., 2014] SR, RS, Gb, Ub 2 Any 4 RatKit [Çakirlar et al., 2015] SR, RS, Ub 7 C  Fault-Tolerant MAS −[Kaminka et al., 2002] RS, Gb, Ub −T −Kalech [2012] Gb, Ub −C4 −[Chia et al., 1998] RS, Gb, Ub −C −[Horling et al., 2000] SR, Gb −C −Micalizio and Torasso [2014] Gb, Ub −C4 −[Rustogi et al., 1999] SR, RS, Gb, Ub −Any  −[Xu and Deters, 2005] SR, Rs, Ub 2 Any 4 SaGE [Souchon et al., 2004] RS, Gb, Ub 1 Any  −[Platon et al., 2008] RS, Gb, Ub −Any 5 4 −[Mallya and Singh, 2005a] RS, Gb, Ub −Cb 4 −[Hägg, 1997] SR, RS 8 Any 5  −[Klein et al., 2003] RS, Gb, Ub −Any  AAA [Kumar et al., 2000] SR, RS, Gb, Ub −C5  DaAgent [Mishra and Xie, 2003] SR, RS, Gb, Ub −Any 5 4 Chameleon [Kalbarczyk et al., 2005] SR, RS, Gb, Ub −Any 5 4 Guardian [Miller and Tripathi, 2004] SR, RS, Gb, Ub −Any  −[Fedoruk and Deters, 2003] SR, RS, Gb, Ub −Any 5 4 DARX [Guessoum et al., 2010] SR, RS, Gb, Ub −Any 4 ∗AA: Agent Architecture - SR: Simple Reflex; RS: Reflex with States; Gb: Goal-based; Ub: Utility-based. ∗∗ AF/PL: Agent Framework/Programming Language - 1: Java; 2: JADE; 3: JADEX; 4: JACK; 5: C/C++; 6: SeSAm; 7: REPAST; 8: Others. ∗∗∗ ToO: Type of Organisation - EI: Electronic Institution; T: Team; C: Collaborative; Cb: Commitment-based. ∗∗∗∗ Op: Openness - : Close; 5: Open. ∗∗∗∗∗ He: Heterogeneity - : Homogeneous; 4: Heterogeneous. 32 2.6 Analysis of Techniques Aiming at Reliable MAS that at some point in the future the fault tolerance scheme will have models for all possible agents. This latter process will certainly take longer than the former but theoretically it also leads to optimal solutions. However, when the MAS is open, there is no guarantee that the testing, validation, or fault tolerance will be able to even detect an anomalous event. Therefore, most of the efforts intends to address the reliability issue first to close MASs, envisioning further generalisation to open MASs. Most of authors disregard the type of organisation because they assume that their approach is robust in all of them; however, their experimental setups do not cover every organisational structure. Nonetheless, a collaborative society opens up the possibility to use team-mates as comparison basis [Kaminka and Tambe, 1998] and, at same time, sets clear boundaries to possible treatments because only benevolent agents are considered. However, agents that either sends incorrect information or act to jeopardise another agent are also found in realistic applications, which might have a negative effect in the aforementioned approaches. As for competitive societies, endevours focus on increase robustness of protocols used in negotiations. Adaptability is taken into account by proposals in a structural level. Some of them are capable of rearranging functions to adapt to some changes in the tested/monitored MAS. However, these changes are restricted to simple MAS reorganisation (for instance, the death of an agent), while more complex forms of adaptation both in MAS behaviour and structure (such as, coalition formation and emergent behaviours) are not in those techniques’ scope. The majority of reviewed work makes no allusion how adaptation or emergent behaviour may influence the performance. 33 3 Spectrum-Based Fault Localisation for MASs Traditional uses of SFL have two fundamental limitations when directly applied to MASs. First, the usual abstraction of the program spectrum as the involvement of software components generates a uniform spectrum (with no useful information to discover the fault), since agents are time-persistent entities and are always perceiving and acting upon the environment. The second SFL limitation regards the autonomic facet of the agent. To localise the faulty component, SFL assumes that components output the same results for the same set of inputs; this assumption does not hold for MASs as agents might act differently while facing the same set of events. The extension described in this work, called Extended Spectrum-based Fault Localisation for MAS (ESFL-MAS), solves the first limitation by proposing the performance spectrum, which encodes the agent performance in terms of expected/not expected in a determined time step. This strategy gives a performance-oriented view over the spectrum by tracing agent behaviour expectancy during a run to provide useful diagnostic information and to solve the time-dependency problem. Concerning the second limitation, we have proposed a simple yet elegant solution, which is to execute the monitored MAS several times in order to catch multiple instances of agent behaviours for different environment settings. Additionally, we have suggested an optimisation, named MAS-Filter, which increases diagnostic accuracy by filtering low-entropy rows in the spectrum. This chapter makes the following contributions: 1. We discuss the limitations of applying SFL with commonly used types of spectrum to time-persistent and autonomous entities such as agents; 2. We describe the Extended Spectrum-based Fault Localisation for Multi-Agent Systems to diagnose agent behavioural faults when testing the system as a whole; The remainder of this chapter is organised as follows. Section 3.1 discusses main SFL concepts and present an illustrative example for sequential software. Section 3.2 introduces definitions used throughout this chapter. Furthermore, the diagnosis problem for multi-agent systems is defined. Section 3.4 describes the SFL constraints and the proposed changes in order to use SFL for MASs. Finally, Section 3.5 summaries this chapter highlighting its main topics. 3.1 Spectrum-based Fault Localisation Spectrum-based fault localisation is a dynamic program analysis technique, which requires minimal information about the system to be diagnosed. The binary search algorithm implemented in Java (first column on the left in Table 3.1) will be considered to illustrate the SFL procedure throughout this section. Briefly, this method finds the integer target given an ordered integer collection as an array. Binary search divides the sorted collection in half until the sought-for item is found, or until it is determined that the item cannot be present in the smaller collection. For instance, let us assume that this Java source code 40 3.1 Spectrum-based Fault Localisation Table 3.1: Faulty Java method for binary search. The input for test cases is composed by collection ={1,2,3,4,5}and target as presented below. Java Source Code Statement target public boolean search (int[ ] collection, int target){null [ ] 1 2 3 4 5 if (target == null) {1 1 1 1 1 1 1 1 return false; }2 1 0 0 0 0 0 0 int low = 0,high =collection.length −1; 3 0 1 1 1 1 1 1 while (low <=high){4 0 1 1 1 1 1 1 int ix =(low +high)/2; 5 0 0 1 1 1 1 1 int rc =target.compareTo(collection[ix]); 6 0 0 1 1 1 1 1 if (rc < 0){7 0 0 1 1 1 1 1 high =ix −1; 8 0 0 1 1 0 0 0 }else if (rc > 0){9 0 0 1 1 1 1 1 //Bug: sign ’−’ instead of ’+’ - - - - - - - - low =ix −1; 10 0 0 0 1 0 1 1 }else {11 0 0 1 0 1 0 0 return true; }12 0 0 1 0 1 0 0 return false; }13 0 1 0 0 0 0 0 }Error 0 0 0 1 0 1 1 has a bug in the sign of Statement 101where the sign ’−’ in the equation low =ix −1 should be a ’+’ sign. Note that this fault can be latent in the system and only leads to errors under certain conditions, but, when it is activated, it leads to an array-out-of-bound exception in the method execution. We first need to introduce the concept of spectrum to correctly understand SFL. Spectrum is a set of run-time data of the dynamic behaviour exhibited by a piece of software. Literature shows that exist different forms of recording such a spectrum (see Reps et al. [1997], Harrold et al. [1998]). Regardless its form, a spectrum can always be abstracted in terms of two general elements, which are: •Component. It is an element of the system that, for diagnosis purposes, is considered to be atomic. For instance, we consider the statement as the atomic element (i.e., component) of the spectrum in the example. •Transaction. It is a specific information about the component. In our illustrative example, this specific information is the involvement of a particular statement. If a particular statement was involved in a given execution, the spectrum is filled with the number 1; otherwise, it is filled with the number 0. After mapping the software into the aforementioned elements, the next step is to gather 1Note that the commented line is not accounted for in SFL since the Java compiler excludes any comment from the binary version. 41 3 Spectrum-Based Fault Localisation for MASs S-2 S-1 F T S-12 S-11 F T S-5 S-6 S-3 S-13 S-4 T F S-8 S-7 F T S-10 S-9 F T collection = {1,2,3,4,5} target = 3 (a) Execution path for inputs collection ={1,2,3,4,5}and target = 3 S-2 S-1 F T S-12 S-11 F T S-5 S-6 S-3 S-13 S-4 T F S-8 S-7 F T S-10 S-9 F T collection = {1,2,3,4,5} target = 2 (b) Execution path for inputs collection ={1,2,3,4,5}and target = 2 Legend Input If Condition Variable Declare While Loop Output Execution Path T Condition is true F Condition is false S-X Statement X Figure 3.1: Work-flow of the Java code in Table 3.1 with the execution flow of two test cases. It outputs the expected result in (a), whereas it has unexpected output in (b). run-time profiles containing the specific information about each system component from runs. These runs are execution of a set of test cases that provide different inputs and expected outputs. A test case result can be either nominal (“pass”), representing that the system had the expected output, or an error (“fail”), representing an unexpected software output; this information of in which test case the software failed constitutes another column vector, the error vector. Back to our example, let us suppose the method was tested for seven test cases where the input collection ={1,2,3,4,5}is immutable while the target input has values according to presented in Table 3.1. For each of these test cases, the dynamic behaviour of the search method was collected as a statement-hit spectrum and it is shown in the right side of Table 3.1. One must bear in mind that this form of spectrum indicates whether or not a certain code statement was executed given a test case. Figure 3.1 presents the work-flow of the Java code in Table 3.1 as well as the execution paths for test cases target = 3 (Figure 3.1.a) and target = 2 (Figure 3.1.b), considering collection ={1,2,3,4,5}for both cases. In the case of a statement-hit spectrum, the process to build the column information for a test case is: as the execution path progresses through the work-flow, positions of involved statements are set to 1, whereas positions of 42 3.1 Spectrum-based Fault Localisation non-involved statements are set to 0. As an example, let us build the spectrum’s column for both test cases in Figure 3.1. Following the execution path in Figure 3.1.a, the first involved statement is S-1 and consequently the first position of the column is set to 1; then, the next involved statement is S-3 that, at this point of the run, results in [1 0 1] (observe the non-involvement of S-2 represented by 0 in the respective vector position); setting as 1 every involved statement along the execution path, which are: S-1, S-3, S-4, S-5, S-6, S-7, S-9, S-11, and S-12, the final spectrum’s column for test case target = 3 is [1 0 1 1 1 1 1 0 1 0 1 1 0] as shown in Table 3.1. In the other test case, one can observe the complete different execution path in Figure 3.1.b that involves statements: S-1, S-3, S-4, S-5, S-6, S-7, S-8, S-9, and S-10 (the last two activated after another while cycle); using the same building process, the spectrum’s column is [1 0 1 1 1 1 1 1 1 1 0 0 0] as presented in Table 3.1. Building the error vector requires to compare the expected output and actual software output of the test case; if the output is the expected one, the error vector is set to 0 in the test case position, otherwise, it is set to 1. For Figure 3.1.a, the expected output is true because the target element 3is indeed present in the collection {1,2,3,4,5}. Observing the last executed statement S-12 and, given the Java code, one can see that the test case execution returned the expected result; therefore, the error vector is set to 0 in the respective position. Similarly, for Figure 3.1.b, the expected output is also true due to the presence of the target element 2in the collection. However, one can see that the execution path finishes in S-6, which is a variable declaration statement. The fault activation in S-10 results in a negative value of variable ix;ix is then used as index of collection in S-6 causing an array-out-of-bounds exception given the attempt to access a negative index in an array. For that reason, the test case has an unexpected output and the error vector is set to 1 in the respective position (see Table 3.1). After acquiring information for every test case, SFL benefits from both spectrum and error vector to localise the faulty statement. Generically, SFL assumes the hypothesis that closely correlated components are more likely to be relevant to an observed failure. In practice, the basic idea is that comparing transactions over multiple runs and then computing the suspiciousness values of components can indicate which of these is the most likely to be the faulty one. Resemblances between binary vector (e.g., error vector) and nominally scaled data (e.g., spectrum) are quantified by means of similarity coefficients. These coefficients measure similarity essentially using dichotomy terms, which for our illustrative example refers to the involvement of statement jin the test case i(aij) and result of test case i(ei), formally defined as: c00(j) = |{i|aij = 0 ∧ei= 0}| (3.1) c01(j) = |{i|aij = 0 ∧ei= 1}| (3.2) c10(j) = |{i|aij = 1 ∧ei= 0}| (3.3) c11(j) = |{i|aij = 1 ∧ei= 1}| (3.4) where, the c11(j)is the number of failed runs in which statement jis involved, c10(j)is the number of passed runs in which statement jis involved, c01(j)is the number of failed 43 3 Spectrum-Based Fault Localisation for MASs Table 3.2: The values of dichotomy terms for SFL example. Dichotomy Statement Element 1 2 3 4 5 6 7 8 9 10 11 12 13 c11 3 0 3 3 3 3 3 1 3 3 0 0 0 c10 4 1 3 3 2 2 2 1 2 0 2 2 1 c01 0 3 0 0 0 0 0 2 0 0 3 3 3 c00 0 3 1 1 2 2 2 3 2 4 2 2 3 runs in which statement jis not involved, and c00(j)is the number of passed runs in which statement jis not involved. Aiming at illustrating the mechanism of filling dichotomy terms, let us focus on the column of Statement 8, which is [0 0 1 1 0 0 0], and correlate it with the error vector [0 0 0 0 0 1 1]. First, second, and fifth positions of both vectors have value 0, therefore c00 = 3. In the third position, involvement column has value 1 whereas error vector has value 0, producing c10 = 1. Forth position of both vector has value 1, thus c11 = 1. Finally, c01 = 2 because, in sixth and seventh positions, involvement column has value 0 and error vector has value 1. Table 3.2 shows all dichotomy terms for every statement of our example. Let us finish the diagnosis process of our example by using the Jaccard coefficient (C16) to compute the suspiciousness value of each statement (see Table 3.3). As an example, we substitute dichotomy values of Statement 8 into Jaccard formulae as illustrated below: C16 =c11 c11 +c10 +c01 =1 1+1+2 = 0.25 (3.5) For the illustrative example, by computing suspiciousness values and ranking statements with respect to them (see Table 3.3), SFL (correctly) identifies Statement 10 as the most likely location of the fault. Clearly, this example has a small number of test cases and statements; nonetheless, it fully illustrates the SFL diagnostic process. Table 3.3: The Jaccard similarity coefficient values and ranking for SFL example. Statement 1 2 3 4 5 6 7 8 9 10 11 12 13 Coefficient Value 0.43 0.00 0.50 0.50 0.60 0.60 0.60 0.25 0.60 1.00 0.00 0.00 0.00 Ranking (D) 8 10 6 7 2 3 4 9 5 1 11 12 13 In a nutshell, SFL is a diagnosis technique that relies on dynamic analysis of the system, not requiring any additional modelling effort. It assumes that exists a high correlation between the fault activation and the system failure. System components are ranked with respect to their suspiciousness values computed using predefined heuristics. SFL requires short time to compute a diagnostic report as it: 1. Initialises the dichotomy terms: O(1). 44 3.2 Concepts and Definitions for SFL in MAS 2. Computes the suspiciousness value per component for Ntest cases: O(M×N). 3. Ranks components of Maccording to their suspiciousness values: O(M×log (M)). Therefore, the overall time complexity is O(M×N+M×log (M)). The space complexity is O(M×N)for storing the spectrum and O(M)for storing the diagnostic report. Since O(M×N)has a faster growth than O(M), the latter can be disregarded. 3.2 Concepts and Definitions for SFL in MAS A multi-agent system is a computational system composed by a set of agents. Each of them (agents) is able to autonomously reason as well as sense and act upon a certain environment, leading to the satisfaction of its own (and sometimes shared) goals. Agents are time-persistent entities, that is, they are continuously operating to fulfil their goals. Definition 1 (Multi-Agent System).A multi-agent system MAS consists of a set of agents AGS ={Ag1,··· , Agm,··· , AgM}that are situated in an environment E. Thus, a MAS is a tuple MAS =hE, AGSi[Lettmann et al., 2011]. The MAS runs during a limited time interval, which can be discrete (represented by non-negative integers) or continuous (represented by real numbers) [Bhattacharya and Waymire, 1990]. This thesis considers the discrete-time representation because (1) continuous time can be sampled and (2) we intend to work within the boundaries of finitedimensional events2. Throughout this thesis, we refer to an unit of time either using time frame or time step. Example 1 In order to explain the basic concepts and the application of spectrum-based fault localisation in MASs, we make use of a running example. Figure 3.2 shows this example MAS which is borrowed from our experimental setup that will be thoroughly described in ??. For the sake of clearness, we have reduced the number of agents and size of the environment of this example. In a nutshell, agents find themselves exploring an area searching for the gold nuggets spread over the environment; they aim to collect as much gold nuggets as they can and to deliver them to a depot where the nuggets are safely stored. Let us assume that agent Ag5erroneously compute its distance from a gold nugget due to an unforeseen bug in the reasoning process unintentionally left by the designer/programmer; as a result of this bug, Ag5has lower performance in some specific situations than it should have. Throughout this chapter, it is shown how to use SFL to pinpoint the faulty agent. 2A finite-dimensional event depends only on the values of the process at finitely many time points [Bhattacharya and Waymire, 1990]. 45 3 Spectrum-Based Fault Localisation for MASs D 1 3 5 2 4 (a) Test Case 1 D 1 2 3 4 5 (b) Test Case 2 Legend X Agent X D Depot Gold nugget Obstacle Figure 3.2: Goldminers example used as the illustrative example throughout this chapter. After defining the basic MAS elements, it is needed to assess its performance by measuring observable variables of both the environment and the set of agents. For instance, a MAS aiming to control traffic lights uses environment variables such as traffic flow to measure MAS performance. Likewise, utility-based MASs measure the global utility (which is commonly used as a system performance measure) by summing the utility of all agents, that is, applying a function over observable variables of agents. In our running example, the MAS performance can be measured by the amount of gold nuggets in the depot. Definition 2 (Measurable Space).Ameasurable space is a set Z, together with a nonempty collection Z, of subsets of Z, satisfying the following two conditions: 1. For any X, Y in the collection Z, the set X∩Yc3is also in Z. 2. For any X1, X2,··· ∈ Z. The elements of Zare called measurable sets of variables. Definition 3 (Measure of MAS).Let (E, E)and (AGS, AGS)be two measurable spaces. Ameasure of MAS performance consists of a two non-empty subsets ME⊂ E and MAGS ⊂ AGS together with µ:f(hE,AGSi, n)→Rthat maps the performance of a MAS in time n(considering discrete time) to a real number. It uses as arguments the measurable set of variables of the tuple hE, AGSi. 3X∩Ycis the set of all values of Xthat are not in Y 46 3.2 Concepts and Definitions for SFL in MAS Note the strong connection between MAS and environment (Definition 1) termed by Ferber [1999] as “the agent/environment duality”. Thereby, we formally define our understanding of an environment, which introduces the necessary components to define test cases for MASs. Definition 4 (Environment).An environment Eis described as a tuple E=hS, s0,Ai where •S={s0, s1,···} is a countable set of environment states with an initial state s0. • A = × Agm∈AGS AAg denotes all joint actions (of agents) that can be performed in the environment. Definition 4 does not explicitly introduce sets of environment objects other than agents, since all (observable) information of these objects are considered to be incorporated into the set of environment states S. In our example, the depot and positions of gold nuggets are objects that are modelled within the environment state set. A test case, in ordinary sequential programs, comprises input values and excepted output values. Defining the input and output of MASs is straightforward by means of the environment and the measure of MAS. Definition 5 (Input, Output).Given a multi-agent system MAS situated in an environment Eand measured by µ, then the inputs comprise the initial state s0of Eand initialisation parameters for agents (ags0). The outputs comprises the measure µof MAS. With this definition of input and output we are able to define a test case for a MAS and its evaluation. Definition 6 (Test case).Given a multi-agent system MAS, then a tuple hI, Oiis a test case for MAS if and only if: •Iis a set of values for each object specifying the environment state s0and a set of initialisation parameters ags0for every agent Agm∈AGS. •Ois a set of values specifying expected MAS outputs when measured by µ. In our setting, test case evaluation works as follows. First, the environment is initialised with state s0and agents with parameters ags0. Subsequently, the MAS is executed. The outputs computed by µare compared with the expected values stated in the test case. If the computed output value is not equivalent to the expected value, the MAS fails the test case during that specific period. Otherwise, the MAS passes the test case during a specific period. Note that, unlike in “traditional” software, running a MAS with a test case yields a vector of errors where each element is the passed/failed MAS status at time n. 47 3 Spectrum-Based Fault Localisation for MASs Example 2 A test case for our running example from Figure 3.2.a is I={depot = (4,6), gold ={(1,4) ,(2,2) ,(2,7) ,(3,7) ,(4,4) ,(4,11) ,(5,8) ,(6,6) ,(7,1) ,(7,10) , (8,6) ,(11,1) ,(11,5) ,(11,7) ,(11,9) ,(11,12) ,(12,7)}, obstacle ={(1,3) ,(2,3) ,(3,3) , (4,3) ,(5,3) ,(6,3) ,(7,3) ,(8,3) ,(1,9) ,(2,9) ,(3,9) ,(4,9) ,(5,9) ,(6,9) ,(7,9) ,(8,9) , (9,6) ,(10,6) ,(11,6) ,(12,6)},ags0={(4,1) ,(1,11) ,(11,3) ,(9,11) ,(8,7)}} and O= (1 ∗collectedgold)/n. The MAS has to be executed during a period so it is possible to establish when it passes and/or fails the test case. Avižienis et al. [2004] define fault-related terms as: a failure is an event that occurs when delivered service deviates from correct service; an error is a system state that may cause a failure; and a fault is the cause of an error in the system. In this thesis, we consider that faults in agents’ behaviour depend on a given context, i.e. on how each agent interprets that particular situation [Platon et al., 2007]; and, mainly, these faults are a systemic matter as it might affect the overall performance [Klein et al., 2003]. More specifically, the term “faulty agent” is used to refer to an agent that either is not healthy and needs to be repaired or has been induced to a failure state (known as cascading effect). Diagnosis is the task of pinpointing the faulty component that led to symptoms (failure/error). In software, the set of components can be defined at any granularity level: a class, a function, or a block. The lower the granularity level gets, the more focused is the diagnosis; even though such low granularities require more computational effort [Zamir et al., 2014]. Hence, following Reiter’s formalism [Reiter, 1987], the diagnosis problem for MASs can be defined as follows. Definition 7 (Multi-Agent Diagnosis Problem).Given a multi-agent system MAS that has a set of agents AGS and a set of observations OBS for test case hI, Oi, then the diagnosis problem is to find the faulty agent which is responsible for the mismatch between the expected MAS performance and the observed one. The multi-agent diagnosis problem is defined with granularity at the agent level and thus considering agents as black boxes. This is a fair assumption when different parties implement agents reasoning and do not completely share their knowledge and/or architecture. On the one hand, the technique proposed in this chapter is not able to identify the specific bug inside the code of the faulty agent; on the other hand, however, it has the advantage of being agnostic to programming languages and agent architectures. 3.3 Limitations of SFL As stated by Definition 7, this work deals with agent-level diagnosis, because it focuses on testing the MAS as a whole ensuring that agents’ performance is nominal when facing several environmental conditions. We envision that, at run-time, the agent-level is the most advisable one as faulty agents are simply removed from the running MAS to avoid performance degradation. Therefore, component abstraction discussed in Section 3.1 is mapped to agents. The challenge when applying SFL in MASs is to map the transaction abstraction so the diagnostic process have useful information about agent to be able to 48 3.3 Limitations of SFL pinpoint the fault. Current SFL approaches have limitations and such limitations will be discussed in this section with the purpose to ground the proposed extensions. 3.3.1 Time Persistence A limitation of the discussed SFL system assessment approach is related to the assumption that every test case is only function of the input variables [Abreu et al., 2009]. While a test case indeed solely depends on inputs when diagnosing non-time-persistent software, such an abstraction is unable to represent MAS performance as it is measured during some period (see Definition 3). For instance, let us assume that for both test cases in Figure 3.3 the expected output is have an empty depot at n= 3. As it can be seen, this expectation is met, thus the error vector is [0,0]. One can see that unexpected MAS outcomes before n= 3 are neglected as they are not encoded in the error vector. Disregarding the effect of time on the MAS performance implies that the perceived system degradation may be completely overlooked by the diagnostic algorithm and, consequently, the diagnostic quality is negatively affected. Moreover, the hit spectrum is the far most commonly used type of spectrum [Harrold et al., 1998]. It encodes the component’s activity in terms of involved/not involved in a given test case. A limitation of the SFL approach presented in Section 3.1 is related to high level of abstraction enforced by hit spectrum as it does not provide useful information about the state of the agent during an execution. Since agents are time-persistent entities, they are always active and acting upon the environment; this creates spectra with very low entropy. Low entropy in the spectrum means that there is less useful information in the spectra and, consequently, decreasing SFL diagnostic quality [Gonzalez-Sanchez et al., 2011, Campos et al., 2013]. Therefore, block hit spectra is not suitable to MASs. This conclusion can be generalised to other types of spectrum that do not account for time within transactions. Using a simpler version of our running example presented in Figure 3.3 to illustrate this limitation, consider that agents’ activities are encoded as hit spectra. Every agent at n= 1 has acted upon the environment, thus its row in the hit spectrum is [1,1,1]. Following, Ag1,Ag2, and Ag3perform a Move Left,Pick, and Move Up actions respectively at n= 2, resulting also in a [1,1,1] row. This reasoning follows throughout both MAS runs, creating hit spectra fulfilled with 1’s, thus impairing the diagnostic accuracy. Time persistence is not specific to MASs; on the contrary, it is intrinsic to well-known software systems such as web servers. In contrast to our performance spectrum that effectivily encode agents’ activity during some time, Casanova et al. [2013] deal with diagnosing architecture run-time failures aiming at self-healing systems. Authors point out that (similarly to our case) traditional proposals of transaction do not correctly encodes the system’s time progression. Their solution is to map the transaction as a two lower-level events: a message sent from the origin and a message arrived at destination. However, this solution is not sufficient to MASs because of two reasons. First, agents do not necessarily have to interact with each other to achieve their goal(s); they choose whether to do so. In the case of Casanova et al. [2013], interactions among components are fundamental to the whole 49 3 Spectrum-Based Fault Localisation for MASs Algorithm 1 ESFL-MAS Inputs: PS Output: Diagnostic report D 1c= [0]2×2×M 2for (AN×M, eN×1)∈PS do 3(A0, e0)←− (Ax, ex) : x={n| ∃i, j :Ani 6=Anj} 4c0 pqm ←− |{n|A0 nm =p∧e0 n=q}| : (p∈ {0,1}, q ∈ {0,1}, m ∈ {0,··· , M −1}) 5c←c+c0 6d←− s(c) 7D←− Sort(d) 8return D The algorithm for computing the dichotomy terms of each agent (line 4 in Algorithm 1) is presented in Algorithm 3. It works by iterating over all elements in A(lines 2 and 3), thus adding 1 to the previous value in the dichotomy table c(lines 4 to 6). This algorithm is the heuristic-based SFL’s core. Both Algorithms 2 and 3 were presented separately for the sake of clearness. In practice, the MAS-Filter application and the dichotomy terms feeding were done inside the same cycle that iterates over Nand M. The upper-bound values for the complexity of ESFL-MAS algorithm is O(I×J×M×N). The space complexity is O(I×J×M×N)for storing the collection of performance spectra. Even though ESFL-MAS is more complex than original SFL, it is still solvable in polynomial time and can be considered light weighted. Algorithm 2 MAS-Filter Inputs: (A, e) Output: Filtered performance spectrum (A0, e0) 1A0= [0]N×M 2e0= [0]N 3for n∈ {0,··· , N −1}do 4skip ←− true 5for m∈ {0,··· , M −2}do 6if Anm 6=An(m+1) then 7skip ←− false 8break 9if skip then 10 continue 11 A0 n←− An 12 e0 n←− en 13 return (A0, e0) 56 3.5 Summary Algorithm 3 feedDichotomyTerms Inputs: (A, e) Output: Dichotomy table c 1c= [0]2×2×M 2for n∈ {0,··· , N −1}do 3for m∈ {0,··· , M −1}do 4p=Anm 5q=en 6cpqm =cpqm + 1 7return c 3.5 Summary MASs are constantly susceptible to several threats that can jeopardise their nominal performance. To detect any abnormality on agent behaviours is a paramount step to ensure performance; however, in practice, error detection rarely exhibits 100% precision. Moreover, when there are multiple cooperative agents, errors might be masked by other agents and possibly go undetected. As stated by [Kalech and Kaminka, 2011], “diagnosis is an essential step beyond the detection of the failures. Mere detection of a failure does not necessarily lead to its resolution.” Motivated by this, we devised and discussed an approach, called ESFL-MAS, which is able to identify agents that may jeopardise the overall performance through run-time profiles of the system while requiring minimal information about it. We mapped MAS concepts to basic elements of SFL, being agents and their expected behaviour at given time respectively mapped to components and transactions, thus incorporating time within the spectrum. Diagnosis at the system level steer the proposed technique towards a performance-oriented direction, resulting in the so-called performance spectrum. Lastly, some data do not effectively contributed to localise the faulty agent given the intensive monitoring of agents; thus we suggested MAS-Filter that increases diagnostic accuracy by excluding low-entropy rows in spectra. 57 58 Chapter 4 Empirical Evaluation of Similarity Coefficients for ESFL-MAS Literature has shown that there is no standard similarity coefficient that yields the best result for SFL [Yoo et al., 2014, Hofer et al., 2015, Le et al., 2013]. Empirical evaluation is therefore essential to establish which set of heuristics excels for the specific context to which SFL is being applied. To the best of our knowledge, SFL has not as yet been applied to diagnose behavioural faults in MASs; hence, there is the need to empirically evaluate different formulae using known faults to compare the performance yielded by several similarity coefficients. This chapter empirically determines the best similarity coefficients for SFL including the necessary extensions in the MAS context. Our experiments study an exhaustive list of similarity coefficients and, as some of them behave very similar, a clustering analysis was performed. Clusters were formed based on the diagnostic performance of heuristics. The performance of similarity coefficients was also assessed regarding the influence of quantity of available data to the Extended Spectrumbased Fault Localisation for Multi-Agent Systems (ESFL-MAS) and, due to ESFL-MAS dependence on the error detection phase, the impact that the precision of error detection mechanisms has on ESFL-MAS was investigated. Based on the empirical results, Accuracy, Coverage, Jaccard, Laplace, Least Contradiction, Ochiai, Rogers and Tanimoto, SimpleMatching, Sorensen-Dice, and Support coefficients excel by showing stability while varying the number of passed and failed time steps as well as by reaching high diagnostic accuracy for low error detection precision. This chapter makes the following contributions: 1. We present an experimental study on the impact of 42 heuristics in the ESFL-MAS diagnostic accuracy using the well-known and real-world representative Pickup and Delivery Problem as test suite; 2. We show that for ESFL-MAS the Accuracy, Coverage, Jaccard, Laplace, Least Contradiction, Ochiai, Rogers and Tanimoto, Simple-Matching, Sorensen-Dice, and Support outperform the remainder coefficients across the entire quantity and quality data space (yielding 96.26% diagnostic accuracy) in the specific conditions of our test suite. 59 4 Empirical Evaluation of Similarity Coefficients for ESFL-MAS The remainder of this chapter is organised as follows. Section 4.1 explains both the created test suite and the data collection process. In Section 4.2, we evaluate the effects of different similarity coefficients in the diagnosis through varying the amount of available data and the precision of the error detection phase that precedes ESFL-MAS. Finally, Section 4.3 summarises the main topics of this chapter. 4.1 Experimental Setup The empirical assessment herein presented aims to discover the set of similarity coefficients that yields the best results in terms of diagnostic quality. This section describes the test suite used in the experiments, the data extraction process, and the metric used to evaluate the ESFL-MAS performance. 4.1.1 Test Suite We use an instance of the Pick-up and Delivery Problem (PDP) [Savelsbergh and Sol, 1995] to test our approach because (i) it is well-known and (ii) it is a real-world representative problem. Problems of this kind are highly dynamic, and decisions have to be made under uncertainty and incomplete knowledge. Briefly, it consists of mobile vehicles retrieving and delivering a set of items. The PDP is a well-studied, NP-hard problem and, given its inherent distribution and decentralisation, MASs offer an interesting solution for PDP [Fischer et al., 1996]. Examples of PDP solved through agents include ride-sharing services [Agatz et al., 2012], application of mobile robots in missions [Posadas et al., 2008] and automated guided vehicle employed in many industrial environments [Grunow et al., 2005]. The Second Edition of the Multi-Agent Programming Contest (MAPC)1[Dastani et al., 2007] provides an instance of PDP known as the GoldMiners scenario in which its multiple agents work under uncertainty and responsive situations, i.e., new destinations become available in real-time and are immediately eligible for consideration. GoldMiners implements fundamental concepts of MASs, such as autonomy, team-work coordination, high-level interaction, as well as partial and local perception of the environment. Another reason to use the MAPC’s implementation of GoldMiners is that all components composing the system (which include world model, agents’ reasoning, and interaction protocols) was previously tested and validated by the MAS community. For our purposes, this assure (in a higher degree of confidence) that only our injected faults will contribute to dysfunctional behaviours. 1The MAPC is an annual competition that, since 2005, aims at providing suitable test suite offering key problems for the community to test agent-oriented programming approaches. 60 4.1 Experimental Setup Figure 4.1: Jason’s view of the MAPC Goldminers scenario (screenshot). From several MASs available in the MAPC, we chose the one programmed in AgentSpeak [Rao, 1996], an agent-oriented programming language, while agents were run using Jason [Rafael H. Bordini, 2007], an interpreter for an extended version of AgentSpeak. The choice was made given our previous experience using AgentSpeak [Rossetti et al., 2002, Rossetti and Liu, 2005b,c,a] and the fact that the Jason team won the Second Edition of MAPC. The MAS aims to solve the PDP by finding a schedule that delivers as many items as possible at the lowest cost while cooperating in a dynamic environment. The environment is a grid-like world where agents can move to a neighbour cell. Agents explore the environment avoiding obstacles and collecting gold nuggets. They also can communicate and coordinate their actions in order to collect as much gold nuggets as possible and to deliver them to the depot where they can be safely stored. In addition, agents have only a local view of the environment, their perceptions might be incomplete, and the executed action may fail. Research on MASs encompasses different aspects of their artefacts (agents, environment, and so forth) and functioning (organisation, type of social behaviour, knowledge representation, and so forth). As aforementioned, ESFL-MAS is able to diagnose the faulty agent regardless its architecture and knowledge representation. Nevertheless, MAS organisation and type of social behaviour (mainly cooperation) may impact on ESFL-MAS performance. Firstly, when cooperation exists, agents work in high synergy which might contribute to very similar choices influencing the performance spectrum. Secondly, when there is no organisation, agents do not have strict roles in the MAS and so agents’ choices might more easily jeopardise another agent performance. Hence, seeking completeness of the test suite and based on previous work in MAS organisations [Stone and Veloso, 2000, Horling and Lesser, 2004], we implement a modified version of the Jason implementation of MAPC’s GoldMiners. Specifically, the original Jason implementation relied on a twofold strategy: first, a priori allocation of agents’ search quadrants and, second, a team-work coordination aiming to find and carry gold nuggets to the depot. Modified MASs vary both in the coordination and in spatial organisation (resource allocation) dimensions resulting in the following types of MAS: 61 4 Empirical Evaluation of Similarity Coefficients for ESFL-MAS 1. Non-Coordinated and Non-Organised (NCNO): Agents work individually (not cooperatively) and do not receive a search quadrant (loose spatial organization); 2. Non-Coordinated and Organised (NCO): Agents work individually but each of them has an assigned search quadrant; 3. Coordinated and Non-Organised (CNO): Agents coordinate the gold-nugget search, yet there is no allocated quadrant. 4. Coordinated and Organised (CO): Agents coordinate the gold-nugget search as well as have an assigned search quadrant. As modules responsible for interaction among agents and organisational composition are Table 4.1: Description of type of faults - Highlighted rows represent the hand-seeded faulty versions and the others are generated through mutation operators. Qnt. Fault Description NCNO NCO CNO CO 1Agent does not respect its search quadrant ×√×√ 1Agent does not communicate gold-nugget positions × × √ √ 1Agent has a delayed response to an event √ √ √ √ 1Agent gets stuck in a specific goal √ √ √ √ 1Agent gets the farthest gold nuggets. √ √ √ √ 3Delete a belief in the agent. √ √ √ √ 3Delete a plan in the agent. √ √ √ √ 3Delete the condition part of a rule. √ √ √ √ 3Replace the triggering event operator of a plan by another operator. √ √ √ √ 3Delete the context of a plan if it is non-empty or not set true. √ √ √ √ 3Delete the body of a plan if it is non-empty or not set true. √ √ √ √ 3Delete a formula in the body of a non-empty plan. √ √ √ √ 3Swap the order of any two adjacent formulae in the body of a plan that contains more than one formula. √ √ √ √ 3Replace the operator of an achievement goal or a mental note formulas by another one. √ √ √ √ 3Replace the subset of receivers in a communication action. × × √ √ 3Replace the illocutionary force in an action for sending messages by another one. × × √ √ 3Delete a propositional content in the message content. × × √ √ 62 4.1 Experimental Setup independent from the agent reasoning and other MAS functions, the modified versions inherit the reliability from the original implementation. Given these baseline (correct) versions, simulating real faults offer a more direct way to assess the proposed technique. These faults can be hand-seeded or seeded by mutation through rules (called mutation operators). We used both of these strategies for different purposes. Hand-seeded faults aim to emulate dysfunctional behaviours specifically for the aforementioned strategy implemented by the Jason Team and, moreover, faults seeded by mutation rules automatically build a set of validated faulty versions as we have used mutation operators proposed by Huang et al. [2014]. In this work we have used the (as called by the authors) high-level mutation operators for Jason. Table 4.1 gives an overview of the faulty versions in the test suite. Each of these faulty versions contains a single injected fault. In the test suite we were not able to use all created faults for all types of MASs. For instance, Fault 2 cannot be applied to non-cooperative MASs because they inherently do not broadcast any gold nugget positions. Thus, signs √ and ×in Table 4.1 represent whether a fault has been injected (√) or not (×). This test suite covers homogeneous and closed MASs in which agents co-habit in an uncertain environment and may organise to optimally allocate resources and/or interact to establish a team cooperation. Several MASs with such features have been used to solve real-world problems such as those aforementioned in the MASs for PDPs [Agatz et al., 2012, Posadas et al., 2008, Grunow et al., 2005] and we can add traffic control [Passos and Rossetti, 2010b] and shop-floor management [Leitão et al., 2012]. 4.1.2 Data Acquisition A two-step process (shown in Figure 4.2) generates the spectra required by the experiments. In the first stage, we collect simulation logs while in the second we train an error detection mechanism and use such simulation logs to generate the required performance spectra. Collecting Logs A MAS initially configured according to a given test case is executed to obtain logs from both agents and the overall system. These logs were collected for every test case and they contained the amount of gold nuggets carried by each agent and the total amount of nuggets in the depot for each time step of a simulation. For the experimental setup, we randomly generated 5 test cases and each of them corresponded to a set of initial positions for: all agents, the depot, and all 400 gold nuggets. Aiming to collect information to generate spectra, the MAS (composed by 25 agents) was executed 75 times for each test case during 1000 time steps. Therefore, we built in total 53,250 performance spectra each with 1000 ×25 dimension, including every seeded fault and MAS version. 63 4 Empirical Evaluation of Similarity Coefficients for ESFL-MAS 1 >> Agent 25 2 >> Agent 17 3 >> Agent 09 4 >> Agent 10 ...................... ...................... ESFL-MAS Diagnosis (A, e) Test Cases Faulty MAS Simulation Simulation Correct MAS Error Detection Compare Performance Generate Performance Thresholds Logs Logs Figure 4.2: Experimental Phases Expected MAS Performance and Error Detection Both test cases and performance spectra demand for measurements to verify the overall MAS and agent correctness. Agents and the MAS are respectively measured by (1) the amount of carried gold nuggets in each time frame and (2) the amount of gold nuggets in the depot. However, we still need to define the expected MAS performance and error detection mechanism. As Goldminers can be seen as an PDP instance, the MAS expected output is the average number of gold nuggets in the depot for each time frame. We run the MAS correct version and compute the performance baseline. While assessing faulty versions, time steps with performance values above the baseline are marked as passed (en= 0) and below as failed (en= 1). Formally, the system assessment have the underlying pass and fail baseline defined as: en=(1,if #dn<Φ(n) 0,otherwise (4.1) where #dnis the number of gold nuggets in the depot at time nand Φ(n)is the baseline inferred from the MAS correct version, which can be seen as the expected output of the MAS. The baseline of a test case is given by: Φ(n) = #dmax nmax ·n(4.2) where #dmax is the maximum number of gold nuggets in the depot and nmax is the maximum length of time that simulation had run. 64 4.1 Experimental Setup An error detector for agents is also necessary to generate the performance spectra. In this manner, we emulated an error detection phase in our experiments to assess ESFL-MAS, even though these mechanisms are not within the scope of this work. Error detection for Miner agents is calculated similarly to MAS expected performance. We compute the average amount of gold nuggets carried by each agent in a certain time frame and used this value as baseline to detect whether the agent is performing as expected (Anm = 0) or not (Anm = 1) for time n, therefore mapping collected logs to performance spectra. Formally, the agent error detection have the underlying pass and fail baseline defined as: Anm =(1,if #Agmn<Ψ(n, m) 0,otherwise (4.3) where #Agmnis the number of gold nuggets carried by Agmat time nand Ψ(n, m)is the baseline inferred from the Agmcorrect version, which can be seen as the nominal behaviour of the agent. The baseline of an agent is given by: Ψ(n, m) = #Agmtotal nmax ·n(4.4) where #Agmtotal is the total number of gold nuggets carried by Agmand nmax is the maximum length of time that simulation had run. 4.1.3 Evaluation Metric As ESFL-MAS returns a list of agents sorted by their suspiciousness values (see Definition 10), diagnostic performance is expressed in terms of diagnostic quality (also referred as accuracy) that evaluates how many agents need to be inspected before the faulty agent is found. If other agents have the same similarity coefficient as the faulty agent, we use the average ranking position for these agents. Diagnostic quality is defined as [Steimann et al., 2013] Q=1−|{j|Sj> Sf}|+|{j|Sj≥Sf}|−1 2(M−1) ∗100% (4.5) where Sjand Sfdenote the suspiciousness value for agent jand for the faulty agent respectively, and Mis the total number of agents in the system. Intuitively, the |{j|Sj> Sf}| term represents the number of agents ranked in front of the faulty agent whereas |{j|Sj≥Sf}| represents the number of agents with same or higher than the suspiciousness value of the faulty one. This metric assumes that, on average, half of agents with same suspiciousness values will be inspected until reaching the fault. 65 4 Empirical Evaluation of Similarity Coefficients for ESFL-MAS 4.2.1 On the Impact of Observation Quantity In the previous results, we have assumed that there is enough time to run the MAS several rounds under different conditions to collect a considerable amount of measurements. In practice, however, the tester works under short-time constraints or he/she does not want to extensively assess the system. To investigate the influence of the amount of available data on ESFL-MAS performance, we evaluate Qwhile varying the number of passed (Np) and failed time steps (Nf) that are available. The spectrum time-line is not rearranged during the variation of both Npand Nf; the process here is to randomly exclude non-consecutive time steps. We did not want to compromise the consistency of our data, even though ESFL-MAS assumes that time steps are independent. Since the ratio of failed and passed time steps is very small (nearly 0.02) and no previous experiment analysing the ESFL-MAS sensitivity have been performed, we study the influence of the quantity of available data on the diagnostic accuracy Qacross the entire range of available data. Thus, Npand Nf are varied from 0.001% to 100% of the total number of passed and failed time steps and results are presented in logarithmic scale. Figures 4.4 and 4.5 show such evaluations of Groups NCNO-01, NCNO-02, and NCNO-07, and CO-01, CO-02, and CO-05, respectively. They allow a comparison of the ESFL-MAS behaviour across the two most different MAS versions as well as of groups of the same MAS version. For each graph, we averaged Qover 1000 randomly selected combinations of passed and failed time steps until the variance in the measured values of Qis negligible. Concerning the number of erroneous time steps Nf, we confirm from Figures 4.4 and 4.5 that adding failed time steps improves the diagnostic quality for most case. The benefit of including more than 200 Nfs for Groups NCNO-01 (Figures 4.4.a and 4.4.b) and CO-01 (Figures 4.5.a and 4.5.b) is marginal on average. This number increases to 2000 Nfs for Groups NCNO-02 (Figures 4.4.c and 4.4.d) and CO-02 (Figures 4.5.c and 4.5.d). Conversely, coefficients in Groups NCNO-07 (Figures 4.4.e and 4.4.f) and CO-05 (Figures 4.5.e and 4.5.f) lose performance when including more failed time steps. This happens once these similarity coefficients are inversely proportional to c11 and c01. Concerning the number of correct time steps Np, results for each version are quite different. As for CO MASs, Npdid not influence the ESFL-MAS accuracy (see Figure 4.5). This phenomenon can be explained by the presence of coordination among agents: when agents work as team-mates in an organised manner, the MAS performs as a “well-oiled machine” and an agent that fails under these circumstances is more easily detected and therefore more easily correlated with the system failure. As for NCNO MASs, correct time steps can have effects on the diagnostic quality: (1) slightly degrade the ESFL-MAS performance for Nf<0.1% (see Figures 4.4.a and 4.4.b); (2) positively influence the ESFL-MAS results across Nfdimension (see Figures 4.4.c and 4.4.d); and (3) decrease ESFL-MAS accuracy for Nf>0.1% (see Figures 4.4.e and 4.4.f). These sparse results are consequence of the chaos2created by autonomic decisions. 2The word chaos refers to the Chaos Theory, which is the area of mathematics that studies the behaviour of dynamic systems that are highly sensitive to initial conditions. 72 4.2 Experimental Results 20 40 60 80 100 10−310−210−1100101102 10−3 10−2 10−1 100 101 102 Nf Np (a) Group 01 - 2D view. 10−2100102 10−2 100 102 20 60 100 Nf Np Quality (b) Group 01 - 3D view. 10−310−210−1100101102 10−3 10−2 10−1 100 101 102 Nf Np (c) Group 02 - 2D view. 10−2100102 10−2 100 102 20 60 100 Nf Np Quality (d) Group 02 - 3D view. 10−310−210−1100101102 10−3 10−2 10−1 100 101 102 Nf Np (e) Group 07 - 2D view. 10−2100102 10−2 100 102 20 60 100 Nf Np Quality (f) Group 07 - 3D view. Figure 4.4: Observation quantity impact of NCNO MASs. 73 4 Empirical Evaluation of Similarity Coefficients for ESFL-MAS 20 40 60 80 100 10−310−210−1100101102 10−3 10−2 10−1 100 101 102 Nf Np (a) Group 01 - 2D view. 10−2100102 10−2 100 102 20 60 100 Nf Np Quality (b) Group 01 - 3D view. 10−310−210−1100101102 10−3 10−2 10−1 100 101 102 Nf Np (c) Group 02 - 2D view. 10−2100102 10−2 100 102 20 60 100 Nf Np Quality (d) Group 02 - 3D view. 10−310−210−1100101102 10−3 10−2 10−1 100 101 102 Nf Np (e) Group 05 - 2D view. 10−2100102 10−2 100 102 20 60 100 Nf Np Quality (f) Group 05 - 3D view. Figure 4.5: Observation quantity impact of CO MASs. 74 4.2 Experimental Results 4.2.2 On the Impact of Error Detection Precision Error detection is the phase that precedes diagnosis and as such it has a great impact on the ESFL-MAS’ diagnostic quality. The following experiment shows how precision in detecting error affects diagnostic quality for each similarity coefficient. For any realistic system and practical error detection mechanism, there will very likely exist errors that go undetected, mainly because of two reasons. Firstly, the faulty agent only jeopardises system operation under specific scenario settings. For instance, let us assume that a Miner agent, erroneously, is not able to perceive gold nuggets; no error is detected unless the agent gets near a gold nugget. Secondly, analogously to faults in software, errors induced by agents might not propagate all the way to system failures and thus go undetected. As consequence of these issues, the number of rows in spectra, in which both faulty agent and system fail, will only be a fraction of the total rows in which the agent fails. More intuitively, this proportion represents the Error Detection Precision (EDP), that is, how precisely the error detection phase is able to correlate a system failure with the faulty agent. Using the previous notation, we define EDP =c11 (f) c11 (f) + c10 (f)∗100% (4.7) where fis the location of the faulty agent. By varying the EDP ratio, we are assessing the response of the ESFL-MAS diagnostic quality for different error detection mechanisms. Each faulty version of our test suite has an inherent value for EDP fluctuating from 3.31% to 97.77%. We vary EDP using two methods: (1) excluding time steps that activate the faulty agent, but for which no system error has been detected decreasing c10 (f), and increasing EDP; and (2) excluding time steps that activate the faulty agent and for each an system error has been detected decreasing c11 (f), and decreasing EDP. In order to unbias our experiment, we randomly sample passed and failed time steps from the set of available ones to control EDP within a 95% confidence interval. Yet, similarly to the experiment of observation quantity impact (Section 4.2.1), this random selection of passed and failed time steps maintained their sequence as the original spectrum to sustain consistency. These time step exclusions can be seen in practice as incomplete monitoring on agents (instrumentation blindness). The experiments serve well to demonstrate whether or not the approach is robust to such incompleteness. Figures 4.6 and 4.7 depict how the diagnostic quality changes with respect to the error detection precision for non-coordinated and coordinated versions respectively. One can see that, on average for all cases, a detection precision greater than 40% have marginal contribution to a better fault diagnosis. This does not mean that the community needs to give up improving error detection techniques; this means that, when coupled with a diagnosis phase, error detection needs a solid (but non-optimal) performance. Moreover, we confirm Group 01 as the best set of similarity coefficients for MAS also regarding EDP variation. We show that ESFL-MAS can achieve high accuracy even for low error detection precision being the borderline EDP ≥10%. 75 4 Empirical Evaluation of Similarity Coefficients for ESFL-MAS 0 20 40 60 80 0 20 40 60 80 100 EDP Quality Groups: 01 02 03 04 05 06 07 (a) NCNO MAS. 0 20 40 60 80 0 20 40 60 80 100 EDP Quality Groups: 01 02 03 04 05 06 07 (b) NCO MAS. Figure 4.6: EDP for Non-Coordinated MAS versions. 76 4.2 Experimental Results 0 20 40 60 80 0 20 40 60 80 100 EDP Quality Groups: 01 02 03 04 05 (a) CNO MAS. 0 20 40 60 80 0 20 40 60 80 100 EDP Quality Groups: 01 02 03 04 05 (b) CO MAS. Figure 4.7: EDP for Coordinated MAS versions. 77 4 Empirical Evaluation of Similarity Coefficients for ESFL-MAS 4.2.3 Discussion From observation quality impact, the Npeffect over ESFL-MAS performance degrades as agents work cooperatively in an organised fashion. Hence, our results suggest that a single faulty agent can more easily be pinpointed in a team organisation (without significant cascading errors) rather than in a selfish MAS. Additionally, adding Nfimproves the diagnostic quality until 200 time frames when its contribution starts to become marginal. Regarding the effect of the error detection precision, ESFL-MAS shows to be robust for a broad range of EDP and Groups NCNO-01, NCO-01, CNO-01, and CO-01 produced the best and more stable performance being their near-optimal response achieved when EDP ≥10%. Experiments suggest that ESFL-MAS accuracy might be jeopardised by cascading faults produced by highly interacting agents. Furthermore, our experiments determined that the best similarity coefficients for ESL-MAS, are Accuracy, Coverage, Jaccard, Laplace, Least Contradiction, Ochiai, Rogers and Tanimoto, Simple-Matching, Sorensen-Dice, and Support yield the best results in our experiment. In agreement with our findings, literature also reports the Ochiai coefficient has yielded the best diagnostic quality when SFL is applied to diagnose faults in practical domains [Hofer et al., 2015, Abreu et al., 2009, Le et al., 2013]. This suggests that Ochiai is a good candidate to be incorporated in a practical implementation of our ESFL-MAS. Several granularity levels might be considered while diagnosing faults in MASs. This initial proposal of ESFL-MAS localises agent behavioural faults aiming at its on-line usage to increase reliability in the system as a whole. Nevertheless, ESFL-MAS could be applied to a lower granularity level inside an agent, for instance, diagnosing flaws in their rules or plans. This finer granularity may help designers to better debug agents’ behaviours and improve their functioning. Without any prior practical knowledge, ESFL-MAS could be employed to this purpose as far as the instrumentation was done at the desired level. Of course that limitations would appear as the research advances, but it is important to highlight that the described technique is a solid starting point for these different abstraction levels of MASs. Threats to internal validity might come from how the empirical study was carried out. To reduce the probability of having faults in our experimental framework, it has been carefully tested. Furthermore, the random process of selecting spectrum rows are affected by chance. Thus, we repeated each described experiments and applied rigorous statistical procedures to assess results. Although we have chosen a well-known instance of PDP problem that was effectively tested during the MAPC, there are threats to external validity. The main one is the use of only one single scenario, which constrains the generalisation of the obtained results. Even though the injected faults created through mutation operators were randomly chosen and our experiments used a more faulty version that any other efforts in the literature, another threat might come from the limited type of used operators. To allow reproducibility of results, all versions and test cases will be available on a public repository. 78 4.3 Summary 4.3 Summary The performance of ESFL-MAS greatly depends on particular factors, namely: (1) similarity coefficient, (2) quantity of observations, and (3) quality of error detectors. These dependencies have been thoroughly studied by the empirical assessments, which yielded prominent results giving a good prospect for the application of ESFL-MAS. Results show that Accuracy, Coverage, Jaccard, Laplace, Least Contradiction, Ochiai, Rogers and Tanimoto, Simple-Matching, Sorensen-Dice, and Support yield the best diagnostic accuracy for the created test suite. They yield roughly 96.26% diagnostic accuracy and are stable when varying both error detection precision and quantity of observations. 79 80 Chapter 5 Conclusion Several MASs application have been deployed over the past decade in real-world scenarios. They demand for agents capable of assuring nominal behaviour in the presence of unforeseen events on a sound and safe basis. Increasing reliability of distributed, intelligent entities mainly relies on the correct diagnosis of faulty components responsible for MAS failures. Current approaches, proposed specifically to MASs, capable of these tasks like (1) formal verification techniques, (2) testing tools, and (3) fault tolerance frameworks generally assume a priori knowledge of the system that describe expected behaviour. Such an assumption may not hold while dealing with complex MASs that operated in dynamic environments with inherent legacy components, because to shape this knowledge in the form of models is a laborious and error-prone work for the designers. Thus, accuracy of fault diagnosis approaches may decrease while using incomplete and/or unreliable model of the system. In this thesis, we considered that diagnosis techniques for MASs should depend on minimal knowledge about the system to pinpoint behavioural faults of agents. Based on spectrumbased reasoning, the proposed approach, named ESFL-MAS, is able to identify agents that may jeopardise the overall performance through run-time profiles of the system with high diagnostic accuracy. In particular, we (1) studied the limitations of applying SFL to timepersistent and autonomous entities and (2) extend the spectrum-based fault localisation to support MAS features, including a filter to augment useful information within spectra. Moreover, similarity-based SFL has no standard heuristic that present optimal performance for every domain; therefore, we conducted an empirical evaluation aimed at establishing the best set of similarity coefficients for the MAS context. The built experimental setup was based on the Jason implementation for Goldminers scenario. We were able to expand our ESFL-MAS assessment by developing different strategies of both agent coordination and organisation; additionally, a broad range of fault types (from hand-seeded to mutation operators) was injected to properly represent realistic abnormal behaviours. Experiment consisted of (1) a study of how the quantity of run-time observation impacts the ESFLMAS performance, and (2) an analysis on the error detection precision so ESFL-MAS is able to sustain a high diagnostic quality. 81 5 Conclusion Exhaustive benchmarking. A wide range of systems and techniques has been proposed over the past few years. However, across the literature there are recognised problems with comparing and even experimenting the methods developed. This is due mainly to the use of different software implementations, different applications, but also because of the lack of solid metrics in many studies. As a result, many of the published approaches present a profound lack of experimental evidences that could convince designers to use them, and comparison between them is not a priority for those which have been assessed. All of this calls for a comprehensive, extensive benchmark involving (1) toy problems that evaluate conceptual boundaries of techniques, (2) complex applications of major domains in which MASs have been deployed, and (3) metrics that may be used for a fair comparison among approaches. Of course building such a benchmark is not an easy task, but there are already efforts in such a direction. For instance, the Multi-Agent Programming Contest (MAPC) is an annual competition that, since 2005, aims to provide suitable test suite offering key problems for the community to test with agent-oriented programming approaches [Behrens et al., 2010, Ahlbrecht et al., 2013]. Dealing with larger scale problems, Maffioletti et al. [2013] focus on the benchmarking of coordination in urban search and rescue scenarios. Although the benchmark does not seem at first glance a crucial component of reliable MAS, the sound, progressive, and solid implementation and deployment of such schemes will be constrained by the challenge of building exhaustive benchmark. Combining techniques. The idea of combining techniques goes back to the beginning of reliable MASs. Since then, many authors have suggested the superiority of combining mechanisms over the use of especialised ones. For instance, the replication framework DARX [Guessoum et al., 2010] has been recently combined with the exception handling framework SaGE [Dony et al., 2011] increasing fault tolerance coverage of the resulting framework. Similarly, PDT [Padgham et al., 2013] associates testing schemes from several levels and as such expands their usefulness. Despite this popularity, the combination of techniques has not been extensively discussed across the development cycle. Winikoff [2010] discusses the combination of testing and proving arguing that the strength of testing is to be able to deal with concrete implementation whereas proving can certify abstract models. We go beyond and include fault tolerance techniques as a crucial stage after the MAS deployment as it can avoid failure situations during the operation phase. Only with these three pieces working in synergy, MAS reliability is covered thoroughly during its complete life cycle. The integration of these pieces is still an open issue and a rich soil for further research. Automated validation. eCAT [Nguyen et al., 2012], PDT [Padgham et al., 2013], and SEAUnit [Çakirlar et al., 2009] frameworks have applied automation up to some extent, but the majority of simulation-based design validation efforts relies on designers to provide useful information and/or assess results of MASs. This dependence on the designer increases labor, error-proneness, and costs. A fully automated testing and validation tool would be able to monitor agents and interaction patterns, and from them formulate the expected behaviour; it would then run the system under several environmental conditions, compare results with the built behavioural model, and report the success or failure of these automatically generated tests. As we can see by the reviewed literature, there are still open challenges so full automation can be achieved for MAS testing and validation. First, the proposal of techniques that build agent behavioural model without having access to its 88 5.3 Research Trends and Challenges internal modules by monitoring perceptions, actions, and messages. Second, mechanisms that are able to detect anomalies in social interaction of agents given only the history of such interactions. Finally, the community should study new methods to measure MAS performance that are neither solely based on the overall utility nor are specific to certain applications. Prognostic framework. Adaptability and evolution are two specially appealing features of MASs. The former concerns short-term events and can be two distinctive things: the ability of an agent to learn and adapt its behaviour to a given event, or the ability of part of the system to restructure given environmental changes. The latter regards to mediumand long-term situations and have a fundamental difference from adaptation. After an unforeseen event ends, in adaptive agent/MAS, the system returns to its original state as before the event; however, if the system evolves, it can no longer come back to its previous state. A prognostic framework addresses issues, such as: (1) how discriminate anomalous behaviour from adaptation; (2) how to identify emergent behaviour and forecast its consequences in the overall performance; (3) how to guide evolution to achieve quasioptimal results, and so forth. Fortunately, some interesting research on drift adaptation in time series6might provide initial guidelines towards solving the aforementioned issues. As one can see, this is perhaps the most long-term line of research pointed out in this thesis, even though it is closely related to the previous trend. 6Readers seeking for extensive review on drift adaptation on time series can consult Gama et al. [2014] 89 90 Appendix A Marginal Research Efforts This appendix describes the marginal research efforts developed along with the main thesis theme during the Ph.D. studies. First, the project A Multi-Agent Platform to Support Ubiquitous Transportation Systems is the previous Ph.D. theme, aimed to supply ubiquitousness through agents in future urban transportation. Second, the project A Platform for the Design, Simulation and Development of Quadcopter MASs aims to provide a toolbox for designers studying autonomous vehicles from the bottom level (e.g., sensors and motors) up to higher levels (e.g., decision making processes). Further details will be given for each project in the next sections. A.1 A Multi-Agent Platform to Support Ubiquitous Transportation Systems In recent years, the population in major urban areas grew and increased in number of cars, becoming traffic chaotic in these areas. The problem of traffic congestion not only affects the day-to-day life of citizens but also has a great impact on business and economic activities. Fearing the consequences of these issues in mid and long terms, both practitioners and the scientific communities have striven to tackle congestion in such large urban networks. Much effort has been put on the design and specification of the future transport systems, putting the user in the centre of all concerns and largely oriented to services. Such efforts culminated in the emergence of the concept of Intelligent Transportation Systems, basically relying on a distributed and advanced communication infrastructure favoring interactions in virtually all levels. It suggests a completely new decentralised perspective of processes; however, discussions are still fostered by current ambitions at this new paradigm. With the emergence the role of electronic devices in people’s lives, a new concept, called Ubiquitous Computing, was firstly pointed out by Mark Weiser. It basically relied on the use of computer resources and provision of information and services to people whenever and wherever they were requested and needed. Furthermore, Ubiquitous Transportation Systems are becoming a reality because of the increasing use of computer resources to 91 A Marginal Research Efforts supply continuous connectivity to such a domain. Multi-Agent Systems have been proving to be an important ingredient to support ubiquitousness, favouring mobility, information acquisition and sharing, awareness and cooperation. The main reason is their ability to provide autonomous decisions and high-level interactions between entities. These three concepts, despite being potentially complementary, have not as yet been dealt with on an integrated basis. Indeed, a diverse range of different applications and for varying purposes have already been reported in the literature, coupling the two of them and opening up a challenging and promising novel field of research. This work proposes the extinction of the barrier between demand and supply in transportation systems, as suggested by researchers in the field. To achieve this ubiquitous computing and other related concepts can be applied to merge the supply and demand, providing support the effective implementation of future transportation systems requirements. Concretely speaking, the work aims to specify, devise and implement a framework featuring the necessary mechanisms underlying the full characteristics of ubiquitous transportation systems, which are presented as a natural perspective of today’s intelligent transportation technologies supported by major multi-agent systems features. This project generated many research outcomes that are listed below: 1. L. S. Passos, R. J. F. Rossetti, J. Gabriel, An Agent Methodology for Processes, the Environment, and Services. In Advances in Artificial Transportation Systems and Simulation, pages 37-53, Rosaldo J. F. Rossetti and Ronghui Liu (eds.) Academic Press, Boston. 2015. [Passos et al., 2015b]. 2. L. S. Passos, Z. Kokkinogenis, R. J. F. Rossetti, J. Gabriel, Multi-Resolution Simulation of Taxi Services on Airport Terminal’s Curbside. In Proceedings of the 15th IEEE International Conference on Intelligent Transportation Systems (IEEE ITSC 2013), The Hague, The Netherlands, October. 2013. [Passos et al., 2013a]. 3. Z. Kokkinogenis, L. S. Passos, R. J. F. Rossetti, J. Gabriel, Towards the nextgeneration traffic simulation tools: a first evaluation. In Proceedings of the 6th Doctoral Symposium in Informatics Engineering (DSIE 2011), Porto, Portugal, January 27-28. 2011. [Kokkinogenis et al., 2011]. 4. L. S. Passos, Z. Kokkinogenis, R. J. F. Rossetti, Towards the next-generation traffic simulation tools: a first appraisal. In Proceedings of the 3th Workshop on Intelligent Systems and Applications (WISA 2011), collocated with the 5th Iberian Conference on Information Systems and Technologies (CISTI 2011), Chaves, Portugal, June 1518. 2011. [Passos et al., 2011a]. 5. L. S. Passos, R. J. F. Rossetti, L. P. Reis, Evaluation of taxi services on airport terminal’s curbside for picking up passengers. In Proceedings of the 3th Workshop on Intelligent Systems and Applications (WISA 2011), collocated with the 5th Iberian Conference on Information Systems and Technologies (CISTI 2011), Chaves, Portugal, June 15-18. 2011. [Passos et al., 2011b]. 92 A.2 A Platform for the Development of Quadcopter MASs 6. L. S. Passos, R. J. F. Rossetti, Traffic Light Control using Reactive Agents. In Proceedings of the 2nd Workshop on Intelligent Systems and Applications (WISA 2010), collocated with the 5th Iberian Conference on Information Systems and Technologies (CISTI 2010), Santiago de Compostela, Spain, June 16-19. 2010. [Passos and Rossetti, 2010a]. 7. L. S. Passos, R. J. F. Rossetti, E. Oliveira, Ambient-Centred Intelligent Traffic Control and Management. In Proceedings of the 13th IEEE International Conference on Intelligent Transportation Systems (IEEE ITSC 2010), Madeira Island, Portugal, September 19-22. 2010. [Passos et al., 2010]. 8. L. S. Passos, Evaluating Agent-based Methodologies with Focus on Transportation Systems. In Proceedings of the 5th Doctoral Symposium in Informatics Engineering (DSIE 2010), Porto, Portugal, January 28-29. 2010. [Passos, 2010]. 9. L. S. Passos, R. J. F. Rossetti, Intelligent Transportation Systems: a Ubiquitous Perspective. In New Trends in Artificial Intelligence collocated in the Proceedings of the 14th Portuguese Conference on Artificial Intelligence (EPIA), Aveiro, Portugal. 2009. [Passos and Rossetti, 2009]. A.2 A Platform for the Development of Quadcopter MASs Unmanned Aerial Vehicles gained notoriety in the past decade due to their successful endeavours in warfare. Since then, many civil applications appeared aiming to use this technology to substitute the human operators in hazardous situations. Indeed, the research directions in their development nowadays seek to consolidate three interesting features: a higher-level decision-making process, autonomy in taking actions, and coordination of efforts towards a common goal in the case of applications with multiple units. Such vehicles in general (and specially because of the aforementioned features) demand proper simulation tools in order to avoid damage to expensive equipment and misuse of means that could be employed to improve their development life-cycle. Our research focuses on the coordinated usage of quadcopters in both indoor and outdoor environments; an illustrative scenario would be a group of quadcopters helping to map the internal blueprint of a building when it is dangerous for people to go inside. This type of aerial vehicle suits indoor applications due to its manoeuvrability (i.e. it changes direction and altitude faster than aeroplanes), as well as it easily stabilizes compared to other types of Unmanned Aerial Vehicles. On the other hand, quadcopters usually struggles with their flying time as designers have to optimize flying weight versus battery life. From the simulation perspective, all the aforementioned aspects must be present in the virtual domain so quadcopters’ planning, learning, and other features might be put under test accounting for realistic conditions. A question emerges upon these considerations: which approach does fulfil the requirements for a collaborative quadcopters simulation tool for real indoor and outdoor applications? We believe that the answer may lie within the symbiotic simulation paradigm. Such per93 A Marginal Research Efforts Figure A.1: The proposed framework for Quadcopter MASs. spective considers a close association between a virtual (simulation) system and a physical system as well as the mutual benefits can emerge from this synergy. We explore the various classes of symbiotic simulation systems with the purposes of (1) controlling the real quadcopter, (2) supporting an external cognitive decision maker, (3) training the quadcopter in different environments, (4) validating the virtual model and strategies, and (5) detecting anomalies in both virtual and physical systems. This work proposes an architecture to support symbiotic simulation of quadcopters aiming to assess techniques from low-level control to coordination and cooperation strategies (Figure A.1). That is, a platform for the design, simulation, and development of quadcopter Multi-Agent Systems. We study the requirements of our quadcopter context from the perspective of symbiotic simulation and thus illustrate some scenarios to base the proposed architecture. A main contribution of this work is to describe all components in our abstract architecture and how the chosen technologies play their roles in each component; also we show some preliminary results that demonstrate all distinct technologies are able to interact in a cohesive manner. This project generated some research outcomes that are listed below: 1. R. Veloso, G. Oliveira, Z. Kokkinogenis, L. S. Passos, R. J. F. Rossetti, J. Gabriel, A Symbiotic Simulation Platform for Agent-based Quadcopters. In Proceedings of the 9th Iberian Conference on Information Systems and Technologies (CISTI 2014), 94 A.2 A Platform for the Development of Quadcopter MASs Barcelona, Spain, June 18-21. 2014. [Veloso et al., 2014b]. 2. R. Veloso, Z. Kokkinogenis, L. S. Passos, G. Oliveira, R. J. F. Rossetti, J. Gabriel, A Platform for the Design, Simulation and Development of Quadcopter Multi-Agent Systems. In: Proceedings of the 9th Iberian Conference on Information Systems and Technologies (CISTI 2014), Barcelona, Spain, June 18-21. 2014. [Veloso et al., 2014a]. 95 96 References [Aamodt and Plaza, 1994] Aamodt, A. and Plaza, E. (1994). Case-based reasoning: Foundational issues, methodological variations, and system approaches. AI Commun., 7(1):39–59. (Cited on page 87.) [Abreu and Van Gemund, 2010] Abreu, R. and Van Gemund, A. J. (2010). Diagnosing multiple intermittent failures using maximum likelihood estimation. Artificial Intelligence, 174(18):1481–1497. (Cited on page 55.) [Abreu et al., 2009] Abreu, R., Zoeteweij, P., Golsteijn, R., and van Gemund, A. J. (2009). A practical evaluation of spectrum-based fault localization. Journal of Systems and Software (JSS), 82(11):1780 – 1792. SI: TAIC PART 2007 and MUTATION 2007. (Cited on pages 5, 39, 49, 78, 82 and 87.) [Agatz et al., 2012] Agatz, N., Erera, A., Savelsbergh, M., and Wang, X. (2012). Optimization for dynamic ride-sharing: A review. European Journal of Operational Research, 223(2):295 – 303. (Cited on pages 60 and 63.) [Agogino and Tumer, 2012] Agogino, A. and Tumer, K. (2012). A multiagent approach to managing air traffic flow. Autonomous Agents and Multi-Agent Systems, 24(1):1–25. (Cited on page 1.) [Ahlbrecht et al., 2013] Ahlbrecht, T., Dix, J., Köster, M., and Schlesinger, F. (2013). Multi-agent programming contest 2013. In Cossentino, M., El Fallah Seghrouchni, A., and Winikoff, M., editors, Engineering Multi-Agent Systems, volume 8245 of Lecture Notes in Computer Science, pages 292–318. Springer-Verlag. (Cited on page 88.) [Almeida et al., 2008] Almeida, A. d. L., Aknine, S., and Briot, J.-P. (2008). Dynamic resource allocation heuristics for providing fault tolerance in multi-agent systems. In Proceedings of the 2008 ACM symposium on Applied computing, SAC ’08, pages 66–70, New York, NY, USA. ACM. (Cited on page 27.) 97 References [Grunow et al., 2005] Grunow, M., Günther, H.-O., and Lehmann, M. (2005). Dispatching multi-load agvs in highly automated seaport container terminals. In Günther, H.- O. and Kim, K., editors, Container Terminals and Automated Transport Systems, pages 231–255. Springer-Verlag. (Cited on pages 60 and 63.) [Guessoum and Briot, 1999] Guessoum, Z. and Briot, J.-P. (1999). From active objects to autonomous agents. IEEE Concurrency, 7(3):68–76. (Cited on page 27.) [Guessoum et al., 2010] Guessoum, Z., Briot, J.-P., Faci, N., and Marin, O. (2010). Towards reliable multi-agent systems: An adaptive replication mechanism. Multiagent Grid Syst., 6(1):1–24. (Cited on pages 27, 29, 30, 32, 35, 36, 37 and 88.) [Guessoum et al., 2003] Guessoum, Z., Briot, J.-P., Marin, O., Hamel, A., and Sens, P. (2003). Dynamic and adaptive replication for large-scale reliable multi-agent systems. In Garcia, A., Lucena, C., Zambonelli, F., Omicini, A., and Castro, J., editors, Software engineering for large-scale multi-agent systems, pages 182–198. Springer-Verlag, Berlin, Heidelberg. (Cited on page 27.) [Gupta et al., 2014] Gupta, S., Abreu, R., de Kleer, J., and van Gemund, A. (2014). Automatic systems diagnosis without behavioral models. In Aerospace Conference, 2014 IEEE, pages 1–8. (Cited on page 5.) [Gürcan et al., 2011] Gürcan, O., Dikenelli, O., and Bernon, C. (2011). Towards a generic testing framework for agent-based simulation models. In Computer Science and Information Systems (FedCSIS), 2011 Federated Conference on, pages 635–642. (Cited on page 22.) [Gürcan et al., 2013] Gürcan, Ö., Dikenelli, O., and Bernon, C. (2013). A generic testing framework for abms models. J. Simulation, 7(3):183–201. (Cited on page 22.) [Hägg, 1997] Hägg, S. (1997). A sentinel approach to fault handling in multi-agent systems. In Zhang, C. and Lukose, D., editors, Multi-Agent Systems Methodologies and Applications, volume 1286 of Lecture Notes in Computer Science, pages 181–195. Springer-Verlag. (Cited on pages 25, 30, 32, 35 and 37.) [Hailpern and Santhanam, 2002] Hailpern, B. and Santhanam, P. (2002). Software debugging, testing, and verification. IBM Systems Journal, 41(1):4–12. (Cited on page 3.) [Harrold et al., 2000] Harrold, M. J., Rothermel, G., Sayre, K., Wu, R., and Yi, L. (2000). An empirical investigation of the relationship between spectra differences and regression faults. Software Testing, Verification and Reliability, 10(3):171–194. (Cited on page 5.) [Harrold et al., 1998] Harrold, M. J., Rothermel, G., Wu, R., and Yi, L. (1998). An empirical investigation of program spectra. In Proceedings of the 1998 ACM SIGPLANSIGSOFT Workshop on Program Analysis for Software Tools and Engineering, PASTE ’98, pages 83–90, New York, NY, USA. ACM. (Cited on pages 41 and 49.) 104 References [Heshmati et al., 2016] Heshmati, S., Kokkinogenis, Z., Rossetti, R., Carravilla, M., and Oliveira, J. (2016). An agent-based approach to schedule crane operations in rail-rail transshipment terminals. In Fonseca, R. J., Weber, G.-W., and Telhada, J., editors, Computational Management Science, volume 682 of Lecture Notes in Economics and Mathematical Systems, pages 91–97. Springer International Publishing. (Cited on page 86.) [Hofer et al., 2015] Hofer, B., Perez, A., Abreu, R., and Wotawa, F. (2015). On the empirical evaluation of similarity coefficients for spreadsheets fault localization. Automated Software Engineering, 22(1):47–74. (Cited on pages 5, 7, 59, 66, 78, 82 and 83.) [Hofer et al., 2013] Hofer, B., Riboira, A., Wotawa, F., Abreu, R., and Getzner, E. (2013). On the empirical evaluation of fault localization techniques for spreadsheets. In Cortellessa, V. and Varró, D., editors, Fundamental Approaches to Software Engineering, volume 7793 of Lecture Notes in Computer Science, pages 68–82. SpringerVerlag. (Cited on page 39.) [Horling et al., 2001] Horling, B., Benyo, B., and Lesser, V. (2001). Using self-diagnosis to adapt organizational structures. Proceedings of the 5th International Conference on Autonomous Agents, pages 529–536. (Cited on page 4.) [Horling and Lesser, 2004] Horling, B. and Lesser, V. (2004). A survey of multi-agent organizational paradigms. Knowl. Eng. Rev., 19(4):281–316. (Cited on pages 31 and 61.) [Horling et al., 2000] Horling, B., Lesser, V., Vincent, R., Bazzan, A., and Xuan, P. (2000). Diagnosis as an integral part of multi-agent adaptability. In DARPA Information Survivability Conference and Exposition, 2000. DISCEX ’00. Proceedings, volume 2, pages 211 –219 vol.2. (Cited on pages 23, 30, 32, 34, 35 and 37.) [Huang et al., 2014] Huang, Z., Alexander, R., and Clark, J. (2014). Mutation testing for jason agents. In Dalpiaz, F., Dix, J., and van Riemsdijk, M., editors, Engineering Multi-Agent Systems, volume 8758 of Lecture Notes in Computer Science, pages 309–327. Springer-Verlag. (Cited on page 63.) [Huberman and Hogg, 1996] Huberman, B. A. and Hogg, T. (1996). Communities of practice: performance and evolution. Computational and Mathmatical Organization Theory, 1(1):73–92. (Cited on page 14.) [Hubner and Sichman, 2003] Hubner, J. F. and Sichman, J. S. (2003). SACI Programming Guide. University of São Paulo. (Cited on page 87.) [Isern et al., 2010] Isern, D., Sánchez, D., and Moreno, A. (2010). Agents applied in health care: A review. International Journal of Medical Informatics, 79(3):145 – 166. (Cited on page 1.) [Isong and Bekele, 2013] Isong, B. E. and Bekele, E. (2013). A systematic review of fault tolerance in mobile agents. American Journal of Software Engineering and Applications, 2(5):111–124. (Cited on page 12.) 105 References [Issicaba et al., 2012] Issicaba, D., Rosa, M. A., Franchin, W., and Lopes, J. A. P. (2012). Practical applications of agent-based technology. chapter Agent-Based System Applied to Smart Distribution Grid Operation, pages 1–20. InTech. (Cited on page 86.) [Iyer et al., 1997] Iyer, R. K., Kalbarczyk, Z. T., and Bagchi, S. (1997). Chameleon: adaptive fault tolerance using reliable, mobile agents. In Reliable Distributed Systems, 1997. Proceedings., The Sixteenth Symposium on, pages 61 –62. (Cited on page 26.) [Jennings and Wooldridge, 1995] Jennings, N. R. and Wooldridge, M. J. (1995). Applying agent technology. International Journal of Applied Artificial Intelligence, 9(4):351– 369. (Cited on page 11.) [Jonge et al., 2009] Jonge, F., Roos, N., and Witteveen, C. (2009). Primary and secondary diagnosis of multi-agent plan execution. Autonomous Agents and Multi-Agent Systems, 18(2):267–294. (Cited on pages 4 and 24.) [Kalbarczyk et al., 1999] Kalbarczyk, Z. T., Iyer, R. K., Bagchi, S., and Whisnant, K. (1999). Chameleon: a software infrastructure for adaptive fault tolerance. Parallel and Distributed Systems, IEEE Transactions on, 10(6):560 –579. (Cited on page 26.) [Kalbarczyk et al., 2005] Kalbarczyk, Z. T., Iyer, R. K., and Wang, L. (2005). Application fault tolerance with armor middleware. Internet Computing, IEEE, 9(2):28–37. (Cited on pages 26, 29, 30, 32, 35, 36 and 37.) [Kalech, 2012] Kalech, M. (2012). Diagnosis of coordination failures: a matrix-based approach. Autonomous Agents and Multi-Agent Systems, 24(1):69–103. (Cited on pages 4, 23, 30, 32, 35, 37 and 87.) [Kalech and Kaminka, 2007] Kalech, M. and Kaminka, G. A. (2007). On the design of coordination diagnosis algorithms for teams of situated agents. Artificial Intelligence, 171:491 – 513. (Cited on pages 4 and 23.) [Kalech and Kaminka, 2011] Kalech, M. and Kaminka, G. A. (2011). Coordination diagnostic algorithms for teams of situated agents: Scaling up. Computational Intelligence, 27(3):393–421. (Cited on pages 23, 51 and 57.) [Kalech et al., 2007] Kalech, M., Lindner, M., and Kaminka, G. A. (2007). Matrix-based representation for coordination fault detection: a formal approach. In Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, AAMAS ’07, pages 162:1–162:8, New York, NY, USA. ACM. (Cited on pages 4 and 23.) [Kaminka et al., 2002] Kaminka, G. A., Pynadath, D. V., and Tambe, M. (2002). Monitoring teams by overhearing: a multi-agent plan-recognition approach. J. Artif. Int. Res., 17:83–135. (Cited on pages 4, 23, 30, 32, 35 and 37.) [Kaminka and Tambe, 1998] Kaminka, G. A. and Tambe, M. (1998). What is wrong with us? improving robustness through social diagnosis. pages 97–104, Madison, WI, USA. AAAI. (Cited on pages 4, 23 and 33.) 106 References [Kaminka and Tambe, 2000] Kaminka, G. A. and Tambe, M. (2000). Robust agent teams via socially-attentive monitoring. J. Artif. Int. Res., 12:105–147. (Cited on pages 4 and 23.) [Keil et al., 1995] Keil, M., Beranek, P. M., and Konsynski, B. R. (1995). Usefulness and ease of use: field study evidence regarding task considerations. Decision Support Systems, 13(1):75 – 91. User interfaces. (Cited on page 28.) [Khalastchi et al., 2015] Khalastchi, E., Kalech, M., Kaminka, G., and Lin, R. (2015). Online data-driven anomaly detection in autonomous robots. Knowledge and Information Systems, 43(3):657–688. (Cited on pages 51 and 85.) [Klein and Dellarocas, 1999] Klein, M. and Dellarocas, C. (1999). Exception handling in agent systems. In Proceedings of the third annual conference on Autonomous Agents, AGENTS ’99, pages 62–68, New York, NY, USA. ACM. (Cited on pages 25 and 26.) [Klein et al., 2003] Klein, M., Rodriguez-Aguilar, J.-A., and Dellarocas, C. (2003). Using domain-independent exception handling services to enable robust open multi-agent systems: The case of agent death. Autonomous Agents and Multi-Agent Systems, 7:179–189. (Cited on pages 14, 26, 30, 32, 35, 37 and 48.) [Knublauch, 2002] Knublauch, H. (2002). Extreme programming of multi-agent systems. In Proceedings of the First International Joint Conference on Autonomous Agents and Multiagent Systems: Part 2, AAMAS ’02, pages 704–711, New York, NY, USA. ACM. (Cited on pages 17, 30, 31, 32, 35 and 37.) [Koca et al., 2013] Koca, F., Sozer, H., and Abreu, R. (2013). Spectrum-based fault localization for diagnosing concurrency faults. In Yenigun, H., Yilmaz, C., and Ulrich, A., editors, Testing Software and Systems, volume 8254 of Lecture Notes in Computer Science, pages 239–254. Springer-Verlag. (Cited on pages 5 and 82.) [Koestler, 1967] Koestler, A. (1967). The Ghost in the Machine. Arkana Publishing, 1st edition. (Cited on page 13.) [Kokkinogenis et al., 2011] Kokkinogenis, Z., Passos, L. S., Rossetti, R. J. F., and Gabriel, J. (2011). Towards the next-generation traffic simulation tools: a first evaluation. In Proceedings of the 6th Doctoral Symposium in Informatics Engineering (DSIE 2011). (Cited on page 92.) [Kolodner, 1992] Kolodner, J. L. (1992). An introduction to case-based reasoning. Artificial Intelligence Review, 6(1):3–34. (Cited on page 87.) [Kumar and Cohen, 2000] Kumar, S. and Cohen, P. R. (2000). Towards a fault-tolerant multi-agent system architecture. In Proceedings of the fourth international conference on Autonomous agents, AGENTS ’00, pages 459–466, New York, NY, USA. ACM. (Cited on page 26.) 107 References [Kumar et al., 2000] Kumar, S., Cohen, P. R., and Levesque, H. J. (2000). The adaptive agent architecture: Achieving fault-tolerance using persistent broker teams. In Proceedings of the Fourth International Conference on MultiAgent Systems (ICMAS2000), pages 159–, Washington, DC, USA. IEEE Computer Society. (Cited on pages 26, 30, 32, 35 and 37.) [Lam and Barber, 2004] Lam, D. N. and Barber, K. S. (2004). Verifying and explaining agent behavior in an implemented agent system. In Autonomous Agents and Multiagent Systems, 2004. AAMAS 2004. Proceedings of the Third International Joint Conference on, pages 1226–1227. (Cited on page 18.) [Lam and Barber, 2005a] Lam, D. N. and Barber, K. S. (2005a). Comprehending agent software. In Proceedings of the Fourth International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS ’05, pages 586–593, New York, NY, USA. ACM. (Cited on pages 5, 18, 30, 32, 35 and 37.) [Lam and Barber, 2005b] Lam, D. N. and Barber, K. S. (2005b). Debugging agent behavior in an implemented agent system. In Bordini, R. H., Dastani, M., Dix, J., and El Fallah Seghrouchni, A., editors, Programming Multi-Agent Systems, volume 3346 of Lecture Notes in Computer Science, pages 104–125. Springer-Verlag. (Cited on pages 5 and 18.) [Laprie et al., 1992] Laprie, J.-C., Avižienis, A., and Kopetz, H., editors (1992). Dependability: Basic Concepts and Terminology - In English, French,German, Italian and Japanese. Springer-Verlag, Secaucus, NJ, USA. (Cited on page 13.) [Le et al., 2013] Le, T.-D. B., Thung, F., and Lo, D. (2013). Theory and practice, do they match? a case with spectrum-based fault localization. In Software Maintenance (ICSM), 2013 29th IEEE International Conference on, pages 380–383. (Cited on pages 5, 7, 39, 59, 78, 82 and 83.) [Lee and Anderson, 1990] Lee, P. A. and Anderson, T. (1990). Fault Tolerance: Principles and Practice. Springer-Verlag, Secaucus, NJ, USA, 2nd edition. (Cited on pages 13 and 22.) [Leitão et al., 2012] Leitão, P., Mařík, V., and Vrba, P. (2012). Past, present, and future of industrial agent applications. Industrial Informatics, IEEE Transactions on, PP(99):1–1. (Cited on pages 1, 13 and 63.) [Leitão and Vrba, 2011] Leitão, P. and Vrba, P. (2011). Recent developments and future trends of industrial agents. In Mařík, V., Vrba, P., and Leitão, P., editors, Holonic and Multi-Agent Systems for Manufacturing, volume 6867 of Lecture Notes in Computer Science, pages 15–28. Springer-Verlag. (Cited on page 1.) [Lettmann et al., 2011] Lettmann, T., Baumann, M., Eberling, M., and Kemmerich, T. (2011). Modeling agents and agent systems. In Nguyen, N. T., editor, Transactions on Computational Collective Intelligence V, volume 6910 of Lecture Notes in Computer Science, pages 157–181. Springer-Verlag. (Cited on page 45.) 108 References [Liskov and Snyder, 1979] Liskov, B. H. and Snyder, A. (1979). Exception handling in clu. IEEE Transactions on Software Engineering, 5(6):546–558. (Cited on page 13.) [Lomuscio and Michaliszyn, 2014] Lomuscio, A. and Michaliszyn, J. (2014). Decidability of model checking multi-agent systems against some ehs specifications. In Proceedings of the 21st European Conference on Artificial Intelligence (ECAI14), pages 543–548, Prague, Czech Republic. IOS Press. (Cited on page 4.) [Lomuscio and Michaliszyn, 2015] Lomuscio, A. and Michaliszyn, J. (2015). Verifying multi-agent systems by model checking three-valued abstractions. In Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2015), AAMAS ’15, Istanbul, Turkey. IFAAMAS Press. (Cited on page 4.) [Lomuscio and Paquet, 2015] Lomuscio, A. and Paquet, H. (2015). Verification of multiagent systems via sdd-based model checking (extended abstract). In Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2015), AAMAS ’15, pages 1713–1714, Istanbul, Turkey. IFAAMAS Press. (Cited on page 4.) [Lomuscio et al., 2009] Lomuscio, A., Qu, H., and Raimondi, F. (2009). Mcmas: A model checker for the verification of multi-agent systems. In Bouajjani, A. and Maler, O., editors, Computer Aided Verification, volume 5643 of Lecture Notes in Computer Science, pages 682–688. Springer-Verlag. (Cited on page 4.) [Lucas, 1998] Lucas, P. J. (1998). Analysis of notions of diagnosis. Artificial Intelligence, 105:295 – 343. (Cited on page 3.) [Lucia et al., 2014] Lucia, Lo, D., Jiang, L., Thung, F., and Budi, A. (2014). Extended comprehensive study of association measures for fault localization. Journal of Software: Evolution and Process, 26(2):172–219. (Cited on page 66.) [Maffioletti et al., 2013] Maffioletti, F., Reffato, R., Farinelli, A., Kleiner, A., Ramchurn, S., and Shi, B. (2013). Rmasbench: A benchmarking system for multi-agent coordination in urban search and rescue. In Proceedings of the 2013 International Conference on Autonomous Agents and Multi-agent Systems, AAMAS ’13, pages 1383–1384, Richland, SC. International Foundation for Autonomous Agents and Multiagent Systems. (Cited on page 88.) [Mallya and Singh, 2005a] Mallya, A. and Singh, M. (2005a). A semantic approach for designing commitment protocols. In van Eijk, R., Huget, M.-P., and Dignum, F., editors, Agent Communication, volume 3396 of Lecture Notes in Computer Science, pages 33–49. Springer-Verlag. (Cited on pages 25, 30, 32, 34, 35 and 37.) [Mallya and Singh, 2005b] Mallya, A. U. and Singh, M. P. (2005b). Modeling exceptions via commitment protocols. In Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, AAMAS ’05, pages 122–129, New York, NY, USA. ACM. (Cited on pages 15 and 25.) 109 References [Manvi and Venkataram, 2004] Manvi, S. and Venkataram, P. (2004). Applications of agent technology in communications: a review. Computer Communications, 27(15):1493 – 1508. (Cited on page 1.) [Marin et al., 2007] Marin, O., Bertier, M., Sens, P., Guessoum, Z., and Briot, J.-P. (2007). Darx - a self-healing framework for agents. In Kordon, F. and Sztipanovits, J., editors, Reliable Systems on Unreliable Networked Platforms, volume 4322 of Lecture Notes in Computer Science, pages 88–105. Springer-Verlag. (Cited on page 27.) [Mayer and Stumptner, 2007] Mayer, W. and Stumptner, M. (2007). Model-based debugging - state of the art and future challenges. Electronic Notes in Theoretical Computer Science, 174(4):61–82. Proceedings of the Workshop on Verification and Debugging (V&D 2006). (Cited on page 5.) [Mcburney and Omicini, 2008] Mcburney, P. and Omicini, A. (2008). Editorial: Special issue on foundations, advanced topics and industrial perspectives of multi-agent systems. Autonomous Agents and Multi-Agent Systems, 17:367–371. (Cited on page 2.) [McQuitty, 1966] McQuitty, L. L. (1966). Similarity analysis by reciprocal pairs for discrete and continuous data. Educational and Psychological Measurement, 26(4):825–831. (Cited on page 69.) [Mellouli et al., 2004] Mellouli, S., Moulin, B., and Mineau, G. (2004). Laying down the foundations of an agent modelling methodology for fault-tolerant multi-agent systems. In Omicini, A., Petta, P., and Pitt, J., editors, Engineering Societies in the Agents World IV, volume 3071 of Lecture Notes in Computer Science, pages 519–519. Springer-Verlag. (Cited on page 15.) [Micalizio, 2009] Micalizio, R. (2009). A distributed control loop for autonomous recovery in a multi-agent plan. In Proceedings of the 21st international jont conference on Artifical intelligence, IJCAI’09, pages 1760–1765, San Francisco, CA, USA. Morgan Kaufmann Publishers Inc. (Cited on pages 4 and 24.) [Micalizio, 2013] Micalizio, R. (2013). Action failure recovery via model-based diagnosis and conformant planning. Computational Intelligence, 29(2):233–280. (Cited on pages 4, 24 and 87.) [Micalizio and Torasso, 2014] Micalizio, R. and Torasso, P. (2014). Cooperative monitoring to diagnose multiagent plans. Journal of Artificial Intelligence Research, 51(1):1–70. (Cited on pages 24, 30, 32, 35 and 37.) [Michel et al., 2009] Michel, F., Ferber, J., and Drogoul, A. (2009). Multi-agent systems and simulation: a survey from the agents community’s perspective. In Danny Weyns, A. U., editor, Multi-Agent Systems: Simulation and Applications, Computational Analysis, Synthesis, and Design of Dynamic Systems, page 47. CRC Press - Taylor & Francis. (Cited on pages 12 and 20.) 110 References [Miller and Tripathi, 2004] Miller, R. and Tripathi, A. (2004). The guardian model and primitives for exception handling in distributed systems. Software Engineering, IEEE Transactions on, 30(12):1008 – 1022. (Cited on pages 4, 26, 30, 32, 35 and 37.) [Mishra, 2001] Mishra, S. (2001). Agent fault tolerance using group communication. In Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, Las Vegas, Nevada, USA. CSREA Publishing. (Cited on page 26.) [Mishra and Huang, 2000] Mishra, S. and Huang, Y. (2000). Fault tolerance in agent-based computing systems. In In Proceedings of the 13th ISCA International Conference on Parallel and Distributed Computing Systems, Las Vegas, NV, USA. (Cited on page 26.) [Mishra and Xie, 2003] Mishra, S. and Xie, P. (2003). Interagent communication and synchronization support in the daagent mobile agent-based computing system. IEEE Trans. Parallel Distrib. Syst., 14(3):290–306. (Cited on pages 26, 30, 32, 35 and 37.) [Moreno et al., 2009] Moreno, M., Pavón, J., and Rosete, A. (2009). Testing in agent oriented methodologies. In Omatu, S., Rocha, M. P., Bravo, J., Fernández, F., Corchado, E., Bustillo, A., and Corchado, J. M., editors, Distributed Computing, Artificial Intelligence, Bioinformatics, Soft Computing, and Ambient Assisted Living, volume 5518 of Lecture Notes in Computer Science, pages 138–145. Springer-Verlag. (Cited on page 16.) [Nguyen et al., 2012] Nguyen, C. D., Miles, S., Perini, A., Tonella, P., Harman, M., and Luck, M. (2012). Evolutionary testing of autonomous software agents. Autonomous Agents and Multi-Agent Systems, 25(2):260–283. (Cited on pages 4, 7, 20, 30, 31, 32, 35, 36, 37 and 88.) [Nguyen et al., 2011] Nguyen, C. D., Perini, A., Bernon, C., Pavón, J., and Thangarajah, J. (2011). Testing in multi-agent systems. In Gleizes, M.-P. and Gomez-Sanz, J., editors, Agent-Oriented Software Engineering X, volume 6038 of Lecture Notes in Computer Science, pages 180–190. Springer-Verlag. (Cited on pages 12, 28 and 39.) [Nguyen et al., 2008] Nguyen, C. D., Perini, A., and Tonella, P. (2008). ecat: A tool for automating test cases generation and execution in testing multi-agent systems (demo paper). In Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems: Demo Papers, AAMAS ’08, pages 1669–1670, Richland, SC. International Foundation for Autonomous Agents and Multiagent Systems. (Cited on page 20.) [Nguyen et al., 2009] Nguyen, C. D., Perini, A., and Tonella, P. (2009). Experimental evaluation of ontology-based test generation for multi-agent systems. In Luck, M. and Gomez-Sanz, J. J., editors, Agent-Oriented Software Engineering IX, volume 5386 of Lecture Notes in Computer Science, pages 187–198. Springer-Verlag. (Cited on page 20.) 111 References [Nguyen et al., 2010] Nguyen, C. D., Perini, A., and Tonella, P. (2010). Goal-oriented testing for mass. Int. J. Agent-Oriented Softw. Eng., 4(1):79–109. (Cited on page 20.) [Núñez et al., 2005] Núñez, M., Rodríguez, I., and Rubio, F. (2005). Specification and testing of autonomous agents in e-commerce systems: Research articles. Softw. Test. Verif. Reliab., 15(4):211–233. (Cited on page 18.) [Padgham et al., 2007] Padgham, L., Thangarajah, J., and Winikoff, M. (2007). Auml protocols and code generation in the prometheus design tool. In Proceedings of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS ’07, pages 270:1–270:2, New York, NY, USA. ACM. (Cited on page 20.) [Padgham and Winikoff, 2004] Padgham, L. and Winikoff, M. (2004). Developing Intelligent Agent Systems: A Practical Guide. John Wiley & Sons, Inc., New York, NY, USA. (Cited on page 20.) [Padgham et al., 2005] Padgham, L., Winikoff, M., and Poutakidis, D. (2005). Adding debugging support to the prometheus methodology. Engineering Applications of Artificial Intelligence, 18(2):173 – 190. Agent-oriented Software Development. (Cited on page 20.) [Padgham et al., 2013] Padgham, L., Zhang, Z., Thangarajah, J., and Miller, T. (2013). Model-based test oracle generation for automated unit testing of agent systems. Software Engineering, IEEE Transactions on, 39(9):1230–1244. (Cited on pages 20, 30, 31, 32, 35, 37 and 88.) [Pardo et al., 2010] Pardo, J. J., Núñez, M., and Ruiz, M. C. (2010). Specification and testing of e-commerce agents described by using uioltss. In Hatcliff, J. and Zucca, E., editors, Formal Techniques for Distributed Systems, volume 6117 of Lecture Notes in Computer Science, pages 78–86. Springer-Verlag. (Cited on pages 18, 30, 32, 35 and 37.) [Parsons and Wooldridge, 2002] Parsons, S. and Wooldridge, M. (2002). Game theory and decision theory in multi-agent systems. Autonomous Agents and Multi-Agent Systems, 5(3):243–254. (Cited on page 1.) [Parunak, 1996] Parunak, H. V. D. (1996). Applications of distributed artificial intelligence in industry, pages 139–164. John Wiley & Sons, Inc., New York, NY, USA. (Cited on pages 1 and 11.) [Parunak, 2000] Parunak, H. V. D. (2000). A practitioners’ review of industrial agent applications. Autonomous Agents and Multi-Agent Systems, 3(4):389–407. (Cited on page 1.) [Passos, 2010] Passos, L. (2010). Evaluating agent-based methodologies with focus on transportation systems. In Proceedings of the 5th Doctoral Symposium in Informatics Engineering (DSIE 2010). (Cited on page 93.) 112 References [Passos et al., 2013a] Passos, L., Kokkinogenis, Z., Rossetti, R., and Gabriel, J. (2013a). Multi-resolution simulation of taxi services on airport terminal’s curbside. In Intelligent Transportation Systems - (ITSC), 2013 16th International IEEE Conference on, pages 2361–2366. (Cited on page 92.) [Passos et al., 2011a] Passos, L., Kokkinogenis, Z., and Rossetti, R. J. F. (2011a). Towards the next-generation traffic simulation tools: a first appraisal. In Proceedings of the 3th Workshop on Intelligent Systems and Applications (WISA 2011), collocated with the 5th Iberian Conference on Information Systems and Technologies (CISTI 2011). (Cited on page 92.) [Passos and Rossetti, 2009] Passos, L. and Rossetti, R. J. F. (2009). Intelligent transportation systems: a ubiquitous perspective. In New Trends in Artificial Intelligence collocated in the Proceedings of the 14th Portuguese Conference on Artificial Intelligence (EPIA). (Cited on page 93.) [Passos and Rossetti, 2010a] Passos, L. and Rossetti, R. J. F. (2010a). Traffic light control using reactive agents. In Proceedings of the 2nd Workshop on Intelligent Systems and Applications (WISA 2010), collocated with the 5th Iberian Conference on Information Systems and Technologies (CISTI 2010). (Cited on page 93.) [Passos et al., 2011b] Passos, L., Rossetti, R. J. F., and Reis, L. P. (2011b). Evaluation of taxi services on airport terminal’s curbside for picking up passengers. In Proceedings of the 3th Workshop on Intelligent Systems and Applications (WISA 2011), collocated with the 5th Iberian Conference on Information Systems and Technologies (CISTI 2011). (Cited on page 92.) [Passos et al., 2014] Passos, L. S., Abreu, R., and Rossetti, R. J. F. (2014). Sensitivity analysis of spectrum-based fault localisation for multi-agent systems. In Proceedings of the 25th International Workshop on Principles of Diagnosis (DX’14). (Cited on page 9.) [Passos et al., 2015a] Passos, L. S., Abreu, R., and Rossetti, R. J. F. (2015a). Spectrumbased fault localisation for multi-agent systems. In Yang, Q. and Wooldridge, M., editors, Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI’15), pages 1134–1140. AAAI Press. (Cited on page 9.) [Passos et al., 2013b] Passos, L. S., Rossetti, R., and Gabriel, J. (2013b). Diagnosis of unwanted behaviours in multi-agent systems. In Proceedings of the 11th European Workshop on Multi-Agent Systems. (Cited on page 9.) [Passos et al., 2015b] Passos, L. S., Rossetti, R. J., and Gabriel, J. (2015b). An agent methodology for processes, the environment, and services. In Rossetti, R. J. and Ronghui, L., editors, Advances in Artificial Transportation Systems and Simulation, pages 37 – 53. Academic Press, Boston. (Cited on page 92.) [Passos and Rossetti, 2010b] Passos, L. S. and Rossetti, R. J. F. (2010b). Traffic light control using reactive agents. In Information Systems and Technologies (CISTI), 2010 5th Iberian Conference on, pages 1–6. (Cited on page 63.) 113 References [Xu and Deters, 2004b] Xu, P. and Deters, R. (2004b). Using event-streams for faultmanagement in mas. In Proceedings. IEEE/WIC/ACM International Conference on Intelligent Agent Technology, 2004. (IAT 2004)., pages 433–436. IEEE. (Cited on page 24.) [Xu and Deters, 2005] Xu, P. and Deters, R. (2005). Fault-management for multi-agent systems. In Applications and the Internet, 2005. Proceedings. The 2005 Symposium on, pages 287 – 293. (Cited on pages 24, 28, 30, 32, 35 and 37.) [Yoo et al., 2014] Yoo, S., Xie, X., Kuo, F.-C., Chen, T. Y., , and Harman, M. (2014). No pot of gold at the end of program spectrum rainbow: Greatest risk evaluation formula does not exist. Technical Report Technical Report RN/14/14, University College London. (Cited on pages 7, 59 and 83.) [Zamir et al., 2014] Zamir, T., Stern, R., and Kalech, M. (2014). Using model-based diagnosis to improve software testing. (Cited on page 48.) [Zhang et al., 2009] Zhang, Z., Thangarajah, J., and Padgham, L. (2009). Model based testing for agent systems. In Filipe, J., Shishkov, B., Helfert, M., and Maciaszek, L. A., editors, Software and Data Technologies, volume 22 of Communications in Computer and Information Science, pages 399–413. Springer-Verlag. (Cited on page 20.) [Zhang et al., 2011] Zhang, Z., Thangarajah, J., and Padgham, L. (2011). Automated testing for intelligent agent systems. In Gleizes, M.-P. and Gomez-Sanz, J. J., editors, Agent-Oriented Software Engineering X, volume 6038 of Lecture Notes in Computer Science, pages 66–79. Springer-Verlag. (Cited on page 20.) [Zoeteweij et al., 2007] Zoeteweij, P., Abreu, R., Golsteijn, R., and van Gemund, A. J. (2007). Diagnosis of embedded software using program spectra. In Engineering of Computer-Based Systems, 2007. ECBS ’07. 14th Annual IEEE International Conference and Workshops on the, pages 213–220. (Cited on page 39.) 120