=Paper=
{{Paper
|id=Vol-1382/paper18
|storemode=property
|title=Adaptive Hybrid Agents for Tactical Decisions in Pedestrian Environments
|pdfUrl=https://ceur-ws.org/Vol-1382/paper18.pdf
|volume=Vol-1382
|dblpUrl=https://dblp.org/rec/conf/woa/CrocianiPV15
}}
==Adaptive Hybrid Agents for Tactical Decisions in Pedestrian Environments==
https://ceur-ws.org/Vol-1382/paper18.pdf
Proc. of the 16th Workshop “From Object to Agents” (WOA15) June 17-19, Naples, Italy
Adaptive Hybrid Agents for Tactical Decisions in
Pedestrian Environments
Luca Crociani, Andrea Piazzoni, Giuseppe Vizzari
CSAI - Complex Systems & Artificial Intelligence Research Center,
University of Milano-Bicocca, Milano, Italy
{luca.crociani,giuseppe.vizzari}@disco.unimib.it
a.piazzoni@campus.unimib.it
Abstract—This paper presents a hybrid agent architecture for and at knowledge level for tactical ones) in a comprehensive
modeling different types of decisions in a pedestrian simulation framework preserving and extending the validity that, thanks
system. In particular, the present work focuses on tactical to recent extensive observations and analyses (see, e.g., [4]),
level decisions that are essentially related to the choice of a
route to follow in an environment comprising several rooms can be achieved at the operational level represents an urgent
connected by openings. These decisions are then enacted at the and significant open challenge.
operational level by mean of a floor-field based model, in a This paper presents a hybrid agent architecture for mod-
discrete simulation approach. The described model allows the eling different types of decisions in a pedestrian simulation
agent taking decisions based on a static a-priori knowledge of the system. In particular, the present work focuses on tactical
environment and dynamic perceivable information on the current
level of crowdedness of visible path alternatives. The paper level decisions that are essentially related to the choice of a
presents the model formally, motivating the adopted choices with route to follow in an environment comprising several rooms
reference to the relevant state of the art. The model is also connected by openings. These decisions are then enacted at
experimented in benchmark scenarios showing the adequacy in the operational level by mean of a floor-field based model,
providing adaptiveness to the contextual situation. in a discrete simulation approach. The described model that
Index Terms—Pedestrian Simulation, Tactical Level, Hybrid integrates within an organised and comprehensive framework
Agents. different spatial representations, types of knowledge and deci-
sion making mechanisms, allows the agent taking decisions
I. I NTRODUCTION based on a static a-priori knowledge of the environment
The simulation of complex systems is one of the most and dynamic perceivable information on the current level of
successful areas of application of agent-based approaches: crowdedness of visible path alternatives.
even though models, mechanisms and technologies adopted The paper presents the relevant state of the art in the
by researchers in different disciplines are not necessarily up- following Section. The tactical level part of the model is
to-date or in line with the most current results in the computer formally presented in Section III-B whereas its experimental
science and engineering area about agent technologies [1], application in benchmark scenarios showing the adequacy in
the area still presents interesting challenges and potential providing adaptiveness to the contextual situation is given in
developments for agent research. Section IV.
The simulation of pedestrians and crowds is an example
of already established yet lively research context: both the
II. R ELATED W ORKS
automated analysis and the synthesis of pedestrian and crowd
behaviour, as well as attempts to integrate these complemen- The research on pedestrian dynamics is basically growing
tary and activities [2], present open challenges and potential on two lines. On the analysis side, literature is producing
developments in a smart environment perspective [3]. methods for an automatic extraction of pedestrian trajectories
Even if we only consider choices and actions related to (e.g. [5], [4]), charactertization of pedestrian flows (e.g. [6])
walking, modelling human decision making activities and automatic recognition of pedestrian groups [7], recently gain-
actions is a complicated issue: different types of decisions are ing importance due to differences in trajectories, walking
taken at different levels of abstraction, from path planning speeds and space utilization [8]. The synthesis side – where
to the regulation of distance from other pedestrians and the contributions of this work are concentrated – has been even
obstacles present in the environment. Moreover, the measure of more prolific, starting from preliminary studies and assump-
success and validity of a model is definitely not the optimality tions provided by [9] or [10] and leading to quite complex,
with respect to some cost function, as in robotics, but the yet not usually validated, models exploring components like
plausibility, the adherence to data that can be acquired by panic [11] or other emotional variables. To better understand
means of observations or experiments. Putting together tactical the model presented in the next section, the following will
and operational level decisions, often adopting different ap- provide a brief description of related works on pedestrian
proaches (typically behaviour-based for operational decisions, dynamics modeling and simulation.
115
Proc. of the 16th Workshop “From Object to Agents” (WOA15) June 17-19, Naples, Italy
[12]1 provides a well-known scheme to model the pedestrian discussed methods to deal with different speeds, in addition
dynamics, describing 3 levels of behavior: to the usage of a finer grid discretization that decreases the
• Strategic level: the person formulates his/her abstract error in the reproduction of the environment, but significantly
plan and final objective motivating the overall decision to impacts on the efficiency of the model. An alternative approach
move (e.g. “I am going to the University today to follow to represent different speeds in a discrete space is given
my courses and meet my friend Paul”); by [25]. [26] is another extension of the floor-field model,
• Tactical level: the set of activities to complete the plan is where groups of pedestrians are also considered.
computed and scheduled (e.g. “I am going to take the 8:00 The tactical level has gained interest only recently in the
AM train from station XYZ then walk to the Department, literature of pedestrian dynamics modeling and simulation,
then meet Paul at the cafeteria after courses, then . . . ”); despite its relevance for the simulation of a realistic behavior
• Operational level: each activity is physically executed, (especially by thinking to evacuation situations). Path planning
i.e., the person perform the movement from his/her algorithms have been widely investigated and proposed in the
position to the current destination (e.g. precise walking field of computer graphics and gaming by means of graph-
trajectory and timing, such as a sequence of occupied based methods (e.g. [27], [28]), but with aims not necessarily
cells and related turn in a discrete spatial representation matching the requirements of pedestrian simulation, since the
and simulation). point is mainly to reach a visual realism.
Most of the literature has been focussed on the reproduction On the pedestrian dynamics side, a relevant recent work is
of the physics of the system, so on the lowest level, where a the one from [29], mainly dealing with tactical level decisions
significant knowledge on the fundamental diagram achieved during evacuation, providing an approach to find the quickest
with different set of experiments and in different environment path towards the exit, i.e. the way that implies the fewest
settings (see, e.g, [14], [15]) allows a robust validation of the time. The approach is tested on the basis of four strategies
models. for the route choice management, given by the combination
of applying the shortest or quickest path, with a local (i.e.,
Literature of this level can be classified regarding the scope
to go out from the room) or global (i.e., to reach the desti-
of the modeling approach. Macroscopic models describe the
nation) strategy. The global shortest path is calculated with
earliest approach to pedestrian modeling, basing on analogies
the well-known Floyd-Warshall algorithm, implying therefore
between behavior of dense crowds and kinetic gas [9] or
a computational time that can become an issue by having
fluids [10], but essentially abstracting the concept of individ-
a large number of nodes or by considering special features
ual. A microscopic approach is instead focused on modeling
in the simulated population (i.e. portion of the path where
the individual behavior, effectively improving the simulations
the cost differs from an agent to another). The work in this
precision also in low density situations.
paper will propose an alternative and efficient approach to
The microscopic approach is as well categorized in two
find a global path, where each agent will be able to consider
classes describing the representation of space and movement:
additional costs in sub-paths without adding particular costs
continuous models simulate the dynamics by means of a force-
to the computation.
based approach, which finds its basis on the well-known social
force model by [16]. These models design pedestrians as
particles moved by virtual forces, that drive them towards their III. A M ODEL FOR TACTICAL L EVEL OF P EDESTRIANS
destination and let them avoid obstacles or other pedestrians. The model described in this work provides a methodology
Latest models on this class are the centrifugal force model to deal with tactical choices of agents in pedestrian simulation
by [17] and the stride length adaptation model by [18]. Other systems. Due to constraints on the length of the paper, the de-
examples consider also groups of pedestrians by means of scription of the part of the model dedicated to the operational
attractive forces among person inside the group [19]. level, thoroughly described in [30], will not be provided.
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
The framework that enables agents to perform choices on
still able to reproduce realistic aggregated data. This class
their plan implies a graph-like, topological, representation of
derives from vehicular modeling and some models are direct
the walkable space, whose calculation is defined in [31] and
adaptations of traffic ones, describing the dynamics with ad
briefly reported in this section. This model allows agents to
hoc rules (e.g. [20], [21]). Other models employs the well-
perform a static path planning, since dynamical information
know floor field approach from [22], where a static floor
such as congestion is not considered in the graph. These
field drives pedestrians towards a destination and a dynamic
additional elements will be considered in the extension that
floor field is used to generate a lane formation effect in
is presented in the next section and represent the innovative
bi-directional flow. [23] is an extension of the floor field
part of this paper.
model, introducing the anticipation floor field used to manage
The environment abstraction identifies regions (e.g. a room)
crossing trajectories and encourage the lane formation. [24]
as node of the labeled graph and openings (e.g. a door) as
1 A similar classification can be found in vehicular traffic modeling edges. This so-called cognitive map is computed starting from
from [13]. the information of the simulation scenario, provided by the
116
Proc. of the 16th Workshop “From Object to Agents” (WOA15) June 17-19, Naples, Italy
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:
P P
xi yi
(a) Center(ω) = , , (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 vice-
versa.
B. Modeling Adaptive Tactical Decisions with A Paths Tree
(b)
To enhance the route choice and enable dynamical, adaptive,
decisions of the agents in a efficient way, a new data structure
Fig. 1. An example environment (a) with the resulting cognitive map (b), by has been introduced, containing information about the cost
applying the procedure from [31].
of plausible paths towards the exit from each region of the
scenario.
Using the well-known Floyd-Warshall algorithm, in fact,
user and necessarily containing: (i) the description of the walk- can solve the problem but introduces issues in computational
able space, that is, the size of the simulated environment and time: the introduction of dynamical elements in the paths cost
the positions of obstacles and walls; (ii) the position of final computation (i.e. congested paths) implies a re-computation of
destinations (i.e. exits) and intermediate targets (e.g. a ticket the cost matrix underlying the algorithm every step. More in
machine); borders of the logical regions of the environment details, the penalty of a congested path is a subjective element
that, together with the obstacles, will define them. Approaches for the agents, since they are walking with different desired
to automatically configure a graph representation of the space, velocities, thus the calculation cost increases also with the
without any additional information by the user, have been number of agents.
already proposed in the literature (e.g. [32]), but they are not The approach here proposed implies an off-line calculation
leading to a cognitively logical description, i.e., a topological of the data-structure that we called paths tree, but is com-
map. A cognitive definition of the space allows, in fact, a putationally efficient during the simulation and provides to
proper definition of portions of the environment where, for the agents direct information about the travel times describing
example, the behavior of a person is systematically different each path. The method is described in the following para-
(e.g. the change of speed profile in stairs or ramps), or that graphs.
contain relevant intermediate targets for the agent plan (e.g. a 1) The Paths Tree: We define the Paths Tree as a tree
ticket machine). data-structure containing the set of “rational” paths towards
The cognitive map is defined as a graph CM = (V, E) a destination, that will be its root. Before describing what we
generated with a procedure included to the floor field diffusion, mean with the attribute rational, that can be seen as a fuzzy
starting from the statements that each user-defined opening concept, a general definition of path must be provided.
generates a floor field from its cells and spread only in the A path is defined as a finite sequence of openings X →
regions that it connects, and that each region has a flag Y → . . . → Z where the last element represents the final
indicating its properties among its cells. The floor fields destination. It is easy to understand that not every sequence
diffusion procedure iteratively adds to CM the couple of nodes of openings represents a path that is walkable by an agent.
found in the diffusion (duplicates are avoided) and labeled with Firstly, a path must be a sequence of consecutive oriented
the region id and the edge labeled with the id of the opening. openings regarding the physical space.
Each final destination, different from the normal openings Definition III.1 (Oriented opening). Let E = R1 , R2 be
since it resides in only one region, will compose an edge a opening linking the regions R1 and R2 , (R1 , E, R2 ) and
linking the region to a special node describing the external (R2 , E, R1 ) define the oriented representations of E.
universe. Intermediate targets will be mapped as attributes of
its region node. An example of environment together with the An oriented opening will therefore describe a path from an
resulting cognitive map is presented in Fig. 1. arbitrary position of the first region towards the second one.
To allow the calculation of the paths tree, that will be
described in the following section, functions Op(ρ) and 2 Its Id, described in the label of the edge mapped to it.
117
Proc. of the 16th Workshop “From Object to Agents” (WOA15) June 17-19, Naples, Italy
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. Fig. 2. A concave region can imply the plausibility of a path crossing it
twice, but its identification is not elementary.
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.
X Dist(openingi , openingi+1 )
T (p) = (1)
speed
i∈[1,|p|−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
Fig. 3. The correct paths for this environment. Inside r2 the choice between
be not rational. the two openings is also determined by the congestion.
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 a different orientation of o2. In addition, given the path
opening more than once during the simulation, but this will p1 = (r2 , o2 , r1 ) → end, the path p2 = (r1 , o2 , r2 ) →
happen only with a change of the agent plan. (r2 , o1 , r1 ) → end is as well a minimal path if and only if the
By assuming to have only convex regions in the simulated travel time of p2 is less than p1 . It is easy to understand that
space, we could easily achieve the set of rational paths by this situation can emerge only if r1 is concave. As we can see,
extending III.5 as to let a path not containing duplicated the starting region of the two paths is different, but the key
regions. However, since the definition of region describes also element of the rule is the position of the opening o2 . If this
rooms, concave regions must be considered. Some paths may, rule is verified in the center position of the opening o2 , this
thus, imply to pass through another region and then return to path will be a considerable path by the agents surrounding o2
the first one to reduce the length of the path. in r1.
As we can see by the Figure 2 both paths starts from In Figure 3 the correct paths for this example environment
r1 , go through r2 , and then return to r1 . However, only the are shown. An agent located in r2 can reach r1 and then
path represented by the continuous line is rational, even if the destination D using both of the opening considering the
the constraint III.5 is respected by both of them. Before the congestions. An agent located in r1 can go directly to the exit
definition of the constraint that identifies the correct paths, the or chose the path o2 → o1 → D.
concept of sub-path has to be defined. Definition III.7 (Minimal path). p is a minimal path if and
Definition III.6 (Sub-path). Let p a path, a sub-path p0 of p is only if it is a valid path and ∀p0 ⊂ p : S(p0 ) = S(p)∧D(p0 ) =
a sub-sequence of oriented openings denoted as p0 ⊂ P which D(p) =⇒ T (p0 ) > T (p)
respects the order of appearance for the openings in p, but the
The verification of this rule is a sufficient condition for the
orientation of openings in p0 can differ from the orientation in
opening loop constraint III.5 and solve the problem on the
p. p0 must be a valid path.
region loop constraint independently from the configuration
The reason of the orientation change can be explained with of the environment (i.e. convex or concave regions).
the example in Fig. 3: given the path p = (r1, o2, r2) → At this point the constraint that defines a minimal path has
(r2, o1, r1) → end, the path p0 = (r2, o2, r1) → end been provided. This can be used to build the complete set
is a valid path and is considered as a sub-path of p, with of minimal paths towards a destination before running the
118
Proc. of the 16th Workshop “From Object to Agents” (WOA15) June 17-19, Naples, Italy
simulation. It must be noted that an arbitrary path represents Algorithm 2 ExpandRegion
a set of paths itself, since it can be undertaken at any region it Require: input parameters (parentId, parentN ame,
crosses. Indeed every path p provides also information about parentT ime, RegionT oExpand, ShortestP ath)
the sub-paths achieved by cutting the head of p with an 1: expandList ← ∅
arbitrary number of elements. So a minimal representation of 2: opList = Op(RegionT oExpand) \ parentN ame
the set is a tree-like structure defined as: 3: for o ∈ opList do
4: τ = parentT ime + D(o,parentN ame)
Definition III.8 (Paths tree). Given a set of minimal paths speed
5: if CheckM inimality(ShortestP ath, o, τ ) == True
towards a destination, the Paths-Tree is a tree where the root
then
represents the final destination and a branch from every node
6: add (id, o, τ ) to N
to the root describes a minimal path, crossing a set of openings
7: add (parentId, id, r) to E
(other nodes) and region (edges). Each node has an attribute
8: ShortestP ath[o] ← τ
describing the expected travel time to the destination.
9: nextRegion = o \ r
2) An Algorithm to Compute the Paths Tree: The algorithm 10: add id to M [nextRegion]
we are proposing build the the Paths Tree in a recursive way, 11: add (id, o, τ, nextRegion) to expandList
starting from a path containing only the destination and adding 12: end if
nodes if and only if the generated path respects the definition 13: end for
of minimality. 14: for el ∈ expandList do
Formally the Paths Tree is defined as P T = (N, E) where 15: ExpandRegion(el, ShortestP ath)
N is the set of nodes and E the set of edges. Each node n is 16: end for
defined as a triple (id, o, τ ) where:
• id ∈ N is the id of the node
• o ∈ O is the name of the opening At this point, the minimality constraint III.7 has to
• τ ∈ R is the expected travel time for the path described
+ be verified for each candidate, by means of the function
by the branch. CheckM inimality explained by Alg. 3. Since this test re-
quires the expected travel time of the new path, this has to be
Each edge e is defined as a triple (p, c, r) where:
computed before. A failure in this test means that the examined
• p ∈ O is the id of the parent
path – created by adding a child to the node parentId – will
• c ∈ O is the id of the child
not be minimal. Otherwise, the opening can be added and the
• r ∈ R is the region connecting the child node to its
extension procedure can recursively continue.
parent. In line 6, id is a new and unique value to identify the
To allow a fast access to the nodes describing a path that node, which represents a path starting from the opening o and
can be undertaken from a certain region, we added a structure with expected travel time τ ; line 7 is the creation of the edge
called M that maps each r in the list of p : (p, c, r) ∈ E (for from the parent to the new node. In line 8, ShortestP ath[o]
every c). is updated with the new discovered value τ . in line 9 the
Given a destination D = (rx , universe), the paths tree opening is examined as a couple of region, selecting the
computation is defined with the following procedures. one not considered now. In fact, the element nextRegion
represents the region where is possible to undertake the new
Algorithm 1 Paths tree computation path. In line 10 the id of the starting opening is added to
1: add (0, D, 0) to N M [nextRegion], i.e., the list of the paths which can be
2: add 0 to M [rx ] undertaken from nextRegion. In line 11 the node with his
3: ∀s ∈ O ShortestPath[s] ← ∞ parameter is added to the list of the next expansions, which
4: expand region(0, D, 0, Rx , ShortestP ath) 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
119
Proc. of the 16th Workshop “From Object to Agents” (WOA15) June 17-19, Naples, Italy
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
Fig. 4. Examples of surroundings of different sizes, for two configurations decision:
of the environment.
• 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
starting node and leading to the same destination. Furthermore,
the expansion procedure implies that once reached a node of expected travel time considering the distance between the
depth l, all the nodes of its path having depth l − k, k > 0 agent and the first opening of a path (d(a, o));
• the information about congestion around each opening,
have been already expanded with all child nodes generating
other minimal paths. computed during the simulation, will be used to estimate
Note that the variable ShortestP ath is particularly impor- the delay introduced by each opening in the path.
tant since, given p the current path in evaluation, it describes The agent, who knows in which region Rx he is located,
the minimum expected travel time to reach the destination can access the Paths Tree using the structure M [Rx ]. The
(i.e. the root of the tree) from each opening already evaluated structure returns a list of nodes, each representing the starting
in previous expansions of the branch. Thus, if τ is less than opening for each path. At this point the agent can compute the
ShortestP ath[o], the minimality constraint III.7 is respected. expected travel time to reach each starting opening and add it
3) Congestion Evaluation: The explained approach of the to the travel time τ of the path.
paths tree provides information on travel times implied by each To consider congestion, the agent has to estimate the delay
path towards a destination. By only using this information, the introduced by each opening in a path, by firstly obtaining the
choice of the agents will be still static, essentially describing size of the jammed area.
the shortest path. This may also lead to an increase of the (
size(o) if d(a, o) ≥ i(x)
experienced travel times, since congestion may emerge without sizea (o) = (2)
being considered. d(a, o) otherwise
For the evaluation of congestion, we provide an approach At this point, the agent can suppose that for the length of the
that estimates, for each agent, the additional time deriving by area it will travel at the average speed around the opening.
passing through a jam. The calculation considers two main
aspects: the size of the eventually arisen congestion around an sizea (o) sizea (o)
delay(o) = − (3)
opening; the average speed of the agents inside the congested averageSpeed(o) speeda
area. Since the measurement of the average speed depends on If the agent is slower than the average speed around an
the underlying model that describes the physical space and opening, the delay will be lower than 0. In this case it is
movement of the agents, we avoid to explain this component assumed that the delay is 0, implying that the congestion will
with full details, by only saying that the speed is estimated not increase his speed.
with an additional grid counting the blocks (i.e. when agents At this point the agent can estimate the delay introduced by
maintain positions at the end of the step) in the surrounding all openings.
area of each opening. The average number of blocks defines X
the probability to move into the area per step, thus the speed pathDelay(p) = delay(o) (4)
of the agents inside. For the size of the area, our approach is to o∈p
define a minimum radius of the area and (i) increase it when This is an example of omniscient agents, since they can
the average speed becomes too low or (ii) reduce it when it always know the status of each opening. Another option is to
returns normal. suppose that the agent can only see the state of the opening
As we can see in Figure 4, the presence of an obstacle in located in the same region of the agent. In this situation the
the room is well managed by using floor field while defining agent must be able to remember the state of the opening when
the area for a given radius. If a lot of agents try to go through it left a region, otherwise the information used to estimate
the same opening at the same time, a congestion will arise, the travel time at each time will not be consistent during the
reducing the average speed and letting the area to increase its execution of the plan.
size. When this one becomes too big and the farthest agents
inside are not slowed by the congestion, the average speed d(a, S(p))
will start increasing until the area re-sizing will stop. T ime(p) = τp + + pathDelaya (p) (5)
speeda
During this measurement the average speed value for each
radius is stored. Values for sizes smaller than the size of Where:
the area will be used by the agents inside it, as will be • τp : the expected travel time of the path p
120
Proc. of the 16th Workshop “From Object to Agents” (WOA15) June 17-19, Naples, Italy
(a) (a) scenario (b) step 0 – 50
(b) (c) step 50 – 100 (d) step 100 – 150
Fig. 5. Example scenario with the respective paths tree.
d(a,S(p)
• speeda: the expected time to reach S(p) from the
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).
(e) step 150 – 200 (f) step 200 – 250
IV. A PPLICATIONS IN E XAMPLE S CENARIOS
Fig. 6. The test scenario (a) with cumulative mean density maps of the
In order to show the reliability and potentials of the pro- simulation for various time windows (b – f).
posed approach, results of two example scenarios will be
presented in this section.
The aim of the first experimental scenario is to show the positions, in order to give an idea of what pedestrians have
output of the paths tree generation algorithm. Figure 5 shows perceived during the simulation. The stream of pictures shows
the environment and the associated data structure. The tree that the arrival rate cannot be sustained from the opening at
contains two information on each node, describing the Id of the top left of the environment, describing the shortest path
the mapped opening and the estimated time associated to its towards the exit, thus a growing congestion arises in front of it.
path. In addition, each edge is labeled with the Id of the region This increases the time perceived by the agents to employ the
crossed by the path. The result shows that the possible minimal shortest path, leading a significant part of them to change their
paths have been represented in the tree. In particular, child route preferring the other opening, that will get also congested
nodes of o1 and o2, passing inside r2, have not been added in the third time window. The arrival rate stops at about step
since that would imply a path passing from o3 or o4 and 150 and from this moment the environment starts to get empty.
describing a not rational way through r2 and the corridor at
the bottom of r1. Paths like p = o2 → o4 → end or p = V. C ONCLUSIONS
o2 → o4 → end have been considered instead, since they The paper has presented a hybrid agent architecture for
could be plausible for pedestrians being in the top left corner modeling tactical level decisions, related to the choice of a
of the scenario. route to follow in an environment comprising several rooms
Results of the second experiment are shown in Figure 6: connected by openings, integrated with a validated operational
the illustrated environment have been populated with 200 level model, employing a floor-field based approach. The
agents, generated in the Start object with an arrival frequency described model allows the agent taking decisions based on
of around 7 pers/sec. The heat maps contain the cumulative a static a-priori knowledge of the environment and dynamic
mean densities of pedestrians, describing a cumulative value perceivable information on the current level of crowdedness
of density in each cell for a fixed time window (in this case the of visible path alternatives. The model was experimented
duration is 50 steps, equal to 12.5 seconds). It must be noted in benchmark scenarios showing the adequacy in providing
that at each step the values are accumulated only in pedestrians adaptiveness to the contextual situation. The future works, on
121
Proc. of the 16th Workshop “From Object to Agents” (WOA15) June 17-19, Naples, Italy
one hand, are mainly aimed at defining requirements and an [15] J. Zhang, W. Klingsch, A. Schadschneider, and A. Seyfried, “Ordering
approach for the validation of the results achieved through the in bidirectional pedestrian flows and its influence on the fundamental
diagram,” Journal of Statistical Mechanics: Theory and Experiment,
model: this represents an open challenge, since there are no no. 02, p. 9, 2011.
comprehensive data sets on human tactical level decisions and [16] D. Helbing and P. Molnar, “Social force model for pedestrian
automatic acquisition of this kind of data from video cameras dynamics,” Physical review E, 1995.
[17] M. Chraibi, A. Seyfried, and A. Schadschneider, “Generalized
is still a challenging task [33]. Even the mentioned [29], like centrifugal-force model for pedestrian dynamics,” Phys. Rev. E, vol. 82,
most works on this topic, just explores the different alternatives no. 4, p. 46111, 2010.
that can be generated with distinct modeling choices, whereas [18] I. von Sivers and G. Köster, “Dynamic Stride Length Adaptation
According to Utility And Personal Space,” Transportation Research
a constrained form of validation was described in [34], al- Part B, vol. 74, pp. 104–117, 2015.
though reported data are not sufficient for a quantitative cross [19] F. Qiu and X. Hu, “Modeling group structures in pedestrian crowd
validation of our approach. On the other hand, the addition of simulation,” Simulation Modelling Practice and Theory, vol. 18, no. 2,
pp. 190 – 205, 2010.
specific area actions (e.g. wait after reaching a certain point of [20] V. Blue and J. Adler, “Modeling Four-Directional Pedestrian Flows,”
interest indicated by a marker) and events (e.g. the arrival of a Transportation Research Record: Journal of the Transportation
train) triggering agents’ actions and, more generally, allowing Research Board, vol. 1710, no. -1, pp. 20–27, Jan. 2000.
[21] V. J. Blue and J. L. Adler, “Cellular Automata Microsimulation of
the elaboration of more complicated agents’ plans is also a Bi-Directional Pedestrian Flows,” Transportation Research Record, vol.
planned extension on the side of model expressiveness. 1678, pp. 135–141, 1999.
[22] C. Burstedde, K. Klauck, A. Schadschneider, and J. Zittartz, “Simulation
of pedestrian dynamics using a two-dimensional cellular automaton,”
R EFERENCES Physica A: Statistical Mechanics and its Applications, vol. 295, no. 3 -
4, pp. 507–525, 2001.
[1] S. Bandini, S. Manzoni, and G. Vizzari, “Agent based modeling and
[23] Y. Suma, D. Yanagisawa, and K. Nishinari, “Anticipation effect in
simulation: An informatics perspective,” Journal of Artificial Societies
pedestrian dynamics: Modeling and experiments,” Physica A: Statistical
and Social Simulation, vol. 12, no. 4, p. 4, 2009.
Mechanics and its Applications, vol. 391, no. 1-2, pp. 248–263, Jan.
[2] G. Vizzari and S. Bandini, “Studying pedestrian and crowd dynamics
2012.
through integrated analysis and synthesis,” IEEE Intelligent Systems,
[24] A. Kirchner, H. Klüpfel, K. Nishinari, A. Schadschneider, and
vol. 28, no. 5, pp. 56–60, 2013.
M. Schreckenberg, “Discretization effects and the influence of walking
[3] D. Pianini, M. Viroli, F. Zambonelli, and A. Ferscha, “HPC from a
speed in cellular automata models for pedestrian dynamics,” Journal of
self-organisation perspective: The case of crowd steering at the urban
Statistical Mechanics: Theory and Experiment, vol. 2004, no. 10, p.
scale,” in International Conference on High Performance Computing
P10011, 2004.
& Simulation, HPCS 2014, Bologna, Italy, 21-25 July, 2014. IEEE,
[25] S. Bandini, L. Crociani, and G. Vizzari, “Heterogeneous Pedestrian
2014, pp. 460–467.
Walking Speed in Discrete Simulation Models,” in Traffic and Granular
[4] M. Boltes and A. Seyfried, “Collecting pedestrian trajectories,”
Flow ’13, M. Chraibi, M. Boltes, A. Schadschneider, and A. Seyfried,
Neurocomputing, vol. 100, pp. 127–133, Jan. 2013.
Eds. Springer International Publishing, 2015, pp. 273–279.
[5] M. Boltes, J. Zhang, A. Seyfried, and B. Steffen, “T-junction: Ex-
[26] G. Vizzari, L. Manenti, and L. Crociani, “Adaptive Pedestrian Behaviour
periments, trajectory collection, and analysis,” in Computer Vision
for the Preservation of Group Cohesion,” Complex Adaptive Systems
Workshops (ICCV Workshops), 2011 IEEE International Conference on,
Modeling, vol. 1, no. 7, 2013.
Nov. 2011, pp. 158–165.
[27] R. Geraerts and M. Overmars, “The Corridor Map Method: A General
[6] S. D. Khan, G. Vizzari, S. Bandini, and S. Basalamah, “Detecting
Framework for Real-Time High-Quality Path Planning,” pp. 107–119,
dominant motion flows and people counting in high density crowds,”
2007.
Journal of WSCG, vol. 22, no. 1-2, pp. 21–30, 2014.
[28] R. Geraerts, “Planning short paths with clearance using explicit
[7] F. Solera and S. Calderara, “Social groups detection in crowd
corridors,” in 2010 IEEE International Conference on Robotics and
through shape-augmented structured learning,” in Image Analysis and
Automation. IEEE, May 2010, pp. 1997–2004.
Processing - ICIAP 2013 - 17th International Conference, Naples,
[29] A. U. K. Wagoum, A. Seyfried, and S. Holl, “Modelling dynamic route
Italy, September 9-13, 2013. Proceedings, Part I, ser. Lecture Notes in
choice of pedestrians to assess the criticality of building evacuation,”
Computer Science, A. Petrosino, Ed., vol. 8156. Springer, 2013, pp.
Advances in Complex Systems, vol. 15, no. 07, p. 15, 2012.
542–551.
[30] S. Bandini, L. Crociani, and G. Vizzari, “Heterogeneous speed profiles
[8] S. Bandini, A. Gorrini, and G. Vizzari, “Towards an integrated approach
in discrete models for pedestrian simulation,” in Proceedings of the
to crowd analysis and crowd synthesis: A case study and first results,”
93rd Transportation Research Board annual meeting, 2014.
Pattern Recognition Letters, vol. 44, pp. 16–29, 2014.
[31] L. Crociani, A. Invernizzi, and G. Vizzari, “A hybrid agent architecture
[9] L. F. Henderson, “The Statistics of Crowd Fluids,” Nature, vol. 229,
for enabling tactical level decisions in floor field approaches,” Trans-
no. 5284, pp. 381–383, Feb. 1971.
portation Research Procedia, vol. 2, pp. 618–623, 2014.
[10] D. Helbing, “A fluid dynamic model for the movement of pedestrians,”
[32] T. Kretz, C. Bönisch, and P. Vortisch, “Comparison of Various Methods
arXiv preprint cond-mat/9805213, 1998.
for the Calculation of the Distance Potential Field,” in Pedestrian
[11] T. Bosse, M. Hoogendoorn, M. C. A. Klein, J. Treur, C. N. van der Wal,
and Evacuation Dynamics 2008, W. W. F. Klingsch, C. Rogsch,
and A. van Wissen, “Modelling collective decision making in groups and
A. Schadschneider, and M. Schreckenberg, Eds. Springer Berlin
crowds: Integrating social contagion and interacting emotions, beliefs
Heidelberg, 2010, pp. 335–346.
and intentions,” Autonomous Agents and Multi-Agent Systems, vol. 27,
[33] S. D. Khan, G. Vizzari, and S. Bandini, “Identifying sources and sinks
no. 1, pp. 52–84, 2013.
and detecting dominant motion patterns in crowds,” Transportation
[12] A. Schadschneider, W. Klingsch, H. Klüpfel, T. Kretz, C. Rogsch, and
Research Procedia, vol. 2, no. 0, pp. 195 – 200, 2014, the Conference
A. Seyfried, “Evacuation Dynamics: Empirical Results, Modeling and
on Pedestrian and Evacuation Dynamics 2014 (PED 2014), 22-24
Applications,” in Encyclopedia of Complexity and Systems Science, R. A.
October 2014, Delft, The Netherlands.
Meyers, Ed. Springer, 2009, pp. 3142–3176.
[34] M. Asano, T. Iryo, and M. Kuwahara, “Microscopic pedestrian
[13] J. A. Michon, “A Critical View of Driver Behavior Models: What Do
simulation model combined with a tactical model for route choice
We Know, What Should We Do?” in Human Behavior and Traffic
behaviour,” Transportation Research Part C: Emerging Technologies,
Safety, L. and Evans and R. C. Schwing, Eds. Springer US, 1985, pp.
vol. 18, no. 6, pp. 842 – 855, 2010, special issue on Transportation
485–524.
Simulation Advances in Air Transportation Research.
[14] J. Zhang, W. Klingsch, T. Rupprecht, A. Schadschneider, and
A. Seyfried, “Empirical study of turning and merging of pedestrian
streams in T-junction,” ArXiv e-prints, p. 8, 2011.
122