Indoor fire emergency evacuation path planning based on improved NavMesh algorithm

Abstract

With the acceleration of urbanization, the frequency of building fire incidents has been increasing year by year. Therefore, rapid, efficient, and safe evacuation from buildings has become an urgent and important task. A construction fire escape path planning method based on an improved NavMesh algorithm is proposed in this paper. Firstly, by using the method of local updates in the navigation grid, redundant computation is reduced, and the update time of the improved algorithm is about 6.8% of that of the original algorithm, immediate generation of navigation is achieved. Secondly, the heuristic function of the pathfinding algorithm is improved, and a multi-exit path planning mechanism is proposed to achieve more efficient, which can quickly plan a safe evacuation path away from the spreading fire and smoke in the event of a fire. Finally, a new evaluation index called Navigation Grid Complexity (NGC) is proposed and demonstrated to measure the quality of navigation grids. The feasibility and effectiveness of the proposed method are validated through simulation experiments on actual building models, which can provide real-time, efficient, intelligent, and safe path planning for rapid evacuation of evacuees in the fire scene.

Keywords

NavMesh path planning fire emergency evacuation dynamic environments

1 Introduction

Building fires are a common disaster accident with characteristics of suddenness, difficulty in control, and elevated risk. With the development of urbanization, there are increasingly more complex high-rise buildings, making rapid building fire evacuation path planning has become important research. In recent years, with the progress of computer technology, computer-based simulation of fire evacuation path planning has become one of the research hotspots [1 –3]. According to surveys, the main causes of casualties among evacuees in buildings are inhalation of smoke, inhalation of hot air, and burns due to the inability to evacuate in a timely manner during a fire. Rapid and timely evacuation is crucial for ensuring the safety of evacuees [4, 5]. In practical applications, Traditional fire emergency evacuation methods cannot effectively guide the evacuation of evacuees due to their failure to fully consider the impact of smoke and flame spread on path planning [6].

Traditional fire emergency evacuation plans are mostly based on two-dimensional building floor plans. In the progress of urbanization, there are increasingly more complex high-rise buildings, and two-dimensional building plans for fire emergency evacuation are inadequate in meeting current needs [7, 8]. The developing computer technology, network technology, and the Internet of Things makes computers and mobile devices increasingly powerful, and the increase in Internet bandwidth. As a result, better three-dimensional visualization of emergency evacuation plans will gradually replace the traditional two-dimensional ones [9, 10]. Pawel Boguslawski et al. [11] provided a comprehensive system framework for the special needs and problems of indoor positioning system in emergencies, covering 3D building models and various aspects of indoor positioning system in emergencies, but the article did not consider the dynamic indoor environment in emergencies. Qiang Yang’s approach [12] divided the fire scene into temporal and spatial zones based on different meteorological elements, building structures, and other spatial-temporal characteristics that may affect the fire. The resulting zones were used for path planning, but the approach did not consider the dynamic environment changes that can affect the planning results during a fire. Chou et al. [13] proposed a real-time optimal path planning method based on wireless sensors and visual guidance for building fire rescue. They utilized the A* algorithm to achieve fast and effective path searching but did not consider the factors of dynamic environment changes in the path planning. In view of the impact of dynamic indoor environment on path planning results in fire emergency evacuation, Ali M et al. [14] combined Internet of Things (IoT) sensors, wireless communication technology, and used a hybrid genetic algorithm and simulated annealing algorithm to guide people to evacuate along the evacuation route in fire events. Jinlong Wang et al. [15] proposed an analysis method for real-time dynamic evacuation path planning based on Building Information Modeling (BIM), using Fire Dynamics Simulator (FDS) to simulate the spread of fire and dynamically adjust the simulation based on real-time fire conditions. This method can achieve dynamic indoor fire evacuation path planning, but due to the large computational cost required for FDS simulation, the real-time performance of the algorithm cannot be guaranteed. Kunxiang Deng et al. [16] proposed a dynamic path optimization method based on an improved A* algorithm with real-time information. They first set up a network topology for the environment in advance and used FDS to simulate the fire situation when an accident occurred and then conducted path planning accordingly.

Currently, most of the research on emergency evacuation path planning in fire scenarios is based on real-time monitoring of the indoor environment in buildings using IoT sensors. When a fire occurs, the FDS is used to simulate the indoor flame environment, and then a path planning algorithm is used to dynamically plan the evacuation path. However, the path planning method can encounter problems such as excessively long calculation times in large-scale scenarios, which can lead to serious consequences in emergency situations. In terms of path planning algorithms, many scholars have improved traditional algorithms to solve the above problems. Enol García et al. [17] studied the multi-robot path planning problem and proposed a solution that combines the optimization capabilities of the A * algorithm with the search capabilities of co-evolutionary algorithms. This scheme can generate a set of collision free paths in real-time. Ali Ebrahimnejad [18] proposed a generalized Dijkstra algorithm for the shortest path problem on networks with interval weights. The article uses an acceptability index to compare any two imprecise values and solves the interval shortest path problem by selecting an acceptability index. Ali Ebrahimnejad et al. [19] proposed an improved artificial bee colony (ABC) algorithm for solving the shortest path problem with mixed interval valued fuzzy number weights. Debora Di Caprio et al. [20] proposed a fuzzy based ant colony optimization (ACO) algorithm to solve the shortest path problem with fuzzy arc weights and compared the proposed algorithm with genetic algorithm (GA), Particle swarm optimization (PSO) algorithm and ABC algorithm to prove the superiority of the proposed algorithm. Jianping Yuan et al. [21] applied the NavMesh algorithm to indoor fire escape by constructing a navigation grid for the building, which can generate the shortest escape path in the event of a fire. However, their approach was only tested on a static environment, and the planned path did not consider the impact of fire spread.

The NavMesh algorithm is a pathfinding technique widely used in games, with good 3D pathfinding results [22]. First, the walkable part of the map is divided into continuous convex polygon or triangular mesh to generate a navigation grid, and then the path is found on the navigation grid. This method can greatly reduce the computational cost of path planning and can also quickly plan the shortest path in large-scale scenarios. Wouter G [23] conducted a comparative study of the navigation mesh in the NavMesh algorithm. The paper introduced some quality indicators to systematically evaluate and compare the performance of the navigation mesh, providing a standardized method for the research and application of navigation mesh. R. Oliva et al. [24] proposed a method for automatically generating navigation meshes based on 3D models and used GPU-accelerated voxelization and rendering techniques to improve the generation speed and efficiency. However, they did not consider the issue of dynamical updating of navigation meshes in a changing environment, and only tested their methods in a static environment. Rhys Goldstein et al. [25] proposed a shortest path planning method based on navigation mesh, but this method did not consider the weight or cost differences that may exist between different vertices on the mesh, such as obstacles, heights, curvatures, etc. These factors may affect the selection of the shortest path and center path, as well as the navigation effect. The lightweight nature of the NavMesh algorithm makes it very suitable for application in path planning for fire emergency evacuation. The heavy computation in navigation mesh generation can be fulfilled on a powerful server, leaving the client with the path planning running that requires much less computation. This allows the algorithm to plan an immediate safe evacuation path for evacuees in the event of a fire.

In response to the above problems, this paper proposes an improved NavMesh algorithm for fire emergency evacuation, which has been improved in two aspects. 1) By improving the navigation grid generation algorithm in the NavMesh algorithm, a more robust and faster dynamic update of the navigation grid is achieved through local generation. 2) Improve the heuristic function of the routing algorithm to avoid areas that may be affected by fires in advance and propose a multi exit routing mechanism to achieve safe and reliable path planning. The method proposed in the paper can guide the evacuation of trapped personnel in the event of a building fire, providing a new idea and method for future planning of escape routes in building fires.

The organization of the rest of this paper is as follows: Section 2 details the improvements made to the algorithm of this paper. Section 3 describes the experimental steps and demonstrates the proposed evaluation index Navigation Grid Complexity (NGC). Section 4 describes the experimental results and discussions. Section 5 provides a summary of the content of the paper.

2 Improved NavMesh algorithm

To address the issues encountered in the practical application of emergency evacuation path planning in a fire scenario, this paper proposes improvements to both the navigation mesh generation and the pathfinding parts of the NavMesh algorithm. The improved NavMesh algorithm retains its lightweight characteristics and is based on the basic navigation mesh data to develop a real-time dynamic updating method of multi-layer navigation mesh. Furthermore, the pathfinding algorithm’s heuristic function is improved to accommodate the characteristics of indoor fire emergency evacuation scenarios, and a multiple-exit path planning mechanism is investigated to meet the needs of emergency evacuation path planning in a fire scenario.

The overall algorithm flow is shown in Fig. 1 and consists of two parts. The first part is Dynamic Navigation Grid Update, which updates the navigation grid based on the input of the basic navigation grid and the fire-affected area to achieve dynamic navigation grid generation. The fire-affected area is determined by the fire monitoring system inside the building, FDS, and other methods to determine the impact range of smoke and flames [26 –28]. The second part is Optimal Path Planning, which improves the heuristic function of multi-exit pathfinding in the basic navigation grid to calculate the optimal safe path. In the following section, this paper will provide detailed explanations for the improvements in these two parts.

Fig. 1

Schematic diagram of the improved NavMesh algorithm.

2.1 Dynamic navigation grid update method

The basic navigation mesh is firstly divided into different layers, each floor consisting of a plana layer and a spatial layer. The purpose is to prevent mutual interference between different floors in the subsequent navigation mesh updates. The plana layer represents the ground level of the floor. The spatial layer represents the space from the ground to the top of the floor, which is generally the passable plane of fire exits such as stairs inside the building. Separate the coordinate points of different layers into multiple array sets and each point in the array collection is added with a flag data L, where L represents the floor number that each array collection belongs to. ${\begin{matrix} H_{0} = α (L - 1) \\ H_{1} = F (x, y) + α (L - 1) \end{matrix}$ (1)

Equation (1) represents the function to calculate the vertical axis coordinate values of points on different levels, which is obtained upon inputs of the plane coordinate values. Where H₀ and H₁ represent the vertical axis coordinate values of the planar layer and spatial layer, α represents the height of one spatial layer in the navigation grid, F (x, y) is the spatial function of different staircases in the current spatial layer.

After completing the layering of the basic navigation grid, the algorithm will update the navigation grid based on the inserted fire-affected area, so that the planned evacuation path can avoid the fire-affected areas. The basic idea of the improved navigation grid update algorithm is to use local update method, which performs intersection tests in two-dimensional space to find the grids affected by the fire, then remove these grids, and regenerate the grid in the local blank area formed along the boundary of the fire. Finally, the remaining grids and new grids are merged to generate a new navigation grid.

Due to the large number of intersection tests required in finding the fire-affected grid cells, the accumulated computation time greatly affects the speed of the dynamic navigation grid generation algorithm. This paper adopts a two-step intersection test. First, a Rapid Rejection Experiment is performed to determine whether the endpoints of two-line segments are within the range of the other line segment. If not, it indicates that the two-line segments do not intersect. This step requires a small amount of computation and can quickly exclude most of the non-intersecting line segments. In the second step, a Straddle Experiment is conducted to accurately determine whether the two-line segments intersect.

As shown in Fig. 2, a simple example will be used to illustrate the method of dynamically updating the navigation grid. Figure 2(a) shows a simple basic navigation grid, which divides the passable area into multiple triangles. Figure 2(b) describes the insertion of an impassable area into Fig. 2(a). In this step, the edges intersecting with the impassable area will be detected and deleted. The result is shown in Fig. 2(c). The next step is to find the grids containing the edges removed in the previous step, merge these grids with the impassable boundary, and generate a blank area as shown in Fig. 2(d). The final step is to generate a navigation grid in the blank area as shown in Fig. 2(e), by merging the grids to create a new navigation grid as shown in Fig. 2(f). In practical use, the algorithm updates the navigation grid of each floor in real-time and calculates the vertical coordinate of each point in the grid using Equation (1) to achieve the 3D representation of the grid, as shown inFig. 2(g).

Fig. 2

Dynamic navigation grid generation steps.

By updating the navigation grid in real-time using this method, the computational cost is limited to the generated blank area, rather than the entire navigation grid. This reduces the computational load of updating the navigation grid. Once the coordinates of the impassable area are available, a new navigation grid will appear, achieving the effect of navigation grid dynamical updating.

2.2 Optimal path planning

2.2.1 Heuristic function improvement

The pathfinding method of the NavMesh algorithm uses the A* algorithm to navigate on the basic navigation grid. With the generated grid as navigation nodes, the A* algorithm will identify the shortest path of the grids between the starting and ending points. Then, the Funnel algorithm will be employed to compute a smooth shortest path from the list of grids. The A* algorithm is improved in this paper to adapt to the features of emergency evacuation path planning in indoor fire scenarios.

The improved A* algorithm can perform multi-exit path optimization in the generated navigation grid, select the most suitable exit, and plan a safe path. Considering the rapid development of indoor fires, this article improves the heuristic function of the A* algorithm, so that the planned path can stay away from areas affected by the fire, enabling evacuees to be minimally affected by the fire in evacuation.

The basic formula of the A* algorithm is f (n) = g (n) + h (n), where f (n) is the overall cost of node n, g (n) is the distance cost from the start point to node n, and h (n) is the estimated cost from node n to the end point. This is also the heuristic function of the A* algorithm, which tends to select nodes with lower overall cost as pathfinding nodes. In the NavMesh algorithm, the distance cost and estimated cost are usually calculated using Euclidean distance, and the calculation formula is as follows:

${\begin{matrix} g (n) = \sum_{i = 1}^{n} \sqrt{{(x_{i} - x_{i - 1})}^{2} + {(y_{i} - y_{i - 1})}^{2}} \\ h (n) = {(x_{n} - x_{g})}^{2} + {(y_{n} - y_{g})}^{2} \end{matrix}$ (2)

In Equation (2), x_n and y_n represent the coordinates of the nth node; x_g and y_g represent the coordinates of the exit node; g (n) represents the total distance from the starting point to node n, which is the distance cost of node n; h (n) represents the square of the distance between node n and the endpoint, which avoids square root operations and reduces computational complexity.

As the estimated cost in the A* algorithm, h (n) determines the intelligence level of the algorithm. If h (n) is too small, the A* algorithm will gradually degrade into Dijkstra algorithm, resulting in blind search and reduced efficiency. If h (n) is too large, it will not be able to ensure that the found path is the optimal path. In the fire environment, flames tend to spread outward. Paths that are closer to the flames may be affected by the spread of flames. The original A* algorithm did not consider the impact of flames on evacuation paths, and the planned path may lead evacuees into danger. Therefore, this paper incorporates the influence of the flame area into the heuristic function of the A* algorithm. ${\begin{matrix} x_{max} = max {x_{fire}} \\ x_{min} = min {x_{fire}} \\ y_{max} = max {y_{fire}} \\ y_{min} = min {y_{fire}} \end{matrix}$ (3)

Equation (3) represents the maximum and minimum values of the horizontal and vertical coordinates in the fire-affected area. Here, x_fire and y_fire respectively represent the range of the fire-affected area along the horizontal and vertical axes. ${\begin{matrix} x_{f} = \frac{x_{max} + x_{min}}{2} \\ y_{f} = \frac{y_{max} + y_{min}}{2} \\ z_{f} = α (L_{f} - 1) \end{matrix}$ (4)

In Equation (4), x_f, y_f, and z_f represent the coordinates of point F in the fire-affected area, where L_f is the floor on which the flame-affected area is located. $r_{f} = max {\frac{x_{max} - x_{min}}{2}, \frac{y_{max} - y_{min}}{2}}$ (5)

In Equation (5), r_f represents the estimated radius of the fire impact zone. $μ (n, F) = {(x_{n} - x_{f})}^{2} + {(y_{n} - y_{f})}^{2} + {(z_{n} - z_{f})}^{2}$ (6) $h (n) = {\begin{matrix} \infty, μ {(n, F)}^{2} ⪡ 1.2 r_{f} \\ {(x_{n} - x_{g})}^{2} + {(y_{n} - y_{g})}^{2} + {(z_{n} - z_{g})}^{2}, \\ 1.2 r_{f} < μ {(n, F)}^{2} ⪡ 10 r_{f} \\ {(x_{n} - x_{g})}^{2} + {(y_{n} - y_{g})}^{2} + {(z_{n} - z_{g})}^{2} \\ + k e^{\frac{1}{μ (n, F)} + 1}, 10 r_{f} < μ {(n, F)}^{2} \end{matrix}$ (7)

Equation (6) defines μ (n, F) as the squared distance between node n and the center point F of the fire.

Equation (7) represents the improved estimated cost, where k is the weight factor of the fire impact, representing the strength of the impact of the fire on the heuristic function. The larger the value of k, the stronger the impact of the fire on the planned path. When the distance between the current node and the fire is too close, its estimated cost is infinitely large to prevent the planned path from being too close to the fire-impact area.

2.2.2 Multi-exit routing mechanism

In large buildings, there are usually multiple exits, and when a fire occurs, the most suitable exit needs to be selected for path planning. The traditional A* algorithm can only calculate the shortest path between a single starting point and endpoint and cannot support multi-exit path planning. To solve this problem, this paper proposes a multi-exit pathfinding mechanism for the A* algorithm to support multi-exit path planning.

To support multi-exit path planning, the coordinates of all exits of the building, including doors, windows, and various special exits, need to be saved to guide the execution of the algorithm. The exits are classified into regular exits and special exits, where regular exits include the entrance and exit of the building, while special exits refer to the windows inside the building.

The algorithm flow is shown in Fig. 3. It tries first to find a path to each regular exit. If an evacuation path is found, the algorithm ends. If the fire is too large for evacuees to evacuate through the regular exits, the algorithm will plan a path to the nearest special exit, guiding evacuees to the windows of the building to cooperate with external rescue.

Fig. 3

Flow chart of multi-exit path planning algorithm.

3 Experimentation setup and indicator demonstration

The goal of this experiment is to verify the generation speed and generated grid quality of the Improved Dynamic Navigation Grid Update Method, and to verify the feasibility, reliability, and operating efficiency of the multi-exit path planning algorithm in the navigation grid. In the experiment, the concept of Navigation grid complexity (NGC) is introduced, which represents the number of grids in the navigation grid, and it is used as an evaluation index of the experiment to measure the complexity of different navigation grids. The platform processor used in the experiment is Intel(R) Core (TM) i7-11700@2.50 GHz 2.50 GHz.

3.1 Experimental setup

Firstly, experiment to verify the generation speed of Improved Dynamic Navigation Grid Update Method and the quality of the generated navigation grid. In terms of navigation grid generation speed, we compared our solution with Recast Navigation, an open-source project on GitHub and the most widely used navigation grid generation algorithm in the field of game development and compared the computation time of navigation grid for different NGCs. In terms of the quality of the navigation grid, we think that the local generation idea used by the Dynamic Navigation Grid Update Method only considers the local optimal solution of the navigation grid while ignoring the global optimal solution when generating the local navigation grid, which may lead to new The NGC of the generated navigation grid is greatly increased which affects the performance of the navigation grid, in order to verify whether this situation exists, we simulated the spread of the fire area from small to large in 28 sets of NGC different navigation grids in the process, use the Improved Dynamic Navigation Grid Update Method to iterate the navigation grid 20 times, and record the changes of its NGC.

Secondly, the experiment verifies the feasibility, reliability, and operating efficiency of the multi-exit path planning algorithm in the navigation grid. A teaching building of Zhengzhou University of Light Industry in China was used for 3D modeling and a basic navigation grid was generated. The building is five stories high. The NGC used to generate the basic navigation grid is 4121. The model is shown in Fig. 4(c). In terms of the feasibility and reliability of the multi exit path planning algorithm, we conducted path planning experiments on the 3D building model, simulating the paths planned by the algorithm under different fire states at different starting points of the building, and observing whether it can successfully plan a safe path. In terms of the running speed of the multi exit path planning algorithm, we established a navigation grid on the same model, counted the calculation time of multiple path planning algorithms planning the same path, and compared them.

Fig. 4

Three different experimental scenarios.

3.2 NGC evaluation indicator demonstration

NGC is the number of grids present within the navigation grid and is used to measure the complexity of the navigation grid. It is proposed in literature [23] that the quality indicators to measure the quality of navigation grid include Coverage, Connectivity, Complexity and Performance of navigation grid. Coverage and Connectivity are determined by navigation grid passable area detection and navigation grid generation algorithm. The former indicates whether the navigation grid can correctly reflect the range of the passable area, and the latter indicates the continuity of the navigation grid.

The Complexity of navigation grid refers to the number of Vertices in the grid and the number of grids, and the Performance is the Construction time and Memory usage of navigation grid. The main purpose of this study is to improve the performance of dynamic Navigation grid generation, so we use the navigation grid generation method of Recast Navigation to generate navigation grids for different NGC in three different sizes of 3D scenes in Fig. 4, to compare the relationship between Coverage, Complexity and Performance of NGC and navigation grid. Since the Connectivity of Navigation grids generated by the navigation grid generation method of Recast Navigation meets the requirements for use, the Connectivity of experimental subjects is not listed in the comparison experiment.

As shown in Table 1, we generated different NGC navigation grids by modifying navigation grid generation parameters in three experimental scenarios. In three scenarios of different sizes, NGC is positively correlated with Vertices, Construction time, and Memory usage. That is, in the same scenario, the larger the NGC is, the more complex the navigation grid is, and the more resources its construction and use occupy. However, when the NGC is too small in a scene, the Coverage of the navigation grid will not meet the standard. We believe that the Coverage is up to the standard when the coverage is greater than 0.95, and the path planning in the scene can be carried out normally.

Table 1
Navigation grid indicator experimental data in three experimental scenarios

Large scene NGC 1626 1776 1914 2215 3949 5509

Coverage 0.725 0.892 0.953 0.984 0.991 0.996

Vertices 3028 3206 3657 3867 6746 7530

Construction time(ms) 2631 3152 3885 4512 5357 8340

Memory usage (Kb) 195 212 248 289 442 631

Middle scene NGC 773 835 934 1045 1175 1310

Coverage 0.812 0.876 0.964 0.989 0.992 0.995

Vertices 1352 1421 1498 1537 1642 1958

Construction time(ms) 1051 1321 1542 1626 1743 1921

Memory usage (Kb) 92 105 111 130 139 167

Small scene NGC 253 271 294 388 490 642

Coverage 0.789 0.862 0.921 0.968 0.989 0.991

Vertices 586 611 665 795 812 857

Construction time(ms) 98 120 153 228 373 537

Memory usage (Kb) 28 31 38 43 50 64

Through the above experiments, we verify that NGC can objectively and practically measure the quality of navigation grid when Coverage of navigation grid meets the usage requirements, which is suitable for the experiment in this paper.

4 Experimental results and discussion

4.1 Experiment on generating quality of dynamic navigation grid update method

The experiment first verifies the quality of the Navigation Grid generated by the Improved Dynamic Navigation Grid Update Method. It has been demonstrated in Article 4.2 that NGC can express the complexity of the navigation grid and represent the quality of the navigation grid when the Coverage of the navigation grid meets the requirements. In this experiment, we first use NGC to represent navigation grids of different complexity, The Construction time of the Navigation Grid generated by Recast Navigation grid generation Method and Improved Dynamic Navigation Grid Update Method with the same complexity was compared.

The experimental results are shown in Fig. 5. When NGC is small, the Construction time of the two Navigation grid generation algorithms is roughly the same. With the increase of NGC, the computation required by Recast Navigation gradually increases, so the generation time is longer and longer. However, under the same complexity, the generation time of the improved dynamic navigation mesh update method is significantly reduced because the navigation mesh is only regenerated in a local area.

Fig. 5

Comparison of construction time for different navigation grid generation methods.

Table 2 shows the detailed construction time of Navigation grids of different NGCs generated by the two Navigation Grid generation methods. Compared with Recast Navigation, the Dynamic Navigation Grid Update Method has the following characteristics: The Voxelization step is omitted in the generation of navigation grid, and due to the local generation method, the time spent by grid generation is also reduced when generating the same navigation grid. In the overall generation time of navigation grid, the generation time of the improved algorithm is about 6.8% of the original algorithm.

Table 2

Navigation grid generation schedule

NGC		524	599	678	708	742	756	812	868	925
Dynamic Navigation Grid Update Method	Intersection tests (ms)	28.3	34.2	33.3	41.4	50.7	58.6	59.8	69.0	75.1
	Grid generation (ms)	16.3	17.3	19.5	24.3	23.9	29.8	36.1	37.9	38.8
	Total (ms)	44.6	51.5	52.8	65.7	74.6	88.4	95.9	106.9	113.9
Recast Navigation	Voxelization (ms)	187.7	247.9	312.8	333.6	357.8	437.7	449.9	508.2	590.8
	Boundary detection (ms)	86.9	106.4	137.1	160.5	185.6	176.9	211.3	236.3	273.0
	Grid generation (ms)	262.1	357.4	441.2	460.8	584.2	626.3	656.4	777.5	810.8
	Others (ms)	26.5	61.7	40.4	65.5	57.7	61.3	125.9	82.3	75.2
	Total (ms)	563.2	773.3	931.5	1020.4	1185.3	1302.2	1443.5	1604.3	1749.8

Secondly, we verify the quality of the Navigation Grid generated by the Improved Dynamic Navigation Grid Update Method. The process of fire area spread from small to large was simulated in 28 sets of different navigation grids of NGC. The NGC change results of the navigation grid are shown in Fig. 6. The first iteration brings about some increases of the NGCs of all 28 navigation grids, and with more iteration, the NGCs gradually decreased due to the reduction of the navigation area. Among the samples with NGC greater than 50, the increase in the complexity of the navigation grid during the first iteration did not exceed 10%, proving that the Dynamic Navigation Grid Update Method will not render negative impacts on the performance of the navigation grid.

Fig. 6

Trend of NGC changes in navigation grid.

4.2 Experimental on improved multi-exit path planning algorithm

The purpose of this experiment is to verify the feasibility, reliability, and efficiency of Improved Multi-Exit Path Planning Algorithm in navigation grid. In terms of the feasibility and reliability of the algorithm, the navigation grid is generated on the 3D building model and the fire is simulated to observe whether the path planned by the algorithm meets the expectation.

Figure 7 shows the performance of the path planning algorithm on the model, with an image of two floors of the building for better display. As shown in Fig. 7(a), under normal circumstances, the algorithm outputs the path to the nearest Exit2, after entering the starting point. When a dangerous situation occurs near the planned path, the algorithm will plan a safe evacuation path that avoids the dangerous area, as shown in Fig. 7(b)–(d) describe that when evacuees are trapped and cannot reach any ordinary exits due to the spread of fire, the algorithm will plan a path to the nearest special exit. The experimental results show that the improved multi-exit path planning algorithm can plan a safe exit path when a fire breaks out.

Fig. 7

Path planning algorithm experiment.

In terms of the efficiency of the algorithm, the experiment compared the time of improved multi-exit path planning algorithm, NavMesh path planning algorithm and A* algorithm for six groups of same starting point to end point path planning under the same environment. In the comparative experiment, A* algorithm constructed a square navigation grid in the navigation area.

As shown in Table 3, among the three Path Planning algorithms, the improved multi-exit path planning algorithm and NavMesh path planning algorithm run significantly faster than A* algorithm. Improved multi-exit path planning algorithm is about 25% slower than NavMesh path planning algorithm. However, since the NavMesh path planning algorithm itself is a very lightweight path planning algorithm, Improved multi-exit path planning algorithm added functionality for multi-exit path planning and automatic avoidance of hazardous areas, Improved multi-exit path planning algorithm is a path planning algorithm that can be well applied in fire emergency evacuation.

Table 3

Comparison of running time of path planning algorithms

	Group 1	Group 2	Group 3	Group 4	Group 5	Group 6
Improved multi-exit path planning algorithm (ms)	98	109	142	113	96	215
NavMesh path planning algorithm (ms)	76	88	105	89	62	182
A* algorithm (ms)	681	793	1056	897	656	1530

5 Conclusion

In this paper, a method of building fire escape path planning based on improved NavMesh algorithm is proposed, the feasibility and effectiveness of the method are verified in the simulation experiment on the actual building model. Firstly, the improved dynamic navigation grid update method in this paper reduces the time consumed in the generation of navigation grid and meets the requirement of real-time generation of navigation grid. The evaluation index NGC to measure the quality of navigation grid is proposed and demonstrated. The fire area diffusion simulation experiments are carried out in Navigation grids under different NGCs, and the generation time of navigation grids is significantly decreased while NGC is not significantly increased. This indicates that the dynamic navigation grid update method can improve the generation efficiency while ensuring the quality of navigation grids. Secondly, the feasibility and reliability of the improved multi-exit path planning algorithm are verified by path planning on the actual building model. By comparing with A* algorithm and NavMesh path planning algorithm, the efficiency of improved multi-exit path planning algorithm is verified. The experimental results show that this method can quickly, efficiently, and safely plan evacuation paths, adjust paths in a timely manner as the fire spreads, and ensure the safety of those who need evacuation.

The improved algorithm in this article can effectively promote the development of indoor fire emergency evacuation technology. However, the result of path planning in this study depends on the result of fire situation awareness, so in the next study, we consider achieving high-precision indoor fire situation awareness, building a complete indoor fire emergency evacuation system combined with the IOT. Further accelerate the development of indoor fire emergency evacuation technology.

Footnotes

Acknowledgments

This project is supported by the Key R&D and Promotion Project of Henan (No. 212102210020).

References

Zhai

and Feng

, A novel evacuation path planning method basedon improved genetic algorithm, Journal of Intelligent & FuzzySystems 42(3) (2022), 1813–1823.

Garcia-Ojeda

J.C.

, Bertok

, Friedler

and Fan

L.T.

, Building-evacuation-route planning via time-expanded process-network synthesis, Fire Safety Journal 61 (2013), 338–347.

and Yang

, Design of distributed WSNs fire remote monitoringsystem based on fuzzy algorithm, Journal of Intelligent &Fuzzy Systems 41(3) (2021), 4319–4326.

Kinateder

, Comunale

and Warren

W.H.

, Exit choice in an emergency evacuation scenario is influenced by exit familiarity and neighbor behavior, Safety Science 106 (2018), 170–175.

Lin

, Li

, Rao

and Lovreglio

, Individual wayfinding decisions under stress in indoor emergency situations: A theoretical framework and meta-analysis, Safety Science 160 (2023), 106063.

Rozo

K.R.

, Arellana

, Santander-Mercado

and Jubiz-Diaz

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

Xiong

, Zhu

, Du

, Zhu

, Zhang

, Niu

, Li

and Zhou

, A dynamic indoor field model for emergency evacuation simulation, ISPRS International Journal of Geo-Information 6(4) (2017), 104.

Niu

, Wang

, Song

and Li

, An Evaluation Model for Analyzing Robustness and Spatial Closeness of 3D Indoor Evacuation Networks, ISPRS International Journal of Geo-Information 10(5) (2021), 331.

Hong

, Li

, Wu

and Xu

, Priority-Oriented Route Network Planning for Evacuation in Constrained Space Scenarios, Journal of Optimization Theory and Applications 181(1) (2019), 279–297.

10.

Xie

, Zlatanova

and Lee

, 3D indoor environments in pedestrian evacuation simulations, Automation in Construction 144 (2022), 104593.

11.

Boguslawski

, Zlatanova

, Gotlib

, Wyszomirski

, Gnat

and Grzempowski

, 3D building interior modelling for navigation in emergency response applications, International Journal of Applied Earth Observation and Geoinformation 114 (2022), 103066.

12.

Yang

, Zhang

, He

, Yan

and Na

, Fire Scenario Zone Construction and Personnel Evacuation Planning Based on a Building Information Model and Geographical Information System, ISPRS International Journal of Geo-Information 11(2) (2022), 110.

13.

Chou

, Cheng

, Hsieh

, Yang

and Hsu

, Optimal path planning in real time for dynamic building fire rescue operations using wireless sensors and visual guidance, Automation in Construction 99 (2019), 1–17.

14.

Mohammadiounotikandi

, Fakhruldeen

H.F.

, Meqdad

M.N.

, Ibrahim

B.F.

, Jafari

, Jafari Navimipour

and Unal

, A Fire Evacuation and Control System in Smart Buildings Based on the Internet of Things and a Hybrid Intelligent Algorithm, Fire 6(4) (2023), 171.

15.

Wang

, Wei

and Dong

, A dynamic fire escape path planning method with BIM, Journal of Ambient Intelligence and Humanized Computing 12(11) (1025), 10253–10265.

16.

Deng

, Zhang

, Xiao

and Chen

, Optimal emergency evacuation route planning model based on fire prediction data, Mathematics 10(17) (2022), 3146.

17.

Garcia

, Villar

J.R.

, Tan

, Sedano

and Chira

, An efficient multi-robot path planning solution using A* and coevolutionary algorithms, Integrated Computer-Aided Engineering 30(1) (2023), 41–52.

18.

Ebrahimnejad

, An acceptability index based approach for solving shortest path problem on a network with interval weights, Rairo-Operations Research 55 (1767), S1767–S1787.

19.

Ebrahimnejad

, Enayattabr

, Motameni

and Garg

, Modifiedartificial bee colony algorithm for solving mixed interval-valuedfuzzy shortest path problem, COMPLEX & INTELLIGENT SYSTEMS 7(3) (2021), 1527–1545.

20.

Di Caprio

, Ebrahimnejad

, Alrezaamiri

and Santos-Arteaga

F.J

, Modified artificial bee colony algorithm for solving mixed interval-valued fuzzy shortest path problem, COMPLEX & INTELLIGENT SYSTEMS 7(3) (2021), 1527–1545.

21.

Yuan

, Chen

and Yu

, Application of navigation grid corner point algorithm in virtual reality simulation images of indoor fire evacuation, Internet of Things 22 (2023), 100716.

22.

van Toll

W.G.

, Cook

A.F.

and Geraerts

, A navigation mesh for dynamic environments, Computer Animation and Virtual Worlds 23(6) (2012), 535–546.

23.

Van Toll

, Triesscheijn

, Kallmann

, Oliva

, Pelechano

, Pettré

, Geraerts

, Proceedings of the 9th International Conference on Motion in Games 2016, pp. 91–100.

24.

Oliva

and Pelechano

, NEOGEN: Near optimal generator of navigation meshes for 3D multi-layered environments, Computers & Graphics-Uk 37(5) (2013), 403–412.

25.

Goldstein

, Walmsley

, Bibliowicz

, Tessier

, Breslav

and Khan

, Path Counting for Grid-Based Navigation, Journal of Artificial Intelligence Research 74 (2022), 917–955.

26.

Hassan

M.K.

, Hossain

M.D.

, Gilvonio

, Rahnamayiezekavat

, Douglas

, Pathirana

and Saha

, Numerical investigations on the influencing factors of rapid fire spread of flammable cladding in a high-rise building, Fire 5(5) (2022), 149.

27.

Xiong

, Weng

, Liu

and Lu

, Numerical Study on Evacuation Evaluation and Strategy of Theater with Rotating Auditorium, Buildings 12(8) (2022), 1202.

28.

Roy

S.S.

, Goti

, Sood

, Roy

, Gavrila

, Floroian

, Paraschiv

and Mohammadi-Ivatloo

, L2 regularized deep convolutional neural networks for fire detection, Journal of Intelligent & Fuzzy Systems 43(2) (2022), 1799–1810.

Large scene	NGC	1626	1776	1914	2215	3949	5509
	Coverage	0.725	0.892	0.953	0.984	0.991	0.996
	Vertices	3028	3206	3657	3867	6746	7530
	Construction time(ms)	2631	3152	3885	4512	5357	8340
	Memory usage (Kb)	195	212	248	289	442	631
Middle scene	NGC	773	835	934	1045	1175	1310
	Coverage	0.812	0.876	0.964	0.989	0.992	0.995
	Vertices	1352	1421	1498	1537	1642	1958
	Construction time(ms)	1051	1321	1542	1626	1743	1921
	Memory usage (Kb)	92	105	111	130	139	167
Small scene	NGC	253	271	294	388	490	642
	Coverage	0.789	0.862	0.921	0.968	0.989	0.991
	Vertices	586	611	665	795	812	857
	Construction time(ms)	98	120	153	228	373	537
	Memory usage (Kb)	28	31	38	43	50	64