-This paper presents a hybrid agent architecture for modeling different types of decisions in a pedestrian simulation system. In particular, the present work focuses on tactical level decisions that are essentially related to the choice of a route to follow in an environment comprising several rooms connected by openings. These decisions are then enacted at the operational level by mean of a floor-field based model, in a discrete simulation approach. The described model allows the agent taking decisions based on a static a-priori knowledge of the environment and dynamic perceivable information on the current level of crowdedness of visible path alternatives. The paper presents the model formally, motivating the adopted choices with reference to the relevant state of the art. The model is also experimented in benchmark scenarios showing the adequacy in providing adaptiveness to the contextual situation.
The simulation of complex systems is one of the most
successful areas of application of agent-based approaches:
even though models, mechanisms and technologies adopted
by researchers in different disciplines are not necessarily
upto-date or in line with the most current results in the computer
science and engineering area about agent technologies [
The simulation of pedestrians and crowds is an example
of already established yet lively research context: both the
automated analysis and the synthesis of pedestrian and crowd
behaviour, as well as attempts to integrate these
complementary and activities [
Even if we only consider choices and actions related to
walking, modelling human decision making activities and
actions is a complicated issue: different types of decisions are
taken at different levels of abstraction, from path planning
to the regulation of distance from other pedestrians and
obstacles present in the environment. Moreover, the measure of
success and validity of a model is definitely not the optimality
with respect to some cost function, as in robotics, but the
plausibility, the adherence to data that can be acquired by
means of observations or experiments. Putting together tactical
and operational level decisions, often adopting different
approaches (typically behaviour-based for operational decisions,
and at knowledge level for tactical ones) in a comprehensive
framework preserving and extending the validity that, thanks
to recent extensive observations and analyses (see, e.g., [
This paper presents a hybrid agent architecture for modeling different types of decisions in a pedestrian simulation system. In particular, the present work focuses on tactical level decisions that are essentially related to the choice of a route to follow in an environment comprising several rooms connected by openings. These decisions are then enacted at the operational level by mean of a floor-field based model, in a discrete simulation approach. The described model that integrates within an organised and comprehensive framework different spatial representations, types of knowledge and decision making mechanisms, allows the agent taking decisions based on a static a-priori knowledge of the environment and dynamic perceivable information on the current level of crowdedness of visible path alternatives.
The paper presents the relevant state of the art in the following Section. The tactical level part of the model is formally presented in Section III-B whereas its experimental application in benchmark scenarios showing the adequacy in providing adaptiveness to the contextual situation is given in Section IV.
The research on pedestrian dynamics is basically growing
on two lines. On the analysis side, literature is producing
methods for an automatic extraction of pedestrian trajectories
(e.g. [
[
The tactical level has gained interest only recently in the
literature of pedestrian dynamics modeling and simulation,
despite its relevance for the simulation of a realistic behavior
(especially by thinking to evacuation situations). Path planning
algorithms have been widely investigated and proposed in the
field of computer graphics and gaming by means of
graphbased methods (e.g. [
On the pedestrian dynamics side, a relevant recent work is
the one from [
Most of the literature has been focussed on the reproduction
of the physics of the system, so on the lowest level, where a
significant knowledge on the fundamental diagram achieved
with different set of experiments and in different environment
settings (see, e.g, [
Literature of this level can be classified regarding the scope
of the modeling approach. Macroscopic models describe the
earliest approach to pedestrian modeling, basing on analogies
between behavior of dense crowds and kinetic gas [
The microscopic approach is as well categorized in two
classes describing the representation of space and movement:
continuous models simulate the dynamics by means of a
forcebased approach, which finds its basis on the well-known social
force model by [
The usage of a discrete environment is mostly employed by
the cellular automata (CA) based models, and describes a less A. A Cognitive Representation of the Environment for Static
precise approach in the reproduction of individuals trajectories Tactical Choices
that, on the other side, is significantly more efficient and
still able to reproduce realistic aggregated data. This class
derives from vehicular modeling and some models are direct
adaptations of traffic ones, describing the dynamics with ad
hoc rules (e.g. [
The framework that enables agents to perform choices on
their plan implies a graph-like, topological, representation of
the walkable space, whose calculation is defined in [
The environment abstraction identifies regions (e.g. a room)
as node of the labeled graph and openings (e.g. a door) as
edges. This so-called cognitive map is computed starting from
the information of the simulation scenario, provided by the
1A similar classification can be found in vehicular traffic modeling
from [
The cognitive map is defined as a graph CM = (V, E ) generated with a procedure included to the floor field diffusion, starting from the statements that each user-defined opening generates a floor field from its cells and spread only in the regions that it connects, and that each region has a flag indicating its properties among its cells. The floor fields diffusion procedure iteratively adds to CM the couple of nodes found in the diffusion (duplicates are avoided) and labeled with the region id and the edge labeled with the id of the opening.
Each final destination , different from the normal openings since it resides in only one region, will compose an edge linking the region to a special node describing the external universe. Intermediate targets will be mapped as attributes of its region node. An example of environment together with the resulting cognitive map is presented in Fig. 1.
To allow the calculation of the paths tree, that will be described in the following section, functions Op(ρ) and Dist(ω1, ω2) are introduced describing respectively: the set of openings accessible from the region ρ2 and the distance between two openings linking the same arbitrary region. While the first one is trivial and outputs the edges linking ρ, the function Dist(ω1, ω2) describes the distance that will be perceived by agents for their path planning calculation. To obtain a scalar from the sets of cells associated to ω1 and ω2, the value of the floor field in their center cell is used, defined as:
Center(ω) = P xi , P yi , (xi, yi) ∈ ω.
|ω| |ω|
The distance between ω1 and ω2 is then calculated as the average between the floor field values in the two center cells, i.e., the value of the floor field of ω1 in Center(ω2) and viceversa.
B. Modeling Adaptive Tactical Decisions with A Paths Tree
To enhance the route choice and enable dynamical, adaptive, decisions of the agents in a efficient way, a new data structure has been introduced, containing information about the cost of plausible paths towards the exit from each region of the scenario.
Using the well-known Floyd-Warshall algorithm, in fact, can solve the problem but introduces issues in computational time: the introduction of dynamical elements in the paths cost computation (i.e. congested paths) implies a re-computation of the cost matrix underlying the algorithm every step. More in details, the penalty of a congested path is a subjective element for the agents, since they are walking with different desired velocities, thus the calculation cost increases also with the number of agents.
The approach here proposed implies an off-line calculation of the data-structure that we called paths tree, but is computationally efficient during the simulation and provides to the agents direct information about the travel times describing each path. The method is described in the following paragraphs.
1) The Paths Tree: We define the Paths Tree as a tree data-structure containing the set of “rational” paths towards a destination, that will be its root. Before describing what we mean with the attribute rational, that can be seen as a fuzzy concept, a general definition of path must be provided.
A path is defined as a finite sequence of openings X → Y → . . . → Z where the last element represents the final destination. It is easy to understand that not every sequence of openings represents a path that is walkable by an agent.
Firstly, a path must be a sequence of consecutive oriented openings regarding the physical space.
Definition III.1 (Oriented opening). Let E = R1, R2 be a opening linking the regions R1 and R2, (R1, E, R2) and (R2, E, R1) define the oriented representations of E.
An oriented opening will therefore describe a path from an arbitrary position of the first region towards the second one.
Definition III.2 (Valid path). let C a sequence of oriented openings X → . . . → Z. C is a valid path if and only if: • |C| = 1 • |C| = 2 : by assuming C = X− > Y , the third element of the triple X must be equal to the first element of Y • |C| > 2: each sub-sequence S of consecutive openings in C where |S| = 2 must be a valid path.
The last oriented opening in the path leads to the universe region.
Given a set of paths, the agent will consider only complete paths towards its goal, starting from the region where the agent is located.
Definition III.3 (Start and Destination of a path). Given p a path (R1, E, Rx) → ... → (Ry, O, universe), the function RS(p) = R1 will return the region R1 where an agent can start the path p. S(p) = E and D(p) = p will respectively return the first opening ( E) and the destination (O) of the path. Definition III.4. Let p a path, T(p) is the function which return the expected travel time from the first opening to the destination.
T (p) =
X i∈[1,|p|−1]
Dist(openingi, openingi+1) speed (1)
Another basic rule is that a path must be loop-free: by assuming the aim to minimize the time to reach the destination, a plan passing through a certain opening more than once would be not rational.
Definition III.5 (opening loop constraint). A path X → . . . → Z must not contain duplicated openings.
This will not imply that an agent cannot go through a certain opening more than once during the simulation, but this will happen only with a change of the agent plan.
By assuming to have only convex regions in the simulated space, we could easily achieve the set of rational paths by extending III.5 as to let a path not containing duplicated regions. However, since the definition of region describes also rooms, concave regions must be considered. Some paths may, thus, imply to pass through another region and then return to the first one to reduce the length of the path.
As we can see by the Figure 2 both paths starts from r1, go through r2, and then return to r1. However, only the path represented by the continuous line is rational, even if the constraint III.5 is respected by both of them. Before the definition of the constraint that identifies the correct paths, the concept of sub-path has to be defined.
Definition III.6 (Sub-path). Let p a path, a sub-path p0 of p is a sub-sequence of oriented openings denoted as p0 ⊂ P which respects the order of appearance for the openings in p, but the orientation of openings in p0 can differ from the orientation in p. p0 must be a valid path.
The reason of the orientation change can be explained with the example in Fig. 3: given the path p = (r1, o2, r2) → (r2, o1, r1) → end, the path p0 = (r2, o2, r1) → end is a valid path and is considered as a sub-path of p, with a different orientation of o2. In addition, given the path p1 = (r2, o2, r1) → end, the path p2 = (r1, o2, r2) → (r2, o1, r1) → end is as well a minimal path if and only if the travel time of p2 is less than p1. It is easy to understand that this situation can emerge only if r1 is concave. As we can see, the starting region of the two paths is different, but the key element of the rule is the position of the opening o2. If this rule is verified in the center position of the opening o2, this path will be a considerable path by the agents surrounding o2 in r1.
In Figure 3 the correct paths for this example environment are shown. An agent located in r2 can reach r1 and then the destination D using both of the opening considering the congestions. An agent located in r1 can go directly to the exit or chose the path o2 → o1 → D.
Definition III.7 (Minimal path). p is a minimal path if and only if it is a valid path and ∀p0 ⊂ p : S(p0) = S(p)∧D(p0) = D(p) =⇒ T (p0) > T (p)
The verification of this rule is a sufficient condition for the opening loop constraint III.5 and solve the problem on the region loop constraint independently from the configuration of the environment (i.e. convex or concave regions).
At this point the constraint that defines a minimal path has been provided. This can be used to build the complete set of minimal paths towards a destination before running the simulation. It must be noted that an arbitrary path represents a set of paths itself, since it can be undertaken at any region it crosses. Indeed every path p provides also information about the sub-paths achieved by cutting the head of p with an arbitrary number of elements. So a minimal representation of the set is a tree-like structure defined as: Definition III.8 (Paths tree). Given a set of minimal paths towards a destination, the Paths-Tree is a tree where the root represents the final destination and a branch from every node to the root describes a minimal path, crossing a set of openings (other nodes) and region (edges). Each node has an attribute describing the expected travel time to the destination.
2) An Algorithm to Compute the Paths Tree: The algorithm we are proposing build the the Paths Tree in a recursive way, starting from a path containing only the destination and adding nodes if and only if the generated path respects the definition of minimality.
Formally the Paths Tree is defined as P T = (N, E) where N is the set of nodes and E the set of edges. Each node n is defined as a triple (id, o, τ ) where: • id ∈ N is the id of the node • o ∈ O is the name of the opening • τ ∈ R+ is the expected travel time for the path described by the branch.
Each edge e is defined as a triple (p, c, r) where: • p ∈ O is the id of the parent • c ∈ O is the id of the child • r ∈ R is the region connecting the child node to its parent.
To allow a fast access to the nodes describing a path that can be undertaken from a certain region, we added a structure called M that maps each r in the list of p : (p, c, r) ∈ E (for every c).
Given a destination D = (rx, universe), the paths tree computation is defined with the following procedures.
1: add (0, D, 0) to N 2: add 0 to M [rx] 3: ∀s ∈ O ShortestPath[s] ← ∞ 4: expand region(0, D, 0, Rx, ShortestP ath)
Require: input parameters (parentId, parentN ame,
parentT ime, RegionT oExpand, ShortestP ath) 1: expandList ← ∅ 2: opList = Op(RegionT oExpand) \ parentN ame 3: for o ∈ opList do 4: τ = parentT ime + D(o,pasrpeenetdName) 5: if CheckM inimality(ShortestP ath, o, τ ) == True
then 6: add (id, o, τ ) to N 7: add (parentId, id, r) to E 8: ShortestP ath[o] ← τ 9: nextRegion = o \ r 10: add id to M [nextRegion] 11: add (id, o, τ, nextRegion) to expandList 12: end if 13: end for 14: for el ∈ expandList do 15: ExpandRegion(el, ShortestP ath) 16: end for
At this point, the minimality constraint III.7 has to be verified for each candidate, by means of the function CheckM inimality explained by Alg. 3. Since this test requires the expected travel time of the new path, this has to be computed before. A failure in this test means that the examined path – created by adding a child to the node parentId – will not be minimal. Otherwise, the opening can be added and the extension procedure can recursively continue.
In line 6, id is a new and unique value to identify the node, which represents a path starting from the opening o and with expected travel time τ ; line 7 is the creation of the edge from the parent to the new node. In line 8, ShortestP ath[o] is updated with the new discovered value τ . in line 9 the opening is examined as a couple of region, selecting the one not considered now. In fact, the element nextRegion represents the region where is possible to undertake the new path. In line 10 the id of the starting opening is added to M [nextRegion], i.e., the list of the paths which can be undertaken from nextRegion. In line 11 the node with his parameter is added to the list of the next expansions, which take place in line 13-14. This passage has to be done to ensure the correct update of ShortestP ath.
With the first line, the set N of nodes is initialized with the destination of all paths in the tree, marking it with the Algorithm 3 CheckMinimality id 0 and expected travel time 0. In the third row the set of Require: input parameter (ShortestP ath, o, τ ) ShortestP ath is initialized. This will be used to track, for 1: if ShortestP ath[o] > τ then each branch, the expected travel time for the shortest sub- 2: return True path, given a start opening s. ExpandRegion is the core 3: else element of the algorithm, describing the recursive function 4: return False which adds new nodes and verifies the condition of minimality. 5: end if The procedure is described by Alg. 2.
In line 2 a list of openings candidates is computed, contain- To understand how the constraint of minimality is verified, ing possible extensions of the path represented by parentId. two basical concepts of the procedure need to be clarified. Selecting all the openings present in this region (except for Firstly, the tree describes a set of paths towards a unique the one labeled as parentN ame) will ensure that all paths destination, therefore given an arbitrary node n, the path eventually created respect the validity constraint III.2. described by the parent of n is a subpath with a different starting node and leading to the same destination. Furthermore, the expansion procedure implies that once reached a node of depth l, all the nodes of its path having depth l − k, k > 0 have been already expanded with all child nodes generating other minimal paths.
Note that the variable ShortestP ath is particularly important since, given p the current path in evaluation, it describes the minimum expected travel time to reach the destination (i.e. the root of the tree) from each opening already evaluated in previous expansions of the branch. Thus, if τ is less than ShortestP ath[o], the minimality constraint III.7 is respected.
3) Congestion Evaluation: The explained approach of the paths tree provides information on travel times implied by each path towards a destination. By only using this information, the choice of the agents will be still static, essentially describing the shortest path. This may also lead to an increase of the experienced travel times, since congestion may emerge without being considered.
For the evaluation of congestion, we provide an approach that estimates, for each agent, the additional time deriving by passing through a jam. The calculation considers two main aspects: the size of the eventually arisen congestion around an opening; the average speed of the agents inside the congested area. Since the measurement of the average speed depends on the underlying model that describes the physical space and movement of the agents, we avoid to explain this component with full details, by only saying that the speed is estimated with an additional grid counting the blocks (i.e. when agents maintain positions at the end of the step) in the surrounding area of each opening. The average number of blocks defines the probability to move into the area per step, thus the speed of the agents inside. For the size of the area, our approach is to define a minimum radius of the area and (i) increase it when the average speed becomes too low or (ii) reduce it when it returns normal.
As we can see in Figure 4, the presence of an obstacle in the room is well managed by using floor field while defining the area for a given radius. If a lot of agents try to go through the same opening at the same time, a congestion will arise, reducing the average speed and letting the area to increase its size. When this one becomes too big and the farthest agents inside are not slowed by the congestion, the average speed will start increasing until the area re-sizing will stop.
During this measurement the average speed value for each radius is stored. Values for sizes smaller than the size of the area will be used by the agents inside it, as will be explained in the next section. Two function are introduced for the calculation: • size(o): return the size of the congestion around the
opening • averageSpeed(o, s) : return the average speed estimated
in the area of size s around the opening o.
4) Agents Dynamical Path Choice: At this point we have defined which information an agent will use to make its decision: • the Paths Tree, computed before the simulation, will be
used as a list of possible path choice; • the position of the agent, will be used to adjust the expected travel time considering the distance between the agent and the first opening of a path ( d(a, o)); • the information about congestion around each opening, computed during the simulation, will be used to estimate the delay introduced by each opening in the path.
The agent, who knows in which region Rx he is located, can access the Paths Tree using the structure M [Rx]. The structure returns a list of nodes, each representing the starting opening for each path. At this point the agent can compute the expected travel time to reach each starting opening and add it to the travel time τ of the path.
To consider congestion, the agent has to estimate the delay introduced by each opening in a path, by firstly obtaining the size of the jammed area.
sizea(o) = (size(o) if d(a, o) ≥ i(x)
d(a, o) otherwise At this point, the agent can suppose that for the length of the area it will travel at the average speed around the opening.
delay(o) =
sizea(o) sizea(o) averageSpeed(o) − speeda If the agent is slower than the average speed around an opening, the delay will be lower than 0. In this case it is assumed that the delay is 0, implying that the congestion will not increase his speed.
At this point the agent can estimate the delay introduced by all openings.
pathDelay(p) =
X delay(o) o∈p
This is an example of omniscient agents, since they can always know the status of each opening. Another option is to suppose that the agent can only see the state of the opening located in the same region of the agent. In this situation the agent must be able to remember the state of the opening when it left a region, otherwise the information used to estimate the travel time at each time will not be consistent during the execution of the plan.
(2) (3) (4) d(a, S(p))
speeda T ime(p) = τp + + pathDelaya(p)
(5)
• τp : the expected travel time of the path p
d(a,S(p) : the expected time to reach S(p) from the • speeda
position of the agent • pathDelaya(p) : the estimation of the delay introduced by each opening in the path, based on the memory of the agent (which may or may not be updated for each opening).
The aim of the first experimental scenario is to show the output of the paths tree generation algorithm. Figure 5 shows the environment and the associated data structure. The tree contains two information on each node, describing the Id of the mapped opening and the estimated time associated to its path. In addition, each edge is labeled with the Id of the region crossed by the path. The result shows that the possible minimal paths have been represented in the tree. In particular, child nodes of o1 and o2, passing inside r2, have not been added since that would imply a path passing from o3 or o4 and describing a not rational way through r2 and the corridor at the bottom of r1. Paths like p = o2 → o4 → end or p = o2 → o4 → end have been considered instead, since they could be plausible for pedestrians being in the top left corner of the scenario.
Results of the second experiment are shown in Figure 6: the illustrated environment have been populated with 200 agents, generated in the Start object with an arrival frequency of around 7 pers/sec. The heat maps contain the cumulative mean densities of pedestrians, describing a cumulative value of density in each cell for a fixed time window (in this case the duration is 50 steps, equal to 12.5 seconds). It must be noted that at each step the values are accumulated only in pedestrians (a) scenario (b) step 0 – 50 positions, in order to give an idea of what pedestrians have perceived during the simulation. The stream of pictures shows that the arrival rate cannot be sustained from the opening at the top left of the environment, describing the shortest path towards the exit, thus a growing congestion arises in front of it. This increases the time perceived by the agents to employ the shortest path, leading a significant part of them to change their route preferring the other opening, that will get also congested in the third time window. The arrival rate stops at about step 150 and from this moment the environment starts to get empty.
The paper has presented a hybrid agent architecture for
modeling tactical level decisions, related to the choice of a
route to follow in an environment comprising several rooms
connected by openings, integrated with a validated operational
level model, employing a floor-field based approach. The
described model allows the agent taking decisions based on
a static a-priori knowledge of the environment and dynamic
perceivable information on the current level of crowdedness
of visible path alternatives. The model was experimented
in benchmark scenarios showing the adequacy in providing
adaptiveness to the contextual situation. The future works, on
one hand, are mainly aimed at defining requirements and an
approach for the validation of the results achieved through the
model: this represents an open challenge, since there are no
comprehensive data sets on human tactical level decisions and
automatic acquisition of this kind of data from video cameras
is still a challenging task [