Proc. of the 16th Workshop “From Object to Agents” (WOA15) June 17-19, Naples, Italy A Hybrid Agent Architecture for Endowing Floor Field Pedestrian Models with Tactical Level Decisions Luca Crociani, Alberto Invernizzi, Giuseppe Vizzari CSAI - Complex Systems & Artificial Intelligence Research Center, University of Milano-Bicocca, Milano, Italy {luca.crociani,giuseppe.vizzari}@disco.unimib.it alby.inve@gmail.com Abstract—For a comprehensive modeling of pedestrian dy- representation from which both the abstract representation and namics in real-world scenarios the consideration of tactical level a set of layers associated to static floor fields are automatically decisions in addition to operational ones is necessary. This paper constructed. The tactical level extension of a previous agent- presents a hybrid agent architecture employing a Floor Field approach at the operational level but granting agents an abstract based model, also allowing the management of groups of representation of the simulated environment. The paper briefly pedestrians, introduced by [3] will then be described to show presents the environmental model and hybrid agent architecture how this level and the existing operational layer interact. based on the floor field approach, then a sample practical Finally, a sample practical application in a simple case study application in a simple case study is also presented to show how it is also presented to show how it allows specifying abstract allows specifying abstract behavioural scripts for different groups of agents. behavioural scripts for different groups of agents. Index Terms—pedestrian simulation, agent-based modeling, floor-field model, hybrid agents, environments for multi-agent II. E NVIRONMENT systems As discussed by [4], the environment of an agent-based system is “a first class-abstraction that provides the surround- I. I NTRODUCTION ing conditions for agents to exist and that mediates both The Floor Field approach to the modeling and simulation the interaction among agents and the access to resources”. of pedestrian dynamics, first introduced by [1], represents a An environment for agent-based systems can encompass both viable option for the implementation of quantitatively val- abstractions and mechanisms, for instance regulating the out- idated simulation systems based on a discrete approach to comes of agents’ chosen lines of action, as discussed by [5]. the representation of the environment. However, a compre- Within this framework, for this particular application of an hensive simulation system for pedestrian dynamics in real- agent-based modeling and simulation approach, the environ- world scenarios requires the consideration of tactical level ment does not only encompass a spatial representation of decisions in addition to operational ones, as discussed by [2], the simulated area, but also a set of abstractions and data that are the main focus of the Floor Field approach. This paper structures (e.g. static floor field matrices) enabling agents’ presents a hybrid agent architecture essentially employing a perceptions, deliberations and actions. In particular, for our Floor Field approach at the operational level but providing purposes we need (i) a discretization describing the walkable agents an abstract representation of the simulated environment area subdivided into cells of configurable size (e.g. 40 cm for tactical level deliberation, a map automatically derived sided square cells); (ii) a similar discrete layer representing the from an annotated CAD-like description of the environment in effect of obstacles on the overall cell desirability; (iii) similar which the simulation must take place. This form of knowledge discrete layers representing the static floor field associated to is essentially a labeled graph in which nodes are associated to a given point of reference/interest; (iv) a graph-like abstract regions and links represent connections among them; links and representation of relevant sub-areas in the simulated space other relevant points in the environment are associated to static connected according to the reachability relationship. floor fields allowing agent navigation at the operational level. In order to support an automated production of the above Considering, instead, tactical level aspects, agents are provided elements and related data structures, a spatial representation of with a goal, a final target destination potentially enriched by the area in which the simulation must take place, in the form intermediate steps and movement constraints; they initially of a CAD-like file, is required: on the other hand, this kind autonomously inspect their knowledge and derive a plan in- of map is generally produced when planning the construction dicating intermediate destinations, associated to specific static of a building or available to managers of a premise. In order floor fields to be followed. The paper will briefly present the to allow algorithms to actually explore this representation and environmental model, including a base CAD-like geometric make sense of it, the designer is required to produce some 80 Proc. of the 16th Workshop “From Object to Agents” (WOA15) June 17-19, Naples, Italy ENTRANCE 1 - EXIT 1 GATE Hall-B A B E F A B E F {lessonA} {lessonE} HALL HALL C D G H ExitNorth ExitSouth H C D G {lessonH} ENTRANCE 2 - EXIT 2 outside (a) CAD-like representation of the environment. (b) Abstract commonsense representation of the environment. (c) Static floor field associated to the gateway between “Hall” and “A”. (d) Static floor field associated to the southern exit. Fig. 1. Relevant elements of pedestrian agents’ environment. form of annotation in it, as exemplified in Figure 1(a). In like structures supporting agents’ navigation of the environ- particular, the sub-areas in which the environment is divided ment are necessary. Examples of these data structures are into must be constrained by obstacles (in red in the figure), shown in Figure 1(c) and 1(d), respectively related to the or passages, gateways to another sub-area (in cyan), and they static floor fields leading towards the gateway between the sub- must contain a specific block indicating a label that will be areas labeled as “Hall” and “E” and the southern exit of the associated to the area. Both gateways and these label blocks scenario. Once again, the annotated CAD-like representation are annotations that do not influence the walkability of the of the environment supports the automated generation of associated cells. Additional annotations represent start areas, these layers, by means of a simple cellular automaton whose in which pedestrian agents can be created (either initially or description is omitted here for sake of space. Please notice even at later stages of the simulation), end areas, final targets that, however, we chose not to extend the diffusion of the of movements in which pedestrian agents actually exit the static floor field associated to an area or marker to all the simulation, and intermediate destinations (also associated to discrete representation of the environment, but to limit this labels, not shown in the figure) that pedestrians must reach at operation to the sub-areas that are in direct connection to the a certain point of a more articulated movement plan. target in the abstract commonsense representation. This, on The construction of such a plan requires the possibility to one hand, simplifies the environment set up phase (especially explore and process a much simpler data structure, in partic- considering relatively large environments, in which it would ular an abstract map in terms of a graph-like commonsense not be practically feasible to do this) and, on the other, is representation of the environment, as discussed by [6]. This sufficient since the agents will be provided with a tactical level structure, also exemplified in Figure 1(b), can be automatically behavioural model allowing them to generate plans requiring derived by the annotated CAD-like representation employing the perception of these fields only in these adjacent sub-areas. an algorithm that cannot be reported here for sake of space. We Additional layers are actually included in the agent en- want to emphasize here the fact that intermediate destinations vironment to support the gathering of statistics about their (such as the one included in area A, labeled as “lessonA”) are dynamics, but also their interactions (in particular, the mutual essentially included in the sub-area they are part of. Moreover, perception of members of groups) and the management of final exits are represented as annotated edges (ExitNorth and conflicts (movement intentions are stored into one of these ExitSouth in the figure) leading to a vertex not associated to additional layers to support a simple identification and man- a sub-area in the CAD-like representation of the environment agement of the conflicts by the environment itself). but rather related to the “outside” world. As we will discuss in the following section, this structure is particularly suited III. AGENT A RCHITECTURE for simple path planning algorithms that can be employed in Considering the above structure for the agent environment, agent’s tactical level. it is clear that the information provided to agents’ perceptions Instead, for managing operational level tasks in the Floor is sufficient to support basic operational level behaviour for Field approach, additional discrete grids containing gradient- pedestrian agents. In fact, whenever an agent knows where 81 Proc. of the 16th Workshop “From Object to Agents” (WOA15) June 17-19, Naples, Italy Fig. 2. Hybrid agent architecture: the operational level manages perceptions and actions, invoking the tactical level whenever plan creation or management is required. it’s headed (i.e. can perceive the static floor field associated structure, they can search for their goal in the abstract map to that destination), the basic floor field model is sufficient to and in particular the intermediate steps leading towards this allow the agent to achieve its own movement goal. However, goal. The result of this search operation (that employs state of as mentioned in the previous section, the static floor fields the art graph search algorithms whose description is omitted is not spread in the complete discrete representation of the for sake of space), leads to the construction of a plan in the environment, so an agent must actually plan a course of action, form of a set of operating instructions (in the vein of [8]) as implying a sequence of intermediate way-points associated to depicted in Figure 3. In this case, an abstract plan leading an other static floor fields, leading to an area in which the target is agent from the “Hall” to the lecture hall where “Lesson E” is finally perceivable. This particular reasoning requires a hybrid held, then to the hall where “Lesson H” is held, then finally to architecture of the agent, whose “body” component reproduces leave the building through the southern exit will be expanded the pure reactive behaviour (i.e. the raw movement at opera- to become a sequence of seven steps (intermediate passages tional level), while a “mind” is dedicated to this cognitive level through gateways among rooms require a specific operating reasoning, aimed at achieving a sequence of fields to follow in instruction). order to reach the final target. A schematic description of the The current implementation of the search algorithm repre- devised agent architecture is shown in Figure 2: the operational sents a basic approach, that does not consider agent prefer- level layer (denoted as body) is actually an implementation ences (e.g. avoid stairs and use escalators), or the crowding of the extension to the floor-field model described by [3]1 conditions of the environment (e.g. when the most direct path slightly modified to trigger the computation of tactical level is getting too congested, change the plan), but these extensions choices (carried out by the layer denoted as mind) whenever have already been considered for extended search strategies: it is necessary. An obvious condition for the activation of the recent developments along this line of research are described tactical level is the fact that an agent has a final goal that is in another contribution in this volume [9]. not immediately perceivable at operational level. For instance, in the sample environment introduced in the previous section, IV. E XAMPLE APPLICATION an agent situated in the sub-area “E” cannot perceive the floor The example application of the hybrid agent model is related field associated to the northern exit. Nonetheless, agents are to the previously described environment; in particular, it is a provided with the spatial knowledge associated to the abstract rough representation of a building including a set of lecture commonsense representation of the environment, which is a halls (labeled from “A” to “E”), all of which reachable from data structure accessible by their tactical level. Therefore, since a central hall (actually including a surrounding corridor), with they are able to understand what is their current location in this a northern and southern exits. Within this scenario, exploiting the previously described tac- 1 Additional details about the implementation are provided by [7]. tical level extension, it is relatively simple to model different 82 Proc. of the 16th Workshop “From Object to Agents” (WOA15) June 17-19, Naples, Italy Fig. 3. Operating instructions for a plan leading from “Hall” to the lecture hall where “Lesson E” is held, then to the hall where “Lesson H” is held, then finally to leave the building through the southern exit. groups of pedestrian agents associated to different groups of Some screenshots of this simulation are shown in Figure 4. students, having different timetables. For instance we could In particular, in Figure 4(a) green agents are exiting hall define three groups (Green, Yellow and White agents) whose “A” and moving towards hall “E” (using both exits of hall tasks in the environment are the following: “A”), while yellow and white agents are moving to hall “A”. Green [A → lessonE → Exit{0.5 North; 0.5 South}] In Figure 4(b) the three groups have reached the respective Yellow[EntranceNorth → lessonA → lessonH → destinations and, later on in Figure 4(c), the green group leaves Exit{0.5 North; 0.5 South}] the environment while the yellow and white groups move White [EntranceSouth → lessonA → lessonH → towards lecture hall “H”. Finally, in Figure 4(d), both groups Exit{0.5 North; 0.5 South}] are reaching their final lesson before leaving the environment. The fact that agents from the same group employ different The green agents, in other words, are already in the environ- paths to reach the same movement target may depend, on one ment at the beginning of the simulation, in particular in lecture hand, on the nature of the static floor field layer, but also on hall “A”, then they have to move to the sub-area in which the fact that, at the tactical level, they may choose different “lessonE” takes place (i.e. lecture hall “E”) and finally they intermediate steps (e.g. there are two gateways leading from must leave the environment, half of them through the northern the main hall to lecture hall “A”). exit and the other half through the souther one. Yellow and white agents, instead, enter the simulation area respectively through the northern and southern entrances, then move to the V. C ONCLUSIONS AND F UTURE D EVELOPMENTS sub-area where “lessonA” takes place (lecture hall “A”), then The paper has shown an extension of a floor field model to they have to move to “lessonH” (lecture hall “H”) and finally encompass tactical level tasks and information. We introduced leave the environment, also splitting equally between northern a particular structure of agents’ environment allowing them to and southern exits.It must be stressed the fact that the modeler perceive and act at the operational level, but also deliberate at is not forced to precisely and extensively define the path to tactical level: environmental data structures are automatically be followed by the agents employing it, which will expand an generated starting from an annotated CAD-like environment abstract plan into a proper sequence of actionable operational description. The hybrid agent architecture, including a simple level movements according to their tactical level knowledge. reactive operational level able to trigger deliberation activities The yellow agents’ plan, for instance, will be expanded into a of the tactical level whenever it is necessary, has also been in- sequence that is analogous to the one described in Figure 3. troduced. A sample application illustrating how this approach 83 Proc. of the 16th Workshop “From Object to Agents” (WOA15) June 17-19, Naples, Italy (a) Green group leaves hall “A” while yellow and white ones move towards (b) All groups reached their intermediate targets. it. (c) Green group leaves the environment, while yellow and white ones move (d) Yellow and white groups have almost completed their movement towards towards hall “H”. hall “H”. Fig. 4. Application in a university building scenario. allows specifying simple behavioural scripts for relatively [3] G. Vizzari, L. Manenti, and L. Crociani, “Adaptive pedestrian behaviour complicated agent’s plans has finally been described. Future for the preservation of group cohesion,” Complex Adaptive Systems Modeling, vol. 1, no. 7, 2013. works are aimed, on one hand, at supporting the possibility [4] D. Weyns, A. Omicini, and J. Odell, “Environment as a first class to enrich the abstract commonsense spatial representation abstraction in multiagent systems,” Autonomous Agents Multi-Agent for allowing tactical level reasoning about information like Systems, vol. 14, no. 1, pp. 5–30, 2007. [5] S. Bandini and G. Vizzari, “Regulation function of the environment estimated distances, level of crowdedness of visible areas or in agent-based simulation,” in Environments for Multi-Agent Systems passages, additional relevant information (e.g. a certain area is III, Third International Workshop, E4MAS 2006, Hakodate, Japan, May a steep ramp or staircase, which would hinder the movement 8, 2006, Selected Revised and Invited Papers, ser. Lecture Notes in Computer Science, D. Weyns, H. V. D. Parunak, and F. Michel, Eds., of elderlies or persons on wheelchairs). Moreover, we are also vol. 4389. Springer–Verlag, 2007, pp. 157–169. going to extend agents’ behavioural specification to allow the [6] S. Bandini, A. Mosca, and M. Palmonari, “Common-sense spatial coordination of group path planning and the definition of area reasoning for information correlation in pervasive computing,” Applied Artificial Intelligence, vol. 21, no. 4&5, pp. 405–425, 2007. activities, in the vein of [10]. [7] L. Crociani, L. Manenti, and G. Vizzari, “Makksim: Mas-based crowd simulations for designer’s decision support,” in PAAMS, Y. Demazeau, T. Ishida, J. M. Corchado, and J. Bajo, Eds., vol. 7879. Springer, 2013, ACKNOWLEDGEMENTS pp. 25–36. This work was partly supported by the ALIAS project [8] M. Viroli, A. Ricci, and A. Omicini, “Operating instructions for intelli- gent agent coordination,” The Knowledge Engineering Review, vol. 21, (“Higher education and internationalization for the Ageing no. 01, pp. 49–69, 2006. Society”), funded by Fondazione CARIPLO. [9] L. Crociani, A. Piazzoni, and G. Vizzari, “Adaptive hybrid agents for tactical decisions in pedestrian environments,” in Proceedings of WOA 2015 - XVI Workshop “From Objects to Agents”, 2015. R EFERENCES [10] J. Was and R. Lubaś, “Towards realistic and effective agent-based models of crowd dynamics,” Neurocomputing, vol. 146, pp. 199–209, [1] C. Burstedde, K. Klauck, A. Schadschneider, and J. Zittartz, 2014. [Online]. Available: http://www.sciencedirect.com/science/article/ “Simulation of pedestrian dynamics using a two-dimensional cellular pii/S0925231214007838 automaton,” Physica A: Statistical Mechanics and its Applications, vol. 295, no. 3 - 4, pp. 507 – 525, 2001. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0378437101001418 [2] A. Schadschneider, W. Klingsch, H. Klüpfel, T. Kretz, C. Rogsch, and A. Seyfried, “Evacuation dynamics: Empirical results, modeling and applications,” in Encyclopedia of Complexity and Systems Science, R. A. Meyers, Ed. Springer, 2009, pp. 3142–3176. 84