=Paper= {{Paper |id=Vol-3304/paper39 |storemode=property |title=Fire Patrol Path Planning Based on Improved Ant Colony Algorithm |pdfUrl=https://ceur-ws.org/Vol-3304/paper39.pdf |volume=Vol-3304 |authors=Xingchao Zhang,Tao Tao,Huiyi Zhang }} ==Fire Patrol Path Planning Based on Improved Ant Colony Algorithm== https://ceur-ws.org/Vol-3304/paper39.pdf

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