A novel three-value grid scheme and rescue path planning algorithm for building fire

Abstract

The 0-1 grid method is commonly used to divide a fire building into fully passable and fully impassable areas. Firefighters are only able to perform rescue tasks in the fully passable areas. However, in an actual building fire environment, there are three types of areas: fully impassable areas (areas blocked by obstacles or with heavy smoke and fire), fully passable areas, and partially passable areas (areas without obstacles or fire, but with some smoke risk). Due to the urgency of rescue, firefighters can consider conducting rescue tasks in both fully passable and partially passable areas to save valuable rescue time. To address this issue, we propose a three-value grid method, which classifies the fire environment into fully impassable areas, fully passable areas, and partially passable areas, represented by 1, 0, and 0.5, respectively. Considering that the ACO algorithm is prone to local optimum, we propose an enhanced ant colony algorithm (EACO) to solve the fire rescue path planning problem. The EACO introduces an adaptive heuristic function, a new pheromone increment strategy, and a pheromone segmentation rule to predict the shortest rescue path in the fire environment. Moreover, the EACO takes into account both the path length and the risk to balance rescue effectiveness and safety. Experiments show that the EACO obtains the shortest rescue path, which demonstrates its strong path planning capability. The three-value grid method and the path planning algorithm take reasonable application requirements into account.

Keywords

Fire rescue path planning 0-1 grid method three-value grid method EACO

1 Introduction

Building fire constantly threatens public safety, as it can cause property damage and casualties [1]. The smoke spreads rapidly in a building due to the complex structure of the building, and it makes the rescue more difficult [2]. Therefore, it is essential to plan an optimal fire rescue path [3, 4] from the starting point to the ending point [5]. Existing methods for path planning fall into two main categories: traditional algorithms and swarm intelligence algorithms. The traditional algorithms for path planning mainly include the artificial potential field method, the Dijkstra algorithm, and the A* algorithm [6 –8]. The swarm intelligence algorithms for path planning mainly include the particle swarm algorithm, the genetic algorithm, and the ant colony algorithm [9 –11]. Traditional algorithms are efficient only in simple environments and cannot effectively deal with complex environments. Though swarm intelligence algorithms perform well in complex environments, which suffer from the problems of premature convergence and local extremes. Therefore, it is necessary to study new path planning algorithms.

The ant colony algorithm (ACO) simulates the foraging behavior of the ants [12]. It is a robust parallel algorithm and performs well in solving path planning. Due to the problems in ACO such as stagnation and local optimum, many scholars improved it and used it for path planning. Yang et al. [13] proposed a PA-C-IACO algorithm which redefined the degree of heuristic and pheromone concentration increments for transfer between intersections in the ant colony algorithm and incorporated a reward mechanism during the pheromone update process, but the algorithm has a high time complexity. Liu et al. [14] used a quantum ant colony algorithm for rescue path planning, but it did not validate the algorithm in complex fire environments. Huang et al. [15] proposed an ant colony evacuation planner (ACEP) and used it for multi-path crowd rescue, but the algorithm was only validated and analyzed in small-scale rescue scenarios. Goodwin et al. [16] used the ACO algorithm to simulate the path planning process in a fire environment, but the direct use of the ACO algorithm will fall into the local optimum, and the algorithm can be considered to be improved. Wang et al. [17] proposed a cellular ant colony optimization algorithm and used it for emergency rescue path planning for passenger ships. Yang et al. [18] used the ACO algorithm for the pedestrian rescue process, but it did not consider that the ACO algorithm is easy to fall into the local optimum problem. Xu et al. [19] proposed an IACO algorithm to plan rescue paths in complex fire scenarios. Singhal et al. [20] provided an overview of the ACO algorithm for solving fire rescue path planning, it was not analyzed in terms of real fire scenarios. Overall, it is necessary to consider the improvement of the ACO algorithm to enhance its search quality. Meanwhile, the effectiveness of the algorithm needs to be verified in different fire scenarios.

In the fire rescue path planning problem, the 0-1 grid method [21, 22] is generally used to divide the fire scene into fully passable and fully impassable areas, i.e., the 0-value grid corresponds to the fully passable area and the 1-value grid corresponds to the impassable area, and use path planning algorithms to carry out path planning in the fully passable areas. However, the actual fire scene usually includes fully impassable areas (areas blocked by obstacles or areas with large fire and smoke), fully passable areas, and partially passable areas (areas without obstacles and fires but with a certain smoke hazard). Due to the urgency of the rescue, firefighters can rescue people in the partially passable areas and fully passable areas when the risk factor of the partially passable area is low, thus improving the rescue efficiency. Therefore, the 0-1 grid method does not fully meet the requirements of actual fire scenarios.

In the fire rescue path planning problem, while the traditional methods based on 0-1 grid do not completely meet the needs of the actual fire scene, the ACO algorithm tends to suffer from the problem of local optimal solutions. To solve these problems, this paper proposes an enhanced ant colony algorithm (EACO) based on a new three-value grid. We summarize our contributions as follows.

First, the traditional 0-1 grid method simply categorizes grids into fully passable and fully impassable grids and represent them by 0 and 1, respectively. However, the actual building fire environment has three areas: fully impassable areas (areas blocked by obstacles or areas with large fire and smoke), fully passable areas, and partially passable areas (areas without obstacles and fires but with a certain smoke hazard). Therefore, we propose a new three-value grid method to divide the fire environment into fully impassable areas, fully passable areas, and partially passable areas.

Second, in the actual rescue, we should consider both the total path length and the risk of rescue. When the rescue is urgent and the risk of the partially passable area is small, the rescuers with safety protection can obtain a shorter total path length and win valuable time for rescuing the trapped persons if they cross the partially passable area. To achieve this, we propose a new concept of weighted distance and use it to define the path length. Specifically, we multiply the actual distance of the partially passable area by a weight factor greater than one and add it to the total path length, where the weight factor becomes larger as the risk of the partially passable area increases. For the partially passable area, the setting of the suitable weight factor enables rescuers to reasonably evaluate the path and risk cost in the fully passable and partially passable areas. By contrast, the corresponding distance of the fully passable area is added to the total path length without processing.

Third, the ACO has a lower pheromone concentration in the early iterations, and it is necessary to guide the ant colony by the heuristic functions. However, the existing heuristic functions of the ACO only consider the distance between the current node and the next node, and do not take into consideration the guidance of the target node. This reduces the path planning ability of the algorithm. To overcome this problem, we not only establish a heuristic function based on the current node and the target node, but also introduce a linear decreasing factor to improve the heuristic function. In the early stage with lower pheromone concentration, the heuristic function guides the ant colony to the optimal path range. In the later stage, while the pheromone concentration gradually increases and plays a leading role, the heuristic function value gradually decreases. The new heuristic function enhances the path planning ability of EACO in the building fire.

Fourth, we introduce two mechanisms to solve the local optimum and iterative stagnation problems of ACO. On the one hand, EACO introduces a novel pheromone increment strategy. Specifically, we update the pheromones based on the average path length of each ant in the previous iteration. This makes the pheromone distribution uniform. In the following iterations, the ants will quickly concentrate within the range of the optimal path as the increases of the concentration of pheromones. This allows the algorithm to avoid the problem of local optimal. On the other hand, we use the pheromone segmentation rule to avoid stagnation. These two mechanisms can improve the path planning capability of the algorithm in the fire environment.

Sec. 2 introduces the 0-1 grid method and the ACO algorithm. Sec. 3 introduces a new three-value gird method. Sec. 4 introduces the EACO algorithm. Sec. 5 conducts experiments on the fire rescue path planning problem, and the experimental results verify the feasibility of the EACO algorithm.

2 Related research

2.1 The 0-1 grid method

In the fire rescue path planning problem, the 0-1 grid method [22, 23] divides the fire environment into fully passable areas and fully impassable areas. As shown in Fig. 1, the 0-value grid is a fully passable area, and the 1-value grid is a fully impassable area. The mathematical correspondence between the grid number and the coordinates is established by Equation (1).

Fig. 1

Traditional 0-1 grid map in fire environment model.

${\begin{matrix} x = a * \mod (m, col) - 0.5 \\ y = a * (col + 0.5 - ceil (m / col)) \end{matrix}$ (1) where col is the total number of columns of the grid map, m is the grid number, and a is the length of each grid. The (x, y) is the center coordinate of the grid. The mod () is a remainder function and the ceil () is an upward rounding function.

2.2 The ACO algorithm

The ACO was first developed to solve the traveling salesman problem (TSP) [24 –26]. The basic idea of ACO is that when ants forage for food, they leave pheromones on their routes to transmit information, and the ants choose the path with higher pheromone concentration to find the shortest foraging path. In the fire evacuation path planning problem, the ACO algorithm uses a positive feedback mechanism [27 –30], which makes the algorithm converge continuously to an optimal path in the search process. The algorithm consists of two stages, namely path selection and pheromone update.

For an ant k located at node i at the time t, we calculate the state transfer probability to visit the next node j. $p_{ij}^{k} = {\begin{matrix} \frac{[τ_{ij} (t)]^{α} [η_{ij} (t)]^{β}}{\sum [τ_{ij} (t)]^{α} [η_{ij} (t)]^{β}}, & j \in C \\ 0, & j \notin C \end{matrix}$ (2) $η_{ij} (t) = 1 / d_{ij}$ (3) where $p_{ij}^{k}$ is the probability that the ant k from node i to visit the next node j at the time t. The C is the set of achievable nodes at the next step, τ_ij (t) denotes the pheromone on the path (i, j) in the current iteration. η_ij (t) is the heuristic function, and d_ij represents the distance between node i and j. The α is the pheromone factor and β is the heuristic factor.

In each iteration, we use the pheromone update rule to update the pheromone concentration, and select the path with high pheromone concentration. The pheromone update rule is: $\begin{matrix} τ_{ij} (t + 1) = (1 - ρ) * τ_{ij} (t) + \sum_{k = 1}^{num} Δ τ_{ij}^{k}, \\ 0 < ρ < 1 \end{matrix}$ (4) where ρ denotes the pheromone evaporation coefficient and num is the number of ants. $Δ τ_{ij}^{k}$ is the pheromone increment, which represents the pheromone left by the ant k on the path (i, j). The equation for the pheromone increment is: $Δ τ_{ij}^{k} = {\begin{matrix} Q / L_{k}, & the ant k passes through path (i, j) \\ 0, & otherwise \end{matrix}$ (5) where L_k is the total length of the path taken by the ant k in this cycle and Q is the strength of the pheromone.

3 A new grid definition method for building fire environment

3.1 Environment description

For fire rescue path planning in a building, we make three assumptions about the building. First, the building is a two-dimensional environment. Second, the fire environment of the building is divided into fully impassable areas, fully passable areas, and partially passable areas, respectively. Third, a rescuer is represented by a point.

3.2 Three-value grid scheme

In traditional fire rescue path planning, the 0-1 grid method simply classifies fire environments into fully passable areas and fully impassable areas. However, the actual building fire scene contains three different types of areas: fully impassable areas (areas blocked by obstacles or areas with severe fire and smoke), fully passable areas, and partially passable areas (areas without obstacles and fires but with a certain smoke hazard). The 0-1 grid method is not entirely consistent with the actual fire scenes. To solve this problem, we propose a three-value grid method, which divides the fire environment into fully impassable areas, fully passable areas, and partially passable areas and represent them by 1, 0, and 0.5, respectively.

As shown in Fig. 2 (a), the white grid is the fully passable area, the black grid is the fully impassable area, the green grid is the partially passable area, and the red grid is the fire source. As shown in Fig. 2 (b), to facilitate the optimization of the algorithm, we use the three-value grid method to transform the 10*10 fire environment model into a 0–0.5–1 grid map.

Fig. 2

The fire scene model of the three different types of areas and the corresponding three-value grid map.

4 The EACO algorithm

The proper choice of path nodes is the key to solving the fire rescue path planning problem. Traditional algorithms generally use the traditional 0-1 grid method to select the path nodes in the fully passable areas. By contrast, our three-value grid method can select the path nodes both in the fully passable areas and partially passable areas. Due to the urgency of fire rescue time, the rescuers with safety protection can obtain a shorter total path length and win valuable time for rescuing the trapped persons if they cross the partially passable area based on actual conditions. Therefore, we design the EACO algorithm to plan the rescue path, the rescuers can pass both fully passable and partially passable areas. As there is some risk if the rescuers purse shorter distance and choose the partially passable areas, we punish the partially passable areas by multiplying the actual distance value of the partially passable area by a weight factor greater than one. A larger weight factor means a higher the risk to cross a partially passable area. For the partially passable area, the setting of the suitable weight factor enables rescuers to reasonably evaluate the path and risk cost in the fully passable and partially passable areas. Our EACO algorithm extends the ACO in two ways.

Firstly, ECAO uses a dynamic heuristic function to guide the optimization procedure. ACO has a lower pheromone concentration, and its guiding effect on the colony is weaker in the early iterations. Thus, it is necessary to guide the ant colony by the heuristic functions. However, the heuristic function in ACO only considers the distance between the current node and the next node. To overcome this problem, we establish a heuristic function based on both the current node and the target node and introduce a linear decreasing factor to improve the heuristic function. In the early iterations, the heuristic function values have a larger guiding effect on the EACO due to the small pheromone concentration. In the late iterations, the pheromone concentration gradually increases and the value of the heuristic function gradually decreases. The new heuristic function enhances the path planning capability of EACO in the fire problem.

Secondly, ECAO uses pheromone segmentation rules to avoid the stagnation problem in ACO. To solve the local optimal problem in ACO, we improve the pheromone increment strategy and update the pheromone based on average the path lengths of all ants in the previous iteration. This makes the pheromone distribution uniform. In the following iterations, as the pheromone concentration increases, the ants will quickly concentrate in the optimal path range and avoid the local optimal solutions. In general, the EACO improves the selection of optimal path nodes and is more suitable for solving path planning problems. Figure 3 shows the execution flow of EACO. Algorithm 1 is the pseudo-code of EACO.

Fig. 3

Execution flow of EACO.

4.1 The weighted distance of the partially passable area

In traditional fire rescue path planning, rescuers select path nodes only in fully passable areas. This makes the rescue time longer. To save rescue time, the rescuers with safety protection can obtain a shorter total path length and win valuable time for rescuing the trapped persons if they cross the partially passable area. There is some risk if the rescuers choose the partially passable areas and pursue shorter distances. Therefore, we multiply the actual distance of the partially passable area by a weighting factor greater than one and add it to the total length of the path, where the weight factor becomes larger as the risk of the partially passable area increases. For the partially passable area, the setting of the suitable weight factor enables rescuers to reasonably evaluate the path and risk cost in the fully passable and partially passable areas. By contrast, the corresponding distance of the fully passable area is added to the total path length without processing.

Let the rescuer locates at the current node i and the node of the partially passable area be j. The weighted distance f of the rescuer from the current node i into the node of the partially passable area j is: $f = w * g$ (6) $g = \sqrt{(x_{i} - x_{j})^{2} + (y_{i} - y_{j})^{2}}$ (7) where g is the actual distance from the current node i to the partially passable area node j, and the parameter w is the weighting factor. The (x_i, y_i) is the position of the rescuers at node i, and the (x_j, y_j) is the position of node j in the partially passable area.

4.2 Adaptive heuristic function

In the early iterations, the pheromone concentration of ACO is lower and its guiding effect on the colony is weaker. Thus, it is necessary to guide the ant colony by the heuristic functions. However, the heuristic function of ACO only considers the distance between the current node and the next node, which is fixed to be 1 or 1.4142. To overcome this problem, we establish a heuristic function for the current node and the target node and introduce a linearly decreasing factor to improve the guiding role of the heuristic function. In the early iterations, the heuristic function values have a larger guiding effect on the ACO and overcome the problems induced by the small pheromone concentration. In the optimization procedure, the pheromone concentration gradually increases and the heuristic function value gradually decreases. In the later iterations, the pheromone plays a guiding role. The new heuristic function enhances the selection of optimal path nodes and improves the path planning capability: $η_{iE} (t) = \frac{1}{d_{iE}} * ξ$ (8) where η_iE is the heuristic function defined for the current node i and the target node E, d_iE is the distance between the current node i and the target node E, and ξ is a linear decreasing factor. $ξ = ξ_{\max} - ((ξ_{\max} - ξ_{\min}) / maxiter) * iter$ (9) where iter is the current iteration number, maxiter is the maximum iteration number, ξ_max = 1 is the maximum linear decreasing factor, and ξ_min = 0.001 is the minimum linear decreasing factor. In the early iterations, the parameter ξ is close to 1, and the pheromone concentration is lower. At this time, the heuristic function value has a larger guiding effect on the ant colony. In the later iterations, the parameter ξ is close to 0.001, the pheromone concentration gradually increases, and the heuristic function value gradually decreases. At this time, the pheromone plays a leading role.

Algorithm 1. The pseudo-code of EACO
1: Use the three-valued grid method to establish the fire environment and calculate the node coordinates by Equation (1).
2: Initialize the parameters. The starting point S, the ending point E, the number of ants num, the maximum number of iterations maxiter, the current number of iterations iter, the pheromone heuristic factor α, the heuristic factor β, the pheromone evaporation coefficient ρ, and the tabu list Tab.
3: While (iter ⩽ Maxiter)
4: fork = 1 : num
5: While the ant kdoes not reach the ending point E
6: Place ants on the starting point and add the starting point to the tabu list
7: Use Equation (2) to find the next node j
8: Determine whether the nodes j pass through the partially passable area and if so, using Equations (6-7) to calculate the weighted distance between the path nodes.
9: Update path length and path nodes
10: End While
11: End for
12: fork = 1 : num
13:
quad Calculate the pheromone increment by Equations (10-11)
14: END for
15: Update pheromones by Equation (4) and Equation (12)
16: Update the heuristic function values by Equations (8-9).
17: iter = iter + 1
18: End While
19: return the optimal path length and path nodes

4.3 A new pheromone increment strategy

In the fire rescue path planning problem, the distribution of pheromones in the ACO is not even as the path lengths of the ants are different. Due to this, the algorithm tends to be trapped in the local optimal solutions, which reduces the path planning capability of ACO. To address this issue, we propose a new pheromone increment strategy. Specifically, we update the pheromones based on the average path length of each ant in the previous iteration. In this way, the pheromones are uniformly distributed. In the optimization procedure, the ants will quickly concentrate within the range of the optimal path as the pheromone concentrations increase. It allows the algorithm to avoid the problem of local optimum. The modified pheromone increment is defined as follows:

$\begin{matrix} Δ τ_{ij}^{k} = \\ {\begin{matrix} Q / L_{avg}, & the ant k passes through path (i, j) \\ 0, & otherwise \end{matrix} \end{matrix}$ (10) $L_{avg} = (\sum_{k = 1}^{num} L_{k}) / num$ (11) where L_avg is the average path length of all ants in the previous iteration, num is the number of ants, and Q is the strength of the pheromone.

To avoid stagnation of the algorithm in the search process, we restrict the pheromone concentration values in the set [τ_min, τ_max] and use segment rules to update the pheromones, as in Equation (12). $τ_{ij} (t) = {\begin{matrix} τ_{\max} / 1000, & τ_{ij} (t) ⩽ τ_{\min} \\ τ_{ij} (t), & τ_{\min} ⩽ τ_{ij} (t) ⩽ τ_{\max} \\ τ_{\max}, & τ_{ij} (t) ⩾ τ_{\max} \end{matrix}$ (12)

where τ_min is the minimum pheromone concentration and τ_max is the maximum pheromone concentration.

5 Experiment simulation and analysis

In the fire rescue path planning problem, we evaluate the ACO [12], IACO [19], and EACO in the three fire environments visualized in Fig. 4. First, we analyze the parameter selection of EACO in fire environment 1. Then, we evaluate these algorithms in both simple and complex fire environments for rescue path planning. The simulation environment is as follows: Windows10 64 bit; processor Intel (R) Core (TM) i5-8300 H; memory 8 GB; simulation software: MATLAB R2017a.

Fig. 4

Four fire environments.

In Fig. 4, the yellow grids show the starting point and ending points, respectively. The red grids are the fire sources, and the green grids are the partially passable areas. In the iterative calculation process of path optimization and the final total path length, the weighted distance value is adopted for the partially passable area instead of the original mathematical distance value.

5.1 Parameter selection of algorithm

In the fire rescue path planning problem, a suitable set of algorithm parameters can plan the shortest rescue path. We test the importance of three parameters, including the pheromone factor α, the heuristic factor β, and the pheromone evaporation coefficient ρ. In each experiment, we fix one parameter and change the other two. To facilitate the experimental analysis, we use the optimal path length and the optimal number of iterations as the evaluation metrics. Fire environment 1 in Fig. 4 is the test environment.

5.1.1 Parameter selection of algorithm α

In fire environment 1, we set the parameters as follows: num = 50, maxiter = 100, β = 5, Q = 1, ρ = 0.5, w = 1.1. The parameter α takes the values of {0.5,0.6,...,1.4} to conduct a series of experiments. As shown in Fig. 5-6, when α ∈ [0.9, 1.1], the EACO converges quickly and can search the global optimal path. As α becomes larger, the convergence rate of the EACO is improved, but the global search ability gradually decreases.

Fig. 5

Relationship between the α and the number of iterations.

Fig. 6

Relationship between the α and the optimal path length.

5.1.2 Heuristic factor β

In fire environment 1, we set the parameters as follows: num = 50, maxiter = 100, α = 0 . 9, Q = 1, ρ = 0.5, w = 1.1. The parameter β takes the values of {1,2,...,9} to conduct a series of experiments. As shown in Fig. 7-8, when β ∈ [5, 9], the performance of EACO is better than ACO. When β ∈ [7, 9], the ACO and the EACO obtain the same path length, while EACO converges faster than ACO.

Fig. 7

Relationship between the β and the number of iterations.

Fig. 8

Relationship between the β and the optimal path length.

5.1.3 Pheromone evaporation coefficient ρ

In fire environment 1, we set the parameters as follows: num = 50, maxiter = 100, α = 0 . 9, β = 7, Q = 1, w = 1.1. The parameter ρ takes the values of {0.1,0.2,...,0.8} to conduct a series of experiments. As shown in Fig. 9-10, when ρ ∈ [0.5, 0.8], the solving ability of EACO is better than ACO. The optimal path length of the algorithm is 34.9706, and the minimum number of iterations is 12.

Fig. 9

Relationship between the ρ and the number of iterations.

Fig. 10

Relationship between the ρ and the optimal path length.

5.2 Rescue path planning in fire environments

To verify the performance of EACO in different fire environments, this paper runs the ACO [12], IACO [19], and EACO for rescue path planning in 20×20 and 30×30 fire environments, respectively. Table 1 lists the parameters of the three algorithms.

Table 1
Parameter setting of the three algorithms

Algorithms Population Iteration Parameters

ACO [12] 50 100 α = 0.9, β = 7, ρ = 0.8, Q = 1

IACO [19] 50 100 α = 1, β = 8, ρ = 0.5, Q₀ = 50

EACO 50 100 α = 0.9, β = 7, ρ = 0.8, Q = 1, τ_max = 1

Algorithms	Population	Iteration	Parameters
ACO [12]	50	100	α = 0.9, β = 7, ρ = 0.8, Q = 1
IACO [19]	50	100	α = 1, β = 8, ρ = 0.5, Q₀ = 50
EACO	50	100	α = 0.9, β = 7, ρ = 0.8, Q = 1, τ_max = 1

5.2.1 The rescue path planning in 20×20 fire environment

To verify the effectiveness of EACO in simple fire environments, this section performs rescue path planning in the fire environment 2. In this environment, the starting point is (0.5, 19.5), and the ending point is (19.5, 0.5). We use three algorithms for fire rescue path planning, and each algorithm is run ten times independently. After the algorithm completes the path planning, we obtain the path nodes and the path length with weighted distance (also called weighted path length) and calculate the actual path length based on the path nodes. Table 2 lists the weighted path length and actual path length of the three algorithms, respectively, where () records the actual path length. Figure 11 shows the optimal path planning of the three algorithms with different weight factors. Figure 12 shows the average convergence curves of the three algorithms.

Table 2
The weighted path length and actual path length of the three algorithms

w Algorithms Optimal path length Worst path length Average path length

1.0 ACO 30.3848(30.3848) 31.2132(31.2132) 31.1061(31.1061)

IACO 30.3848(30.3848) 31.2132(31.2132) 31.0233(31.0233)

EACO 30.3848(30.3848) 31.2132(31.2132) 30.8333(30.8333)

1.1 ACO 31.3546(31.2132) 32.7262(32.3848) 31.7504(31.3889)

IACO 31.4546(31.2132) 32.2831(32.0416) 31.6216(31.2960)

EACO 30.7262(30.3848) 31.5546(31.2132) 30.9376(30.5262)

1.2 ACO 31.4960(31.2132) 32.0960(31.2132) 31.9346(31.2718)

IACO 31.6960(31.2132) 32.0960(31.2132) 31.9689(31.3061)

EACO 31.0676(30.3848) 31.8534(30.9706) 31.3448(30.5020)

1.3 ACO 31.7090(30.3848) 32.5375(31.2132) 32.1246(31.1304)

IACO 31.6948(30.9706) 33.0659(32.0416) 32.2618(31.4475)

EACO 31.4090(30.3848) 31.7090(30.3848) 31.6647(30.5505)

1.4 ACO 32.1505(30.3848) 32.9789(32.2132) 32.4018(31.1162)

IACO 31.7789(31.2132) 32.9789(31.2132) 32.4241(31.0818)

EACO 31.7789(31.2132) 32.1789(31.2132) 32.0047(30.7990)

1.5 ACO 31.9203(31.2132) 33.4203(31.2132) 32.7875(31.3304)

IACO 31.9203(31.2132) 33.5772(31.2132) 32.7738(31.4961)

EACO 31.9203(31.2132) 32.9203(31.2132) 32.5561(30.7990)

w	Algorithms	Optimal path length	Worst path length	Average path length
1.0	ACO	30.3848(30.3848)	31.2132(31.2132)	31.1061(31.1061)
	IACO	30.3848(30.3848)	31.2132(31.2132)	31.0233(31.0233)
	EACO	30.3848(30.3848)	31.2132(31.2132)	30.8333(30.8333)
1.1	ACO	31.3546(31.2132)	32.7262(32.3848)	31.7504(31.3889)
	IACO	31.4546(31.2132)	32.2831(32.0416)	31.6216(31.2960)
	EACO	30.7262(30.3848)	31.5546(31.2132)	30.9376(30.5262)
1.2	ACO	31.4960(31.2132)	32.0960(31.2132)	31.9346(31.2718)
	IACO	31.6960(31.2132)	32.0960(31.2132)	31.9689(31.3061)
	EACO	31.0676(30.3848)	31.8534(30.9706)	31.3448(30.5020)
1.3	ACO	31.7090(30.3848)	32.5375(31.2132)	32.1246(31.1304)
	IACO	31.6948(30.9706)	33.0659(32.0416)	32.2618(31.4475)
	EACO	31.4090(30.3848)	31.7090(30.3848)	31.6647(30.5505)
1.4	ACO	32.1505(30.3848)	32.9789(32.2132)	32.4018(31.1162)
	IACO	31.7789(31.2132)	32.9789(31.2132)	32.4241(31.0818)
	EACO	31.7789(31.2132)	32.1789(31.2132)	32.0047(30.7990)
1.5	ACO	31.9203(31.2132)	33.4203(31.2132)	32.7875(31.3304)
	IACO	31.9203(31.2132)	33.5772(31.2132)	32.7738(31.4961)
	EACO	31.9203(31.2132)	32.9203(31.2132)	32.5561(30.7990)

Fig. 11

Optimal path planning of the three algorithms with different weight factors.

Fig. 12

Average convergence curves of the three algorithms.

When the weight factor is 1, the partially passable areas are switched to fully passable areas. In this case, our method integrates the 0-1 grid method for rescue path planning and only selects path nodes in the fully passable areas. The output path length is equal to the actual path length. EACO performs better than the other two methods, as its average path length (30.8333) is lower than the other two algorithms and close to the optimal path length (30.3848).

When the weight factor takes values of {1.1, 1.2, 1.3, 1.4, 1.5}, our method uses the three-value grid strategy for rescue path planning in both the partially passable and the fully passable areas. The average weighted path length of EACO is lower than ACO and IACO. The partially passable area is less dangerous when the weight factor takes the value of {1.1, 1.2}. In this case, the rescuers with safety protection can pass through them to obtain the shortest rescue path and win valuable time to rescue the trapped people. As the weight factor is slightly larger than one, the weighted path length is close to the actual path length. The experiments demonstrate the effectiveness of EACO in simple fire environments. Table 1 Parameter setting of the three algorithms

As shown in Fig. 11, the partially passable area is less risky when the weight factor is small, the three algorithms cross the partially passable area many times, and the rescuers can enter the area to rescue the trapped people. As the weight factor increases, the rescuers reduce the chance to pass through the partially passable area. As shown in Fig. 12, the average weighted path length of the three algorithms gradually becomes larger as the weight factor increases.

5.2.2 The rescue path planning in 30×30 fire environment

To validate the effectiveness of EACO in complex fire environments, this section performs rescue path planning in fire environment 3. In this environment, the starting point is (0.5, 29.5), and the ending point is (29.5, 0.5). After the algorithm completes the path planning, we obtain the path nodes to calculate the actual path length. Table 3 lists the weighted path length and actual path length of the three algorithms, respectively, where () records the actual path length. Figure 13 shows the optimal path planning of the three algorithms with different weight factors. Figure 14 shows the average convergence curves of the three algorithms.

Table 3
The weighted path length and actual path length of the three algorithms

w Algorithms Optimal path length Worst path length Average path length

1 ACO 45.1127(45.2217) 45.9411(45.9411) 45.6926(45.6926)

IACO 44.5269(44.5269) 46.8701(46.8701) 45.3470(45.3470)

EACO 44.5269(44.5269) 45.3553(45.3553) 44.9026(44.9026)

1.1 ACO 45.8382(45.3553) 49.3098(48.5269) 46.8154(46.2926)

IACO 45.5955(45.1127) 46.3240(45.9411) 45.9083(45.3855)

EACO 45.0098(44.5269) 45.8382(45.1127) 45.5241(44.8784)

1.2 ACO 45.8784(45.1127) 48.5612(47.1127) 47.0134(45.9512)

IACO 46.1210(45.3553) 46.9068(45.3553) 46.4368(45.5410)

EACO 45.4926(44.5269) 46.3210(45.3553) 46.0962(45.1026)

1.3 ACO 46.7897(45.9411) 49.3897(47.9411) 47.5592(46.2482)

IACO 46.5039(45.3553) 47.0897(45.9411) 46.9225(45.6239)

EACO 45.9754(44.5269) 46.8039(45.3553) 46.6539(45.2725)

1.4 ACO 46.8867(45.3553) 48.6440(47.1127) 47.6297(45.8583)

IACO 46.8867(45.3553) 47.8725(45.9411) 47.3824(45.5310)

EACO 46.4583(44.5269) 47.2867(45.3553) 46.7851(45.0926)

1.5 ACO 47.3553(45.9411) 49.1127(45.6985) 48.0796(45.7654)

IACO 47.7696(45.3553) 48.3553(45.9411) 47.8953(45.5310)

EACO 46.7696(45.3553) 47.7696(45.3553) 47.3232(45.1654)

w	Algorithms	Optimal path length	Worst path length	Average path length
1	ACO	45.1127(45.2217)	45.9411(45.9411)	45.6926(45.6926)
	IACO	44.5269(44.5269)	46.8701(46.8701)	45.3470(45.3470)
	EACO	44.5269(44.5269)	45.3553(45.3553)	44.9026(44.9026)
1.1	ACO	45.8382(45.3553)	49.3098(48.5269)	46.8154(46.2926)
	IACO	45.5955(45.1127)	46.3240(45.9411)	45.9083(45.3855)
	EACO	45.0098(44.5269)	45.8382(45.1127)	45.5241(44.8784)
1.2	ACO	45.8784(45.1127)	48.5612(47.1127)	47.0134(45.9512)
	IACO	46.1210(45.3553)	46.9068(45.3553)	46.4368(45.5410)
	EACO	45.4926(44.5269)	46.3210(45.3553)	46.0962(45.1026)
1.3	ACO	46.7897(45.9411)	49.3897(47.9411)	47.5592(46.2482)
	IACO	46.5039(45.3553)	47.0897(45.9411)	46.9225(45.6239)
	EACO	45.9754(44.5269)	46.8039(45.3553)	46.6539(45.2725)
1.4	ACO	46.8867(45.3553)	48.6440(47.1127)	47.6297(45.8583)
	IACO	46.8867(45.3553)	47.8725(45.9411)	47.3824(45.5310)
	EACO	46.4583(44.5269)	47.2867(45.3553)	46.7851(45.0926)
1.5	ACO	47.3553(45.9411)	49.1127(45.6985)	48.0796(45.7654)
	IACO	47.7696(45.3553)	48.3553(45.9411)	47.8953(45.5310)
	EACO	46.7696(45.3553)	47.7696(45.3553)	47.3232(45.1654)

Fig. 13

Optimal path planning of the three algorithms with different weight factors.

Fig. 14

Average convergence curves of the three algorithms

As shown in Table 3, when the weight factor is 1, the partially passable areas of fire environment 3 are switched to the fully passable areas. In this case, our method integrates the 0-1 grid method for rescue path planning and only selects path nodes in the fully passable areas. The path length of this algorithm is equal to the actual path length, while the average path length of EACO is lower than the other two algorithms.

When the weight factor takes the values of {1.1, 1.2, 1.3, 1.4, 1.5}, the algorithm uses the three-value grid strategy for rescue path planning in both the partially passable and the fully passable areas. As the weight factor increases, the weighted path length of the three algorithms gradually becomes larger, indicating that the risk of the partially passable area gradually increases. The pheromone increment strategy and pheromone segmentation rule of EACO can avoid the algorithm falling into the local optimal solution, and thus the average weighted path length of EACO is lower than the other two algorithms. When the weight factor takes the values of {1.1,1.2}, the weighted path length is close to the actual path length, indicating that the risk of the partially passable area is lower and the rescuers can enter the area to rescue the trapped people.

When the weight factor takes the values of {1.3, 1.4, 1.5}, the partially passable area has higher risks and the rescuers should reduce the chance to pass through them. In this case, the difference between the weighted path length and the actual path length is larger. Experiments demonstrate the effectiveness of EACO in complex fire environments.

As shown in Fig. 13, the three algorithms cross the partially passable area many times when the weight factor is small. In this case, the rescuers with safety protection can pass through the partially passable area to obtain the shortest rescue path and win valuable time to rescue the trapped people. As the weight factor increases, the three algorithms gradually decrease the chance to pass through the partially passable area. With a weight factor of 1.5, ACO and IACO pass through three partially passable areas, while EACO passes through only two partially passable areas. As shown in Fig. 14, the average weighted path length of the three algorithms gradually becomes longer as the weight factor increases.

5.2.3 The rescue path planning in 40×40 fire environment

To validate the effectiveness of EACO in complex fire environments, this section performs rescue path planning in fire environment 4. In this environment, the starting point is (0.5, 39.5), and the ending point is (39.5, 0.5). After the algorithm completes the path planning, we obtain the path nodes to calculate the actual path length. Table 4 lists the weighted path length and actual path length of the three algorithms, respectively, where () records the actual path length. Figure 15 shows the optimal path planning of the three algorithms with different weight factors. Figure 16 shows the average convergence curves of the three algorithms.

Table 4
The weighted path length and actual path length of the three algorithms

w Algorithms Optimal path length Worst path length Average path length

1 ACO 65.2548(65.2548) 112.9533(112.9533) 73.3418(73.3418)

IACO 66.0833(66.0833) 82.6691(82.6691) 72.0833(72.0833)

EACO 62.4264(62.4264) 63.8406(63.8406) 63.0891(63.0891)

1.1 ACO 65.7377(65.2548) 75.1519(74.6690) 68.6577(68.2507)

IACO 66.3222(65.5980) 73.9377(73.2548) 73.6224(73.1761)

EACO 63.5950(63.0122) 64.4235(63.8046) 63.9063(63.3234)

1.2 ACO 65.5176(64.6690) 97.1911(96.2254) 74.3267(73.3176)

IACO 65.8347(64.6690) 78.1176(76.6690) 71.2056(70.2453)

EACO 63.5921(62.2154) 66.3034(65.2548) 64.6314(63.4889)

1.3 ACO 67.8749(66.4264) 78.8075(78.0833) 72.4312(71.2548)

IACO 67.2749(66.4264) 76.6691(76.6691) 73.1659(72.3619)

EACO 64.4607(63.0122) 65.9323(64.1838) 65.0892(63.4607)

1.4 ACO 68.1152(66.1838) 89.3970(84.3970) 74.4247(72.6767)

IACO 68.3210(67.3553) 79.6347(79.6347) 75.6210(75.4279)

EACO 65.1862(63.2548) 66.9436(65.0122) 65.9320(63.8406)

1.5 ACO 68.5477(67.8406) 84.5833(82.0833) 76.2197(75.0732)

IACO 70.9264(69.0122) 97.6396(97.6396) 78.2904(75.9176)

EACO 65.4264(63.0122) 66.8406(64.4264) 66.3548(63.8406)

w	Algorithms	Optimal path length	Worst path length	Average path length
1	ACO	65.2548(65.2548)	112.9533(112.9533)	73.3418(73.3418)
	IACO	66.0833(66.0833)	82.6691(82.6691)	72.0833(72.0833)
	EACO	62.4264(62.4264)	63.8406(63.8406)	63.0891(63.0891)
1.1	ACO	65.7377(65.2548)	75.1519(74.6690)	68.6577(68.2507)
	IACO	66.3222(65.5980)	73.9377(73.2548)	73.6224(73.1761)
	EACO	63.5950(63.0122)	64.4235(63.8046)	63.9063(63.3234)
1.2	ACO	65.5176(64.6690)	97.1911(96.2254)	74.3267(73.3176)
	IACO	65.8347(64.6690)	78.1176(76.6690)	71.2056(70.2453)
	EACO	63.5921(62.2154)	66.3034(65.2548)	64.6314(63.4889)
1.3	ACO	67.8749(66.4264)	78.8075(78.0833)	72.4312(71.2548)
	IACO	67.2749(66.4264)	76.6691(76.6691)	73.1659(72.3619)
	EACO	64.4607(63.0122)	65.9323(64.1838)	65.0892(63.4607)
1.4	ACO	68.1152(66.1838)	89.3970(84.3970)	74.4247(72.6767)
	IACO	68.3210(67.3553)	79.6347(79.6347)	75.6210(75.4279)
	EACO	65.1862(63.2548)	66.9436(65.0122)	65.9320(63.8406)
1.5	ACO	68.5477(67.8406)	84.5833(82.0833)	76.2197(75.0732)
	IACO	70.9264(69.0122)	97.6396(97.6396)	78.2904(75.9176)
	EACO	65.4264(63.0122)	66.8406(64.4264)	66.3548(63.8406)

Fig. 15

Optimal path planning of the three algorithms with different weight factors

Fig. 16

Average convergence curves of the three algorithms.

As shown in Table 4, when the weight factor is 1, the partially passable areas of fire environment 4 are switched to the fully passable areas. In this case, our method integrates the 0-1 grid method for rescue path planning and only selects path nodes in the fully passable areas. The path length of this algorithm is equal to the actual path length, while the average path length of EACO is lower than the other two algorithms.

When the weight factor takes the values of 1.1, 1.2, 1.3, 1.4, 1.5, the algorithm uses the three-value grid strategy for rescue path planning in both the partially passable and the fully passable areas. As the weight factor increases, the weighted path length of the three algorithms gradually becomes larger, indicating that the risk of the partially passable area gradually increases. Moreover, the average weighted path length of EACO is lower than the other two algorithms.

As shown in Fig. 15, the three algorithms cross the partially passable area many times when the weight factor is small. In this case, the rescuers with safety protection can pass through the partially passable area to obtain the shortest rescue path and win valuable time to rescue the trapped people. As the weight factor increases, the three algorithms gradually decrease the chance to pass through the partially passable area. As shown in Fig. 16, the average weighted path length of the three algorithms gradually becomes longer as the weight factor increases.

6 Conclusion

Existing algorithms for fire rescue path planning generally use the traditional 0-1 grid method to divide fire scenes into fully impassable and fully passable areas. In contrast, the actual fire scene includes fully impassable, fully passable, and partially passable areas. The 0-1 grid method does not fully consider the actual application requirements. To solve this problem, we propose a new three-value grid method and use three different values to represent the fully impassable areas, fully passable areas, and partially passable areas, respectively.

In the actual rescue, when the rescue is urgent and the risk of the partially passable area is small, rescuers with safety protection can obtain a shorter total path length and valuable time to rescue trapped people if they cross a partially passable area. Considering the danger of rescuers passing through partially passable areas, we propose the concept of weighted distance and the corresponding path length formula. Specifically, we multiply the actual distance of the partially passable area by a weighting factor greater than one and add it to the total path length, where the weighting factor becomes larger as the risk of the partially passable area increases. For partially passable areas, the setting of a suitable weighting factor enables rescuers to reasonably evaluate the path length and risk cost both in the fully passable and partially passable areas. By contrast, the corresponding distance of the fully passable area is added to the total path length without processing.

Based on the characteristics of the three-value grid method, this paper proposes an enhanced ant colony algorithm (EACO) for fire rescue path planning. We use an adaptive heuristic function to improve the path planning capability of ACO. The new pheromone increment strategy is also used to prevent the algorithm from falling into local optimal solutions. The pheromone segmentation rule is also used to avoid the stagnation of the algorithm.

In this paper, we use three fire environments to validate the effectiveness of EACO and experimentally compare EACO with the other two algorithms. The EACO is used for parameter selection in fire environment 1. In fire environment 2, EACO obtains the shortest rescue path. As the complexity of the fire environment increases, EACO obtains the optimal rescue path in fire environment 3-4. Experiments confirm the effectiveness of EACO in both simple and complex fire environments.

For future work, we will investigate two issues. First, this paper only studies the fire rescue path planning problem in two-dimensional scenarios, and we will study the fire rescue path planning problem in three-dimensional scenarios. Second, we will introduce temperature and CO volume fractions in the fire environment to facilitate path planning.

Footnotes

Acknowledgments

This work was supported by the Shenzhen Science and Technology Innovation Commission (Grant No. KCXFZ20211020163402004).

References

Kinateder , Brittany , Comunale , et al. Exit choice in an emergency evacuation scenario is influenced by exit familiarity and neighbor behavior[J], Safety Science 106 (2018), 170–175.

Rozo

K.R.

, Arellana

, Santander-Mercado

,et al. Modelling building emergency evacuation plans considering the dynamic behaviour of pedestrians using agent-based simulation[J], Safety Science 113 (2019), 276–284.

Lujak

and Giordani

, Centrality measures for evacuation: Finding agile evacuatio-n routes[J], Future Generation Computer Systems 83 (2018), 401–412.

Lujak

and Ossowski

, Evacuation route optimization architecture considering human factor[J], Ai Communications 30(1) (2017), 53–66.

Sudhakara

, Ganapathy

, Priyadharshini

, et al. Obstacle avoidance and navigation planning of a wheeled mobile robot using amended artificial potential field method[J], Procedia Computer Science 133 (2018), 998–1004.

Orozco-Rosas

, Montiel

and Sepúlveda

, Mobile robot path planning using membrane evolutionary artificial potential field[J], Applied Soft Computing 77 (2019), 236–251.

Mirahadi

and Mccabe

B.Y.

, EvacuSafe: A real-time model for building evacuation based on Dijkstra’s algorithm[J], Journal of Building Engineering 34 (2020), 101687.

Chen

Y.Q.

, Guo

J.L.

, Yang

, et al. Research on navigation of bidirectional A* algorithm based on ant colony algorithm[J], The Journal of Supercomputing 77(1) (2021), 1958–1975.

Che

, Liu

and Yu

, An improved ant colony optimization algorithm based on particle swarm optimization algorithm for path planning of autonomous underwater vehicle[J], Ambient Intell Human Comput 11 (2020), 3349–3354.

10.

Chen

and Gao

, Path planning and control of soccer robot based on genetic algorith-m[J], Journal of Ambient Intelligence and Humanized Computing 2019(1), 1–10.

11.

Jiao, Zhuqing, Ma, et al. A path planning method using adaptive polymorphic ant colony algorithm for smart wheelchairs[J], Journal of Computational Science 25 (2018), 50–57.

12.

Yen

C.T.

and Cheng

M.F.

, A study of fuzzy control with ant colony algorithm used in mobile robot for shortest path planning and obstacle avoidance[J], Microsyst Technol 24 (2018), 125–135.

13.

Yang

, Wu

, Xiong

, et al. Location and path planning for urban emergency rescue by a hybrid clustering and ant colony algorithm approach[J], Applied Soft Computing (2023), 110783.

14.

Liu

, Zhang

, Ma

, et al.Evacuation path optimization based on quantum ant co-lony algorithm[J], Advanced Engineering Informatics 30(3) (2016), 259–267.

15.

Huang

Z.M.

, Chen

W.N.

, Li

, et al. Ant Colony Evacuation Planner: An Ant Colony System With Incremental Flow Assignment for Multipath Crowd Evacuation[J], IEEE Transactions on Cybernetics 51(11) (2020), 5559–5572.

16.

Goodwin

, Granmo

O.C.

and Radianti

, Escape planning in realistic fire scenarios with Ant Colony Optimisation, Appl Intell 42 (2015), 24–35.

17.

Wang

, Zhang

and Xiao

, Emergency Evacuation Path Planning of Passenger Ship Based on Cellular Ant Optimization Model[J], Shanghai Jiaotong University 25 (2020), 721–726.

18.

Yang

, Yang

, Li

, et al. Obstacle avoidance in the improved social force model based on ant colony optimization during pedestrian evacuation[J], Physica A: Statistical Mechanics and its Applications 2021(8), 126256.

19.

, Huang

, Liu

, et al. Intelligent planning of fire evacuation routes using an improved ant colony optimization algorithm[J], Journal of Building Engineering 2022(61), 105208.

20.

Singhal

and Sahu

, Fire Evacuation using Ant Colony Optimization Algorithm[J], International Journal of Computer Applications 139(8) (2016), 17–20.

21.

Hao

, Chunfu

and Zhisheng

, Pedestrian evacuation flow simulation based on cellular automata[J], Acta Physica Sinica 58(07) (2009), 4523–4530.

22.

Lei

, Hao

, Mei

, et al. Simulation of pedestrian push-force in evacuation with congestion[J], Acta Physica Sinica 64(06) (2015), 92–101.

23.

Yoon

, Yoon

S.E.

, Lee

, et al. Recursive path planning using reduced states for car-like vehicles on grid maps[J], IEEE Transactions on Intelligent Transportation Systems 16(5) (2015), 2797–2813.

24.

Ouyang

X.Y.

and Yang

S.G.

, Obstacle avoidance path planning of mobile robots based o-n potential grid method[J], Control Engineering of China 21(1) (2014), 134–137.

25.

Shi

, Chen

, Li

, et al. Research on method of global path-planning for mobile robot based on ant-colony algorithm[J], Nongye Jixie Xuebao/Transactions of the Chinese Society of Agricultural Machinery 45(6) (2014), 53–57.

26.

Wang

, Bai

and Yue

, An Improved Ant Colony Algorithm for Solving TSP Proble-ms[J], Mathematics in Practice & Theory 42(4) (2012), 133–140.

27.

and Ding

, An Improved Ant Colony Algorithm and Application in the TSP[J], Systems Engineering-Theory & Practice 49(2) (2006), 45–51.

28.

Yao

, Chen

, Song

, et al.Fresh seafood delivery routing problem using an improved ant colony optimization[J], Annals of Operations Research 273(1-2) (2019), 163–186.

29.

Dentler

, Rosalie

, Danoy

, et al. Collision Avoidance Effects on the Mobility of a UAV Swarm Using Chaotic Ant Colony with Model Predictive Control[J], Journal of Intelligent & Robotic Systems 93(1/2) (2018), 227–243.

30.

Luo

, Wang

, Zheng

, et al. Research on path planning of mobile robot based on improved ant colony algorithm[J], Neural Computing and Applications 32 (2020), 1555–1566.

A novel three-value grid scheme and rescue path planning algorithm for building fire

Abstract

Keywords

1 Introduction

2 Related research

2.1 The 0-1 grid method

3.1 Environment description

3.2 Three-value grid scheme

5.1.1 Parameter selection of algorithm α

Table 1 Parameter setting of the three algorithms Algorithms Population Iteration Parameters ACO [12] 50 100 α = 0.9, β = 7, ρ = 0.8, Q = 1 IACO [19] 50 100 α = 1, β = 8, ρ = 0.5, Q0 = 50 EACO 50 100 α = 0.9, β = 7, ρ = 0.8, Q = 1, τ max = 1

Footnotes

Acknowledgments

References

Table 1
Parameter setting of the three algorithms

Algorithms Population Iteration Parameters

ACO [12] 50 100 α = 0.9, β = 7, ρ = 0.8, Q = 1

IACO [19] 50 100 α = 1, β = 8, ρ = 0.5, Q₀ = 50

EACO 50 100 α = 0.9, β = 7, ρ = 0.8, Q = 1, τ_max = 1