Data Collection Task Planning of a Fixed-Wing Unmanned Aerial Vehicle in Forest Fire Monitoring

This article studies the data collection task planning for a fixed-wing unmanned aerial vehicle (UAV) in forest fire monitoring. Multiple wireless-based detection nodes (DNs) are distributed in high-risk areas of the forest to monitor the surrounding environment. The task of UAV is to circularly fly to them and collect the environmental data. Because of the kinematic constraints of UAV and the effective communication range between UAV and DN, this problem can be generally regarded as a Dubins traveling salesman problem with neighborhood (DTSPN). A bi-level hybridization-based metaheuristic algorithm (BLHMA) is proposed for solving this problem. At the first level, differential evolution (DE) optimizes the continuous-valued communication positions and UAV headings by the population-based search. For the asymmetric traveling salesman problem (ATSP) corresponding to the combination of the positions and headings generated by DE, a constructive heuristic based on self-organized multi-agent competition (SOMAC) is proposed to determine the discrete collection sequence. By competitive iterations in such a cooperative way in DE, a high-quality data collection tour can be generated. At the second level, a local search based on multistage approximate gradient is proposed to further refine the positions and headings, which accelerates the convergence of the BLHMA. Referring to a real-world scene of forest fire monitoring, the simulation experiments are designed, and comparative results show that BLHMA can find significantly shorter data collection tours in most cases over three state-of-the-art algorithms. The proposed UAV data collection planning algorithm is conducive to the efficient execution of the forest fire monitoring data collection mission and the energy saving of UAV.

SECTION I. Introduction

Forest fire is one of the most destructive disasters to the ecological environment, and the forest fire protection is receiving more and more attention from the governments of the world [1]. Thus, it is very meaningful to carry out prevention and control of the forest fire, and how to make use of high-tech means to monitor forest fire has become a hot topic [2], [3].

At present, there are mainly two kinds of high-tech means for forest fire monitoring. The first high-tech means are based on the unmanned aerial vehicle (UAV) surveillance. It is easier for a fixed-wing UAV to get a large range of ground information because of its top-view and high mobility [4], [5]. It has been increasingly applied in monitoring missions, which can be regarded as curvature-constrained path planning problems. In some research, the path planning of UAV is simplified as the traveling salesman problem (TSP) [6]–​[10]. However, it is very important to consider the kinematic constraints from the practical aspects, and the Dubins vehicle model is usually used to approximate the dynamic model of UAV [11]–​[14]. In the path planning, a UAV circularly collects images above the forest and detects the fire source through image analysis [15]–​[18]. The second high-tech means are based on wireless sensor network (WSN). Multiple wireless sensors are distributed in the forest and form a monitoring network [19]. These sensors continuously monitor the surrounding environment and collect environmental data to achieve forest fire monitoring.

Both means have advantages and disadvantages. For the UAV-based means, a UAV can quickly obtain a large range of ground information, but its monitoring effectiveness is greatly affected by the image quality, which is easily affected by weather factors, such as dust, fog, etc. In addition, in the early stage of the forest fire, the fire is so small that there is no obvious burning phenomenon, so it is difficult to monitor the fire at a high altitude. For the WSN-based means, WSN can quickly detect the possible fire area in the early stage of the fire by monitoring the temperature, humidity, and harmful gases. But in the deep forest of the mountainous area, the transmission signal may be very poor, and a large number of sensors need to be arranged to cover the forest. This will bring great economic costs and maintenance difficulties.

This paper combines the advantages of the two means. Multiple wireless-based, low-power, and self-sustaining detection nodes (DNs) are distributed in high-risk areas of the forest to perceive the surrounding environment and record environmental data. Because of their poor signal transmission condition in the mountain forest, they have limited communication capability and can only perform short-range communication. Thus, a small, low-altitude, and low-cost fixed-wing UAV which is equipped with a transceiver device is adopted to circularly collect the latest data of DNs, as shown in Fig. 1.

FIGURE 1.

UAV data collection task in forest fire monitoring.

At the beginning of the forest fire monitoring, the command center will plan a data collection tour for the UAV, and command the UAV to circularly collect the latest data from all DNs to obtain the information of monitoring areas. When the UAV arrives at the planned collection position of each DN, it sends an application to the DN to receive the latest data. After receiving the application, the DN sends the data to the UAV. Then the UAV transmits the data back to the command center, and flies to the next planned collection position.

In this sense, UAV needs to enter the communication range of each DN with an appropriate sequence to collect data, and its flight path is constrained by curvature, so the data collection task planning for a UAV in forest fire monitoring can be generally formulated as a Dubins traveling salesman problem with neighborhood (DTSPN) [20], [21].

A. Related Work

As mentioned above, the UAV data collection task planning in forest fire monitoring is formulated as a DTSPN which can be regarded as a generalized variant of the classic TSP. In addition, there are two other generalized variants of TSP. On one hand, if the traveling salesman in TSP becomes a mobile agent which can be treated as a Dubins vehicle, the resulting TSP variant is called Dubins TSP (DTSP) [22], [23]. In the DTSP, the distance between two neighboring targets to be visited is not Euclidean distance. It should be measured by the Dubins paths which rely not only on the visiting positions but also on the headings of the vehicle at the positions [12]. On the other hand, if the targets to be visited are extended from points to regions, TSP will be transformed into its well-known variant, named the traveling salesman problem with neighborhood (TSPN) [24]–​[26]. DTSPN shares the characteristics of DTSP and TSPN, and also inherits their difficulties.

Similar to DTSP and TSPN, the DTSPN is also an NP-hard optimization problem with mixed variables [27], [28]. Solving the DTSPN involves optimizing the discrete collection sequence, the continuous communication positions, and the UAV headings simultaneously, which makes it more challenging.

The existing methods for solving this class of problems can be mainly grouped into four categories: decoupling methods, transformation methods, unsupervised learning methods, and direct search methods. In the decoupling methods, mixed variables are optimized separately [11], [22], [28]–​[31]. To some extent, the decoupling method reduces the difficulty of solving the problem. However, the effectiveness of decoupling methods mainly relies on the similarity between problems, which makes them unsuitable for the situations where the Euclidean distance between two points is obviously shorter than the minimal turning radius of UAV when solving DTSP and DTSPN [32]. In the transformation methods, positions and headings are uniformly sampled to construct the generalized traveling salesman problem (GTSP) firstly, and then the GTSP is converted into an asymmetric traveling salesman problem (ATSP) by the Noon-Bean transformation [33]–​[37]. The transformation method can obtain a global optimum when taking a large number of samples, but it greatly increases the amount of calculations. Decoupling methods and transformation methods share the similarity that an efficient TSP solver like the LKH can be used to provide a high-quality solution [38]. In the unsupervised learning methods, the solution of the sequencing part of the problem is combined with the online sampling of the suitable positions and headings [39], [40]. The unsupervised learning method can be regarded as a kind of constructive algorithm, which can find a solution with high efficiency. However, the initialization and competition of neurons have a great influence on the solution in different cases. In the direct search methods, the mixed variables are optimized simultaneously and many optimization algorithms can be used as search engine [26], [32], [41]–​[46]. In this method, the model has no sacrifice in accuracy, but the solution space is complex, which makes it difficult to find the optimal solution.

Many scholars devote themselves to the research of the DTSPN. Obermeyer proposed a genetic algorithm (GA) that uses a hybrid encoding scheme for mixed variables [20]. In addition, the authors also proposed the other two methods to solve a polygon visiting Dubins traveling salesman problem (PVDTSP), and both of them belong to the transformation method [36], [37]. Under certain technical assumptions, the algorithms are resolution-complete, and can converge to a global optimum as the number of samples grows but consumes more computing time. Macharet proposed a three-stage evolutionary method that optimizes mixed variables independently [44]. The authors also proposed a heuristic method for optimizing visiting positions within the target’s neighborhood and connecting them with Dubins paths [47], [48]. Pěnička proposed a variable neighborhood search (VNS) algorithm for solving the Dubins Orienteering Problem with Neighborhoods (DOPN), which can be regarded as a variant of the DTSPN [45]. A set of neighborhood operators are designed to perform a well combinatorial optimization. Zhang proposed a memetic algorithm in which a relaxed DTSPN model is used to obtain an approximated optimal solution, and a local search based on an approximated gradient is adopted to improve the quality of the solution [32].

B. Main Contributions

In view of two typical high-tech means in forest fire monitoring, this paper combines their advantages, and regards the UAV data collection task in forest fire monitoring as a DTSPN. Because the DTSPN is a mixed-variable optimization problem with extremely complex solution space, this paper deliberates the algorithm design to reduce the complexity of problem solving, and makes the following innovations and contributions:

1. In the proposed bi-level hybridization-based metaheuristic algorithm (BLHMA), differential evolution (DE) is adopted to evolve a group of continuous communication positions and UAV headings which are metaphorize as multiple individuals. Besides, a constructive heuristic based on self-organized multi-agent competition (SOMAC) is proposed to generate the discrete collection sequence by solving an asymmetric traveling salesman problem (ATSP) corresponding to the combination of the positions and headings generated by DE. In such a cooperative way, a data collection tour can be generated. Because SOMAC is a deterministic constructive heuristic, it avoids a large amount of blind search in the mixed-variable space and leads to better convergence. Compared with the transformation method [36], the huge amount of computation caused by a large number of samplings is avoided.

2. A local search based on a multistage approximate gradient is developed to improve the communication positions and UAV headings during the iteration of DE, which can lead to a better trade-off between exploration and exploitation in the solution space. Compared with the strategy proposed in the literature which does not optimize UAV headings [32], the proposed local search can achieve precise adjustment of the communication positions and UAV headings. This is helpful to accelerate the convergence of the BLHMA.

3. This paper provides an effective method for the UAV data collection task planning in forest fire monitoring, which is conducive to the efficient execution of the task and the energy saving of UAV.

This papaer organized as follows. Section II presents the formulation of the UAV data collection task planning. Section III gives a detailed description of the proposed algorithm. Section IV evaluates the proposed algorithm through a series of computational experiments and analyses. Section V concludes the paper.

SECTION II. Problem Formulation

In this paper, it is assumed that multiple wireless-based, low-power, and self-sustaining DNs are deployed in high-risk areas of the forest. Because of their poor signal transmission condition in the mountain forest, DNs can only perform short-range communication. Each DN can continuously monitor the temperature, humidity, and harmful gas of the surrounding environment, and record environmental data. Then, a fixed-wing UAV circularly inspects each DN to obtain the monitoring data.

In this situation, neighborhoods of DNs should be defined to fit the effective communication range between UAV and the DN. For the sake of clarity, the neighborhood of each DN is specified as a disk centered at the DN. For the UAV, the Dubins vehicle model is used to approximate its kinematic model [12], and the model is described as follows:\begin{align*} \begin{cases} \displaystyle \dot {x} = \upsilon \cdot \text {cos} \theta,\\ \displaystyle \dot {y} = \upsilon \cdot \text {sin} \theta,\\ \displaystyle \dot {\theta } = \frac {\upsilon }{r} \cdot u, u\in \{-1,0,1\}. \\ \displaystyle \end{cases}\tag{1}\end{align*} where $[x,y]$ and $\theta $ are the planar coordinates and the heading of the Dubins vehicle, respectively; $[x,y,\theta]$ is called Dubins state; $\upsilon $ and $r$ represent the speed and the minimum turning radius of the Dubins vehicle, respectively; $u$ denotes the control input that controls the movement direction of the Dubins vehicle.

Based on the model, Dubins gave an important conclusion that there are at most six possible shortest paths for any transition from one Dubins state to another [12], as shown in Fig. 2.

FIGURE 2.

The six possible shortest Dubins paths.

Based on the above description, the optimization model of the UAV data collection task planning is shown as (2). Detailed descriptions of parameters and variables used in the model are shown in Table 1.\begin{equation*} min ~J(\mathbf {S},\mathbf {Y})=\sum _{i=1}^{n-1} d(Y_{s_{i}},Y_{s_{i+1}})+d(Y_{s_{n}},Y_{s_{1}})\tag{2}\end{equation*}

TABLE 1 Parameters in the Formulation of the UAV Data Collection Task Planning

By using the boundary-based encoding scheme [32], a Dubins state can be further simplified from $[x_{i},y_{i},\theta _{i}]$ to $[\varphi _{i},\theta _{i}]$ , $\varphi _{i}$ and $[x_{i},y_{i}]$ can be calculated from each other through coordinate transformation, as shown as follow:\begin{align*} x_{i}=&c_{x_{i}}+R\cdot \text {cos} \varphi _{i} \\ y_{i}=&c_{y_{i}}+R\cdot \text {sin} \varphi _{i}\tag{3}\end{align*} where $[c_{x_{i}},c_{y_{i}}]$ is the position of the $i^{th}$ DN, and $R$ is the radius of its neighborhood.

In this way, the optimization scale is effectively reduced from $4n$ to $3n$ . However, mixed-variable optimization with a scale of $3n$ is still a great challenge.

Remark 1:

In order to simulate the UAV data collection planning in forest fire monitoring with different scales and scenarios, instances with different minimum distance constraints $D_{K}$ are considered in this paper [49], including $D_{4}$ and $D_{1}$ -constraint instances, and more intensive ones with overlapping situations, denoted by $D^{*}$ . In $D_{4}$ -constraint instances, the distribution of high-risk areas is relatively sparse, and all DNs are far apart. In $D_{1}$ -constraint instances and $D^{*}$ -constraint instances, the distribution of high-risk areas is relatively dense, and DNs are relatively close. The definition of the minimum distance constraint is that: for all $i,j\in \{1,2,\cdots,n\}$ , $i \ne j$ , $\forall p_{i} \in \Omega _{i}$ , $\forall p_{j} \in \Omega _{j}$ , and $\lVert p_{i}-p_{j} \rVert > K \cdot r$ , where $r$ is the minimum turning radius of UAV. The bigger the value of $K$ is, the closer the UAV data collection planning problem is to the common ATSP. In this sense, the decoupling strategy is more suitable for instances in which DNs are far away from each other. On the contrary, it is not suitable for instances with dense DNs distribution.

SECTION III. Bi-Level Hybridization-Based Metaheuristic Algorithm

In this section, a bi-level hybridization-based metaheuristic algorithm (BLHMA) is proposed to solve the UAV data collection task planning in forest fire monitoring. An outline of the BLHMA is illustrated in Fig. 3. First of all, only the communication positions and UAV headings are encoded to form multiple individuals in the initialization of DE. By using the information of an individual, including communication positions and UAV headings, a Dubins distance matrix that represents Dubins distances between all DNs can be calculated to form an ATSP. While the ATSP is addressed by SOMAC to obtain the collection sequence. Then a data collection tour is obtained by introducing the collection sequence, communication positions, and UAV headings into (2). With the iteration of the BLHMA, communication positions and UAV headings are constantly updated in the process of DE, and new ATSPs are constantly constructed and handled, which leads to new data collection tours. Then, a high-quality data collection tour can be obtained by the way of iterative competition.

FIGURE 3.

The outline of the BLHMA.

Moreover, to achieve a desirable trade-off between exploration and exploitation of the algorithm, a modified local search based on the previous work [32] is integrated after the selection operator of DE, which includes three stages: the full-dimensional and local-dimensional approximate gradient descents, and the diversification mechanism. As mentioned above, the so-called BLHMA is constructed, and the details are described as follows.

A. The Optimization of Communication Positions and UAV Headings by Differential Evolution

In this paper, DE is used to optimize communication positions and UAV headings, and the following gives a detailed introduction from the aspects of the encoding, decoding, mutation, crossover, and selection.

Remark 2:

Generally, GA is good at dealing with discrete search domain. DE is an efficient and effective global optimizer in the continuous search domain, and its variants also have excellent performance [50]. Compared with classical population-based optimizers, such as GA, particle swarm optimization (PSO), etc., DE has outstanding performance in many studies [51], [52]. Besides, DE and its variants also have been applied to the international contest on evolutionary optimization (ICEO) many times, and they all have excellent performance.

1) Encoding and Decoding

Because when UAV flies to a DN to collect data, it must pass through the boundary of the DN’s neighborhood, so only the communication positions and headings of the UAV at each DN’s neighborhood need to be determined. Based on the boundary-based encoding scheme described in Fig. 4, any position and heading on the boundary can be expressed by the polar angle, and the coordinates of the communication position can be transformed by using (3).

FIGURE 4.

Schematic of the encoding scheme.

Based on the encoding scheme, an individual can be described as (4), a population is formed by randomly generating multiple individuals.\begin{equation*} \mathbf {x}_{i}=[\varphi _{i}^{1},\varphi _{i}^{2},\cdots,\varphi _{i}^{n},\theta _{i}^{1},\theta _{i}^{2},\cdots,\theta _{i}^{n}]\tag{4}\end{equation*} where $i=1,2,\cdots,NP$ , and $NP$ is the population size. $\varphi $ and $\theta $ represents the encoding of the communication positions and UAV headings respectively, and they are generated randomly in the range of $[0,2\pi)$ .

As for the decoding, in addition to communication positions and UAV headings, the collection sequence is also needed, and all of them form a solution, as (5) shows. Take them together into (2) to obtain the data collection tour and complete the individual evaluation. The next section will introduce how to use SOMAC to get the collection sequence.\begin{align*} SOL_{\mathbf {x}_{i}}= \left \{{ \begin{array}{lr} \mathbf {S}_{\mathbf {x}_{i}}\\[0.5pc] \boldsymbol {\varphi }_{\mathbf {x}_{i}}\\[0.5pc] \boldsymbol {\theta }_{\mathbf {x}_{i}} \end{array} }\right \} = \left \{{ \begin{array}{lr} s_{\mathbf {x}_{i}}^{1},s_{\mathbf {x}_{i}}^{2},\cdots,s_{\mathbf {x}_{i}}^{n}\\[0.5pc] \varphi _{\mathbf {x}_{i}}^{1},\varphi _{\mathbf {x}_{i}}^{2},\cdots,\varphi _{\mathbf {x}_{i}}^{n}\\[0.5pc] \theta _{\mathbf {x}_{i}}^{1},\theta _{\mathbf {x}_{i}}^{2},\cdots,\theta _{\mathbf {x}_{i}}^{n}\\ \end{array} }\right \}\tag{5}\end{align*}

2) Mutation Operator

After the decoding, all individuals have been evaluated. Then DE employs the differential mutation to produce a mutant vector $\mathbf {u}_{i}$ with respect to different individuals in the current population. In this paper, an advanced DE variant, called SADE [50], is adopted, and four kinds of mutation operators are selected.

1. DE / rand / 1 \begin{equation*} \mathbf {u}_{i}=\mathbf {x}_{r1}+F\cdot (\mathbf {x}_{r2}-\mathbf {x}_{r3})\tag{6}\end{equation*}

2. DE / current-to-rand / 1 \begin{equation*} \mathbf {u}_{i}=\mathbf {x}_{i} + F\cdot (\mathbf {x}_{r1}-\mathbf {x}_{i})+F\cdot (\mathbf {x}_{r2}-\mathbf {x}_{r3})\tag{7}\end{equation*}

3. DE / best / 1 \begin{equation*} \mathbf {u}_{i}=\mathbf {x}_{best}+F\cdot (\mathbf {x}_{r1}-\mathbf {x}_{r2})\tag{8}\end{equation*}

4. DE / best / 2 \begin{equation*} \mathbf {u}_{i}=\mathbf {x}_{best}+F\cdot (\mathbf {x}_{r1}-\mathbf {x}_{r2})+F\cdot (\mathbf {x}_{r3}-\mathbf {x}_{r4})\tag{9}\end{equation*}

where $r1, r2, r3$ and $r4$ are mutually exclusive integers that are randomly generated from the set $\{1,2,\cdots,NP\}$ , and all of them are different from $i$ . $F$ is the scaling factor. $x_{best}$ is the best individual found so far.

3) Crossover Operator

After the mutation, a crossover operator, shown as (10), is developed to produce a trial vector $\mathbf {v}_{i}$ .\begin{align*} v_{i,d}= \begin{cases} \displaystyle u_{i,d},~if~rand_{i}^{d} \le CR ~or ~d=rn_{i}\\ \displaystyle x_{i,d},~otherwise\\ \displaystyle \end{cases}\tag{10}\end{align*} where $d=1,2,\cdots,2n$ . $CR$ is the crossover probability, and it is usually set as a fixed value or dynamically adjusted within the interval (0, 1). $rand_{i}^{d}$ is a random number within the interval (0, 1). $rn_{i}$ is a number randomly selected from the set $\{1,2,\cdots,2n\}$ , and it is used for ensuring that $\mathbf {v}_{i}$ and $\mathbf {x}_{i}$ are different.

4) Selection Operator

After the evaluation of the trial individual $\mathbf {v}_{i}$ , the selection operation will be performed. If the data collection tour calculated by the trial individual is not worse than that of the original individual $\mathbf {x}_{i}$ , the original individual will be replaced and the trial individual will survive to the next generation. Otherwise, the original individual will enter the next generation. The selection operation is shown as (11). In addition, the solution also needs to be updated, as shown as (12). It is noted that, the evaluation of the trial individual need the sequence $(\mathbf {S}_{\mathbf {v}_{i}})$ obtained by SOMAC which will be introduced in the next section.\begin{align*} \mathbf {x}_{i}=&\begin{cases} \displaystyle \mathbf {v}_{i},& if~J(\mathbf {S}_{\mathbf {v}_{i}},\mathbf {v}_{i}) \le J(\mathbf {S}_{\mathbf {x}_{i}},\mathbf {x}_{i}) \\ \displaystyle \mathbf {x}_{i},& otherwise\\ \displaystyle \end{cases} \tag{11}\\ SOL_{\mathbf {x}_{i}}=&\begin{cases} \displaystyle SOL_{\mathbf {v}_{i}},~if~J(\mathbf {S}_{\mathbf {v}_{i}},\mathbf {v}_{i}) \le J(\mathbf {S}_{\mathbf {x}_{i}},\mathbf {x}_{i}) \\ \displaystyle SOL_{\mathbf {x}_{i}},~otherwise\\ \displaystyle \end{cases}\tag{12}\end{align*} where $J(\cdot)$ is the objective function of the data collection planning problem, as shown in (2).

B. Collection Sequence Obtained by SOMAC

Solving the collection sequence based on the communication positions and UAV headings generated by DE is essentially an ATSP problem. Black arrows on the boundary of each DN’s neighborhood shown in Fig. 5 represents the communication positions and UAV headings at all DNs. The positions and headings are used to calculate a Dubins distance matrix, as (13) shows, which leads to an ATSP. Then, the ATSP is solved by SOMAC. \begin{align*} \mathbf {D}= \left [{ \begin{array}{ccccc} inf &\quad d_{12} &\quad d_{13} &\quad \cdots &\quad d_{1n}\\ d_{21} &\quad inf &\quad d_{23} &\quad \cdots &\quad d_{2n}\\ \vdots &\quad \vdots &\quad \vdots &\quad \cdots &\quad \vdots \\ d_{n1} &\quad d_{n2} &\quad d_{n3} &\quad \cdots &\quad inf\\ \end{array} }\right]\tag{13}\end{align*} where $d_{ij}=d(Y_{i},Y_{j})$ , $i,j=1,2,\cdots,n$ , $i\ne j$ . $d_{ij}$ is the Dubins distance from the $i^{th}$ DN to $j^{th}$ DN, which is calculated by the positions and headings at the $i^{th}$ DN and $j^{th}$ DN.

FIGURE 5.

Solving the collection sequence based on the communication positions and UAV headings.

For solving the ATSP, a directed graph $G=(V,A)$ is constructed, where $V$ is the vertex set and $A$ is the arc set. The mathematical model of the ATSP is shown as follows [53]:\begin{align*}&\text {min} \sum _{i=1}^{n}\sum _{j=1,j\ne i}^{n}d_{ij}\cdot y_{ij},\tag{14}\\&s.t.~\sum _{i=1,i\ne j}^{n}y_{ij}=1,\quad i=1,2,\cdots,n,\tag{15}\\&\hphantom {s.t.} \sum _{j=1,j\ne i}^{n}y_{ij}=1,\quad j=1,2,\cdots,n,\tag{16}\\&\hphantom {s.t.}\sum _{i\in K}\sum _{j\in K,j\ne i} y_{ij}\le |K|-1,\quad K \varsubsetneqq V,~K \ne \varnothing \qquad \tag{17}\\&\hphantom {s.t.}y_{ij} \in \{0,1\}, \quad i,j=1,2,\cdots,n,i\ne j.\tag{18}\end{align*} where $d_{ij}$ is associated with $arc_{i,j} \in A$ . $y_{ij}$ is equal to 1 if $arc_{i,j}$ is selected. Equations (15)–(16) guarantee that every DN is inspected exactly once. $K$ is a subset of $V$ and (17) makes sure that there is no local loop.

Then, the solution of the data collection planning can be obtained by solving the ATSP. Figure 5 also shows the solution of the simulation scenario of the UAV data collection in forest fire monitoring. The ATSP can be regarded as an inner-loop subproblem embedded in DE for determining the collection sequence. Here, an efficient constructive heuristic is expected to address it, rather than an iterative algorithm with a large amount of computations. Thus, SOMAC is proposed to handle the ATSP.

In SOMAC, the Dubins state of UAV at each DN’s neighborhood shown in Fig. 5 is regarded as an independent agent. Those agents connect with each other through self-organized competition. It is noted that each agent can only connect to other agents once, and it can only be connected once. Because the connection among all agents is simultaneous, it is possible that a certain agent is connected by many other agents. In addition, some agents may connect with each other, which leads to a local loop. A local objective function is designed to eliminate the above conflicts. The details are shown as follows.

1) Initialization of All Agents

Because each agent can only connect to other agents once, and it can only be connected once, an outgoing edge and an incoming edge are defined for each agent. At the beginning, all agents have neither outgoing edges nor incoming edges.

2) Local Objective Function and Selection Operation

Each agent will gather information from other agents, and select the one with the shortest Dubins distance. The local objective function of the connected agent can be denoted as follows:\begin{align*} f_{a_{j}}(C^{j},a_{j})= \begin{cases} \displaystyle inf,& C^{j}=\varnothing \\ \displaystyle d_{c_{q}^{j}a_{j}},& C^{j}\ne \varnothing \end{cases}\tag{19}\end{align*} where $a_{j}$ stands for the $j^{th}$ agent, $C^{j}=\{c_{1}^{j},c_{2}^{j},\cdots,c_{m_{j}}^{j} \}$ is the set of agents that can connect to $a_{j}$ . $m_{j}$ is the number of members in $C^{j}$ . $c_{q}^{j} \in C^{j}$ , $q=1,2,\cdots,m_{j}$ .

In determining $C^{j}$ of $a_{j}$ , three kinds of agents need to be excluded, including itself, the agents with incoming edges, and the agents that can cause a local loop.

3) Conflict Resolution Operation

Because the connection among all agents is simultaneous, a certain agent may be connected by multiple agents. The agent will be disconnected proactively from its connected agents one by one according to the local objective function value until the conflict is resolved.

An example is shown in Fig. 6. Agent 2 is connected by agents 1 and 10, and agent 6 is connected by agents 5, 7, and 8. According to (19), for agent 2, two candidate incoming edges can be obtained. Then, agent 1 leads to the best local objective function value of agent 2. Thus, the connection between agents 1 and 2 is retained, and agents 2 and 10 are disconnected. The conflict resolution of agents $5\backsim 8$ is similar. Fig. 7 shows the connection of agents after conflict resolution.

FIGURE 6.

Connection of agents after selection.

FIGURE 7.

Connection of agents after conflict resolution.

It can be observed that there is a local loop between agents 6 and 7, then the longest Dubins path (dotted line) in the loop is disconnected.

4) Termination Criteria

When all the agents have selected two agents without conflict, a complete directed graph emerges, and the complete data collection tour can be obtained by sequentially connecting the Dubins path in the digraph.

Based on the above, the agents can link with each other to form a feasible solution, and the collection sequence is obtained. Then the sequence is combined with the positions and headings generated by DE in the previous section, and an individual $\mathbf {x}_{i}$ can be evaluated.

5) Pseudo-Code of the SOMAC

In order to understand SOMAC more intuitively, some key sets are defined to store agents with different connection states and some concepts are explained in Fig. 8.

FIGURE 8.

Connection of agents after selection.

The pseudo-code of the SOMAC is presented in Algorithm 1. In line 1, the sets $S_{NI}$ and $S_{NO}$ reflect the connection status of all agents. Every agent in $S_{NI}$ is not connected by any other agent, and every agent in $S_{NO}$ is not connected to any other agent. In line 5, $L_{i}$ is the $i^{th}$ connection chain which reflects the connection between agents. Take Fig. 7 as an example, $\{a_{1},a_{7},a_{9},a_{10}\} \in S_{NI}$ , there are four connection chains. In the first chain, the agent 1 serve as a starting of a connection chain, and the connection is completed when the next connected agent is in $S_{NO}$ . Then, a connection chain $L_{1}$ is formed, like $L_{1}=\{a_{1},a_{2},a_{3},a_{4},a_{5}\}$ . In this way, each agent in $S_{NI}$ corresponds to a connection chain. The other three chains are $L_{2}=\{a_{7},a_{6}\}$ , $L_{3}=\{a_{9},a_{8}\}$ , and $L_{4}=\{a_{10}\}$ . It is noted that, all agents are in $S_{NI}$ at the beginning of the SOMAC, and a single agent can be regarded as a special connection chain.

Algorithm 1 Heuristic Based on Self-Organized Multi-Agent Competition (SOMAC) for Solving the Collection Sequence

1:

Two sets $S_{NI}$ and $S_{NO}$ are initialized, and both of them include all agents;

2:

while $S_{NI}$ and $S_{NO}$ are not empty do

3:

Find all agents in $S_{NI}$ , and record the number of agents in $S_{NI}$ as $M$ .

4:

for $i=1:M$ do

5:

Built the connection chain $L_{i}$ among agents, and the chain starts with the agent in $S_{NI}$ and ends with the agent in $S_{NO}$ .

6:

end for

7:

Find all agents in $S_{NO}$ , and record the number of agents in $S_{NO}$ as $K$ .

8:

for $i=1:K$ do

9:

For the agent $a_{i}$ , find the agents that $a_{i}$ cannot connect to, and from the rest of agents, find the agent with the shortest Dubins distance to connect. Then, remove $a_{i}$ from $S_{NO}$ .

10:

end for

11:

Remove the connected agents from $S_{NI}$

12:

Find the agents that have been connected by multiple agents, and form the set $S_{con}$ . The size of the set is $J$ .

13:

for $i=1:J$ do

14:

For the agent $a_{i}$ in $S_{con}$ , among multiple connections, find the one leading to the shortest Dubins distance. Then, disconnect the other connections, and put the corresponding agents back into $S_{NO}$ .

15:

end for

16:

Find the agents that are neither in $S_{NI}$ nor in $S_{NO}$ , and form the set $S_{lp}$ .

17:

while $S_{lp}$ is not empty do

18:

For an agent in $S_{lp}$ , starting from it, the connection chain is gradually built.

19:

if the connection chain is looped and does not contain all agents then

20:

Disconnect the two agents in the loop with the longest Dubins Distance and put them back into $S_{NI}$ and $S_{NO}$ .

21:

end if

22:

Find agents that exist in both the connection chain and $S_{lp}$ , and remove them from $S_{lp}$ .

23:

end while

24:

end while

25:

Get the connection chain of all agents, and output the collection sequence.

In line 9, for an agent $a_{i}$ in $S_{NO}$ , three kinds of agents cannot be connected to, which is mentioned in the selection operation. It should be noted that when the selection operation shown in lines $8\backsim 10$ is executed for the first time, all agents are in $S_{NI}$ and $S_{NO}$ . Because they connect to others simultaneously, they can connect to any other agents except for themselves. However, from the second execution of lines 8-10, some agents are already connected together. By analyzing these connections, when an agent without an outgoing edge performing the selection operation, the agents that have incoming edges or cause local loops can be excluded. In line 16, because the agents that are neither in $S_{NI}$ nor in $S_{NO}$ are either in a chain or in a loop, local loops can be judged by the connection chains constructed by these agents.

The time complexity of the SOMAC is analyzed as follows. Denote the number of agents by $n$ . In the selection operation, when constructing all connection chains shown in lines $4\backsim 6$ , all agents will be retrieved once. And for the operation shown in lines $8\backsim 10$ , the selection operation can be executed $n$ times at most. Thus, the time complexity of the selection operation is $O(n)$ . In the conflict resolution operation, the maximum size of the set $S_{con}$ is $n-1$ , so the time complexity of this operation is $O(n)$ . In the local loop resolution operation, the maximum size of $S_{lp}$ is $n$ , and with the construction of the connection chain, the size of $S_{lp}$ is gradually reduced to zero. Thus, the time complexity of this operation is also $O(n)$ .

The time complexity of the SOMAC mainly depends on the number of loop execution shown in lines $2\backsim 24$ . There are two possibly worst cases. In the first case, all agents connect to the same agent when executing the selection operation. After the conflict and local loop resolution, at least one connection can be determined. In this case, the number of loop execution is $n-1$ , and the time complexity of the SOMAC is $O(n^{2})$ . In the second case, agents are always connected with each other and lead to the occurrence of local loop. In this case, the maximum value of the number of loop execution is not more than $n$ , and the time complexity of the SOMAC is also $O(n^{2})$ . It should be noted that in either case, the probability of its occurrence is very small.

C. Local Search

In the process of population evolution, the local search is triggered at a certain interval $T$ , and a competitive tour is selected to be improved [32]. Then, the full-dimensional approximate gradient descent, the diversification mechanism, and the local-dimensional approximate gradient descent act on this tour sequentially. In this paper, the communication positions and UAV headings are optimized simultaneously. First, a full-dimensional approximate gradient descent is proposed to improve all the communication positions and UAV headings, which can make a full dimensional improvement.

When the local optimal Dubins path shown in Fig. 9 appears, the diversification mechanism and the local approximate gradient descent are applied to each component of these variables. In this way, the communication positions and UAV headings are further improved, and the quality of the data collection tour is further enhanced.

FIGURE 9.

Local optimal Dubins path.

1) Full-Dimensional Approximate Gradient Descent

An approximate gradient on a certain dimension of continuous variables can be calculated by two solutions, as shown in the following example:\begin{align*} SOL_{\mathbf {\hat {x}}}=&\left \{{ \begin{array}{lr} \mathbf {S}_{\mathbf {\hat {x}}}\\[0.5pc] \boldsymbol {\varphi }_{\mathbf {\hat {x}}}\\[0.5pc] \boldsymbol {\theta }_{\mathbf {\hat {x}}} \end{array} }\right \} = \left \{{ \begin{array}{lr} s_{\mathbf {\hat {x}}}^{1},s_{\mathbf {\hat {x}}}^{2},\cdots,s_{\mathbf {\hat {x}}}^{n}\\[0.5pc] \varphi _{\mathbf {\hat {x}}}^{1},\varphi _{\mathbf {\hat {x}}}^{2},\cdots,\varphi _{\mathbf {\hat {x}}}^{n}\\[0.5pc] \theta _{\mathbf {\hat {x}}}^{1},\theta _{\mathbf {\hat {x}}}^{2},\cdots,\theta _{\mathbf {\hat {x}}}^{n}\\ \end{array} }\right \} \tag{20}\\ ^{*}SOL_{\mathbf {\hat {x}}}=&\left \{{ \begin{array}{lr} \mathbf {S}_{\mathbf {\hat {x}}}\\[0.5pc] ^{*} \boldsymbol {\varphi }_{\mathbf {\hat {x}}}\\[0.5pc] \boldsymbol {\theta }_{\mathbf {\hat {x}}} \end{array} }\right \} = \left \{{ \begin{array}{lr} s_{\mathbf {\hat {x}}}^{1},s_{\mathbf {\hat {x}}}^{2},\cdots,s_{\mathbf {\hat {x}}}^{n}\\[0.5pc] \varphi _{\mathbf {\hat {x}}}^{1},\cdots,\varphi _{\mathbf {\hat {x}}}^{q}+\Delta \sigma,\cdots,\varphi _{\mathbf {\hat {x}}}^{n}\\[0.5pc] \theta _{\mathbf {\hat {x}}}^{1},\theta _{\mathbf {\hat {x}}}^{2},\cdots,\theta _{\mathbf {\hat {x}}}^{n}\\ \end{array} }\right \}\tag{21}\end{align*} where $SOL_{\mathbf {\hat {x}}}$ is a competitive solution, and $^{*}SOL_{\mathbf {\hat {x}}}$ is formed by adding a perturbation to $SOL_{\mathbf {\hat {x}}}$ . $^{*} \boldsymbol {\varphi }_{\mathbf {\hat {x}}}$ is the position vector after the perturbation. The two solutions have different communication positions. $\Delta \sigma $ is a small and fixed real number which is used as a small perturbation to calculate the approximate gradient of each dimension of continuous variables.

Then, an approximate gradient of the $q^{th}$ dimension of positions can be calculated by (22).\begin{align*} g_{q} \!\approx \! \frac {J(\mathbf {S}_{\mathbf {\hat {x}}},(\boldsymbol {\varphi }_{\mathbf {\hat {x}}}, \boldsymbol {\theta }_{\mathbf {\hat {x}}}))\!-\!J(\mathbf {S}_{\mathbf {\hat {x}}},(^{*} \boldsymbol {\varphi }_{\mathbf {\hat {x}}}, \boldsymbol {\theta }_{\mathbf {\hat {x}}}))}{\Delta \sigma }, ~q \in \{1,2,\cdots,n \} \\{}\tag{22}\end{align*}

Based on (20)–​(22), the gradient vector of the $2n$ continuous variables, as shown in (23), can be obtained by calculating the approximate gradient on the $n$ positions and $n$ headings gradually.\begin{equation*} \mathbf {g}=[g_{1},g_{2},\cdots,g_{2n}]\tag{23}\end{equation*}

After deriving the approximate gradient vector, the corresponding update equation of the $2n$ continuous variables is shown as follow:\begin{equation*} [\boldsymbol {\varphi }_{k+1}, \boldsymbol {\theta }_{k+1}]=[\boldsymbol {\varphi }_{k}, \boldsymbol {\theta }_{k}]-\rho \cdot \frac {\mathbf {g}}{|\mathbf {g}|}\tag{24}\end{equation*} where $\rho $ is the step size, and $k$ is the iteration number. The iteration goes on until the tour no longer turns better.

2) Local-Dimensional Approximate Gradient Descent

Due to the full-dimensional approximate gradient descent has strong directionality, the local optimal Dubins path caused by an improper heading shown in Fig. 9 may exist. The diversification mechanism is adopted firstly, and the reverse operation is performed for each dimension of the UAV headings to jump out of the local optimal Dubins path. Then the updated $SOL_{\mathbf {\hat {x}}^{,}}$ is obtained, and the local-dimensional approximate gradient descent is adopted to it. Because the position and heading at a certain DN have the greatest influence on the Dubins paths connected to the adjacent DNs, only the adjacent DNs are considered to reduce the computational cost.

Thus, a local solution $SOL_{\mathbf {\hat {x}}^{,}{}}^{local}$ shown as (25) is considered, which can lead to a local data collection path by using (2). For a pair of position and heading $[\varphi _{\mathbf {\hat {x}}^{,}{}}^{j},\theta _{\mathbf {\hat {x}}^{,}{}}^{j}]$ at the $j^{th}$ DN, an approximate gradient vector can be obtained by the following.

Taking the first dimension of $[\varphi _{\mathbf {\hat {x}}^{,}{}}^{j},\theta _{\mathbf {\hat {x}}^{,}{}}^{j}]$ as an example, a perturbation is added, as shown in (25)–(26).\begin{align*} SOL_{\mathbf {\hat {x}}^{,}{}}^{local}=&\left \{{ \begin{array}{lr} \mathbf {S}_{\mathbf {\hat {x}}^{,}{}}^{local}\\[0.5pc] \boldsymbol {\varphi }_{\mathbf {\hat {x}}^{,}{}}^{local}\\[0.5pc] \boldsymbol {\theta }_{\mathbf {\hat {x}}^{,}{}}^{local} \end{array} }\right \} = \left \{{ \begin{array}{lr} s_{\mathbf {\hat {x}}^{,}{}}^{j-1},s_{\mathbf {\hat {x}}^{,}{}}^{j},s_{\mathbf {\hat {x}}^{,}{}}^{j+1}\\[0.5pc] \varphi _{\mathbf {\hat {x}}^{,}{}}^{j-1},\varphi _{\mathbf {\hat {x}}^{,}{}}^{j},\varphi _{\mathbf {\hat {x}}^{,}{}}^{j+1}\\[0.5pc] \theta _{\mathbf {\hat {x}}^{,}{}}^{j-1},\theta _{\mathbf {\hat {x}}^{,}{}}^{j},\theta _{\mathbf {\hat {x}}^{,}{}}^{j+1}\\ \end{array} }\right \} \tag{25}\\ ^{*}SOL_{\mathbf {\hat {x}}^{,}{}}^{local}=&\left \{{ \begin{array}{lr} \mathbf {S}_{\mathbf {\hat {x}}^{,}{}}^{local}\\[0.5pc] ^{*} \boldsymbol {\varphi }_{\mathbf {\hat {x}}^{,}{}}^{local}\\[0.5pc] \boldsymbol {\theta }_{\mathbf {\hat {x}}^{,}{}}^{local} \end{array} }\right \} = \left \{{ \begin{array}{lr} s_{\mathbf {\hat {x}}^{,}{}}^{j-1},s_{\mathbf {\hat {x}}^{,}{}}^{j},s_{\mathbf {\hat {x}}^{,}{}}^{j+1}\\[0.5pc] \varphi _{\mathbf {\hat {x}}^{,}{}}^{j-1},\varphi _{\mathbf {\hat {x}}^{,}{}}^{j}+\Delta \sigma,\varphi _{\mathbf {\hat {x}}^{,}{}}^{j+1}\\[0.5pc] \theta _{\mathbf {\hat {x}}^{,}{}}^{j-1},\theta _{\mathbf {\hat {x}}^{,}{}}^{j},\theta _{\mathbf {\hat {x}}^{,}{}}^{j+1}\\ \end{array} }\right \}\tag{26}\end{align*} where $^{*}SOL_{\mathbf {\hat {x}}^{,}{}}^{local}$ is formed by adding a perturbation to $SOL_{\mathbf {\hat {x}}^{,}{}}^{local}$ , and $^{*} \boldsymbol {\varphi }_{\mathbf {\hat {x}}^{,}{}}^{local}$ is the position vector after the perturbation.

Then, the gradient of the first dimension of $[\varphi _{\mathbf {\hat {x}}^{,}{}}^{j},\theta _{\mathbf {\hat {x}}^{,}{}}^{j}]$ can be calculated by (27).\begin{align*} g_{\varphi _{\mathbf {\hat {x}}^{,}{}}^{j}} \!\approx \! \frac {J(\mathbf {S}_{\mathbf {\hat {x}}^{,}{}}^{local},(\boldsymbol {\varphi }_{\mathbf {\hat {x}}^{,}{}}^{local}, \boldsymbol {\theta }_{\mathbf {\hat {x}}^{,}{}}^{local}))\!-\!J(\mathbf {S}_{\mathbf {\hat {x}}^{,}{}}^{local},(^{*} \boldsymbol {\varphi }_{\mathbf {\hat {x}}^{,}{}}^{local}, \boldsymbol {\theta }_{\mathbf {\hat {x}}^{,}{}}^{local}))}{\Delta \sigma } \\{}\tag{27}\end{align*}

Based on the above, the gradient of $\theta _{\mathbf {\hat {x}}^{,}{}}^{j}$ can be calculated in the same way. The gradient vector $\mathbf {g}^{local}=[g_{\varphi _{\mathbf {\hat {x}}^{,}{}}^{j}},g_{\theta _{\mathbf {\hat {x}}^{,}{}}^{j}}]$ of position and heading on the $j^{th}$ DN is formed, and $[\varphi _{\mathbf {\hat {x}}^{,}{}}^{j},\theta _{\mathbf {\hat {x}}^{,}{}}^{j}]$ can be updated by (28).\begin{align*} [\varphi _{\mathbf {\hat {x}}^{,}{}}^{j}(k+1),\theta _{\mathbf {\hat {x}}^{,}{}}^{j}(k+1)]=[\varphi _{\mathbf {\hat {x}}^{,}{}}^{j}(k),\theta _{\mathbf {\hat {x}}^{,}{}}^{j}(k)]-\rho \cdot \frac {\mathbf {g}^{local}}{|\mathbf {g}^{local}|} \\{}\tag{28}\end{align*}

Remark 3:

It is easy to see from (24) and (28) that the upper bound of the iteration number is $\lfloor 2\pi / \rho \rfloor $ , where $\lfloor \cdot \rfloor $ is the downrounding function.

The time complexity of the local search is analyzed below. For the full-dimensional approximate gradient, the gradients on $2n$ continuous variables need to be sequentially calculated, so the time complexity of this part is $O(2n\lfloor 2\pi / \rho \rfloor)$ . For the diversification mechanism, the reverse operations are executed $n$ times for the $n$ -dimension headings, so the time complexity of this part is $O(n)$ . For the local-dimensional approximate gradient, for each DN, it needs to calculate the gradients on $\varphi $ and $\theta $ . Thus, the time complexity of this part is $O(2n\lfloor 2\pi / \rho \rfloor)$ . Based on the above, because the three parts are executed sequentially, the time complexity of the local search can be regarded as $O(n)$ .

D. Complexity Analysis of the BLHMA

The pseudo-code of the BLHMA is presented in Algorithm 2, and the time complexity and space complexity are analyzed in Table 2. The evaluation operation has the highest time complexity because the time complexity of the construction of the Dubins distance matrix is $O(n^{2})$ . $G$ is the number of iterations, and $mod(\cdot)$ is the modulo operation. When the algorithm satisfies the criterion $mod(G,T)=0$ , the local search is triggered, and the number of runs of the local search is $G/T$ . Based on the above, the time complexity and the space complexity of the BLHMA are $O(G\cdot NP\cdot n^{2})$ and $O(n\cdot NP + n^{2})$ , respectively.

TABLE 2 Complexity of the BLHMA

Algorithm 2 Bi-Level Hybridization-Based Metaheuristic Algorithm (BLHMA) for the UAV Data Collection Planning

1:

Initialize a population based on (4);

2:

Pertaining to each individual generated by DE, SOMAC is used to determine the sequence which mentioned in subsection III-B. Take them into (2) to complete the individual evaluation, and record the solution as (5);

3:

Set the number of iterations $G=1$

4:

while the stopping criterion is not satisfied do

5:

for $i=1:NP$ do

6:

According to the adaptive selection strategy mentioned in the literature [50], mutate $\mathbf {x}_{i}$ by (6)–​(9), then a trial vector $\mathbf {v}_{i}$ is generated by the crossover based on (10);

7:

Evaluate the trial vector $\mathbf {v}_{i}$ by using the methods in line 2;

8:

Update the population based on the selection operator shown as (11), and update the solution by (12);

9:

end for

10:

if $mod(G,T)==0$ ($T$ is a constant) then

11:

All solutions are sorted, and one of the first 30% solutions is randomly selected as the competitive solution. Then the multistage local search mentioned in subsection III-C is conducted to improve its parts of positions and headings;

12:

Re-evaluate the improved positions and headings by using the methods in line 2, and update the corresponding solution;

13:

end if

14:

$G=G+1$

15:

end while

16:

Output the best solution and the corresponded data collection tour.

SECTION IV. Computational Experiments

For the UAV data collection planning in forest fire monitoring, it is assumed that the installation height of each DN is 5m, and the maximum communication distance of DN is 200m. A small and low-altitude UAV cruises 110m above the ground at a speed of 40m/s, and its maximum communication distance is more than 200m. UAV circularly flies to all DNs to obtain their data, as Fig. 10 shows, and the effective communication radius ($R$ ) between the UAV and a DN can be calculated by simple geometric relation, which is approximately equal to 170m. The schematic diagram is shown in Fig. 11. Besides, assume that the maximum roll angle of the UAV is 50°. According to the force analysis about the UAV turning, (29) can be obtained, then by using (30), the turning radius ($r$ ) of the UAV is approximately equal to 137m.\begin{align*} \frac {\mathcal {F}_{hori}}{\mathcal {F}_{vert}}=&\frac {\mathcal {L}\cdot sin(\beta)}{\mathcal {L}\cdot cos(\beta)}=\frac {M\cdot \frac {V^{2}}{r}}{M\cdot \mathfrak {g}}=tan(\beta) \tag{29}\\ r=&\frac {V^{2}}{\mathfrak {g}\cdot tan(\beta)}\tag{30}\end{align*} where $\mathcal {F}_{hori}$ and $\mathcal {F}_{vert}$ are the force of the UAV in the horizontal and vertical direction. $\mathcal {L}$ is the lift force of the UAV. $V$ and $M$ are the speed and weight of the UAV, $\mathfrak {g}$ is the gravitational acceleration, and $\beta $ is the maximum roll angle.

FIGURE 10.

UAV obtains data from multiple DNs.

FIGURE 11.

Transmission diagram of UAV and a DN.

Based on the above assumptions, to verify the performance of the BLHMA in solving the UAV data collection planning, two-part computational experiments are conducted in this section. In addition, three state-of-the-art algorithms identified in the literature are involved in the computational experiments (denoted by transformation method [36], VNS [45], and MA [32], respectively).

Firstly, general analyses on a series of random instances with different minimum distance constraints are given, including $D_{4}$ , $D_{1}$ , and $D^{*}$ -constraint instances. Secondly, the convergence performance of different algorithms is carried out, and the mechanisms of the BLHMA are analyzed.

All algorithms were implemented on a personal computer with Intel(R) Xeon(R) Silver 4114 CPU 2.20GHz, 32GB RAM. BLHMA, VNS, and MA were implemented by the MATLAB R2019b. For the transformation method, a GTSP was formed by the uniform sampling of communication positions and UAV headings firstly, and then the GTSP was converted to an ATSP by the Noon-Bean transformation [36], which was implemented by the MATLAB. At the last, LKH Ver.2.0.9 was applied for solving the ATSP to obtain a data collection tour, which was implemented by the Visual Studio 2019 (C++). Thus, for the fairness of comparison, the solution obtained by the transformation method is only regarded as a reference value. The code of LKH can be downloaded from the website: http://akira.ruc.dk/~keld/research/LKH/.

The parameter settings of the BLHMA are shown in Table 3, and the selection of some key parameters is analyzed. Here, the framework of the SADE is adopted [50], and the four mutation operators shown in (6)–​(9) are selected. In order to ensure the best performance of the SADE, the setting of all parameters in SADE was consistent with the original literature, except for population size $NP$ . $NP$ was left as a user-specified parameter because it highly depends on the complexity of a given problem.

TABLE 3 The Main Parameters of the BLHMA

To find a suitable value of $NP$ , three typical values were tried. $NP$ with the settings of $n$ , $10n$ , and $20n$ were tried in the instances with different scales. BLHMA was run 20 times, and the length of the so-far-best tour is stored every 5s. Then the mean value at each time is calculated. The results are shown in Figs. 12–​14. In the 10-DNs instance, when $NP$ is set to $n$ , although the ability of the algorithm to jump out of the local optimal solution is not strong, the algorithm has a good balance between convergence and performance, as shown in the displayed curve. Similarly, good results are achieved in the 20 or 30-DNs instances when $NP$ is set to $n$ .

FIGURE 12.

Convergence curves of the BLHMA under different population sizes on 10-DNs instance.

FIGURE 13.

Convergence curves of the BLHMA under different population sizes on 20-DNs instance.

FIGURE 14.

Convergence curves of the BLHMA under different population sizes on 30-DNs instance.

In the local search, $\Delta \sigma $ is used to construct approximate gradients, and it can usually be set to a small and fixed positive real number. We tested many different values of $\Delta \sigma $ ranging from 0.01% of $2\pi $ to $2\pi $ , and found that when its value is less than 1% of $2\pi $ , its value has little effect on the performance of the local search. $\rho $ and $T$ usually have a great impact on the performance of the BLHMA, and both of them were determined as follows.

In order to determine the step size ($\rho $ ) in the local search, different step sizes were used to improve a poor data collection tour on the 10-DNs instance. The local search was run for each step value, and Fig. 15 shows the values of the length of the data collection tour and the runtime. When the value of $\rho $ is small, the improvement effect of the local search is remarkable, but it takes a long time. On the contrary, the runtime is very short, but the search capability of the local search is poor. It can be seen that when $\rho $ is set as 0.2, the local search has a good tradeoff between the runtime and performance.

FIGURE 15.

Influence of the step size of the local search.

After determining the step size, the execution frequency of the local search was analyzed, and it also affects the convergence of the BLHMA. It can be adjusted to achieve a better tradeoff between exploration and exploitation in the solution space by changing the value of $T$ . A comparison of different $T$ of the BLHMA on the 10-DNs instance is shown in Fig. 16. Similarly, BLHMA was run 20 times, and the length of the so-far-best tour is stored every 5s. Then the mean value at each time is calculated. When the value of $T$ is small, the local search is frequently triggered, and the algorithm tends to exploitation, which makes it easy to fall into a local optimal solution. When the value of $T$ is large, the trigger frequency of the local search becomes lower, the algorithm tends to explore, and the ability to jump out of the local optimal solution becomes stronger, but it takes more time to converge. As Fig. 16 shows, when $T$ takes the value of 5, the comprehensive performance of the algorithm is better.

FIGURE 16.

Comparison of different execution frequencies of the local search strategy in BLHMA.

After analyzing the parameter setting of the BLHMA, the parameter setting of the competitors is explained as follows. For the transformation method, in order to get high-quality solutions, the highest sample counts are used according to the numerical study of Obermeyer [36]. The sample counts of the transformation method are set as 1100, 1600, and 2100 corresponding to the 10, 20, and 30-DNs instances, respectively. The mean runtimes on these three kinds of instances are 210s, 420s, and 850s, respectively. In addition, in order to get a better balance between position samples and heading samples in the designed instances in this paper, the weighting parameter which determines how many heading samples there will be per position is set to 68. For the other algorithms, the parameter settings are consistent with the original works of literature, and the maximum runtime is defined as the stop condition. Those algorithms will be terminated when the time of the transformation method is exhausted. It is worth noting that in order to make MA generate the cyclic data collection tour, the optimization of the position and UAV heading at the first DN is considered without changing the key framework and the idea of the algorithm.

In addition, to verify the performance of the SOMAC algorithm, the nearest neighbor rule (NNR) is used which can also solve the ATSP quickly and stably [54], and the bi-level hybridization-based metaheuristic algorithm with the nearest neighbor rule (BLHMA-NNR) is formed. Because the time complexity of the SOMAC and NNR is less than that of calculating the Dubins distance matrix, the influence of replacing SOMAC with NNR on the time complexity of the collection sequence obtaining can be ignored.

A. Comparison in Random Instances With Different Minimum Distance Constraints and Scales

A series of random simulated UAV data collection instances with different minimum distance constraints and scales are designed and used for analyzing the performance of all algorithms. The tested instances are labelled as $n-i$ , where $n$ is the number of DNs and $i$ is the identifier of instances. Similar to the study [49], all DNs are randomly generated inside a bounding box with the side $7\sqrt {n}((R+r)/2)$ , which can provide a relatively high density. The five algorithms were applied to solve the 27 instances with different minimum distance constraints and scales, and the results were compared. For each instance, the statistical results of all algorithms are presented in Table 4.

TABLE 4 Statistical Results About Different Algorithms in Solving Randomly Generated Instances

BLHMA, BLHMA-NNR, VNS, and MA were run 20 times, and the processing time of each algorithm is the same among all 20 attempts. Then, the length of the data collection tours can be calculated by the objective function, as shown in (2). The results were evaluated from four aspects including the mean value (avg), the maximum value (max), the minimum value (min), and the standard deviation (std). The Wilcoxon rank-sum test is also used for analyzing the significance of the difference of results [55], and the confidence level is set as 0.95. Besides, the data collection tours obtained by the transformation method are regarded as references.

From the statistical results, for most instances, BLHMA is the best one as it can find high-quality data collection tours in all aspects as compared with MA, VNS, and even the reference value. BLHMA-NNR also performed well in most instances. For $D_{4}$ -constraint instances, when the number of DNs is small, BLHMA, BLHMA-NNR, and VNS can find better tours than that of the reference, and BLHMA and BLHMA-NNR outperform other algorithms with minor advantages. By comparing BLHMA-NNR and BLHMA, it can be seen that their performances are comparable in most $D_{4}$ instances, and the minimum length values of tours obtained by BLHMA-NNR is only slightly inferior to that of the BLHMA.

With the increase of the number of DNs and the enhancement of the constraint, in most cases, data collection tours found by MA are better than that of the VNS. In addition, tours obtained by BLHMA are obviously better than those of its competitors in all aspects, including BLHMA-NNR and the other three algorithms. It can be observed that the difference between BLHMA and BLHMA-NNR is not significant from the Wilcoxon rank-sum test results, but BLHMA can find better tours than BLHMA-NNR in most cases.

By summarizing the results of the experiments on the simulated instances of the UAV data collection task in forest fire monitoring, it can be obviously observed that MA is hard to find a satisfactory data collection tour in most cases. Because the Dubins path is relaxed, resulting in incomplete solution space. VNS can achieve a good balance between exploration and exploitation by using a neighborhood structure composed of different actions to the mixed variables. However, due to the large amount of optimization variables, the solution space is still very complex. Supported by an efficient solver for the ATSP, the sampling-based transformation method can find a better approximate optimal data collection tour. However, the extensive calculation caused by a large number of samplings usually consumes a large amount of time, and uniform sampling is not conducive to finding the optimal tour. In contrast, BLHMA proposed in this paper can decompose the solution space and search cooperatively in different subspaces, which significantly reduces the difficulty of searching, and it can obtain significantly shorter data collection tours in most cases. The data collection tours generated by BLHMA, BLHMA-NNR, MA, VNS, and the transformation method in different instances are presented in Fig. 17. It can be seen intuitively that the tours generated by BLHMA, BLHMA-NNR, and the transformation method are almost coincident in most cases, and BLHMA wins BLHMA-NNR and the reference tours with a slight advantage.

FIGURE 17.

The data collection tours generated by different algorithms in different instances.

In addition to the simulated UAV data collection instances, this paper also considers an instance in a real-world case. According to historical experience, there are several high-risk areas in the Xishuangbanna forest, and it is necessary to implement the fire monitoring mission in these areas. As Fig. 18 shows, 25 DNs are distributed in the high-risk areas of the forest around the scenic spot, and a UAV is used to perform a data collection task in forest fire monitoring. BLHMA, BLHMA-NNR, VNS, and MA were run 20 times. The mean runtime of the transformation method is 718s, and BLHMA, BLHMA-NNR, VNS, and MA stop running at 718s as termination conditions. The best data collection tours obtained by the four algorithms are 13906.2m (BLHMA), 14038.9m (BLHMA-NNR), 17986.3m (VNS), 17406.2m (MA), and 13930.3m (Reference). The tours generated by BLHMA, BLHMA-NNR, and the transformation method are also almost coincident. By observing the regions marked by the blue dot line in Fig. 18, it can be observed that BLHMA also wins BLHMA-NNR and the reference tours with a slight advantage, so the data collection tour obtained by BLHMA is more conducive to the efficient mission execution and the energy saving of the UAV.

FIGURE 18.

UAV data collection instance in a real world case.

B. Convergence and Mechanism Analysis

In this subsection, the convergence of the BLHMA is discussed and compared with its competitors. Each algorithm runs 20 times on a 10-DNs instance repeatedly and independently. During the runtime, the length of the so-far-best tour is stored every 5s, then the mean value at each time is calculated, as shown in Fig. 19. The mean runtime of the transformation method is 210s, and the data collection tour obtained by the transformation method is regarded as a reference. All the other algorithms run the same time.

FIGURE 19.

Convergence curves of different algorithms on the 10-DNs instance.

It can be observed intuitively from Fig. 19 that BLHMA converges in a very short time, and the obtained data collection tour is better than that of the transformation method. MA also converges quickly, but due to the incomplete solution space, it cannot converge to a better solution. It can be seen from the mean curve that the convergence rate of the BLHMA is the fastest. BLHMA can obtain a comparable tour to the transformation method in a very short time.

To verify the contribution of the local search to BLHMA, Fig. 20 shows the comparison of the BLHMA and its version without the local search (BLHMAxLS). Each algorithm runs 20 times on a 10-DNs instance repeatedly and independently, the length of the so-far-best tour is stored every 5s, then the mean value at each time is calculated. It can be seen that the mean curve of the BLHMA tends to be flat in about 15 seconds, while BLHMAxLS reaches the same level in about 70 seconds.

FIGURE 20.

Comparison of the BLHMA and BLHMAxLS on the 10-DNs instance.

For further verifying the performance of the local search, different search strategies were used to improve a poor data collection tour shown in Fig. 21 (black line). Fig. 21 and Table 5 show the improvement of the tour by different search strategies. Although multistage approximate gradient descent strategy proposed in this paper consumes a little more time, its improvement to the tour is better than that of the two sub-strategies.

TABLE 5 Local Search Performance of Different Strategies

FIGURE 21.

A poor data collection tour improved by different local search strategies.

SECTION V. Conclusion

In this paper, a bi-level hybridization-based metaheuristic algorithm is proposed for the UAV data collection task planning in forest fire monitoring. At the first hybridization level, DE and the proposed SOMAC act on continuous and discrete variables respectively to produce data collection tours in a cooperative way, which avoids a large amount of blind search in complex solution space. To enhance the quality of the tours and accelerate the convergence of the algorithm, at the second level, a local search strategy based on a multistage approximate gradient is incorporated to improve the communication position and UAV heading at each DN. Finally, numerical results based on the simulated and real-world UAV data collection instances demonstrate that the algorithm proposed in this paper, compared with the state-of-the-art algorithms, can generate shorter data collection tours in most cases. It is conducive to the efficient execution of a UAV data collection task in the fire monitoring, and effectively reduces the energy consumption of the UAV. This paper provides favorable technical support for the UAV data collection in forest fire monitoring, and the idea can be extended to many other applications, such as electric power inspection, pipeline detection, mobile edge computing, etc.