In this paper, we treat pedestrian evacuation in emergency scenarios of networked smart spaces. Personal safety may be jeopardized due to natural catastrophes (e.g., hurricanes, earthquakes, etc.) and/or adversarial actions of intentional enemies. During evacuation, the severity of emergency may increase causing partial or complete blockage of some evacuation routes. Thus, it is of the highest importance to (re)route evacuees based on updated real-time structure safety conditions. In this paper, we propose a multi-agent based architecture for dynamic route safety optimization in large smart space evacuation. The objective of the model is to ensure that the smart space network gets evacuated securely while aptly responding to unpredictable contingencies in the network safety.
The objective of an evacuation is to relocate evacuees from hazardous to safe areas or the areas where the life-threatening risk is minimal while providing them with safe routes. Present building evacuation approaches are mostly static and preassigned. Frequently, no coordination is available except for predefined evacuation maps. With sufficient estimated time to calamity and in case of larger evacuations, human coordinators are introduced mostly in isolated critical evacuation points. Due to uncertainty related with emergencies, there is a need for a real-time route recommendation system for dynamically determining evacuation routes in inner spaces based on the imminent or ongoing emergency.
Some typical reasons for evacuation include natural disasters like hurricanes, earthquakes, and wildfire, and adversarial actions like biological, nuclear, or chemical attacks. Evacuation routes may be subject to damage and destruction that may arise from natural catastrophes or action of intentional enemies. Due to the lack of the overall evacuation network information, there might be casualties caused by a too slow evacuation on hazardous routes. To avoid casualties and facilitate evacuation, we propose the usage of smart space technology for the introduction of route recommender systems into inner spaces. Smart spaces are spaces equipped with information processing, sensing and actuation facilities. These systems can provide assistance and facilitate the distribution of real-time evacuation information to evacuees through, e.g., LCD displays and smartphones.
A smart space can be modelled as an agent able to acquire and apply knowledge about itself and about its inhabitants in order to improve their well-being in the same. Moreover, a network of smart spaces can be implemented not only in buildings, but also at an urban scale. A city may be seen as a network of smart spaces and their inhabitants. In such a complex system, by using the information of the both, intelligent evacuation route recommendation is aimed at guiding people to safe areas considering individually optimal routes while optimizing global people flow based on safety conditions. The resulting interaction of a multitude of space agents and humans requires a scalable and responsive evacuation coordination approach.
In this paper, we propose a multi-agent based architecture for evacuation safety optimization that considers personal safety requirements in the recommended routes and ensures dynamic route update based on safety conditions within buildings and on the road infrastructure. The proposed model reduces exposure to hazard by dynamically updating evacuees’ routes in real time thus leading them to safe areas. Routes, evacuation areas, and safe areas are dynamically calculated and recalculated based on additional data, either realtime, historical, or other data added to the system, to compute optimal initial routes and redirect evacuees if changes in the emergency situation occur.
The rest of the paper is organized as follows. In Section 2, we consider crowd dynamics related with velocity, density and flow of pedestrians in inner spaces and State-ofthe-art evacuation control approaches. The proposed routerecommender architecture is presented in Section 3 with necessary details on its functioning when recommending safe and efficient evacuation routes. In Section 4, we formally define the distributed evacuation safety optimization problem and in Section 5, we describe the optimization approach. We conclude the paper in Section 6. 2
Total capacity is traditionally used to measure a building safety related with panic. It determines the total number of people who can fit in an edifice due to the physical space available or limitations set by law. However, it is not a sufficient parameter to avoid panic-related casualties in larger spaces since the capacity should be controlled for every larger constituent space in the building.
Evacuation routes may pass from larger to smaller spaces where overcrowding may occur. The formation of crowds, their size and granularity, and in general dynamics of crowds are crucial parameters in panic tolerant evacuation systems, see, e.g., Lujak and Ossowski [2016, In press 2016]. Overcrowding is the main reason for crowd crushing, injuries and mass fatalities that can be avoided by keeping density and velocity of the crowd under critical values. These values are influenced by multiple factors like, e.g., crowd profile (average age, physical conditions, presence of families with children and people with physical disabilities, etc.), nature of surface (e.g., concrete, mud, sand), presence of depressions in the walking surface or debris, gravel, rocks, mud, slopes, steps, etc.
Similar to vehicle flow, a macroscopic fundamental diagram for pedestrian traffic involves crowd traffic flow, density and velocity. The relationship between crowd density (number of people per square metre [#people=m2]) and crowd flow (number of people per metre per second [#people=(m s)]) is as follows: x = v( ) , where x is unit flow rate, is pedestrian density, and v( ) is pedestrian velocity [m=s], which in general depends on the pedestrian density , Figure 1.
One of the assumptions under which a proper shape of the fundamental diagram for pedestrian traffic is found, is that the congestion is spread homogeneously over the network, see, e.g., Knoop and Hoogendoorn [2013]. However, crowds rarely pack in regular formation. Knoop and Hoogendoorn Daamen et al. [2015] show the effect of inhomogeneity by deriving the so-called generalised macroscopic fundamental diagram. Hoogendoorn et al. [2011] have shown that a similar relation exists between the number of pedestrians in an area and the average flow in that area.
When there are few pedestrians on a walkway, i.e., low flow levels, there is space available to choose higher walking speeds. As crowd density increases, crowd flow increases only until critical density cr is reached, Figure 1. When a critical level of crowding occurs, maximal flow xmax occurs at some critical combination of velocity and density and separates the free flow (x xcr) from the congested one (x > xcr). With the increase of density above cr, people flow decreases until jam density where there is no more flow.
The critical density can be different for different events/crowds, see, e.g., Helbing and Johansson [2011]. Pedestrians can only circulate freely when crowds are no denser than approximately 10-15 persons per 10 m2. After this point, as crowd density increases the crowd flow rate falls. As individual movement becomes effortful because of closer interactions among evacuees, consequently also crowd velocity falls.
At high density, the crowd moves at the pace of the slowest individuals and there is the potential for overcrowding and personal injury. Evacuees’ safety decreases due to a higher possibility of panic related behaviors such as herding and stampeding. This is why we should aim not to let the people density pass the critical value at any area.
Regarding velocity, people should avoid running to avoid panic. Human walking speed can vary depending on various factors such as, e.g., height, age, terrain, weight, effort, etc. The average human walking speed is about 5.0 kilometres per hour and it ranges from 4.51 to 5.43 kilometres per hour, see, e.g., Rastogi et al. [2010]. This means that every space should be dynamically controlled detecting group formations that should not surpass these values at any position.
The crowd is unlikely to be evenly distributed throughout an open space. This can make it difficult to estimate the point at which the space is reaching its capacity limit. This is why, at high risk people densities, it is important to monitor and control the crowd movement in all constituent areas of the space of interest at all times.
Before the crowd reaches jam density max, we can detect spaces between evacuees by people tracking technologies. Tracking refers to data output from the technologies that capture the evacuees’ walking paths, e.g., WiFi by tracking their mobile phone signals, monocular and 3D stereo video, thermal imaging, infrared beams, and beacons. Each technology has its own set of challenges and benefits. For example, Wi-Fi and beacons are based on radio wave technologies, and are distinct by range and the accuracy of the signal capture process. 2.1
By the use of ambient intelligence, we can both monitor and influence crowd actions during evacuation. The space access restrictions can be changed dynamically depending on the area safety status. The information about the number of people to evacuate and their behaviour facilitates successful planning of evacuation and assessing necessary emergency services.
Application of ambient intelligence to evacuation control is a dynamic research area. In Mitleton-Kelly et al. [2013], a review on the utilisation of AmI (Ambient Intelligence) technology in providing support and enhancing crowd evacuation during emergencies and improving traffic management is presented. While most of the approaches treat congested networks and related k-shortest path problem, to the best of our knowledge, there is little work on dynamic real-time route optimization based on the safety of the paths’ constituent arcs, e.g., Stepanov and Smith [2009]. Most of the approaches take the binary approach for safety: the route is safe or not. In this paper ,we go a step forward and offer the optimization of the routes when the route safety is represented by a continuous variable.
Azhar Mohd et al. [2016] provide a review of intelligent evacuation management systems covering the aspects of crowd monitoring, crowd disaster prediction, evacuation modelling, and evacuation path guidelines. While the review deals with video and nonvideo based aspects of crowd monitoring and crowd disaster prediction, evacuation techniques are reviewed via the theme of soft computing, along with a brief review on the evacuation navigation path.
A literature review of network emergency evacuation modeling was presented in Xiongfei et al. [2010]. The linear programming approach uses time-expanded networks to compute the optimal evacuation plan and requires a user-provided upper bound on evacuation time. It suffers from high computational cost and may not scale up to large transportation networks in urban scenarios. In Lu et al. [2005], a capacity constrained route planner (CCRP) was proposed. It is a heuristics that produces sub-optimal solution for the evacuation planning problem. The CCRP models capacity as a time series and uses a capacity constrained routing approach to incorporate route capacity constraints. It addresses the limitations of the linear programming approach by using only the original evacuation network and it does not require prior knowledge of evacuation time. The CCRP algorithm produces high quality solutions and significantly reduces the computational cost compared to the linear programming approach that produces optimal solutions. CCRP is also scalable to the number of evacuees and the size of the network.
Desmet and Gelenbe [2013] propose an approach to the design and optimisation of emergency management schemes that offers fast estimates based on graph and probability models. They show that graph models can offer insight into the critical areas in an emergency evacuation and that they can suggest locations where sensor systems are particularly important and may require hardening.
In Bruce et al. [2008], a GIS-based system that determines evacuation routes for specific areas requiring evacuation is presented. Routes, evacuation areas, and safe areas are dynamically calculated and recalculated based on additional data to compute optimal initial routes and redirect evacuees if changes in the emergency situation occur. However, the model includes only two operative states of the roads: open, closed, and their travel time if open. The proposed system does not take into account relative safety variation of the route.
One possible way of personalizing evacuation notifications and communicating evacuation routes in indoor work environments over smartphones was presented in Aedo et al. [2012]. The paper considers efficient communication of predefined evacuation routes that can be personalized based on a type of the evacuee. However, this paper does not consider autonomous smart space route update based on the evacuation route real time safety conditions.
Safety conditions in the infrastructure change due to the evacuees’ behavior and the safety conditions caused by the hazard. The proposed architecture for safe evacuation routes’ recommendation integrates real-time evacuation route computation and situational awareness both at the evacuee and infrastructure level. The proposed architecture is made of the evacuee’s route recommender and overall smart route evacuation system, both relying on smart space technologies, Figure 2. In more detail:
Evacuee’s route recommender is meant as a mobile app that serves as an evacuee’s evacuation guide and an interaction bridge between the evacuee and the smart space while increasing situational awareness of the evacuee and recommending him/her evacuation route that avoids unsafe and highly congested spaces. The situation awareness solution should take into account data received through relevant sensors, evacuee’s current mental state and the capacity to follow the recommended route based on the momentary GPS coordinates and the actual area safety state, the evacuation infrastructure complexity (e.g., through Google Services), sensor readings and actual smart phone’s state (acceleration, velocity dynamics, orientation, etc.).
It uses smart phone sensors for knowledge extraction and communicates with nearby smart space infrastructure. Evacuee’s personal route recommender system (EPRS) is a CPS that works as an evacuee’s assistant that mediates the interaction between the evacuee and the Smart Space. The EPRS’s objective is that the evacuation be safe in complex evacuation situations so it adapts the evacuation route to the profile of the evacuee. Moreover, evacuee’s route recommender informs the evacuee about evacuation safety conditions and its malfunctions, battery, his/her performance, security alerts, crowdedness and related risks, alternative routes, etc.
Smart Route Evacuation System (SRES) monitors and manages the strategic behavior of the smart space network and in the case of necessity, performs corrective actions on the spaces in real-time. SRES informs the evacuee’s route recommender about the state of the evacuee’s physical environment, eventual contingencies, and evacuation performance. It establishes a personal evacuee profile record (based on personal data, presence of mobility disabilities, affiliate ties with other evacuees etc.). If necessary, it undertakes corrective actions on the evacuees and minimizes the performance degradation during sudden changes of safety conditions. Moreover, it monitors in real time and acts upon human-factor processes (presence of panic and related herding and stampeding behaviors) and predicts possible such states. If necessary, it reassigns routes in real-time to overcome contingencies, e.g., accidents and overcrowding.
Smart space is a Cyber-Physical System that integrates a series of sensors for obtaining data that passes through several levels of processing: data filtering by noise elimination, synchronization, abstraction at a semantic level, and data stream reasoning and knowledge extraction. The result of these processes is a situation awareness of the evacuees present in the smart space and knowledge sharing with other smart spaces and the smart route evacuation system. Some of the exemplary smart space situation awareness processes are: forecasting the hazard and evacuation dynamics with the specific evacuees’ profiles and hazard description, and networking with other smart spaces in the system for optimal route computation and contingency coverage. The identification of the evacuation situation is possible through image recognition, fusion of data received from different sensors,and sensor knowledge extraction. Due to increased energy, computational and memory requirements, those operations are performed in a distributed manner by infrastructure node agents connected with a computational cloud.
There are services available at the overall architecture level for knowledge extraction integrating the situation awareness from the evacuees’ route recommenders, the network of smart spaces, and the smart route evacuation system. These services serve for knowledge fusion from different databases and bottleneck routes’ resolution at the system’s level. They also keep track and evaluate evacuees’ profiles based on their historical data and present behavior. After knowledge-based data fusion, safety classification of scenarios gives us numeric values for each safety condition, Figure 2. 3.1
The proposed multi-agent system model is composed of four different agent categories: Evacuee agent is implemented on evacuees’ smart phones within an evacuee’s route recommender and it represents each evacuee in the evacuation process. Node agent represents a physical node of the smart space network on which it is installed and controls the evacuation flow on it. Node agents interact with their neighboring node agents and in a distributed way monitor and control smart space network and, if necessary, compute the safest efficient evacuation routes for evacuees in a distributed way. Moreover, node agents are situated in the smart space and serve as its computational nodes. Each node agent senses its assigned physical node and its incoming arcs. Furthermore, it can open and close automatic exit doors and broadcast information to evacuees within its realm.
Each node broadcasts its incoming arc travel times in regular intervals such that any node in the network has a complete information about arcs’ safety and costs. If a node detects the outage of one of its incident incoming arcs or neighbor nodes, it evacuates these areas and informs of the accident all neighboring nodes to deviate all traffic that has to be sent over this failed element. Origin agent is created on demand whenever there is at least one evacuee present in the realm of a node agent. It is a part of the smart route evacuation system that interacts with the evacuee agent through the evacuee’s route recommender, Figure 2. Origin agents perform the shortest safe route computation for the evacuees positioned in their realm of influence. This computation can be made in a centralized or distributed manner with infrastructure node agents.
Once when the safest efficient routes are computed, each origin agent assigns them to its evacuees based on individual evacuee’s characteristics (e.g., mobility disabilities, presence of families with children, etc.). Evacuees exchange the information only with their origin agent. As evacuees move in the infrastructure, their assigned origin agents change respectively.
evacuation manager or management team that has a broader knowledge of evacuation reasons and purposes. Their role is the description of key performance indicators based on the evacuation strategy.
No a priori global assignment information is available and the information is exchanged among these four agent types through neighbor to neighbor communication. In this way, we obtain a dynamic communication network operating in a multi-hop manner, which can recalculate evacuation routes based on the actual infrastructure safety conditions, evacuee congestion, and evacuation demand. 4
In this Section, we concentrate on finding the safest temporally efficient paths for each evacuee within the decision making module of the evacuee’s route recommender. With this aim, we consider a network of smart spaces in flow conditions where flow represents people transit pattern at steady state.
If real-time infrastructure information is available to evacuees and they can negotiate their routes (paths), it becomes possible to provide a selection of safe fair routes considering individual safety requirements. Therefore, we assume that the building and evacuees are monitored by strategically positioned sensors like, e.g., cameras, beacons, etc. The monitoring permits us both to recognize the evacuees’ behavior in respect to the suggested route and time window as to perceive the congestion and safety conditions of the infrastructure.
Furthermore, we assume that the people flow demand (i.e., evacuation requests) is known at the beginning of the time window. Based on the population density data, we determine the evacuation demand in the case of regional evacuation, while in smart building evacuation, we use the number of persons in each node to enumerate the requests.
In this way, each individual is seen as a unit element (particle) of the total people flow. We assume, furthermore, that the variations of the evacuation requests are negligible in an observed time window.
Starting from the above stated assumptions, let us define the infrastructure from which the people need to evacuate. Let G = (N; A) be a connected digraph representing the smart space network where N is the set of n vertices representing rooms, offices, halls, and in general, any portion of space within a building or other structure, separated by walls or partitions from other parts. In the case of larger spaces, for simplicity, the same are divided into regions represented by nodes completely connected by arcs a 2 A, where A is the set of m arcs a = (i; j), i; j 2 N and i 6= j, representing corridors or passages connecting nodes i and j. To simplify the notation, we assume that there is at most one arc in each direction between any pair of nodes.
Let O N and D N be the set of all origins and destinations respectively. We assume that there are nO origin nodes o 2 O disjoint from nD destination nodes d 2 D, where nO + nD n. Here, origins are all areas with evacuees inside the smart space network while destinations are their near safe exits.
In the definition of evacuation requests, we introduce fictitious sink node d^ 2 N that is adjacent to all the destination nodes (safe exits) by fictitious (dummy) arcs. In this way, we assume that graph G includes (together with actual nodes) also fictitious node d^and its incoming dummy arcs. Then, let w 2 W be a generic evacuation request from node o 2 O to fictitious sink node d^, where W is the set of all evacuation requests. Moreover, let R be a vector of cardinality nO representing evacuation demands from origins O towards fictitious safe exit d^, where Rod^ = Rw entry indicates the demand of evacuees in unit time period who request to leave origin node o 2 O to go to any of the safe exits d 2 D and, hence, to fictitious destination d^.
Our objective is, thus, to safely evacuate all the evacuees and if not possible, then as many people as possible within the allotted time period. To this aim, we should find optimal paths toward safe exits that minimize the evacuation time considering safety of the evacuation areas and thus avoiding the hazardous conditions that might result in fatalities and/or panic.
Let P w denote the set of available (simple) paths acceptable in terms of duration cost for each evacuation request w 2 W from origin ow 2 O to fictitious sink d^. By acceptable in terms of duration cost, we mean the paths from an origin o 2 O to safe exits d 2 D considering the upper bound in respect to the minimum duration among the paths for that origin. Furthermore, let P W be the set of all such paths.
Moreover, let us assume that safety status Sa is given for each arc a 2 A as a function of safety conditions that can be jeopardized by hazardous conditions as, e.g., natural disaster or terrorist attacks. We normalize it to the range [0; 1], such that 1 represents perfect conditions while 0 represents conditions impossible for survival, with a critical level for survival 0 < Scr < 1 depending on the combination of the previously a mentioned parameters. The data quantizing and fusion whose result is the arc safety status is not a topic of this paper. More details can be found in, e.g., Khaleghi et al. [2013]; Zervas et al. [2011].
The safety optimization problem is related with minimizing the risks caused by possible threats present on the arcs of the paths towards evacuees’ safe areas. If each constituent arc a of path k, k 2 Pw, w 2 W has safety Sa Scr, then path k is considered to be safe. On the contrary, when safety Sk on path k 2 Pw falls behind threshold value Scr, its harmful effects may threaten the evacuees’ lives. Thus, path k is considered unsafe and is jeopardized by the safety of its constituent unsafe arcs Ackr = fa : a 2 k; Sa < Scrg.
We are concerned about the number of these unsafe arcs and their safety values in the proposed paths. The proposed paths k 2 Pw for w 2 W should all satisfy safety conditions Sk Scr. However, when such a path is not available, a path with the maximal safety should be proposed where the travel time passed in the safety jeopardized areas should be minimized. Since arcs’ safety Sa can vary significantly within a proposed shortest path, we introduce a normalized path safety that maintains balance between the minimal and average arcs’ safety values:
s Sk = ja2kj
Y Sa; 8k 2 Pw; w 2 W: (1) a2k We want to find a path k 2 Pw for each w 2 W that maximizes (1) and minimizes path’s evacuation time tk, where tk = P ta2k and ta2k is the travel time of each arc a 2 k. Since the longest path problem is NP hard, we convert the safety maximization to jeopardy minimization problem, where jeopardy U k of path k is defined as U k = 1 Sk.
Then, the objective is to find a temporally efficient path with minimized jeopardy. For this reason, we search for a path with both minimized path’s jeopardy and the evacuation time.
Overall path safety for the evacuation request of each origin agent can then be computed by a product of the constituent paths’ safeties, Formula 2.
Sw = jksj Y S0k; 8k 2 Pw; w 2 W; (2)
Route resilience to contingencies should be provided through the computation of k- shortest paths in regular time intervals such that evacuees may be simply redirected to a backup path if the proposed path gets dangerous at some node. By computing k shortest paths from each origin and any intermediate node towards safe exits, we guarantee that the evacuees will be given viable alternatives based on the real-time safety updates. In this light, each origin agent computates k shortest paths towards safe exits that comply with the requirements on the maximal evacuation time. If an arc or node failure occurs, the route of affected evacuees is changed locally by the node agent that detects the failure.
In the case there are no available safe shortest routes for some origin node, it remains isolated. To resolve this issue, and to maintain the connectivity of origin nodes with safe exits at all times, in the shortest path computation, we multiply the travel time of unsafe arcs for which Sa < Scr by M Sa , where M is a very large number. In this way, the unsafe arcs will be included in the shortest paths only if there is no alternative path composed of safe arcs. Moreover, the number of the unsafe arcs will be minimal and their safety value will be maximal.
The dynamic component of the evacuation should be included in the computation since the original demand gets lower as the time passes. In this respect, we can assume that an arc is loaded with flow until all the evacuees haven’t evacuated the arc.
In the computation of k shortest paths, we use Yen’s algorithm. The time complexity of Yen’s algorithm is dependent on the shortest path algorithm used in the computation of the spur paths. For this purpose, we use Dijkstra algorithm. Dijkstra’s algorithm has a worse case time complexity of O(n2), but using a Fibonacci heap it becomes O(m + n log n).
After the shortest paths are found for each origin agent, the latter can decide of the evacuees’ assignment to the paths based on relevant personal characteristics that guarantee equality through an iterative auction. The negotiation through auctions is local between each origin agent and the evaccuees starting their travel at that origin, similar to Lujak et al. [2014]. 6
In this work we studied crowd evacuation coordination problem with the focus on smart spaces. We considered how route safety affects the selection of evacuation routes and their reconfiguration in the case of contingencies. In this context, we proposed an architecture for evacuation route safety optimization in large smart spaces that recommends safe and efficient situationally aware routes for evacuation.
If we consider multiple communicating open and closed spaces, this evacuation coordination approach can be potentially applied to different scales in emergency evacuation at a building, district, and urban level. In the future work, we plan to validate the model in relevant simulated scenarios. This work has been partially supported by the Autonomous Region of Madrid through grant “MOSI-AGILCM” (P2013/ICE-3019) co-funded by EU Structural Funds FSE and FEDER, “SURF” (TIN2015-65515-C4-4-R) funded by the Spanish Ministry of Economy and Competitiveness, and through the Excellence Research Group GES2ME (Ref. 30VCPIGI05) co-funded by URJC and Santander Bank.