Soutenance mémoire
EAC Engineering and Simulation Tools
To enable the benefits of the MIC∗ environment and the coordination theory developed in this thesis to be applied to an EAC context we have developed a social model of the software system. Within this social metaphor, the software system is considered as an open society of agents that interact with other societies in a spontaneous manner. So, new organisational concepts have been introduced such as the internal and interface roles, intracives and extracives in order to adapt the social metaphor to the EAC context. An integrated develompment environment (IDE) allows the modelling of the artificial society and generates automatically the source code of the software system using the MIC∗ environment and the coordination framework.
Constraints and Hypotheses of the EAC
In order to present a coherent and relevant state of the art, one has to make a preliminary study of the constraints and hypotheses of the EAC. This preliminary study is used in order to select the existing works that may constitute relevant starting points for our work. From the software engineering point of view, we have considered the following major constraints and hypotheses of the EAC:
Constraints of the Communication Medium: Within the EAC, communication media are not centralized but appear locally and spontaneously as soon as the physical or logical communication links can be established. Besides, the communication between the software entities can be intermittent and disturbed. These disturbances have not to be considered as network problems but as hypotheses of work to be taken into account at the conceptual and implementation levels.
Hypothesis of the Autonomy: Traditional software engineering approaches assume to have a complete knowledge and control of the software entities that compose the software system. However, this assumption is challenged in open and large-scale distributed systems. In fact, several systems developed by different authorities have to communicate and interact. For example, let us consider a typical scenario of an Internet-based application where an open software system developed by a company ’X’ interacts with another software system developed by a company ’Y’. Neither of these companies controls the global software system that is made by the composition of the two sub-systems:’X’ plus ’Y’. However, these independent systems have to interact and coordinate their actions to offer their functions. The lack of knowledge and means to control the behavior of a software entity makes this entity behaving autonomously. The EAC assumes the autonomy of the software entities and systems. So, the autonomy feature has to be considered at the conceptual and implementation levels.
Hypothesis of the Openness: As mentioned in section [1.2, page 14] the EAC assumes the openness of software systems. In fact, the added value of the EAC is created by the composition of open and interacting services. So, the EAC offers the potential to provide a new generation of e-services, only because new functionalities can emerge by the spontaneous interactions of more elementary services.
Interpretation of the Autonomy
Steels in [Steels, 1995] tries to understand what makes a software entity autonomous. This paper refers to a personal communication with Tim Smithers (1992) on the autonomy: “The central idea in the concept of autonomy is identified in the etymology of the term: autos (self ) and nomos (rule or law). It was first applied to the Greek citystate whose citizens made their own laws, as opposed to living according to those of an external governing power. It is useful to contrast autonomy with the concept of automatic systems. The meaning of automatic comes from the etymology of the term cybernetic, which derives from the Greek for self-steering. In other words, automatic systems are self-regulating, but they do not make the laws that their regulatory activities seek to satisfy. These are given to them, or built into them. They steer themselves along a given path, correcting and compensating for the effects of external perturbation and disturbances as they go. Autonomous systems, on the other hand are systems that develop, for themselves, the laws and strategies according to which they regulate their behavior: they are self-governing as well as self-regulating. They determine the paths they follow as well as steer along them.” This description defines the autonomy of a system (or an entity) as its ability to produce its own laws and to follow them. By contrast, an automatic system (or entity) is given the laws and leaves them unchanged. There are also other interpretations of the autonomy that will be presented in section [2.5.2, page 41]. Still, the actual question is not in knowing what is the ’correct’ interpretation of the autonomy but what is the most appropriate and meaningful for the EAC. In fact, on some generic concepts there will be no consensus and people accept the definitions that are meaningful to their specific domain. For the EAC the most meaningful interpretation of the autonomy is the one that relates autonomy to the lack of knowledge and means to control the software entities. In other words, the more an observer lacks knowledge and means to control a software entity, the more she/he has to consider it as an autonomous entity. However, there is still a gap between the conceptual debate on the autonomy and the engineering of autonomous software entities. In fact, within the literature of MASs several works present the how to build an autonomous software entity. For instance, for a cognitive agent, this agent must have motivations that steer its behaviors (cf. §2.5.2, page 41). These approaches assume too much knowledge on the agents’ internal model. In fact, who can force all the agents of the EAC to have an explicit model of motivations in order to be considered as autonomous! In this thesis we have adopted a different point of view: the primary question is not to have a recipe of how to build an autonomous software entity, but what are the low levels requirements to guarantee autonomy. In [Goua¨ıch, 2003], we argue that the internal integrity of a software entity is a sine qua none condition for the autonomy. The internal integrity is a programming constraint that avoids the direct access or modification of the software entities’ internal state. So, the autonomous software entities have to be considered as bounded blackboxes that do not intersect. In fact, if the structure of the software entity is accessed or modified by any external entity, the decision process may be altered and consequently the autonomy feature is lost. The internal integrity is also shown for collaborative learning where the learning occurs as an autonomous construction of knowledge. For instance, when an agent A ”learns by being told” a piece of software from agent B, it is always A who decides to perform the change on its own state [Cerri et al. , 2004].
Concerns of the Interoperability
The communication is far from being sufficient to make heterogeneous open software systems working together and coordinating their joint activities. In fact, when the information is encoded as data and transmitted using the communication medium; the entity that receives the data has to be able to decode the information and to capture its meanings and semantics. So, while the communication media deal with the transfer of the encoding of information from one point to another; the interoperability means deal with the transfer of the semantics of information from one point to another. Furthermore, the interoperability concerns also the means that makes the open systems collaborating for the achievement of joint activities. The first concern of the interoperability that is related to the transfer of the semantics is represented by the following works: eXtensible Markup Language (XML) [W3C, 2004a], RDF Resource Description Framework (RDF) [W3C, 2004c], OWL (Web Ontologies Language) [W3C, 2004b], Knowledge Interchange Format (KIF) [Genesereth & Fikes, 1994], DARPA Agent Markup Language (DAML) [McIlraith et al. , 2001], Knowledge Query and Manipulation Language (KQML) [Finin et al. , 1994], Semantic Language (SL) [FIPA, 2002c],FIPA Agent Communication Language (FIPA-ACL) [FIPA, 2001]. The following works represent the second concern of the interoperability which is related to the collaboration of open systems: coordination means presented in section [4.2, page 92], Web Services [W3C, 2002b], Web Service Choregraphy Interface (WSCI) [W3C, 2002a], Business Process Modelling Language (BPML) [DBMI, 2000], Web Services Flow Language (WSFL) [Leymann, 2001], XLANG [Thatte, 2001], Business Process Execution Language for Web Services (BPEL4WS) [Weerawarana & Curbera, 2002].
Pioneer Works on the Blackboard Paradigm
The title of this section should be ’Pioneer works on the Blackboard Paradigm in Informatics’. In fact, the blackboard paradigm is probably the most ancient and natural paradigm that the humanity has followed to communicate in a timely and spatially uncoupled manner. So, its pioneer works have to be considered with the appearance of the civilizations and humanity. Still, this is too far from the problem treated by this thesis. Within the informatics, the first works that mention the explicit use of a shared and persistent communication medium are those of the ’distributed artificial intelligence’ (DAI). In contrast to the classical artificial intelligence (AI) field where the focus is made on the reasoning capabilities of a single ’intelligent’ entity; the DAI focuses on the ’intelligence’ of a group of entities. Hence, during the late 70s first DAI systems have emerged as an interesting alternative for complex problem resolution. Originally, this research was to shift the focus from computational control (e.g. algorithmic approach for problem resolution is about computational control) to the communication and co-ordination among distributed entities. The HEARSAY II [Erman et al. , 1980] is a speech recognition system used to recognize English speeches and querying databases. It is considered as the first system that has used the BB paradigm: several software entities coordinate their actions and share knowledge througha common data space. Erman and colleagues have noticed that finding an algorithmic solution for the speech recognition problem is very hard. In fact, speech recognition involves different competences of different entities, called knowledge sources (KS), to recognize signals, syllables, words, sentences, semantics and so on. These entities need also to collaborate and to share knowledge. This was conducted through the blackboard. However, the entities’ decision process was not totally autonomous and a meta-entity, called Focus, was defined in order to steer the execution of the system. Still, the global control was not known before the execution and determined as a result of the entities interactions. The Ether system is another example of pioneer blackboard systems. The Ether has been introduced by a student of C. Hewitt (cf. §2.5.1, page 38), W.A. Kornfeld in [Kornfeld, 1979]. Kornfeld has noticed that the distribution is usually motivated by efficiency. Hence, the programs are executed concurrently to use more resources and to terminate more quickly. He suggested the use of distribution for more ’qualitative’ criteria rather than ’quantitative’ criteria. To demonstrate his approach, he developed a theorem-proving application: two different algorithms proving a mathematical property were implemented; when these algorithms where collaborating and sharing their partial results, the solution was found more quickly. Kornfeld’s architecture is composed of two orthogonal components: the Ether, representing the persistent communication medium; and theSprites, representing the software entities. The sprites communicate by sending and retrieving messages from the Ether. Furthermore, a sprite may stop its execution waiting for a particular event to arrive in the Ether. In contrast to its precedents architectures, the Ether has made the properties of the blackboard explicit. So, the blackboard is no longer a flat set of data without any structure but owns some particular properties that affect the dynamics of the software system. For instance, the Ether defines the property of the commutability: the sprite creation and appearance of a message in the Ether are commutative operations; and the monotoniaty: messages cannot disappear from the Ether
TuCSoN
TuCSoN is a Linda-like TS proposed by A. Omicini and F. Zambonelli [Omicini & Zambonelli, 1998]. The TuCSoN model has been designed for coordination purposes and not only for communication. For instance, the authors use the term of coordination medium rather than the communication medium to highlight the objectives of the TuCSoN model and architecture. Despite the fact that TuCSoN is a Linda-like TS, there are significant differences between these architectures. In fact, just as MARS [Cabri et al. , 2001] (another Linda-like TS), the TuCSon model introduces the idea of a programmable coordination medium: while Linda is composed of tuple spaces that define statically the interaction schemes between the tuples and the anti-tuples, within TuCSoN the interaction schemes of the tuple centres [Omicini & Denti, 2001a] are programmable and can be dynamically changed using the ReSpecT [Omicini & Denti, 2001b] logical programming language. In other words, each tuple centres may define its own rules of reaction to the elementary communication primitives. This is a significant modification of the initial approach proposed by Linda. In fact, the communication medium is now an active entity that affects the dynamics of the global software system. Consequently, the communication medium has to be considered explicitly as a first class entity2 during the engineering phases of the software system.
|
Table des matières
1 The “Everywhere, Anytime, Computing” Paradigm
1.1 Introduction
1.2 Definition of the EAC Context
1.3 Problem and Thesis Statements
1.4 Contributions
1.4.1 MIC∗
1.4.2 Coordination and Conversation Protocols
1.4.3 EAC Engineering and Simulation Tools
1.5 Outlines
2 State of the art
2.1 Introduction
2.2 Glossary
2.2.1 Definitions
2.2.2 Using the Terms in Examples
2.3 Constraints and Hypotheses of the EAC
2.3.1 Dealing with the Constraints of the Communication Medium
2.3.2 Dealing with the Autonomy of the Software Entities
2.3.3 Interoperability of Open Systems
2.3.4 Overall Discussion
2.4 The Blackboard Paradigm
2.4.1 Pioneer Works on the Blackboard Paradigm
2.4.2 The Tuple Spaces
2.4.3 Tuple Space Architectures
2.4.4 Advantages and Limitations of the BB Paradigm and TS Architectures for the EAC
2.5 The Multi-Agent Systems Paradigm
2.5.1 Pioneer Works of MASs
2.5.2 Current Vision(s) of MASs
2.5.3 Agent Centered MAS and System Centered MAS
2.5.4 The FIPA Proposition to Address the EAC
2.5.5 Advantages and Limitations of the MAS Paradigm to Address the AEC
2.6 Conclusion
3 The MIC∗ Deployment Environment
3.1 Introduction
3.2 Motivations for the Explicit Representation of the Deployment Environment
3.2.1 Guaranteeing the Autonomy
3.2.2 Enabling the Identification of the Responsibility of the Autonomous Agents
3.2.3 Modeling On-the-fly Composition of the Software Systems
3.3 The MIC∗ Model
3.3.1 Intuitive Introduction to MIC∗
3.3.2 Formalizing the Intuitions
3.3.3 MIC∗ Elements as Algebraic Equations
3.3.4 The Dynamics of MIC∗
3.4 The Specification and Implementation of the MIC∗ Model
3.4.1 Populating the Deployment Environment
3.4.2 The Perception/Deliberation/Influence Agent’s Loop
3.4.3 The Composition of MIC∗ Deployment Environments
3.4.4 MIC∗ Packages and Classes
3.4.5 Classes Description
3.5 Building a Social Framework upon MIC∗
3.5.1 Presentation of the Social Framework
3.5.2 Implementation of the Social Framework
3.5.3 Mapping Table between AGR and MIC∗
3.6 Conclusion
3.6.1 Acknowledgement
4 Coordinating the Autonomous Agents
4.1 Introduction
4.2 Backgrounds
4.2.1 Generalized Study of the Coordination
4.2.2 Formalisms to Express the Coordination Protocols
4.2.3 Architectures and Middlewares for Coordination
4.2.4 The Conversational Aspect of the Coordination
4.2.5 Discussion
4.3 Intuitive Introduction to the Dependency-Based Coordination Model
4.4 Formal Definition of the Dependency-based Coordination Model
4.4.1 Definition of the Dependency-based Coordination Model
4.4.2 The Digraph Associated to the Dependency-Based Coordination Model
4.4.3 Partitioning the Dependency-based Coordination Model
4.5 The Generated Resource Patterns
4.5.1 Marked Resource Set
4.5.2 The Structure of the Resource Patterns
4.5.3 Recognizing Actual Resources by Using the Control Functions
4.6 Validating the Conversations According to a Coordination Protocol
4.6.1 Informal Presentation of Petri Nets
4.6.2 The Queue Petri Net Theory
4.6.3 Building the QPN from the Coordination Protocol
4.6.4 Algorithm to Validate Conversations using the QPNs
4.7 Link between the Generated Resource Patterns and the QPNs
4.8 The XML Representation of DBCM Coordination Protocols
4.9 Integrating the Coordination Framework within MIC∗
4.9.1 Global and Centralized Control of the Coordination Process
4.9.2 Local and Decentralized Monitoring of the Coordination Process
4.9.3 Complete Example of the Distributed Monitoring of the Coordination Process
4.10 Conclusion
5 Building Open Software Systems as Open Artificial Societies
5.1 Introduction
5.2 State of the Art
5.2.1 AAII
5.2.2 AGR/Aalaadin
5.2.3 AUML
5.2.4 CoMoMas
5.2.5 GAIA
5.2.6 MACE
5.2.7 MaSE
5.2.8 MASSIVE
5.2.9 MAS-CommonKADS
5.2.10 MESSAGE
5.2.11 PASSI
5.2.12 SODA
5.2.13 TROPOS
5.2.14 Discussion
5.3 Organizational Model for Open Artificial Societies
5.3.1 Proposition of an Organizational Model for (not yet open!) Artificial Societies
5.3.2 Opening the Organizational Model
5.3.3 Overall Picture of the Organizational Model
5.4 Translating the Organizational Model into MIC∗ Deployment Environment
5.4.1 Translating the Organizational Structure
5.4.2 Translating the Functional Mapping
5.4.3 Integrated Development Environment for the Specification of Open Artificial Societies
5.5 Application: Ubiquitous Web
5.5.1 The ’Web Server’ Specifications
5.5.2 The ’Web Client’ Specifications
5.6 The EAC Simulation Platform
5.6.1 Presentation of the Simulation Platform
5.6.2 Link between the Simulation Platform and the MIC∗ Layer
5.6.3 User Views in the Simulation Platform
5.7 The Virtual City Project
5.8 Conclusion
6 Conclusion
6.1 Synthesis
6.2 Summary of the Main Contributions
6.2.1 MAS
6.2.2 BlackBoards & Tuple Spaces
6.2.3 Coordination
6.2.4 Social Metaphor for the Engineering of EAC Applications
6.3 Perspectives
6.3.1 Grid Computing
6.3.2 Multi-Agent Based Simulations
6.3.3 Fault Tolerant Software Systems
6.3.4 Extending the Coordination Framework
6.3.5 Development Environments and Tools to Build EAC Applications
6.4 General Conclusion
A Mathematical notations
B Formal definition of Petri-Net Theory
B.1 MultiSet (Bag) Theory
B.2 Petri Net Structure
B.3 Petri Net Markings
B.4 Execution Rules for Petri Nets
C MIC∗ Message Headers
C.1 General Definition of the Message Structure
C.2 Agent to MIC∗ Message Headers
C.2.1 Login Request Message
C.2.2 Login Reply Message
C.2.3 Logout Request Message
C.2.4 Inbox Request Message
C.2.5 Inbox Reply Message
C.2.6 Movement Request Message
C.2.7 Movement Reply Message
C.2.8 Computation Request Message
C.2.9 Computation Reply Message
C.3 MIC∗ to MIC∗ Message Headers
C.3.1 Connection Request Mess
C.3.2 Connection Reply Message
C.3.3 Diconnection Request Message
D DTD and XML Definitions
D.1 Dependency Based Coordination Model
D.1.1 DTD Definition
D.1.2 Examples of Coordination patterns expressed using the XML representation
D.2 XML Formalism For the Specification of Open Artificial Societies
E Testing the Conversations of the Ubiquitous Web Application
F Introduction to Networking Technologies
F.1 The OSI Model
F.2 How Does it Work?
F.3 Networking Technologies
F.3.1 TCP/IP
F.3.2 Mobile IP and IPv6
F.3.3 Bluetooth
F.3.4 Infrared Data Association (IrDA)
F.3.5 IEEE 802.11
F.3.6 HomeRF
F.3.7 HiperLAN
F.3.8 DECT
F.3.9 Global System for Mobile Communication (GSM)
F.3.10 HSCSD
F.3.11 GPRS
F.3.12 EDGE
F.3.13 UMTS
F.3.14 Analysis of the Network Technologies
References
Télécharger le rapport complet
