Objective Coordination in Multi-Agent System Engineering

From its beginning, Artificial Intelligence (AI) has tried to synthesize intelligent behavior by reducing it to artifacts. Two families of approaches have, however, appeared [Zie97].

On one hand, Knowledge-Based AI (also named Classical AI or Top-Down AI, closely related to the classical view of cognitive sciences) has developed methodologies for manipulating internal representation models of the world, using notions like knowledge or information. This trend has focused on building expert systems (see [FMN88] for an overview) that own and manage ‘knowledge’ in a sufficiently narrow problem domain. Thus, research in this field has concentrated on knowledge representation and knowledge engineering. Several systems have shown good performance in domains like medical diagnosis and theorem proving.

On the other hand, Behavior-Based AI (also named Bottom-Up AI) considers interaction with an environment as an essential feature for intelligent behavior. Research in this area has studied systems that have ‘life’-like attributes, in particular autonomous agents that persist within an environment. Autonomous agents are therefore defined as embodied systems that are designed to fulfill internal goals by their own actions in continuous long-term interaction with the environment in which they are situated [Zie97], [Bee95]. Autonomous agents possess two essential properties: autonomy and embod- iment. Autonomy basically means that an agent acts on its own, without being driven by another agent (possibly a human): it has its own control over its actions and its internal state. Embodiment refers to the fact that an autonomous agent has a “body” that delineates it from its environment in which the agent is situated. It is on this environment that an agent senses and acts through its own specific means (sensors and effectors). The degrees of embodiment define several autonomous agent types: physical embodied agents have a physical body, sensors and effectors (they are robots); simulated embodied agents roam in a simulated physical environment; and software agents lack a body but persist and interact in a complex software environment.

Interest has rapidly shifted from the single agent case towards the multiagent case, in which several agents share a common environment and interact with one another. Thismeans that an agent participates in a society of agents, a so-called multi-agent system. These systems result therefore from the or- ganization of multiple agents within an environment, whereby the state of each agent individually changes as a result of its sensing and its own behavior rules. As no global control is applied to the participating agents, every agent has a subjective view of the evolution of the world. Multi-agent systems are therefore interested in an interaction-centered perspective. Dealing with interactions leads naturally to the concept of emergence of behavior, which essentially means that a system’s behavior can only be specified using descriptive categories which are not to be used to describe the behavior of the constituent components (the agents) [For90].

The interest for multi-agent systems (MASs) has grown increasingly in the last years. These systems are beginning to be used in a great variety of applications such as air traffic control, process control, manufacturing, electronic commerce, patient monitoring, or games. This appeal is due to the fact that multi-agent systems present very attractive means of more naturally understanding, designing and implementing several classes of complex distributed and concurrent software. This growing attention to multi-agent technology has been even more accentuated with the increase of internet computing, which integrates an underlying infrastructure presenting a space organization in which autonomous agents roam and interact with one another.

Nevertheless, as a consequence of their popularity, the terms “autonomous agents” and “multi-agent systems” are often misused. It is indeed not rare to find software described in these terms, although it is not necessarily correlated with multi-agent technology. Therefore, we have to clarify what autonomous agents and multi-agent systems really are, how they can be modeled, designed and implemented.

This chapter is organized as follows. In sections 2.2 and 2.3, we present what are autonomous agents and multi-agent systems. On this basis, we discuss in section 2.4 MAS modeling by proposing an explicit integration of the interaction setup of a MAS and by sustaining a distinction between subjective and objective coordination. Then, section 2.5 exposes our target class of systems. Finally section 2.6 discusses how practical MASs can be built and concludes by maintaining the use of coordination models and languages for the design and the implementation of MASs.

Coordination is a central problem for numerous complex dynamic systems composed of interacting activities. In order to study issues related to coordination, Malone and Crowston proposed the development of a new theory called Coordination Theory [MC94a]. This theory intends to study how coordination is handled in various systems such as in enterprises, animal colonies or markets [Kle97]. It is therefore interdisciplinary, re-grouping ideas from sciences such as computer science, organization theory, economics, linguistics or biology. By providing practical cases from these different sciences, the authors try to identify common key concepts of coordination in order to facilitate a cross-fertilization of these different disciplines.

Diverse definitions of coordination have been proposed. Probably the most general has been stated by Malone and Crowston [MC94a]:

An interesting general outlook on coordination can be found in [Oss99], in which Ossowski gives an overview on formal and informal characterizations and models of coordination in human societies and its models in social science.

In this chapter, we present the ECM1 coordination model [SCKH98], [KCDS98], [SCH99], which proposes coordination abstractions that are orthogonal to computation. ECM is a general model of the coordination languages STL2 [Kro97], [KCD+98], [SKCH98], [KCDS98], STL++ [SCKH98], [SCH99], [SCK+99] and Agent&Co. It includes the following design characteristics: - The model restricts features to the minimum, in order to concentrate on coordination duties only. So, only five abstractions have been proposed. - The model supports only anonymous communication; this means that the entities communicate anonymously through communication means without any knowledge of the identity of the communication partners. Furthermore, entities communicate through well-defined ports of communication, which are openings to their surrounding. This has several strong advantages: - the programmer can treat entities as black boxes and abandon dependencies coming from the identification of communication partners; - this forces the designer to define clean interfaces and it helps the reusability of code. - The flows of communication are automatically established, according to the state of the communication interfaces. No coordinator is in charge of binding ports in order to establish connections; this is done implicitly by the system. - Modularity is a key element of ECM, in the sense that the model supports encapsulation and nested blocks. - ECM introduces a preliminary level of privacy, because connections are private means of communications: only participant processes may read or write information on these connections. However, there is no support for stronger security such as encryption or identification of communication partners.

STL1 [Kro97], [KCD+98], [SKCH98], [KCDS98] is applied to multi-threaded applications on a LAN of UNIX workstations. STL materializes the separation of concern as it uses a separate language exclusively reserved for coordination purposes; it however provides some primitives which are used in a computation language to express interactions between the entities. The implementation of STL is based on Pt-pvm [KHS96], a library providing message passing and process management facilities at thread and process level for a cluster of workstations. In particular, blops are implemented as heavy-weight UNIX processes, and processes are realized as light-weight processes (threads).

An application written using STL is composed of two parts (see figure 5.1 as an illustration): - The computation part implemented in an ordinary computational language (file app-func.c). The implementation supports the C programming language [KR78]: every process is implemented with a function that is launched as a thread. - The coordination part implemented in STL (file app.stl).

From the STL code (app.stl), the STL-compiler produces pure C code (app.c), which uses the Pt-pvm communication API; the generated C file (app.c) together with the computation files (app-func.c)must then be compiled and linked together with the Pt-pvm and STL runtime libraries, in order to generate the executable (app).

As already stated, STL implements only coordination duties of processes implemented in a computation language (namely C). However, several primitives have been implemented to be used in the computational language. They are necessary to interact with the STL coordination elements. The set of primitives includes the following families: i) Operations to dynamically create ports, referred to as dynamic ports; note that the port type definition can only be done in the coordination language; ii) Operations for process manage- ment, namely for dynamic creation of processes from within the computation language; iii) Methods to transfer data from and to ports.

Figure 5.2 gives a first impression of what STL code looks like. In a default world blop (line 1), which is a root blop encompassing every other entity, a hierarchy of processes and blops are defined (process the process and blop the blop at lines 3 and 10) and then created (lines 14 and 16). This shows that the hierarchical structure is used yet at definition level, because a blop is always defined within another blop.

With the experience of STL, it turned out that in ECM the separation of code cannot always be easily maintained. Although the blackbox process model of ECM is a good attempt to separate coordination and computation code, dynamic properties proved to be difficult to be expressed in a separate language.

This consideration led us to initiate the development of our new coordination language called STL++ [SCKH98] [SCH99], [SCK+99]. Starting from the experience acquired with STL, a single language approach has been adopted: STL++ implements the conceptual model of ECM by embedding it in a given object-oriented language (namely C++ [Str97]) with coordination primitives realized in a library.

This chapter is organized as follows. In this introduction, we expose the principal design decisions of STL++ and give an overview of an STL++ application. Sections 6.2 to 6.6 give a semi-formal presentation of STL++. Section 6.7 discusses a tutorial example implemented in STL++. Section 6.8 sketches the main characteristics of a prototype implementation of STL++. Section 6.9 concludes the chapter with a discussion. Appendix A systematically presents the core interface of STL++.

The main motivations for the design of a new ECM instance was the desire of studying agent mobility in the context of ECM and experimenting an integration of an ECM-grounded coordination language in an object request broker architecture [OMG97b] in order to enhance portability. For that aim, a new coordination language named Agent&Co has been designed; it has been implemented as a library [Doi99], like STL++.

This chapter gives a general description of this new language binding, trying to show specific characteristics differentiating Agent&Co from STL++. Note that this project is still underway, and has therefore to be enhanced from the experience that will be acquired with testing concrete applications. For these reasons, we review Agent&Co on a general ground, skipping details. Sections 7.2 to 7.6 review the instantiations of each ECM construct, sticking to the essential. Section 7.7 discusses choices in a realized implementation.

In section 2.5, our specific class of MASs has been introduced. We have also described a generic model belonging to this class (section 2.5.1) and presented a peculiar application of this model (section 2.5.2). In this chapter, the design and the implementation of this application with ECM/STL++ is presented. Figure 8.12, at the end of this chapter, summarizes the whole process from the model to the implementation.

In the Environment, which is a torus grid, every cell has four neighbors. By applying a four connectivity, the implementation is facilitated, and this does not fundamentally vary the functionality from a more complex scheme such as an eight connectivity. The agents that roam on this environment are named SimRobots, because they simulate the robots. They comply the agent model introduced in figure 2.6 of section 2.5: the agents sense the environment through their sensors and act upon their perception at once.

To take advantage of distributed systems, the Environment is split into N sub-environments, each being encapsulated in a blop, as depicted in figure 8.1, thus providing an independent functioning between sub-environments (and hence between agents roaming in different sub-environments). Note that blops have to be arranged so as to preserve the topology of the sub-environments they implement.

STL++ has primarily been designed for supporting the implementation of MASs comprising simulated embodied agents. However, the coordination language may also be used to implement other classes of MASs. For that reason, we show in this chapter how STL++ can be used for implementing a simulation of a trading system [SCK+99], [SCH99].

Indeed, the numerous activities that take place within a trading system are typically distributed and can be modeled by a MAS. Agent-based electronic commerce is therefore becoming one of the most important application domains for MASs [NRS+98], [NS98], [MGM99]. Concrete solutions encompass several agent-based frameworks like Kasbah [CM96] or FishMarket [RANSP97].

The research in coordination models and languages has also proposed some specific scenarios for implementing electronic commerce applications; see for instance a proposal based on the PageSpace platform [CKR+97] and another one using IWIM and Manifold [PA98b].

Our goal is not to achieve full automation of a trading system. This work rather concentrates on simulating the automation of such a system. Furthermore, our aim is neither to focus on the control algorithms of the different agents, nor on the negotiation techniques (see e.g. [GM98]) that are undertaken by the agents in order to process a transaction, but rather to concentrate on the basic coordination mechanisms (the objective coordination) that come into play in the interactions between agents, for which STL++ is precisely suitable. Thus, in this implementation, agents are endowed with a very basic autonomy in the sense that they can make decisions on their own, without the intervention of the user. More sophisticated autonomy-based control algorithms and smart negotiation techniques could be tackled in a further stage.

Figure 9.7, at the end of this chapter, gives a scaled down graphical overview of the organization of the agents that compose our trading system, as well as their interactions. To avoid cluttering the graph, port names (on which the matching is based) have been intentionally omitted. Figure 9.1 shows the class hierarchy of the implementation discussed in this chapter. We explain the different classes in the following sections.

The present work has focused on the use of coordination models and languages in the field of multi-agent systems. More precisely, it has thoroughly described a general coordinationmodel named ECMand its instance STL++ in order to support the design and the implementation of simulated embodied agents’ systems.

In chapter 2, we have first described what are autonomous agents and multi-agent systems, and we have maintained an explicit integration of the interaction setup in the modeling of a multi-agent system and have proposed to distinguish between objective and subjective coordination as the management of objective and subjective dependencies in a multi-agent system. Then, after having introduced embodied simulated autonomous agents systems, our target class of systems, we have proposed a specific approach to the implementation of multi-agent systems whose main benefit is an explicit integration of the objective coordination dimension in the design and implementation of a multi-agent system. To that aim, we have sustained the use of coordination models and languages (from the fields of concurrent and distributed computing, programming languages and software engineering) in order to support the design and the implementation of multi-agent systems. Hence, in chapter 3, we have proceeded with the review of existing coordination models and languages on the basis of an established taxonomy that classifies models as data-driven or process-oriented. We have, furthermore, presented several hybrid models, some of them being also used for multi-agent systems. Finally, we have analyzed the prerequisites which we have required for a coordination model and for a language to be used for our target class of multi-agent systems.

In chapter 4, we have presented the ECM model of coordination. Its main benefits, in regard to our requirements exposed in chapter 3, are the following: - Thanks to blops, ECM allows a grouping mechanism that permits the encapsulation of a set of agents, local communication within the created space, and hierarchical structuring means for an environment. - ECM processes support the realization of a basic autonomy, because they are conceived as blackboxes, which also permits a pro-active behavior. Process data is private and, therefore, not accessible to other entities. - Sensing and effecting on the environment are supported thanks to anonymous communication through ports. - Basic communication paradigms are supported (stream, group and blackboard). Furthermore the setup of the communication means is ensured in a decentralized manner thanks to the implicit matching mechanism.

In the subsequent chapters we have presented the three existing ECM instances. In chapter 5, we have reviewed STL which is a separate language to be used in conjunction with a computation language realizing the coordinated processes. STL is intended at the implementation of multi-threaded applications in the context of network-based concurrent computing. STL showed important potentials for the implementation of multi-agent systems. This was the reason for the abstraction of STL’s basic ideas towards a general coordination model (ECM) and the definition of a new coordination language, STL++. STL++ has the following benefits: - It enhances dynamicity, enabling dynamic blop as well as agent creation and termination, and dynamic port creation and deletion, thus allowing reorganization of the connection patterns. - It has a single language approach in order to facilitate dynamicity and to help uniformity in the programming. - It is conceived in an object-oriented way, because every ECM abstraction has a corresponding class, and the operations on these abstractions are class methods. - The semantics of each ECM construct is clearly specified, especially in what concerns port matching, deleted ports and consequent freed connections.