-In this paper we present an extension of an agentbased model representing pedestrian dynamics in order to include elements related to activity scheduling and the management of events. In particular, we will focus on the guidelines to analyze the scenario, identifying activities and the temporal relationships among them, such as how events that happen in an environment and change its configuration can be represented by means of the operational model and how the decision process of agents is influenced by them. An analysis of modeling activities in a real-word case scenario will be presented.
Crowding phenomena are an interesting topic traditionally
studied in the context of human sciences (e.g. Sociology and
Anthropology [
Considering the works which can be found in the
literature, a part of the models are devoted to the description
of pedestrian behavior focusing on walking process, taking
into account the interactions with other pedestrians and with
obstacles. All these information belong to the so-called
operational level [
Sometimes, strategic and tactical levels are considered to be exogenous to the pedestrian simulation. For these reasons the majority of the models in the literature just point out the operational level or the tactical and strategical level: in fact, it is very difficult to develop and to validate a comprehensive model considering all the three levels.
Related to the tactical and strategical levels there are a
lot of dedicated theories and models describing pedestrian
route choice: the main question is which are and in which
order pedestrians perform activities. In order to reach this
scope, the majority of the models works considering network
decision analysis in which pedestrians can make decisions
about where to move, applying basic discrete choice modeling
and determining a finite number of routes through the walking
infrastructures [
More similar to our model, in [
In this paper we want to present an ongoing work about the extension of an agent-based model for the simulation of pedestrian dynamics, based on CA-method for the management of the environment, in order to include some elements of the tactical level starting from a model developed for the operational level. Considering the complexity of dealing with tactical level, in this work we just want to point out some guidelines to start modeling activities, by means of an analysis of the scenario, identifying activities and the temporal relationships among them (if any), such as how events that happen in an environment and change its configuration can be represented by means of the operational model and how they influence the decision process of agents. Our assumption is that every agent has its own route and that events can change the schedule of activities and can influence the decision of the agents during the simulation.
The paper is organized as follows: first, the basic elements of the model are presented (Sec.II), in order to introduce how the operational level works (Sec. III). Then, the extension of the model to include the schedule of activities is presented (Sec. IV). The paper ends with an application about modeling activity scheduling to a real word scenario (Sec. V) and indications about future works (Sec. VI).
The environment is modeling in a discrete way both in space and time.
1) Space: The physical environment is represented with a
discrete grid of square cells with cell size of 40cm 40cm
(according to literature [
Env = fc0; c1; c2; c3; :::g
Every cell has a row and a column index, which indicates its position in the grid.
Every cell is linked with other cells, that are considered its neighbors. In the basic model we assume the Moore neighborhood, all the cells surrounding the cell being considered, even in diagonal directions.
Every cell can be in three possible states: free, occupied by an obstacle, or occupied by a pedestrian. In this third case the cell contains also a reference to the specific pedestrian occupying it.
State(c) = s : s 2 fF ree; Obstacle; P edestrianig
2) Floor fields as virtual grids: Following the approach
of the floor field model [
All these fields can be seen as grids identical to the environment grid, and we define a function that extract the value of the field for the given cell:
Val (f; c) : F ield
P athFj;k = V al(P athF; c) ObsFj;k = V al(ObsF; c)
DensFj;k = V al(DensF; c) where c 2 Env ^ (Row(c) = j) ^ (Col(c) = k). 3) Spatial markers: Space can be annotated at design-time with different markers, that are a set of cells that have the function of assigning particular roles for these cells.
The main kinds of marker conceived for the model are the following: start area, cells where pedestrian are generated, all at once (en-bloc generation) or with a certain frequency distribution. A start area contains also information on the kind of pedestrians it must be generated and the probability to assign the routes they must follow; destination area, places where pedestrians want to go, either final or intermediate; obstacle area, non-walkable cells that represent obstacles and walls.
Each destination is associated to a path field indicating (as a discrete version of a gradient) the shortest path between each cell in the environment and this (intermediate) destination. An example of the use of path field is shown in Fig. 2. Fig. 2: Path fields in a simple scenario of a linear corridor with two exits. Figures show respectively the path field associated to the exit on left and to the exit one right. Cells in red represent obstacles, while cells in blue represent destination areas 4) Time: Time is discrete, divided into steps of equal duration. We chose to set the maximum velocity of a pedestrian to 1 cell per step so, given that the size of the cell 40cm 40cm, we can calculate the duration of the single time-step in terms of seconds, given the fact that average pedestrian velocity measured empirically is about 1:2m=s. According to these assumptions, we have a ratio of 3 steps=second.
The pedestrian of the basic model is fundamentally an utility-based agent with state. Functions are defined for utility calculation and action choice, and rules are defined for statechange. Pedestrians have associated, in addition to their identifier, the route they must follow according to the initialization of the simulation, the identifier of the group they belong to, and their state.
The state of the pedestrian is composed of different variables:
Position is the cell where the agent is on, oldDirection is the last chosen action, routeIndex indicates the current goal on the route, and attitude indicates the motivational state of the agent (e.g. normal, hurry, panic and so on). From this state components we can derive the current path field and the weights for the utility function that allow to choose the next movement of an agent in the simulation: currentP athF ield = P athF ields(routerouteIndex) weights = W eights(attitude)
The decision of what happens when an agent arrives at the final destination or complete one activities is not a destination task: it is the agent that decides what to do (i.e. if it must disappear, it can reappear in another place, it can choose which is the next activity according to its route ).
1) Agent actions: Possible actions (A) are movements in one of the eight neighbor cells (indicated as cardinal points), plus the action of remaining in the same cell (indicated by an ‘X’):
A = fN; S; W; E; N E; SE; N W; SW; X g Usually, just a subset of actions are admissible because agents can move only in the cells that are free at the moment in which it is update. The chosen cell becomes an “occupied by pedestrian” cell while the old cell becomes free. Moreover, the effect of an action is to update the density field by reducing density in the surroundings of the previous cell and increasing it in the surroundings of the chosen cell.
As introduced in Section I, we now show the modeling of pedestrian dynamics considering first the operation level in which walking behavior respect to the environment is described. In our model agents work in a fundamentally utilitybased way considering operational level: at each time-step t agents choose their next action ai by evaluating the utility of all admissible actions.
Agents assign a desirability value to each of the possible actions, based on five influencing factors: the floor field value (G), indicating the path to the goal, the obstacles field value (O), indicating the presence of obstacles, the proxemic separation value (S), indicating if there are other pedestrians near the agent, the group cohesion value (Co), indicating the presence of the other components of the group (if any) and the direction value (D), that indicates if the next direction is the one adopted for the previous movement.
The utility of a destination cell (which corresponds to an action/direction) is the weighted sum of all these factors (this allows also having different types of pedestrian, or even different states of the same pedestrian, changing dynamically its weights): kgG(c) + koO(c) + ksS(c) + kcoCo(c) + kdD(c) d where d is the distance of the new cell from the current position (1 or p2) for diagonal cells.
Given the list of possible actions (that in the basic model correspond to possible movement directions), two strategies are implemented to choose the next action: deterministic behavior, in which action with the higher probability is always chosen, and stochastic weighted behavior, in which an action is randomly chosen with a probability that is function of utility. In particular, the probability of choosing an action a is given by the exponential of the utility, normalized on all the possible actions pedestrian can take in the current turn:
p(a) = N eU(c) where N is the normalization factor and c = a(currentCell) is the cell chosen according to action a.
Several turns of simulations for calibration of utility
function parameters such as for validation of the model with data
from real experiments and literature were conducted and the
outputs fit with other results and information presented in the
pedestrian dynamics literature. A complete overview about
calibration and validation phases is out of the scope of this
paper, see [
DEFINITION OF TACTICAL LEVEL
In this section we introduce an extension of the basic elements presented in Sec. II in order to expand the model from the operational level to the tactical level. The extension of the model is an ongoing-work, with the scope to improve the basic model allowing the representation and the simulation of more complex scenario in which the behavior of pedestrians can be influenced by schedule of activities such as the presence of events.
Modeling activities is a complex task that needs an analysis of the scenario in order to identify activities, and an analysis of the constraints among activities and the relationships between activities and the environment. In the follows we point out all the phases that are necessary for the definition of tactical level.
As written above, scheduling of activities requires an analysis of the environment of the simulation in order to identify all the relevant activities that have to be modeled in the particular scenario. Every scenario has a set of activities ACT = fact1; : : : ; actng where every acti is an activity that can be performed by agents.
It is necessary to consider that some activities can be mandatory for pedestrians to reach their final destination (e.g., to buy a ticket and to pass through turnstiles in the scenario of a station) while other activities can be optional (e.g., to buy something to drink or to eat). On the basis of the time-table of the simulation and on the changing in the scenario by means of events presence, it could happen that an optional activity was not performed.
In order to model these features, we define every activity as acti(mandi) where mandi 2 N : mandi 2 [0; 1]: mandi = 1 if an activity is mandatory, mandi = 0 if it is optional.
After the identification of all the relevant activities that can be performed in a scenario, it could be necessary to model temporal relationships among them: some activities have to be done following a precise temporal order while others can be done in concurrency. A way to try to model all the activities and the relationships among them is to use an UML activity diagram, in which the flow of activities is represented by oriented edges which indicates the temporal sequence. In addition to activities, the other main components allow the representation of starting and ending point such as fork and join of activities that can be performed in parallel.
After the modeling of the relevant activities in the scenario, it is necessary to take into account the spatial connection among them. In fact, every activity is located in a portion of the environment in which the simulation will take place: the evaluation of spatial connections is essential in order to build and initialize the routes followed by agents.
Starting from the activity diagram, the main idea is to build a graph of the environment identifying nodes and edges. More formally, we can design a finite graph of the environment G : hV; Ei where V is a set of vertices (nodes) and E V V is a set of edges. Two vertices are called adjacent if they share a common edge, in which case the common edge is said to join the two vertices. An edge and a vertex on that edge are called incident. A walk is an alternating sequence of vertices and edges, beginning and ending with a vertex, where each vertex is incident to both the edge that precedes it and the edge that follows it in the sequence, and where the vertices that precede and follow an edge are the end vertices of that edge. A walk is closed if its first and last vertices are the same, and open if they are different. The length l of a walk is the number of edges that it uses (open walk: l = jnodesj 1, closed walk l = jnodesj). Traditionally, with the term path is indicated a “simple” walk, meaning that no vertices (and thus no edges) are repeated.
For our scope, every node represents an activity (and the spatial area in which it has to be performed) and every edge represents the spatial connection between activity areas: two spatial areas are directly connected iff an edge exists between them. The edges in our graph are oriented, in order to model temporal orders: in fact, the graph of the environment is building taking into account all the information related to concurrency and temporal relationships expressed by activity diagram. We are also interested in the study of open paths (not walks) starting from starting areas and ending with final destinations, as modeled in the activity diagram. For this reason, the dimension of the graph in terms of nodes is equal to jV j = jactivityj + jstartpointj. Considering edges, it is necessary to model all the allowed spatial relationships among activities, in order to build all the possible spatial paths in the environment.
Considering the definition of nodes as activities, we define a set P = fp1; : : : ; png including all allowed paths, and every path is defined as a list of activities pi = hact1; : : : ; actmi. The set P can be obtained by an analysis of the scenario and by a survey in which collected data allow to understand the behavior of pedestrians in terms of activity scheduling and routes, try to establish the probability that a pedestrian will follow a particular route in the simulation. For this reason we assign to every path pi a probability P r i.e., the probability that an agent assumes that path as its own in the simulation. In particular, this probability is obtained as the composition of the probabilities of all the activities which pi is composed of, that are independent and consistent events:
P r(pi) = P r(act1) : : : P r(actm) = m Y P r(acti) i=1
Events are something that happen in the environment and that can modify the scenario and the pedestrian activities. We introduce in the model a new kind of floor field, the event field, that is dynamics and that shares information about some event happened in the scenario. The event floor field expands information related to the event and, if an activity is involved in the definition of the event (e.g. a train is leaving the station, some emergency situation happens), a priority flag for this activity is shared in the environment and it can be perceived by agents.
Moreover, the event floor field shares a value valueattitude 2 N that can change the attitude of pedestrians. Sometimes, events modify the motivational state of pedestrians (i.e. the attitude of agents): considering the scenario of a station in which a train is leaving, pedestrians could modify their attitude being hurry respect to the normal situation. It is also possible to model panic or emergency situation, changing the attitude of pedestrians and notifying that exits or safety points have priority respect to the current schedule. According to the definition of pedestrians (Sec. II-B) the attitude modifies the weights considered in the calculation of the utility function that allow to choose the next movement of an agent in the simulation. In particular, we define a maximum valueattitude that is used to model emergency or panic situation:in this way, the activity notified becomes a mandatory destination, even if it is not included in the agent path.
In conclusion, we can indicate with the function emit(acti; valueattitude) the information shared by means of event floor field in the environment that agents can perceive by means of event floor field.
In this section we show how the schedule of activities is influenced by events and how agents can change their own schedule on the basis of event perceptions and also considering that, at the beginning of the simulation, every agent has a route to follow that is assigned by the starting area according to a given probability.
1) Schedule Without Event Perception: The way in which agents perform their activity list depends on the situation (the presence of events): in general, every agent has just to perform the activity list that has in its mind. Agent starts with the first activity in the list and reaches this (intermediate) destination according to the corresponding path field (currentP athF ield = P athF ields(act1)). Then, agent checks which is the next activity in the list and starts to follow the new path field (currentP athF ield = P athF ields(act2)). The turn of the simulation ends when the agent performed all the activities in its list (currentP athF ield = P athF ields(actm)). Activity diagram in Fig. 3 shows overall process of activity schedule in the without event case. This simple behavior changes if some event happens in the environment.
2) Schedule With Event Perception: Starting from the simple scenario without events, different situations have to be analyzed in order to understand the scheduling of activities in complex cases. An overview of the decision process of agents in the case of event perception is shown in Fig. 4a. Note that the activity diagram refers only to the process associated to the management of a notified event, and it is a part of the simulation cycle of every agent.
When an agent perceives information related to an event, it first checks the value of attitude: if it corresponds to the maximum valueattitude, the activity notified becomes a mandatory destination, even if it is not included in the agent path. If the valueattitude is not the maximum, it is necessary to verify if the activity is part of the agent list of activities: agent only considers the notification if the activity is part of its path. In this case, a rescheduling of the activity list is necessary.
3) Reschedule of Activities: In the case in which a reschedule of activities is necessary, a more complex behaviour is expected from the agent. If the current activity is the notified activity, agent just completes the activity and then, eventually, (a) (b) continues the normal schedule. Differently, if the agent is occupied to reach another destination, if it is mandatory agent completes the current activity else it considers next activity in the list, until the latter is equal to the notified activity. Fig. 4b shows the activity diagram representing the process of reschedule of activities.
V. CASE STUDY: MODELING ACTIVITIES IN THE CONTEXT
OF CRYSTALS PROJECT
In this section we introduce a real scenario in which modeling activities is an important step in order to understand and to express the management of the pedestrian flows: we apply the extension of the basic model to the Arafat I station, on the Mashaer Rail line, in the context of the CRYSTALS project1, a joint research effort between the Complex Systems and Artificial Intelligence research center of the University of Milano–Bicocca, the Centre of Research Excellence in Hajj and Omrah and the Research Center for Advanced Science and Technology of the University of Tokyo, with the main aim of supporting designers and organizers involved in the management of Hajj, the annual pilgrimage to Mecca. More in detail, we focus on the identification of the activities by means of the analysis of the scenario and on the building of the graph of the environment. Due to the particular constraints in the management of pedestrian flow in this scenario (see below) no events are hereby presented.
The goal of building Mashaer Rail line is to reduce the congestion caused by the presence of other collective means of pilgrim transportation (i.e. buses) during the Hajj: the yearly pilgrimage to Mecca that involves over 2 millions of people coming from over 150 countries and some of its phase often result in congestion of massive proportions. For this reason, it is necessary that the management of the pilgrim flow is under control during the process of entry the station. The size of the platforms was determined to allow hosting in a safe 1http://www.csai.disco.unimib.it/CSAI/CRYSTALS/ and comfortable way a number of pilgrims also exceeding the potential number of passengers of a whole train. Each train is made up of 12 wagons, each able to carry 250 passengers for a total of approximately 3000 persons. In order to achieve an organized and manageable flow of people from outside the station area to the platforms, the departure process was structured around the idea of waitingboxes (WB): pilgrims are subdivided into groups of about 250 persons that are led by specific leaders (generally carrying a pole with signs supporting group identification). The groups start from the tents area and flow into these fenced queuing areas located in immediately outside the station, between the access ramps. Groups of pilgrims wait in these areas for an authorization by the station agents to move towards the ramps (R) or elevators (E). In this way, it is possible to stop the flow of pilgrims whenever the number of persons on the platforms (or on their way to reach it using the ramps or elevators) is equal to the train capacity, supporting thus a smooth boarding operation. The inner station is organized into two parts: an initial waiting area (WAR) for people coming from elevators and ramps, and a boarding area (BA), one for every carriage (C). See Fig. 5 for a complete overview on the scenario.
Previous studies support the requirement of strictly organizing pedestrian flow, underlining that unexpected and anomaly situations can produce a noticeably worse performance not only from the perspective of the size of the area characterized by a medium-high space utilization, but also from the perspective of the highest value of space utilization of the environment. According to these results, the management of the movement of group of pilgrims from the tents area to the ramps should try to avoid exceptions to the waiting box principle as much as possible.
We apply our guidelines for modeling activities to this scenario identifying first the set of activities performed by pedestrians: actually, the majority of the them are timedependent (i.e. an order to execute activities exists and has to respected) and they are all mandatory, in the sense that it is (a) (b) not possible to skip any activity. The first step was the analysis of the scenario (see Fig. 5a), the identification of activities (see Fig. 5b) and the analysis of temporal-order relationships, by means of the building of UML activity diagram (see Fig. 6a).
Fig. 6b shows the graph related to the scenario of Arafat I station: note that the number of nodes is equal to the sum between the number of activities and the number of starting area. Moreover, the probabilities for every route is obtained as a product among the probabilities of single activity. According to the analysis of the scenario, P r(W B1) = P r(W B1) = P r(W B1) = 33%, P r(W AR) = 100%, P r(R1) = 90%, P r(E1) = 10%, P r(BA1) = P r(BA2) = 50%, P r(C1) = P r(C2) = 100%. From these values and according to the UML activity diagram, we obtain that there are 12 allowed (a) UML activity diagram (b) Graph of the environment Fig. 6: Activity diagram and graph of the environment, with all the allowed routes and the relative probabilities routes and that 6 of them have the probability value equal to 15% (obtained as P r(W B) P r(R1) P r(W AR) P r(BA) P r(C)) while the others have the probability value equal to 1:5% (obtained as P r(W B) P r(E1) P r(W AR) P r(BA) P r(C)).
This is an ongoing work in which an extension of the basic elements of an agent-based model for pedestrian dynamics modeling and simulation is presented. Next steps are related to the inclusion of temporal duration of activities, in order to model the time spending, an element necessary to build more realistic and complex simulation. Another part of the work will be devoted to the modeling activities for pedestrian groups.
Moreover, an implementation of this model is necessary to
test the model: while the operational level is already been
developed [