Page 100 - Read Online

Mai et al. Intell Robot 2023;3(4):466-84 I http://dx.doi.org/10.20517/ir.2023.37 Page 7 of 19

4. PATH PLANNING BASED ON DUAL STRATEGY ACO ALGORITHM
The traditional ACO algorithm often relies on a stochastic mechanism to choose the next node, which can lead
to an indiscriminate search during the initial phase of the algorithm and result in slow convergence. While
the algorithm does possess positive feedback traits, if it initially identifies a sub-optimal solution, this positive
feedback can subsequently trap the algorithm in a local optimum. To address the aforementioned issues, en-
hancements are implemented in two critical aspects: (1) the method for selecting candidate nodes; and (2) the
rules governing pheromone updates.

4.1 State transition strategy of deterministic selection
While searching for the next feasible node, the heuristic values for candidate nodes are determined using the
Equation ℎ = ∗ ∗ . The specific equations for S, M, and D are provided in Equations (11)-(13),
respectively.
{
1 ℎ +1 ≥ + ℎ
= (11)
0 ℎ

1
= (12)
1 + ℎ +1
1
= √ √ (13)
2 2 2 2 2
1 + Δ + Δℎ + 1 + ( − +1 ) + ( − +1 ) + (ℎ − ℎ +1 )

Among them, S signifies the accessibility of the next node, taking the value 1 if the node is reachable and 0
otherwise. ℎ is the safety threshold, and H represents the height of the mountain node. M represents the
probability of selecting a candidate node, +1, +1, and ℎ +1 represent the 3D coordinates of the candidate
node, , , and are the 3D coordinates of the mountain node, D is the correlation coefficient between
two nodes, Δ represents the interpolation of the y-axis of the two nodes, and Δ represents the interpolation
of the z-axis of the two nodes.

The traditional ACO algorithm employs a probabilistic transition strategy where transition probabilities be-
tween nodes are calculated, and the roulette method is commonly used to select the next node. As the algo-
rithm progresses into its later stages, paths with clear advantages become more evident, and a deterministic
node transition strategy can be applied to expedite algorithm convergence. In light of this, we have designed
a novel state transition function to choose the subsequent node at the later stage of the algorithm, as shown in
Equation (14):

 ∈ [ ( )] [ ( )] ≤ 0


 [ ] [ ]

 
   ( ) ( ) (14)

( ) =  ∑ ∈


 ∈ [ ( )] [ ( )] ≥ 0
 
 
 0 ℎ
 

where q is a tunable parameter within the interval [0, 1] that represents the probability of using a deterministic
nodetransitionstrategy. 0 determinestheprobabilityofselectingeitherthedeterministicorrandomselection
modes. Consequently, 0 plays a crucial role in influencing the convergence speed and the global search
capability. A higher value of 0 favors the likelihood of choosing the deterministic mode for selecting the
next point, resulting in an accelerated convergence speed. However, this comes at the cost of reduced global
search capability. Conversely, a smaller 0 inclines the path shift towards the random mode, introducing more
randomness in the selection process and enhancing the global search capability. A rule for setting the 0
value must be established to balance between deterministic and random modes. 0 is calculated as shown in