## 5 Dynamic Firefighter Guiding
### Computation of Escape Paths  
The objective is to compute escape paths that minimize risk using the measurements available at the Base Station. The proposed method adopts a graph approach: the building is modeled as an undirected graph where the vertices are rooms and the edges are connections between rooms. The outside of the building is also modeled by one vertex (ID = 0): the graph model naturally allows buildings with several exits. The cost of each edge is calculated following a cost model that uses the current fire measurements. Our objective is to compute the minimum cost path from each building room to the exit. Graph representations are suitable in our problem since many graph-based optimization algorithms have been developed. Two main variations of the shortest path problem can be found: the single-source shortest path problem, which finds shortest paths from a source vertex to all other vertices in the graph; and the all-pairs shortest path problem, which finds the shortest paths between every pair of vertices in the graph. In our problem, the objective is to compute the shortest path to the exit: it is a single-source problem. There are two main algorithms to solve this problem, the Bellman-Ford algorithm and the Dijkstra algorithm. We selected Dijkstra [30] since it is faster, intuitive and easy to implement. Dijkstra solves the single-source minimum cost path problem for a graph with nonnegative edge costs. It obtains the minimum cost path from an initial vertex to the rest of the graph vertex, producing a minimum cost tree. The outside of the building (vertex 0) is taken as the initial vertex. Dijkstra computes the minimum cost paths from the vertex 0 to each of the rooms. Since the building graph is undirected, these will be as well the minimum cost paths from each of the rooms to the vertex 0. Each resulting path is an ordered list of contiguous vertices--room identifiers--that ends in vertex 0. Paths can be seen as a concatenation of local guiding commands. The local guiding information of node \(i\), \(\{LGI_{i}\}\), is represented by a pair with the current room identifier and the next room in the path. The proposed method requires an edge cost model. The cost of the edge between vertices \(i\) and \(j\), \(C_{ij}\), is related to the conditions a firefighter are exposed to in its way from room \(i\) to \(j\). It is not the objective of this paper to define an accurate cost model. Expertise from firefighter is critical here. In this paper, we used a simple but efficient model that illustrates the capabilities of the approach. In the cost model used \(C_{ij}\) is considered as the sum of three terms: \(C_{ij}=CA_{ij}+CB_{ij}+CC_{ij}\). The first one, \(CA_{ij}\), refers to cases in which a strong risk is identified, such as high temperatures or flammable gases in a room. Presence of a strong risk in rooms \(i\) and/or \(j\) is modeled setting \(CA_{ij}\) to very high values. Otherwise, it is set to zero. The objective is to prevent these rooms from being included in escape paths. The second one, \(CB_{ij}\), refers to the presence of accumulative risks, such as toxic gases. Humans can tolerate low concentrations or short expositions until a certain threshold is reached. Its objective is to minimize the exposition to toxic gases. \(CB_{ij}\) is computed summing the contributions of both rooms:  
\[CB_{ij}=CB_{i}d_{i}+CB_{j}d_{j} \tag{6}\]  
where \(d_{i}\) is the distance between the center of room \(i\) and the door between both rooms and \(d_{j}\) is the distance between the door and the center of room \(j\). \(CB_{i}\), the accumulative risk in room \(i\), can be computed summing the contributions of all toxic gases considered:  
\[CB_{i}=\sum_{k}(\alpha_{k}C_{k,i}) \tag{7}\]where \(C_{k,i}\) is the concentration of toxic gas \(k\) in room \(i\) and \(\alpha_{k}\) is the weighting factor to consider the gas toxicity. In the experiments shown in Section 6, \(CO\) and \(CO_{2}\) were considered with weights \(\alpha_{1}=0.7\) and \(\alpha_{2}=0.3\), respectively, for the highest toxicity of \(CO\).