Intelligent Scheduling Technology of Swarm Intelligence Algorithm for Drone Path Planning

Abstract

Different kinds of swarm intelligence algorithm obtain superior performances in solving complex optimization problems and have been widely used in path planning of drones. Due to their own characteristics, the optimization results may vary greatly in different dynamic environments. In this paper, a scheduling technology for swarm intelligence algorithms based on deep Q-learning is proposed to intelligently select algorithms to realize 3D path planning. It builds a unique path point database and two basic principles are proposed to guide model training. Path planning and network learning are separated by the proposed separation principle and the optimal selection principle ensures convergence of the model. Aiming at the problem of reward sparsity, the comprehensive cost of each path point in the whole track sequence is regarded as a dynamic reward. Through the investigation of dynamic environment conditions such as different distances and threats, the effectiveness of the proposed method is validated.

1. Introduction

Swarm intelligence (SI) represents the collective intelligent behavior of a class of decentralized self-organizing systems, and the macroscopic SI is shaped through the interaction of microscopic individuals [1,2]. SI algorithms obtain the possible solutions through stochastic searches in the feasible domain and have all solutions converge to a target optimal solution through iterative updates. The essence of SI algorithms involves a type of parallel computing with individual information communication. The number of individuals determines the scale of parallel computing, and information exchange between individuals determines the efficiency of parallel operation. The increasing complexity of optimization problems leads to the continuous development and improvement of optimization algorithms. On the one hand, new structural algorithms are constantly proposed. The purpose of SI algorithm development is to study the swarm intelligence behavior of natural organisms and simulate more efficient information communication methods [3,4]. On the other hand, the existing algorithms are constantly improved. They can be improved by introducing chaos theory [5] quantum theory [6,7], Lévy flight [8,9], and other theories, and they can also be improved by the fusion of SI algorithms [10].

Path planning is an important basis for drones to execute various tasks. It has the characteristics of high dimensionality and multi-constraints. Current methods for path planning can roughly be divided into two categories: Traditional algorithm and intelligent optimization algorithm. Typical traditional algorithms include the Voronoi diagram method [11] and signpost diagram method based on graph theory, fast random tree method (RRT) [12] based on random sampling, and A* algorithm [13] based on heuristic information. They have a fast construction speed and a high route safety but have different drawbacks, such as being unable to adapt to a dynamic environment and being unable to be applied to three-dimensional scenes.

The SI algorithm is the typical representative of intelligent algorithms. Due to its fast planning speed, simple principle, and freedom from spatial dimensions, it has numerous applications in the estimation and setting of control parameters [14,15,16,17] fault diagnosis, task allocation, and flight path planning [18,19,20]. However, the no free lunch (NFL) [21] theorem logically proves that there is no suitable SI algorithm for solving all optimization problems. A particular SI algorithm may perform well on one kind, while poorly on another. NFL has created the research upsurge of SI algorithms, and various new algorithms and improvements emerge endlessly. But these studies on single algorithms cannot break the limit of NFL. So, this paper demonstrates the differences of SI algorithms by building deep Q-learning networks. Through the reasonable selection of multiple algorithms, the advantages of each SI algorithm are maximized.

Combined with deep learning nets and reinforcement learning (RL) [22], deep reinforcement learning (DRL) takes advantage of the feature representation capabilities of deep neural networks to fit RL functions [23], including state, action, and value, to improve the performance of RL models. Among different DRL methods, the deep Q-network (DQN) has achieved remarkable success. Mnih et al. proposed Deep Q-Net [24], the first DRL framework. Its neural network fits the table of the action–value pairs in the Q-learning algorithm into a function, which addresses the disadvantage of only being applicable to a finite state space. The DQN has two neural networks, the eval network and target network, which can improve the learning efficiency through different updating methods. The presence of experience pools can weaken the correlation between samples.

Since the proposal of DQN, various improved algorithms have been proposed. The dual deep Q-network (DDQN) [25] eliminates the problem of overestimation by decoupling the selection of the target Q-action and the calculation of the target Q-value. Its improvement is reflected in the structural optimization. Prioritizing experience, the Q-network [26] gives the priority of the samples and stores the value of this priority in the experience replay buffer pool. Its improvement is reflected in the experience pool optimization. The dual deep Q-network [27] illustrates the improvement of network structure. It replaces the last fully connected layer with two networks, the price function network and the dominance function network. The final output of the Q-network is obtained by a linear combination of the output of the price function network and the output of the dominance function network. Except for the DQN, policy-based RL algorithms which include the actor–critic framework (A3C), deep deterministic policy gradient (DDPG) [28,29], and proximal policy gradient optimization (PPO) algorithm [30] are also growing. The problem of continuous control, which Q-learning is unable to solve, is solved. Regarding data processing, Markov chain Monte Carlo (MCMC) [31] and approximate Bayesian computation (ABC) [32] are widely used.

In terms of path planning, with different threat changes and planning dimensions, a single SI algorithm struggles to determine the optimal value every time. For this reason, analysis of performance differentiation of SI algorithms and intelligent scheduling technology are increasingly important.

In this paper, a novel scheduling technology about swarm intelligence algorithms based on deep Q-learning (DQN-SISA) is proposed to intelligently select the optimal algorithm to realize 3D path planning when a drone faces different dynamic environments. Firstly, this study creates a library of SI algorithms including four typical algorithms, ant colony optimization (ACO) [33], particle swarm optimization (PSO) [34], grey wolf optimizer (GWO) [35], whale optimization algorithm (WOA) [36] and chaos particle swarm optimization (CPSO) [37]. Based on the establishment of the library, theories of algorithms are compared and analyzed from two aspects of structure and parameters. Secondly, path points are calculated by the SI algorithms as the state that is constructed to establish a Markov process for path planning. The DQN is suitable for discrete action spaces and is selected to learn the performance differences of the SI algorithms with different path distances, numbers of threats, and other dynamic environments. Two principles are proposed for model training. A separation principle is proposed to separate the solution processes of the SI algorithms from the DQN training process by establishing a path point database such that the point data are reusable and the training time cost of the DQN is greatly reduced. An optimal extraction principle is proposed to solve the influence of the randomness of the SI algorithms on model convergence.

For the hyperparameters of the model, an adaptive greedy strategy is used to select the behavior to then improve the early exploration ability and late convergence ability of the model.

2. SI Algorithm Library for Path Planning

2.1. Theory of Selected Algorithms

Most SI algorithms follow considerably similar processes. The definition of a population is the first step, which is responsible for defining objects including population size, iteration time, and characteristic parameters such as the speed and position of the algorithm. The iterative loop is the most important phase, which typically includes the necessary boundary processing, fitness calculation and comparison, and information updating methods of the SI algorithm. The last step involves determining whether the loop terminates. If the maximum number of iterations is reached, the loop breaks, otherwise, the loop iterates. The criteria for ending the loop can be a pre-set number of iterations, minimum error labeling, or minimum accuracy requirements. The overall flow chart is shown in Figure 1.

Mimicking the swarm intelligence behavior of ants in determining the closest route to target food, the ACO algorithm developed by Dorigo is the earliest SI algorithm with practical significance.

The pheromone updating formula of ACO is expressed as

$$\begin{array}{l}{\tau }_{ij}(t+1)=(1-\rho ){\tau }_{ij}(t)+\Delta {\tau }_{ij}(t)\\ \Delta {\tau }_{ij}(t)={\displaystyle \sum _{k=1}^m\Delta {\tau }_{ij}^k(t)}\end{array}$$

(1)

where ${\tau }_{ij}(t)$ denotes pheromone intensity at time $t$ and $\rho$ refers to the pheromone volatilization factor.

Inspired by the foraging behavior of birds, the PSO algorithm proposed by Eberhart is one of the most widely used SI algorithms.

The updating formula of position and velocity information of the standard PSO is expressed as

$$\begin{array}{l}\nu =\omega \cdot v+c_1{r}_1(pBest-x)+c_2{r}_2(gBest-x)\\ x=x+v\end{array}$$

(2)

Here, $w$ is the inertia weight, $c_1$ and $c_2$ are the learning rates, $pBest$ the historical optimal position of the corresponding particle, and $gBest$ the global optimal position in this iteration. As a coefficient, $w$ determines the influence of the particle velocity of the previous iteration for this iteration.

Classical algorithms, including ACO and PSO, have a strong robustness and global search ability, but also a slow convergence speed and poor accuracy. From the perspective of model structure, the slow convergence speed is due to the single structure. There is no hierarchical stratification of information among individuals. Although the equivalence of information can enhance the search ability of the algorithm in the early stage, once the local optimum is found in the later stage, it is easy to break the balance between individuals and affect the adjacent individuals, so that the algorithm falls into the local optimum. Although the accuracy is low, due to a less random mechanism, it has a shorter computing time in the low-dimension route planning optimization problem.

Newer algorithms, such as GWO and WOA, whose superiority is attributed to the more diverse and efficient algorithm structure design, have fast convergence speeds and high accuracies and have been widely used in flight-path planning.

The GWO search and update formula of position information during its predation period is expressed as

$$\begin{array}{l}D=|C{X}_p(t)-X(t)|\\ X(t+1)=X_p(t)-A\cdot D\\ D_{\alpha }=|C_1\cdot X_{\alpha }(t)-X(t)|,D_{\beta }=|C_2\cdot X_{\beta }(t)-X(t)|,\\ D_{\xi }=|C_3\cdot X_{\xi }(t)-X(t)|\\ X_1=X_{\alpha }-A_1\cdot D_{\alpha },X_2=X_{\beta }-A_2\cdot D_{\beta },\\ X_3=X_{\xi }-A_3\cdot D_{\xi }\\ X(t+1)=\frac{X_1+X_2+X_3}{3}\end{array}$$

(3)

Here, $X_{\alpha }$, $X_{\beta }$, and $X_{\delta }$ denote the position vectors of wolves $\alpha$, $\beta$, and δ in the current population; $X$ is the location of individual grey wolves; $D_{\alpha }$, $D_{\beta }$, and $D_{\delta }$ denote the distances between the current object wolf and the three candidate wolves; $A$ and $C$ are coefficient vectors; $X_n(t)$ refers to the position vector of the prey; $D$ is the distance between the current grey wolf and the location of the prey.

Concerning WOA, the location information updating law for the two periods of encircling prey and forced attacks is expressed as:

$$\begin{array}{l}D=|\overrightarrow{C}{\overrightarrow{X}}^{*}(n)-\overrightarrow{X}(n)|\\ \overrightarrow{X}(n+1)={\overrightarrow{X}}^{*}(n)-\overrightarrow{A}\cdot \overrightarrow{D}\\ \overrightarrow{X}(n+1)=\overrightarrow{d}{e}^{bI}\cos (2\pi l)+{\overrightarrow{X}}^{*}(n)\end{array}$$

(4)

Here, $n$ denotes the number of iterations, $\overrightarrow{A}$ and $\overrightarrow{C}$ the updated coefficient vectors, ${\overrightarrow{X}}^{*}(n)$ the optimal position of the whale at iteration $n$, $\overrightarrow{X}(n)$ the position vector of the current whale. The first two formulas show the shrinkable encircling prey stage, and the final formula is the spiral position update.

$\left|\overrightarrow{d}\right|=|\overrightarrow{C}{\overrightarrow{X}}^{*}(n)-\overrightarrow{X}(n)|$ represents the distance between the whale and its prey. The role of random coefficient A is similar to that in GWO. When $\left|A\right|>1$, the whale herd performs a decentralized search, and the whale position is updated randomly. The random updating formula is as follows:

$$\begin{array}{l}K=\left|C\times {\overrightarrow{X}}_{rand}-\overrightarrow{X}\right|\\ \overrightarrow{X}(n+1)={\overrightarrow{X}}_{rand}-\overrightarrow{A}\cdot \overrightarrow{K}\end{array}$$

(5)

WOA is one SI algorithm with many random search mechanisms, and the selection of the information updating formula is random. Many random search mechanisms can effectively improve the global search ability in the early stage of the algorithm, but simultaneously affect the stability of the algorithm performance and computation time in the late stages.

These four algorithms cover the early SI algorithms that have been widely used and new SI algorithms proposed in recent years. From the aspect of algorithm performance, they cover different performance requirements, such as strong robustness, strong convergence, and high accuracy. Most importantly, they are widely used in the field of drone cluster control. In summary, the four algorithms were selected as candidate algorithms and incorporated into the algorithm scheduling library for the DQN to study algorithm scheduling technology.

2.2. Modeling Environments and Threats

2.2.1. Digital Maps with Terrain Threats

An appropriate planning space must be established in accordance with the flight environment and mission requirements for terrain models. The former is expressed as digital elevation maps (DEMs) adopting the form of a group of ordered numerical arrays to represent the ground elevation. A mountain background is taken as a task environment, and a DEM is established using a random function to simulate peaks and other threat obstacles. The mountain model function was proposed in Ref. [31]. The former is expressed as:

$$\begin{array}{l}z(x,y)=\sin (y+a)+b\cdot \sin (x)+c\cdot \cos (d\cdot \sqrt{x^2+y^2})\\ \hspace{0.33em}\hspace{1em}\hspace{0.33em}\hspace{1em}\hspace{1em}+e\cdot \cos (y)+f\sin (f\cdot \sqrt{x^2+y^2})+g\cdot \cos (y)\end{array}$$

(6)

where $(x,y)$ refer to the point coordinates on a horizontal projection plane; $z$ refers to the height coordinate that corresponds to $(x,y)$; $a, b, c, d, e, f$ are the coefficients. Changing the coefficients can obtain different landforms.

The threat cost $T_{terrain}$ of a certain peak $k$ is expressed as

$$T_{terrain}=\left\{\begin{array}{l}\hspace{0.33em}{R}_t(h)+d_{\min }-d\hspace{0.33em}\hspace{0.17em},\hspace{1em}d<(R_t(h)+d_{\min })\hspace{0.33em}and\hspace{0.33em}h<H(k)\hspace{1em}\\ \hspace{0.33em}0\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em},\hspace{1em}d>(R_t(h)+d_{\min })\hspace{0.33em}or\hspace{0.33em}h>H(k)\end{array}\right.$$

(7)

where $d$ is the distance from the drone to the symmetrical axis of the peak, $d_{\min }$ the minimum distance allowed on the terrain, $H(k)$ the height of peak $k$, $R_t$ the maximum extension radius. The calculation formula of $R_t(h)$ is expressed as

$$R_t(h)=(H(k)-h)/\tan \theta$$

(8)

where $\theta$ the slope of the terrain.

The relationship between the variables in the formula of the mountain threat is shown in Figure 2.

2.2.2. Radar Threat

Radar is the most common threat in battlefield scenarios that transmits directional electromagnetic waves to search and analyze objects in a space, obtaining information about the direction, altitude, and speed of objects. The signal strength of the radar is the same in all directions and satisfies the signal-to-noise ratio (SNR) formula as follows:

$$S/N=\frac{P_t{G}_r{G}_{t}P{\lambda }^2\sigma }{{(4\pi )}^3{K}_s{L}_m{B}_n{T}_s{d}_R^4}\hspace{1em}\hspace{1em}$$

(9)

Here, $S/N$ denotes the signal-to-noise ratio of the radar, $P_t$ the transmitter power, $G_r$ the gain of the receiving antenna, $G_t$ the transmit antenna gain, $\sigma$ the effective radar scattering area of the detected target, $\lambda$ the operating wavelength, $K_s$ the Boltzmann constant, $L_m$ the loss factor, $B_n$ the bandwidth, $T_s$ the thermodynamic temperature, and $d_R$ denotes the distance between the drone and radar source. All parameters except $d_R$ can be regarded as constants. Thus, the SNR formula is simplified as follows:

$$S/N=K_a·\frac{\sigma }{d_R^4}\hspace{1em}\hspace{1em}(K_a=\frac{P_t{G}_r{G}_{t}P{\lambda }^2}{{(4\pi )}^3{K}_s{L}_m{B}_n{T}_s})$$

(10)

3. Algorithm Scheduling Technology Based on DQN

3.1. Framework of DQN-SISA

In this section, the training flow of the DQN-SISA model is designed and it is shown in Figure 3.

As shown in Figure 3, in an episode, the agent first greedily selects an action based on the current state S. When the random number is larger than the default greedy value, the model chooses behavior A according to the maximum Q-value. When the random value is less than the greedy value, the model randomly selects the four algorithms. Based on the selected behavior A, the scheduled SI algorithm completes the path planning and outputs immediate reward R, the next point, and provides the next state. Subsequently, if the experience replay buffer is not full, the experience replay buffer should store the experience data in the form $(state,\hspace{0.33em}action,\hspace{0.33em}reward,\hspace{0.33em}next\_reward)$, and the next path point is used to determine the final state. The final state is determined as follows: If the agent does not reach the final target point, the program transfers to the next state according to the relative position obtained from the next path point and then repeats the previous operation. The episode ends if the agent reaches the final target point. When the experience replay buffer reaches its maximum capacity, the agent randomly selects experiences consistent with the batch sample size for learning. At this stage, the parameters of the evaluation network are updated by a gradient descent method.

Applying the DQN model directly to algorithm scheduling is evidently impractical, and the following problems must be considered. The randomness of the optimization algorithm makes forming a fixed mapping relationship between action and state difficult, which affects the learning efficiency of the DQN model and even the convergence ability. The computation times of the SI algorithms also multiply the cost of training the model by tens or thousands of episodes. Therefore, this study proposes two basic principles and builds a node database to solve the above problems and the details are presented in the following sections.

3.1.1. Network Structure of DQN for Path Planning

Deep reinforcement Q-learning is a type of method based on a Markov decision process (MDP) to solve temporal decision problems. Obviously, path planning satisfies the Markov property. When a drone interacts with a threat environment, the point state value at the next moment is only related to the current state and action, irrespective of the previous state and action. The MDP can be represented by a quintuple $<S,\hspace{0.33em}A,\hspace{0.17em}R,\hspace{0.33em}T,\hspace{0.33em}\gamma >$, where $S$ (state) represents an environment consisting of a finite set of known states, and $A$ (action) represents a finite set of actions that can be taken in the behavior space. The reward function $R$ defines the immediate reward for a state transition, and $\gamma$ is the reward discount factor. State transition function $T$ represents the probability distribution function that maps a state–action pair to a possible successor state, known as the policy $\pi$. At time $t$, the policy function of current state $s$ executes behavior $a$ as follows:

$$\pi (a|s)=P(a_t=a|s_t=s)$$

(11)

In Q-learning, the Q-value determines the expected reward obtained by state $s$ after taking action $a$ under policy $\pi$, and its formula $Q^{\pi }(s,a)$ is expressed as:

$$Q^{\pi }(s,a)=E_{\pi }[G_t|s_t=s,a_t=a]=E_{\pi }[{\displaystyle \sum _{k=0}^{\infty }{\gamma }^k}{R}_t+k+1|s_t=s,a_t=a]$$

(12)

The expected reward $Gt$ is related to current and past rewards. The current action provides a delay reward $Rt+1$, and the subsequent reward is multiplied by discount factor $\gamma$, whose number of powers is divided by the interval. In practice, the time-difference control algorithm of the offline strategy of the Q-function is as follows:

$$Q^{\pi }(s,a)=Q^{\pi }(s,a)+\alpha (R+\gamma \max Q^{\pi }(s’,a)-Q^{\pi }(s,a))$$

(13)

The current Q-value of Equation (11) is updated depending on the maximum Q-value of the next state. However, the actual selection of an action–state transition follows a greedy strategy with random selection. The difference between two policies is an important basis for classifying Q-learning as off-policy.

Figure 4 shows the network structure of the DQN model for path planning. The DQN uses a convolutional neural network (CNN) instead of a table to store the Q-values and expands the storage range through function fitting to broaden Q-learning to continuous state spaces. Moreover, two networks are used for interactive learning. The eval network updates network parameters with each action selection and state transition when the target network does not train in real time. After a certain number of training iterations, the target network is updated by copying the parameters of the training network. The eval network is trained by calculating the mean square deviation loss function, and the parameters of the Q-network are updated through gradient backpropagation of the neural network. In addition, the DQN creates the experience replay buffer to accumulate experience data and reduces the correlation between agent actions using the experience data and random sampling. This method helps reduce the overfitting of neural networks and facilitates more extensive learning.

3.1.2. Database of Equidistant Path Points

Similar to the experience replay buffer in the Figure 3, a path point database stores a series of path points obtained by the SI algorithms in the form $(now\_point,\hspace{0.33em}next\_point,\hspace{0.33em}reward)$ that includes the current location of the drone $now\_point$, calculated next point $next\_point$, and $reward$. The path points obtained from one network training can be directly used for the next network training under the condition that the starting point and the target point are unchanged.

For this database, the coverage of the database can be improved by expanding the voyage distance of the initial point, intermediate target, and final target points such that the model using the database is more general. In the actual training process, the DQN model only requires action A and $now\_po\mathrm{int}$ to index the next path point and corresponding reward from the database and finally complete the data exchange and environment interaction. If no interactive data are in database, the SI algorithm corresponding to A is directly invoked to execute real-time path planning, and the data are stored in the database after the solution. Thus, the database continues to expand during training.

The SI algorithm obtains the number of nodes by using the method of dividing coordinates with fixed step. The method of equal division of X-axis coordinates is shown in Figure 5.

Using the X-axis coordinate or Y-axis coordinate alone will cause the risk of algorithm model failure. If only X coordinates are used, the model will fail when the X-axis coordinates of the starting point and target point of the UAV are equal. Moreover, when the change of X coordinates is much smaller than that of Y coordinates, the calculated planned flight track points are too few, resulting in the flight track having no flight value. In order to prevent the above problems, this paper adopts the joint coordinate method. The maximum value of the X coordinate and Y-axis coordinate under a fixed step size is selected as the number of nodes to be planned.

The number of points changes with the distance from the target point. At the same distance, the change of step size will also cause the change of planning dimension. Each time the drone reaches a node, it will call the algorithm to execute the path planning from the current position to the final target point until it reaches the final target point. Arriving at each node is accompanied by path planning with different dimensions and threats. In this manner, the DQN-SISA model can indirectly learn the performance of the SI algorithms in different environments such that the algorithm model has general applicability.

3.1.3. Separation and Optimal Selection Principles

Satisfying the requirements of real-time performance and stability while processing long distances and complex flight-path planning is difficult. To satisfy these real-time requirements, the convergence times of SI algorithms must be limited, which makes it difficult for algorithms to obtain stable convergence solutions. Therefore, determining the mapping relationship between the four algorithms and path points is difficult, which leads to the difficulty of model convergence.

The optimal selection principle is proposed to solve the randomness problem. It means when database data are indexed by action $a$ and $now\_point$, if the path point database has multiple matching data, the model follows the principle of optimal selection and uses a sorting comparison to select the next point with the best reward. The optimal selection principle involves forming a unique mapping relationship between action A and the next state to reduce the influence of the randomness of the SI algorithms on the convergence of the DQN model. Note that the optimal selection principle plays a role in optimizing the DQN training results, and the specific influence is shown in the following comparison of simulation results.

The point database established in the above section corresponds to the proposal of the separation principle. By establishing a path point database, the two processes of SI algorithm path-planning and DQN model training are separated such that the solution results of the SI algorithms can be reused, and the time sunk cost of model training can be significantly reduced.

3.2. Markov Process for DQN-SISA

3.2.1. State and Action Spaces

(1)

State space

The SI algorithm exists as a kind of algorithm which must be abstracted through the state space to establish a real Markov process that reflects the performance difference of SI algorithms. DQN-SISA selects the node coordinates of path planning as the state space. The starting and target points form corresponding relations with the initial and final states, and the state transition of the algorithm is transformed into a typical position state transition. Finally, a complete Markov chain is formed. In order to find the path from the starting point to the target point in any environment, the drone cannot directly use the absolute coordinate information. Directly using the original coordinate information reduces the fitting degree of the model. Solidifying the information of the target point in the model is easy, and reaching the new target point in the new environment will be difficult.

This study uses relative coordinates as $P_{state}$ and its formula is expressed as

$$\begin{array}{l}{P}_{uav}=[x_{uav},\hspace{0.33em}{y}_{uav},\hspace{0.33em}{z}_{uav}]\\ P_t=[x_t, y_t, z_t]\\ P_{state}=[x_{uav}-x_t,\hspace{0.33em}{y}_{uav}-y_t, z_{uav}-z_t]\end{array}$$

(14)

where $P_{uav}$ is the original drone coordinate; $P_t$ is the target coordinate.

The drone has a pre-defined sensing range. With the change of position coordinates, the number of threats and planning dimensions will also change dynamically, thus introducing dynamic environment input for the whole model.

(2)

Action space

DQN-SISA action space is discrete, and the code 0–3 is used to replace the four SI algorithms. The action space is defined as a finite set $\{0, 1, 2, 3\}$.

3.2.2. Episode Reward and Q-Function

DQN-SISA adopts the weighted sum of the path cost and running time of the SI algorithm as the immediate reward $R$, and the episode reward $R_{episode}$ for an episode is the sum of all immediate $R$ rewards for a whole training episode.

Step size can increase or decrease the number of points of different path lengths, which can satisfy the performance selection between high-precision solutions and quick path planning calculations. The real-time reward R formula is denoted as

$$R_{episode}=\sum _t^N{R}_t=-{\displaystyle \sum _t^N({\alpha }_1{J}_{\cos t}+{\beta }_1{J}_{time})}$$

(15)

where $N$ refers to the number of points, $\alpha$ and $\beta$ are the weight coefficients, and the specific value depends on the performance requirements. If the threat environment is complex and the flight path is long, the safe arrival of the drone should be guaranteed first, and the threat and flight-path costs should be reduced such that the size of $\alpha$ can be appropriately increased. Conversely, for short distances and high real-time requirements, the $J_{cost}$ of each point is the path cost is calculated by the algorithm from the current point to the final goal point. A state transfer and real-time reward are obtained when each point is reached.

A fixed step is a partition to isolate the state of each path point, which solves the problem of sparse rewards such that the step obtained by each point has a guiding effect on the final target point. Since the SI algorithm requires solving the minimum $J_{cost}$ as the optimization direction, it is negatively related to the pursuit of the maximum reward by the DQN when interacting with the environment. So, a negative sign has been added to the formula to represent this.

The path cost $J_{cost}$ comprehensively considers the constraints of the drone and the environment. The constraints of the drone include length range $path$, climb angle $angle$, and altitude $heigth$. The threat environmental constraints include: Terrain threats $T_{terrain}$ and radar threats $T_{radar}$. In conclusion, the path planning cost $J_{cost}$ formula is as follows:

$$J_{cost}=w_1{J}_{path}+w_2{J}_{angle}+w_3{J}_{height}+w_4{J}_{threat}$$

(16)

where $w_1, w_2, w_3, w_4$ are the weight coefficients of each cost, and $J_{threat}$ is the total cost of the threat environment constraint, including $T_{mountain}$ and $T_{radar}$.

In Section 2, the formula of the radar SNR showed that the detection threat of radar is inversely proportional to the fourth power of the distance. Thus, the radar threat can be simplified with $T_{radar}$:

$$T_{radar}=\frac{K}{d_R^4}$$

(17)

Here, $K$ is a constant parameter. By combining the mountain threats $T_{mountain}$, we can obtain a new calculation formula $J_{threat}=T_{mountain}+T_{radar}$.

According to the defined real-time reward $R$, the $Q_{\pi }(s_t,a_t)$ of the DQN-SISA model is rewritten as follows:

$$\begin{array}{l}{Q}_{\pi }(s_t,a_t)=R_t+\gamma R_t+1+\dots =\sum _{\tau =0}^N{\gamma }^{\tau }{R}_t+1+\tau \\ \hspace{1em}\hspace{0.33em}=\sum _{\tau =i}^{Nt}{\gamma }^{\tau }[{\alpha }_1(w_1{J}_{path}+w_2{J}_{\cos t}+w_3{J}_{height}+w_4{J}_{threat})+{\beta }_1{J}_{time}]\end{array}$$

(18)

The formula of $Q_{\pi }(s_t,a_t)$ can be understood in Figure 6.

DQN−SISA does not offer an additional reward if the drone reaches a target point, which is convenient for the simulations and comparisons with the solution results of a single SI algorithm.

3.3. Use of the Point Database and Model

In practice, DQN-SISA exists as a black box. During model training, the fixed step is used as a tool to obtain position information, whereas during the process of the DQN-SISA model, the current position is obtained by the on-board sensor as input. The model no longer outputs the next path point of an artificially constructed position state transition but outputs a complete point sequence. If a dynamic change is not evident in the environment, the sequence is directly executed. Since the real-time reward is directly related to the path cost and is selected according to the maximum Q-value, the sequence planned at one time remains relatively optimal. When the drone is in a dynamic environment, an airborne sensor is used to update the environmental data and the flight control system selects fixed time or distance step to call the module to output a sequence of new path points for the new dynamic environment.

4. Simulation Validation

4.1. Parameter Selection

The simulation experiment platform was on a Lenovo notebook AIR14 computer with a running memory of 16 G, AMD Ryzen 4800U CPU, and an AMD integrated graphics card of 512 MB. The DEM had a range of 100 km × 100 km × 300 m, and parameters of the original digital terrain model were set to $a=0.1$, $b=0.01$, $c=1$, $d=0.1$, $e=0.2$, $f=0.4$, and $g=0.02$. The parameters of each SI algorithm were set according those shown in

Table 1. SI algorithm parameter settings.

Algorithm	Population	Iterations	Characteristic Parameters
ACO	30	90	transition probability p0 = 0.2, pheromone volatilization factor rou = 0.8, original pheromone tau0 = 0.3;
PSO	30	90	learning rates c1 = c2 = 2, inertia weight w = 0.6, velocity v = [−1,1];
GWO	30	90	A = 2 − 2t/90
WOA	30	90	a1 = 2 − 2t/90, a2 = −1 − t/90

.

In addition to the parameters of the SI algorithms, the hyperparameters of the DQN were set according those shown in

Table 2. Hyperparameters of the DQN algorithm.

Replay Memory	Episodes	Greedy	Update Interval	Learning Rate	Batch Size
6 × 104	30,000	0.8–1.0	400	0.001	128

.

4.2. Model Validation

In order to simulate a real threat environment, a starting point, intermediate, and final target point were randomly initialized, and 2 radar threats were randomly selected from the map data for path planning. In addition, the simulation results of the four algorithms need to be calculated separately to facilitate data comparison.

DQN-SISA designed in this section consisted of four network layers, with 128 × 128 neurons in the input layer, 128 × 128 neurons in the first fully connected layer, 128 × 64 neurons in the second fully connected layer, and 64 × 4 neurons in the output layer. The activation function chooses the rectified linear activation function (ReLU), and the adaptive formula of the greedy strategy is expressed as

$$Greedy=0.8+\left(episode-10000\right)/10000\times 0.1$$

(19)

With a starting point at (8, 2, 60), intermediate point at (20, 35, 65), and final target point at (40, 80, 75), Figure 6 shows the model reward $R_{episode}$ convergence curve.

In Figure 7, after 100 hundred episodes, which means 10,000 training episodes, the experience replay buffer has sufficient experience data to perform network learning, and the reward rapidly increases and converges. Rewards can converge quickly and level off as the greedy behavior increases. The optimal convergence solution is −322.5979.

For data comparison, ACO, PSO, WOA, and GWO were used separately in sequence to obtain the solving reward of one episode. The rewards $R_{episode}$ obtained were −585.0233, −405.8917, −402.6372, and −409.554, by testing 100 times and taking the average value. Obviously, DQN-SISA achieves a better reward than any single algorithm, with a reward improvement rate of nearly 20% compared with the single optimal solution re−ward of −402.6372. The effectiveness of the algorithm model is verified. The three−dimensional path planning and contour map of each SI algorithm are displayed in Figure 8, and the result of DQN-SISA is shown separately in Figure 9.

Each path point settlement incurs a significant time cost. The path shown in Figure 9 has fewer path points, indicating that DQN-SISA can maximize the efficiency of saving unnecessary computational costs. In addition, this path is smoother than the others.

4.3. Dynamic Environment Verification

This section defines two terms for data analysis: Optimal rate and suboptimal rate. The optimal rate represents the success rate of DQN-SISA in obtaining episode rewards that are better than the four single SI algorithms, and the suboptimal rate is the success rate of model rewards that are second only to the optimal rewards of the four SI algorithms.

Starting or target points are changed and 50 simulations are performed to verify whether DQN-SISA can adapt to the change of planning dimensions. When the node step size is unchanged, different distances mean that the number of nodes to be planned is different, that is, the planning dimensions are different.

Table 3. Change in the position of the intermediate target point and the starting point.

Test Description	Starting and Target Points	Optimal Rate	Suboptimal Rate
Initial start and target points	starting point: (8, 2, 60) target point: (20, 35, 65), (40, 80, 75)	100%	100%
Change intermediate target point	starting point: (8, 2, 60) target point: (35, 75, 65), (40, 80, 75)	98%	100%
Change starting point	starting point: (15, 5, 60) target point: (20, 35, 65), (40, 80, 75)	98%	100%

summarizes the comparison data between the model and single SI algorithm.

Table 3 shows the test results with the path point database. Since the database contains the final target points during DQN-SISA model training, the final target points are unchanged.

The results show that the optimal rate of DQN-SISA is 100%, and the optimal rate of DQN-SISA remains over 95%, with the suboptimal rate near 100%. The existence of a path point database saves solution time. In this case, the time DQN-SISA requires to complete the path planning of all path points from the original starting point to the target point is 2.47 s. This involves 11 points in the state space; thus, the time required using DQN-SISA technology is 0.224 s. Note that the points in the state space are selected from the path points of flight-path planning, and the number of flight-path planning points in this study is three times that of the former.

Variation in the number of threats is also an important indication of a dynamic environment.

Table 4. Changing the number of radar threats.

Test Description	Positions of Radar Threats	Optimal Rate	Suboptimal Rate
Two radar threats	(40, 10, 5), (10, 60, 15)	56%	80%
Three radar threats	(40, 10, 5), (10, 60, 15), (60, 60, 30)	52%	80%
One radar threat	(10, 60, 15)	64%	96%

shows the results of changing the number of radars without the path point database. Therefore, the dynamic environment in Table 4 shows the real simulation results without using the database.

The optimal and suboptimal rates are significantly reduced, but the reward gap of the optimal solution is less than 1%, which still proves DQN-SISA has optimization ability. Furthermore, DQN-SISA still maintains a suboptimal rate of more than 80%. This method effectively avoids the situation where a single algorithm will fail and verifies the success of redundancy design.

4.4. Comparative Performance Study

The optimality principle not only ensures the convergence of the model but also exaggerates the actual results that creates a new problem. For the sake of technical rigor, a separate discussion of the optimal selection principle is still necessary. The experimental results in this section are obtained without the database. In other words, there is no optimality principle.

Firstly, it is necessary to discuss the advantages and disadvantages of the algorithm in different dynamic environments. The optimal rates of each algorithm at different distances are summarized in Figure 10. The optimal rates of each algorithm at different numbers of radars are summarized in Figure 11. It is worth noting that the test distance refers to the Euclidean distance, and all test results are the average values obtained after 50 text times.

Compared with each other, the variation of the number of tested radars has little influence on the optimal rate. In the case of a short distance or low risk, the advantages and disadvantages of algorithms are not obvious.

Table 5. Text data about different distances.

Distance/km	ACO	PSO	WOA	GWO	DQN-SISA
20	−66.9389	−57.0966	−56.9566	−56.9566	−56.8932
40	−223.0057	−196.9844	−197.853	−198.8895	−196.9767
60	−585.0233	−402.6372	−405.8917	−409.554	−400.1349
80	−856.9973	−637.824	−605.5098	−631.9259	−618.375
100	−1331.3168	−975.9081	−932.2784	−948.8938	−913.3382
120	−1688.0116	−1236.6424	−1181.642	1213.7527	−1058.5061

shows specific data about Figure 10 and the new DQN-SISA technology.

Table 6. Text data about different numbers of radars.

Number of Radars	ACO	PSO	WOA	GWO	DQN-SISA
0	−527.8471	−387.6395	−389.5866	−393.403	−372.5513
1	−543.8884	−398.9181	−399.4087	−404.5372	−395.4596
2	−552.2305	−409.0755	−406.0639	−409.2116	−400.9123
3	−592.1842	−411.3604	−409.2053	−414.0574	−375.7854
4	−623.1587	−414.0406	−412.8543	−418.0748	−406.1839
5	−632.8925	−419.6303	−418.0416	−422.0225	−413.3023

shows specific data about Figure 11 and DQN-SISA.

The optimal rates of the four algorithms for each of the above dynamic environments are summarized in a single figure, and the proportion by which DQN-SISA outperforms all SI algorithms is added. The final result is shown in Figure 12.

As shown in Figure 12, DQN-SISA still has high optimal and suboptimal rates for actual route planning without data. Especially, with the increase in the Euclidean distance of the planned path, the proportion of DQNs obtaining the optimal solution also increases steadily.

It is worth noting that under the condition that all algorithms are not invalid, the ACO results are always the worst. It cannot be regarded as a mistake to select ACO as a candidate algorithm. The disadvantage of ACO in accuracy and convergence makes it produce a wider range of path point sequences, which plays an important role in improving the coverage of the path point database. In this manner, ACO has a “catfish effect”.

Considering the actual environment, we synthesize these experiments and change the number and positions of radar threats and the starting and target point positions to create a comprehensive dynamic environment. The number of radar threats is limited to a range of [0–5], and the starting and target points are limited to the range of the model training map. After 100 simulations, we obtain the optimal solutions of each SI algorithm and DQN-SISA. Figure 13 shows the percentages of optimal solutions. The dynamic simulation evidently verifies the feasibility of DQN-SISA.

5. Conclusions

This study proposed an intelligent scheduling technology, DQN-SISA, based on SI algorithms for drone trajectory planning. The differential optimization performance of SI algorithms in different dynamic scenarios is analyzed. DQN-SISA enables drones to obtain relatively optimal solutions in multiple situations by establishing an SI algorithm library and using RL for intelligent scheduling. Simultaneously, the redundancy design of the four SI algorithms can reduce the probability of finding no solution, unlike when using one path planning algorithm, thereby significantly improving drone survivability. For DQN-SISA, a reusable path point database is established, and the SI algorithm solving and DQN model training processes are separate. Without influencing the model applicability, querying data can reduce the influence of the randomness of SI algorithms on the model convergence according to the optimal principle. The simulation results show that this technique can obtain better path point sequences than a single SI algorithm.

The DQN-SISA technology in this study still has shortcomings. The DQN model training depends on the point database of the algorithms, and the coverage of the database directly impacts the model’s optimal rate. In addition to expanding the distance between the initial starting point and target point, improving the regional coverage of the node library such that DQN-SISA can obtain broader path planning solutions requires further study and discussion.