Fire Patrol Path Planning Based on Improved Ant Colony Algorithm Xingchao Zhang*, Tao Tao, Huiyi Zhang School of Computer Science & Technology, Anhui University of Technology, Maโ€™anshan 243032, China. ABSTRACT With the rapid development of social economy and science and technology, fire hazards in all walks of life emerge in an endless stream, and the difficulty of fire prevention and control is gradually increasing. Aiming at the problem of fire patrol path planning, based on the classic ant colony algorithm, an adaptive improved ant colony algorithm is proposed to solve the problems of slow convergence and low efficiency of the classical ant colony algorithm. Matlab simulation experiments show that the ant colony algorithm can improve the efficiency of the algorithm while ensuring the found of the optimal path after adaptively changing the pheromone volatile factor and differentially processing the pheromone constant. Keywords ant colony algorithm, route plan, pheromone 1. Introduction1 In recent years, my country's attention to the field of fire protection has been continuously increased, which started from the " Guiding Opinions on Comprehensively Promoting the Construction of Smart Fire Protection " issued by the Fire Bureau of the Ministry of Public Security[1, 2]. Under the call of national policies, provinces and cities across the country have actively responded and carried out "smart fire protection" related construction. Relying on the development and application of new-generation information technologies such as the Internet of Things, big data, and mobile Internet, as well as the construction of smart cities, it provides strong technical support for the development of smart firefighting camps[3, 4, 5]. Due to the constraints of working hours and geographical environment, the progress of fire inspection work is slow. For strengthening the management of firefighting camps and determining an optimal inspection path to improve the efficiency of inspections, it is imperative to establish an efficient and intelligent firefighting smart camp platform. Based on meeting the actual needs of the fire inspection process, the fire intelligent camp platform plans the best fire inspection route through the improved ant colony algorithm. 2. Fire Patrol Route Planning 2.1. Problem Modeling The problem of fire inspection path planning can be described as: a fire truck starts from the fire station to check whether the fire hydrants and fire extinguishers in each building are in normal operation. After completing the inspection task, it returns to the fire station. The distance between the fire station and each inspection target is known. And formulating a reasonable inspection route can enable the inspectors to complete the task smoothly and quickly. The fire inspection path planning problem is described as: an undirected graph G (V, E), where V is the set of all inspection targets, and E is the set of edges between the targets. ICBASE2022@3rd International Conference on Big Data & Artificial Intelligence & Software Engineering, October 21- 23, 2022, Guangzhou, China * Corresponding author: e-mail: xc_zhang173@163.com (Xingchao Zhang) ยฉ 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings (CEUR-WS.org) 314 2.2. Traditional Ant Colony Algorithm Ant colony algorithm is a probabilistic algorithm used to find optimal paths. Marco Dorigo proposed the algorithm in his doctoral dissertation in 1992 and was inspired by the behavior of ants to find paths in their search for food[6]. It was originally designed to solve the traveling salesman problem and was later applied to various aspects of the optimization problem domain[7]. The basic principle of the ant algorithm is that in the process of foraging, an ant can release a substance called " pheromone " on the path of its travels. And the pheromone itself will continue to volatilize over time. In the process of searching for food, ants choose the direction of movement according to the concentration of pheromone and finally reach the food site. The core functions of the traditional ant colony algorithm are the state transition probability function and pheromone update function. The state transition probability indicates that ants always tend to move in the direction of high pheromone concentration when choosing a path. The pheromone update can be understood as the pheromone concentration on the path from i to j at a certain time is equal to the remaining pheromone concentration after volatilization at the previous time, plus the sum of the pheromone concentrations released by all ants on this path in the previous period. โ€ข State transition probability formula ๐œ (๐‘ก) โˆ— ๐œ‚ (๐‘ก) ๐‘— โˆˆ ๐‘Ž๐‘™๐‘™๐‘œ๐‘ค๐‘’๐‘‘ (1) ๐‘ƒ = โˆ‘ ๐œ (๐‘ก) โˆ— ๐œ‚ (๐‘ก) โˆˆ 0 other Among them: ๐‘ƒ is the probability of the kth ant from i to j at time t; ฮฑ is the pheromone factor; ฮฒ the heuristic function factor; ๐œ (t) is the pheromone concentration from i to j at time t; ๐œ‚ (๐‘ก) = 1 ๐‘‘ is the reciprocal of the path distance between two points i, j; ๐‘Ž๐‘™๐‘™๐‘œ๐‘ค๐‘’๐‘‘ is the set of nodes that have not been visited. โ€ข Pheromone update formula ๐œ (๐‘ก + 1) = ๐œ (๐‘ก) โˆ— (1 โˆ’ ๐œŒ) + โˆ†๐œ , 0<๐œŒ<1 (2) Among them: ฯ is the pheromone volatilization factor; ๐œ (๐‘ก) is the pheromone concentration from i to j at time t; โˆ†๐œ is the pheromone increment, that is, the sum of the pheromone left by m ants from i to j. The update method is as follows. โˆ†๐œ = โˆ†๐œ (3) ๏ƒฌQ ๏ƒฏ , (i, j ) โˆˆ ฯ‰k (4) ฮ”ฯ„ = ๏ƒญ LK k ij ๏ƒฏ 0, other ๏ƒฎ Among them: Q is the pheromone constant; Lk is the total path length traversed by the kth ant; ฯ‰k is the path traveled by the kth ant in this iteration. 2.3. Improved Ant Colony Algorithm At present, the traditional ant colony algorithm exists some problems such as slow convergence speed and easy falling into local optimum. The methods of algorithm improvement are mainly improved from the aspects of the structure of the algorithm, the optimization of the parameters of the algorithm, the way of pheromone initialization, and the rules of pheromone update. For example, Chen et al[8] increased the randomness of the search by integrating the chaotic disturbance factor in the ant colony algorithm; Yuan et al[9] combined simulated annealing algorithm and traditional ant colony algorithm for path planning; Xu et al[10] improved the traditional ant colony algorithm by changing the state transition probability and path selection strategy. 315 โ€ข Improve how pheromones are updated Pheromone renewal is a process of simulating the accumulation and volatilization of ant pheromones over time in nature. The pheromone update rule of the traditional ant colony algorithm is aimed at the ants reaching the destination, and the subsequent ants are easily misled by the ants on the worst path releasing pheromone, which affects the final path planning effect. To better distinguish the pheromone concentration on the path, the improvement idea based on the traditional ant colony algorithm in this paper is to increase the pheromone on the optimal path and weaken the pheromone on the worst path in each iteration, so that the ants can search for the best path. The concentration of pheromone released by the kth ant on each path is equal. By comparing the total path length traveled by the kth ant with the optimal path length in each generation, different pheromone enhancement coefficients are used to distinguish the pheromone constant Q, to improve the optimality of path planning. ฯ„ (t + 1) = ฯ„ (t )*(1 โˆ’ p) + ฮ”*ฯ„ (5) ij ij ij m ฮ”*ฯ„ ij = ๏ƒฅ ฮ”*ฯ„ ijk (6) k =1 ๏ƒฌ Q ๏ƒฏฮต ๏ง โˆ’ ๏ผŒIf ant k passes i, j (7) ฮ”*ฯ„ ijk (t ) = ๏ƒญ i Lk ๏ƒฏ๏ƒฎ0๏ผŒother The coefficient ฮต is: ๏ƒฌฮต ๏ผŒL โ‰ค Lbs ฮตi ๏ƒญ 1 k (8) ๏ƒฎฮต 2๏ผŒLk > Lbs Among them: ฯ is the pheromone volatilization factor; ฮต i is the pheromone enhancement coefficient; Lk is the total path length traversed by the kth ant. โ€ข Adaptive Volatility Coefficient The pheromone volatilization factor reflects the disappearance level of pheromone, and conversely reflects the retention level of pheromone. The value of the pheromone volatilization factor affects the global search ability and convergence speed of the algorithm. If it is too large, the pheromone volatilizes too fast, which will easily cause the optimal path to be excluded. If it is too small, the difference in pheromone content on each path will be small. The pheromone volatility factor of the traditional ant colony algorithm is a constant, which is not conducive to the search of the optimal value. Therefore, by adaptively changing the pheromone volatilization factor, if the current optimal path distance is less than the last one, more pheromone needs to be left for the next generation of ants, and if it is greater than the last one, more dilution is required to avoid subsequent ants repeat the same mistakes. ๏ƒฌ ฯ t+1 = ฯt , Lmin (t + 1) โ‰ค Lmin๏ผˆt๏ผ‰ ๏ƒญ ๏ผˆ9๏ผ‰ ๏ƒฎ ฯ t+1 = 0.75 ฯt , Lmin (t + 1) > Lmin๏ผˆt๏ผ‰ Among them: Lmin (t ) is the shortest path at time t; Lmin (t + 1) is the shortest path at time t+1. 2.4. Experimental Simulation and Analysis In this paper, the eil51 instance in the TSP international general TSPLIB data set is used to simulate the fire inspection path planning. Dataset source: http://elib.zib.de/pub/mp- testdata/tsp/tsplib/tsp/eil51.tsp. The parameter values of the ant colony algorithm are different, and the efficiency of the algorithm is also different. Therefore, after many tests, the appropriate parameter values are determined as shown in Table 1 below. Table 1. Algorithm parameter settings parameter name value number of ants 150 heuristic 3 316 pheromone factor 1 Pheromone constant 100 pheromone volatile factor 0.5 Pheromone Enhancement Coefficient[1๏ผŒ1.5] The maximum number of iterations 150 The comparison of the convergence process trajectories between the traditional ant colony algorithm and the improved ant colony algorithm is shown in Figure 1; The worst path comparison is shown in Figure 2; after 10 repeated experiments, the experimental results of the algorithm are shown in Table 2. Table 2. Algorithm experiment results starting optimal path worst path average path average search algorithm point length length length time traditional 453.2391 462.8769 457.3707 16.5079 Coordinate algorithm 1 improve algorithm 449.2579 460.0284 456.2055 16.4345 Figure 1. Convergence trajectories of the two algorithms (a) (b) Figure 2: Comparison of the shortest path between the two algorithms 317 Figure 2 shows that the relationship between the optimal path length and iterations of traditional ant colony algorithm and improved ant colony algorithm, respectively. It can be seen that the lowest point of the iterative curve of the improved ant colony algorithm is below the lowest point of the iterative curve of the traditional ant colony algorithm, which indicates that the optimal path length found by the improved ant colony algorithm is better than the optimal path found by the traditional ant colony algorithm. After 10 repeated experiments, it can be seen from Table 2 that the improved ant colony algorithm is slightly better than the traditional algorithm in terms of average path length and average optimization time, and the optimal path searched is also the shortest. Therefore, the improved ant colony algorithm is more stable than the traditional algorithm, which can help fire inspection vehicles quickly find the optimal route and improve work efficiency. 3. Conclusion In this paper, the pheromone constant Q is differentiated based on the traditional ant colony algorithm, which is very helpful for distinguishing the pheromone concentration on the path. And by adjusting the pheromone volatile factor adaptively, the blindness caused by the influence of pheromone is avoided. Applying the improved ant colony algorithm to the fire inspection path planning can find the optimal inspection path quickly and improve the inspection work efficiency. Although the improved ant colony algorithm optimizes the pheromone updating method, it does not consider the influence of state transition probability. The follow-up work is to improve the state transition probability according to weather conditions and road congestion so that the inspection path planning method is more efficient and intelligent. 4. References [1] Li M, Jiang Z. Research on the construction and development of " smart fire protection " [A]. China Fire Protection Association. 2019 China Fire Protection Association Science and Technology Annual Conference Proceedings [C]. China Fire Protection Association: China Fire Protection Association, 2019, 480-483. [2] Shi C. Smart fire protection construction in the new era: connotation, realistic challenges and development path [J]. Fire Protection (Electronic Edition), 2022, 8(03): 25-27. [3] Li S, Xu X, Gao Tao. Construction and practice of military digital camps [M]. Beijing: Tsinghua University Press, 2018. [4] Zheng W, Cai Q. Implementation of intelligent fire evacuation route based on Internet of things[C]. 2015 IEEE Advanced Information Technology, Electronic and Automation Control Conference (IAEAC). IEEE, 2015, 934-938. [5] Li T, Hou P. Application of NB-IoT in intelligent fire protection system[C]. 2019 International Conference on Virtual Reality and Intelligent Systems (ICVRIS). IEEE, 2019, 203-206. [6] Zhao Y, Zhang S. Intelligent traffic path planning based on improved ant colony algorithm [J]. Industrial Instrumentation and Automation Device, 2019(02): 30-32. [7] Zhao L. Indoor evacuation path optimization based on improved ant colony algorithm [J]. Fire Science and Technology, 2021, 40(07): 999-1003. [8] Chen J, Yan G, Zhang J. Design of police equipment management platform based on improved ant colony algorithm [J]. Industrial Control Computer, 2022, 35(04): 144-146. [9] Yuan J, Li S, Wu Y, Jian G. Robot path planning method based on simulated annealing ant colony algorithm [J]. Computer Simulation, 2019, 36(10): 329-333. [10] Xu Y, Li K, Zhou J. Path planning of drilling rescue vehicles based on improved ant colony algorithm [J]. Computer System Application, 2022, 31(04): 268-272. 318