Holonic Multiagent Multilevel Simulation: Application to Real-Time Pedestrian Simulation in Urban Environment

1 Introduction

A large complex system contains a great number of interacting entities. Their components are themselves complex (nested relationship) and the boundaries of the system are difficult to determine. Some behaviors and patterns emerge as a result of interactions between elements [Simon, 1996; Holland, 1995; Rodriguez, 2005]. Exhibiting all these characteristics, the urban environments can thus be considered as complex systems. In recent years, scientific community has seen an great number of research works dedicated to complex systems. Multiagent systems are emerging as one of the most adapted tools for analysis, modeling and simulation of this kind of systems. The holonic paradigm [Koestler, 1967] and its application to multiagent systems have proven to be an effective solution to model complex systems [Tecchia et al., 2001; Ulieru and Geras, 2002]. Holons are defined as self-similar structures composed of holons as substructures. They are neither parts nor wholes in an absolute sense. The organizational structure defined by holons, called holarchy, allows the modeling at several granularity levels. Each level corresponds to a group of interacting holons.

Since we consider several individuals and their relationships, the complexity of the system is increased. One issue in the real-time simulation of complex systems is to allow multilevel simulation. This type of simulation aims at dynamically adapting the level of the entity behaviors (microscopic, macroscopic) while being as faithful as possible to the simulated model. We propose a holonic organizational multilevel model for real-time simulation of complex systems by exploiting the hierarchical and distributed properties of the holarchies. To fully exploit this model, we estimate the deviation of simulation accuracy between two adjacent levels through physics-based indicators. These indicators will then allow us to dynamically determine the most adapted level for each entity of the application to maintain the best compromise between simulation accuracy and available resources.

After a short review of related works, this paper will introduce our holonic organizational model. Then we will detail our physics-based indicators and how to integrate them into a multilevel model. Finally a 3D real-time multilevel simulation of pedestrians is presented as well as a discussion of experimental results.

2 Related works

A great number of works dedicated to multilevel simulation have already been proposed in many scientific domains : social simulation [Troitzsch, 1996], virtual urban simulation [Donikian, 1997], robotics [Pettinaro et al., 2003], real-time multilevel simulation platforms [Kim, 2001]. However, multilevel modeling works are mainly concentrated on Computer-Aided Design (CAD) optimizations [Schwabacher, 1998]. Besides the major part of existent multilevel models work with a fixed number of levels, usually two : microscopic and macroscopic. Moreover the level at which an entity is simulated is usually fixed, determined a priori by the designer according to its experience and experimental results of previous simulations. This point of view is shared by [Ghosh, 1986] who proposes the first dynamical multilevel simulation. His approach is based on hierachical models from an abstract level to a more concrete one.

As soon as we consider a highly detailed simulation of several individuals and their relationships, the complexity of the system and the associated computational costs increase. The multilevel simulation appears as one of the best solutions. [Brogan and Hodgins, 2002] and [Musse and Thalmann, 2001] propose multilevel behavioral models for mobile entities in virtual environments or situated environments, where various behaviors are attached to virtual characters.

In the multiagent domain, works dealing with multilevel problems mainly focus on the study of emergent phenomena with various approaches : mathematical, biological, or a purely multiagent way. MAS models for emergence usually deal with multilevel emergent structures (also called multiple emergence) [Heylighen, 1989] and focus on the detection and the recognition of behavioral patterns [Beurier et al., 2003]. Multiagent-based simulations (MABS) often lead to the emergence of local groups of entities [Servat et al., 1998], but provide no means of manipulating them. Giving a full sense to multiagent simulations would certainly imply the dynamic creation of agent's groups, but also their agentification to deal with specific behaviors at each level. [Van Aeken, 1999] introduces the notion of minimal multiagent system to study the dynamics of multiagent systems. This approach is based on the creation of a composed agent for each couple of atomic agent that could be merged. Even if its model remain relatevily abstract and difficult to apply to real applications, we can consider that with HMAS we adopt an equivalent approach. But the modularity and the reusability of the holonic organizational model (cf. section 3.1) allow us to overcome Van Aeken's model drawbacks. Our approach consists in dynamically grouping agent and creating new level, and also determining the deviation of simulation accuracy between adjacent levels through physic-inspired indicators. The aims of these indicators is to dynamically detect when it's necessary to switch between simulation levels.

3 An holonic multiagent approach for multilevel simulation

3.1 An holonic organizational model

A holon can be seen, depending on the level of observation, either as an autonomous "atomic" entity or as an organization of holons. This duality of holons, sometimes called the Janus Effect in reference to the two faces of a holon, is particularly useful for the multilevel simulation and is detailed in the next section. In order to allow a modular and reusable modeling that minimizes impact on the underlying architecture, we have leaned for a model based on an organizational approach. We have selected the framework of [Rodriguez et al., 2006; Rodriguez, 2005] based on the Role-Interaction-Organization (RIO) model [Hilaire et al., 2000] to represent organizations. This model enables formal specification, animations and proofs based on the OZS formalism [Gruer et al., 2004]. OZS is a multi-formalisms language combining Object-Z and Statechart notations to describe an agent's role. Statecharts are used to describe the behavior of the roles, and specify their possible states and how events may change these states. Object-Z schemas describe operations called by the statechart.

So as to maintain this framework as generic as possible, [Rodriguez, 2005] distinguishes two aspects that overlap in a holon. The first is directly related to the holonic character of the entity, i.e. a holon (super-holon) is composed of other holons (sub-holons or members). This aspect is common to every holon, thus called holonic aspect. And the second is related to the problem(s) the members are trying to solve, and thus specific to the application or domain of application.

A super-holon is an entity in its own right, but it is composed by its members. Then, we need to consider how members organize and manage the super-holon. This constitutes the first aspect of the holonic framework. To describe this aspect, [Rodriguez, 2005] define a particular organization called Holonic Organization. This organization represents a moderated group [Gerber et al., 1999] in terms of roles and their interactions. It defines three main roles corresponding to the status of a member inside a super-holon. The Head role players are the representatives or moderators of the group, and a part of the visible interface. For the represented members two different roles have been defined. The Part role represents members belonging to only one super-holon. The Multi-Part role is played by sub-holons shared by more than one super-holon. In this approach, every super-holon must contain at least one instance of the Holonic Organization. Every sub-holon must play at least one role of this organization to define its status in the super-holon composition.

Super-holons are created with an objective and to perform certain tasks. To achieve these goals/tasks, members must interact and coordinate their actions. The framework also offers means to model this second aspect of the super-holons. These goal-dependent interactions are modeled using organizations, called Internal Organizations, since they are specific to each holon and its goals/tasks. The behaviors and interactions of the members can thus be described independently of their roles as a component of the super-holon. The set of internal organizations can be dynamically updated to describe additional behaviors. The only strictly required organization is the Holonic organization that describes member's status in the super-holon. At the holon level, organizations are instantiated into groups. Figure 5 depicts an example of such an instanciation. Notation g1: Scheduling denotes that g1 group is an instance of the organization Scheduling. Super-holon 21 is thus composed of three groups. The first one represents an instance of the holonic organization, and the other two groups instanciate the goals-dependent organizations : Scheduling and Pedestrian Navigation 1 .

This approach guarantees a clear separation between the management of the super-holon and the goal-specific behaviors and favors modularity and re-usability. Further details on the framework can be found in [Rodriguez, 2005].

3.2 Applying holonic model to multilevel scheduling mechanism

[Michel, 2004] describes the 4 fundamental aspects of a MABS : Agent Behaviors, Environment, Scheduling and Interaction. Agents' behaviors and interactions being strongly dependent from the applications, our approach focus on the scheduling aspect to remain generic. So we propose to exploit the hierarchical structure and scalable properties of the holarchy to ensure dynamical scheduling of the behaviors (role) at various simulation levels. This approach is essentially dedicated to simulations requiring good performances (real-time, virtual reality. . . ) and involving a great number of individuals and their relationships (i.e. crowd, traffic or more generally urban simulation). By simulation levels, we refer to the accuracy, the complexity and/or the realism of the individuals behaviors.

1 The RIO diagram of these organizations are shown in figure 1 resp. 4

Each individual is associated to an atomic holon. These holons are grouped into super-holons according to their affinity. Then super-holons are grouped in their turn, and so on, to obtain a single and complete holarchy. The affinity measures, according to the applications objectives and simulation constraints, the compatibily of two holons to work together to a shared objective (inspired from [Rodriguez, 2005]). In this context affinity is exploited to dynamically aggregate holons to obtain a scheduling holarchy coherent with application objectives. A holon can thus change of super-holons during the simulation if its goals have evolved and thus impacted its affinity with other members. Affinity provides an easy mean to integrate application constraints in our model.

Each holon of this holarchy plays at least one role in the scheduling organization and one role corresponding to the behavior related to the application. If we have two or more independant application behaviors/roles to schedule at various levels, we have to dispose of one holarchy per role.

The behaviors related to the scheduling mechanisms are depicted in the RIO diagram shown in figure 1. The Scheduling organization defines five roles : The Scheduler role have to be played by a holon having and controlling its own computational resources (i.e. thread, computer . . . ). This role provides to its player the right to schedule 2 holons playing the role multilevelScheduler or Scheduled. The Scheduled role provides the right to schedule/execute its roles. The multilevelScheduler role have absolutely to be played by a superholon (composed). It represents a fusion of the two previous roles allowing its player to schedule its role and its members. This role also provides all required tools to dynamically determine if it is necessary to schedule its members or its application roles (cf. the section 4 on the next page). Environmental Reactor represents the environment and allowed other roles to add/remove holon body to the environment. Simulation's Controller is dedicated to the controls of the simulation and their graphical user interfaces if any.

2 Considering we use an organizational approach, executing a holon is modeled using an interaction between scheduler and scheduled where the first provides the computational resource to the second.

An example of a possible structure of the resulting scheduling holarchy is described in the figure 2. The lowest level of the holarchy represents the simulation most accurate level where each individual is modeled using an atomic holon. This level is commonly described as the microscopic level. Then the more we rise in the holarchy the more the application behavior is aggregated. The wide range of possible simulations levels is depicted in figure 3. The height of the holarchy depends on the affinity function that defines how holons are grouped, this holarchy is build from a dynamic bottom-up approach. Each new super-holons is associated with a behavior of a more aggregated level than its members. This mechanisms allows thus to simulate applications behaviors at several granularity levels.

4 A physics inspired evaluation of simulation accuracy

One of the main problems in MAS is the evaluation of the accuracy/efficiency of the system relatively to the task to perform and to the local mechanisms involved. Our measurements are designed by considering local and/or global characteristics such as individual holon goal, system's goal, and holons' and environmental dynamics. In order to tackle this issue, solutions have been developed in the literature taking inspiration from biology (fitness value), sociology (altruism) or physics (energy). Among the physics inspired measurements, the most widespread is entropy which value represents disorder/organization in the system. Several ways to compute entropy were proposed from the hierarchical social entropy [Balch, 2000] to the dynamic and static entropy [Parunak and Brueckner, 2001]. However, this kind of analysis has two main drawbacks. First, since it depends on the past transformations of the system, entropy cannot be considered as a state function (i.e. two identical system can be in a same state but with two different values for their entropy depending on their previous states). Second, entropy is mainly a global measurement that does not take into account local mechanisms of the system. In order to evaluate the accuracy of our multilevel simulation and to overcome these drawbacks, we have designed three measurements that are inspired by different energy values wide used in physics :

• Kinetic energy Eci : measurement linked to the dynamics (velocity) of the considered holon i.
• Goal potential energy Epgi : measurement linked to the individual goal to reach for holon i.
• Constraints potential energy Epci : measurement linked to interactions of holon i with other holons and with obstacles in environment.

These three measurements can be considered as state functions since they only depend on current parameters (velocity, position relatively to the individual goal, positions of obstacles/other holons, etc). Moreover, these measurements can be used whatever the level of the considered holon in the holarchy (microscopic, mesoscopic, macroscopic). The way to compute the various energies is dependent from the application, and will be detailed in the following sections (cf. section 5.2).

According to these three energies, we can define the global energy of a holon k by Ek = Eck +Epgk +Epck . This energy is characteristic of the current state of a holon and thus can be used to determine the deviation of the simulation accuracy between two adjacent levels. In that way, we introduce the notion of level similarity s, defined by :

with En i the energy of holon i of a level n and En+1 j the energy of its super-holon j (level n + 1). If the similarity is aiming toward zero, we can consider that the upper level consitutes a good estimate of the lower level. If the difference is increasing, it can be interpreted as a degradation of the upper level approximation. The similarity can thus be considered as a indicator of the quality of the approximation realized by a more aggretated behavioral level.

5 Application to real-time pedestrians simulation in urban environment

3D multiagent simulations of pedestrians (Human crowds) implies to simulate the motions of a large number of people while maintaining a reasonable frame rate. Multiagent Systems are a convenient way to simulate such behaviors at the finest level but it often requires a lot of computations and it is thus often difficult to maintain acceptable performances for the 3D visualization unless having important computational resources. This is a typical application where the complexity/realism of simulated behaviors have to be adapted according to simulation constraints, here available computational resources. We propose to adapt our holonic multilevel model to this case study and detail the instanciation of the previous physics-based indicators.

5.1 PedestrianModel

In this application, we are interested in simulating pedestrian navigation (virtual human) in urban environment, this kind of behavior is used in a wide range of applications : Escape panic, Urban Dynamics, Bus Network Validation. . .

We use an organizational model, so pedestrian behaviors are defined in terms of roles and interactions. The Pedestrian organization, depicted in figure 4, describes the three main roles involved in the simulation of pedestrian motion : Actor and Perceptor provide means to act, resp. perceive, in the urban environment (role Environment). Integration of the perceptions and computation of the motion according to holon objectives and environmental constraints (other holons and obstacles) are assured by the Pedestrian role.

In this application, we have choosen an hybrid approach : in the low levels of the holarchy the pedestrian behavior of a super-holon is the same of its members but perceptions/actions are aggregated, and then we use aggregate pedestrian behaviors.

Affinity between two pedestrians is defined according to three main functions : the distance between holon objectives, the distance between holon location, and the energetic affinity (cf. equation 2).

The two lowest levels of the resulting scheduling holarchy are shown in figure 5. Four pedestrians are grouped into a super-holons, if available computational resources are comfortable. The super-holon schedules its multilevelScheduler role and thus schedules its members, else it schedules its pedestrian behavior. All members play the Head role in the holonic organization of the holon 21, because they have all an equivalent part in the decision making process within their super-holon. Super-holon 21 (mesoscopic level 1) disposes of the same pedestrian behavior as its members but its perceptions correspond to an aggregation of its members perceptions. Its environmental body corresponds to a group of individual bodies. When a motion is computed, all members bodies are impacted by the same movement. Thus we exploit the self-similarity of the holon to reuse the same behavior at various levels, in this case a meso holon can be considered as a kind of elementary pedestrian boids. Aggregating perceptions and actions allows a significant reduction of computational costs while maintaining a relatively good simulation accuracy.

5.2 Instanciation of physics-based indicators

This section will introduce a physics-based evaluation of simulation accuracy for the case study of pedestrian simulation. Each pedestrian disposes at least of one objective (local and/or global). To model pedestrian behavior, we use a classical force model based on three main forces : a forward force (3) attracting the holon to its goal, and two repulsive forces from other holons (4) and the obstacles (5).

According to this force model, energy measurement can be detailled as follow :

• For kinetic energy, a standard expression is used. In the following equation, mi corresponds to the mass of agent

• Goal potential energy, Epgi for agent i, is computed using the general expression of the potential energy considering a conservative force :

with -→ du a unit vector in the direction of agent speed. Expression of the goal potential energy is given by equation 8.

• Constraints potential energy, Epci for agent i, is computed with the same principle as previous item.

5.3 Experimental Results and discussion

We have introduced a holonic multiagent model for multilevel simulation. First we have compared computational costs (in millisecond) between microscopic and mesoscopic simulation levels. Experimental results are presented in figure 6. These results confirm that mesoscopic approximation is effectively less expensive than the microscopic level. That validates rising in the scheduling holarchy implies a reduction of computational cost. So our model is able to adapt agent behavioral level according to simulation constraints, i.e computational cost. Then we can consider that mesoscopic level maintain a good approximation of pedestrian behavior because the difference between energy value (level similarity) is relatevily small and the animation of pedestrian navigating into the 3D world remains realistic compared to microscopic level. Finally using this model, we have succeeded to simulate on a quite performant computer 3 a reasonable number of agents with a good behavioral level while maintaining an acceptable 3D visualization : frame rate 18-23.

3 Pentium 4 2.40GHz, 512 Mo RAM, GeForce3 Ti 200

6 Conclusion and FutureWorks

In this paper, we have presented a holonic multi-agent scheduling model to enable multilevel simulation. To achieve that we exploit the hierarchical structure and scalable properties of the holarchy to assure a dynamical scheduling of the application's entities at various behavioral levels. The use of an organizational approach allows a modular and reusable model. This approach confirms that multiagent systems allow through multilevel mechanism to simulate complex systems while satisfying application dependent constraints, like realtime. This work is part of a larger effort to develop a whole holonic multiagent simulation platform. Further works will particularly deepen the study of levels' transition (micro ↔ meso). Based on our physics-based indicators, we will try to determine if and when it is really appropriate to change level, by trying to foresee at short terms the next states of a holon.