Automation and Robots for Disaster Response

Intelligent Scheduling Technology of Swarm Intelligence Algorithm for Drone Path Planning

By inergency On Mar 25, 2024

[ad_1]

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} τ_{i j} (t + 1) = (1 - ρ) τ_{i j} (t) + Δ τ_{i j} (t) \\ Δ τ_{i j} (t) = \sum_{k = 1}^{m} Δ τ_{i j}^{k} (t) \end{array}$

(1)

where $τ_{i j} (t)$ denotes pheromone intensity at time $t$ and $ρ$ 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} ν = ω \cdot v + c_{1} r_{1} (p B e s t - x) + c_{2} r_{2} (g B e s t - x) \\ x = x + v \end{array}$

(2)

Here, $w$ is the inertia weight, $c_{1}$ and $c_{2}$ are the learning rates, $p B e s t$ the historical optimal position of the corresponding particle, and $g B e s t$ 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_{α} = | C_{1} \cdot X_{α} (t) - X (t) |, D_{β} = | C_{2} \cdot X_{β} (t) - X (t) |, \\ D_{ξ} = | C_{3} \cdot X_{ξ} (t) - X (t) | \\ X_{1} = X_{α} - A_{1} \cdot D_{α}, X_{2} = X_{β} - A_{2} \cdot D_{β}, \\ X_{3} = X_{ξ} - A_{3} \cdot D_{ξ} \\ X (t + 1) = \frac{X_{1} + X_{2} + X_{3}}{3} \end{array}$

(3)

Here, $X_{α}$ , $X_{β}$ , and $X_{δ}$ denote the position vectors of wolves $α$ , $β$ , and δ in the current population; $X$ is the location of individual grey wolves; $D_{α}$ , $D_{β}$ , and $D_{δ}$ 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 = | \vec{C} {\vec{X}}^{*} (n) - \vec{X} (n) | \\ \vec{X} (n + 1) = {\vec{X}}^{*} (n) - \vec{A} \cdot \vec{D} \\ \vec{X} (n + 1) = \vec{d} e^{b I} \cos (2 π l) + {\vec{X}}^{*} (n) \end{array}$

(4)

Here, $n$ denotes the number of iterations, $\vec{A}$ and $\vec{C}$ the updated coefficient vectors, ${\vec{X}}^{*} (n)$ the optimal position of the whale at iteration $n$ , $\vec{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.

|\vec{d}| = | \vec{C} {\vec{X}}^{*} (n) - \vec{X} (n) |

represents the distance between the whale and its prey. The role of random coefficient A is similar to that in GWO. When

|A| > 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 = |C \times {\vec{X}}_{r a n d} - \vec{X}| \\ \vec{X} (n + 1) = {\vec{X}}_{r a n d} - \vec{A} \cdot \vec{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.

[ad_2]