Balanced Multi-UAV path planning for persistent monitoring

Abstract

In scenarios such as environmental data collection and traffic monitoring, timely responses to real-time situations are facilitated by persistently accessing nodes with revisiting constraints using unmanned aerial vehicles (UAVs). However, imbalanced task allocation may pose risks to the safety of UAVs and potentially lead to failures in monitoring tasks. For instance, continuous visits to nodes without replenishment may damage UAV batteries, while delays in recharging could result in missing task deadlines, ultimately causing task failures. Therefore, this study investigates the problem of achieving balanced multi-UAV path planning for persistent monitoring tasks, which has not been previously researched according to the authors’ knowledge. The main contribution of this study is the proposal of two novel indicators to assist in balancing task allocation regarding multi-UAV path planning for persistent monitoring. One of the indicators is namely the waiting factor, which reflects the urgency of a task node waiting to be accessed, and the other is the difficulty level which is introduced to measure the difficulty of tasks undertaken by a UAV. By minimizing differences in difficulty level among UAVs, we can ensure equilibrium in task allocation. For a single UAV, the ant colony initialized genetic algorithm (ACIGA) has been proposed to plan its path and obtain its difficulty level. For multiple UAVs, the K-means clustering algorithm has been improved based on difficulty levels to achieve balanced task allocation. Simulation experiments demonstrated that the difficulty level could effectively reflect the difficulty of tasks and that the proposed algorithms could enable UAVs to achieve balanced task allocation.

1. Introduction

Persistent monitoring requires uninterrupted and continuous surveillance of the target environment to obtain real-time information. Common task scenarios include environmental data collection [1], power line inspections [2], wildfire tracking [3], and rescue operations [4]. Unmanned aerial vehicles (UAVs) are renowned for their high flexibility and ease of deployment, making them valuable assets across industries and various sectors of human life. For example, UAVs can serve as auxiliary devices for data collection, significantly reducing data collection delays [5]. Furthermore, equipped with cameras and diverse sensors, UAVs are ideal for monitoring tasks [6].

Multi-robot systems demonstrate exceptional robustness and scalability, making them highly effective for various applications in dynamic environments. Employing multiple UAVs in large-scale persistent monitoring helps to address the limitations of a single UAV, such as insufficient energy, limited resources, and singular performance, while enabling better task coordination [7]. However, imbalanced task allocation to UAVs often poses significant challenges to the execution of these tasks. For example, overloading poses a threat to the safety of UAVs and, in extreme cases, may result in tasks being unable to be completed at all. Meanwhile, timely replenishment of UAVs is also important in persistent monitoring. Broadly speaking, the recharging methods for UAVs can be classified into dynamic replenishment and static replenishment. The former method involves utilizing unmanned ground vehicles (UGVs) to transport batteries to UAVs to be replaced at rendezvous nodes [8]. However, the mobility of UGVs is limited by the road network, and failing to reach the rendezvous node may lead to task failure. The latter method relies on UAVs returning to a designated base station for energy replenishment at scheduled intervals which is deemed more reliable [9]. This paper focuses on the fairness of task allocation among multiple UAVs, specifically in the situation where UAVs need to return to a fixed base station for replenishment while visiting monitoring nodes with revisit constraints.

On the basics of coverage path planning, which typically involves determining routes to cover an entire area [10], path planning in some persistent monitoring scenarios also focuses on the optimization of monitoring frequency. Hari et al. [11] investigated the problem of UAVs with limited energy for persistent monitoring. It was defined that within one energy cycle, a UAV could only visit $K$ nodes before returning to a depot for energy replenishment. They provided tight lower bounds that help in evaluating the quality of any feasible routes developed. Scott et al. [12] concentrated on path planning in persistent intelligence surveillance reconnaissance missions, treating it as a multi-depot multiple traveling salesman problem (MDTSP), which ensures that the revisit time of each node is the time required to complete the TSP task once. By the Lagrangian algorithm proposed, the coupling constraints in the primal problem were relaxed. Both studies utilized static charging stations for UAV replenishment, enabling persistent monitoring. With UGV serving as mobile charging for UAVs, Lin et al. [13] used multiple UAVs to periodically monitor large areas. However, the proposed method was not suitable for monitoring conditions with strict revisit requirements. Shu et al. [14] incorporated path entropy to enhance the safety of UAV flight routes in persistent monitoring tasks, making it difficult for intruders to detect patrol patterns. Nevertheless, the multi-UAV scenario was not taken into account. Besides, some authors have explored optimizing the number of UAVs for monitoring missions with specific revisit constraints. Feng et al. [15] aimed to determine the minimum number of UAVs for coverage task with dynamic priorities. By the proposed recursive algorithm of the minimum spanning tree, the upper bound of the minimum number of UAVs was determined. However, the energy limit of UAVs was not taken into account. Lien et al. [16] presented an algorithm that considers flight endurance, charging time, and latency constraints in a unified framework to find the minimum number of UAVs. Nonetheless, only cases with same monitor latencies across all points were considered. None of the aforementioned studies have addressed the impact of imbalanced task allocation on the persistent monitoring tasks of multiple UAVs. In fact, imbalanced task allocation could potentially affect the efficiency of monitoring tasks, leading to increased energy consumption and maintenance costs for UAVs.

Balanced task assignment can reduce competition and conflict among robot systems, lower the risk during task execution, and enhance the safety and reliability of overall task performance. Wang et al. [17] aimed to plan the energy-balanced path for multiple ferrying UAVs, effectively addressing the issue of task failure due to energy mismatch in search and rescue scenarios. Various studies aim to achieve task balance within robot groups by minimizing the maximum travel time of robots [18–21], focusing on enhancing algorithms to tackle these challenges. For instance, Huo et al. [18] enhanced the simulated annealing algorithm to address task allocation and path planning issues in 3D vehicle routing problem (VRP). Lee et al. [19] introduced a method that evenly distributes paths to each robot without generating redundant paths, effectively preventing collisions among robots. You et al. [20] devised a multi-angle K-means clustering algorithm for the initial partitioning of the different types of tasks and a two-staged strategy for further balanced task assignment. Guo et al. [21] put forward a novel $5\frac{1}{3}$ -approximation algorithm, which is much closer to the optimal. Nevertheless, the differences in task load for each individual robot were ignored in these works. Tang et al. [22] aimed to balance the path length of robots in persistent collaborative coverage tasks. By the proposed feedback mechanism, the bias between the tasks of the robots was greatly reduced. Yu et al. [23] considered balancing the UAVs in scattered region coverage missions. Balanced time consumption of UAVs was achieved through the improved two-staged solution. However, the energy limit of UAVs was not considered. Furthermore, none of the approaches in the above researches are suitable for task scenarios with revisit constraints.

Table I. Summary of the literature review.

A comprehensive table (see Table I) has been made to summarize the features of the aforementioned studies. It can be concluded that few research has been conducted on the balance between multiple UAVs for persistent monitoring tasks with strict revisit constraints while considering the limited energy of UAVs. Therefore, this study investigates balanced multi-UAV path planning for persistent monitoring tasks, where UAVs must return to the base to replace their batteries after completing an energy cycle (see Figure 1). The key contributions are as follows:

1. 1. An assessment method is proposed to balance the tasks among UAVs in persistent monitoring using two innovative indicators. The first indicator is called the waiting factor , which is used to measure the urgency of a node waiting to be revisited after UAVs returned from the base, where a larger waiting factor signifies less urgency and a smaller waiting factor indicates that the node requires prompt visitation. The other one is called the difficulty level , which is introduced to evaluate the task difficulty for each UAV by taking into account the mean and variance of the waiting factors, as well as the number of task nodes.

2. 2. For a single UAV, the ant colony initialized genetic algorithm (ACIGA) algorithm has been proposed to plan its path and calculate its difficulty level. For multiple UAVs, improved K-means clustering algorithm based on difficulty levels has been proposed to achieve balanced task allocation.

Figure 1. Persistent monitoring scenario, where multiple UAVs are used to monitor wildfire situations and return to a fixed base station for replacing the battery at the end of their energy cycle.

The rest of this study is organized as follows: Section 2 introduces the problem background and defines the balance indicators. Section 3 presents the mathematical model used to study the problem. Section 4 introduces ACIGA for planning paths and the improved K-means clustering algorithm for task allocation. Section 5 analyzes the simulation experimental results and evaluates the effectiveness of the algorithms. Lastly, Section 6 concludes the study.

2. Problem descriptions and task balance indicators

2.1. Problem description

To formulate this problem, the set of task nodes that requires persistent monitoring is represented by $G$ . Each task node, denoted as $i$ , has a monitoring period $T_i$ , indicating how often it should be revisited. The UAVs all depart from the base $s_0$ and are capable of visiting a specified set of nodes within one UAV energy cycle before returning to the base for energy replenishment. The algorithmic flow of the proposed method is shown in Figure 2, and this study mainly addresses the following two issues:

1. 1. When there is only one UAV, plan a path that satisfies the monitoring constraints of each node and obtain its difficulty level;

2. 2. When there are multiple UAVs, it is ensured that each node is assigned to only one UAV and task allocation is adjusted based on difficulty levels of UAVs to achieve balanced allocation of tasks.

Figure 2. Research methodology.

Assuming that the maximum monitoring step size in one UAV energy cycle is $K$ , Hari et al. [24] proposed a procedure to estimate it considering the relative positions of task nodes and the actual access sequence of UAVs. The difference is that in this paper, in order to ensure that each task node is visited at least once within one energy cycle of UAV, the monitoring step size of UAVs needs to be greater than the number of their assigned task nodes. Since the UAVs discussed in this paper share identical dynamic characteristics, the maximum monitoring step size in one UAV energy cycle (i.e., $K$ ) for each UAV remains consistent.

2.2. Task balance indicators

The waiting time for a task node is defined as the elapsed time since it was last visited by a UAV. Upon receiving a new visit by a UAV, the waiting time is reset to zero. The remaining lifespan of a node $i$ is calculated by subtracting its waiting time from the monitoring period $T_i$ . Assuming that the time required for a UAV to replace the battery at the base is fixed as $\Delta$ , unexpected situations such as maintenance or malfunction may arise during the process, resulting in the actual replenishing time to exceed $\Delta$ . Therefore, it is preferable to avoid particularly urgent task nodes when returning from the base to the task area, ensuring that UAV has enough buffer time for accidents and avoids violating the monitoring constraints of task nodes.

The waiting factor is introduced in this study to describe the urgency of a node waiting to be revisited when UAVs finish replenishment. And the waiting factor of node $i$ assigned to UAV $n$ is denoted by $V_{i}^{n}$ , as shown in equation (1):

(1) \begin{equation} V_{i}^{n}=\frac{T_{i s_0}^{n}}{t_{i s_0}^{n}} \end{equation}

where $T_{i s_0}^{n}$ is the remaining lifespan of node $i$ when UAV $n$ completes its energy replenishment at the base. $t_{i s_0}^{n}$ represents the minimum flight time for UAV $n$ from the base to node $i$ . To ensure successful execution of missions, the waiting factor of node $i$ needs to satisfy the following constraint:

(2) \begin{equation} V_{i}^{n} \geq 1 \end{equation}

This is because when $0 \leq V_{i}^{n} \lt 1$ , the mission will fail even if the UAV $n$ visits node $i$ from the base immediately; when $V_{i}^{n} \lt 0$ , UAV $n$ has already violated the monitoring constraint before returning to the base. The larger the value $V_{i}^{n}$ is, the less urgent it is for the node $i$ to be accessed; on the contrary, the node should be accessed as soon as possible.

Figure 3. Example.

Choosing $V_{i}^{n}$ instead of $T_{i s_0}^{n}$ to reflect the urgency of node $i$ will be more conducive to balancing task allocation. This is briefly demonstrated with the example in Figure 3, where the information in parentheses represents the node coordinates (in meters) as well as the remaining lifetime (in seconds) of the node, given that the eight nodes have been divided between two UAVs traveling at a speed of 10 m/s. The average remaining lifespan of the task nodes for both UAVs is the same. However, the average waiting factor for nodes assigned to UAV1 is 3.56, whereas the average waiting factor for nodes assigned to UAV2 is 1.19. In terms of average remaining lifespan, both of them bear similar task difficulty. From the perspective of average waiting factor, UAV2 faces a more difficult task. Intuitively, since the task nodes of UAV2 are further away from the base than UAV1, the actual execution difficulty of UAV2 is greater than that of UAV1. Therefore, it can be concluded that using waiting factors will better reflect UAV’s task difficulty and further ensure balanced task allocation.

In addition, there are other factors that need to be considered when assessing the difficulty of UAV tasks. For instance, if all nodes require access simultaneously, the UAV will experience significant pressure. Similarly, a task becomes harder when there are more nodes assigned to the UAV. Therefore, the difficulty of the task could be defined by comprehensively considering the mean and variance of the waiting factors, as well as the number of the nodes assigned to UAV. In this study, the concept of difficulty level is proposed to quantify the task difficulty of UAVs, which is denoted by $C$ . Therefore, the optimization of $C$ can be regarded as the combination of optimization of the mean, variance, and number of the waiting factors. This optimization problem could be inspired by the mathematical approach commonly used in economics to allocate resources or assets over time while considering the trade-off between the expected return and the variance (or risk) of those returns. This is called dynamic mean variance optimization, which can be divided into three categories [25]. The first two methods require optimizing one variable subject to given before optimizing the other one. The third method simultaneously optimizes a combination of mean $E(\cdot )$ and variance $\sigma ^{2}(\cdot )$ , such as Sharpe ratio $E/\sigma$ or weight combinations $E(\cdot )-\beta \sigma ^{2}(\cdot )$ , where $\beta$ is the coefficient. When certain constraints are violated, the negative waiting factor of the task node can lead to a large variance. Therefore, $\beta$ should be as small as possible, $\beta \gt 0$ . In summary, this paper defines the difficulty level of UAV $n$ as follows:

(3) \begin{equation} C_n=\frac{\left |G_n\right |}{\overline{V_n}+\beta \sigma _{n}^2} \end{equation}

where $\overline{V_n}$ is the mean of waiting factors for all nodes assigned to the UAV $n$ , $\sigma _{n}^2$ is the variance, and $|G_n|$ represents the number of task nodes. The higher the difficulty level is (i.e., the larger the value $C_n$ is), the more challenging tasks the UAV $n$ will undertake. Conversely, when the value of $C_n$ is smaller, the task is easier.

It is crucial to emphasize that although the indicators suggested in this study may not hold direct physical significance, the experimental results have demonstrated that these indicators can accurately represent their intended meanings.

3. Persistent monitoring model

Section 3.1 introduces the mathematical model for path planning when there is only one UAV. Section 3.2 presents the mathematical model for balanced task assignment to multiple UAVs. For ease of reference, Table II summarizes the notations introduced in this paper.

Table II. List of notations.

3.1. Path planning model

Use $\{1,2,\ldots, K\}$ to represent the set of discrete steps a UAV takes within one energy cycle, assuming that the UAV starts and ends its trajectory at the base during each cycle. Moreover, it is required that each node is visited at least once, and only one node can be accessed per step. Furthermore, it is not allowed for UAVs to visit the same node during adjacent steps in order to avoid energy waste. The Boolean variable $y_{k,i}^{n}$ indicates that UAV $n$ has reached the node $i$ at step $k$ when its value is 1. The above conditions can be expressed as follows:

(4) \begin{equation} y_{1, s_0}^{n}=1, y_{K, s_0}^{n}=1 \end{equation}

(5) \begin{equation} \sum _{k=1}^{K} y_{k, i}^{n} \geq 1, \forall i \in G_n \end{equation}

(6) \begin{equation} \sum _{i=1}^{|G_n|} y_{k, i}^{n}=1, k=1, 2, \ldots, K \end{equation}

(7) \begin{equation} y_{k, i}^{n}+y_{k+1, i}^{n} \leq 1, \forall i \in G_n, k=1, 2, \ldots, K-1 \end{equation}

where $G_n$ represents the set of nodes assigned to the UAV $n$ . The waiting time $f_{k,i}^{n}$ of node $i$ ( $i\in G_{n}$ ) at the $k$ -th step of UAV $n$ can be defined as:

(8) \begin{equation} f_{k,i}^{n}=\begin{cases}0 &,k=1 \\[5pt] \left (1-y_{k,i}^{n}\right )\bigl (f_{k-1,i}^{n}+c_{k-1,k}^{n}\bigr )&, k=2,3,\ldots, 2K\end{cases} \end{equation}

where $c_{k-1,k}^{n}$ is the time taken by UAV $n$ from step $k-1$ to $k$ . To meet the monitoring requirements, the waiting time at each node should satisfy the following constraint:

(9) \begin{equation} f_{k, i}^{n} \leq T_i, \forall i \in G_n, k=1, \ldots, 2K \end{equation}

where $T_i$ is the maximum monitoring period of node $i$ . The UAV needs to repeat the same path to achieve persistent monitoring. The upper bound of $2K$ for $k$ in Equation 8 and Equation 9 is justified by the fact that as long as the path remains within the constraints during the UAV’s second flight (i.e., from step $K+1$ to $2K$ ), the route will definitely satisfy the monitoring requirements. Besides, the remaining lifespan of node $i$ when UAV $n$ leaves base $T_{i s_0}^{n}$ and the minimum flight time from node $i$ to base $t_{i s_0}^{n}$ in Equation (1) can be represented as follows:

(10) \begin{equation} T_{i s_0}^{n}=T_i-f_{K, i}^{n}-\Delta, \forall i \in G_n \end{equation}

(11) \begin{equation} t_{i s_0}^{n}=\frac{l_{i s_0}}{v}, \forall i \in G_n \end{equation}

where $l_{i s_0}$ represents the linear distance from node $i$ to the base and $v$ is the speed of the UAV $n$ .

For UAV $n$ , its penalty cost $W_n$ for violating constraints is constructed as the sum of overdue time for all monitoring nodes:

(12) \begin{equation} W_n=\sum _{i=1}^{\left |G_n\right |} \sum _{k=1}^{2K} \max \left \{0, f_{k, i}^{n}-T_i\right \} \end{equation}

In order to minimize the urgency of nodes and to realistically reflect tasks difficulty, the chosen route should ensure that the UAV’s difficulty level is minimized. Although the flight time of a UAV is constrained by the maximum energy step size $K$ , it is also necessary to take the flight time $S$ into account to avoid UAVs exceeding their actual energy range. The mathematical model for path planning of UAV $n$ can be expressed as follows:

(13) \begin{equation} \begin{aligned} \text{min } &\quad C_n+\gamma _1S_n+\gamma _2W_n \\[5pt] \text{s.t. } &\quad \overline{V_n}|G_n|=\sum _{i\in G_n}V_i^{n}, \sigma _{n}^2\left |G_n\right |=\sum _{i\in G_n}\left (V_i^{n}-\overline{V_n}\right )^2, \\[5pt] & \quad \text{(1)-(12)} \end{aligned} \end{equation}

where $\gamma _1$ ensures that the difficulty level and flight time of UAV are in the same order of magnitude, which depends on the environment and the flying speed of UAV, $\gamma _1\gt 0$ . In order to reflect the punishment for violating such constraints, the penalty will be increased by a factor of $\gamma _2$ times, $\gamma _2\gt 0$ .

3.2. Task assignment model

If there are $N$ UAVs available, the task assignment serves to allocate unique task nodes to each UAV while ensuring balanced allocations of tasks among all the UAVs. The mathematical model is as follows:

(14) \begin{equation} \begin{aligned} \text{min } &\quad C_{\text{max}} - C_{\text{min}} \\[5pt] \text{s.t. } &\quad G_i\cap G_j=\varnothing, i=1,2,\ldots N,j=1,2,\ldots N,i\neq j \\[5pt] & \quad G_i \neq \varnothing, i=1,2,\ldots N \\[5pt] &\quad \bigcup _{i=1}^N G_i = G \end{aligned} \end{equation}

where $C_{\text{max}}$ is the highest difficulty level among UAVs, while $C_{\text{min}}$ is the lowest. By minimizing the difference between the two (i.e., the maximum deviation of difficulty levels), we can achieve balanced task allocation. This approach prevents the situation where $C_{\text{max}}$ is already at its minimum value, while the difference between $C_{\text{min}}$ and $C_{\text{max}}$ is still significant.

4. Algorithm design

To adjust the task allocation to UAVs, we need to plan their paths first. Section 4.1 introduces the ACIGA for planning a path for a UAV to obtain its difficulty level. Section 4.2 explains how to use difficulty levels to improve K-means clustering algorithm in order to obtain balanced task allocations.

4.1. Ant Colony Initialized Genetic Algorithm (ACIGA)

Heuristic-based methods are effective approaches for solving path planning problems [26]. Among these methods, intelligent optimization algorithms such as genetic algorithms (GAs) are commonly used. Furthermore, most of the existing intelligent optimization algorithms require constructing an initial population that meets certain requirements. The path to be sought in our method differs from a typical TSP path, as the length of a TSP path is determined by the number of nodes that UAV needs to visit, whereas the path length in this paper is fixed as $K$ . For UAV $n$ , when $K=|G_n|+2$ , a random arrangement of $|G_n|$ forms a path. When $K\gt |G_n|+2$ , a feasible approach for constructing a path is to first generate a random arrangement of $|G_n|$ to ensure that all task nodes are accessed. Then, fill the remaining positions with random numbers between 1 and $|G_n|$ , satisfying that adjacent positions have different numbers.

However, the initial population generated in this encoding method often violates the monitoring constraints, affecting the search for optimal solutions. In contrast to other intelligent algorithms, the ant colony algorithm constructs paths by selecting the next node based on heuristic probability, eliminating the need for an initial population for optimization and improving the quality. In this study, we build upon the method introduced by [14] and enhance its heuristic function to generate an initial path. The improvement of heuristics is as follows:

(15) \begin{equation} \eta _{kj}=\frac{f_{k-1,i}}{d_{ij}/\nu }\text{,}k=2,3,\ldots, K \end{equation}

This encourages the ants to select nodes with longer waiting time and shorter distance from their current position. To ensure that all nodes are visited, the remaining path length and the number of unvisited nodes are considered for choosing the next node. If the number of unvisited nodes matches the remaining step length, the unvisited nodes are added directly to the target set. Initializing paths with an enhanced ant colony algorithm reduces the chances of violating constraints and improves the search for optimal solutions in subsequent steps.

Figure 4. Mutation methods (assume $K=12, |G_n|=7$ and 0 represents the base).

While the 2_opt operator utilized in [14] proves to be a potent technique for local search, its efficiency diminishes with increased number of ants and nodes. To avoid this, we limit the use of the ant colony algorithm to the first generation for constructing the initial population. Subsequently, we integrate an enhanced GA characterized by rapid convergence to optimize this initial population. Figure 4 shows the mutation methods involved in GA. The entire ACIGA algorithm is presented in Algorithm1.

Algorithm 1. ACIGA for planning a path for single UAV.

4.2. Improved K-means clustering algorithm

K-means is a widely used clustering algorithm known for its versatility, fast processing, and simplicity. Assigning closer nodes to the same UAV helps to minimize its flight time. As the number of task nodes significantly impacts the UAV’s task difficulty, we aim to achieve a balanced allocation by adjusting the number of task nodes assigned to each UAV. Inspired from the method for equalizing the length of robots’ path in [22], we redefine the distance between nodes and cluster centers by incorporating difficulty levels in Equation 16, which aims to facilitate balanced task allocation:

(16a) \begin{align} &d_{ij}^*=\frac{d_{ij}}{\omega _i},i\in center,j\in G\&j\notin center \end{align}

(16b) \begin{align} &C_i^*=1/C_i,i=1,\ldots N \end{align}

(16c) \begin{align} &\omega _i=\omega _i+p\left (C_i^*-\overline{C^*}\right ),i=1,\ldots N \end{align}

where $d_{ij}$ represents the actual Euclidean distance from a task node $j$ to the cluster center $i$ , $\omega _i$ is the scaling factor of the cluster center $i$ , and $d^*_{ij}$ represents the distance between a task node $j$ and a cluster center $i$ during clustering. $p$ is an amplification factor greater than 0. $\overline{C^*}$ is the mean of $C^*$ . The update method of $\omega _i$ indicates that when the UAV assigned to cluster $i$ has a smaller difficulty level, $\omega _i$ should be increased accordingly, which means that this cluster will attract more task nodes. Otherwise, it will reduce the number of nodes in the cluster. This improved K-means clustering algorithm is presented in Algorithm 2.

Algorithm 2. Improved K-means clustering algorithm for multi-UAV task allocations.

5. Simulation experiment and result analysis

5.1. Single UAV path planning

This subsection presents the experimental results of using ACIGA to plan a path for a single UAV. The UAV’s speed is fixed at 10 m/s, and $\Delta =60$ s, $\beta =0.007$ , $\gamma _1=0.001,\gamma _2=1000$ . Figure 5 shows the distribution map of 15 task nodes, and Table III lists the monitoring period of each node. The parameter settings for ant colony algorithm refer to [14], $Max\_iter1=100$ , $pop\_size=1000$ . All experiments in this paper were conducted in MATLAB R2016a.

Figure 5. The locations of nodes.

When $K=17$ , the maximum waiting time of each task node is consistent and equals the sum of one energy cycle flight time $S$ and $\Delta$ . Table IV compares the results obtained from different objective functions, which shows that both paths obtained can satisfy the monitoring period constraints. Although the flight time obtained under the proposed objective function is slightly longer, both the mean and variance of waiting factors are larger. This indicates that with a slightly higher cost in flight time, our proposed path ensures that the overall urgency level for visiting all task nodes is reduced, allowing more time for dealing with unexpected situations at the base.

The experimental results in Figure 6 demonstrate the effectiveness of ACIGA in solving path problem with $K=22$ . Figure 6(a) illustrates that all nodes have been visited, while Figure 6(c) shows the fast convergence speed of ACIGA. Since the UAV achieves persistent monitoring through a looping path, the maximum waiting time for each task node will be their maximum waiting time during UAV’s second flight. Figure 6(b) displays the maximum waiting time of each task node during the UAV’s first two flights, confirming the path’s compliance with the requirements. For task nodes visited only once within UAV’s one energy cycle, their maximum waiting time equals the sum of $S$ and $\Delta$ .

To further demonstrate the algorithm’s performances, ACIGA was compared to three other algorithms, namely GA without ant colony algorithm initialization, the improved Firefly Algorithm (FA), and the Overdue-aware Ant Colony Optimization (OACO) algorithm [14]. The comparison was based on the results of objective function and time cost of the solution (measured in seconds). Among them, the number of fireflies in FA is 1000, the number of ants in OACO is 100 (the original paper used only 10 ants), and both have an iteration count of 100. The experimental conditions are consistent with Figure 5 and Table II, $K=22$ . Table V displays the comparison between the results of 20 solutions. It can be seen that the proposed ACIGA not only has a relatively faster solving speed but also has better results than other algorithms. These benefits are critical because fast pathfinding is crucial for solving the whole task allocation problem. Furthermore, ensuring minimal variation in objective results for UAVs with the same task allocation helps avoid deception on assignment results and reduce computation time.

5.2. Multi-UAV balanced task allocation

This section will verify the effectiveness of the improved K-means clustering algorithm based on UAVs’ difficulty levels and demonstrate that the proposed indicator can represent the difficulty of UAVs’ tasks. Assuming that there are 3 UAVs available, 43 nodes need to be monitored, with a step size $K=30$ for one energy cycle of each UAV. The weight factors $\omega$ of the initial cluster centers are all set to 10, and $p=5$ , $\varepsilon =0.5$ , $Max\_iter2=10$ .

Table III. The monitoring periods of nodes.

Table IV. Results of different objective functions.

Figure 6. Results of ACIGA with $K=22$ .

According to Figure 8(a) and Figure 8(b), task nodes assigned to UAV3 with numbers 31, 34, 38, 39, 40, 41, 42, and 43 violate monitoring constraints. It is due to imbalanced task allocation that UAV3 violates the constraints, as we have demonstrated the effectiveness of the path solving algorithm in Section 5.1. Hence, task allocation needs adjustment. The difficulty levels of the three UAVs are 1.6925, 2.8341, and 8.3252, with UAV3 having the highest difficulty level. This demonstrates that the proposed indicator effectively represents the task difficulty of UAVs.

Figure 9 shows the results of the improved K-means algorithm, while Figure 10 depicts variation in the maximum difficulty level deviation with the algorithm. When the green nodes in Figure 9(b) do not overlap with the purple nodes, it indicates that the maximum waiting time for that node occurs when the UAV visits the node, returns to the base for replacing the battery, and then visits the node again. Figure 9(b) and Figure 9(c) demonstrate that as UAVs return from the base to the task area and are required to promptly visit all task nodes first, each UAV encounters some task nodes that have a maximum waiting time close to its monitoring period. This suggests that assigning any additional task node to any UAV at this time would increase the risk of violating the constraints. Thus, the task allocation is balanced. Furthermore, the difficulty levels of the three UAVs are very similar, 3.6316, 3.7745, and 3.7802, respectively. It is important to note that assigning No.3 node in Figure 9(a) to UAV2 may seem more energy efficient. However, this would actually result in a larger maximum difficulty level deviation (i.e., the objective value of Equation 14). Because the maximum deviation still exists between UAV1 and UAV3, with the difficulty level of UAV1 decreasing while the difficulty level of UAV3 remains unchanged. To promote the balance of task allocation among UAVs in this paper, it is reasonable to assign No. 3 node to UAV1.

Table VI shows the comparison of the maximum difficulty level deviation under different quantities of UAVs. Due to different initial conditions, the final deviation may vary. However, it can be seen that the algorithm proposed in this paper can effectively reduce the difference to ensure balanced task allocation.

Table V. Algorithm performance comparison.

Figure 7. Comparison of iteration curves from different algorithms.

Figure 8. Results from the ordinary K-means.

Figure 9. Results from the improved K-means.

Figure 10. The variation of maximum deviation.

6. Conclusion

The utilization of multiple UAVs for conducting persistent monitoring tasks with revisit constraints has been widely adopted. However, UAVs have limited energy and require periodic returns to the base for replacing the battery, resulting in time wastage and the potential for mission delays. Therefore, balanced task assignment for multiple UAVs is crucial for guaranteeing UAV safety and improving task success rates. This study introduces two novel indicators to achieve balanced path planning for persistent monitoring. By considering the distance between the task node and the base along with the remaining lifespan of the node, the waiting factor can more accurately be used to indicate the urgency of visiting an individual task node after UAVs have returned from the base. Then, by taking into account the number of task nodes and the variance and mean of waiting factors, the task difficulty of the UAV can be evaluated. The objective for a UAV is to ensure a minimum difficulty level, allowing sufficient time for accessing task nodes during the return from the base to the mission area. By minimizing the deviation of difficulty levels among UAVs, balanced task allocation is achieved. To address these issues, this study additionally proposes ACIGA for UAV’s path planning and an improved K-means clustering method for balanced task allocation of multiple UAVs. The experimental results have demonstrated the effectiveness of the proposed algorithms and confirmed that the introduced indicators could assist in achieving balanced multi-UAV path planning for persistent monitoring tasks. However, the dynamics of UAVs and the communications among UAVs, as well as between UAVs and the base, are ignored in this paper. When a UAV malfunctions during the mission, it is crucial to reallocate the remaining UAVs promptly to complete the tasks assigned to the faulty UAV. How to balance the workload of these UAVs is also an important issue to consider.

Table VI. Maximum deviation of difficulty level under different quantities of UAVs.