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. [Reference Hari, Rathinam, Darbha, Kalyanam, Manyam and Casbeer24] 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 [Reference Xia25]. 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.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.1. Ant Colony Initialized Genetic Algorithm (ACIGA)

Heuristic-based methods are effective approaches for solving path planning problems [Reference Tan, Gao, Wang, Zhang and Zhang26]. 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 [Reference Shu, Chen, Hu, Wu and Zhao14] 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 [Reference Shu, Chen, Hu, Wu and Zhao14] 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 [Reference Tang, Zhou, Sun, Di and Xiong22], 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.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 [Reference Shu, Chen, Hu, Wu and Zhao14], $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 [Reference Shu, Chen, Hu, Wu and Zhao14]. 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.