TOWARD A PLATFORM FOR MULTI-LAYERED MULTI-AGENT SITUATED SYSTEM (MMASS)-BASED SIMULATIONS: FOCUSING ON FIELD DIFFUSION

The paper introduces some issues and related solutions adopted in order to realize the MMASS platform. This is a framework to specify and execute simulation applications based on the multi-layered multi-agent situated system model (MMASS). MMASS is a model for multi-agent systems (MAS) situated in an environment whose structure is explicitly defined. The behavior and interaction models of MMASS agents are strongly related to the spatial structure of their environment.

The MMASS model is the result of a long-term research that has its roots and motivations on application domains and problems that require spatial features to be considered.

Our experiences with these problems have concerned the design of domain models and their implementations, according to the MAS approach for simulation purposes. This activity has revealed that currently available tools do not support the management of spatial features of agent environment and interaction mechanisms defined by the MMASS model and thus they are not suitable for our purposes.

The paper focuses on the MMASS platform that aims to support the specification and development of applications (mainly, simulations) based on MMASS. Design issues and related solutions that have been adopted in order to manage those aspects that characterize the MMASS model will be shown. After a description of the conceptual model that underlies the MMASS platform and its general architecture, we will overview how the platform supports the specification of agent structured environment, behavior and interaction, and how it supports the execution of agent actions and interactions. Then we will describe issues and adopted solutions (both algorithmic and implementative ones) to manage at-a-distance interaction among MMASS agents.

The recent evolution and the growing interest in multi-agent systems (MAS) have led to some interesting development and execution tools and platforms for agent software developers. AgentBuilder (2004); JACK (2005); JADE (Bellifemine et al. 2001); JAFMAS (Chauhan and Baker 1998); Madkit (2005); Zeus (Nwana et al. 1999); Swarm (2005); Ascape (2004); Repast (2005); Mason (Luke et al. 2003); AgentSheets (2003); and StarLogo (2005) are some examples of these types of tools. Platforms for development of multi-agent systems are widely heterogeneous. Although, some of them are grounded on well-known models (e.g., BDI (Rao and Georgeff 1995) for agent behavior, or KQML (Finin et al. 1997) and FIPA ACL (2005) infrastructures for communication among agents), they limit the development of MASs designed according to these models. This may represent a serious issue, both from a conceptual and from a computational point of view, when these models are not suited to represent the specific application domain: For instance, it is not appropriate to model simple entities by means of rational entities, as it is unrealistic and unnecessary to provide them with advanced social abilities. For instance, this is the case of multi-agent-based simulation (MABS) applications, which often exploit simple reactive agents whose interaction causes global emergent effects. On the other hand, some platforms cover only some of the features of MAS, like single-agent platform, mobile-agent platform or interaction infrastructures toolkit. In particular, few of them deliver a complete development environment (e.g., integrated development environment or IDE) supporting users in every development stage (i.e., analysis, modeling, design, development, and deployment) in order to create MAS-based applications (Ricordel and Demazeau 2001).

The work presented in this paper is part of a larger project aimed to develop an integrated development environment (IDE) (i.e., a language, needed infrastructures, and tools) to design, develop, and run simulation-oriented applications based on the multi-layered Multi-Agent Situated System (MMASS) model (Bandini et al. 2002). The latter is a formal and computational framework where to describe, represent, and simulate complex systems that require spatial features to be explicitly considered and different forms of interaction to be integrated.

The MMASS model gives an explicit definition of the spatial structure of the environment (i.e., space) as a multi-layered network of sites in which situated agents act and interact. A single layer is modeled as a graph, and thus neighborhoods (both for sites and for agents, which inherit these relationships from the sites they are situated on) are not uniform across the space. Different layers composing a MMASS space are interconnected by means of interfaces, which regulate the exchange of signals among layers. The MAS is composed by heterogeneous agents (i.e., different agent types, with different features and behaviors that can be defined) that derive spatial relationships (e.g., distance and adjacency) from the structure on which they are situated. Both actions and interactions of situated agents are strongly dependent on the agents' positions in their structured environment. Different forms of interaction are possible within a MMASS: synchronous reaction between spatially adjacent agents and asynchronous and at-a-distance interaction through a field emission-diffusion-perception mechanism. Fields are emitted by agents according to their type and state, and propagate throughout the spatial structure of the environment according to their diffusion function, reaching and being eventually perceived by other spatially distant agents. Different sensitivity to fields, capabilities, and behaviors characterize agents of different types. The platform also supports the implementation of applications based on the situated cellular agents (SCA) model (Bandini et al. 2003), which is a particular class of MMASS characterized by a single-layered agent environment and specific constraints on field definition. The attention paid to the role of the environment in agent behavior and interaction makes these models closer to reactive and biologically founded approaches (Parunak 1997) rather than deliberative ones.

The MMASS platform will provide services to manage the basic elements that characterize the MMASS model. The main ones are:

	Specification and modification of agent structured environment.
	Behavior description and execution of situated agents.
	Synchronous reaction involving spatially adjacent agents.
	Specification and management of field emission-diffusion-perception mechanism (i.e., asynchronous and at-a-distance interaction among agents).

The services provided by the MMASS platform could be exploited by software developers to implement and execute their own applications. The first class of applications whose development the platform will support are simulations. The aim of simulation developers is to build a representation of the target reality and then to translate that model into a software simulation (i.e., a software implementation of the domain model). These activities can require a great effort and work, and can be profitably supported in two ways. First, the application of a modeling approach (i.e., abstractions, concepts, and mechanisms) to different domains allows to facilitate the modeling phase. Not only the modeling task can be performed in shorter time, but also it can exploit a framework already validated in other domains and that is characterized by known features. Moreover, when a known modeling approach is adopted, also the task of model translation into software simulations can be facilitated. For instance, tools to manage simulation specification, execution, and validation (according to features and peculiarities of the modeling framework) can be provided with many evident advantages for developers.

The MMASS platform consists of a set of reusable and configurable software packages that can be exploited (e.g., reused or specialized) when a system based on a MMASS model has to be implemented for simulation purposes. An object-oriented (OO) design approach has been chosen, since (like it has been demonstrated by existing tools and platforms) it is particularly suitable for agent implementations. Moreover, like for most available tools for MAS-based applications, the Java programming language has been adopted due to its features and provided tools (e.g., for concurrent and distributed programming).

The long-term project aimed to develop the MMASS platform has been planned according to three main steps.

As schematically shown in Figure 1, first basic software components devoted to manage the whole MAS-based system and to provide a set of services that are not strictly related to the MMASS model but that are required by all software applications (e.g., management of interaction between the application and its users) are realized (i.e., basic library). Then, the MMASS library is designed in order to allow to incrementally add new software components that are more specifically related to the MMASS model. The latter is a set of general classes that provide services required by the MMASS framework (e.g., spatial structure definition and modification, field diffusion and perception, agent autonomous execution) and that can be specialized by software developers in order to implement their specific MMASS-based applications. In order to fully match the global project goals (i.e., to develop an IDE for MMASS simulations), the MMASS library has to be integrated with tools to support the monitoring, analysis, and evaluation of simulations.

FIGURE 1 Development stages for MMASS platform.

WHY A NEW PLATFORM FOR MAS?

Several existing tools and platforms for the development of MAS-based applications have been analyzed in order to decide whether to adopt one of them and to adapt it for supporting the development of MMASS-based applications (in particular, IDE and software tools devoted to simulation applications have been considered in this analysis). The result of this evaluation step was that none of today's available tools is suitable for our purposes, or the effort required to adapt them in order to represent and manage MMASS concepts in a general way is too high. In particular, one of the main elements that distinguish the MMASS model is the explicit representation of spatial structures and the definition of interaction mechanisms that are strongly dependent on the context in which interaction takes place. To our knowledge, the only approaches that provide abstractions and concepts for environment representation and space-dependent forms of communication comparable to MMASS at-a-distance interaction are pheromone-based models such as those adopted by Swarm (and other projects that are based on it, like Ascape, Repast, and Mason) and Co-Fields (Mamei and Zambonelli 2006). There are other relevant works in the area of situated MAS, but they are mainly focused on situated agent action and synchronization issues (Weyns and Hovoet 2003).

Swarm-based platforms generally provide an explicit representation of the environment in which agents are placed and mechanisms for the diffusion of signals. However, in the previously mentioned platforms, this diffusion mechanism is not well documented and, even though it allows a certain degree of configurability (e.g., through the definition of constants regulating signals diffusion and evaporation), it does not allow the definition of specific diffusion functions. Moreover, the possibility to distribute signals over the spatial structure and the mechanism to regulate this process exploit specific spatial features. Therefore diffusion is strictly related to the definition and implementation of the spatial structure and, as a consequence, is only available for particular regular lattices (square and hexagonal grids). Swarm and other projects based on it may thus represent a possible solution for specific simulations, even modeled with MMASS, but would require a heavy effort to design and implement more general spatial structures and diffusion mechanisms (see Bandini et al. [2003]) for an example of a immune system model based on MMASS implemented exploiting repast).

The Co-Fields model has been recently proposed within the area of agent coordination and it provides a novel interaction method for agents through an explicit description of agent context (more generally, the model is proposed for distributed components). The Co-Fields approach provides agents with contextual information in order to tackle a central issue in agent modeling that cannot be disregarded and delegated to ad-hoc implementations (i.e., spatial context awareness). This approach is particularly interesting for us since it, even designed with different aims and goals, suggests a solution that is similar to the one proposed by at-a-distance interaction between MMASS agents. In this model agents are constantly guided by fields, while in MMASS, every perception of a field triggers a single action. Despite this difference, the TOTA middleware (Mamei and Zambonelli 2004), which implements the Co-Field approach in distributed environments, represents an interesting possible support for the implementation of MMASS based distributed applications.

Some other integrated development environments (e.g., AgentSheets, StarLogo, and to a certain degree even MadKit) are provided with a representation of spatial structures, but the related abstractions and mechanisms are strictly related to a specific MAS model and would be hardly adaptable to supply a suitable support for MMASS interaction model. Other general purpose MAS platforms (e.g., Jade, Zeus, and MadKit) are generally based on a point-to-point message-passing communication model. Agents are aware of each other, or they can obtain acquaintance information from a facilitator (an agent that plays the role of white pages), and can directly exchange messages, according to specific rules defined by an agent communication language (Finin et al. 1997). In this kind of approach concepts related to the spatial context in which interaction takes place are not elements of the model and must be unnaturally introduced in the interacting entities (that should regulate their own interaction, according to considerations on their own context, for instance, discarding specific messages) or in third-part modules (e.g., other facilitators implementing a sort of space agent, managing perceptions and interactions). In fact, in the last two cases, conceptual elements (i.e., interaction and spatial context management) would be mixed up with other aspects related to domain-specific issues (e.g., agents' behavior) and delegated to ad-hoc implementations, which are generally not reusable.

THE MMASS LIBRARY

Design Choices

The designed and developed tool provides developers of MMASS-based simulations with reusable modules implementing elements of the model (i.e., space, agents, and fields) and the possibility of creating structured environments on which MMASS agents can be situated before starting the simulation. To this purpose, all the basic concepts and mechanisms defined by the MMASS had to be considered. Since the model is very rich, and provides a complex interaction model, the design and implementation of a platform supporting all the provided concepts and mechanisms in a generalized situation is clearly a long-term project. At first glance it is clear that there are specific concurrency issues not only in a synchronized system situation, but also with reference to agent mobility and in the management of reaction, and the related agreement process. In order to obtain a usable and useful prototype representing a first version of a platform supporting MMASS-based simulations, we focused on some aspects that we considered crucial for the first applications we planned to implement with it. What we needed was a support for a basic agent, able to move throughout the non-uniform spatial structure of its environment, and able to emit and perceive MMASS fields in order to communicate with other agents. The agent deliberation strategy that has been implemented is the simplest one: Actions included in its behavioral specification are evaluated in the order they were stated and the first one whose preconditions are verified will be executed. Moreover, this first implementation of the platform does not provide any support to implement reactions (i.e., the local and synchronous interaction among adjacent MMASS agents), which is currently delegated to specific agent implementations.

Field diffusion through the MMASS space has been considered as a fundamental task for the first version of the platform. Implemented mechanisms for field management concern issues related to field emission, diffusion, and perception within the graph-like spatial structure on which MMASS agents are situated. Even in this case design choices have lead to consider a specific class of fields that constitutes a specialization of the more general field defined by the MMASS model. In the following these design choices will be motivated and described in more details.

Underlying Conceptual Model

At a conceptual level, the relationships between MMASS elements that have been considered for the design and development of the library are represented in Figure 2. The main elements of the MMASS model are the environment, the layers that compose it (also called spaces), agents, which inhabit this environment, and the types of signal that they may emit and perceive (i.e., fields).

FIGURE 2 MMASS model elements and relationships among them.

Every space is composed of sites. Each site is characterized by the space (i.e., space layer) it belongs to, the set of adjacent sites, the set of fields active in it, and the agent that it (possibly) hosts; a site may host at most one agent, according to a non-interpenetration principle. Both fields and agents are characterized by a type. For agents it specifies the allowed states and the specification of perceptive capabilities (i.e., the sensitivity to field types, based on agent current state) and behavioral specification (i.e., specified actions, with related preconditions, and action selection strategy). Field type instead specifies the allowed states, the diffusion function defining the effects of field emission (i.e., the extent of its diffusion), and the comparison and composition functions that are related, respectively, to the perception of that type of field and the composition of fields of the same type. In fact, at a given site, a unique value for every field type is perceivable by an agent situated on that site.

Each agent acts autonomously as an effect of its perceptions according to its state, position, and type. An agent is situated in a site (and just one, according to a non-ubiquity principle) and can emit one or more fields. Thus, a field is an entity that can be emitted by an agent (each field instance can be emitted by a single agent), and propagates throughout sites (thus, fields derived from the same emission can be present on more than one site). The MMASS space is defined as a multi-layered structure, thus the MMASS space is composed by a set spaces. An agent can change its state or site as an effect of field perception. When an agent emits a field, the latter is communicated to the hosting site that diffuses it into adjacent sites, according to a specific diffusion algorithm. This topic will be more thoroughly discussed later.

General Architecture

The MMASS library has been designed to be composed of different layers of modules. At the top there are simulation applications that are coordinated and managed during their execution by the MasManager module. Simulations can be seen as MasManager extensions that are created by developers for their own simulation problems. Then, a module for each MMASS basic element follows: The Graph module manages sites (i.e., graph nodes) and connections among them (i.e., graph edges) that are defined by the Sites module; the Space module defines different spatial structures that are defined as graphs of sites. The Diffusion module manages at-a-distance interaction mechanism among agents by diffusing throughout space sites fields that are defined by the Fields module. The Agents module is posed on top of Space and Diffusion modules since it exploits them to manage agent behavior. Utility services are provided by modules represented as ovals in Figure 3: The SpaceEditor allows the specification of spatial structures through a graphical user interface (GUI), while the MASViewer allows for the visualization of the spatial structure, agents, and fields during the simulation execution. Finally, the lowest level of Figure 3 shows the Java API, since Java is the development language exploited as a development platform.

FIGURE 3 The structure of the MMASS library.

From the implementation viewpoint, library classes are organized into packages according to the structure of the MMASS model. Each package corresponds to a basic element of the MMASS model. The Space package contains a set of classes to manage the spatial structure of simulations and it contains the tool for graphical visualization. The Sites package manages single sites, diffuses fields, and contains the Graph package that defines classes for edges and nodes. Relationships among packages have been defined: For instance, the Space and Site packages are related since each space is composed of a set of sites and, vice versa, each site contains information about the space it belongs to. The Field package contains a set of classes corresponding to different field types, while the Agents package defines the structure of an agent. The relationship between the Site package and the Field package exists since a site contains information about the set of fields that are active in it, while its relationship with the Agent package concern information about hosted agent.

Within the MMASS library, all basic elements have been defined either as interfaces or as abstract classes. Moreover, the library contains also a set of classes that can be reused or specialized for specific tasks. When the library does not provide suitable tools for the aims of developers (e.g., it does not provide suitable classes for their target simulation), they can implement and possibly extend an interface, adding new functionalities to it. In the following we will provide more details about the module of the MMASS library that manages field diffusion and we will give some indications about interfaces and classes that are available within the related package.

MasManager

The MasManager module manages the whole MAS since it owns all the information about a specific simulation (e.g., space structure and agents), as shown in Figure 4. Moreover, it represents an interface to simulation developers and users. The MasManager provides a GUI to start and stop simulations, and to visualize the simulation evolution. Start action corresponds to activate all threads that are associated to agents and those that manage the spatial structure, while stop action causes the opposite effect. Currently, the MasManager does not manage single agents once they have been created and their autonomous behavior has started, since design choices lead to implement a first version of the library in which no control on agent execution is possible. On the contrary, if developers need to control the execution of some agents (e.g., they need agents to act synchronously), the MasManager implementation has to be modified and provided with control functionalities on agents. Similarly, other MasManager extensions could provide developers with functionalities, for instance, to visualize through GUI agents and sites properties, to modify the spatial structure (e.g., adding or deleting sites, modifying connection between sites), or to modify the set of agents (e.g., adding or deleting agents).

FIGURE 4 Concerns of the MasManager.

Managing MMASS Environments

The Space module manages the environment in which agents move and fields diffuse. Between the possible representations for the space, an adjacency list has been chosen for the implementation of the Space module. This choice was motivated by the assumption that the space structure is not dense, that is, in a graph of n nodes, the number of edges is much lower than n ². Thus, the required memory occupation (i.e., O(e + n), where e is the number of edges) is quite lower than O(n ²) required by an adjacency matrix. Moreover, thanks to this choice, some frequently used operations on the graph are executed in a constant time (e.g., to obtain the neighboring sites to a given site).

Space and Site packages contain all the elements that allow the management of the spatial structure. The first one, shown in Figure 5, defines classes containing sites that specify how to build the graph with them, while the second package implements single sites. The current implementation of the platform provides a single-layered structure for the space and, thus, all site adjacency defines links between sites belonging to the same space layer. In order to extend the platform and allow the definition of multi-layered spatial structure for agent environments, Site package must be extended to allow adjacency relationships to exist between sites belonging to different layers (i.e., external adjacency). The main classes that have been defined to support space specification and management will be now briefly outlined.

FIGURE 5 A high-level class diagram for the Space package.

Graph management is performed through an adjacency list in which the set of adjacent sites is associated to each site. Directed and weighted graphs can be defined. DefaultNode class represents a graph node and it is characterized by the set of incoming and outgoing edges. These sets are managed by a set of operators that allow to add and delete edges (e.g., at graph creation). Moreover, it is possible to know the set of its adjacent nodes (i.e., nodes with an incoming edge that goes out from the target node). DefaultEdge class represents an edge graph and it is characterized by the pair of nodes that are linked by a given edge. Edges are directed, and in order to define undirected edges, two directed edges must be defined. A site identifies a position within the space and constitutes a node graph. Each site stores a set of information about the agent situated in it and about fields that during their diffusion have passed through it. In order to manage conflicting accesses to a site, mutual exclusion strategy has been selected. The Site class has been implemented specializing the DefaultNode class and it is available as part of the MMASS library.

AbstractSpace class defines a generic space, contains information about the set of sites belonging to it, and describes the set of services offered by it (e.g., space creation and management, site addition and deletion, support for field diffusion). The spatial structure is built at simulation start-up, during which sites are added and adjacency is defined. AbstractSpace subclasses implement specific spatial structures, some of which are defined by the library, while others can be created by simulation developers. In particular, regular spatial structures (e.g., bi-dimensional grid) and generic spaces (defined through a standard markup language) are available within the library. For instance, when a bi-dimensional grid has to be defined by a simulation developer, an instance of Grid2DSpace class can be created specifying the number of rows and columns (Figure 6 represents a toroidal grid 5 × 5 with a Von Neuman neighborhood).

FIGURE 6 Regular 5 × 5 toroidal grids with Von Neumann neighborhood (a VonNeumannTorusSpace in the MMASS space package).

Other types of regular spaces (e.g., grids with Moore neighborhood, hexagonal grid, and 3D bi-dimensional grid) can also be added to extend the library. XmlSpace class is another implementation of AbstractSpace that allows specifying a spatial structure as a XML file. The library interprets these files and builds the corresponding space. Figure 7 shows an example of the XML format. The < graph > tags contain the graph definition. Within < node > tag, each node is defined by a numeric identifier, an optional label, and node coordinates. Within < edge > tag, each edge is defined by its source and target nodes, and an optional weight and label.

FIGURE 7 XML spatial definition and the corresponding graph editing tool.

A possible graphical representation of a situated MAS is shown in the middle of Figure 7. The library representation is based on a defined notation, where circles correspond to sites, lines to edges, small circles to agents, and different colors indicate different agent states. Spatial structure definition has been facilitated through the adoption of a graphical tool that has been included in the library. Figure 7 also shows the user interface of an integrated tool that allows users to situate nodes, to create edges between nodes, and to store the corresponding XML file. After having stored an XML file corresponding to the desired and drawn spatial structure, developers can exploit this file for different simulations. The possibility to design a similar support for the definition of standard field types, with basic diffusion strategies, is currently being considered.

Managing MMASS Agents

As previously introduced, the current MMASS library provides a basic model for agents. Agents are described as entities situated on a site that are able to perceive their surrounding environment and move and emit fields. The library supports the definition and execution of this basic type of agent, providing an interface that developers can exploit to implement their specific agent model.

In particular, the interface includes the AbstractAgent class that specifies the set of basic actions that can be performed by agents. It constitutes a building block to specify agents. In fact, simulation developers are not required to know the implementation of agent behavior, they simply have to select behavior to endow agents with and let the library define them. An abstract agent is specified by the set of information the agent owns, its perceptions (i.e., the set of fields it can perceive), and the set of actions it is able to perform. An agent owns information about its spatial context and, more precisely, with reference to:

	The site it is situated in and its adjacent sites.
	The set of fields that are present on its site and into its neighborhood.
	Other agents that are situated in adjacent sites.

An agent can move into adjacent sites not occupied by other agents and can emit fields. Actions and perceptions are realized through interactions involving the agent and its hosting site. For instance, the emit action is realized by communicating to the hosting site that a new field has to be diffused (in this way, the hosting site becomes a new source site). Moreover, the result of agent perception is an updating of its available information. Agent perception is an action that the agent can execute: The agent asks its site about the set of active fields or whether a specific field is active.

Agents must be defined by developers as subclasses of the AbstractAgent class (Figure 8 shows a sample concrete agent definition). Agents are implemented as threads and their behavior can be defined redefining the run() method and exploiting other methods defined for abstract agents. Examples of agent implementations are provided by the MMASS library and others performing specific behaviors can be added.

FIGURE 8 Concrete agents are subclasses of the AbstractAgent class.

The library has been designed and developed under the assumption that no more than one agent can be hosted by a site. This means that when an agent has to move into a site, it has to verify that it is occupied by another agent. Thus, situations in which a set of agents have to move into the same site have to be managed by the MMASS library. The management of this type of conflict was one of the design issues for the library and the adopted solution in this case was to implement the simple first-arrived-first-served strategy, and to allow library users to modify it and implement their own strategy, according to their application requirements. In order to extend the library to other strategies, the AbstractAgent class must be redefined. On the contrary, in order to allow the possibility of multiple agents to coexist in the same site, the AbstractSite class must be defined while control on agent movement is no longer necessary (in this case, policies on the maximum number of agents that can be hosted by a site must be considered and managed accordingly). Similar solutions have been adopted for other issues related to the development of the MMASS library. In the following section, issues related to the management of at-a-distance interaction of MMASS agents will be described together with the adopted solution, its implementations, and a description of assumptions under which this solution has been designed.

Managing MMASS Fields

In order to realize the MMASS library, at-a-distance interaction between agents had to be managed and the mechanism for field emission-diffusion-perception to be implemented. Field emission is realized as communication between the emitting agent and its hosting site: The site is informed by the emitting agent about the field initial intensity value, while field perception is realized as an agent action performed to ask about new active fields. The next subsections will describe the algorithmic solution that has been designed to manage field diffusion and its implementation within the MMASS library, under the assumption that no central control is allowed and thus, local interaction between sites are exploited.

MANAGING FIELD DIFFUSION

To design an algorithm for field diffusion over a generally irregular spatial structure, several aspects must be taken into account and different alternatives are possible. The rationale of this work was to provide a spatial infrastructure supplying the service of field diffusion to entities that are placed in it. No assumption was made on the synchronicity of the system, and on the form and nature of the diffusion function directing field diffusion in the environment. This means that, for instance, a signal generated by an entity could possibly reach all sites in the agent environment. In this scenario there is not a generally optimal algorithm, but each application presents specific features that must be taken into account in the choice (or design) of a strategy for field diffusion. One of the main aspects to be considered is the nature of the spatial structure, the number of agents that can emit fields, their emission frequency, and whether they can move throughout the space or are they immobile. The introduction of assumptions on field diffusion function (for instance, limiting the diffusion range to a constant number of hops) or on the spatial structure (for example, limiting it to regular structures) dramatically simplifies the algorithms and structures required to perform this operation, at the cost of reducing the generality of the approach. However, in case of particularly large spatial structures, the latter may represent a favorable solution.

In the following subsections, a possible approach to field diffusion in the previously introduced scenario will be described.

Field Diffusion: Algorithmic Solution

The designed algorithm specifies the way sites can perform field diffusion, according to the field diffusion function. It has been designed under the assumption that field diffusion has to take place throughout an irregular, undirected, and non-weighted graph and that the number of agents is high and characterized by frequent field emissions. Under these assumptions we considered the possibility of storing a spatial structure representation for each site, and, namely, a minimum spanning tree (MST) that connects the site to all other sites (in fact, an emitted field could possibly reach all sites in the space). This solution requires a long start-up time and a large amount of memory space. However, it becomes convenient during execution, since these structures are frequently used and the overhead for their construction at every diffusion operation would be relevant.

Among the several algorithms for MST building, design choices led us to analyze those approaches that could be easily adapted to work in a distributed and concurrent environment. The breadth first search(BSF) algorithm starts exploring the graph from a node that will be the root of the MST, and incrementally expands knowledge on the structure by visiting at phase k nodes distant k hops from the root. This process can be performed by nodes themselves (sites, in our case), that could offer a basic service for local graph inspection and it could be useful also in the case of dynamic structures. The root site could inspect its neighborhood and require adjacent sites to do the same, iterating this process with newly known sites until there is no more site graph to be visited. An important side effect of this approach is that this MST preserves the distance between sites and the root (i.e., the path from a site to the root has a number of hops equal to its distance from the root). Fields propagate through arcs of the MST and thus the computation of the diffusion function is facilitated. The complexity of the MST construction using this approach is in the order of O(n + e), where n is the number of sites and e is the number of edges in the graph. Such an operation should be performed by every site, but with a suitable design of the underlying protocol they could proceed in parallel. Field diffusion requires at most O(log _b n), where b is the branching factor of the MST centered in the source site and the field diffusion between adjacent sites is performed in constant time. The issue of this approach is the memory occupation of MST structures, that is, O(n ²) (in fact it is made up of n MSTs, each one providing n-1 arcs). Moreover, if the agents-sites ratio is not high or field emission is not frequent enough to keep stored, the MST for every site could be pointless, since many of those structures could remain unused. In order to face this issue some correctives have been considered (other correctives could be designed and applied according to specific requirements of the target domain and problem). A first approach provides the storage of just one MST, requiring a central data structure with the distances between different sites, and another provides the construction of MSTs by request and the caching of this structure in a limited buffer. The first approach uses a single MST whose edges are used to diffuse fields that will thus reach every site just once (see Figure 9). For the diffusion of a field, the source site becomes the root of the tree and exploits it to send the related information to other sites. However, this structure does not preserve the actual distance between nodes, so, to effectively compute the actual value of a field in the destination site according to the diffusion function, another structure is needed to store distances among nodes. This structure's size is O(n ²), so according to the asymptotic memory occupation, this approach is comparable to the previous one, and the same holds for the time complexity related to the building of these structures. To perform a diffusion operation instead, a field must visit n-1 sites in the worst case. This approach seems thus comparable to the previous one, according to the space occupation, and even worse according to the complexity of the diffusion operation. This comparison is related to asymptotical costs, but related constants could be relevant (at least for certain values of n) so these results should be supported (or possibly confuted) by tests and benchmarks.

FIGURE 9 A single minimum spanning tree allows the diffusion of a field over the space without replications, but a separate structure is needed to compute field intensity in destination sites. The structure size is O(n²).

The second modification does not bring substantial changes in the infrastructures and algorithms, but limits the memory occupation by defining an MST cache facility that allows the storage of a constant number of these structures. By doing so, the space complexity is reduced to O(n), but the diffusion operation is more complex, because it depends on the cache hit-rate. If the MST centered on the source site has already been built and is still in the cache, the cost of diffusion is at most O(log _b n), otherwise the MST must be constructed and the cost grows to O(n + e). This approach seems thus the most effective, especially in a scenario where the agents-sites ratio is not high and agents do not have a high mobility. In order to adapt this approach, a suitable strategy for cache management (e.g., derived by virtual memory handling policies), and especially for MST replacement in the related buffer, should be defined and implemented.

Field Diffusion: Implementation

The underlying idea of field diffusion implementation is that each site receives a field to modulate its intensity (according to field diffusion function) and communicates the related data to its neighboring sites, which will do the same until the diffusion function voids the field intensity. This communication is guided by additional structures that were defined in the previous section, providing a unique diffusion path for every site and preserving distance from the source of the emission. In order to implement the solution that allows to provide field diffusion with both these properties, MST building and exploitation must be implemented within the MMASS library. Since the diffusion of a field emitted in site S (i.e., source site) must occur through the MST that has its root in S (see Figure 10), and since fields can possibly be emitted in any site space, it is necessary to built a set of MSTs, where each MST has its root in one of the graph sites. In order to implement MST building, the distributed version of the breadth first search algorithm (i.e., layered breadth first search ¹ ) has been exploited. Within the MMASS library, information about MSTs is provided to the space (in particular, to its sites) that builds these diffusion infrastructures and provides information about them to entities that eventually requiring them. MST building can be performed for all sites at simulation start-up or on demand during simulation execution when required. As shown in the previous section, the choice between these possible strategies must take into account memory occupation, agents' mobility, and field emission-rate. One of the goals of the library is to provide standard spatial structure implementations, providing different diffusion strategies and allowing users to select the one that is most suitable to the simulation they are implementing.

FIGURE 10 Minimum spanning tree with S as source site.

Fields are defined as objects that can be present on space sites and are defined by the Field package. Field diffusion strategy is defined in the Space package, as different approaches could be profitably defined for different spatial structures. In order to allow this separation, an interface defining required services for fields was defined. In particular, diffusion function, composition, and comparison of its intensity values (in the following, also referred as values) are part of this interface. AbstractField class is a first implementation of interface Field and also specifies that a field is characterized by: a unique identifier, a name (or field type), and an intensity value. Fields are defined as AbstractField subclasses and define implementations for diffusion, compose, and compare functions. For instance, ColoredField and EvaporateColoredField are two classes that are available within the MMASS library that are characterized by a color attribute, a diffusion function that decreases field value at each diffusion step, and a composition function that computes the mean field value.

During field diffusion, a site that has to diffuse a field first asks the space about the set of sites to which perform diffusion (specifying the field source site), and then the space returns to the site the portion of the source MST that includes the asking site. Figure 11 shows three situations in which to the same site d, different set of sites (a and b, or S, or a, S, and b) are returned for the diffusion of fields that have different source sites (S, e, and d, respectively). The operative diffusion infrastructure is contained in the Site package and its main classes are Site and SiteManager. A Site owns information about the spatial layer it belongs to, is connected to other sites, and its main task is to perform local field diffusion. Fields active in a site can be classified into diffused fields and visible fields. The first type indicates fields that are diffused on a site; they can be characterized by different identifiers, but they may belong to the same field type (e.g., they can be different instances of the same field). On the contrary, only one visible field of each field type can be active on a site, as agents perceive a single intensity for a specific field type. Visible fields have been introduced for implementation purposes and correspond to fields resulting by composing different diffused field of the same type. In fact, only visible fields are modulated and actually diffused to other sites.

FIGURE 11 Three minimum spanning trees used for field diffusion, according to the source site (root node of the tree).

Site is a passive entity offering services that are required for field management: When new fields are diffused to it, it adds them to the set of its diffused fields. When agents ask information about active fields, it provides information about visible fields, and modulates (and eliminate, if needed) fields according to their diffusion functions. SiteManager is a thread that actually manages the site and its main task is field diffusion and management. When a new instance of Site class is created, a SiteManager is created, too, and associated with it. SiteManager interacts with its site in order to add new incoming fields, and it interacts with the SiteManager associated to neighboring sites to diffuse fields. This type of interaction has been implemented by introducing a message queue (i.e., buffer) in which fields to be diffused must be inserted. The SiteManagers detect the presence of fields to be diffused and send messages about diffused fields (i.e., DiffuseFieldMessage). Messages in the buffer indicate its sender and content: The content represents the field identifier and the site where it has been emitted. Thus, the SiteManager adds the read field to its set of diffused fields and diffuses it to its neighboring sites. SiteManager performs diffusion according to three steps: It asks the space to which sites it has to diffuse field (i.e., subset of neighboring sites belonging to the MST with root in the source site), encapsulates the field into a message, and sends the message to them (i.e., inserts it into their buffers).

A SAMPLE APPLICATION: HUMAN AGENTS IN PHYSICAL ENVIRONMENTS

Design and development activities on the MMASS platform will continue in order to provide developers of MMASS applications with an IDE that can support them fruitfully during specification and execution stages. First-use cases of the current version of the library were developed in the area of crowd modeling and simulation in realistic environments using SCAs. In particular, in fact, for this kind of application, a single-layered environmental structure is enough to model the space where pedestrians move and interact to generate realistic crowd behaviors. Such a spatial structure is augmented with specific “immobile” agents, which are really parts of the environment generating specific attraction or repulsion effects (modeled as fields) that, for instance, guide agents in their movement toward exits from a given room in an evacuation scenario. Figure 12 shows a screenshot of the platform user interface (on the left) and a 3D rendering of the simulation dynamics generated with 3D Studio Max (on the right). In this case, the platform exported the structure of the environment and the dynamics of the agents' movement into a log file that was parsed by a 3D Studio Max script.

FIGURE 12 A sample crowd modeling application of the MMASS platform. On the left, the simulator UI shows the spatial structure of agents' environment. On the right, the final 3D visualization is shown.

In particular, the simulator based on the described platform produces results that can undergo a quantitative analysis whose results can be easily understood by experts of the area of application. To do so, the specific MasManager developed for the simulation must implement a form of MAS monitoring activity to analyze the dynamics of relevant system entities (e.g., changes in the position of pedestrian). In different scenarios, the MasMonitor could be in charge of checking the relevant elements of the system that must be reported for analysis, or it could be simply notified by active elements themselves when relevant actions are carried out. However, the monitor should suitably store the acquired data into log files that can be imported by common data analysis tools for further processing.

For sake of communication with non-experts, it can also be useful to obtain a more effective visualization of simulation dynamics. To this purpose, the previously introduced log file should be exploited to instruct an external instrument on the scene to be rendered on the dynamics of the agents (i.e., paths followed by pedestrian). In the described application, the log file had a fixed-record structure, in which every record was related to a node of the spatial structure or the position of an agent with reference to this structure. Initially, the simulator prints on the log the entire structure of the environment and the starting position of each agent. At the end of each iteration, the new position of every agent is also printed. This file is parsed by a 3D Studio Max script, which generates a plane and walls related to the spatial structure, nodes related to sites, and bipeds related to agents. Splines are then generated starting from the discrete positions assumed by various agents, and represent bipeds' movement. This process introduces modifications to trajectories defined by the bi-dimensional simulator whose sense is to give a more realistic movement to agents' avatars. The process interfacing the bi-dimensional simulator and the 3D modeling tool is summarized in Figure 13.

FIGURE 13 The interface between the bi-dimensional simulator and an external 3D modeling tool (3D Studio Max) is realized by means of a log file indicating relevant elements of simulation dynamics.

CONCLUSIONS AND FUTURE WORKS

The paper describes the MMASS library, a first step toward the development of an IDE for applications based on MMASS or SCA models. In particular, an algorithmic solution and the related implementation to manage field diffusion have been described. We claim that there is not a generally optimal algorithm to tackle this issue, but each situation presents specific features that must be taken into account in the choice or design of a strategy (and thus structures and algorithms) to manage field diffusion. However, some possible solutions have been presented specifying the type of situations for which they can be suitably adopted. Other issues related to the development of the MMASS platform will be tackled with a similar approach: A first step toward the management of synchronization issues related to the reaction among agents can be found in Vizzari and Bandini (2004).

A sample application providing the exploitation of data generated by a crowd behavior simulator was introduced. This application, which essentially demonstrates the potential of innovative visualization systems supporting MABS instruments, actually started a new vein of research which aims at the design and development of a distinct platform that enables the implementation of MMASS-based simulation in an interactive 3D environment, allowing the dynamic visualization (and possibly modification) of simulation execution without the need for an external 3D modeling instrument such as 3D Studio Max. In this context, the need for efficient strategies supporting field diffusion has a higher priority than the generality of the approach. Moreover, in this case, the involved spatial structures are generally grids (with missing nodes representing areas in which agents may not walk). The diffusion strategies that are being considered for this full 3D platform are thus different from those described in this paper.

Other activities related to the described work will concern, on one hand, the design of new experiments within the MABS area, but, on the other hand, different application domains will be considered. The notion of space, in fact, can be adopted fruitfully for modeling several distributed applications for which the MAS approach can also be suitable. First steps in this direction have been made to apply the MMASS model within the CSCW context (see Bandini et al. [2002]).

The work presented in this paper has been partially funded by the Italian Ministry of University and Research within the FIRB project “Multichannel Adaptive Information Systems.” The authors would like to thank Carla Simone for her valuable contribution to the fundamental work on the theoretical foundation of the MMASS model. Moreover, the authors would like to thank the people who contributed to the development of the MMASS platform.

Notes

1. http://www.risc.uni-linz.ac.at/software/daj/BFS