After Collecting Sensors Information, the Next Work Is to Calculate a Safest Path for the User

Safe path in fire scene

After collecting sensors information, the next work is to calculate a safest path for the user.

Let cost be the time spending by the user to escape; thus our issue of safest path is as following:

Cost less: The safe path should be less cost for the user to escape from the fire place.

Fire-free: The safe path should be fire-free to ensure the user's safety.

The cost can be derived in advance by measuring the length all edges between all nodes. The length is divided by the human velocity so that we can simply use it in the next part. To ensure paths to be cost less, we use shortest path algorithm to derive paths from the user’s location to all exits. One advantage to use shortest path algorithm is that the algorithm guarantee to find a solution, if there is any. Here we use Dijkstra's shortest path algorithm (see APPENDIX I).

Besides finding all paths from user’s location to all exits, we use BFS with limit depth to find some redundant paths to exits because these paths might be useful. The limit depth for BFS is given as, where is the maximum cost of all paths from user’s location to exits. is given by us and depends on the computing capability of the hand-held system.

In order to obtain fire-free path, we derive that Exponential distribution is useful to estimate the degree of danger.

Given an exponential process:

Where is the inverse of the node’s mean failure time, estimated according to experiment, and varied from the node’s state.

Since the cost of every edge is estimated in advance, the degree of danger could be estimated. Given a path with nodes, be the costs of the edges, and be the inverses of the node’s mean failure time, the probability of the user succeed to escape from the path is:

Let be the probability of the paths derived from shortest path algorithm and limit depth BFS, the best fire-free path with maximumcan be obtained by:

Here we present the pseudo code of our algorithm:

Paths are derived from Dijkstra's shortest path algorithm

D = min cost of

are derived from limit depth BFS if cost

for()

compute probability

return the path with the maximum probability

APPENDIX I

Dijkstra's shortest path algorithm

1 function Dijkstra(Graph, source):

2 for each vertex v in Graph: // Initializations

3 dist[v] := infinity // Unknown distance function from source to v

4 previous[v] := undefined

5 dist[source] := 0 // Distance from source to source

6 Q := copy(Graph) // All nodes in the graph are unoptimized - thus are in Q

7 whileQis not empty: // The main loop

8 u := extract_min(Q) // Remove and return best vertex from nodes in two given nodes

// we would use a path finding algorithm on the new graph, such as depth-first search.

9 for each neighbor v of u: // where v has not yet been removed from Q.

10 alt = dist[u] + length(u, v)

11 ifalt < dist[v] // Relax (u,v)

12 dist[v] := alt

13 previous[v] := u

14 return previous[]

Reference: