LAV Path Planning by Enhanced Fireworks Algorithm on Prior Knowledge

As shown in the original FWA paper [24], FWA outperformed SPSO and CPSO significantly and converged in most cases towards the function optimum already after a few iterations. However, when applying FWA on shifted functions the results worsen progressively with increasing distance between function optimum and origin of the search space. By investigating the operators of FWA, it is found that conventional FWA has the following drawbacks:

(1)For functions which have their optimum at FWA will find the optimal solution very fast. However, not due to the intelligence of the algorithm but due to the specific mapping and Gaussian mutation operators which map/create sparks close to the origin;

(2) For functions which have their optimum far away from the origin, FWA has to face the two drawbacks that the mapping operator rebounds most solutions which are out of the search space to locations which are far away from the function optimum, and that the mutation operator creates many sparks at locations close to the origin (for example, again far away from the optimum).

(3) FWA has a high computational cost per iteration.

As shown in [25], Y Tan et al. made 5 major changes in FWA and got the EFWA. The 5 changes are shown as follows.

EFWA is a significant improvement of the recently developed FWA. And it eliminates the drawbacks of conventional FWA. As is shown in the experimental evaluation, with the exception of one benchmark function, the results of EFWA are very stable and remain almost unaffected even if the optimum of the function is shifted towards the edges of the search space. EFWA shows significant improvements over conventional FWA. Compared to SPSO, which turned out to be rather sensitive to increasing shift values, EFWA achieves very stable results, and has the advantage that its results do not deteriorate even for large shift values. In terms of computational cost, the new selection operator is faster by a factor of 6 compared to the distance based selection operator of conventional FWA.

TAN also proposed AFWA (an adaptive version of FWA) [29] and dynFWA( dynamic version of FWA) [30], AFWA improvement is similar with FAC-PSO, and dynFWA improvement is also similar with other intelligent algorithm. Although adaptive algorithm can improve computational efficiency to some extent, but to significantly improve the efficiency of path planning, takes full advantage of a priori knowledge of the battlefield environment, directly reduce the optimization EFWA space. Therefore, this article uses EFWA, and apply the prior knowledge of the battlefield environment to determine its optimization space.

We use the same path coding in the literature [1], as shown in Figure 1. In this way, the path from the starting node P to the target node P_f can be described as follows:

Path={Ps,P1,P2,⋯,Pn,Pf}$$\begin{array}{} \displaystyle Path = \{P_s,P_1,P_2, \cdots,P_n,P_f\} \end{array}$$(1)

Fig. 1

Therefore, each point P_i(i = 1, 2, ···, n) can be expressed using only 1 parameter,its distance to the straight line PsPf¯$\begin{array}{} \displaystyle \overline{P_{s}P_{f}} \end{array}$.The benefits of this kind of path coding is that two-dimensional problem can be represented with a one-dimensional variable to facilitate the problem model solving.

Optimization space involves determining the threat weight calculations. To facilitate the presentation, Let T_i denote the threat i, and set its data structure as:

Ti={TiP,TiR,TiD,TiV,TiTPsPf,TiEIP,TiEDTPsPf}$$\begin{array}{} \displaystyle T_{i}= \{T_i{^P}, T_i{^R},T_i{^D},T_i{^V},T_i{^{TP_{s}P_{f}}},T_i{^{EIP}},T_i{^{EDTP_{s}P_{f}}}\} \end{array}$$(2)

Where TiP$\begin{array}{} \displaystyle T_i{^P} \end{array}$ denotes the position of T_i, T R_i, denotes the radius of T_i, TiD$\begin{array}{} \displaystyle T_i{^D} \end{array}$, denotes the threat degree of T_i, TiV$\begin{array}{} \displaystyle T_i^V \end{array}$, denotes the velocity of T_i, TiTPsPf$\begin{array}{} \displaystyle T_i^{T{P_s}{P_f}} \end{array}$, denotes the distance between T_i and PsPf¯$\begin{array}{} \displaystyle \overline {{P_s}{P_f}} \end{array}$, TiEIP$\begin{array}{} \displaystyle T_i^{EIP} \end{array}$ denotes the ability of influencing the path of T_i, 1 denotes it can, -1 denotes it can not, TiEDTPsPf$\begin{array}{} \displaystyle T_i^{EDT{P_s}{P_f}} \end{array}$ denotes the effective threat degree of T_i to PsPf¯$\begin{array}{} \displaystyle \overline {{P_s}{P_f}} \end{array}$, and PsPf¯$\begin{array}{} \displaystyle \overline {{P_s}{P_f}} \end{array}$ denotes the line between P_f and P_s. TiP,TiR,TiD,TiV$\begin{array}{} \displaystyle T_i^P,T_i^R,T_i^D,T_i^V \end{array}$ is the information already known in the battlefield, TiEIP$\begin{array}{} \displaystyle T_i^{EIP} \end{array}$ is initialized to -1. TiTPsPf$\begin{array}{} \displaystyle T_i^{T{P_s}{P_f}} \end{array}$ can be calculated with a simple geometric method:

TiTPsPf=|Pf−PsTPi−Ps|/‖Pf−Ps‖$$\begin{array}{} \displaystyle T_i{^{TP_sP_f}}=\begin{vmatrix}P_f-P_s\\TP_i-P_s\end{vmatrix}/\begin{Vmatrix}P_f-P_s\end{Vmatrix} \end{array}$$(3)

The calculation of TiEDTPsPf$\begin{array}{} \displaystyle T_i^{EDT{P_s}{P_f}} \end{array}$ is as follows:

TiEDTPsPf=[TiD⋅Su/Si TiD⋅Sd/Si]$$\begin{array}{} \displaystyle T_i{^{EDTP_sP_f}}=\begin{bmatrix}T_i{^D}\cdot S_u/S_i~&~T_i^{D}\cdot S_d/S_i \end{bmatrix} \end{array}$$(4)

Here, S_u and S_d denote the effective threat area of T_i up and down PsPf¯$\begin{array}{} \displaystyle \overline{P_{s}P_{f}} \end{array}$ respectively. S_i is the area of T_i, and the method of calculating [S_u S_d] is as Formula (5).

[SuSd]={[Su=Si−SdSd=cos-1(|TiTPsPf/TiR|)⋅(TiR)−TiTPsPf⋅(TiR)2−(TiTPsPf)2],if|TiTPsPf|<TiRandTiTPsPf≥0[Su=cos−1(|TiTPsPf/TiR|)⋅(TiR)2−TiTPsPf⋅(TiR)2−(TiTPsPf)2Sd=Si−Su],if|TiTPsPf|<TiRandTiTPsPf<0[Si⋅(TiR)2/(TiTPsPf)20],ifTiR≤|TiTPsPf|≤3⋅TiRandTiTPsPf≥0[0Si⋅(TiR)2/(TiTPsPf)2],ifTiR≤|TiTPsPf|≤3⋅TiRandTiTPsPf<0[0 0],if|TiTPsPf|≥3⋅TiR$$\begin{array}{} \displaystyle \left[ {{S_u}{S_d}} \right] = \left\{ \begin{array}{*{20}{l}} {\left[ {{S_u} = {S_i} - {S_d}{S_d} = {\rm{co}}{{\rm{s}}^{{\rm{ - 1}}}}\left( {\left| {T_i^{T{P_s}{P_f}}/T_i^R} \right|} \right) \cdot \left( {T_i^R} \right) - T_i^{T{P_s}{P_f}} \cdot \sqrt {{{\left( {T_i^R} \right)}^2} - {{\left( {T_i^{T{P_s}{P_f}}} \right)}^2}} } \right],} \hfill \\ \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad{if{\rm{ }}\left| {T_i^{T{P_s}{P_f}}} \right| \lt T_i^R{\rm{and}}T_i^{T{P_s}{P_f}} \ge 0} \hfill \\ {\left[ {{S_u} = {\rm{co}}{{\rm{s}}^{ - 1}}\left( {\left| {T_i^{T{P_s}{P_f}}/T_i^R} \right|} \right) \cdot {{\left( {T_i^R} \right)}^2} - T_i^{T{P_s}{P_f}} \cdot \sqrt {{{\left( {T_i^R} \right)}^2} - {{\left( {T_i^{T{P_s}{P_f}}} \right)}^2}} {S_d} = {S_i} - {S_u}} \right],} \hfill \\ \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad{if{\rm{ }}\left| {T_i^{T{P_s}{P_f}}} \right| \lt T_i^R{\rm{and}}T_i^{T{P_s}{P_f}} \lt 0} \hfill \\ {\left[ {{S_i} \cdot {{\left( {T_i^R} \right)}^2}/{{\left( {T_i^{T{P_s}{P_f}}} \right)}^2}0} \right],if{\rm{ }}T_i^R \le \left| {T_i^{T{P_s}{P_f}}} \right| \le 3 \cdot T_i^R{\rm{and}}T_i^{T{P_s}{P_f}} \ge 0} \hfill \\ {\left[ {0{\rm{ }}{S_i} \cdot {{\left( {T_i^R} \right)}^2}/{{\left( {T_i^{T{P_s}{P_f}}} \right)}^2}} \right],if{\rm{ }}T_i^R \le \left| {T_i^{T{P_s}{P_f}}} \right| \le 3 \cdot T_i^R{\rm{and}}T_i^{T{P_s}{P_f}} \lt 0} \hfill \\ {\left[ {0{\rm{ 0}}} \right],if\left| {T_i^{T{P_s}{P_f}}} \right| \ge 3 \cdot T_i^R} \hfill \\ \end{array}\right. \end{array}$$(5)

T^TTLof the threats of upper and lower sides to PsPf¯$\begin{array}{} \displaystyle \overline{P_{s}P_{f}} \end{array}$ can calculated as formula(6).

TTTL=∑i=1nTiEDTPsPf$$\begin{array}{} \displaystyle {T^{TTL}} = \sum\limits_{i = 1}^n {T_i^{EDT{P_s}{P_f}}} \end{array}$$(6)

Then the potential side P^PD of the optimal path is,

PPD=sign(TTTL(1,1)−TTTL(1,2))∈{1,−1}$$\begin{array}{} \displaystyle {P^{PD}} = sign\left( {{T^{TTL}}\left( {1,1} \right) - {T^{TTL}}\left( {1,2} \right)} \right) \in \left\{ {1, - 1} \right\} \end{array}$$(7)

Here, the value of sign is 1 when the independent variable is non-negative, and is -1 when the independent variable is negative. 1 denotes that the optimal path exists on the upper side of PsPf¯$\begin{array}{} \displaystyle \overline{P_{s}P_{f}} \end{array}$, then -1 denotes the optimal path exists on lower side of PsPf¯$\begin{array}{} \displaystyle \overline{P_{s}P_{f}} \end{array}$ . In order to more intuitively describe, with the data in Table 2 in literature [1], P^PD = −1 can be calculated, that is that the optimal path is on the lower side of PsPf¯$\begin{array}{} \displaystyle \overline{P_{s}P_{f}} \end{array}$ as shown in Fig.2.

Table 2

Average computation time(s)

Fig. 2

Known the potential side of optimal path, the upper and lower limits of the initial population can be calculated. Let B^I be the upper and lower limits of the initial population, the data structure is as follows,

BI={(BiIU,BiID,BiIP)|1≤i<n}$$\begin{array}{} \displaystyle {B^I} = \left\{ {\left( {B_i^{IU},B_i^{ID},B_i^{IP}} \right)|1 \le i \lt n} \right\} \end{array}$$(8)

Where, BiIU$\begin{array}{} \displaystyle B_i^{IU} \end{array}$ denotes the upper limit of seed i,BiID$\begin{array}{} \displaystyle B_i^{ID} \end{array}$ denotes the lower limit of seed I, BiID$\begin{array}{} \displaystyle B_i^{ID} \end{array}$ denotes the position locating the upper and lower limit, and dimB^I < n .The method of calculating B^I is as the pseudo-codes in Fig.3.

Fig. 3

ΔL in Fig.3 can be calculated as follows,

ΔL=‖PfPs¯‖/(n+1)$$\begin{array}{} \displaystyle \Delta L=\begin{Vmatrix}\overline{P_fP_s}\end{Vmatrix}/(n+1) \end{array}$$(9)

Based on the results calculated in section 3.2, the upper and lower initial limits of the population can be retained as shown in Fig.4. To facilitate the analysis, it is rotated to the horizontal axis as shown in Fig.5.

Fig. 4

Fig. 5

After the upper and lower initial limits of the population retained, the path still cannot be optimized with EFWA. Upper and lower limits of the population on each dimension B_i need to be calculated according to the initial limits. The structure of B_i is set as follows.

Bi={BiU,BiD},i=1,2,⋯,n$$\begin{array}{} \displaystyle {B_i} = \left\{ {B_i^U,B_i^D} \right\},i=1,2,\cdots,n \end{array}$$(10)

Here, B^U denotes upper limit, B^Ddenotes lower limit, dimB = n. The method of calculating B is as pseudo-codes in Fig.6.

Fig. 6

Based on the retained results in section 3.3, the transition results are got from step 1 to step 3 in Fig.6, and are shown in Fig.7. Then linear interpolation completed by step 4, the final results of upper and lower limits are retained, and are shown in Fig.8.

Fig. 7

Fig. 8

o increase the probability that final upper and lower limits cover the optimal path, numbers of iterative calculations need to be done between start point and target point, and the final upper and lower limits are retained in which contains the optimal path the probability is highest. That is, optimization space is got finally. Iterative calculation process is as shown in Fig.9.

Fig. 9

Table 1

Information of 2D threatening objects

Because of use the path coding in [1], in order to facilitate comparison, we use the same objective function and simulation settings in [1] too. Programming Environment is MATLAB 2014b. CPU in our computer is P4, its frequency is 2.8GHz, and memory is 2G.

The results of path planning are as shown in 10, and the data of consuming time are as shown in 4.1.

The number of threats is still 8, set the threat positions as TiP∈[10,80]$\begin{array}{} \displaystyle T_i^P \in \left[ {10,80} \right] \end{array}$and the threat radius as TiP∈[10,15]$\begin{array}{} \displaystyle T_i^P \in \left[ {10,15} \right] \end{array}$, and set the dimension n of path as 30. Six groups of representative results are shown in Figure 11.

Fig. 10

The setting of dynamic path planning is still the same as [1], and set the dimension as 20. To improve the performance of the path planning, the iterative number is increased to 300. The LAV paths by the EFWA on Prior Knowledge at steps 0, 5, 10, and 15 are shown in Fig.12, which implies the feasibility of EFWA on Prior Knowledge under moving threatening conditions. The time consuming of each step is shown in Table 4.

Fig. 12

Table 3

time consuming of each step(s)