Task Parameter Planning Algorithm for UAV Area Complete Coverage in EO Sector Scanning Mode

Abstract

When Unmanned Aerial Vehicles (UAVs) are used in search and rescue operations, electro-optical (EO) devices are usually used as the detection equipment, and area coverage is used as the main search method. However, the sector scanning mode of EO puts forward higher requirements for task parameter planning. First, to ensure there is no missing coverage, a method to determine the full coverage width of EO equipment in sector scanning mode is proposed. Second, the constraint of no interval missing and the model of the speed-to-high ratio constraint are established, and the constraints of other factors are addressed in the context of the problem situation. Third, a coverage efficiency index is proposed for the boustrophedon coverage of a rectangular area, and a comprehensive coverage index is established. Finally, task parameter planning algorithms are designed, based on Immune Algorithm (IA), Grey Wolf Optimization (GWO) and Variable Neighborhood Search (VNS), respectively. The simulation results showed that the designed algorithms, based on IA, GWO and VNS, can effectively solve task planning problems. In general, IA is more suitable for offline occasions, VNS is suitable for online real-time planning, and GWO has characteristics between the two. The coverage process, based on optimized parameters, meets all constraints, has higher search efficiency and does not miss areas, proving the correctness of these models and the effectiveness of the planning algorithm. The research presented in this paper provides a technical basis for efficient and fully automated target search and rescue.

1. Introduction

The search and rescue problem has always existed along with the development of society, and it is also a long-term challenge. Traditional search and rescues are mainly implemented with the utilization of manned aircraft, helicopters, ships, etc. In recent years, with the increasing maturity of Unmanned Aerial Vehicles (UAVs) and photoelectric sensors, search and rescue operations based on UAV have proven feasible and have been successfully tested and applied [1,2,3], showing advantages of large range, strong timeliness, low risk and low economic cost.

Area complete coverage search is a commonly used search and rescue method for UAVs [4] and is suitable for maritime rescue [5], disaster rescue [6], and for use in mountainous areas [7]. In addition, area coverage search can also be used for regional investigation [8], patrol and surveillance [9], infrastructure inspection [10], precision agriculture [11,12] and other scenarios. Consequently, it has become an important research direction for UAV applications. The goal of area coverage is to cover the entire area of interest, while minimizing the time and distance spent on covering routes [13].

In a UAV area coverage search, electro-optical (EO) equipment is typically used for detection. EO equipment has advantages of high resolution and long detection distances, but the disadvantage is that the fixed field of view is relatively small. Therefore, to improve search efficiency, operators control the EO device to perform sector scanning relative to the aircraft body. This usage greatly increases the coverage width of UAV during a single route, but also puts higher requirements on mission parameter planning, such as balancing the limitations of the UAV platform, EO device, environmental conditions, and operators to maximize the execution efficiency of the mission process. This has become a difficult and valuable issue for users.

At present, many studies on UAV area coverage have focused on route planning algorithms, mainly focusing on the effective planning of covered routes in complex areas. For areas with regular shapes, such as rectangles, no decomposition is required. Simple path planning is sufficient for complete coverage without overlapping. A typical example is the boustrophedon method, which is a route pattern that simply moves back and forth along the longest side of a polygon [14,15].

For areas with irregular shapes, most area coverage route planning algorithms decompose the target area into subunits. For example, Choset proposed an approximate cell decomposition method [16], which decomposes the generated grid map into smaller sub-maps and then generates the navigation trajectory covering the entire area, according to the density of obstacles in each sub-map. Other similar decomposition methods include cell-based [17], Morse-based [18], wavefront-based [19], and neural network-based [20]. On the basis of decomposition, further path planning to cover the area can be performed. For example, ref. [21] proposed a new method based on ant colony optimization (ACO) to determine the trajectory of a UAV that can strike a balance between the calculation requirements and the quality of the trajectory plan. A new coverage flight path planning algorithm, based on the ACO algorithm, was also designed in [22], which can find collision-free, minimum-length flight paths for UAV in a three-dimensional (3D) urban environment with fixed obstacles. Other algorithms used for UAV coverage route planning include the constrained differential evolution [23], grey wolf optimizer [24], and hybrid algorithms [25]. A real-time path-planning solution for an area-coverage mission using multiple cooperative UAVs was proposed in [26]. The experimental results showed that the probability of achieving a 50% success rate with three UAVs is 2.35 times faster than that with one UAV. Given the limited capabilities of a single UAV, it is sometimes necessary for multiple UAVs to collaborate to complete a certain task, which can significantly improve coverage efficiency and provide better timeliness. Leader–follower [27] is an effective route planning method for multi-UAV formation flight.

In the aforementioned studies, the coverage width of the search equipment is usually set as a constant, and route planning is carried out accordingly, without considering the influence of EO equipment resolution, scan mode, and other factors on coverage width and route planning.

A brief model of EO coverage width was established in some studies, wherein the influence of factors, such as flight height, on coverage width was initially considered, and a comprehensive study was conducted by combining a route planning algorithm. For example, in [28,29,30], the geometric relationship between the static detection width of the UAV detector and flight height, pitch angle, and search azimuth angle was preliminarily studied. Avellar [31] calculated the coverage width of the camera according to the width of the field of view of the image sensor, focal length of the camera lens, and distance H (flight height) between the camera and ground. Di Franco [32] calculated the optimal motion trajectory and maximum height according to the distance of ground samples (image resolution) and proposed an energy-saving round-trip complete coverage algorithm to minimize the number of turns and, thus, improve task efficiency. However, these models of coverage width do not consider limitations and influencing factors, such as target recognition, velocity-to-height ratio, scan omission, and field-of-view distortion. Generally, they differ significantly from the actual situation, and cannot reflect the actual situation in practice.

Some scholars have promoted the application of computer vision in search tasks to reduce the workload of mission personnel and have even promoted the development of fully autonomous UAVs for search missions [33,34]. Experiments have begun on UAVs equipped with perception components based on deep neural networks (DNN). In [35], DNN models that were pre-trained in different fields were proposed for UAVs, one for detecting human joints, and the other for measuring the similarities in appearance between two images in pedestrian tracking to solve the tracking problem. In [36], the limitation of time for search and rescue missions was emphasized, and the embedded system, which is based on deep learning technology, can detect swimmers in open waters, thus enhancing the combat ability of emergency personnel. Combined with global navigation satellite system (GNSS) technology, it can be used for accurate human detection and rescue equipment release. In [37], a camera-based UAV system for automatic target positioning was developed. By setting reasonable pigment thresholds, the automatic recognition of red and blue targets in aerial images was realized, providing useful insights for exploration in automatic target recognition. It should be pointed out that fully autonomous UAVs for search missions undoubtedly represent the trend of the future. However, although this progress improves identification efficiency, it also has higher requirements for no-omission coverage.

According to the literature searched, research on parameter planning of complete area coverage tasks in the EO sector scanning mode is still lacking.

Furthermore, task parameter planning for sector scanning involves many factors and needs to consider requirements and constraints from the perspective of many aspects, which is a typical multi-objective optimization problem. Many effective algorithms have been developed for different multi-objective optimization problems. Exhaustive search techniques can solve discrete optimization problems, but the computational cost is high when the variable space is large [38]. Scenario-based robust optimization can ensure better optimization robustness under the premise of achieving optimization objectives, such performance being crucial for uncertain environments [39]. Heuristic search algorithms have high efficiency but can only obtain suboptimal solutions [40]. Some new bionic heuristic algorithms, such as Gray Wolf Optimization (GWO) [41,42] and Particle Swarm Optimization (PSO) [43], have similar characteristics. The Genetic Algorithm (GA) [44] is suitable for almost all optimization problems, but requires a large amount of computation and is generally used in offline situations. The Immune Algorithm (IA) [45] retains the evolutionary mechanism of GA, and at the same time has a unique concentration inhibition mechanism, which better overcomes the problem of local optimization, but has the disadvantage of high computational cost. The Variable Neighborhood Search (VNS) [46] and Multistage Neighborhood Search (MNS) [47] algorithms overcome the local search limitation of Neighborhood Search (NS) and can search the solution space in multiple different neighborhoods, so they have good global search ability. The implementation of the algorithm is relatively simple. However, its convergence accuracy depends on the design of neighborhood operators and the setting of the algorithm parameters, which requires users to have a certain amount of professional experience. Therefore, it is necessary to develop an efficient and high-precision optimization algorithm for this problem. In the study here presented, the representative IA, GWO, and VNS algorithms were used to solve the task planning problem, and the convergence performance and computing efficiency of different optimization algorithms compared, providing a useful reference for solving the problem.

In general, there are several problems in the current research, as follow:

• Most research on UAV coverage focuses on route planning algorithms, and the processing of EO equipment factors is too simple, or is even ignored, which does not reflect the actual situation.
• There is a lack of research on area-coverage task planning in the sector scanning mode of UAV EO equipment. There is not only a lack of descriptive model research for the problem but also a lack of task planning research combining the problem model and optimization algorithm.

In view of this, the objectives of this paper follow:

• A no-omission coverage width model was established for the sector scanning of UAV EO equipment that considers the influence of target recognition.
• Description models of the constraints were established that, combined with the sector scanning method, consider the influence of various constraints on parameter planning of the area coverage task. Such as target recognition, speed-to-height ratio, and missed scanning, etc.
• A parameter planning algorithm to address the area coverage task in the sector scanning mode was designed to ensure an efficient search, based on the representative IA, GWO, and VNS algorithms, and combined with constraints.
• The three designed task planning algorithms were simulated and verified, and the main performances of these algorithms in solving the problems in this study were compared.

2. Coverage Width Modeling

2.1. Scanning Mode of the UAV EO Equipment

There are a variety of scanning modes for the UAV EO equipment, such as side scan, cone scan, and sector scan. In this study, the most common and complex sector scanning mode was investigated, and the other modes regarded as a special case of the sector scanning mode.

As shown in Figure 1, it was assumed that the UAV maintains horizontal flight. In sector scanning mode, the pitch angle ${\mu }^{\prime }$ of the EO equipment view field remains unchanged, and the azimuth angle $\theta$ of the field of view scans back and forth at a constant speed within an angular range [$-\theta$,$\theta$].

2.2. Model of Static View Field of EO Equipment

In the sector scanning mode, there are two types of view fields of the EO equipment: scanning view field and static view field. The static view field is the inherent angle of view of EO equipment, and the scanning view field is the detectable range of the static view field during scanning mode, which is related to the static view field and the scan azimuth angle $\theta$.

As shown in Figure 2, $O_1$ represents the position of the EO equipment, its projection on the ground is $O$, and its flying height is $h$. A coordinate system is established with $O$ as the origin, the $OX$ axis is the projection direction of the central axis of the view field on the ground, and the $OY$ axis is the vertical upward direction. The $OZ$ axis is determined according to the right-hand rule.

As shown in Figure 2, if $\epsilon$ is used to represent the static view field angle of the EO equipment, then ${\mu }_1$ and ${\mu }_2$ are the pitch angles of the inner and outer edges of the view field, respectively.

$${\mu }_2={\mu }_1+\epsilon$$

(1)

Generally, to find a target in a certain area, we need to ensure two points [48]: first, that the target area is completely scanned without missing data, ensuring that when the field of view scans the target, the target can be identified and found. The problem of target recognition is related to many factors, including the ability of the searcher, environmental factors, and the characteristics of the target itself [49]. Therefore, it needs to be studied by combining theory and practice, and is not addressed in this study. However, to reflect the impact of the target recognition problem on task planning, a target recognition distance threshold $d_{ShB}$ was set in this study. When the target distance is less than $d_{ShB}$, the target can be recognized; otherwise, it is missed. The distance $d_{ShB}$ comprehensively represents the influence of weather visibility, target characteristics, and EO resolution on the target recognition problem, which limits task parameter planning during coverage search tasks.

As shown in Figure 2, the larger the pitch Angle u is, the larger the area covered by the static view field is, but this also brings adverse effects, including image resolution reduction, graphic distortion aggravation, and so on, affecting the target recognition. Therefore, the pitch Angle ${\mu }_2$ must be limited. In the region ABCD covered by the static view field, point B is the furthest position away from the EO device. When the target is located at point B, it is the most difficult to identify. Therefore, when the flight altitude is constant, it can be considered that, when the length of OB is equal to $d_{ShB}$, it is the maximum allowable pitch Angle of EO for target recognition. Therefore, the following equation must be satisfied:

$$O_{1}A=O_{1}B\le d_{ShB}$$

(2)

Threshold $d_{ShB}$ needs to be determined in advance according to weather conditions, target characteristics, and EO equipment recognition pixels, combined with the experience of task operators.

The region formed by the four points of A, B, C and D is the coverage area of the static view field of the EO equipment. It can be seen that the area is not a rectangle, but a trapezoid. For subsequent optimization calculations, each side of the region must be determined.

When $O_{1}A=O_{1}B=d_{ShB}$, the maximum static coverage region can be obtained, and the reliable recognition of the target guaranteed, which is beneficial in improving the search efficiency; thus, $O_{1}A=O_{1}B=d_{ShB}$ can be set.

The four sides are represented as l_AB, l_BC, l_CD, l_AD, and l_BC = l_AD. In triangle $O_{1}A{E}_1$, it can be deduced that:

$$l_{AB}=2\cdot d_{ShB}\cdot \sin \frac{\epsilon }{2}$$

(3)

Similarly, in triangle $O_{1}OA$, using the trigonometric function, it can be deduced that:

$$l_{OA}=\sqrt{{\left(d_{ShB}\right)}^2-h^2}$$

(4)

$${\mu }_2=\arccos \left(h/d_{ShB}\right)$$

(5)

Using Equations (1) and (5), ${\mu }_1$ can be obtained. In the triangle $O_{1}OD$, it can be deduced that:

$$l_{OD}=h\cdot \tan {\mu }_1$$

(6)

$$l_{O_{1}D}=h/\cos {\mu }_1$$

(7)

$l_{CD}$ and $l_{AD}$ are obtained as:

$$l_{CD}=2\cdot l_{O_{1}D}\cdot \sin \frac{\epsilon }{2}$$

(8)

$$l_{AD}=l_{OA}-l_{OD}$$

(9)

2.3. Complete Coverage Width Modeling

Complete coverage of the target area is a prerequisite for target identification. Therefore, a reasonable determination of the EO coverage width is of great significance to ensure an effective search success rate and to improve search efficiency.

2.3.1. Problem Description

As shown in Figure 2, $l_{OA}$ and $l_{OD}$ are defined as the outer radius $R_2$ and inner radius $R_1$ of the static coverage region, respectively.

$$R_2=\sqrt{{\left(d_{\max }^{ShB}\right)}^2-h^2}$$

(10)

$$R_1=h\cdot \tan \left(\arctan \left(R_2/h\right)-\epsilon \right)$$

(11)

As shown in Figure 3, $V$ is defined as the flight speed, and it is assumed that the rotational angular velocity of the optical axis of the EO equipment in the horizontal plane is $\omega$. When the EO equipment rotates and scans in the horizontal plane, the pitch angle µ of the optical axis of the field of view remains unchanged.

We define a process in which the static coverage region moves from the leftmost end (position “A₁B₁C₁D₁”) to the rightmost end (position “A₂B₂C₂D₂”), and then back to the leftmost end (position “A₃B₃C₃D₃”) as a scanning cycle. The scanning cycle time is denoted by T.

$$T=4\left({\theta }_1-\epsilon /2\right)/\omega$$

(12)

${\theta }_1$ is the scan azimuth.

In a scanning cycle, the UAV flies from $O_1$ to $O_3$, The distance between $O_1$ and $O_3$ is represented by $l_{O_1{O}_3}$, then:

$$l_{O_1{O}_3}=V\cdot T$$

(13)

In a scanning cycle, the EO completes the scanning of two circular arc areas; the area scanned clockwise is indicated by the red line, and the area scanned counterclockwise is indicated by the blue line.

The reachable search width is represented by $d$.

$$d=2R_2\sin {\theta }_1$$

(14)

However, because the UAV is in continuous flight, there is a “missing area” between the two scan areas in the direction of the maximum value of the dynamic search azimuth, as shown in Figure 3.

Therefore, the search width must be appropriately reduced to exclude the “missing area” to ensure that there are no missing searches. If the innermost point of the “missing area” is represented by $P_1$, a parallel line parallel to the flight direction through $P_1$ is drawn, and the parallel line is the maximum range that can be guaranteed to search without omission.

Let $d_1$ represent the coverage width of the complete search, related to factors such as UAV flying speed $V$, photoelectric equipment scanning angular velocity $\omega$, static field of view $\epsilon$, search azimuth ${\theta }_1$, inner/outer radius of the static coverage region $R_1$ and $R_2$, etc. It is necessary to comprehensively consider many factors to determine $d_1$.

First, a two-dimensional ground-level coordinate system is established with $O_1$ as the origin, the flying direction as the $Y$ axis, the $X$ axis perpendicular to the $Y$ axis, and the right direction as positive. The intersection of trajectory $\stackrel{⌢}{B_1{B}_2}$ and straight-line $L_{O_3{B}_3}$ is the position of point $P_1$. In the coordinate system $O_{1}XY$, the point $P_1$ can be expressed as $\left(x_{P1},y_{P1}\right)$. Then:

$$d_1=2\left|x_{P1}\right|$$

(15)

To solve point $P_1$, it is necessary to establish a mathematical equation of trajectory $\stackrel{⌢}{B_1{B}_2}$ and straight-line $L_{O_3{B}_3}$.

2.3.2. Equation of Trajectory $\stackrel{⌢}{B_1{B}_2}$

The time was set to 0 when the UAV was at $O_1$, and $B_1$ was set as the starting point of the trajectory. In the coordinate system $O_{1}XY$, since the static coverage region moves in a uniform circular motion in the horizontal plane on the one hand, and flies in a straight line with the carrier aircraft on the other hand, the functional expression of the trajectory $\stackrel{⌢}{B_1{B}_2}$ can be described as:

$$\{\begin{array}{l}{x}_{B1}\left(t\right)=R_2\cdot \sin \left(\omega \cdot t-{\theta }_1\right)\\ y_{B1}\left(t\right)=R_2\cdot \cos \left(\omega \cdot t-{\theta }_1\right)+V\cdot t\end{array}$$

(16)

In Formula (16), $t$ is the time variable, $t\in \left[0,T/2\right]$. $x_{B1}\left(t\right)$ and $y_{B1}\left(t\right)$ are the abscissa and ordinate, respectively, of a point on the trajectory at time t.

Transform the expression of $x_{B1}\left(t\right)$ as:

$$t=\left(\arcsin \left(x_{B1}/R_2\right)+{\theta }_1\right)/\omega$$

(17)

The value range of $x_{B1}$ was [$-R_2\sin {\theta }_1$, $R_2\sin \left({\theta }_1-\epsilon \right)$]. Substituting Equation (17) into the expression for $y_{B1}\left(t\right)$, we obtain:

$$y_{B1}=R_2\cdot \cos \left(\arcsin \left(x_{B1}/R_2\right)\right)+V\cdot \left(\arcsin \left(x_{B1}/R_2\right)+{\theta }_1\right)/\omega$$

(18)

2.3.3. Equation of Trajectory $\stackrel{⌢}{C_3{C}_2}$

The same method was used to model the trajectory $\stackrel{⌢}{C_3{C}_2}$. However, for convenience of calculation, consider $C_3$ as the starting point and $C_2$ as the end of the trajectory; that is, when the trajectory is at point $C_3$, t = 0. Although this setting is opposite to that of the actual process, it maintains synchronization with the trajectory $\stackrel{⌢}{B_1{B}_2}$ in time, which is convenient for the subsequent comparison of the two trajectories. The functional expression of the trajectory $\stackrel{⌢}{C_3{C}_2}$ is described as

$$\{\begin{array}{l}{x}_{C2}\left(t\right)=R_1\cdot \sin \left(\omega \cdot t-{\theta }_1\right)\\ y_{C2}\left(t\right)=R_1\cdot \cos \left(\omega \cdot t-{\theta }_1\right)+V\cdot \left(T-t\right)\end{array}$$

(19)

t is the time variable, $t\in \left[0,T/2\right]$. $x_{C2}\left(t\right)$ and $y_{C2}\left(t\right)$ are the abscissa and ordinate, respectively, of a point on the trajectory at time t.

Similarly, Equation (19) is transformed to eliminate the time variable t, and we obtain:

$$y_{C2}=R_1\cdot \cos \left(\arcsin \left(x_{C2}/R_1\right)\right)+V\cdot \left(T-\left(\arcsin \left(x_{C2}/R_1\right)+{\theta }_1\right)/\omega \right)$$

(20)

The value range of $x_{C2}$ was [$-R_1\sin {\theta }_1$, $R_1\sin \left({\theta }_1-\epsilon \right)$]. Compared with the value range of $x_{B1}$, since $R_2>R_1$, the value range of $x_{B1}$ includes the value interval of $x_{C2}$.

2.3.4. Equation of Straight Line $L_{O_3{B}_3}$

The function expression of the straight line $L_{O_3{B}_3}$ is:

$$y_{O_3{B}_3}=-\tan \left({\theta }_1\right)\cdot x_{O_3{B}_3}+V\cdot T$$

(21)

The value range of $x_{O_3{B}_3}$ is $\left[-R_2\sin {\theta }_1,0\right]$. Combining the equation of trajectory $\stackrel{⌢}{B_1{B}_2}$ and the equation of $L_{O_3{B}_3}$, we obtain the following equation system:

$$\{\begin{array}{l}{y}_1=-\tan \left({\theta }_1\right)\cdot x_1+V\cdot T\\ y_1=R_2\cdot \cos \left(\arcsin \left(x_1/R_2\right)\right)+V\cdot \left(\arcsin \left(x_1/R_2\right)+{\theta }_1\right)/\omega \end{array}$$

(22)

The solution of Equation (22) described as $\left(x_{P1},y_{P1}\right)$ is the coordinate of $P_1$, and $d_1=2\left|x_{P1}\right|$.

3. Constraints Modeling

There is still a lack of corresponding research on the limitations of the speed-to-height ratio and the no interval missing in the sector scanning mode. In this section, we focus on the limitations of the speed-to-height ratio and the no interval missing constraint on the task planning problem and establish corresponding mathematical models. In addition, various constraint conditions are provided in the form of a threshold or value range.

3.1. Speed-to-Height Ratio Constraint Modeling

To ensure stable imaging of the target, photoelectric imaging equipment generally has the limitation of a speed-to-height ratio. As shown in Figure 4, assuming that the speed of the UAV is V, the flying height is h. The point $P_2$ is a point in the detection area, and its pitch angle, relative to the location of the EO equipment $O_1$, is ${\mu }^{\prime }$, so, ${\mu }_1\le {\mu }^{\prime }\le {\mu }_2$. The azimuth angle is represented by ${\theta }^{\prime }$. The distance between $P_2$ and $O_1$ is represented as $R^{\prime }$, then:

$$R^{\prime }=h/\cos {\mu }^{\prime }$$

(23)

Assume that the partial velocity of V in the direction perpendicular to $O^{\prime }{P}_1$ is represented by $V^{\prime }$. Using velocity decomposition and trigonometric functions, $V^{\prime }$ can be obtained as:

$$V^{\prime }=\sqrt{{\left(V\cdot \cos {\theta }^{\prime }\cdot \cos {\mu }^{\prime }\right)}^2+{\left(V\cdot \sin {\theta }^{\prime }\right)}^2}$$

(24)

The rotational angular velocity of $P_2$ relative to $O_1$ is represented by ${\omega }_1$, then

$${\omega }_1=V^{\prime }\cos {\mu }^{\prime }/h=\sqrt{{\left(V\cdot \cos {\theta }^{\prime }\cdot \cos {\mu }^{\prime }\right)}^2+{\left(V\cdot \sin {\theta }^{\prime }\right)}^2}\cos {\mu }^{\prime }/h$$

(25)

Assuming that the maximum speed-to-height ratio is $\gamma$, according to the principle of the speed-to-height ratio, then

$$V\cdot \sqrt{{\left(\cos {\theta }^{\prime }\cdot \cos {\mu }^{\prime }\right)}^2+{\left(\sin {\theta }^{\prime }\right)}^2}\cdot \cos {\mu }^{\prime }/h\le \gamma$$

(26)

As a result of ${\mu }_1\le {\mu }^{\prime }\le {\mu }_2$, the following formula holds:

$$\sqrt{{\left(\cos {\theta }^{\prime }\cdot \cos {\mu }^{\prime }\right)}^2+{\left(\sin {\theta }^{\prime }\right)}^2}\cdot \cos {\mu }^{\prime }\le \sqrt{{\left(\cos {\theta }^{\prime }\cdot \cos {\mu }_1\right)}^2+{\left(\sin {\theta }^{\prime }\right)}^2}\cdot \cos {\mu }_1$$

(27)

So, Equation (26) can be replaced by:

$$V\cdot \sqrt{{\left(\cos {\theta }^{\prime }\cdot \cos {\mu }_1\right)}^2+{\left(\sin {\theta }^{\prime }\right)}^2}\cdot \cos {\mu }_1/h\le \gamma$$

(28)

Further transforming the left side of Equation (28), we derive:

$$V\cdot \sqrt{1-{\left(\cos {\theta }^{\prime }\cdot \sin {\mu }_1\right)}^2}\cdot \cos {\mu }_1/h\le \gamma$$

(29)

As a result of ${\theta }^{\prime }\le {\theta }_1$, we obtain:

$$V\cdot \sqrt{1-{\left(\cos {\theta }^{\prime }\cdot \sin {\mu }_1\right)}^2}\cdot \cos {\mu }_1/h\le V\cdot \sqrt{1-{\left(\cos {\theta }_1\cdot \sin {\mu }_1\right)}^2}\cdot \cos {\mu }_1/h\le \gamma$$

(30)

Equation (30) is the constraint due to the speed-to-height ratio.

3.2. No Interval Missing Constraint Modeling

When the flight speed is too fast, the static coverage region is too small, and there is a missing coverage area between the two sector scan areas, as shown in Figure 5.

To avoid this situation, we suggest that trajectory $\stackrel{⌢}{C_3{C}_2}$ never exceeds trajectory $\stackrel{⌢}{B_1{B}_2}$. That is, for any $x$ in the range $\left[-R_1\sin {\theta }_1,R_1\sin \left({\theta }_1-\epsilon \right)\right]$ that is applicable to trajectory Formulae (18) and (20), the following equation holds.

$$y_{c2}\left(x\right)\le y_{B1}\left(x\right)$$

(31)

Equation (31) is an important constraint in coverage task planning.

3.3. The Other Constraints

Many factors affect the coverage width. Commonly used constraints are described in the following sections.

3.3.1. Constraint on Pitch Angle

Due to equipment performance limitations, generally the pitch angle of the field of view is not lower than a threshold, as otherwise, it is difficult for the equipment to track the target stably. Suppose the threshold is ${\mu }_{\min }$, then,

$${\mu }_{\min }\le {\mu }_1<{\mu }_2$$

(32)

3.3.2. Constraint on Rotation Angular Velocity

Owing to the requirements of visual recognition and visual fatigue of the task staff, the value of $\omega$ should not be too large. If ${\omega }_{\max }$ is used to represent its maximum value of $\omega$, then

$$\omega \le {\omega }_{\max }$$

(33)

3.3.3. Constraint on Search Azimuth ${\theta }_1$

When the axis of the centerline of the static field of view coincides with the direction of the flight speed on the ground, the value of ${\theta }_1$ is the smallest, which is $\epsilon /2$. The maximum value of ${\theta }_1$ is $\pi /2$, and the search width reaches its maximum. So that

$$\epsilon /2\le {\theta }_1\le \pi /2$$

(34)

3.3.4. Constraint on Flying Height $h$

For the sake of flight safety, the flying altitude is generally not allowed to be lower than a certain altitude $h_s$, and $h_s$ is usually set according to the performance of the aircraft and different weather conditions. In a mission, $h_s$ is typically given as a threshold.

$$h\ge h_s$$

(35)

Owing to the requirement of recognition distance, the distance between the outer edge of the static coverage region and the UAV position $O_1$ should not be greater than $d_{ShB}$, that is, $l_{O_{1}A}\le d_{ShB}$. This limits the flying height of UAVs. From Equations (1) and (32), we know that

$${\mu }_2\ge {\mu }_{\min }+\epsilon$$

(36)

While flight altitude

$$h=l_{O_{1}A}\cdot \cos \left({\mu }_2\right)\le d_{\max }^{ShB}\cos \left({\mu }_2\right)\le d_{\max }^{ShB}\cos \left({\mu }_{\min }+\epsilon \right)$$

(37)

3.3.5. Constraint on Flying Speed $V$

At present, most UAVs that have been used practically have had low cruise speeds. Assuming that the selectable range of cruising speed is [$V_1$,$V_2$], then

$$V_2\ge V\ge V_1$$

(38)

4. Design of Task Parameter Planning Algorithm

4.1. Comprehensive Task Planning Objective Model

For global optimization problems, a certain parameter cannot simply be used as an optimization objective. For example, in this study, maximizing the coverage width without omissions is not sufficient, and the task objective must be the final planning objective.

For the coverage search, the larger the coverage search area per unit time, the better. Based on this, an evaluation index is defined as coverage efficiency $\eta$:

$$\eta =S/t=\left(V\cdot t\cdot d_1\right)/t=V\cdot d_1$$

(39)

where S is the search area within t time. If the maximum coverage in a cycle time is required, the index function, based on search efficiency, is

$$\max \left(d_1\cdot V\right)$$

(40)

From the perspective of identification, the smaller the $\omega$ value, the better. Therefore, another index function can be obtained

$$\min \left(\omega \right)$$

(41)

Set $h_0$ and $V_0$ to be the best cruise speed and cruise altitude, respectively, under current weather conditions. Then, $h_0$ and $V_0$ are more conducive to maintaining a longer task range. However, in general, the optimal speed at different altitudes is also different, but their corresponding relationship i not expanded in this study; therefore, $h_0$ and $V_0$ are both constants.

The deviations $\left|\mathsf{\Delta }{h}_0\right|$ and $\left|\mathsf{\Delta }{V}_0\right|$ are the deviations between the current altitude h, speed V and the best value, respectively. The smaller the deviation from the ideal value, the better. Therefore, two index functions can be obtained as:

$$\min \left(\left|\mathsf{\Delta }{V}_0\right|\right)=\min \left(\left|V-V_0\right|\right)$$

(42)

$$\min \left(\left|\mathsf{\Delta }{h}_0\right|\right)=\min \left(\left|h-h_0\right|\right)$$

(43)

Equations (40)–(43) constitute the objective function system of coverage task planning. This is a typical multi-objective optimization problem. For multi-objective optimization problems, a common approach to establish a comprehensive objective function is the weight coefficient method [50,51], which consists of the following steps:

• First, the values of each objective function are normalized for comparison at the same scale.

$$\{\begin{array}{l}\max \left(d_1\cdot V\right)/\left(d_{ShB}\cdot V_2\right)\\ \min \left(\left|\mathsf{\Delta }{V}_0\right|\right)/V_2\\ \min \left(\left|\mathsf{\Delta }{h}_0\right|\right)/h_{\max }\\ \min \left(\omega \right)/{\omega }_{\max }\end{array}$$

(44)

2.

Second, according to the importance of the indices, different weight coefficients are assigned. For a complete coverage search task, the primary goal is to complete the coverage area in the shortest time, the secondary goal is to ensure search efficiency and high recognition probability, and the third goal is to ensure economy. Therefore, for the four index functions to be optimized the following is important:

$$\max \left(d_1\cdot V\right)Prior.to.\min \left(\omega \right)Prior.to.\min \left(\left|\mathsf{\Delta }{V}_0\right|\right)Equal.to.\min \left(\left|\mathsf{\Delta }{h}_0\right|\right)$$

If the weight coefficients of the four index functions are represented by $K_{\eta }$, $K_{\omega }$, $K_{V_0}$, and $K_{h_0}$, the following should be ensured:

$$K_{\eta } > K_{\omega } > K_{V_0}=K_{h_0}$$

3.

Finally, the weighted sum of each optimization index function can be used to obtain a comprehensive task planning objective function $J$:

$$\{\begin{array}{l}\max \left(J\right)\\ J=K_{\eta }\cdot \left(d_1\cdot V\right)/\left(d_{\max }^{ShB}\cdot V_2\right)-K_{\omega }\cdot \omega /{\omega }_{\max }-K_{V_0}\cdot \left|\mathsf{\Delta }{V}_0\right|/V_2-K_{h_0}\cdot \left|\mathsf{\Delta }{h}_0\right|/h_{\max }\end{array}$$

(45)

4.2. Design of Task Planning Algorithm

The task planning problem is a typical multi-objective problem with complex models, numerous constraints, and nonlinear mutations, which are difficult to handle with traditional analytical methods. Based on evolutionary algorithms, this type of problem can be solved effectively [52].

4.2.1. Task Planning Algorithm Based on IA

The Immune Algorithm (IA) was first used to design the task planning algorithm. In sector scanning mode, the main task parameters include speed $V$, altitude $h$, scanning azimuth ${\theta }_1$ and scanning angular velocity $\omega$, forming a set. Each set of parameters, $\left(V,h,{\theta }_1,\omega \right)$ is used as an antibody in the IA population, and the population size set to 50. It is important to note that the initialization of these parameter sets was limited by the corresponding threshold range.

According to a set of task parameters, the pseudocode to calculate the complete coverage width $d_1$ is shown in Algorithm 1.

Algorithm 1: Pseudocode to calculate the complete coverage width $d_1$

1: Set EO static view field $\epsilon$, set $d_{\max }^{ShB}$ according to the target characteristics, weather condition and EO resolution;

2: Calculate $R_1$, $R_2$ according to Formulae (10) and (11), respectively;

3: Calculate the time of a scanning cycle T;

4: For $x_{B1}$ = $-R_2\sin {\theta }_1$ to 0 do

5:  Calculate $y_{B1}$ according to Formula (18);

6:  Set $x_{O_3{B}_3}=x_{B1}$, calculate $y_{O_3{B}_3}$ according to Formula (21);

7:  If $y_{O_3{B}_3}$ = $y_{B1}$

8:    Save $d_1=2\left|x_{B1}\right|$;

9:    Break out of the loop;

10:   End if

11: End for

For any set $\left(V,h,{\theta }_1,\omega \right)$ in the IA population, with a complete coverage width $d_1$, the $J$ index can be generated based on Equation (45), which can be used as the fitness of the set.

It is also necessary to judge whether the set conforms to the speed-to-height constraint and the no-interval missing constraint. If not, the $J$ index of the set is 0. The pseudocode is presented in Algorithm 2.

Algorithm 2: Pseudocode to judge whether a parameter set conforms to the speed-to-height constraint and the no interval missing constraint

1: Set speed to height ratio $\gamma$;

2: Calculate ${\mu }_1$, ${\mu }_2$ according to Formulae (1) and (5);

3: Calculate the value of formula $V\cdot \sqrt{1-{\left(\cos {\theta }_1\cdot \sin {\mu }_1\right)}^2}\cdot \cos {\mu }_1/h$;

4: If $V\cdot \sqrt{1-{\left(\cos {\theta }_1\cdot \sin {\mu }_1\right)}^2}\cdot \cos {\mu }_1/h$>$\gamma$

5:  Set $J=0$;

6: End if

7: Calculate $R_1$, $R_2$ according to Formulae (10) and (11) respectively;

8: For $x_{C2}$=$-R_1\sin {\theta }_1$ to $R_1\sin \left({\theta }_1-\epsilon \right)$ do

9:  Calculate $y_{C2}$ according to Formula (20);

10:   Calculate $y_{B1}$ according to Formula (18);

11:   If $y_{c2}>y_{B1}$

12:   Set $J=0$;

12:   Break out of the loop;

10:   End if

11: End for

After calculating the $J$ index of all the parameter sets in the population, various evolutionary operations can be performed according to their fitness. The pseudocode of the main task planning algorithm based on IA is shown in Algorithm 3.

Algorithm 3: Pseudocode of the main program of the task planning algorithm

1: Initial parameters of IA, including mutation probability $P_m$, crossover probability $P_c$, update probability $P_u$, population number N, the maximum evolutionary number $Era$. Set static view field $\epsilon$, the minimum pitch angle ${\mu }_{\min }$, the maximum scanning angular velocity ${\omega }_{\max }$, the minimum flight altitude $h_s$, the minimum speed $V_1$, the maximum speed $V_2$, the best cruise speed $V_0$, the best cruise altitude $h_0$. Set the weight coefficients $K_{\eta }$, $K_{\omega }$, $K_{V_0}$ and $K_{h_0}$.

2: Initial coordinates of the area to be searched;

3: According to the parameter threshold ranges expressed by Equations (32)–(38), 50 task parameter sets are randomly generated to form the initial IA antibody population. Each set contains 4 parameters $\left[V,h,{\theta }_1,\omega \right]$;

4: For i = 1 to $Era$ do

5:  Calculate the $J$ index of every set as their fitness based on Algorithm 1 and Formula (45);

6:  Check whether every set meet the speed to height constraint and the no interval missing constraint according to Algorithm 2.

7:  The vector distance concentration of each antibody in the population are calculated based on their fitness, ${\rho }_i=1/{\displaystyle \sum _{j=1}^{49}\left|f_i-f_j\right|}$, and the selection probability of each antibody are calculated based on the vector distance concentration, $P_i={\rho }_i/{\displaystyle \sum _{j=1}^n{\rho }_j}$;

8:  Antibody selection is implemented based on the concentration regulation mechanism of IA, and clonal expansion is implemented based on clonal selection probability $P_s=0.4$;

9:  Each antibody in the clonal amplified population is mutated, the mutation probability $P_m=0.8$, and each parameter of the antibody obtained by mutation should conform to their threshold range limitation.

10:   Determine whether the number of antibodies in the current population reaches 50. If not, randomly produce antibodies to supplement the population to 50.

11: End for

4.2.2. Task Planning Algorithm Based on GWO

GWO achieves optimization by simulating the collaborative mechanism during the hunting process of wolf packs. It has the advantages of simple structure, few adjustment parameters, and easy implementation. Owing to the existence of the adaptive adjustment convergence factor and information feedback mechanism in the GWO algorithm, it can achieve a balance between local optimization and global search and has good performance in solving the problem accurately and in rate of convergence. The pseudocode of the main task planning algorithm based on GWO is shown in Algorithm 4.

Algorithm 4: Pseudocode of the main program of the task planning algorithm based on GWO

1: Initialize the grey wolf population $X_i$ (i = 1, 2, …, 50). According to the parameter threshold ranges expressed by Equations (32)–(38), 50 task parameter sets are randomly generated to form the initial grey wolf population, each grey wolf contains 4 parameters $\left[V,h,{\theta }_1,\omega \right]$;

2: Initialize $a$, $A$, $C$, $t$ = 0; initialize max number of iterations $I_{\max }$;

3: Calculate the $J$ index of each grey wolf as their fitness based on Algorithm 1 and Formula (45); set $X_{\alpha }$ = the best grey wolf, $X_{\beta }$ = the second-best grey wolf, $X_{\delta }$ = the third-best grey wolf.

4: While (t < $I_{\max }$) do

5:  Calculate $a=2-t\cdot \left(2/I_{\max }\right)$;

6:  For i = 1 to 50 do

7:     Calculate the $J$ index of the ith grey wolf $X_i$ as its fitness $f_i$ based on Algorithm 1 and Formula (45);      Update $X_{\alpha }$, $X_{\beta }$, $X_{\delta }$ based on $f_i$, $f_a$, $f_{\beta }$, $f_{\delta }$;

8:  End for

9:  For i = 1 to 50 do

10:    Randomly generated $r_1$, $r_2$, update A and C, $A=2\cdot a\cdot r_1-a$, $C=2\cdot r_2$;

11:    Update $D_{\alpha }=\left|C\cdot X_{\alpha }-X_i\right|$, calculate $X_{D\alpha }=X_{\alpha }-A\cdot D_a$;

12:    Update $D_{\beta }=\left|C\cdot X_{\beta }-X_i\right|$, calculate $X_{D\beta }=X_{\beta }-A\cdot D_{\beta }$;

13:    Update $D_{\delta }=\left|C\cdot X_{\delta }-X_i\right|$, calculate $X_{D\delta }=X_{\delta }-A\cdot D_{\delta }$;

14:    Calculate $X_i=\left(X_{D\alpha }+X_{D\beta }+X_{D\delta }\right)/3$;

15:   End for

16:   $t=t+1$;

17: End while

18: Return $X_{\alpha }$;

4.2.3. Task Planning Algorithm Based on VNS

The basic neighborhood search algorithm is based on the idea of “greedy acquisition.” The algorithm starts from an initial solution, uses the neighborhood structure, and continuously searches for a better solution in the neighborhood. If a better solution can be obtained, the current solution is updated until the termination condition is satisfied. The neighborhood structure of the VNS algorithm is not a single invariant, but there are multiple neighborhood structures, and in the case of the same initial solution, there is a wider and deeper search space. Owing to the different neighborhood structures for alternating search and real-time adjustment of neighborhood structures, a good balance is achieved between centrality and dispersity, the local optimal solution can better leap out, and the approximate optimal solution can be obtained at a faster speed. The variable neighborhood search algorithm mainly consists of two parts: variable neighborhood descent (VND) search and shaking process. The pseudocode of the task planning algorithm based on VNS is shown in Algorithm 5.

Algorithm 5: Pseudocode of the main program of the task planning algorithm based on VNS

1: Set the maximum number of iterations of the outer loop $I_{\max gen}=100$; Initialize a set of neighborhood structures $N_k$, $k=1,2,3$, set the number of cycles for VND $M=50$;

2: According to the parameter threshold ranges expressed by Equations (32)–(38), initial solution $S$ is generated, $S$ contains 4 parameters $\left[V,h,{\theta }_1,\omega \right]$; calculate the $J$ index of $S$ based on Algorithm. 1 and Formula (45) as its fitness $f$;

3: Initialize the best solution $S_{best}=S$, initialize the fitness of $S_{best}$ as $f_{best}=f$;

4: While (t < $I_{\max gen}$) do

5:  For i = 1 to 3 do /* Shaking */

6:     generate a random solution $S^{\prime }$ from the kth neighborhood $N_k\left(S\right)$ of $S$;

7:  End for

8:  Calculate the fitness $f^{\prime }$ of $S^{\prime }$;

9:  For i = 1 to 3 do /* local search by VND */

10:    Set $S_{best}^{″}$ = [], $f_{best}^{″}$ = 0;

11:    For j = 1 to M do

12:     Generate a solution $S^{″}\left(j\right)$ according to $S^{\prime }$ and the rules of the ith neighborhood $N_i$;

13:     Calculate the fitness $f_j^{″}$ of $S^{″}\left(j\right)$;

14:     If $f_j^{″}$ > $f_{best}^{″}$

15:       Update $S_{best}^{″}$ and $f_{best}^{″}$;

16:     End if

17:    End for

18:    If $f_{best}^{″}$>$f^{\prime }$

19:     Update $S^{\prime }$ = $S_{best}^{″}$ and $f^{\prime }$=$f_{best}^{″}$;

20:    End if

21:    If $f_{best}^{″}$ > $f_{best}$

22:     i = 1, continue to search within $N_i$; update $S_{best}$ = $S_{best}^{″}$ and $f_{best}$ = $f_{best}^{″}$;

23:    Else

24:     i = i + 1;

25:    End if

26:   End for

27: End while

28: Return $S_{best}$;

5. Simulation and Discussion

In this section we describe the simulation performed to comprehensively evaluate the effectiveness of the models and algorithm.

First, we set the parameter threshold and value range. The maximum recognition distance $\epsilon =20°$; maximum recognition distance $d_{ShB}=10 km$; minimum pitch angle ${\mu }_{\min }=15°$; maximum scanning angular velocity ${\omega }_{\max }=8°/s$; minimum flight altitude $h_s=200 m$; and maximum flying altitude can be obtained by Equation (37) as $h_{\max }=8191.5 m$; minimum speed $V_1=100 km/h$; maximum speed $V_2=300 km/h$; and speed-to-height ratio threshold $\gamma =0.08 rad/s$. Best cruise speed $V_0=220 km/h$ and best cruise altitude $h_0=2800 m$.

5.1. Search Range and Full Coverage Width Simulation

First, six sets of task parameters were set based on experience, and simulations were performed based on the coverage area model established above. The results are shown in Figure 6 and

Table 1. Six sets of task parameters and their corresponding coverage width and coverage efficiency.

Serial Number	V (m/s)	h (m)	${\mathit{\theta }}_1$ (°)	$\mathit{\omega }$ (°/s)	${\mathit{d}}_1$ (m)	$\mathit{\eta }$ (m2/s)
(a)	80	3500	75	2	5822.3	465,784
(b)	70	2500	60	3	11,968.2	837,774
(c)	60	2000	80	3	14,979.7	898,782
(d)	83	3000	80	4	14,161.5	1,175,406
(e)	83	1500	85	2.5	9877.3	819,816
(f)	83	5000	85	2.5	7105.5	589,757

.

The static view field, based on the first set of parameters, is shown as $A_1{B}_1{C}_1{D}_1$ in Figure 6a. It moves around the position of the aircraft and uses the flight direction as the symmetrical axis to create a uniform sector-scanning motion. If the task parameters do not change, then the area remains the same during the search process. Trajectory $B_1{B}_2$ is the motion trajectory of the point $B_1$ in half a period, and the other trajectories are the same.

The maximum coverage width that could be obtained, based on the third set of parameters, was 14,979.7 m. The simulation results are shown in Figure 6c, but the search efficiency was not high. Although the coverage width of the fourth set of parameters was not the maximum, the maximum coverage efficiency obtained was 1175, 405 m²/s, as shown in Figure 6d. From Figure 6a,f, it can be seen that the first and sixth sets of parameters did not meet the limit conditions of complete coverage, and there was a missing area between the two round-trip scans. Therefore, relying on experience to set task parameters is not satisfactory, as there may be missing areas, and it is also difficult to obtain high coverage efficiency.

5.2. Analysis of the Changes of J

In the actual task process, not only is high search efficiency required, but many other factors must also be considered. The task planning simulation was performed according to the comprehensive optimization index J established by Equation (45). Set $K_{\eta }=100$, $K_{\omega }=10$, $K_{V_0}=K_{h_0}=1$.

Next, when the other parameters were fixed, we observed the changes in the comprehensive optimization index J with two different parameters.

As shown in Figure 7, with search azimuth θ₁ = 85° and scanning search angular velocity ω = 3°/s, J changed with V and h. It can be observed that the corresponding relationship was a curved surface. When V was large and h was high, there was a large restricted area and the parameters in this area did not meet the condition of complete coverage. When V was large and h was low, there was a small restricted area.

As shown in Figure 8, when V = 80 m/s and h = 3500 m, J changed with θ₁ and ω. It can be seen that the corresponding relationship was also a curved surface. When ω was small and θ₁ was large, there was a larger restricted area, and the parameters in this area did not satisfy the conditions of a complete coverage search.

When V and ω were unchanged, J changed with h and θ₁, shown in Figure 9. When h and ω remained unchanged, the changes in J with V and θ₁ are shown in Figure 10. In both cases, it can be seen that there were restricted areas and non-linear mutations.

From Figure 7, Figure 8, Figure 9 and Figure 10, it can be observed that there was no specific proportional relationship between J and a certain group of task parameters. Owing to many constraints, there was a non-linear mutation relationship, so it was difficult to solve such problems based on traditional analytical methods. Task parameter optimization was performed, based on IA, GWO, and VNS.

5.3. Task Planning Simulation Based on IA, GWO and VNS

The IA evolutionary algebra Era = 100 was set, and 10 rounds of task parameter planning were conducted. The results are presented in

Table 2. Ten rounds of planning results based on the IA.

Serial Number	V (m/s)	h (m)	${\mathit{\theta }}_1$ (°)	$\mathit{\omega }$ (°/s)	${\mathit{d}}_1$ (m)	$\mathit{\eta }$ (m2/s)	$\mathit{J}$	${\mathit{T}}_{\mathit{I}\mathit{A}}$ (s)
1	83.30	432.85	89.68	7.26	19.36	1.61	183.84	47.66
2	83.33	398.33	89.99	7.29	18.77	1.56	178.03	57.31
3	83.32	418.92	89.98	7.07	18.71	1.56	177.72	51.14
4	83.33	418.06	89.99	7.26	18.76	1.56	177.96	53.22
5	83.33	409.00	89.98	7.85	18.95	1.58	179.12	60.77
6	83.33	442.65	90.00	7.56	18.87	1.57	178.67	47.48
7	83.21	400.91	89.94	7.70	18.97	1.58	179.23	54.05
8	83.29	429.07	89.99	8.00	19.01	1.58	179.41	45.22
9	83.33	396.68	89.99	8.00	19.01	1.58	179.52	44.14
10	83.33	407.84	89.99	7.48	18.83	1.57	178.37	42.70

.

The maximum iterations of GWO were set as $I_{\max }=400$, and the running time of the GWO algorithm was similar to the 100 generations evolution time of the IA. Similarly, we set the maximum number of iterations of the VNS to ${I^{\prime }}_{\max }=500$. Tenrounds of task parameter planning were conducted, based on the GWO and VNS algorithms. The results are presented in

Table 3. Ten rounds of planning results based on the GWO.

Serial Number	V (m/s)	h (m)	${\mathit{\theta }}_1$ (°)	$\mathit{\omega }$ (°/s)	${\mathit{d}}_1$ (m)	$\mathit{\eta }$ (m2/s)	$\mathit{J}$	${\mathit{T}}_{\mathit{I}\mathit{A}}$ (s)
1	83.22	974.90	87.59	7.86	19.27	1.60	182.07	58.06
2	83.32	630.72	89.83	7.98	18.94	1.58	178.81	45.86
3	83.33	709.02	89.98	7.88	18.90	1.58	178.65	53.97
4	83.33	1017.45	89.97	7.97	18.87	1.57	178.22	68.81
5	83.29	535.72	89.28	7.92	18.96	1.58	179.02	46.38
6	83.32	507.00	90.00	7.97	18.95	1.58	178.99	45.12
7	83.32	675.99	89.97	7.93	18.92	1.58	178.72	44.57
8	83.33	455.82	89.84	7.98	18.95	1.58	178.95	38.47
9	83.32	744.37	89.99	7.90	18.90	1.58	178.62	61.12
10	83.33	487.38	89.97	7.98	18.95	1.58	179.02	37.62

and

Table 4. Ten rounds of planning results based on the VNS.

Serial Number	V (m/s)	h (m)	${\mathit{\theta }}_1$ (°)	$\mathit{\omega }$ (°/s)	${\mathit{d}}_1$ (m)	$\mathit{\eta }$ (m2/s)	$\mathit{J}$	${\mathit{T}}_{\mathit{I}\mathit{A}}$ (s)
1	83.01	575.38	89.37	7.50	18.77	1.56	177.07	42.07
2	83.31	1654.54	89.35	7.96	18.63	1.55	175.93	46.29
3	83.21	400.86	89.50	7.48	18.79	1.56	177.71	38.82
4	82.64	474.15	89.03	7.22	18.67	1.54	175.62	40.13
5	83.28	1437.23	89.99	7.61	18.66	1.55	176.58	37.40
6	83.23	582.76	87.29	7.72	18.64	1.55	175.98	37.24
7	83.23	589.85	89.66	7.92	18.90	1.57	178.37	42.71
8	83.20	463.49	89.99	7.53	18.84	1.57	178.15	40.09
9	82.63	1041.88	88.47	7.91	18.74	1.55	175.41	37.88
10	83.26	1331.90	89.06	7.80	18.67	1.55	176.35	41.46

, respectively.

The change curves of fitness of 10 rounds of IA optimization are shown in Figure 11, the change curves of fitness of 10 rounds of GWO optimization are shown in Figure 12 and the curves of VNS are shown in Figure 13.

It can be seen from the simulation results that IA, GWO, and VNS obtained excellent task parameter sets, had high search efficiencies and comprehensive indices, and met the no-interval missing scan and speed-to-height ratio constraints. However, there were some differences in the results. Next, the differences in the parameter planning results of the three algorithms were compared and analyzed.

As shown in Figure 14, the optimal J index, average J index, and average time cost of the three algorithms were compared.

As shown in Figure 14, the planning results obtained by the three algorithms exhibited little difference in index J. However, in comparison, the results obtained based on IA were slightly better than those of the other two algorithms in terms of J. The optimal J index in the 10 rounds based on IA was 183.84, and the optimal J index in regard to GWO and VNS were 182.07 and 178.37, respectively. From the average $\overline{J}$, the average $\overline{J}$ based on IA was 179.19, the average $\overline{J}$ based on GWO was 179.11, which was almost the same as that for IA, and the average $\overline{J}$ based on VNS was 176.72, which was significantly worse than those for IA and GWO. This showed that IA had a higher convergence accuracy when solving such problems, GWO was second, and VNS convergence accuracy was the lowest.

The J index change curves are shown in order to compare the convergence speeds of the three algorithms, and are given in Figure 15. At the same time, to make the image easy to observe and not too crowded, only the J index change curve of the optimal round of each algorithm was selected. The selected results were as follows: 1th round of IA, 1th round of GWO and 7th round of VNS. In addition, because IA had 100 evolution times, GWO 400 cycles, and VNS 500 cycles, the quantities of data are different, so the curves of IA and GWO are “stretched” to facilitate comparison.

As can be seen from Figure 16, in IA, the fitness of the optimal solution increased steadily, the change curve was relatively gentle, and there was “step” improvement during the operation, which indicated that the IA jumped out of the local optimal and converged in a position of relatively high precision. At the early stage of GWO, the fitness of the optimal solution ($\alpha$-wolf) increased rapidly, surpassing that of IA. In the subsequent process, the phenomenon of “step” improvement was constantly produced, which indicated that the GWO constantly jumped out of the local solution and converged to a relatively optimal position (slightly worse than IA). At the early stage of VNS, the fitness of the optimal solution increased the fastest, surpassing that of the IA and GWO algorithms. However, the optimization process then stagnated. This showed that VNS had the best optimization efficiency in the early stage, but the global optimization ability was relatively weak, and it was suitable for questions with high real-time requirements.

The optimization results were further analyzed. To facilitate the observation, the ten groups of planning results obtained by the three algorithms are presented in the form of bar charts in Figure 15, Figure 17 and Figure 18. It can be seen from the bar chart comparisons that the results obtained by the three algorithms tended to be consistent in each round for speed $V$ and sector scanning Angle $\theta$. In terms of flight height $h$, the results based on VNS were the most different, followed by GWO and IA. However, even the planning results of IA showed the largest difference in flight altitude $h$ compared to other mission parameters, such as flight speed $V$. With respect to sector scanning angular velocity $\omega$, the difference in planning results based on GWO was the smallest, and the difference between IA and VNS was relatively large. Overall, IA had the most stable planning results, followed by GWO and VNS.

Furthermore, the changing process of the task parameters under a typical optimization process was compared. Similarly, to make the image less crowded, only the change curves of typical processes were selected for observation and comparison. The selection principle was that the J index was the best or the J index was the closest to the average. The selection results of IA were as follows: the 1th round and the 3th round; GWO selection results were: the 1th round and the 4th round; VNS selection results were: the 7th round and the 9th round.

The speed change curves of the typical rounds are shown in Figure 19. It can be seen that among the three optimization algorithms, the overall trend of speed was increasing, which reflected the positive significance of increasing speed for improving J index. The optimization efficiency of VNS was the highest, followed by GWO, with IA the slowest. Both GWO and IA exhibited oscillations in the early stage of operation, which reflected the complexity of the problem.

The change curves of h, $\theta$, and $\omega$ are shown in Figure 20, Figure 21 and Figure 22. It can be seen that the change trend of height h in all three algorithms was downward overall, and the change trends of $\theta$ and $\omega$ were both increasing.

However, the optimization processes of the different algorithms exhibited significant differences. Basically, the optimization processes of VNS were the fastest, and sub-optimal solutions soon found, as shown in “7th-VNS” and “9th-VNS” in Figure 19, Figure 20, Figure 21 and Figure 22, while the subsequent processes were basically stable and unchanged. The GWO optimization process was also fast; however, the subsequent optimization processes entered a state of oscillation, as shown in “1th-GWO” and “4th-GWO” in Figure 19, Figure 20, Figure 21 and Figure 22. In the IA process, the variation curves of the parameters were relatively stable and gentle. This difference reflected the algorithmic characteristics of the three methods.

The change curves of coverage width d₁ are shown in Figure 23. As d₁ was the main component of J and its weight was much greater than that of the other indices, the trend of d₁ was basically consistent with J.

5.4. Comparison of Area Coverage under Different Parameter Sets

The scanning trajectory based on typical optimization results are shown in Figure 24. It can be seen that the optimized coverage widths were generally large and met all the constraints.

To demonstrate the advantages of the optimized task parameters, a coverage search was implemented based on different parameter sets. It was supposed that there was an area of 160 km × 80 km that had to be covered.

Test (a): Test (a) referred to the optimized task parameters using IA, and the 1th round planning results selected as an exampl.

Test (b): Test (b) referred to the optimized task parameters using GWO, and the 1th round planning results selected as an example.

Test (c): Test (c) referred to the optimized task parameters using VNS, and the 7th round planning results selected as an example.

Test (d): Test (d) referred to the parameters selected by experience, and the 4th group of parameters in Table 1 was selected as an example.

Test (e): The other task parameters were the same as in test (d), but the coverage width was determined according to the traditional method $d_1=2R_1\cdot \sin {\theta }_1$, and the interval missing was not considered.

A common boustrophedon coverage method was adopted for the search track. The turning process, wherein the UAV completed a line scan and turned around, is shown in Figure 25. Assuming that the turning overload of the aircraft was 30 m/s², the starting position of each scanning line (e.g., p_turn) was 5 km from the edge of the area to be searched.

The coverage results of the area are shown in Figure 26a–e. Defining the miss ratio $P_{missed}$ = $S_{missed}$/$S_{all}$, $S_{missed}$ as the area missed in the coverage search, and $S_{all}$ as the total area. The time consumption and $P_{missed}$ of the five tests were calculated, and the results are presented in

Table 5. Comparison of main indices of three simulation tests.

	Test (a)	Test (b)	Test (c)	Test (d)	Test (e)
Coverage width d1 (m)	18,731	18,643	18,904	11,968	19,071
Number of scanning lines	9	9	9	14	9
Time to complete coverage (s)	10,742	10,858	10,761	19,328	11,331
Miss ratio Pmissed	0%	0%	0%	0%	13.96%

.

Compared with Test (e), the simulation results of Tests (a)–(c) showed that the coverage width model could achieve complete coverage of the target area without missing data. However, if the task parameters were simply determined by the traditional method, without considering miss scanning, the miss ratio $P_{missed}$ could be as high as 13.96% (Test (e)) indicated that the model and algorithm in this study are effective and necessary.

By comparing the results of Tests (a) and (d), it can be seen that both sets ensured no missed coverage. However, the empirical parameters cost 19,328 s to complete coverage, while the planned parameters had a shorter time consumption of 10,742 s, which was only 55.58% of the time cost of Test (d). Tests (b) and (c) were similar to test (a) and they were also significantly better than test (d). Therefore, the planned parameters had better coverage efficiency, and the algorithm designed in this study is effective and feasible.

By comparing the results of tests (a), (b), and (c), it was observed that the task parameters planned, based on IA, GWO, and VNS, could achieve an efficient search process without missing areas. When covering the area set in this study, there were no significant differences among the three sets of planning parameters. For example, the task completion times were 10,742 s (IA), 10,858 s (GWO), and 10,761 s (VNS). The planning result of IA was only slightly superior in terms of completion speed, 116 s faster than GWO and 19 s faster than VNS. This may not result in a significant difference in an actual mission. Therefore, all three algorithms are feasible. For offline task planning, IA and GWO could be the appropriate choices for time-efficient online task planning, while VNS and GWO could be the appropriate choices for online and real-time task parameter planning.

6. Conclusions

Automated target search and rescue must ensure complete coverage of an area. In this study, we conducted an in-depth study on task parameter planning when UAVs use EO equipment to cover areas in the sector scanning mode.

A model for the complete coverage width under sector scanning mode was established, and a model with no interval missing constraint and speed-to-height ratio constraint was also established. The test results indicated that the models were effective and reliable.

Although task planning is a serious nonlinear problem, the algorithm designed, based on IA, GWO, and VNS, can effectively solve task planning problems. The coverage process, based on optimized parameters, meets all constraints, has a higher search efficiency, and does not miss areas. Although all three optimization methods are feasible, they exhibit some differences. In general, IA is more suitable for offline occasions, VNS is more suitable for online real-time planning, and GWO has characteristics between the two.

The coverage task planning algorithm in this study can not only realize no-omission coverage but also consider the problem of target recognition, which provides technical support for fully automated target search and rescue.