Individual Behavior Simulation Based on Grid Object and Agent Model

Abstract

For the simplicity of spatial modeling in Cellular Automaton (CA) and the complexity of vector spatial expression in the Multi-Agent System (MAS), the concept of grid object as the spatial model of individual behavior simulation was proposed with spatial information, semantic information, and connection relationship of geographic entity. Then, by incorporating the MAS, the method for individual behavior simulation with the Grid Object and Agent Model (GOAM) was demonstrated. Meanwhile, a prototype system including the three subsystems was developed based on the GOAM, and experiments were conducted for two cases in different spatial environments. The prototype system can be used to obtain grid object data with 3D model data, to compute and simulate the behavior of individuals, and to render individuals. The two cases involve goal-driven behavior in both indoor and outdoor environments as examples to evaluate the validity of the GOAM and to provide a reference for building individual behavior simulation with the GOAM in other scenarios.

1. Introduction

As positioning technology and wide applications of geographic information systems have advanced, increasing attention has been applied to individual behavior simulation in Geographical Information Science (GIS) [1,2]. The results of individual simulation must be both realistic and accurate, and to guarantee such results modeling the human, the environment, and the relationships between them using valid expressions, is import.

Methods for modeling the human with the individual are always a prominent topic in sociology and computer science. In these two fields, the two most commonly used models are the Cellular Automaton (CA) and the Multi-Agent System (MAS) [3,4,5]. By partitioning the environment using cellular spaces, CA can model individual behavior through simple transformational rules (e.g., moving an individual to a neighboring location that is closer to the individual’s goal in the next computation step). Because of its simple individual behavior rules, CA has been widely used in individual behavior simulation [5]. The agents in the MAS are capable of context-awareness and autonomous decision-making in spatial environments. Based on the agents, the MAS can model individual behavior through spatial relationship reasoning, environmental perception, cooperation, and so on [4]. Although much research has been performed on individual behavior modeling in sociology and computer science, research that includes environmental modeling, which is the basis of individual behavior, is still relatively rare. In individual behavior simulation systems (e.g., EXODUS, Simulex and Swarm) with CA [6,7], the environment is typically modeled using cells while a cell can represent only the spatial attributes of a specific region. In addition, the semantics of features such as a road or a room cannot be represented using a cell. In individual behavior simulation systems (e.g., RVO2 and OpenSteer) with MAS, the environment is typically modeled using vector data [8,9], and it is time-consuming rather to compute the individual behavior than with the cell.

Given this background, by combining GIS and MAS, a model named the Grid Object and Agent Model (GOAM) for individual behavior simulation is proposed in this paper. The definition of the GOAM, its construction methods, and a prototype system with GOAM are presented and used in two case studies described in detail. The goals of this paper are to improve the ability to simulate and analyze individual behaviors in GIS systems, to improve individual behavior simulation accuracy by introducing methods for modeling spatial environments in GIS, and to improve the effectiveness and reliability of individual behavior simulations.

2. Grid Object and Agent Model

2.1. Modeling Environment in Individual Behavior Simulation

The area occupied by an individual is typically important and cannot usually be ignored in micro-spatial environments because it affects the results, for example of computing of individual behaviors (e.g., extrusion, queuing) or the analysis of human-environment relationships (e.g., the number of individuals that a building can accommodate) [5]. With this, based on the modeling requirements of environments in individual behavior simulation, the concept of the grid is advanced first, and then the method of the modeling environment with the grid object is proposed in combination with the object-oriented model.

A grid can be regarded as an extended CA cell in spatial, which can be defined as a 2.5 dimensional raster cell that has a fixed size, corresponding to a spatial location and can be expressed using semantic information [10]. Mathematically, a grid can be expressed as follows: $Grid=(G_g,G_p)$, where $G_g$ denotes the geometric description of the grid and $G_p$ denotes the grid’s attributes. In the GOAM, the grid is regarded as the basic spatial unit of the human-environment relationship. The spatial area occupied by an individual at a specific time is a single grid or several grids. The environmental perception of an individual is also defined by the grid.

A grid object can be regarded as a combination of grids adjacent to each other that have the same semantic information, and it includes three types of information: geometric, semantic, and connectivity relationship.

The geometric representation of the grid object is divided into point grid object (CGPoint), line grid object (CGLine), and surface grid object (CGSurface), refer to the GIS spatial data model (Figure 1). A CGPoint object can be used to model a single independent geographic entity or to represent an individual’s spatial location at a specific time. A CGLine object and a CGSurface object both consist of multiple adjacent grids. The number of adjacent grids in the CGLine is less than two, and can be used to model linear geographic entities such as building exits or individual parameters such as the trajectory of an individual. A CGSurface object is the most common spatial morphology of individual simulation in micro-spatial environments (e.g., a room or a square).

The semantic information of the grid object is the non-spatial features descriptions of it and its contents are closely related to the requirements of individual behavior simulation. The description method can be same as the semantic representation in GIS spatial data, and the attribute domain can be restricted also.

Take the grid object as node (N), and the connectivity between grid objects as link (L), the connectivity relationship of the grid object is expressed with the graph (Figure 2). In this way, the unit of an individual’s environmental perception can be expanded from the grid to the whole spatial environment. Consequently, an individual gains the ability to cognize the surrounding space. In addition, the unit of individual behavior (e.g., routing) can be computed from grid to grid object using specific spatial relationships. In this way, computed individual behavior becomes more convenient and the results will be more credible.

The distance between two grid objects is not a fixed value, thus the distance weight of L is an interval. To enhance the efficiency of individual behavior simulation, the distance weight between the nodes can be pre-computed and the value can be stored as a link attribute (Figure 2). The distance between adjacent grids can be set to 1 in the horizontal direction and vertical direction and to 1.5 in the diagonal direction. The passing state of L can be divided into three types: passable, in which an individual can pass from one grid object (node) to another (node) directly; impassable, in which individuals are prohibited from crossing between two grid objects (nodes); and conditional (passable only under certain conditions), which means there are rules that govern passing between two grid objects. A passing rule can be defined as a combination of IF-THEN statements. For example, if the pass rule of a grid object is subject to a traffic light state, the conditional passing rule can be expressed as follows:

$$\begin{array}{l}IfT.state=redthenlin{k}_{ij}=Impassable;\\ IfT.state=Greenthenlin{k}_{ij}=Passable;\end{array}$$

in which $T$ denotes the traffic light, $T.state$ is the state of the traffic light, and $lin{k}_{ij}$ denotes the connection rules between the grid objects.

The procedure to obtain the grid object from the environment is: (1) Object partition based on the geometrics and semantics of the 3D model data input. (2) To obtain the grids that correspond to the geographic entities in the spatial environment. In this step, the conservative voxelization algorithm [11] is used first to compute the voxels that correspond to the geographic entities. Voxels that occupy the same size area in the horizontal direction and are adjacent to each other in the vertical direction are merged. The upper or under surface of the merged voxels forms the geometric information of a grid object. For areas inaccessible to individuals (e.g., indoor supports and outdoor traffic lights), the grid geometric information is the upper surface of the merged voxels, while for accessible areas, the grid geometric information is the under surface of the merged voxels. (3) To assign attribute values to each grid objects. The height of the merged voxels can be stored as an attribute value of the grid also. (4) To construct a network with the grid objects and to define the passing state and the distance weight of each link.

There is also a special kind of grid, boundary grid, in the grid object. A boundary grid can refer to two types of grids. The first is a grid to which several grid objects belong in space. The second is a grid to which only one grid object belongs and which is adjacent to another grid object in space. A boundary grid is a transition zone through which an individual moves from one grid object to another. Boundary grids play an important role in simulating individual behavior. When an individual enters a boundary grid, its behavior state may change. For example, when an individual enters a pedestrian crossing, its behavior state may change from “walking” to “wait” while the traffic light is red. The boundary grids can be searched based on a traversal of all the grid objects and grid objects adjacent to a boundary grid or that belong to it will be stored as attributes.

2.2. Modeling the Human in Individual Behavior Simulation

Based on the agent model in MAS, modeling the human in the GOAM involves three factors: an individual’s attributes, a method for environmental perception, and rules for the individual’s behavior.

Individual attributes are the set of characteristics encapsulated in the agent. Individual attributes include spatial location, physical attributes, and behavioral attributes. Individual physical attributes are those that distinguish an individual from others through appearance and physical parameters (e.g., age, gender, body weight, position, velocity). Individual’s behavioral attributes include both behavior states (e.g., waiting, walking, running) and behavior parameters (e.g., start position, target, response time to an emergency, familiarity with the spatial environment). In contrast to the traditional MAS model, an individual’s attributes in the GOAM are based on the grid object, which means that the individual’s position at any given time is a specific grid. The grid, the grid objects it located and the grid objects it is adjacent to can be obtained with the individual’s position also. Besides that, the motion parameter of individuals in the GOAM was given some limits. First, the speed of an individual was limited to a multiple of the grid size. That is, the distance over which an individual moves must be an integer multiple of the grid size. Consequently, the time division method during individual behavior simulation must be discretized also. That is, the computation time is not continuous but discretized in the GOAM.

Environmental perception is a dynamic process in which an individual observes the surrounding environment to obtain semantic information. Environmental perception includes two factors: static environmental perception and dynamic environmental perception. Based on the grid where an individual is located, the static environmental perception can be calculated using the distance between static geographic entities and the individual in 3D space, allowing an evaluation of whether a geographic entity can be perceived by that individual. There are two types of dynamic geographic entities in individual behavior simulation. One is emergencies (e.g., fire or bioterrorism), the impact of which can be computed using an emergency model using surface grid objects with a time parameter. When an individual perceives an emergency, it will respond according to its behavior rules. The other type of dynamic geographic entity involves other moving individuals in the space. Because individuals are in constant motion, but move at different speeds and directions, an individual’s perception of other moving individuals can be computed using their dynamic physical motion parameters [8]. The scope of an individual’s environment perception in the GOAM is also restricted to an integer multiple of the grid size.

An individual’s behavior rules form guidelines for that individual’s motion. The types of individual behaviors are diverse and include such factors as following behavior, obstacle avoidance behavior, aggregation behavior, and so forth. The diversity of individual behaviors is necessary for analyzing simulation because it allows the consideration of the behavioral characteristics of different individuals in different scenes. The main steps of constructing individual’s behavior rules in GOAM are: (1) Analyzing the behavior characteristics of each individual ($P$), and classifying their behavior states ($P_i$). For example, according to the characteristics of individual movement, individual behavior can be divided into $wait$ or $walk$; (2) Combining with environment modeling and individual behavior characteristics, the individual’s behavior rules can be designed by using IF-THEN statements [12].

$$IfT.state==red\mathrm{and}P.GridObject.Type!=Crosswalkthen{P}_i=wait$$

Besides that, because the environmental model in the GOAM includes three levels (grid, grid object, and grid object network), individual behavior rules in the GOAM are also constructed according to these three levels. This means that the individual behavior rules in the GOAM can also have hierarchical characteristics, which have a definite correspondence to the psychology of individual behavior [13,14].

2.3. Interactions between the Human and the Environment in the GOAM

The GOAM is an integration of human models with environment models as discussed in the two preceding sections (Figure 3), which means that the GOAM involves three aspects. First, the environment model consists of grid objects. Second, the human models are expressed through individuals and simulated with agents. Third, there are interactions between humans and environments. The primary GOAM equation is

$$GOAM=f(GridObjects,Agents)$$

where $GridObjects$ describe the environments and $Agents$ describe the humans. The function $f$ denotes the interaction between human and the environment. In addition, $f$ includes the concepts of two types of perception. One is the perception from the environment to the human ($GridObjects$ to $Agents$) and the other is the perception from the human to the environment ($Agents$ to $GridObjects$).

The perception of $GridObjects$ to $Agents$ can be accomplished either proactively or passively. Given the location of an individual, obtaining the attributes of the grid or grid object where that individual is located is the common method of proactive perception. Obtaining information about adjacent grid objects through spatial analysis (e.g., a buffer) is also a method of proactive perception. Passive perception can be accomplished by associating $GridObjects$ with a predefined field. When the value of the predefined field changes, the region of $GridObjects$ affected is computed first, and then, the individuals influenced can be searched using predefined rules. Finally, the message can be transmitted to specific individuals. An $Agents$ perception of $GridObjects$ occurs mainly through proactive spatial analysis in the GOAM, which means that the overlapping area is computed using the spatial locations of $GridObjects$ and $Agents$ at a specific time or over a period of time. If the overlapping area is not null, the $Agents$ can perceive the $GridObjects$.

2.4. Unified Modeling Language Class Diagram Graph of the GOAM

Based on a combination of modeling the environment, the human and the interactions between them, a Unified Modeling Language (UML) class diagram graph of the GOAM was designed (Figure 4).

The two main classes of the CSDM are CGridObject (

Table 1. The main attribute filed in the CGridObject.

Filed	Description
ID	The unique identifier for this grid object.
pGeometry	The set of grids contained in this object. Each grid contains the information listed of X (the row number of this grid), Y (the column number of this grid), Z (the elevation value of this grid), isBoundary (a Boolean value denoting whether this grid is a boundary grid), pBoundaryGridObject[] (when isBoundary is true, the list of grid objects adjacent to this grid), and pProp[] (other properties of this grid).
pLinkID[]	The set of other grid objects connected to this object, stored as an array.
pLinkType[]	The connection states of the arcs corresponding to pLinkID[]. The value of the connection state is either passable, impassable or conditional.
pLinkWeight[][]	The link distance weight corresponding to pLinkID[], stored in a hash table.
pProp[]	Other properties of this object, such as its name.

) and CAgent (

Table 2. The main attribute filed and method in CAgent.

Filed or Method	Description
ID	The unique identifier for this individual.
pRule[]	The sets of rules for the individual behavior.
pProp[]	The set of individual attributes.
queryEnvironment()	The method for environmental perception.
calRule()	The method to compute the behavior rules of the individual (See Section 3.1.).

), which represent the grid object to modeling the environment, the agent to modeling the human, respectively. The special topic classes (e.g., room (CRoom) and road (CRoad)) in the environment can be all derived from CGridObject while MAS (CMAS) can be modeled with multiple CAgent objects.

3. The Prototype System and Case Study with GOAM

By combining the developed prototype system and a set of parameters, two cases involving individuals in indoor buildings and outdoors on roads were investigated.

3.1. The Prototype System with GOAM

The prototype system developed using the GOAM is divided into three subsystems (Figure 5): (1) Grid object compute subsystem. The main function of this subsystem is to obtain grid object data for individual behavior simulation. The inputs to this subsystem are 3D model data (*.3ds or *.obj format from 3ds Max software) and the spatial relationships between geographic entities, while its outputs are the grid objects corresponding to the input data. The grid parameters for voxelization in the following two case studies were set to 0.5 m (length), * 0.5 m (width), * 0.2 m (height). (2) Individual behavior compute subsystem. The main function of this subsystem is to obtain individual behavior information with individual’s attributes, environmental perception, and the method to compute individual behavior rules. The input data to this subsystem are the grid objects and their individual behavior parameters. The output data of this subsystem are the individuals behavior information (individual’s attributes and the motion trajectories of each individual). (3) Individual behavior rendering subsystem. Based on the 3D rendering engine OpenSceneGraph (OSG) [15], the main function of this subsystem is to visualize individual behavior in a virtual geographical environment. The inputs to this subsystem visualize the spatial environment and the individuals behavior information.

Target-driven behavior, the most common individual behavior in daily life—meaning that the target location of an individual has been determined before the individual starts moving and does not change with the environment—was implemented in the prototype system as an example of behavior for computing individual behavior information. Two problems must be solved in the process of modeling target-driven behavior with multi-level analysis [16,17]. The first problem is how to reach the target. That is, how to choose the route according to the experience and preferences of the individual. This problem can be considered as one that involves modeling individual routing behavior. The second problem is how to model the motion behavior. That is, during the process of moving an individual, based on the individual’s dynamic environment perception, how to model the interactions between the individual and the environment and, thus, how to determine the moving direction in the current computation period. Given that both these problems must be solved, target-driven behavior in the GOAM is divided into two steps. The first step involves computing the individual’s routing behavior based on the grid objects network. The results of this step are the grid objects through which the individual passes. The second step is to compute the individual motion behavior in each grid object obtained in the first step. The result of this step is the grids through which the individual passes.

Set the grid object where an individual is located as $G_0$ and the results of the individual routing model as $G_R$. In the grid objects network, the main steps of the individual routing algorithm are as follows. (1) based on the starting position and the target location, the grid objects corresponding to $G_s$ and $G_g$ are computed, respectively. and then set $G_0$ = $G_s$. (2) Compare $G_0$ and $G_g$, if they are the same object, $G_0$ is pushed to $G_R$, and the routing is complete. (3) Obtain the next passable nodes $N$ from $G_0$ and their connection relationships from the grid objects network. (4) For every node $N_i$ in $N$, repeat step (2). (5) For every node $N_i$ in $N$, repeat step (3), obtaining the node set $NN$. For every node $N{N}_i$ in $NN$, the distance weight of the path composed of $G_0$ and $N_i$ is the minimum distance between $N_i$ and the grid set $N{N}_i$ (the grids belonging to $N_i$ and adjacent to $N{N}_i$). Using the distance weight, the individual’s path can be searched using the Dijkstra algorithmor the A* algorithm [18] until the individual reaches node $G_g$.

Based on the grid objects obtained in the individual routing behavior model and to analyze the force from other individuals and geographic entities to the individual in both a static environment and a dynamic environment, an individual motion behavior model consisting of a fused field model [19] and a social force model [20] is proposed in this paper. In a static environment, the forces an individual experiences mainly include driving forces ($F_a$) from moving targets, and repulsive forces ($F_b$) from obstacles in the individual’s path. In a dynamic environment, the force individuals experience is primarily the repulsive force ($F_c$) from other individuals in the individual’s path. All the forces ($F_a$, $F_b$ and $F_c$) can be obtained using the social force model. Together with the grid objects obtained through the individual routing behavior model, the sub-targets are divided to calculate $F_a$ (each grid object can be considered as a sub-target), which make the social model more amenable to complex spatial environments. In addition, the obstacles in $F_b$ can be obtained from the impassable arcs linked to the grid object where each individual is located. The individuals involved in calculating $F_c$ can be obtained using two steps. The first is to obtain the grids adjacent to the grid where the individual is located, and then the individuals located in those adjacent grids can be obtained dynamically. Based on the forces ($F_a$, $F_b$ and $F_c$) acting on an individual, that individual’s direction of movement and speed can be calculated using the social force model. Then, the individual’s position can be updated to its adjacent eight grids (or simply remain in place according to the field model) with a biased random walk model with no back step.

3.2. Case 1: Individual Behavior Simulation in a Multi-Story Building

The spatial environment of Case 1 was a two story, single exit, double-staircase building (Figure 6a). The grid objects were divided into three types: stairs, rooms, and an exit, and the grid object connectivity relationship was defined as shown in Figure 6b.

The initial positions of individuals in Case 1 were set randomly throughout the 2nd floor. The behavior of individuals was all set to move from their initial positions to the exit along the shortest-distance path (Figure 7). That is, within the connectivity relationship of grid objects, the grid objects an individual would pass were searched by distance weight first, then the grids in each searched grid object were calculated using the social force model, and, finally, the grids obtained formed the routes along which the individuals walked.

During individual behavior simulation, if an emergency (e.g., fire or bioterrorism) were to occur, the individual behavior may change because of the influence from the emergency. If an individual perceives a sudden event, that individual may change his or her original walking path to avoid the risk. In contrast, if an individual does not perceive the emergency, that individual may get injured from contact with the results of the emergency. In this paper, an aerosol-borne pathogen release [21] was used as an emergency, and the Gaussian cluster model was used as the pathogen diffusion model (Figure 8). In this case, the simulation of an individual’s behavior was conducted as follows: (1) the dynamic diffusion region $S$ of the pathogen was calculated, and the corresponding grids $G$ obtained; (2) for individuals who can perceive the emergency, the grid objects that the individual would pass are recalculated. In addition, $G$ was regarded as a set of obstacles in the social force model; (3) individuals who are not aware of the emergency will continue moving toward the exit along their original path, and the awareness (infection situation) of an individual can be judged based on the grids through which that individual is moving.

3.3. Case 2: Individual Behavior Simulation on the Outdoors Road

The spatial environment of Case 2 consists of two longitudinal sidewalks, a longitudinal roadway, a pedestrian crossing, and two traffic lights, one on each side of the pedestrian crossing (the time interval between red and green is 30 s) as shown in Figure 9a. The grid objects were divided into four types: sidewalks, the roadway, the pedestrian crossing and the traffic lights. Combined with the road segmentation methods in the GIS road networks [18], the grid objects that contain multiple nonadjacent geometric information were divided into sub-objects. The grid object connectivity relationship was then set as shown in Figure 9b.

The initial positions of the individuals in Case 2 were set randomly along the sidewalks. The behavior of individuals was all set to move from their initial positions to the opposite sidewalk, which involved crossing the road. However, in Case 2, individual behavior was affected by the traffic rules. Based on whether they obey the traffic rules, the individuals’ behaviors can be divided into three categories (Figure 10). Under Rule 1, individuals will observe the traffic rules, crossing the road only at the pedestrian crossing and reaching the opposite sidewalk only when the traffic light is green. Under Rule 2, individuals do not observe the traffic lights; they will cross the pedestrian crossing even if the traffic light is red. Finally, under Rule 3, individuals will choose the shortest path to reach their goal. That is, the individual may reach the target without using the pedestrian crossing. For Rules 1 and 2, individuals must pass through the pedestrian crossing, but only under Rule 1 does the traffic light influence individual behavior, determining whether individuals wait or walk.

4. Conclusions

Using GIS and MAS combined with human and environmental characteristics in micro-spatial environments, a GOAM-based individual behavior simulation was proposed in this paper. The advantage of the GOAM is that because the GIS spatial data model is introduced first, the GOAM has the potential to model human behavior in complex geographic environments. In addition, by incorporating the MAS, the individuals in the GOAM are able to perceive geographic entities and the spatial relationships between those entities, which not only improve the fidelity and effectiveness of individual behavior simulation but also lay a foundation for integrating individual behavior simulation with complex geospatial modeling. In the method used for spatial division in the GOAM, the basic spatial unit (the grid) is similar to that of CA (the cell). However, the GOAM incorporates additional information and enhancements that improve the authenticity of individuals’ behaviors, the interactions between individuals, and the integrated analysis and expression of individual and spatial environments. This paper also provided a detailed description of the individual behavior simulation prototype system developed based on the GOAM and presented two cases involving different scenarios that can serve as references for GOAM-based individual behavior simulation in other scenarios.

Based on the GOAM, the individual behavior simulation cases in this paper were limited to individuals who have a specific target to which they move. The individual behaviors are complex, uncertain and dynamic. As individuals move, they may change their target due to changes in the environment or due to interactions among individuals. Individuals may also exhibit irrational behavior in non-conventional environments [5]. These behaviors can be extended using the GOAM by defining more complex behavior rules; however, the way in which these are extended needs further study in the future. Another area for future study involves implementing the GOAM using parallel computing techniques, which would accelerate the speed of individual behavior simulation in large or complex scenes.