# ESCAPE: Evacuation Strategy through Clustering and Autonomous Operation in Public Safety Systems
## 5 ESCAPE Algorithm
```
1:Input:
2:\(\Rightarrow\) Set of Humans: \(M=[1,\ldots,m,\ldots,|M|]\)
3:\(\Rightarrow\) Set of Evacuation Routes: \(E=[1,\ldots,e,\ldots,|E|]\)
4:Output:
5:\(\Rightarrow\) Action probabilities at stochastic learning automata convergence \(\mathbf{Pr}^{*}=[\mathbf{Pr}^{*}_{1},\ldots,\mathbf{Pr}^{*}_{\mathbf{m}}, \ldots,\mathbf{Pr}^{*}_{|\mathbf{M}|}]\)
6:Initialization:
7:\(\Rightarrow\) Each human \(m\), \(m\in M\) has equal probability for each route \(Pr_{m,e}(0)=\frac{1}{|E|},\forall m\in M\), \(\forall e\in E\)
8:\(t=0\), the number of timeslots for stochastic learning automata convergence
9:\(\Rightarrow\) Convergence \(=0\)
10:Iterative Procedure:
11:whileConvergence\(==0\)do
12:\(N_{e}=\varnothing\), \(\forall e\in E\); At first the cluster of each route is empty
13:for\(m=1\) to \(|M|\)do
14:\(human\)\(m\) chooses the evacuation route \(e\) based on its action probabilities: \(Pr_{m}=[Pr_{m,1},\ldots,Pr_{m,|E|}]\)
15:\(e_{m}^{(t)}=e\); human's \(m\) choice
16:\(N_{e}=N_{e}\cup\{m\}\); human \(m\) is appended to route's cluster
17:endfor
18:for\(e=1\) to \(|E|\)do
19:\((N_{e}^{go},N_{e}^{ngo})=DEMG(N_{e},C_{e},|M|_{e})\);
20:\(|M|_{e}(t)=|M|_{e}(t)-\lambda_{e}\cdot|M|_{e}(t)+|N_{e}^{go}|\)
21:\(\lambda_{e}(t)=\lambda_{e}(0)\cdot\frac{(C_{e}-|M|_{e}(t))}{C_{e}}\)
22:endfor
23:for\(m=1\) to \(|M|\)do
24:for\(e=1\) to \(|E|\)do
25:\(human\)\(m\) determines the reward function \(r_{m,e}(t)\) based on Equation (1)
26:endfor
27:\(human\)\(m\) determines the normalized reward function \(\hat{\eta}_{m,e_{m}^{(t)}}(t)\)
28:for\(e=1\) to \(|E|\)do
29:if (\(e==e_{m}^{(t)}\)) then
30:\(human\)\(m\) updates their action probability \(Pr_{m,e}(t+1)\) based on Equation (2a)
31:else
32:\(human\)\(m\) updates their action probability \(Pr_{m,e}(t+1)\) based on Equation (2b)
33:endif
34:endfor
35:endfor
36:if\((\forall m\in M\), \(\exists e\in E\): \(|Pr_{m,e}(t+1)-1|\leq e\), \(e\to 0)\)then
37:\(Convergence=1\);
38:else
39:\(t=t+1\);
40:endif
41:\(\mathbf{Pr}^{*}_{m}=Pr_{m}(t+1)\), \(\forall m\in M\)
42:\(M=M\smallsetminus \begin{matrix}|E|\\ e=1\end{matrix} N_{e}^{go}\); Ercauated humans are excluded from the system
43:endwhile
```  
**Algorithm 1** ESCAPE Algorithm  
Regarding ESCAPE's complexity, it can be assumed that in each timeslot \(t\) of the stochastic learning automata, minority games for evacuation routes (ESCAPE algorithm's lines 12 to 16) are played in parallel, since each minority game for each evacuation route \(e\in E\) is fully independent, and the only necessary information is corresponding cluster size \(N_{e}\) and available space inside the route \(e\), i.e., \(C_{e}-|M|_{e}\). Therefore, by denoting as \(Ite|_{t}\) the number of iterations that are needed for the convergence of the minority game that finishes last for timeslot \(t\), and since the complexity of the DEMG algorithm is \(\mathcal{O}(|M|)\), the complexity of all minority games is \(\mathcal{O}(Ite|_{t}\cdot|M|)\). Moreover, the rest of the ESCAPE algorithm has complexity \(\mathcal{O}(|M|+|M|\cdot|E|)\), i.e., \(\mathcal{O}(|M|\cdot|E|)\), and by denoting as \(T\) the number of timeslots that are needed for the reinforcement-learning component's convergence, the ESCAPE algorithm's complexity is \(\mathcal{O}(T\cdot(Ite|_{t}\cdot|M|+|M|\cdot|E|))\). Furthermore, as we see in the numerical results below (Section 6), both \(Ite|_{t}\) and the number of the timeslots \(T\) scale very well with respect to the number of humans, i.e., \(|M|\), and the number of evacuation routes, i.e., \(|E|\); consequently, our approach is characterized by low complexity.