A dynamic rescue route planning method based on 3D network in mine water inrush hazard

Abstract

Water inrush in mine is one of the most common hazards in the mining industry. To solve the problem of rescue route planning during a mine water inrush hazard, a dynamic rescue route planning method based on a 3 D network is proposed. First, the basic elements in the 3 D network model of the mine roadway are abstractly described, furthermore, the weights of edges, the topological connectivity of the elements, and the data structure of the network are defined. Then, the Dijkstra algorithm and the Breadth-first search algorithm are combined to implement the best rescue search route and return route planning based on the 3 D network model. Finally, the dynamic rescue route planning is simulated in 3 D virtual spatial scenario of a real mine. The factors such as topological connectivity of the elements, real-time water level, and slope of the mine roadways are considered in the process of rescue route planning, as the rescue route is adjusted dynamically according to the actual situations. This method proposed can provide powerful decision support for mine water inrush hazard rescue.

Keywords:

• Mine water inrush hazard
• dynamic rescue route planning
• 3D (three-dimensional) spatial network model of mine roadways
• Dijkstra algorithm
• Breadth-first search algorithm

1. Introduction

With the expansion of mining scale, the mine roadways in the mine are getting longer and longer, the layouts in the mine roadways are more complicated, therefore the mine roadways gradually become a complex 3 D (three-dimensional) network [1-4] (Xu and Gong 2011; Wu, Lei, et al. 2013; Cui 2015; Dash, Bhattacharjee, and Paul 2016). Water inrush is one of the most common hazards in mines and results from hydrogeological factors (Wu, Zhou, et al. 2009; Ma and Zhang 2012). The flooding of the water in the mine roadways is a gradual process during water inrush. The water flows from the water inrush point into the mine roadways, then flows into the bottom along the mine roadways, and then the water level rises gradually from the bottom until it reaches equilibrium (Yao et al. 2011; Wu, Lei, et al. 2013; Wu et al. 2016; Qi et al. 2017). At this time, the rational formulation of rescue route plan is directly related to the life safety of the people working in the mine roadways. Therefore, rescue route plan is an important research subject in mine safety (Sheu 2007; Jalali and Noroozi 2009; Yuan and Wang 2009; Şalap, Karslıoğlu, and Demirel 2009; He et al. 2019).

In previous research within the field of mine safety, the concept of equivalent length is introduced to measure the weights of edges in the network (Wang 2017), but a method to determine the weights of various factors affecting the capacity of mine roadways in the rescue route planning during the water inrush hazard is not described in detail in the research (Fang et al. 2011; Wu, Zhou, et al. 2009; Wang 2017). However, the weights of some important factors, such as real-time water level, and slope of mine roadways, should be considered while the rescue route is being planned (Dong et al. 2018).

Dijkstra algorithm (Huang 2017) or its improved variants are the most popular approach used in the rescue route planning in previous research (Cheng, Zhang, and Li 2014; Zhao et al. 2015; Zhao and Zong 2015; Likaj and Shala 2017), however, seldom is the dynamic variation in the weights of various factors taken into account in the algorithms. It is precisely because of the neglect of the dynamic variation in various weights that the route is regarded as an impassable only due to its capacity varying dynamically. It easily results in selection of sub-optimal rescue routes instead of the real most optimal route (Cheng, Zhang, and Li 2014; Zhao et al. 2015; Zhao and Zong 2015). Therefore, in order to make more practical rescue route plans, there are still two problems that need to be solved: (1) as the situations (such as the water level, accessibility of the mine roadways) in the mine roadways are varying in real-time, the rescue route planning should also be adjusted accordingly; (2) the positions of the mineworkers underground in the mine roadways may also change during the rescue, so the rescue route planning should also be adjusted according to the change of the positions of the mineworkers underground.

In addition, previous research on optimal route analysis problems for route planning during mine hazards is mostly simulated in 2 D visualization space (Wang and Wu 2008; Jalali and Noroozi 2009; Cheng, Zhang, and Li 2014; Zhao et al. 2015; Zhao and Zong 2015; Wang 2017). However, the rescue route in the mine often includes uphill and downhill sections, and may pass through mining faces at different elevations, thereby having significant 3 D features. It is difficult to exactly represent the rescue route with 3 D features in 2 D visualization space.

To solve the problems above, a dynamic rescue route planning method based on 3 D network during a mine water inrush hazard is explored in this paper. First and foremost, the basic elements in the 3 D network are abstractly described, furthermore, the data structure of various elements is defined with the object-oriented method. The storage model of the 3 D network of mine roadways is then established by using the adjacency matrix. On this basis, the traffic capacity weight of mine roadways is determined by combining the factors such as spatial distance, slope and water level of the mine roadways. Finally, the rescue search and return routes planning algorithm is implemented by combining the Dijkstra algorithm with the Breadth-first search algorithm.

2. 3 D Network model of mine roadway

2.1. Representation of the 3 D network model

The entities included in the rescue route planning issue are mine roadways, mineworkers, and facilities (e.g., water level monitoring sensors and mineworker positioning sensors) in the mine. The entities involved should be defined in the simulation environment. In this paper, the 3 D network is built based on the graph theory (Hwang et al. 2003; Price and Ostfeld 2014; Alexiou and Tsouros, 2017; Likaj and Shala 2017; Huang and Dinavahi 2018; Zuecco et al. 2019), the entities involved are abstracted as elements in logical network model and represented as geometric objects in physical network model.

1. The mine roadway entities are abstracted as the edge elements, which are represented with line objects (that are the centerlines of the mine roadways).

2. The end vertexes of the edge elements are abstracted as static vertex elements, which are represented with static point objects.

3. The mineworker and the rescuer entities are abstracted as movable node elements, which are represented with dynamic point objects.

4. The facility entities are abstracted as static node elements, which are represented with static point objects.

There are definite relationships among the entities involved, e.g., a facility is attached to a roadway. Therefore, the relationships among the elements are descripted correspondingly as follows.

1. There are adjacency relationships among the edges, which describe the topological connectivity among the mine roadways.

2. There are association relationships among the edges and the vertexes, which describe the topological association among the edges and their endpoints.

3. There are dependency relationships among the edges and nodes, which describe the facilities, the rescuers, and the mineworkers attaching to the edges.

2.2. Data structure of objects

The objects in a physical network model are the geometric objects created in memory, and the data structures of them are the foundation of the rescue route planning algorithm. The data structures are defined through the following classes written with C# code. The MineRoadwayNetwork class defines the data structure of the roadway network, which is actually a directed graph. There are two edges with opposite directions between two adjacent vertexes, conversely, there is no edge between two non-adjacent vertexes. As a member of the MineRoadwayNetwork class, the Matrix is an asymmetric adjacency matrix, which records the topological connectivity, their directions, and weights of edges. The element M_ij in Matrix is the edge, whose start vertex’s ID is i (denoted as V_i), and end vertex’s ID is j (denoted as V_j). If V_i and V_j are not adjacent, the element M_ij is assigned an empty value, “Null”. The rescue route planning algorithm is programmed based on the adjacency matrix.

The data structure of 3 D roadway network model is shown as Figure 1.

Figure 1. Data structure of 3 D roadway network model.

2.3. Data storage of objects

The data of various objects in the network model are stored in the SQL Server database tables and used to create the objects in memory according to corresponding classes.

1. The vertex table stores the information including ID, type and 3D coordinates of the point objects representing vertex elements.

2. The edge table stores the information including ID, IDs of vertexes, IDs of nodes, roadway length, roadway slope, and roadway water level of line objects representing edge elements.

3. The facility table stores the information including ID, type and 3D coordinates of the point objects representing various auxiliary facilities in the roadway, such as flow meters for monitoring water flow, personnel positioning equipment, etc.

4. The rescue personnel information tables store the information including ID, type and 3D coordinates of the point objects representing the rescuer elements.

5. The underground mineworker information tables store the information including ID, type and 3D coordinates of the point objects representing the mineworker elements.

2.4. The weights of the edges

When the optimal rescue route is being planned, an indicator is needed to measure the optimization of the rescue route. The length, slope and water level of each edge in the network are important factors affecting the accessibility of the roadway and the speed of rescuers and mineworkers, so the factors determine the optimization of the rescue route. Therefore, these factors are quantified as the weights of each edge. The weights of the factors are combined to be a comprehensive weight as the final indicator to measure optimization of the edge. The sum of the comprehensive weights of all edges in the rescue route is the final optimization indicator of the rescue route. The weight quantification of the factors and the calculation of the comprehensive weight are addressed as follows. It is different from the evacuations in fire disaster scenario, in which the indicators including heat release rate, generation of harmful fire gases, smoke, burning rate of the material, generated heat from fire, should be considered to calculate weights. In addition, the mining roadway weights calculating models are significantly different between them (Adjiski et al. 2015).

2.4.1. The influence coefficient of the slope factor

The slope of the roadway has a certain influence on the rescue speed, the time cost and the physical strength of rescuers, so it is necessary to quantify the influence coefficient of the slope factor. The distance and height difference of each edge can be calculated with the 3 D coordinates of the vertexes of the edge, and then slope value of the edge can be calculated with the arcsine function. For the same roadway, there are two walking directions, which are ascending direction and descending direction. The slope value is positive in ascending direction and negative in descending direction. The walking difficulty increases as the slope value increases in the ascending direction. In the descending direction, if the absolute value of the slope is less than 30, the walking difficulty decreases as the absolute value of the slope increases, else the walking difficulty increases as the absolute value of the slope increases. With reference to the relevant research (Zhao et al. 2015; Zhao and Zong 2015) and the actual situation of mine roadway, the rules to determine the influence coefficient of the slope factor are refined as shown in Table 1.

Table 1. The influence coefficient of the slope factor.

Slope value (S)	Influence coefficient ($K_s$)	Walking direction
S = 0°	1.0	Horizontal
0° < S <  = 30°	1 + S*0.01	Ascending
30° < S <  = 45°	1.3+(S-30)*0.015	Ascending
45° < S <  = 60°	1.525+(S-45)*0.02	Ascending
60° < S <  = 90°	1.825+(S-60)*0.03	Ascending
0° < S <  = −15°	1-|S|*0.01	Descending
−15° < S <  = −30°	0.85+|S + 15|*0.01	Descending
−30° < S <  = −45°	1+|S + 30|*0.015	Descending
−45° < S <  = −60°	1.225+|S + 45|*0.02	Descending
−60° < S <  = −90°	1.525+|S + 60|*0.03	Descending

2.4.2. The influence coefficient of water level factor

When the water inrush hazard occurs, a large amount of water flows into the roadway from one or more positions in practical occasion. In this study, the inrush positions and the flow are simulated with simulation software. The water in the roadway affects the rescue speed and safety of rescuers and mineworkers. Therefore, the influence of water level factor should be considered when the rescue route is being planned. Currently, the water level in mine roadway can be monitored in real-time with water level sensors and transferred with the reliable communication network to the rescue database. The walking difficulty increases as the water level increases until the roadway is impassable. By referring to the relevant research (Fang et al. 2011; Wang, Zhang, and Li 2014; Cheng, Zhang, and Li 2014; Zhao et al. 2015; Zhao and Zong 2015; Wang 2017), and also according to the actual situation of roadway, the influence coefficient of water level in the roadway is shown in Table 2.

Table 2. The influence coefficient of water level factor.

water level (WL)	Influence coefficient ($K_w$)	Degree of influence
WL = 0cm	1.0	Uninfluential
0cm < WL < =55cm	1.25	Minor influence
55cm < WL< =101cm	2	Difficult to pass
101cm < WL< =131cm	5	Very difficult to Pass
WL > 131cm	∞	Impassable

2.4.3. The dynamic comprehensive weight

The length and the slope are the unvarying geometric attributes of the roadway, while the water level is the varying attribute in real-time of it. Therefore, the length and the slope of the roadway are the static factors whereas the varying water level is dynamic factor, which affect the accessibility of the roadway. The influence coefficient of water level should be calculated in real-time while the rescue route is being planned. To measure the total influence of all factors, the influence coefficients are combined into the dynamic comprehensive weight defined as Eq. (1). (1) $$W_{ij}=l_{ij}\times K_s\times K_w$$(1)

Where $W_{ij}$ is comprehensive weight of the roadway edge between vertex i and vertex j; $l_{ij}$ is the 3 D length of the edge; $K_s$ is the slope influence coefficient of the edge; $K_w$ is the water level influence coefficient of the edge. The comprehensive weight is also called the optimal relative length in previous research (Wang, Zhang, and Li 2014; Zhao et al. 2015; Zhao and Zong 2015; Wang 2017; Dong et al. 2018).

3. Rescue route planning

The main task of the simulation is to rescue the mineworkers underground, not to guide the mineworkers to escape. In the process of guiding the mineworkers, the rescuers need not go underground to search for the mineworkers, only need monitor positions of the mineworkers and inform them the current optimal escape route. While in the process of rescuing the mineworkers, the position of the mineworkers may be changing, so the rescuers should search for the mineworkers in the first step and find them. Then, the rescuers take the mineworkers to the mineworkers to the up ground. Therefore, the rescue process includes the following two steps: (1) the rescuers go underground to search for the mineworkers along the mine roadways; (2) the rescuers take the mineworkers back to the ground surface. Correspondingly, the rescue route planning should include two processes, the route planning for mineworker-search and the route planning for rescue return.

The rescue route planning algorithm is a combination of the Breadth-first search of the graph and the Dijkstra algorithm. First of all, this paper mainly draws on the idea of Breadth-first search when designing the rescue route planning algorithm. The search process starts from the starting point and expands outward through the boundary between the searched vertices and the unsearched vertices. In the route expansion process, the route search can skip the invalid route and the unreachable route by setting the judgment condition. Breadth-first search can calculate all reachable routes from the start point to the target point, but when the number of vertices in the graph is large, the search efficiency is very low. In order to improve the efficiency of route search, the search process of the rescue route is optimized based on the idea that the Dijkstra algorithm (Xu et al. 2007; Wang and Wu 2008; Deng et al. 2012; Wang 2012; Price and Ostfeld 2014; Hu, Yang, and Huang 2016). There are two aspects to the specific optimization. One is to remove the route with the larger weight in the same route, and only keep one or more paths with smaller weights. Second, if the end vertex $V_k$ of one route $R_i$ is the intermediate point of the other route $R_j,$ and the weight of the route $R_i$ is greater than the weight from the start point to the vertex $V_k$ in the route $R_j,$ then remove $R_i$ from route set. Through the optimization of these two aspects, the number of routes in the set of routes to be searched can be greatly reduced, thereby improving the efficiency of route search. Therefore, the rescue route search algorithm designed in this paper can not only search the optimal route from the source point to the specified target point but also calculate the non-shortest route that can be reached from the source point to the target point.

3.1. Route planning for mineworker-search

When planning the search route for the mineworkers, the position of the rescuers is set as the source point, and the position of the mineworkers is set as the destination point. During the process of rescue, rescuers need to consider two dynamic factors, one is the varying water level in the roadway; the other is the moving positions of the rescuers and the mineworkers. The planned route should be dynamically adjusted according to the changes of the factors. According to the 3 D network model described above, the weighted directed graph is defined as $G=(\mathit{Vertexes},\mathit{Edges},\mathit{Matrix}),$ where $\mathit{Vertexes}$ are the set of vertexes in the graph, $\mathit{Edges}$ are the set of edges in the graph, and $\mathit{Matrix}$ is an asymmetric adjacency matrix, which records the topological connectivity among vertexes. Instead of directly storing the weight between the two vertexes, the edge, the starting vertex and the end vertex of the edge, and the weights in two directions are stored in the matrix. The advantage of this is that when the weight of an edge varies, the weight of the corresponding edge in the adjacency matrix is automatically updated. Combining Breadth-first search idea and Dijkstra algorithm, the process of route planning for mineworker-search underground is described as follows:

1. The R_Node (the rescue personnel node) in the network is set to the source point $V_S$ (normally it is the mine exit), and the MW_Node (the mineworker node) is set to the target point $V_T.$ Initialize the effective route set $S(ER)$ and the new route set $S(NR)$ to null, and set the total number C of rescue route that need to be calculated.

2. The vertex ${\mathrm{V}}_n$ closest to $V_S$ is searched on the edge on which $V_S$ lies. Each edges whose starting point is ${\mathrm{V}}_n$ are searched in the Matrix. All of the edges compose the edge set denoted as $S\left(E\right)=\left\{E_1,E_2,\dots ,E_n\right\}.$ Each edge in $S\left(E\right)$ is the initial edge of a route. All of the routes compose the route set denoted as $S\left(R\right)=\left\{R_1,R_2,\dots ,R_n\right\}.$

3. If ${\mathrm{V}}_S$ and ${\mathrm{V}}_T$ are not on the same edge $E_j,$ step (4) is executed. Otherwise the current route searching process is over, the route is marked as a valid route, and the weight of the route is calculated according to equation (2)(2) $$W_0=W_e\times \mathit{Dist}(V_s,V_T)/L_e$$(2) : (2) $$W_0=W_e\times \mathit{Dist}(V_s,V_T)/L_e$$(2)

   Where $W_0$ denotes the comprehensive weight between $V_S$ and $V_T,$ $W_e$ denotes the comprehensive weight of the edge where $V_S$ and $V_T$ are located, $\mathit{Dist}(V_S,V_T)$ is the distance between $V_S$ and $V_T,$ and $L_e$ is the length of the edge where $V_S$ and $V_T$ are located.

4. Select the route $R_t$ from $S(R)$ in order, if the order has exceeded the upper limit of the number of routes in $S(R),$ go to step (8), otherwise select route $R_t$ from $S(R)$ in this order. Then searching all edges of the adjacency matrix (Matrix) with the end vertex in the route $R_t$ as the starting point, and composing a new set of edges $S\left(E\right)=\left\{E_1,E_2,\dots ,E_n\right\},$ and then go to step (5).

5. Select the edge $E_t$ from $S\left(E\right)$ in order, and if the order has exceeded the upper limit of the number of edges in $S\left(E\right),$ go to step (4), otherwise select an edge $E_t$ from $S\left(E\right)$ in this order. If the edge $E_t$ contains the source point $V_S,$ the current edge $E_t$ is skipped, otherwise a new route $R_t$ is generated based on the current route. Then, it is determined whether there are two identical vertices in the newly generated route $R_t.$ If yes, the newly generated route is an invalid one, and the current edge $E_t$ is skipped; if not, the weight of the current route is updated, and then go to step (6).

6. Determine whether the target point $V_T$ is included in the edge $E_t.$ If it is included, it indicates that $R_t$ is a valid route from the source point to the target point. If the total number of routes in $S\left(ER\right)$ is less than C, add $R_t$ to the set $S\left(ER\right),$ and then go to step (5). If the total number of routes in the set $S\left(ER\right)$ is equal to C, sort the routes in $S\left(ER\right)$ according to the weight of the route. If the weight of $R_t$ is smaller than that of the route with the largest weight in $S\left(ER\right),$ replace the route with the largest weight in $S\left(ER\right)$ with $R_t,$ and then go to step (5), otherwise go directly to step (5). If the target point $V_T$ is not included in the edge $E_t,$ it indicates that the current route $R_t$ has not reached the end vertex, and then go to step (7).

7. If the total number of routes in the set $S\left(ER\right)$ is less than C, $R_t$ is directly added to $S\left(NR\right),$ and then go to step (5). If the total number of routes in the set $S\left(ER\right)$ is equal to C, the routes in $S\left(ER\right)$ are first sorted according to the size of the weights. If the weight of $R_t$ is smaller than the route with the largest weight in $S\left(ER\right),$ then $R_t$ is added to $S\left(NR\right)$ and then to step (5), otherwise it goes directly to step (5).

8. If there are multiple routes with the same end vertex in the set $S\left(NR\right),$ only one route with the smallest weight value is reserved at $S\left(NR\right),$ and then go to step (9).

9. In the set $S\left(NR\right),$ if the end vertex $V_k$ of one route $R_i$ is an intermediate point on another route, $R_j,$ and the weight of the route $R_i$ is greater than the weight from the start point to the vertex $V_k$ in the route $R_j,$ then remove $R_i$ from $S\left(NR\right)$ and then go to step (10).

10. Update the set $S\left(R\right)$ to the route in the set $S\left(NR\right),$ and then judge whether $S\left(R\right)$ is empty. If $S\left(R\right)$ is empty, the route search is completed, return the effective route set $S\left(NR\right),$ and then go to step (11). If $S\left(R\right)$ is not empty, empty $S\left(NR\right)$ and then go to step (4).

11. The route with the smallest cumulative weight in $S\left(R\right)$ is the optimal route $P$ of the current plan, and $P$ is stored in the optimal route set $S(P).$ The rescuer performs rescue according to the planned route. Then go to step (12).

12. The current source point $V_S$ and the target point $V_T$ are dynamically updated according to the rescuer's latest coordinates RN_x, RN_y, RN_z and the mineworkers' latest coordinates MWN_x, MWN_y, MWN_z.

13. The overall weight of each edge in the adjacency matrix (Matrix) is dynamically updated based on the water level of each roadway, which can be obtained either from a simulation or real-time monitoring.

14. Steps (1)∼(13) are executed repeatedly until the source point $V_S$ and the target point $V_T$ are on the same edge, and the optimal route search ends.

15. A combination of all the planning routes in $S(P)$ and removing the overlapping edges yields the final optimal rescue route.

The flow chart of the route-planning algorithm for mineworker-search is shown as Figure 2.

Figure 2. The flow chart of the route-planning algorithm for mineworker search.

3.2. Route planning for rescue return

Route planning for rescue return should be executed when the rescuers find the mineworkers. The route planning for rescue return algorithm is similar to the route-planning algorithm for mineworker-search, with two differences: (1) In the route planning for rescue return process, the rescuers and the mineworkers are in the same position, therefore the $\mathrm{R}\_\mathrm{Node}$ or $\mathrm{MW}\_\mathrm{Node}$ in the network is set as the source point $V_S,$ and the $\mathrm{O}\_\mathrm{Vertex}$ (normally the exit of the well) is set as the destination point $V_D;$ (2) The destination point $V_D$ does not change under normal conditions, so it is unnecessary to dynamically update $V_D.$ Only the current source point, $V_S,$ needs to be updated according to the latest coordinates, $\mathrm{RN}\_\mathrm{x},$ $\mathrm{RN}\_\mathrm{y},$ $\mathrm{RN}\_\mathrm{z},$ of the rescuers and $\mathrm{MWN}\_\mathrm{x},$ $\mathrm{MWN}\_\mathrm{y},$ $\mathrm{MWN}\_\mathrm{z}$ of the mineworkers. Therefore, all the steps in the mineworker-search route planning algorithm are the same as the route planning for rescue return algorithm except for steps (1) and (8). Steps (1) and (12) are modified as follows:

1. The R_Node or MW_Node in the network is set as the source point $V_S,$ and the ground exit is set as the target point $V_T.$ Initialize the effective route set $S(ER)$ and the new route set $S(NR)$ to null and set the total number C of rescue routes that need to be calculated.

2. The current source point $V_S$ is dynamically updated according to the latest coordinates$\mathrm{}\mathrm{RN}\_\mathrm{x},$ $\mathrm{RN}\_\mathrm{y},$ $\mathrm{RN}\_\mathrm{z}$ of the rescuers or $\mathrm{MWN}\_\mathrm{x},$ $\mathrm{MWN}\_\mathrm{y},$ $\mathrm{MWN}\_\mathrm{z}$ of the mineworkers.

4. Simulation experiments and results

4.1. Constructing a 3 D network of roadways

A 3 D network of roadways is constructed based on the plane drawing of mining engineering in this paper. The MineRoadwayNetwork class designed in this paper is used to create geometric objects in the 3 D roadway network model in the computer memory. Based on the TerraExplorer 6.6.1 development library provided by the Skyline platform, the 3 D rescue route planning simulation system is developed. The static objects, such as 3 D tunnel bodies, and the dynamic objects, such as rescue routes and personnel positions, are built in the system. The rescue route planning simulation function and some auxiliary functions such as distance measurement, view control operation and network communication are implemented in the system. The main interface of the system is shown in Figure 3.

Figure 3. The 3 D scene and models in the simulation system.

4.2. Simulation of walking speed and water level

The data simulation software running on the server is used to dynamically simulate the water level of each roadway as well as the speeds and current position of underground rescuers and mineworkers. The simulated data is transmitted in real time through the TCP/IP protocol to the simulation system running on the client. The data simulation software is shown as Figure 4.

Figure 4. Data simulation software.

4.2.1. Simulation of walking speed

According to the related literature (Fang et al. 2011), the moving speed of the underground personnel in the horizontal roadway is set to $v=1.3\mathrm{m}/\mathrm{s}$ by default. The default movement speed of the underground personnel in the horizontal roadway can be modified according the actual situation with the data simulation software. The slope and water level of roadway are two important factors that affect the walking speed, and they correspond to two coefficients named $K_s$ and $K_w$ as defined in Section 2.3. The walking speed is calculated with Eq.(3). (3) $$v_{ij}={v/(K}_s\times K_w)$$(3)

Where $v_{ij}$ denotes the actual walking speed between vertex $i$ and vertex $j;$ $K_s$ denotes the influence coefficient of the slope of the roadway; $K_w$ denotes the influence coefficient of the water level of the roadway.

The time it takes to walk to the next position is calculated based on the ratio of the length of the current roadway to the walking speed of the person. The time is calculated with Eq.(4). (4) $$t_{ij}=\frac{l_{ij}}{v_{ij}}$$(4)

Where $l_{ij}$ denotes the length of the roadway between vertex $i$ and vertex $j;$ $v_{ij}$ denotes the walking speed when the rescuers walks on the roadway between the vertex $i$ and the vertex $j.$

According to the speed and time, the simulated position of the rescuers at any time in the roadway can be calculated. The position is calculated with Eq.(5). (5) $$\left.\begin{array}{c}X=X_i-\frac{X_i-X_j}{t_{ij}}\\ Y=Y_i-\frac{Y_i-Y_j}{t_{ij}}\\ Z=Z_i-\frac{Z_i-Z_j}{t_{ij}}\end{array}\right\}$$(5)

Where $X$ denotes the $x$ coordinate of the rescuers' current position; $Y$ denotes the $y$ coordinate of the rescuers' current position;$Z$ denotes the $z$ coordinate of the rescuers' current position; $X_i$ denotes the $x$ coordinate of the starting point of the roadway;$Y_i$ denotes the $y$ coordinate of the starting point of the roadway; and $Z_i$ denotes the $z$ coordinate of the starting point of the roadway.

4.2.2. Simulation of water level

The water capacity of each roadway in the mine is fixed, but the water yield is dynamic and the number of water inrush points may increase. The mine water level monitoring system based on the Internet of Things and sensing technologies can collect the water level of mine roadways in real time and realize real-time transmission, storage and remote access of monitoring data. Due to the absence of sensor water level monitoring data, the dynamic water level simulation software is developed to calculate the dynamic change of water level in the roadway in this study. In order to carry out the simulation and calculation, it is assumed that the mine roadway is in shape of cuboid, the water volume per unit length of each roadway is the same. When the water volume per second filled in the roadway is a constant, hence the real-time water level in each roadway can be calculated. The water level is calculated with Eq. (6) (Ma and Liu 2015). (6) $$h=\left\{\begin{array}{l}\frac{V}{WL},(\alpha =0)\\ \sqrt{\frac{V\text{sin}2\alpha }{W}},(0<\alpha <90,0\le V\le \frac{W{H}^2}{2\text{tan}\alpha })\\ \frac{2V\text{sin}\alpha +W{H}^2\text{cos}\alpha }{2WH},(0<\alpha <90,\frac{W{H}^2}{2\text{tan}\alpha }\le V\le \mathit{WHL}-\frac{W{H}^2}{2\text{tan}\alpha })\\ H\text{cos}\alpha +L\text{sin}\alpha -\sqrt{\frac{(\mathit{WHL}-C)\text{sin}2\alpha }{W}},(0<\alpha <90,\mathit{WHL}-\frac{W{H}^2}{2\text{tan}\alpha }\le V\le \mathit{WHL})\\ \frac{V}{WH},(\alpha =90)\end{array}\right.\mathrm{}$$(6)

Where $h$ denotes the height of the water level in the roadway; $V$ denotes the amount of water in the roadway; $\alpha$ denotes the inclination angle of the roadway; $W$ denotes the width of the underside of the roadway; $L$ denotes the length of the roadway; and $H$ denotes the height of cuboid of the roadway. The parameters are indicated in the Figure 5.

Figure 5. The diagram of parameters in the water level calculating equation.

4.3. Dynamic rescue route planning simulation

4.3.1. Simulation of route planning for mineworker-search

It is assumed that the mineworkers at vertex V need to be rescued because of the water inrush into the mine. After starting the water inrush simulation, the water inrush rate is set as 600 m^3/h. At the beginning of the rescue route planning, take the mine entrance point (vertex V71) as the starting point, and vertex V193 as the target point to carry out the rescue route analysis. According to the current weights of the edges in the 3 D roadway network, the route-planning algorithm for mineworker-search is executed. Fourteen potential routes are searched in total by the algorithm, three routes with smaller weights are list in Table 3, and the route with least weight (Route 1) is the current optimal route. The IDs of the vertices on the planned route for mineworker-search are sequentially listed in Table 3.

Table 3. The first three routes with smaller weights searched in initial planning for mineworker-search.

Optional Route	Weight	Vertex
Route 1	114906	$\mathrm{V}71\to \mathrm{V}2\to \mathrm{V}73\to \mathrm{V}8\to \mathrm{V}152\to \mathrm{V}98\to \mathrm{V}84\to \mathrm{V}83\to \mathrm{V}124\to \mathrm{V}138\to \mathrm{V}193$
Route 2	115727	$\mathrm{V}71\to \mathrm{V}2\to \mathrm{V}73\to \mathrm{V}8\to \mathrm{V}152\to \mathrm{V}192\to \mathrm{V}166\to \mathrm{V}59\to \mathrm{V}58\to \mathrm{V}164\to \mathrm{V}57\to \mathrm{V}56\to \mathrm{V}11\to \mathrm{V}61\to \mathrm{V}12\to \mathrm{V}14\to \mathrm{V}16\to \mathrm{V}55\to \mathrm{V}92\to \mathrm{V}95\to \mathrm{V}97\to \mathrm{V}90\to \mathrm{V}54\to \mathrm{V}68\to \mathrm{V}66\to \mathrm{V}53\to \mathrm{V}52\to \mathrm{V}172\to \mathrm{V}193$
Route 3	117475	$\mathrm{V}71\to \mathrm{V}2\to \mathrm{V}73\to \mathrm{V}8\to \mathrm{V}152\to \mathrm{V}192\to \mathrm{V}69\to \mathrm{V}18\to \mathrm{V}167\to \mathrm{V}77\to \mathrm{V}76\to \mathrm{V}60\to \mathrm{V}61\to \mathrm{V}12\to \mathrm{V}14\to \mathrm{V}16\to \mathrm{V}55\to \mathrm{V}92\to \mathrm{V}95\to \mathrm{V}97\to \mathrm{V}90\to \mathrm{V}54\to \mathrm{V}68\to \mathrm{V}66\to \mathrm{V}53\to \mathrm{V}52\to \mathrm{V}172\to \mathrm{V}193$

The route-planning algorithm for mineworker-search is executed repeatedly after the initial planning, because the weights of the edges and the positions of the rescuers and mineworkers are dynamic. At the beginning of each re-planning phase, the starting point and the target point are updated according to the current positions of the rescuers and the mineworkers. For example, at the beginning of the re-planning, the starting point is the vertex V98 and the target point is still the vertex V193. However, the weight of the E111 roadway between the vertex V84 and the vertex V83 changes, and the roadway becomes impassable. At this time, two routes are searched in total by the algorithm, as shown in Table 4, the route with least weight (Route 1) is the current optimal route. Therefore, the re-planned route is different from the initial planned route, as can be seen in Table 4 and Figure 6. Until the position of rescuers coincides with the position of mineworkers, the process of route planning for mineworker-search remains unfinished.

Figure 6. Simulation of route planning for mineworker-search.

Table 4. The potential routes searched in re-planning for mineworker-search.

Optional Route	Weight	Vertex
Route 1	111821	$\mathrm{V}98\to \mathrm{V}84\to \mathrm{V}70\to \mathrm{V}80\to \mathrm{V}79\to \mathrm{V}22\to \mathrm{V}85\to \mathrm{V}169\to \mathrm{V}83\to \mathrm{V}124\to \mathrm{V}138\to \mathrm{V}193$
Route 2	277056	$\mathrm{V}98\to \mathrm{V}84\to \mathrm{V}70\to \mathrm{V}80\to \mathrm{V}79\to \mathrm{V}22\to \mathrm{V}168\to \mathrm{V}122\to \mathrm{V}78\to \mathrm{V}123\to \mathrm{V}102\to \mathrm{V}85\to \mathrm{V}169\to \mathrm{V}170\to \mathrm{V}171\to \mathrm{V}144\to \mathrm{V}145\to \mathrm{V}155\to \mathrm{V}132\to \mathrm{V}133\to \mathrm{V}165\to \mathrm{V}139\to \mathrm{V}140\to \mathrm{V}142\to \mathrm{V}154\to \mathrm{V}147\to \mathrm{V}143\to \mathrm{V}141\to \mathrm{V}146\to \mathrm{V}156\to \mathrm{V}135\to \mathrm{V}105\to \mathrm{V}100\to \mathrm{V}183\to \mathrm{V}182\to \mathrm{V}81\to \mathrm{V}167\to \mathrm{V}77\to \mathrm{V}76\to \mathrm{V}60\to \mathrm{V}7\to \mathrm{V}6\to \mathrm{V}68\to \mathrm{V}66\to \mathrm{V}53\to \mathrm{V}52\to \mathrm{V}172\to \mathrm{V}193$

The rescue route planning is dynamically simulated with the 3 D rescue route planning simulation system, and the results are displayed in Figure 6. The IDs of vertices and roadways in the rescue route are listed in Tables 3–5. In order to make the rescue route clearer, the corresponding IDs on the route are not shown in Figure 6. The red route in the Figure is the rescue route for the initial planning, and the purple route is the re-planned rescue route. The re-planned rescue route successfully avoided the flooded E111 roadway.

Table 5. The edges in the optimal routes searched in initial planning and re-planning for mineworker-search.

Initial planning	Vertexes	$\mathrm{V}71\to \mathrm{V}2\to \mathrm{V}73\to \mathrm{V}8\to \mathrm{V}152\to \mathrm{V}98\to \mathbf{V}84\to \mathbf{V}83\to \mathrm{V}124\to \mathrm{V}138\to \mathrm{V}193$
	Edges	$\mathrm{E}243\to \mathrm{E}242\to \mathrm{E}189\to \mathrm{E}187\to \mathrm{E}186\to \mathrm{E}185\to \mathbf{E}111\to \mathrm{E}87\to \mathrm{E}41\to \mathrm{E}35$
Re-planning	Vertexes	$\mathrm{V}98\to \mathbf{V}84\to \mathbf{V}70\to \mathbf{V}80\to \mathbf{V}79\to \mathbf{V}22\to \mathbf{V}85\to \mathbf{V}169\to \mathbf{V}83\to \mathrm{V}124\to \mathrm{V}138\to \mathrm{V}193$
	Edges	$\mathrm{E}185\to \mathbf{E}135\to \mathbf{E}128\to \mathbf{E}127\to \mathbf{E}110\to \mathbf{E}109\to \mathbf{E}108\to \mathbf{E}107\to \mathrm{E}87\to \mathrm{E}41\to \mathrm{E}35$

4.3.2. Simulation of route planning for rescue return

When the process of route planning for mineworker-search is complete, the process of route planning for the rescue return begins. The planning algorithms in the two processes are similar, however, except that the starting point (vertex V71) in the previous planning process is set as the target point in the return planning process, and the current target point (vertex V193) in the previous planning process is set as the starting point in the return planning process. At this time, there are 2 routes are searched in total by the route-planning algorithm for rescue return, as shown in Table 6, the route with least weight (Route 1) is the current optimal route for rescue return.

Table 6. The potential routes with smaller weights searched in planning for rescue return.

Optional Route	Weight	Vertex
Route 1	161110	$\mathrm{V}193\to \mathrm{V}172\to \mathrm{V}52\to \mathrm{V}53\to \mathrm{V}66\to \mathrm{V}68\to \mathrm{V}54\to \mathrm{V}90\to \mathrm{V}97\to \mathrm{V}95\to \mathrm{V}92\to \mathrm{V}55\to \mathrm{V}16\to \mathrm{V}14\to \mathrm{V}12\to \mathrm{V}61\to \mathrm{V}11\to \mathrm{V}56\to \mathrm{V}57\to \mathrm{V}164\to \mathrm{V}58\to \mathrm{V}59\to \mathrm{V}166\to \mathrm{V}192\to \mathrm{V}152\to \mathrm{V}8\to \mathrm{V}73\to \mathrm{V}2\to \mathrm{V}71$
Route 2	199209	$\mathrm{V}193\to \mathrm{V}172\to \mathrm{V}52\to \mathrm{V}53\to \mathrm{V}66\to \mathrm{V}68\to \mathrm{V}54\to \mathrm{V}90\to \mathrm{V}97\to \mathrm{V}95\to \mathrm{V}92\to \mathrm{V}55\to \mathrm{V}16\to \mathrm{V}14\to \mathrm{V}12\to \mathrm{V}61\to \mathrm{V}60\to \mathrm{V}76\to \mathrm{V}77\to \mathrm{V}168\to \mathrm{V}22\to \mathrm{V}79\to \mathrm{V}181\to \mathrm{V}184\to \mathrm{V}183\to \mathrm{V}100\to \mathrm{V}105\to \mathrm{V}135\to \mathrm{V}132\to \mathrm{V}155\to \mathrm{V}145\to \mathrm{V}144\to \mathrm{V}171\to \mathrm{V}170\to \mathrm{V}169\to \mathrm{V}83\to \mathrm{V}84\to \mathrm{V}98\to \mathrm{V}23\to \mathrm{V}21\to \mathrm{V}74\to \mathrm{V}73\to \mathrm{V}2\to \mathrm{V}71$

The IDs of the vertices on the planned return route and the IDs of the edges of planned return route are sequentially listed in Table 4. The red route is the planned return route as shown in Figure 7. It can be seen that the planned route for mineworker-search and the planned route for rescue return do not overlap perfectly, because the weights of the edges in the 3 D roadway network vary dynamically during the two processes (Table 7).

Figure 7. Simulation of route planning for rescue return.

Table 7. The edges in the optimal routes searched in planning for rescue return.

Initial planning	Vertexes	$\mathrm{V}193\to \mathrm{V}172\to \mathrm{V}52\to \mathrm{V}53\to \mathrm{V}66\to \mathrm{V}68\to \mathrm{V}54\to \mathrm{V}90\to \mathrm{V}97\to \mathrm{V}95\to \mathrm{V}92\to \mathrm{V}55\to \mathrm{V}16\to \mathrm{V}14\to \mathrm{V}12\to \mathrm{V}61\to \mathrm{V}11\to \mathrm{V}56\to \mathrm{V}57\to \mathrm{V}164\to \mathrm{V}58\to \mathrm{V}59\to \mathrm{V}166\to \mathrm{V}192\to \mathrm{V}152\to \mathrm{V}8\to \mathrm{V}73\to \mathrm{V}2\to \mathrm{V}71$
	Edges	$\mathrm{E}34\to \mathrm{E}36\to \mathrm{E}38\to \mathrm{E}42\to \mathrm{E}45\to \mathrm{E}48\to \mathrm{E}55\to \mathrm{E}57\to \mathrm{E}60\to \mathrm{E}64\to \mathrm{E}66\to \mathrm{E}69\to \mathrm{E}78\to \mathrm{E}81\to \mathrm{E}84\to \mathrm{E}97\to \mathrm{E}113\to \mathrm{E}114\to \mathrm{E}118\to \mathrm{E}121\to \mathrm{E}123\to \mathrm{E}124\to \mathrm{E}143\to \mathrm{E}175\to \mathrm{E}187\to \mathrm{E}189\to \mathrm{E}242\to \mathrm{E}243$

5. Discussion

Mine roadways form a kind of network entity with typical three-dimensional spatial characteristics. There are topological relationships such as adjacency, intersection, and disjunction among the elements of the roadway network (Mei, Wu, and Liu 2013; Liu, Mao, and Mei 2015). In order to more vividly express such three-dimensional spatial relationships and feature information, the two-dimensional network model is extended to a three-dimensional roadway network model for the purposes of route planning in this paper. In the extended three-dimensional roadway network model, not only are the static vertices and network edges of the three-dimensional coordinates defined, but also the human entities are abstracted into movable, three-dimensional, dynamic nodes, and the various facilities in the underground are abstracted as non-movable, three-dimensional, static nodes. When determining the weight of the edges in the network, previous studies have quantified the factors affecting the passage and the length of the roadway as an equivalent path (Wang 2017) or equivalent length (Zhao et al. 2015). In order to highlight the dynamically changing characteristics of roadway accessibility, the product of the roadway length $L,$ the roadway slope influence coefficient $K_s,$ and the roadway water level influence coefficient $K_w$ is proposed as the dynamic integrated weight for each edge in in this paper. The costs of ascending and descending a given sloped roadway are not consistent. Therefore, the edges between vertices are no longer defined as directed or undirected, but as bi-directional edges with different weights in each direction.

During the rescue route planning, a rescue route search algorithm combining the Breadth-first search idea and the Dijkstra algorithm (Wang 2012; Wang 2017) is designed. The Breadth-first search algorithm can be used to calculate all accessible routes from a single source point to a single target, but when the number of vertices in the graph is large, its computational efficiency is very low. The Dijkstra algorithm can be used to calculate a shortest route from a single source point to other vertices, but not to calculate reachable non-shortest routes from a single source point to other vertices. In this paper, the two algorithms are effectively combined when designing the single-target rescue route planning algorithm so that the single-target rescue route planning algorithm can calculate the shortest route from the specified source point to the specified target point and the non-shortest passable route at the same time.

In previous studies, the path was not dynamically adjusted during the rescue (Yao et al. 2011; Wu, Lei, et al. 2013; Adjiski et al. 2015) planning or escape (Jalali and Noroozi 2009) route planning. In this paper, a dynamic adjustment method is designed for the rescue route planning, so that the planned route is more in line with the actual needs of the emergency rescue. There are two advantages to dynamically adjust the route during the rescue process. First, the water level in the roadway is dynamically changing. When one of the planned rescue routes becomes impassable, the rescue route needs to be re-planned. With reference to previous relevant research, the influence coefficients of the roadway slope (Zhao et al. 2015; Zhao and Zong 2015), the roadway water level (Fang et al. 2011; Wang, Zhang, and Li 2014; Cheng, Zhang, and Li 2014; Zhao et al. 2015; Zhao and Zong 2015; Wang 2017), and the water flow (Ma and Liu 2015; Li et al. 2013) are considered in the route-planning algorithm in this paper. Second, the position of the target may change before the rescuer reaches the target, so this factor is also considered in the algorithm. This gives the route planning method proposed in this paper a certain degree of rationality. At present, the 3 D network is an ideal model, and some complex conditions, such as equipment barriers and road roughness in the roadway, are not considered in this study. In addition, the algorithm proposed is suitable for rescue route planning, but not for self-rescue guiding. We will improve the model and the algorithm in further studies to account for more real-world conditions.

6. Conclusion

In order to solve the route planning problem during a mine water inrush hazard rescue operations, this paper constructs a mine 3 D network model of mine roadways, proposes a rescue route planning algorithm, and simulates an instance of single-target rescue route planning. The research in this paper has the following advantages:

1. Object-oriented thinking is used to construct a roadway network data model suitable for mine water inrush hazard route planning. When setting the weights of the edges in the roadway network model, the concept of dynamic integrated weight is proposed. The dynamic comprehensive weight accounts for the influence coefficients of both the roadway water level and the roadway slope as well as the spatial distance, so as to characterize the traffic capacity of all roadways in the mine during the water inrush event.

2. The rescue route planning is divided into two processes: route planning for mineworker-search underground and route planning for rescue return. Based on the idea of graph Breadth-first search and the Dijkstra algorithm, the single-objective rescue route planning algorithm is designed and implemented. The rescue route calculated using this algorithm is not only shorter but safer as well.

3. This paper designs a simulation experiment in a 3D scene. In the simulation experiment, when the weight of the planned route is updated, the route planning algorithm dynamically adjusts the planned rescue route to account for current personnel positions and roadway water levels.

Acknowledgments

The authors are grateful to the editor and the reviewers for their valuable comments and suggestions for this paper.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This research was supported by the Major Science and Technology Innovation Projects of Shandong Province [grant number 2019JZZY020103], the National Key Research and Development Program of China [grant number 2017YFC1405004].