Sign In to Follow Application
View All Documents & Correspondence

Methods And Systems For Planning Evacuation Paths

Abstract: Methods and systems for planning evacuation paths are provided to identify an optimum path for evacuation of every evacuee from a region of interest. Methods of the instant disclosure ensure that for each suggested evacuation path, the capacity of any edge on the path is not exceeded and the evacuation time is minimum. A path once identified is maintained. A randomized behavior model is employed to re-distribute evacuees in emergency situations. This provides optimum evacuation time that employs an improved technique with optimized run time and evacuation time after taking into consideration herd behavior.

Get Free WhatsApp Updates!
Notices, Deadlines & Correspondence

Patent Information

Application #
Filing Date
20 August 2015
Publication Number
08/2017
Publication Type
INA
Invention Field
MECHANICAL ENGINEERING
Status
Email
ip@legasis.in
Parent Application
Patent Number
Legal Status
Grant Date
2022-09-16
Renewal Date

Applicants

Tata Consultancy Services Limited
Nirmal Building, 9th Floor, Nariman Point, Mumbai 400021, Maharashtra, India.

Inventors

1. PAL, Arindam
Tata Consultancy Services Limited, Innovation Lab - Kolkata Building 1B, Ecospace Plot - IIF/12, New Town, Rajarhat, Kolkata - 700156,West Bengal, India
2. MISHRA, Gopinath
Tata Consultancy Services Limited, Innovation Lab - Kolkata Building 1B, Ecospace Plot - IIF/12, New Town, Rajarhat, Kolkata - 700156,West Bengal, India
3. MAZUMDAR, Subhra
Tata Consultancy Services Limited, Innovation Lab - Kolkata Building 1B, Ecospace Plot - IIF/12, New Town, Rajarhat, Kolkata - 700156,West Bengal, India

Specification

Claims:WE CLAIM: A computer implemented method for planning evacuation paths, in a region of interest, from source nodes to sink nodes in a network of routes comprising a plurality of nodes (n), vertices and edges (E) therebetween, said method comprising: receiving input parameters comprising layouts of the region of interest, number of evacuees (p), transit time (T) and maximum capacity (C) associated with each edge (E); defining the network of routes based on the received input parameters; identifying shortest paths (P) from each source to a sink in increasing order of transit time associated with the routes constituting the network of routes; eliminating at least one of a node or an edge associated with each identified shortest path to obtain a residual network of routes; computing combined evacuation time (CET) and reserve capacity at each of the nodes and edges in the residual network of routes; iteratively performing steps (c) through (e) until at least one condition of there is a sink node reachable from a source node; the transit time of identified shortest path is less than combined evacuation time (CET); and there is a path identified for each evacuee; is satisfied; and computing number of evacuees to be distributed along each of the identified paths. The computer implemented method of claim 1, further comprising re-distributing evacuees according to a probabilistic behavioral model. The computer implemented method of claim 1, wherein the step of defining the network of routes includes defining the received input parameters in the form of a graph. The computer implemented method of claim 1, wherein the CET is a function of maximum capacity (C), the transit time (T) and the number of evacuees (p). The computer implemented method of claim 1, wherein the step of computing number of evacuees satisfies a relationship that is based on the number of evacuees x_ialong path P_i havingT_i transit time and maximum capacity C_i. The computer implemented method of claim 1, wherein the step of computing number of evacuees satisfies a relationship T_i+x_i/C_i -1=CET, wherein x_i is the number of evacuees along path P_i havingT_i transit time and maximum capacity C_i. The computer implemented method of claim 2, wherein the step of re-distributing evacuees further comprises a step of computing expected evacuation time satisfies a relationship based on transit time T_i along Path P_i, probability that an evacuee follows the shortest path to the nearest sink(1- a), probability that an evacuee follows suggested patha, number of evacuees x_i along path P_i and number of identified paths k. The computer implemented method of claim 2, wherein the step of re-distributing evacuees further comprises a step of computing expected evacuation time according to a relationship: E[T]=max?( T_1+(1- a)n/C_1 – 1, max2= i = k(T_i+(ax_i)/C_i -1)) wherein, E[T] is expected evacuation time, T_i is transit time along Path P_i, (1- a) is the probability that an evacuee follows the shortest path to the nearest sink, a is the probability that an evacuee follows suggested path, x_i is the number of evacuees along path P_i and k is the number of identified paths. The computer implemented method of claim 2, wherein the step of re-distributing evacuees is preceded by the step of receiving location information pertaining to each of the evacuees. A system for planning evacuation paths, in a region of interest, from source nodes to sink nodes in a network of routes comprising a plurality of nodes (n), vertices and edges (E) therebetween, said system comprising: one or more processors; a communication interface device; one or more internal data storage devices operatively coupled to the one or more processors for storing: an input module configured to receive input parameters comprising layouts of the region of interest, number of evacuees (p), transit time (T) and maximum capacity (C) associated with each edge (E); a network module configured to define the network of routes based on the received input parameters; a path discovery module configured to identify shortest paths (P) from each source to a sink in increasing order of transit time associated with the routes; eliminate at least one of a node or an edge associated with each identified shortest path to obtain a residual network of routes and further configured to compute combined evacuation time (CET) and reserve capacity at each of the nodes and edges in the residual network of routes; and an evacuee distributing module configured to compute number of evacuees to be distributed along each of the identified paths. The system of claim 10 further comprising a path optimizer module configured to re-distribute evacuees according to a probabilistic behavioral model. The system of claim 10, wherein the input module is further configured to receive location information pertaining to each of the evacuees from at least one sensor configured to detect location of the evacuees either directly or indirectly. The system of claim 10, wherein the network module is further configured to define the received input parameters in the form of a graph. The system of claim 10, wherein the path identifier module is further configured to compute the CET as a function of maximum capacity (C) the transit time (T) and the number of evacuees (p). The system of claim 10, wherein the evacuee distributing module is further configured to compute the number of evacuees such that a relationship that is based on the number of evacuees x_ialong path P_i havingT_i transit time and maximum capacity C_i is satisfied. The system of claim 10, wherein the evacuee distributing module is further configured to compute the number of evacuees such that a relationshipT_i+x_i/C_i -1=CET, is satisfied, wherein x_i is the number of evacuees along path P_i having transit time T_iand maximum capacity C_i. The system of claim 11, wherein the path optimizer module is further configured to compute expected evacuation time satisfies a relationship based on transit time T_i along Path P_i, probability that an evacuee follows the shortest path to the nearest sink (1- a), probability that an evacuee follows suggested path a, number of evacuees x_i along path P_i and number of identified paths k. The system of claim 11, wherein the path optimizer module is further configured to compute expected evacuation time according to a relationship: E[T]=max?( T_1+(1- a)n/C_1 – 1, max2= i = k(T_i+(ax_i)/C_i -1)) wherein, E[T] is expected evacuation time, T_i is transit time along Path P_i, (1- a) is the probability that an evacuee follows the shortest path to the nearest sink, a is the probability that an evacuee follows suggested path, x_i is the number of evacuees along path P_i and k is the number of identified paths. The system of claim 10further comprising a termination module configured to check for at least one termination condition selected from the group consisting of: there is a sink node reachable from a source node; the transit time of identified path is less than combined evacuation time (CET); and there is a path identified for each evacuee. The system of claim 10further comprising an annunciator module configured to provide at least one of audio and video annunciations pertaining to suggested identified path for each evacuee. , 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: METHODS AND SYSTEMS FOR PLANNING 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 planning evacuation paths, and more particularly to systems and methods involving probabilistic behavior models. BACKGROUND Evacuation planning is a critical aspect that involves movement of people away from threat or actual occurrence of hazard such as natural disasters, terrorist attacks, fires and bombs. Safe evacuation of a large number of people in a timely manner is a major challenge for building administrators. There have been several endeavors in this domain to provide methods for planning evacuation paths. Linear Programming (LP) based polynomial time techniques for evacuation problem uses time-expanded graphs for the network, where the expression for time complexity makes it non-scalable even for mid-sized networks. Capacity Constrained Route Planner (CCRP) techniques use generalized shortest path technique to find shortest paths from any source to any sink, provided that there is enough capacity available on all nodes and edges of the path. Space complexity and unnecessary expansion of source nodes in each iteration are two main disadvantages of CCRP. CCRP++ runs faster than CCRP but the quality of solution is not good, because availability along a path may change between the times when paths are reserved and when they are actually used. Network flow based approaches are based on minimum cost transshipment and earliest arrival transshipment. The minimum cost approach does not consider the distances between evacuees and exits. It may fail if there are exits very far away. Problems also arise if a lot of exits share the same bottleneck edges. The earliest arrival approach uses an optimal flow over time and thus does not suffer from these problems. But the exit assignment computed by the earliest arrival approach may not be optimal. There is a need therefore for methods and systems that address the above and other possible drawbacks and limitations of the currently used methods and systems for planning evacuation paths. SUMMARY Systems of the present disclosure identifies shortest paths from at least one source to a sink in increasing order of transit time in each iteration till the transit time of the currently identified path exceeds the combined evacuation time CET of the previously added set of paths. Also, systems of the present disclosure are not required to identify all possible paths from a source to a sink; if a path is added in any iteration, it remains till the end. The combined evacuation time CET after each iteration will be monotonically non-increasing. In an emergency, people tend to panic and do not always follow suggested paths. To address this issue, system of the present disclosure includes a simple randomized behavior model to obtain a minimum expected evacuation time. Methods and systems are described that enable planning of evacuation paths, in a region of interest, from source nodes to sink nodes in a network of routes including a plurality of nodes (n), vertices and edges (E) therebetween. In an aspect, a computer implemented method of the present disclosure includes receiving input parameters comprising layouts of the region of interest, number of evacuees (p), transit time (T) and maximum capacity (C) associated with each edge (E); defining the network of routes based on the received input parameters; iteratively performing the steps of identifying shortest paths (P) from each source to a sink in increasing order of transit time associated with the routes constituting the network of routes, eliminating at least one of a node or an edge associated with each identified path to obtain a residual network of routes, and computing combined evacuation time (CET) and reserve capacity at each of the nodes and edges in the residual network of routes, until at least one termination condition is satisfied; and computing number of evacuees to be distributed along each of the identified paths. In an embodiment, the method described herein above further includes re-distributing evacuees according to a probabilistic behavioral model. In an embodiment, the step of computing number of evacuees satisfies the relationshipT_i+x_i/C_i -1=CET, wherein x_i is the number of evacuees along path P_i havingT_i transit time and maximum capacityC_i. In an embodiment, the step of re-distributing evacuees further includes a step of computing expected evacuation time according to the relationship: E[T]=max?( T_1+(1- a)n/C_1 – 1, max2= i = k(T_i+(ax_i)/C_i -1)) wherein, E[T] is expected evacuation time, T_i is transit time along Path P_i, (1- a) is the probability that an evacuee follows the shortest path to the nearest sink, a is the probability that an evacuee follows suggested path, x_i is the number of evacuees along path P_i and k is the number of identified paths. In another aspect, there is provided a system for planning evacuation paths, in a region of interest, from source nodes to sink nodes in a network of routes comprising a plurality of nodes (n), vertices and edges (E) therebetween, the system comprising one or more processors; a communication interface device; one or more internal data storage devices operatively coupled to the one or more processors for storing: an input module configured to receive input parameters comprising layouts of the region of interest, number of evacuees (p), transit time (T) and maximum capacity (C) associated with each edge (E); a network module configured to define the network of routes based on the received input parameters; a path identifier module configured to identify shortest paths (P) from each source to a sink in increasing order of transit time associated with the routes; eliminate at least one of a node or an edge associated with each identified path to obtain a residual network of routes and further configured to compute combined evacuation time (CET) and reserve capacity at each of the nodes and edges in the residual network of routes; and an evacuee distributing module configured to compute number of evacuees to be distributed along each of the identified paths. In an embodiment, the system as described herein above can further comprise a path optimizer module configured to re-distribute evacuees according to a probabilistic behavioral model. In yet another aspect, there is provided a computer program product for processing data, comprising a non-transitory computer readable medium having program instructions embodied therein for: receiving input parameters comprising layouts of the region of interest, number of evacuees (p), transit time (T) and maximum capacity (C) associated with each edge (E); defining the network of routes based on the received input parameters; iteratively performing the steps of discovering shortest paths (P) from each source to a sink in increasing order of transit time associated with the routes, eliminating at least one of a node or an edge associated with each discovered path to obtain a residual network of routes, and computing combined evacuation time (CET) and reserve capacity at each of the nodes and edges in the residual network of routes, until at least one termination condition is satisfied; computing number of evacuees to be suggested to follow a particular discovered path; and re-distributing evacuees according to a probabilistic behavioral model. BRIEF DESCRIPTION OF THE DRAWINGS The embodiments herein will be better understood from the following detailed description with reference to the drawings, in which: FIG.1 illustrates an exemplary building graph defined on the basis of input parameters received by a system of the present disclosure; FIG. 2 illustrates a portion of an exemplary graph showing parallel flows sent on non edge-disjoint paths; FIG. 3 illustrates an exemplary block diagram of a system for planning evacuation paths in accordance with an embodiment of the present disclosure; FIG. 4 is an exemplary flow diagram illustrating a computer implemented method for planning evacuation paths using the system of FIG. 3 in accordance with an embodiment of the present disclosure; FIG. 5 is a graphical illustration of evacuation time versus number of nodes for Capacity Constrained Route Planner (CCRP) and Single source Single sink Evacuation Problem (SSEP) of the present disclosure; and FIG. 6 is a graphical illustration of run time of the technique of the present disclosure versus number of nodes for Capacity Constrained Route Planner (CCRP) and Single source Single sink Evacuation Problem (SSEP) of the present disclosure. 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 will be 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. 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. For ease of explanation, the description of systems and methods of the present disclosure is provided with reference to a non-limiting example of Single source Single sink Evacuation Problem (SSEP) like evacuating people in an emergency as soon as possible from an auditorium having only one exit in the building. It may be understood that systems and methods of the present disclosure can find applicability in Multiple Source Multiple Sink scenarios with suitable adaptations. Referring now to the drawings, and more particularly to FIGS. 1 through 6, where similar reference characters denote corresponding features consistently throughout the figures, there are shown preferred embodiments and these embodiments are described in the context of the following exemplary system and method. FIG.1 illustrates exemplary building graph 100 defined on the basis of input parameters received by a system of the present disclosure. The building floor plan can be represented as a graph G = (V, E), where V and E are the set of vertices and edges respectively. The number of vertices and edges are n and m respectively. Nodes represent rooms, lobbies and intersection points and arcs represent corridors, hallways, staircases and the like. Some nodes in the building having significant number of people are modeled as source nodes. The exits of a building are represented as sink nodes. Each node has a capacity, which is the maximum number of people that can stay at that location at any given time and an occupancy, which is the number of people currently occupying the location. p is the total number of people who needs to be evacuated or the evacuees. Each edge has a capacity, which is the maximum number of people that can traverse the edge per unit time and a travel time, which is the time needed to travel from one node to another node along that edge. The expression “region of interest” as referred to in the present disclosure pertains to region or premise of threat or actual occurrence of hazards such as natural disasters, terrorist attacks, fires and bombs. The expression “evacuee” as referred to in the present disclosure pertains to people who are intended to be evacuated from the “region of interest” as described herein above and may be used interchangeably with the expression “evacuee” in the context of the present disclosure. The expression “position detection device” as referred to in the present disclosure refers to at least one of sensors, wearable devices, mobile devices including smart phones, hand-held devices, portable devices and PDAs that can enable detection of location information pertaining to an evacuee. Sensors referred to in this context may be heat sensors, motion sensors or location sensors based on Wi-Fi or any other means known in the art. Accordingly, in the context of the present disclosure, the expressions “position detection device” and “sensors” may be used interchangeably to refer to device that provides location information either directly or indirectly. Again, expressions used interchangeably throughout the description include {graph, network}, {node, vertex}, {edge, arc}, and {path, route}. The expression “transit time” as referred to in the present disclosure pertains to the sum of the transit times of all the edges in path P from source s to sink t, and is denoted as T(P). The expression “destination arrival time of a path” as referred to in the present disclosure is the time required by a person to move from sources to sink t using path P subject to prior reservations, and is denoted as DA(P). In other words, DA(P) is the sum of T(P) and any intermediate delay and DA(P) > T(P). The expression “capacity of a path” as referred to in the present disclosure pertains to the minimum of the capacities of all nodes and edges present in path P, and is denoted by C (P). The expression “saturated node or edge” as referred to in the present disclosure pertains to a node or edge on a path P when capacity of that node or edge is the same as the capacity of path P. The expression “distinct paths” as referred to in the present disclosure pertains to two paths P_1 and P_2 if and only if V_1?V_2 or E1? E2, where V_1,V_2 are the set of vertices and E_1,E_2are the set of edges in the paths P_1 and P_2 respectively. Exemplary building graph 100 consists of 10 vertices and 15 edges. For each vertex v, its name and the capacity are specified by a pair of the form (v, c(v)). A vertex representing an exit is represented as a square, while the others are represented as circles. For each edge e, the capacity and the travel time are specified on the edge by the pair (c(e), d(e)). The goal of the system of the present disclosure is to find the exit and an optimal path (route) for each evacuee, subject to the constraint that the number of source-sink paths passing through an edge does not exceed the capacity of the edge at any unit time interval. The objective function that the system of the present disclosure minimizes is the total time of evacuation. This is the time at which the last evacuee is evacuated, hereinafter referred to as the evacuation time. In an embodiment, system of the present disclosure can minimize time T in which a feasible flow value at least f can be sent from sources to sinks. FIG. 2 illustrates a portion 200 of an exemplary graph showing parallel flows sent on non edge-disjoint paths.In FIG. 2, ordered pair (C,T ) denotes capacity and transit time of an edge. There are two paths P_1 and P_2 between source s and sinkt. P_1: s - B - C - E - G - t,C(P_1) = 4,T (P_1) = 19. P_2 : s - A - C - E - F - t,C(P_2) = 6,T (P_2) = 23. Paths P1and P2 are not edge-disjoint, but common edge CE has capacity of 10. Accordingly, C(P_1) + C(P_2) = C(CE). So, flow can be sent through paths P1 and P2 in parallel and edge CE can be considered for all practical purposes as being two edges one having capacity 4 dedicated for P1 and other one having capacity 6, dedicated for P2. The concepts of combined evacuation time (CET) and quickest paths, as known in the art, consider both transit time and capacity on each path and provide a fair balance between them. In the event that there are k edge-disjoint paths P1, P2, … , P k from source node s to sink node t, the combined evacuation time is given by, CET(P_1,…,P_k )=?(p + ?_(i=1)^k¦?C_i T_i ?)/(?_(i=1)^k¦C_i )? (1) wherein, Ci and Ti denote the capacity and transit time of path Pi respectively, and p denotes the number of evacuees. Time required to evacuate p people via a path P having transit time T and capacity C is T+ ?p/C?-1. So, Pi is said to be the quickest path in the event that, T_i+ ?p/C_i ?-1 = T_j+ ?p/C_j ?-1,?j ?{1,…,k} \{i} The formula for CET, as known in the art, provides an expression for evacuation time and the number of people that will be evacuated on each path. It will be understood by those skilled in the art that paths having lesser arrival time will evacuate more groups. This technique is known as QPER (Quickest Path Evacuation Routing). The technique finds all edge-disjoint paths between a single source and a single sink and orders them according to the quickest evacuation time (calculated using CET) and adds them one by one. The technique does not use time-expanded graphs and there is no need to store availability information at each time stamp, as only edge-disjoint paths are considered. But the technique is limited to Single source Single sink Evacuation Problems (SSEP). Also, the addition of paths is not consistent, i.e., a path added at some point of time may be removed by the technique at a latter point of time, in case removal makes the solution better. In accordance with the present disclosure, to apply the formula of combined evacuation time CET for a set of paths, it is not necessary that the paths are edge-disjoint, instead the condition is that paths can be used to send flow in parallel as illustrated in FIG.2. Conventionally, in an optimal solution of Single Source Sink Evacuation Problem (SSEP), all possible paths between sources and sink t may be used up. In the event that P_1,P_2,...,P_Karek paths from source s to sink t (not necessarily edge-disjoint), in the worst case k can be exponentially large. But in accordance with the present disclosure, all k paths are not identified at the beginning. Instead paths are identified one by one in the order of their transit time. Firstly, path P_1 along with its capacity C_1having minimum transit time is identified and capacities of each node and path of P_1is decreased by its capacity C_1 permanently to obtain a residual graph. Then path P2 having minimum transit time in the residual graph is identified and so on. After each path addition combined evacuation time CET can be calculated. In an embodiment, a formal technique for the method of the present disclosure can be as described in Technique1 herein below. Running time analysis of SSEP in accordance with the present disclosure - In the event that paths P_1,P_2,...,P_K are identified after execution of Technique1, as in each step at least one edge or one node is deleted, at most m + n paths will be identified by system of the present disclosure. In each path at least one person will be evacuated. In the worst case, system of the present disclosure can identify p paths. Hence,k = min(m + n,p). As each path identification can be done in O(m + n log n) time, Technique1 requires O(min(m + n,p)(m + n log n)) time. Assuming m = O(n), this becomesO(min(n,p) • n log n), which is always at most O(pn log n).Time- complexity of CCRP as known in the art is O(pn log n). Hence, SSEP in accordance with the present disclosure always performs faster than CCRP. In real life, the number of evacuees is much larger than the number of vertices, so SSEP runs much faster than CCRP. Analysis of Technique1 - Let (P_1 ,C_1),(P_2 ,C_2),...,(P_k ,C_k) be distinct paths (not necessarily edge-disjoint) from s to t in order of their transit time identified by CCRP. Number of iterations that will return path P_i is? T?_k - T_i +?,1 = i = k, where ? denotes number of iterations that returns path P_k . Number of iterations that will return path P_i before phase j is T_j - T_i , where i = j = k. The same paths will be returned by Technique1. In accordance with the present disclosure, addition of paths by Technique1 of the present disclosure is consistent, i.e. when a path is added then it will remain till the end of the technique execution. Again, the evacuation time of the solution given by Technique1 is at most as that of the CCRP technique for single source and single sink. In accordance with the present disclosure, upper bound on the evacuation time given by CCRP (hence by Technique1) for single source single sink network is ?p/k? + (n - 1)t - 1, where p is the number of evacuees, n is the number of nodes in the graph, t is the maximum transit time of any edge and k is the number of paths used by CCRP (and Technique1).Technique1 also finds a path after saturated nodes and edges of all previously identified path are deleted if it satisfies the conditions given in Technique1 (line numbers 4 and 6).Each path identified by CCRP can be represented as an ordered pair of path and its group size. Technique1 also returns a path with maximum number of evacuees who can travel by that path at a time. As each path is identified only once in Technique1, we can also represent each path along with the capacity as an ordered pair. The above upper bound is tight. For instance, for a line graph of 10 nodes where first node is the source and last node is the sink, if each node and edge has capacity of 1 and each edge has a transit time of 10 and in the event there is only one evacuee, the evacuation time is 90for p = 1, k = 1, n = 10,t= 10. In accordance with an embodiment, Technique1described herein above can be extended to the case where there is a single source and multiple sinks. A super sink can be created which is connected to all the sinks of the original graph. The capacity and transit time of all the edges (that connect the super sink to all original sinks) are 8 and 0 respectively. In an emergency situation, people are stressed and they may consider evacuating via the shortest known path as a better option instead of following the route suggested by Technique1 (or CCRP). This may be due to several factors like route suggested may not be known by a person, they may feel that suggested path will take longer time to evacuate or they may display herd behavior wherein when a path is being followed by majority of people, chances are high that remaining population will also follow the same path. Such factors cause the evacuation pattern to deviate from the optimal solution. In an embodiment, systems and methods of the present disclosure consider probabilistic behavior of people to re-distribute evacuees in an efficient manner. In the event that in an evacuation, people do not follow paths suggested by Technique1 (or CCRP), with probability a > 0that a person follows suggested path and with probability 1 - a he follows the shortest path (to the nearest exit), system of the present disclosure redistributes people via various paths. If x_ipersons are suggested to followP_i, i ? 1, then the number of persons of persons who will follow P_i and P_1 is ax_iand (1-a) x_irespectively (in expectation). The total number of people following P_1 and P_i are x_1+?_(i=2)^k¦?(1-a) x_i ? and ax_i, i ? 1 respectively. Expected time at which the last person will arrive at destination via P_1 isT_1+(x_1+?_(i=2)^k¦?(1-a) x_i ?)/C_1 Expected time at which last person will arrive at destination via Pi isT_i+(ax_i)/C_i – 1,i ? 1. If the expected evacuation time in this scenario be E[T]. E[T]=max?( T_1+(1- a)n/C_1 – 1, max2= i = k (T_i+(ax_i)/C_i -1)) E[T]Will be minimum when it satisfies the following equation, E[T]=T_1+ (x_1+?_(i=2)^k¦?(1-a) x_i ?)/C_1 -1=T_i+(ax_i)/C_i -1,2 = i =k., (2) Where?_(i=1)^n¦?x_i=n? and x_i=0 ,?i. Solving the above equation we get, E[T]=( n+ ?_(i=1)^k¦?C_i T_i ?)/(?_(i=1)^k¦C_i ) – 1 = CET({P_1,P_2,…….,P_k }) (3) Expected evacuation time given by equation (3) doesn't depend on a.This is true and solution is feasible as long as x_1= 0. But it is not always the case, specifically when (1-a)?_(i=2)^k¦?x_i>C_1 (T-T_1+1) ?. So, implicitly evacuation time is dependent on a. In accordance with an embodiment, on expectation x_1+?_(i=2)^k¦?(1-a) x_i ?=ax_1+(1-a)n number of people will be evacuated via path? P?_1. This is minimum when x_1 = 0 as? x?_1 = 0. So, lower bound for expected evacuation time is T1+ (1- a)n/C1 – 1. In an embodiment, Technique1 as described herein above can be succeeded by a formal technique for re-distributing evacuees as described inTechnique2 herein below. Run Technique1. Find CET and x_1,x_2,...,x_k using Equation (2). If x_1 = 0 then quit; else go to step 3 of Technique1. In this case the expected evacuation time = CET. Assign x_1’ to 0 and x_i'=(nx_i)/(?_(j=2)^k¦x_j ), ?i ? 1. In this case , the expected evacuation time isT_1+(1- a)n/C_1 -1 . In accordance with the present disclosure, If x_i’ s are calculated then x_i’

Documents

Application Documents

# Name Date
1 3186-MUM-2015-IntimationOfGrant16-09-2022.pdf 2022-09-16
1 Form 3 [20-08-2015(online)].pdf 2015-08-20
2 3186-MUM-2015-PatentCertificate16-09-2022.pdf 2022-09-16
2 Form 20 [20-08-2015(online)].pdf 2015-08-20
3 Form 18 [20-08-2015(online)].pdf 2015-08-20
3 3186-MUM-2015-Written submissions and relevant documents [06-08-2022(online)].pdf 2022-08-06
4 Drawing [20-08-2015(online)].pdf 2015-08-20
4 3186-MUM-2015-Correspondence to notify the Controller [30-06-2022(online)].pdf 2022-06-30
5 Description(Complete) [20-08-2015(online)].pdf 2015-08-20
5 3186-MUM-2015-FORM-26 [30-06-2022(online)]-1.pdf 2022-06-30
6 REQUEST FOR CERTIFIED COPY [03-06-2016(online)].pdf 2016-06-03
6 3186-MUM-2015-FORM-26 [30-06-2022(online)].pdf 2022-06-30
7 Form 3 [20-08-2016(online)].pdf 2016-08-20
7 3186-MUM-2015-US(14)-HearingNotice-(HearingDate-27-07-2022).pdf 2022-06-24
8 Request For Certified Copy-Online.pdf 2018-08-11
8 3186-MUM-2015-ABSTRACT [25-01-2020(online)].pdf 2020-01-25
9 3186-MUM-2015-CLAIMS [25-01-2020(online)].pdf 2020-01-25
9 ABSTRACT1.jpg 2018-08-11
10 3186-MUM-2015-COMPLETE SPECIFICATION [25-01-2020(online)].pdf 2020-01-25
10 3186-MUM-2015-Power of Attorney-220316.pdf 2018-08-11
11 3186-MUM-2015-FER_SER_REPLY [25-01-2020(online)].pdf 2020-01-25
11 3186-MUM-2015-Form 1-110915.pdf 2018-08-11
12 3186-MUM-2015-Correspondence-220316.pdf 2018-08-11
12 3186-MUM-2015-OTHERS [25-01-2020(online)].pdf 2020-01-25
13 3186-MUM-2015-Correspondence-110915.pdf 2018-08-11
13 3186-MUM-2015-FER.pdf 2019-07-25
14 3186-MUM-2015-Correspondence-110915.pdf 2018-08-11
14 3186-MUM-2015-FER.pdf 2019-07-25
15 3186-MUM-2015-Correspondence-220316.pdf 2018-08-11
15 3186-MUM-2015-OTHERS [25-01-2020(online)].pdf 2020-01-25
16 3186-MUM-2015-FER_SER_REPLY [25-01-2020(online)].pdf 2020-01-25
16 3186-MUM-2015-Form 1-110915.pdf 2018-08-11
17 3186-MUM-2015-Power of Attorney-220316.pdf 2018-08-11
17 3186-MUM-2015-COMPLETE SPECIFICATION [25-01-2020(online)].pdf 2020-01-25
18 3186-MUM-2015-CLAIMS [25-01-2020(online)].pdf 2020-01-25
18 ABSTRACT1.jpg 2018-08-11
19 3186-MUM-2015-ABSTRACT [25-01-2020(online)].pdf 2020-01-25
19 Request For Certified Copy-Online.pdf 2018-08-11
20 3186-MUM-2015-US(14)-HearingNotice-(HearingDate-27-07-2022).pdf 2022-06-24
20 Form 3 [20-08-2016(online)].pdf 2016-08-20
21 3186-MUM-2015-FORM-26 [30-06-2022(online)].pdf 2022-06-30
21 REQUEST FOR CERTIFIED COPY [03-06-2016(online)].pdf 2016-06-03
22 3186-MUM-2015-FORM-26 [30-06-2022(online)]-1.pdf 2022-06-30
22 Description(Complete) [20-08-2015(online)].pdf 2015-08-20
23 3186-MUM-2015-Correspondence to notify the Controller [30-06-2022(online)].pdf 2022-06-30
23 Drawing [20-08-2015(online)].pdf 2015-08-20
24 3186-MUM-2015-Written submissions and relevant documents [06-08-2022(online)].pdf 2022-08-06
24 Form 18 [20-08-2015(online)].pdf 2015-08-20
25 3186-MUM-2015-PatentCertificate16-09-2022.pdf 2022-09-16
26 Form 3 [20-08-2015(online)].pdf 2015-08-20
26 3186-MUM-2015-IntimationOfGrant16-09-2022.pdf 2022-09-16

Search Strategy

1 search_25-07-2019.pdf

ERegister / Renewals

3rd: 14 Dec 2022

From 20/08/2017 - To 20/08/2018

4th: 14 Dec 2022

From 20/08/2018 - To 20/08/2019

5th: 14 Dec 2022

From 20/08/2019 - To 20/08/2020

6th: 14 Dec 2022

From 20/08/2020 - To 20/08/2021

7th: 14 Dec 2022

From 20/08/2021 - To 20/08/2022

8th: 14 Dec 2022

From 20/08/2022 - To 20/08/2023

9th: 18 Aug 2023

From 20/08/2023 - To 20/08/2024

10th: 20 Aug 2024

From 20/08/2024 - To 20/08/2025

11th: 13 Aug 2025

From 20/08/2025 - To 20/08/2026