Claims:1. A computer implemented method for planning location-sensitive probabilistic behavior based evacuation paths, in a building, from source nodes to sink nodes in a network of routes comprising a plurality of vertices and edges there between, the method comprising:
receiving input parameters comprising layouts of the building, a number of evacuees at each source node, a transit time, a predetermined time period and a maximum capacity associated with each edge and vertex;
defining multiple weak evacuation schedules at a state of the evacuees based on the layouts of the building, the number of evacuees, the transit time and the predetermined time period, wherein each of the multiple weak evacuation schedules is an evacuation schedule to evacuate one or more of the evacuees to the sink nodes in the predetermined time period;
defining a strong evacuation schedule at the state of the evacuees based on the multiple weak evacuation schedules and the maximum capacity associated with each edge and vertex, wherein the strong evacuation schedule is an evacuation schedule to evacuate a plurality of the evacuees to the sink nodes in the predetermined time period;
defining a mapping from the strong evacuation schedule to the multiple weak evacuation schedules to obtain a probabilistic behavior model, wherein the probabilistic behavior model represents constraints associated with behavior of the evacuees; and
planning, in real-time, an evacuation path for the building based on the probabilistic behavior model.

2. The method as claimed in claim 1, wherein the planned evacuation path represents an evacuation path with a probability distribution over the multiple weak evacuation schedules which provides an expected number of evacuees evacuated when the strong evacuation schedule is provided.

3. The method as claimed in claim 1, wherein planning the evacuation path for the building based on the probabilistic behavior model, comprises:
dividing the building into multiple sub-regions;
planning an evacuation path for each of the multiple sub-regions based on the probabilistic behavior model; and
merging the evacuation path for each of the multiple sub-regions to obtain the evacuation path for the building.

4. The method as claimed in claim 1, wherein the probabilistic behavior model comprises at least one of a delayed behavior model and a nearest-exit behavior model.

5. The method as claimed in claim 4, wherein the delayed behavior model represents delayed behavior of the evacuees following the strong evacuation schedule with multiple probabilities and wherein the nearest-exit behavior model represents behavior of the evacuees moving towards the nearest exit to the source node where they are located.

6. The method as claimed in claim 1, wherein the state of the evacuees is determined, in real-time, based on at least one of sensors in the building and global positioning system based mobile phones associated with the evacuees.

7. The method as claimed in claim 1, wherein defining the multiple weak evacuation schedules at the state of the evacuees based on the layouts of the building, the number of evacuees, the transit time and the predetermined time period, comprises:
solving an integer linear program on the layouts of the building, the number of evacuees, the transit time and the predetermined time period; and
defining the multiple weak evacuation schedules at the state of the evacuees upon solving the integer linear program on the layouts of the building, the number of evacuees, the transit time and the predetermined time period.

8. The method as claimed in claim 1, wherein defining the strong evacuation schedule at the state of the evacuees based on the multiple weak evacuation schedules and the maximum capacity associated with each edge and vertex, comprises:
solving an integer linear program on the multiple weak evacuation schedules and the maximum capacity associated with each edge and vertex; and
defining the strong evacuation schedule at the state of the evacuees upon solving the integer linear program on the multiple weak evacuation schedules and the maximum capacity associated with each edge and vertex.

9. A system for planning location-sensitive probabilistic behavior based evacuation paths, in a building, from source nodes to sink nodes in a network of routes comprising a plurality of vertices and edges there between, the system comprising:
at least one processor; and
a memory communicatively coupled to the at least one processor, wherein the memory comprises a evacuation path planning module to:
receive input parameters comprising layouts of the building, a number of evacuees at each source node, a transit time, a predetermined time period and a maximum capacity associated with each edge and vertex;
define multiple weak evacuation schedules at a state of the evacuees based on the layouts of the building, the number of evacuees, the transit time and the predetermined time period, wherein each of the multiple weak evacuation schedules is an evacuation schedule to evacuate one or more of the evacuees to the sink nodes in the predetermined time period;
define a strong evacuation schedule at the state of the evacuees based on the multiple weak evacuation schedules and the maximum capacity associated with each edge and vertex, wherein the strong evacuation schedule is an evacuation schedule to evacuate a plurality of the evacuees to the sink nodes in the predetermined time period;
define a mapping from the strong evacuation schedule to the multiple weak evacuation schedules to obtain a probabilistic behavior model, wherein the probabilistic behavior model represents constraints associated with behavior of the evacuees; and
plan, in real-time, an evacuation path for the building based on the probabilistic behavior model.

10. The system as claimed in claim 9, wherein the planned evacuation path represents an evacuation path with a probability distribution over the multiple weak evacuation schedules which provides an expected number of evacuees evacuated when the strong evacuation schedule is provided.

11. The system as claimed in claim 9, wherein the evacuation path planning module is configured to:
divide the building into multiple sub-regions;
plan an evacuation path for each of the multiple sub-regions based on the probabilistic behavior model; and
merge the evacuation path for each of the multiple sub-regions to obtain the evacuation path for the building.

12. The system as claimed in claim 9, wherein the probabilistic behavior model comprises at least one of a delayed behavior model and a nearest-exit behavior model.

13. The system as claimed in claim 12, wherein the delayed behavior model represents delayed behavior of the evacuees following the strong evacuation schedule with multiple probabilities and wherein the nearest-exit behavior model represents behavior of the evacuees moving towards the nearest exit to the source node where they are located.

14. The system as claimed in claim 9, wherein the state of the evacuees is determined, in real-time, based on information received from at least one of sensors in the building and global positioning system based mobile phones associated with the evacuees.

15. The system as claimed in claim 9, wherein the evacuation path planning module is configured to:
solve an integer linear program on the layouts of the building, the number of evacuees, the transit time and the predetermined time period; and
define the multiple weak evacuation schedules at the state of the evacuees upon solving the integer linear program on the layouts of the building, the number of evacuees, the transit time and the predetermined time period.

16. The system as claimed in claim 9, wherein the evacuation path planning module is configured to:
solve an integer linear program on the multiple weak evacuation schedules and the maximum capacity associated with each edge and vertex; and
define the strong evacuation schedule at the state of the evacuees upon solving the integer linear program on the multiple weak evacuation schedules and the maximum capacity associated with each edge and vertex.
, Description:
FORM 2

THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENT RULES, 2003

COMPLETE SPECIFICATION
(See Section 10 and Rule 13)

Title of Invention:
SYSTEMS AND METHODS FOR PLANNING LOCATION-SENSITIVE PROBABILISTIC BEHAVIOR BASED EVACUATION PATHS

Applicant:
Tata Consultancy Services Limited
A company Incorporated in India under the Companies Act, 1956
Having address:
Nirmal Building, 9th floor,
Nariman point, Mumbai 400021,
Maharashtra, India

The following specification particularly describes the embodiments and the manner in which it is to be performed.
TECHNICAL FIELD
The embodiments herein generally relate to evacuation paths and, more particularly, to systems and methods for planning location-sensitive probabilistic behavior based evacuation paths.
BACKGROUND
Generally, buildings with various capacities need to be evacuated during emergencies, such as fire, terror attack, the earthquake and so on. These emergencies have led to the development of work on building evacuation models in both operations research and other communities. The existing approaches are developed based on the assumption that in an emergency, people do what they are told. However, if you are in a building at location L and an emergency occurs and people are told to move along a given route to an exit e that the people know is further away than the nearest exit e0, then the people move towards the nearest exit e0 instead of the exit e. Also, people may exhibit delay in moving to the exit. Thus, creating a problem for planning an evacuation path during the emergency.

SUMMARY
The following presents a simplified summary of some embodiments of the disclosure in order to provide a basic understanding of the embodiments. This summary is not an extensive overview of the embodiments. It is not intended to identify key/critical elements of the embodiments or to delineate the scope of the embodiments. Its sole purpose is to present some embodiments in a simplified form as a prelude to the more detailed description that is presented below. In view of the foregoing, an embodiment herein provides a system and method for creating a predictive query index for natural language query interfaces.
In one aspect, a computer implemented method for planning location-sensitive probabilistic behavior based evacuation paths, in a building, from source nodes to sink nodes in a network of routes comprising a plurality of vertices and edges there between is disclosed. In an example embodiment, input parameters including layouts of the building, a number of evacuees at each source node, a transit time, a predetermined time period and a maximum capacity associated with each edge and vertex are received. Further, multiple weak evacuation schedules at a state of the evacuees are defined based on the layouts of the building, the number of evacuees, the transit time and the predetermined time period. Each of the multiple weak evacuation schedules is an evacuation schedule to evacuate one or more of the evacuees to the sink nodes in the predetermined time period. Furthermore, a strong evacuation schedule at the state of the evacuees is defined based on the multiple weak evacuation schedules and the maximum capacity associated with each edge and vertex. The strong evacuation schedule is an evacuation schedule to evacuate a plurality of the evacuees to the sink nodes in the predetermined time period. Moreover, a mapping from the strong evacuation schedule to the multiple weak evacuation schedules is defined to obtain a probabilistic behavior model, the probabilistic behavior model represents constraints associated with behavior of the evacuees. Also, an evacuation path for the building is planned, in real-time, based on the probabilistic behavior model.
In another aspect, a system for planning location-sensitive probabilistic behavior based evacuation paths, in a building, from source nodes to sink nodes in a network of routes including a plurality of vertices and edges there between is disclosed. In an example, the system includes one or more processors and a memory communicatively coupled to the processors. Further, the memory includes an evacuation path planning module. In an example implementation, the evacuation path planning module receives input parameters including layouts of the building, a number of evacuees at each source node, a transit time, a predetermined time period and a maximum capacity associated with each edge and vertex. Further, the evacuation path planning module defines multiple weak evacuation schedules at a state of the evacuees based on the layouts of the building, the number of evacuees, the transit time and the predetermined time period. Each of the multiple weak evacuation schedules is an evacuation schedule to evacuate one or more of the evacuees to the sink nodes in the predetermined time period. Furthermore, the evacuation path planning module defines a strong evacuation schedule at the state of the evacuees based on the multiple weak evacuation schedules and the maximum capacity associated with each edge and vertex. The strong evacuation schedule is an evacuation schedule to evacuate a plurality of the evacuees to the sink nodes in the predetermined time period. Moreover, the evacuation path planning module defines a mapping from the strong evacuation schedule to the multiple weak evacuation schedules to obtain a probabilistic behavior model, the probabilistic behavior model represents constraints associated with behavior of the evacuees. Also, the evacuation path planning module plans, in real-time, an evacuation path for the building based on the probabilistic behavior model.
It should be appreciated by those skilled in the art that any block diagram herein represent conceptual views of illustrative systems embodying the principles of the present subject matter. Similarly, it is appreciated that any flow charts, flow diagrams, state transition diagrams, pseudo code, and the like represent various processes which may be substantially represented in computer readable medium and so executed by a computing device or processor, whether or not such computing device or processor is explicitly shown.

BRIEF DESCRIPTION OF THE DRAWINGS
The embodiments herein are better understood from the following detailed description with reference to the drawings, in which:
FIG. 1 illustrates a block diagram of a system for planning location-sensitive probabilistic behavior based evacuation paths, according to an embodiment of the present disclosure;
FIG. 2A illustrate a layout of a building, according to an embodiment of the present disclosure;
FIGS. 2B-2E illustrate various exit graphs of the building, according to an embodiment of the present disclosure; and
FIG. 3 is a flow chart illustrating a method for planning location-sensitive probabilistic behavior based evacuation paths, according to an embodiment of the present disclosure.
DETAILED DESCRIPTION
The embodiments herein and the various features and advantageous details thereof are explained more fully with reference to the non-limiting embodiments that are illustrated in the accompanying drawings and detailed in the following description. The examples used herein are intended merely to facilitate an understanding of ways in which the embodiments herein may be practiced and to further enable those of skill in the art to practice the embodiments herein. Accordingly, the examples should not be construed as limiting the scope of the embodiments herein.
The term “people”, “person”, and “evacuees” are used interchangeably throughout the document. Further, the term “node” and “vertex” are used interchangeably throughout the document.
FIG. 1 illustrates a block diagram of a system 100 for planning location-sensitive probabilistic behavior based evacuation paths, according to an embodiment of the present disclosure. As shown in FIG. 1, the system 100 includes one or more processor(s) 102 and a memory 104 communicatively coupled to each other. The system 100 also includes interface(s) 106. Further, the memory 104 includes modules, such as an evacuation path planning module 108 and other modules. Although FIG. 1 shows example components of the system 100, in other implementations, the system 100 may contain fewer components, additional components, different components, or differently arranged components than depicted in FIG. 1.
The processor(s) 102 and the memory 104 may be communicatively coupled by a system bus. The processor(s) 102 may include circuitry implementing, among others, audio and logic functions associated with the communication. The processor(s) 102 may include, among other things, a clock, an arithmetic logic unit (ALU) and logic gates configured to support operation of the processor(s) 102. The processor(s) 102 can be a single processing unit or a number of units, all of which include multiple computing units. The processor(s) 102 may be implemented as one or more microprocessors, microcomputers, microcontrollers, digital signal processors, central processing units, state machines, logic circuitries, and/or any devices that manipulate signals based on operational instructions. Among other capabilities, the processor(s) 102 is configured to fetch and execute computer-readable instructions and data stored in the memory 104.
The functions of the various elements shown in the figure, including any functional blocks labeled as “processor(s)”, may be provided through the use of dedicated hardware as well as hardware capable of executing software in association with appropriate software. When provided by a processor, the functions may be provided by a single dedicated processor, by a single shared processor, or by a plurality of individual processors, some of which may be shared. Moreover, explicit use of the term “processor” should not be construed to refer exclusively to hardware capable of executing software, and may implicitly include, without limitation, digital signal processor (DSP) hardware, network processor, application specific integrated circuit (ASIC), field programmable gate array (FPGA), read only memory (ROM) for storing software, random access memory (RAM), and non-volatile storage. Other hardware, conventional, and/or custom, may also be included.
The interface(s) 106 may include a variety of software and hardware interfaces, for example, interfaces for peripheral device(s), such as a keyboard, a mouse, an external memory, and a printer. The interface(s) 106 can facilitate multiple communications within a wide variety of networks and protocol types, including wired networks, for example, local area network (LAN), cable, etc., and wireless networks, such as Wireless LAN (WLAN), cellular, or satellite. For the purpose, the interface(s) 106 may include one or more ports for connecting the system 100 to other devices or systems.
The memory 104 may include any computer-readable medium known in the art including, for example, volatile memory, such as static random access memory (SRAM) and dynamic random access memory (DRAM), and/or non-volatile memory, such as read only memory (ROM), erasable programmable ROM, flash memories, hard disks, optical disks, and magnetic tapes. The memory 104, may store any number of pieces of information, and data, used by the system 100 to implement the functions of the system 100. The memory 104 may be configured to store information, data, applications, instructions or the like for enabling the system 100 to carry out various functions in accordance with various example embodiments. Additionally or alternatively, the memory 104 may be configured to store instructions which when executed by the processor(s) 102 causes the system 100 to behave in a manner as described in various embodiments. The memory 104 includes the evacuation path planning module 108 and other modules. The module 108 and other modules include routines, programs, objects, components, data structures, etc., which perform particular tasks or implement particular abstract data types. The other modules may include programs or coded instructions that supplement applications and functions of the system 100.
In an example embodiment, the evacuation path planning module 108 plans location-sensitive probabilistic behavior based evacuation paths, in a building, from source nodes (e.g., a node at which people are located) to sink nodes (e.g., exits) in a network of routes including a plurality of vertices and edges there between. In this example embodiment, the evacuation path planning module 108 receives input parameters comprising layouts of the building, a number of evacuees at each source node, a transit time, a predetermined time period and a maximum capacity associated with each edge and vertex and the like. For example, the layouts of the building include floor plans of the building or building graphs.
Further, the evacuation path planning module 108 defines multiple weak evacuation schedules at a state of the evacuees based on the layouts of the building, the number of evacuees, the transit time and the predetermined time period. The state of the evacuees may be determined, in real-time, based on sensors in the building, global positioning system based mobile phones associated with the evacuees and the like. In an example implementation, the evacuation path planning module 108 solves an integer linear program on the layouts of the building, the number of evacuees, the transit time and the predetermined time period. Further, the evacuation path planning module 108 defines the weak evacuation schedules at the state of the evacuees upon solving the integer linear program on the layouts of the building, the number of evacuees, the transit time and the predetermined time period. For example, each of the weak evacuation schedules is an evacuation schedule to evacuate one or more of the evacuees to the sink nodes in the predetermined time period. The predetermined time period includes a deadline to evacuate the evacuees to the sink nodes. In other words, the weak evacuation schedule is a schedule which people generally tend to follow based on people’s intuition during an emergency situation and in this case, the schedule do not take into account the capacity of each edge or vertex.
Furthermore, the evacuation path planning module 108 defines a strong evacuation schedule at the state of the evacuees based on the weak evacuation schedules and the maximum capacity associated with each edge and vertex. In an example implementation, the evacuation path planning module 108 solves an integer linear program on the weak evacuation schedules and the maximum capacity associated with each edge and vertex. Further, the evacuation path planning module 108 defines the strong evacuation schedule at the state of the evacuees upon solving the integer linear program on the weak evacuation schedules and the maximum capacity associated with each edge and vertex. For example, the strong evacuation schedule is an evacuation schedule to evacuate a plurality of the evacuees to the sink nodes in the predetermined time period.
Moreover, the evacuation path planning module 108 defines a mapping from the strong evacuation schedule to the multiple weak evacuation schedules to obtain a probabilistic behavior model. For example, the probabilistic behavior model represents constraints associated with behavior of the evacuees. In this example, the probabilistic behavior model includes a delayed behavior model and/or a nearest-exit behavior model. The delayed behavior model may represent delayed behavior of the evacuees following the strong evacuation schedule with multiple probabilities. The nearest-exit behavior model may represent behavior of the evacuees moving towards the nearest exit to the source node where they are located.
Also, the evacuation path planning module 108 plans, in real-time, an evacuation path for the building based on the probabilistic behavior model. The planned evacuation path may represent an evacuation path with a probability distribution over the weak evacuation schedules which provide an expected number of evacuees evacuated when the strong evacuation schedule is provided. In an example, the evacuation path planning module 108 divides the building into multiple sub-regions. The evacuation path planning module 108 further plans the evacuation path for each of the multiple sub-regions based on the probabilistic behavior model. The evacuation path planning module 108 merges the evacuation path for each of the sub-regions to obtain the evacuation path for the building.
FIG. 2A illustrates a layout 200A of a building (i.e., a building graph), according to an embodiment of the present disclosure. For example, a building graph G is a tuple (V, E, EX, c, d) where V is the set of vertices, E ? V × V is the set of edges, c, d : E ?V ? Z are a capacity function and a travel time function, respectively, EX ? V is a set of exits, c(v) and c(e) represent a capacity of a vertex v and an edge e, respectively and d(e) is a time required to travel from one end of the edge e to other end, even if the edge is at full capacity. In an example, the following conditions are considered for the building graph G.
d (v) = 0 for all vertices v ? V, i.e., time needed to traverse a vertex is negligible. If not, a location previously modeled with a vertex v can instead be modeled by means of a new edge e whose endpoints are appropriately connected with the vertices adjacent to v and such that the capacity c(e) is greater than zero.
c (v) = |P| for all the vertices v ? EX, i.e., an exit has a capacity sufficient to contain all people. If a person reaches an exit, then the person is safe. For example, P is to denote the set of people in a building that must be evacuated, T = {0, 1…, tmax} is a set of all time points.
In the building graph 200A, square nodes denote exits, node labels denote name and capacity of a node and edge labels denote capacity and travel time for an edge. The capacity and travel time for edge e is shown by the pair (c (e), d (e)) next to e. Further, vertex labels (v, c (v)) indicate vertex name and capacity. Furthermore, persons p1, p2, p3, p4, p5, p6, p7 are located on vertices v1, v2, v3, v8, v9, v6, v10, respectively. The exits ex1 and ex2 are situated on v4 and v7, respectively.
Further as shown in FIG. 2A, at state s and time t = 0, p1, p2, p3, p4, p5, p6, p7 are located at vertices v1, v2, v3, v8, v9, v6, v10, respectively. For example, a state is a mapping s: P ? V ? E indicating where each person is at a fixed time point. At a given time, a person can be at a vertex or on an edge connecting two vertices. For instance, s (p1) = v1 and s (p7) = v10. Suppose p1 starts moving from v1 at t = 0 toward v5. For the edge e = (v1, v5), travel time d (e) = 2. At t = 1, the person may be on e (i.e., s (p1) = e at t = 1). At t = 2, the person may reach the vertex v5 or still stay on the edge e.

Further, multiple weak evacuation schedules (wes or WES) are defined at a state of the evacuees based on the layouts of the building, the number of evacuees, and the transit time. For example, an evacuation schedule is a sequence of states capturing positions of the people for each t ? T. In this example, evacuation planning may start at time 0 and end by tmax. As a WES may violate capacity constraints and not get all people to an exit by tmax. Therefore, an evacuation schedule (es) for person p is indicated by esp = s_1 (p),…,s_(t_max )(p) where s_t is the state es (t) for t ?Tand esp (t) denotes the state of person p at time t with reference to the es.
For example, a weak evacuation schedule (wes) is a mapping wes : T ? ST (let ST be a set of all possible states) such that:
?p ? P, if wes(t) = s’ and s’(p) = v1 and wes(t + 1) = s”, then one of the following is true: a) s”(p) = v1, b) ? e = (v1, v2) ? E such that s”(p) = e, c) ? e = (v1, v2) ? E such that s”(p) = v2. That is if a person is in a vertex v1 at time t, then at time t + 1 the person stays in v1 or moves to an edge incident on v1 or an adjacent vertex v2.
?p ? P, if wes(t) = s” and s”(p)= e = (v1, v2) ? E and wes(t + 1) = s” ,then one of the following is true: (a) s” (p) = e, (b) s” (p) = v1, (c) s”(p) = v2. That is, if a person is on an edge e = (v1, v2) at time t, then at time t + 1 the person stays in e or moves to one of the vertices incident on e.
?p ? P, , ?e = (v1, v2) ? E, if wes(t) = s’ and s’ (p) = v1 then wes(t + k) = s” and s” (p) = v2 only if d(e) = k. That is, if a person is in v1 at time t, then the person can reach an adjacent vertex v2 only if travel time d (e) elapses.
?p ? P, 0 = t’< t” =tmax, if wes (t’) = s’ and s”(p) ? EX and west” = s” then s”(p) s’(p). That is, if a person reaches an exit at some time point, then the person cannot go back to other places leaving the exit.

A below example table shows a wes1 for the building graph 200A of FIG. 2A. In the table, each column (except the leftmost) is a state. Rows report the evacuation schedule wes1 p for person p. Note that between t = 1 and t = 2, p3, p5 and p6 are crossing the edge (v10, v7) whose capacity is 2, thus violating a capacity constraint. Although it is not required by of wes, all evacuees reach an exit (at time point t = 4) with reference to wes1. Further, a wes2 in a table 2 differs from wes1 in following:
p2 as well as p5 and p6 move with a delay of one time point, while p7 immediately reach exit v7.
p1 does not reach any exit but passes through v2 and waits at v9.
The capacity constraint of edge (v10, v7) is not violated as only p5 and p6 are crossing this edge at the same time.
Person p wes1 (0)
p wes1 (1)
p wes1 (2)
p wes1 (3)
p wes1 (4)
p
p1 v1 v1, v5 v5 v5, v4 v4
p2 v2 v3 v7 v7 v7
p3 v3 v10 v7 v7 v7
p4 v8 v8, v5 v5 v5, v4 v4
p5 v9 v10 v7 v7 v7
p6 v6 v10 v7 v7 v7
p7 v10 v6 v6, v3 v3 v7
Table 1: Weak evacuation schedule wes1
Person p wes2 (0)
p wes2 (1)
p wes2 (2)
p wes2 (3)
p wes2 (4)
p
p1 v1 v1, v2 v2 v2, v9 v9
p2 v2 v2 v3 v7 v7
p3 v3 v10 v7 v7 v7
p4 v8 v8, v5 v5 v5, v4 v4
p5 v9 v9 v10 v7 v7
p6 v6 v6 v10 v7 v7
p7 v10 v7 v7 v7 v7
Table 2: Weak evacuation schedule wes2
Furthermore, a strong evacuation schedule is defined at the state of the evacuees based on the multiple weak evacuation schedules and the maximum capacity associated with each edge. In other words, a wes es is said to be a strong evacuation schedule (ses or SES) if the wes es satisfies the following additional constraints:
?t ? T, ?v ? V, if es (t) = s’ then | {p |p ? P, s’ (p) = v}| = c (v). The constraint indicates that a number of people in a vertex cannot exceed the capacity at any time.
?t ? T, ?e ? E, if es (t) = s’ then | {p |p ? P, s’ (p) = e}| = c (e), i.e., the number of people in an edge cannot exceed the capacity.
?p ? P, es (tmax) = s such that s (p) ? EX, i.e., every person must reach an exit by time tmax.
An example SES es is shown in a table below. In this table, the capacity constraints of all vertices and edges of the building graph 200A are satisfied.
Person p esp(0) esp(1) esp(2) esp(3) esp(4)
p1 v1 v1, v5 v5 v5, v4 v4
p2 v2 v3 v7 v7 v7
p3 v3 v7 v7 v7 v7
p4 v8 v8, v5 v5 v5, v4 v4
p5 v9 v10 v7 v7 v7
p6 v6 v10 v7 v7 v7
p7 v10 v7 v7 v7 v7
In an example implementation, the multiple weak evacuation schedules and the strong evacuation schedule are defined by solving an integer linear program. In this example implementation, the multiple weak evacuation schedules is defined upon solving the integer linear program on the layouts of the building, the number of evacuees, the predetermined time period and the transit time. Further, the strong evacuation schedule is defined upon solving the integer linear program on the multiple weak evacuation schedules and the maximum capacity at each edge and vertex.
In order to solve an integer linear program, the building graph G is simplified by considering edges e = (v, w) with travel time d (v, w) > 1 as three edges by introducing 2 virtual nodes e’ and e”. The e’ is a new vertex (on edge e) that can be reached in one time unit from v. Similarly, e” is the location on edge e that can reach w in one time unit. Thus, d(v,e’) = d((e”, w)) = 1, and d(e’,e”)= d((v, w)) - 2 (if d((v, w)) = 2 then d(e’,e”) = 0 indicating that the transition between the two virtual vertices can be instantaneous. A variable xv, t for each (v, t) ? V × T, indicating us the number of people at v at time t. Similarly, xv, w, t denotes the net number of people that leave v at time t and reach w at time t + 1 [when d ((v, w)) = 1]. If d((v, w)) = 2,xv,e,t denotes the net number of people who have left v along edge e at time t and are on e’ at time t + 1, xe,t denotes the net number of people who have left e’ at time t and reach e” at time t + d(e) - 2, and xe,w,t is the net number of people who have left e” at time t and are on the way towards w that may be reached at time t + 1.
In an example table below, a linear program for WES (LPW) (G) is used to denote a set of constraints (1)-(8), and a linear program for SES LPS (G) is used to denote a set of constraints (9)-(11). The solutions of LPW (G) and LPS* (G) = LPW (G) ? LPS (G), respectively, capture a set of all wes and ses, respectively, of the building graph G.

For example, in the above table, constraint (2) indicates that a number of people at e’ at time t + 1 equals the number at e’ at time t minus the number (i.e. xe, t) who left e’ for e” at time t plus the number who arrived (xv, e, t) from v. The constraint (1) indicates that a number of persons at a vertex v at time t + 1 equals a number of people at v at time t minus a number of people that moved from v at time t to an adjacent vertex or an edge plus a number of people that came from an adjacent vertex or an edge to v at time t. The constraint (3) applies to virtual vertex e” and can be read analogously by noting that moving from e’ to e” takes d (e) - 2 time. Thus, the constraint (3) indicates that the number of people at e” at time t + 1 equals a number of people at e” at time t minus a number of people that moved from e to w at time t plus a number of people that moved from e’ to e” at time t -d(e) + 2. Next, the constraint (4) says that no person can move from v to w, if the travel time of the edge e = (v, w) is greater than 1. Similarly, constraint (5) says that no person can move from e’ to e” if the travel time of the edge e = (v, w) is 1. Finally, the constraint (6) says that the number of people that reaches an exit never decreases if a person reaches an exit at some time t1, the person cannot move out of that exit at a later time t2. The constraints (7) and (8) ensure that xv,t , x e’,t and x e”,t are positive integers and xv,w,t , xv,e,t , xe,w,t and xe,t are integers.
Further, following propositions state that a set of solutions of LPW (G) corresponds to a set of weak and strong evacuation schedules.
Every wes ? W corresponds to a solution s of LPW (G) such that s (xv, t) is equal to the number of people on vertex v at time t according to wes (t) and s (x e’, t) + s (x e”, t) is equal to the number of people on edge e at time t according to wes (t), where s (x) is denoted as the value assigned by a solution s of LPW (G) to variable x. Thus indicating that every wesi corresponds to a solution si.
Every solution s of LPW (G) corresponds to the set of WESs W (s ) consisting of the WESs wes ? W such that ?t ? T, v ? V, e ? E it holds that wes(t) = s and |{p ? P|s(p) = v}| = s (xv,t ) and |{p ? P|s(p) = e}| = s (x e’,t ) + s (x e”,t ). Thus stating that every solution si of LPW (G) corresponds to a set of WESs that are equivalent.
Further, the constraints (9)-(11) of the above table are used to capture the meaning of strong evacuation schedules. In fact, the constraints (9) and (10), respectively, say that the vertex and edge capacities cannot be exceeded at any time t. Note that the number of people on edge e at time t is given by summing the number of people on the (virtual) vertices e’ and e” associated with e. Finally, the constraint (15) says that every person in P must reach some exit by time tmax.The following propositions mirror those stated above for wes, and states the correspondence between ses and solutions of LPS*(G) = LPW (G) ? LPS(G).
1) Every ses es ? S corresponds to a solution s of LPS*(G) = LPW (G) ? LPS(G) such that (i) s (xv,t ) is equal to a number of people on vertex v at time t according to es(t), and (ii) s (x e’,t ) + s (x e”,t ) is equal to a number of people on edge e at time t according to es(t).
2) Every solution s of LPW (G) ? LPS(G) corresponds to the set of SESs S (s ) consisting of the SESs es ? S such that ?t ? T, v ? V, e ? E it holds that es(t) = s and |{p ? P|s(p) = v}| = s (xv,t ) and |{p ? P|s(p) = e}| = s (x e’,t ) + s (x e”,t ).
Furthermore, a behavior model which is a function ß: S ? PW that associates every SES with a pdf over the set of all WESs is defined. For example, a pair (es, ß (es)) indicates a probability that if users follow SES es, then the users instead end up following the WESs in ß (es) with corresponding probabilities. In other words, a behavior model ß maps an SES es onto a set {wes1... wesk} of WESs with probability a1... ak, respectively with ai > 0. Further, a set of constraints Fß are used to define the behavior models. The constraints are as follows:
For all 1 = i = k, si of LPWi(G) corresponds to equivalent WES wesi, where k copies of LPW (G) include LPW 1(G),..., LPWk (G).
s of LPS* (G) = LPW (G) ? LPS (G) corresponds to equivalent SES es.
If Yi is a vector of the variables in LPWi (G), then si (Yi) = fi (s (X)) where X is a vector of variables in LPS* (G) and fi is a function. Basically, fi maps a solution of LPS* (G) corresponding to es to a solution of LPWi (G) corresponding to wesi.
In an example, the behavior models are expressed via the set Fß of constraints having the following syntax.
Syntax for behavior models: Given a building graph G, a vector X of variables in LPS*(G), vectors Yi (i ? [1..k]) of variables in i-th copy LPWi(G) of LPW (G), and a vector z1, . . . , zk of variables, Fß is the set of constraints having the following form:
• Yi = fi(X), ?i ? [1...k]
• zi = f l(X), ?i ? [1...k]
?_(i=1)^k¦?zi=1?
zi=0, ?i ? [1..k]
For example, the last two constraints ensure that the value assigned to variables z1…zk represent probabilities a1... ak. The first constraint ensures that solutions corresponding to SESs es are mapped to solutions corresponding to each wesi via some function fi. The second constraint ensures that the probability calculation ensures that wesi’s probability is ai. In this example, set Fß encodes behavior model ß: SES ? PWES if for each pair (es, ? = ß (es)) and for each wesi ? WES, there is a solution ? of Fß such that
? coincides with solution s of LPS*(G) on variables X (that is, for each variable x in X, it holds that ? (x) = s (x));
? coincides with solution si of LPWi (G) on variables Yi;
? (zi) = ? (wesi) = ai.
Example behavior models include a delayed behavior model and a nearest-exit behavior model. In an example, given an SES es as a value assignment for the variable in vector X. Associated with the SES es are k WESs wes1,.., wesk , represented as value assignments for variables Y1,...,Yk. Assume the delayed behavior model indicates that everyone follows WES wesi with a delay of ti with probability ai. That is, ß is such that for a given es, a pdf over the k WESs wesi assigning probability ai, for i = 1. . . k is obtained. In this case, time interval [0, tmax] is divided into [0, ti - 1] and [ti, tmax]. A first set of constraints in a table below considers the [0, ti - 1] time interval. For instance, the constraint y_(v,t,i)= xv,0 for t ? [0, ti - 1] indicates that the number of people at vertex v at time t according to wesi is the same as the number of people at vertex v according to the SES es at time 0. This is because the delay of ti time units has not finished yet. The second set of constraints in the table below considers the [ti, tmax] time interval. For instance, the constraint y_(v,t,i) = x_(v,t-t_i )says that a number of people at vertex v at time t according to wesi is the same as a number of people at v according to es at time t - ti, that is ti time points before t. Finally, constraints zi = ai specify the probabilities of WESs.

For example, given a strong evacuation schedule es, the nearest exit behavior model (NEBM) indicates that people follow the paths suggested by es with probability a, and follow the shortest paths from the vertices on which they are present to the nearest exits with probability 1- a. In other words, when the system generates a suggested schedule, people follow that schedule with probability a while others head for the nearest exit with probability (1- a). Again, determining a can be a challenge, however, a can be obtained from a series of regular evacuation drills where it is measured how many people go the nearest exist even if the people are told to go elsewhere and how many followed instructions and went to the exit the schedule told to go to, even if it is further away.

In the above table, for each vertex v € V, let ex (v) denote the exit nearest to v. Furthermore, let ? (v) = (v1=v, v2. . . vnv-1, vn ) be a shortest path from a vertex v=v1 to the nearest exit ex(v1). There may be several shortest paths from a given vertex v to an exit, but it is assumed that one of the shortest path is chosen and retuned by ? (v). As an example of shortest path, considering vertex v1 of FIG. 1, the travel time of the path p1 = (v1, v5, v4) to the exit ex1 = v4 is 4, while the travel time of the path p2 = (v1, v2, v3, v7) to the exit ex2 = v7 is 3. Hence, the shortest path for v1 is ? (v1) = p2 and the nearest exit is ex (v1) is ex2.
In the above table, Fß consists of two groups of constraints. The first group (first three constraints) of constraints corresponds to a weak evacuation schedule wes1 which indicates that people move in accordance with the evacuation plan suggested. The second group of constraints (all the remaining ones) corresponds to a weak evacuation schedule wes2 which indicates that people move towards the closest exit. The first group consists of the first three constraints in Fß which say that the number of people on vertices v (resp., e’, e”) at time t according to wes1 is equal to the number of people on v (resp., e’ and e”) at the same time according to the given strong evacuation schedule es.
The second group of constraints in Fß regards wes2 and consists of constraints 4 through 7. Specifically, the fourth constraint in Fß indicates that the number of people on vertex v j at time t, according to wes2, is equal to the sum of the number of people xvb, 0 that at time 0 are on any vertex vb such that there is shortest path ? (vb) starting in vb and reaching v j at time T (vb, v j) equal to t. The fifth constraint is similar to the previous one but regards vertices v j ? EX and thus the number of people on these vertices takes into account also people that reached the exit at previous time points. The sixth and seventh constraints in Fß concern virtual vertices e’ and e”, with e = (v j, w), i.e. when d (e) > 1. Assume that these vertices can be reached in 1 and d (e) - 1 time points starting from v j. Thus, the sixth (seventh) constraint in Fß says that the number of people on e’ (resp., e”) at time t is equal to the sum of the number of people xvb,0 that was at time 0 on any vertex vb such that there is shortest path ?(vb) starting in vb and reaching e (resp., e”) at time t equal to T (vb, v j )+ 1 (resp., T (vb, v j )+ d(e) - 1), where e is of the form (v j, w). We note that the constraints for et and ett are not needed if d (e) = 1 as in this case no person can reside on e. Finally, the last two constraints in Fß say that wes1 and wes2 are assigned the probability a and 1- a, respectively.
FIGS. 2B and 2C illustrate exit graphs EG (G, v4, 1) 200B and EG (G, v4, 2) 200C, respectively, for the building graph G shown in FIG. 2A. Further, FIGS. 2D and 2E show exit graphs EG (G, v7, 1) 200D and EG (G, v7, 2) 200E, respectively, for the building graph shown in FIG. 2A. Assume IN (EG (G, v, ?)) to denote the set of vertices vl of EG (G, v, ?) such that the minimum number of edges between vl and exit v equals ?. For instance, IN (EG (G, v4, 1)) = {v5}, IN (EG (G, v4, 2)) = {v1, v8}, IN (EG (G, v7, 1)) = {v3, v10}, and IN (EG (G, v7, 2)) = {v2, v6, v9}. The vertices in IN (G, v, ?) are referred to as the entry vertices of EG (G, v, ?). In an example, given Fß and an exit graph EG(G, v, ?), the projection ?EG(G,v,? )(Fß ) consists of
the inequalities Yi = fi(X ) (with i ? [1..k]) of Fß using only the x’s variables of LPS*(EG(G, v, ?)) and the y’s variables of LPWi(EG(G, v, ?)), as well as constants;
the inequalities ai = fi’(X ) (with i ? [1..k]) of Fß using only the variables of LPS*(EG(G, v, ?)) and constants, when the variable ai only depends on variables not belonging to LPS*(EG(G, v, ?)) the remaining variables are normalized to 1;
?_(i=1)^k¦? ai=1;? and
ai = 0, ?i ? [1...k].
In an example implementation, an evacuation path is planned based on the behavior model. In this example implementation, a copy Gl of the input building graph, an SES es to be returned initially set to the initial state for each time point, a variable time U (v) for each temporary exit vertex v representing the amount of time used to evacuate people from v (initially set to 0 for the exists of G) are received. In this example, vertices v ? tempEX are ordered in ascending order of timeU (v). Initially, tempEX contains the exits of the input building graph, then is updated using the entry vertices of the exit graphs processed. Further, nextEX represents the set of temporary exits that may be processed at subsequent iteration. At each iteration, a temporary exit v is extracted from tempEX. After finding ? = 1 such that at least [? • |IN (EG (G, v, ?))|], entry vertices of EG (Gl, v, ?) are occupied by someone, and constructing the exit graph Gv = EG (Gl, v, ?), the initial state s0 is restricted to the people in Gv by considering that the people on vertex v are those not already evacuated. Next, the projection Fv = ?Gv (Fß ) of the behavior model Fß to Gv is computed, and an evacuation problem with reference to the sub-evacuation problem (Gv, sv, Fv) is solved by finding a solution sv of IP((Gv, sv, Fv), D-timeU (v)). Further, the SES esv corresponding to solution sv is used to update the SES es being constructed. Let e (esv) be the time needed to evacuate the people in Gv by esv. Basically, updating es with esv means (i) using the information provided by esv to move persons p initially residing on a vertex of Gv towards v during the time period [0..e (esv)], and (ii) using the information provided by es to evacuate p according to an evacuation schedule that allowed to reach an exit starting from vertex v to another person p* that initially was on vertex v (a delay may be introduced to make es consistent with the capacities constraints).
Let es be a SES for G, and let esv be a SES for Gv. The evacuation schedule esl obtained by updating es with esv as follows.
?p ? P such that s0 (p) is not in Gv, and for each time point t ? T, it is the case that eslp (t) = esp (t) (i.e., nothing changes in esl for people not evacuated by esv).
?p ? P such that s0(p) is in Gv, it is the case that
eslp(t) = esVp (t) for t ? [0, e (esv)] (i.e., esl mimics esv during the time needed to move p from his initial state to the temporary exit v).
eslp(t) = esVp (e(esv)) for t ? [e(esv), e(esv) + d ], where d is the minimum delay for which no violation of the capacity constraints occurs (i.e., esl may require that p waits on the temporary exit v for d time points).
eslp(t) = esp* (t -e(esv) -d ) for t ? [e(esv) + d , D], where p* is any person such that s0(p*) = v and sD(p*) ? EX.
Upon updating es with esv, variable time U (v) is updated and the building graph Gl is updated by removing the sub graph Gv. Next, if timeU (v) > 0, the entry vertices of the examined temporary exit v are added to nextEX. These vertices are considered as temporary exits at the next iteration of the repeat loop. Further, variable time U is initialized for each entry vertex of Gv. After all temporary exits in tempEX have been examined, a new set tempEX is created by using the entry vertices collected in nextEX, and Gl is consistently updated by adding to it both the vertices in nextEX and edges of G incident on vertices in nextEX . The process ends when all vertices of Gl have been examined and returns SES es incrementally built during its execution.
In an example, consider the building graph G of FIG. 2A where persons residing on a vertex at time 0 are specified beside the vertex, the time interval T with tmax = 10, the deadline D = 5, and the delayed behavior model ß of 12. Let ? = 100%. At the beginning, the priority queue tempEX contains the exits v4 and v7 of G, both having priority given by timeU (v4) = timeU (v7) = 0. Assume that the (temporary) exit v4 is extracted. Then, since v4 is not an isolated vertex, ? = 2 is computed such that all the entry vertices of Gv4 = EG (Gl, v4, 2) (shown in FIG. 2C) are occupied by at least one person at time 0. Next, the restriction of s0 to the set {p1, p4} of persons residing on a vertex of Gv4 except on v4 is computed, that is, s0 (p1) = v1 and s0 (p4) = v8. Since timeU (v4) = 0 and es coincides with s0, according to which none is on v4, and no update of sv4 is performed on the basis of the persons on the (temporary) exist v4. After this, the projection Fv4 of the input delayed behavior model is computed and a SES esv4 is computed by solving IP ((Gv4, sv4, Fv4), D -timeU (v4)), where timeU (v4) = 0. Let esv4 be such that esp1v4 and esp4v4 is as reported in an example table below. So, es is updated as follows: esp1 = esp1v4 and esp4= esp4v4 and ?p (P\ {p1, p4}), t ? T, esp (t) = s0 (p).
Person p esv4 (0)
p esv4 (1)
p esv4 (2)
p esv4 (3)
p esv4 (4)
p esv4 (t), 5 = t = t
p max
p1
p4 v1
v8 (v1, v5)
(v8, v5) v5
v5 (v5, v4)
(v5, v4) v4
v4 v4
v4
Next variable timeU (v4) is set to 4, and the copy Gl of G is updated by removing all the vertices of Gv4 and the edges incident with the vertices (hence Gl have the shape of the graph in FIG. 2E). Further, D -timeU (v4) = 1 > 0), and variable nextEx is set to {v1, v8}, and timeU (v1) and timeU (v8) are assigned with 4.
At the second iteration, the (temporary) exit v7 ? tempEX is considered. Since each entry vertices of Gv7 = EG (Gl, v7, 1) (shown in FIG. 2D) contains some person, Gv7 is processed and a SES esv7 is computed by solving IP ((Gv7, sv7, Fv7), D-timeU (v7)), where timeU (v7) = 0. Let esv7 be such that esp3v7 (0) = v3, and esp3v7 (t) =v7 for t=1, esp7v7 (0) = v10, and esp7v7 (t) =v7 for t=1. Thus, es is updated as shown in an example table below, where p2, p5, and p6 are residing on the initial vertices yet.
Person p esp(0) esp(1) esp(2) esp(3) esp(4) esv4 (t), 5 = t = t
p max
p1 v1 (v1, v5) v5 (v5, v4) v4 v4
p2 v2 v2 v2 v2 v2 v2
p3 v3 v7 v7 v7 v7 v7
p4 v8 (v8, v5) v5 (v5, v4) v4 v4
p5 v9 v9 v9 v9 v9 v9
p6 v6 v6 v6 v6 v6 v6
p7 v10 v7 v7 v7 v7 v7

Further, variable timeU (v7) is set to 1, and the copy Gl of G is updated by removing all the vertices of Gv7 and the edges incident with them. That is Gl consists of the subgraph containing only vertices v2, v6, and v9 and the edges between these vertices. After this, variable nextEx is update to {v1, v3, v8, v10}, and time used (v3) and timeU (v10) are assigned with 1. Since all the temporary exits in tempEx have been examined, the set nextEX is used to update the priority queue tempEx and the copy Gl of G is updated by adding the vertices in tempEx as well the edges incident with the vertices. Then, a new while loop begins with the priority queue tempEx containing the vertices v3, v10, v1, v8 whose ordering is implied by timeU (v3) = timeU (v10) = 1,timeU (v1) = timeU (v8) = 4. Assume that at the first iteration of this loop, the temporary exit v3 is extracted from tempEx. Since the entry vertices v2 and v6 of Gv3 = EG (Gl, v3, 1) are occupied by some person, Gv3 is used for computing a SES. Further, the restriction s0v3 of the initial state s0 over the vertices of Gv3 except v3 is computed, obtaining s0v3 (p2) = v2 and s0v3 (p6) = v6. Next, as there is no person p€P such that esp (1) =v3, s0v3 is not updated to keep track of people residing on the temporary exit v3 and not evacuated yet. Thus, a SES esv3 is computed by solving IP ((Gv3, sv3, Fv3), D-timeU (v3)), where time used (v3) = 1. Let esv3 be such that esp2v3 (0) = v2, esp2v3 (1) = v3, and esp6v3 (0) = v6, esp6v3 (1) = (v6, v3), esp6v3 (2) = v3. Thus, es is updated where (i) p2 after implementing esp2v3 follows with no delay the evacuation schedule esp3 of p3 that initially was on the temporary exit v3 and reached an exit by the deadline according to es.
Person p esp(0) esp(1) esp(2) esp(3) esp(4) espv4 (t), 5 = t = tmax

p1 v1 (v1, v5) v5 (v5, v4) v4 v4
p2 v2 v3 v7 v7 v7 v7
p3 v3 v7 v7 v7 v7 v7
p4 v8 (v8, v5) v5 (v5, v4) v4 v4
p5 v9 v9 v9 v9 v9 v9
p6 v6 v3 v3 v7 v7 v7
p7 v10 v7 v7 v7 v7 v7
Also, variable timeU (v3) is incremented by 2 (the amount of time needed to esv3 to evacuate people in Gv3 towards v3, thus timeU (v3) = 3, and the copy Gl of G is updated by removing all the vertices v2, v3, v6 of Gv3 and the edges incident with the vertices. Hence, Gl consists of the subgraph containing only vertices v1, v8, v9 and v10. Further, variable nextEx is set to {v2, v6}, and timeU (v2) and timeU (v6) are assigned with 3.
At the next iteration of the while loop, vertex v10 with timeU (v10) = 1 is extracted from the priority queue, and Gv10 = EG (Gl, v10, 1) is used for computing a SES esv10 by solving IP ((Gv10, s0v10, Fßv10), D -timeU (v10)). Let esv10 be such that esp5v10 (0) =v9 and esp5v10 (1) =v10.
Furthermore, timeU (v10) is incremented by 1, thus obtaining timeU (v10) = 2, and the copy Gl of G is updated by removing the vertices v9 and v10 of Gv10, and the edges incident with them. Thus Gl consists of the subgraph containing only the (isolated) vertices v1, v8. Then, set nextEx is augmented with the entry vertex v9 of Gv10, obtaining nextEx = {v2, v6, v9}, and timeU (v9) are assigned with 2. During the subsequent iterations of the while loop, only the isolated vertices v1, v8 are extracted from the priority queue tempEX. After the execution of the while loop, the priority queue tempEX is updated with the items v2, v6, v9 2 nextEx. Then, v2, v6, v9 and the edges between the vertices are added to G0 that consists of the isolated vertices v1 and v8. Hence, all the vertices in G0 are temporary exists and the process ends after returning the SES es shown in an example table below.
Person p esp(0) esp(1) esp(2) esp(3) esp(4) espv4 (t), 5 = t = tmax

p1 v1 (v1, v5) v5 (v5, v4) v4 v4
p2 v2 v3 v7 v7 v7 v7
p3 v3 v7 v7 v7 v7 v7
p4 v8 (v8, v5) v5 (v5, v4) v4 v4
p5 v9 v10 v7 v7 v7 v7
p6 v6 v3 v3 v7 v7 v7
p7 v10 v7 v7 v7 v7 v7
FIG. 3 is a flow chart 300 illustrating a method for planning location-sensitive probabilistic behavior based evacuation paths, according to an embodiment of the present disclosure. In an example embodiment, the flowchart 300 illustrates a method for planning location-sensitive probabilistic behavior based evacuation paths, in a building, from source nodes to sink nodes in a network of routes including a plurality of vertices and edges there between. At block 302, input parameters including layouts of the building, a number of evacuees at each source node, a transit time, a predetermined time period and a maximum capacity associated with each edge and vertex and the like are received. For example, the layouts of the building include floor plans of the building.
At block 304, multiple weak evacuation schedules at a state of the evacuees are defined based on the layouts of the building, the number of evacuees, the transit time and the predetermined time period. The state of the evacuees may be determined, in real-time, based on sensors in the building, global positioning system based mobile phones associated with the evacuees and the like. In an example implementation, an integer linear program is solved on the layouts of the building, the number of evacuees, the transit time and the predetermined time period. Further, the weak evacuation schedules at the state of the evacuees are defined upon solving the integer linear program on the layouts of the building, the number of evacuees, the transit time and the predetermined time period. For example, each of the weak evacuation schedules is an evacuation schedule to evacuate one or more of the evacuees to the sink nodes in a predetermined time period. The predetermined time period includes a deadline to evacuate the evacuees to the sink nodes.
At block 306, a strong evacuation schedule at the state of the evacuees is defined based on the weak evacuation schedules and the maximum capacity associated with each edge and vertex. In an example implementation, an integer linear program is solved on the weak evacuation schedules and the maximum capacity associated with each edge and vertex. Further, the strong evacuation schedule at the state of the evacuees is defined upon solving the integer linear program on the weak evacuation schedules and the maximum capacity associated with each edge and vertex. For example, the strong evacuation schedule is an evacuation schedule to evacuate a plurality of the evacuees to the sink nodes in the predetermined time period.
At block 308, a mapping is defined from the strong evacuation schedule to the multiple weak evacuation schedules to obtain a probabilistic behavior model. For example, the probabilistic behavior model represents constraints associated with behavior of the evacuees. In this example, the probabilistic behavior model includes a delayed behavior model and/or a nearest-exit behavior model. The delayed behavior model may represent delayed behavior of the evacuees following the strong evacuation schedule with multiple probabilities. The nearest-exit behavior model may represent behavior of the evacuees moving towards the nearest exit to the source node where they are located.
At block 310, an evacuation path for the building is planned, in real-time, based on the probabilistic behavior model. The planned evacuation path may represent an evacuation path with a probability distribution over the weak evacuation schedules which provides an expected number of evacuees evacuated when the strong evacuation schedule is provided. In an example, the building is divided into multiple sub-regions. The evacuation path is then planned for each of the multiple sub-regions based on the probabilistic behavior model. The evacuation path for each of the sub-regions is then merged to obtain the evacuation path for the building.
Even though the above evacuation path planning is described with respect to a building, one can envision that the above evacuation path planning can be applicable to any region of interest.
The order in which the method(s) are described is not intended to be construed as a limitation, and any number of the described method blocks can be combined in any order to implement the above method, or an alternative method. Additionally, individual blocks may be deleted from the methods without departing from the spirit and scope of the subject matter described herein. Furthermore, the above method can be implemented in any suitable hardware, software, firmware, or combination thereof.
In an implementation, one or more of the method(s) described herein may be implemented at least in part as instructions embodied in non-transitory computer-readable storage medium and executable by one or more computing devices. In general, a processor (for example a microprocessor) receives instructions, from a non-transitory computer-readable medium, for example, a memory, and executes those instructions, thereby performing one or more method(s), including one or more of the method(s) described herein. Such instructions may be stored and/or transmitted using any of a variety of known computer-readable media.
It is, however to be understood that the scope of the protection is extended to such a program and in addition to a computer-readable means having a message therein; such computer-readable storage means contain program-code means for implementation of one or more steps of the method, when the program runs on a server or mobile device or any suitable programmable device.
The preceding description has been presented with reference to various embodiments. Persons having ordinary skill in the art and technology to which this application pertains appreciate that alterations and changes in the described structures and methods of operation can be practiced without meaningfully departing from the principle, spirit and scope.