| Titre : | A Graph Transformation Approach for Dynamic Reorganization in Multi-Agent Systems |
| Auteurs : | Fayçal Guerrouf, Auteur ; Allaoua Chaoui, Directeur de thèse |
| Type de document : | Thése doctorat |
| Editeur : | Biskra [Algérie] : Faculté des Sciences Exactes et des Sciences de la Nature et de la Vie, Université Mohamed Khider, 2021 |
| Format : | 1 vol. (110 p.) / couv. ill. en coul / 30 cm |
| Langues: | Français |
| Mots-clés: | Multi-Agent System,Organization Centered Multi-Agent System,Reorganization.,Complex System,AGG,Graph Transformation |
| Résumé : |
Nowadays, complexity and high distribution are considered as the main properties of large real-world systems such as airports and manufacturing systems. The Organization Centered Multi-Agent System (OCMAS) approach is advocated as an appropriate solution to handle the complexity and the distribution of such systems. These systems are often open, and execute under a dynamic environment with unpredictable interaction. In fact, the concept of organization that is explicitly defined in OCMAS provides a key feature to the designed system which is the “stability”. Despite that, when the Multi-agent system operates in dynamically changing environments and often unreliable communication resulting in various events originating from its external environment and/or its internal elements which de-stabilize the system state. To overcome this kind of undesirable situation, the Multi-Agent System has to reorganize its behavior and structure to continue fulfilling its overall objectives.In this dissertation, we proposed a formal approach for the reorganization of a multi-agent system statically at design time or dynamically at run-time. Indeed, we proposed to formulate the reorganization using graph transformation. In particular, we have defined a type graph to represent the multi-agent system organization and a set of rules that define the different actions that can be performed to reorganize the system. We implemented our approach using AGG. We evaluated our approach on a case study related to a manufacturing system implemented as a Multi-Agent System. The obtained results show the efficiency and the effectiveness of our approach. |
| Sommaire : |
Acknowledgment ii Abstract iii Résumé iv Contents vii List of Figures xi 1 Introduction 1 1.1 Context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 The problem studied in the thesis . . . . . . . . . . . . . . . . . . 4 1.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4 Thesis Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 I State of the Art 8 2 Background 9 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2 Graph Transformation System . . . . . . . . . . . . . . . . . . . . 10 2.2.1 Graph and Graph Morphism . . . . . . . . . . . . . . . . 11 vii2.2.2 Typed Graph and Typed Graph Morphism . . . . . . . . 11 2.2.3 Graph Rule . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2.4 Concept of Transformation . . . . . . . . . . . . . . . . . 14 2.2.5 Negative Application Conditions . . . . . . . . . . . . . . 14 2.2.6 Typed Attributed Graph . . . . . . . . . . . . . . . . . . . 14 2.2.7 Typed Graph Transformation System . . . . . . . . . . . 15 2.2.8 Typed Graph Grammar . . . . . . . . . . . . . . . . . . . 16 2.2.9 Graph Transformation Tools . . . . . . . . . . . . . . . . . 16 2.3 Agent-Oriented Software Engineering . . . . . . . . . . . . . . . 17 2.3.1 Concept of Agent . . . . . . . . . . . . . . . . . . . . . . . 17 2.3.2 Multi-Agent System . . . . . . . . . . . . . . . . . . . . . 19 2.3.3 Agent Centered Multi-Agent System . . . . . . . . . . . . 20 2.3.4 Organization Centered Multi-Agent System . . . . . . . 22 2.3.5 Concept of Organization . . . . . . . . . . . . . . . . . . . 22 2.3.6 Types of Agent Organization . . . . . . . . . . . . . . . . 25 2.3.7 Organizational Change Motivation . . . . . . . . . . . . . 29 2.3.8 Reorganization . . . . . . . . . . . . . . . . . . . . . . . . 31 2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3 Literature Review 36 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.2 Semi-Formal Approaches . . . . . . . . . . . . . . . . . . . . . . 37 3.2.1 GORMAS Approach . . . . . . . . . . . . . . . . . . . . . 37 3.2.2 OMACS Framework . . . . . . . . . . . . . . . . . . . . . 39 3.2.3 MOISE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.3 Graph Transformation Based Approaches . . . . . . . . . . . . . 42 3.3.1 Multi-level graphs for System Reorganization . . . . . . 42 3.3.2 A Model for MAS with Dynamic Organizations . . . . . 44 3.3.3 Rule-Based Modeling and Static Analysis of Self-adaptive Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.4 Formal specification approaches for Multi-Agent Systems . . . . 47 3.4.1 Formal Semantics Framework . . . . . . . . . . . . . . . 47 3.4.2 Rewriting Logic for the Specification of MAS . . . . . . 48 3.4.3 Automatic generating algorithm of rewriting logic for multi-agent system . . . . . . . . . . . . . . . . . . . . . 49 3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 II Contributions 51 4 Graph Transformation Approach for the Reorganization in Multi-Agent Systems 52 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.2 Approach Overview . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.2.1 MAS Monitor . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.2.2 MAS Organization . . . . . . . . . . . . . . . . . . . . . . 55 4.2.3 Reorganization Manager . . . . . . . . . . . . . . . . . . . 55 4.2.4 Basic Elements Life Cycle . . . . . . . . . . . . . . . . . . 56 4.3 MAS Organization Type Graph . . . . . . . . . . . . . . . . . . . 59 4.3.1 ORG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.3.2 Goal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.3.3 Role . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4.3.4 Agent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.3.5 Structural State (sstate) . . . . . . . . . . . . . . . . . . . . 63 4.3.6 Behavioral State (bstate ) . . . . . . . . . . . . . . . . . . . 64 4.3.7 Extension Mechanism . . . . . . . . . . . . . . . . . . . . 64 4.4 MAS Organization Rules . . . . . . . . . . . . . . . . . . . . . . . 65 4.4.1 Behavioral Rules . . . . . . . . . . . . . . . . . . . . . . . 66 4.4.2 Structural Rule . . . . . . . . . . . . . . . . . . . . . . . . 74 4.5 Mathematical Notation of our MAS Organization . . . . . . . . 79 4.5.1 Priority . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 4.5.2 Sequentially Independent . . . . . . . . . . . . . . . . . . 82 4.5.3 Confluence . . . . . . . . . . . . . . . . . . . . . . . . . . 83 4.5.4 Termination . . . . . . . . . . . . . . . . . . . . . . . . . . 85 4.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 5 Evaluation: Case Study 87 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 5.2 Case Study Description . . . . . . . . . . . . . . . . . . . . . . . . 88 5.3 Planning and execution . . . . . . . . . . . . . . . . . . . . . . . . 89 5.4 Scenario 1: Agent Entering the System . . . . . . . . . . . . . . . 91 5.5 Scenario 2: Agent Leaving the System . . . . . . . . . . . . . . . 91 5.6 Scenario 3: A Goal Being Ended . . . . . . . . . . . . . . . . . . . 94 5.7 Discussion and limitations . . . . . . . . . . . . . . . . . . . . . . 97 5.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 6 Conclusion and Future Work 98 6.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 6.2 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 Bibliography 101 |
| En ligne : | http://thesis.univ-biskra.dz/id/eprint/5383 |
Disponibilité (1)
| Cote | Support | Localisation | Statut |
|---|---|---|---|
| TINF/157 | Théses de doctorat | bibliothèque sciences exactes | Consultable |
