Nomenclature

UAV

unmanned aerial vehicle

BaF

back-and-forth algorithm

PPlanner

Parallel Planner

2.0 Literature summary

Pan et al. introduced the CIJADE that combines the advantageous sides of two DE implementations, namely CIPDE and JADE, with the purpose of planning for a UCAV [Reference Pan, Liu and Chu3]. They tested the CIJADE for a two-dimensional battlefield and proved that the CIJADE is not only better than the CIPDE and JADE, but also outperforms the DE, PSO and ABC algorithms. Each individual of the GWO algorithm was matched with an agent of the Q-learning, which is a reinforcement learning technique by C. Qu et al., and RLGWO was proposed. They also executed the geometrical and global adjustment strategies for boosting the feasibility and smoothness of the discovered UAV paths [Reference Qu, Gai, Zhong and Zhang4]. From the experimental studies, it was seen that the RLGWO is a more sensitive three-dimensional UAV path planner than the GWO and other three GWO variants. In another study, C. Qu et al. developed a hybridisation between the GWO and Symbiotic Organism Search (SOS) algorithm and then presented HSGWO-MSOS as a UAV path planner [Reference Qu, Gai, Zhang and Zhong5]. A fast convergent ABC algorithm (FC-ABC) was introduced by C. Wu et al. and experimented on solving UAV path planning problem [Reference Wu, Huang, Luo and Leng6]. In FC-ABC algorithm, the physical constraints of a UAV were taken into account for exploring the neighbourhood and accelerating the convergence. Chen et al. modified the flower pollination algorithm (FPA) in a manner that a new global update equation is replaced with the existing one and a neighbourhood mechanism is added for further expanding the population diversity by controlling the stagnant solutions [Reference Chen, Pi and Xu7]. Some experiments based on visual comparison stated that the modified FPA obtains more smooth paths than the A^*, APF and RRT.

Zhou et al. used the bat algorithm (BA) with the ABC algorithm for their hybrid PPlanner, also called the improved BA (IBA), and carried out some tests in a three-dimensional environment constructed by taking into account radar, missile, anti-air artillery and climate [Reference Zhou, Gao, Fang and Lan8]. The results of the experiments informed about the superiority of the IBA against the standard BA, ABC and four other improved meta-heuristic guided path planners. Zaslavskii chaotic map was used by P. Wu et al. for increasing the convergence characteristics of the PSO [Reference Wu, Li and Song9]. Xu et al. attempted to adjust the exploration and exploitation balance of the GSA adaptively after employing a procedure that calculated the value of the attenuation factor and Cauchy mutation [Reference Xu, Jiang and Zhang10]. The mixed-strategy-based GSA (MSGSA) showed promising path planning performance when compared to the GWO, gbest-guided GSA (GGSA) and a hybridisation between the PSO and GSA. Jiang et al. solved the UAV path planning problem by executing the GWO with level comparison (GWOLC) that also utilises the $\varepsilon $ -level comparison, partially observable Markov decision process and Monte-Carlo tree search for collision avoidance. The tests carried out proved the strong performance of the GWOLC against the PSO and DE variants [Reference Jiang, Lyu, Li, Guo and Zhang11]. Parallel cooperative coevolutionary GWO (PCCGWO) was introduced by Jarray et al. for addressing the path planning problem. They divided the initial population into sub-populations that are responsible for solving a special part of the problem and assigned to different slave nodes executing in a parallel model [Reference Jarray, Mujahed Al-Dhaifallah and Bouallègue12].

Aslan pioneered a set of studies in which the immune plasma algorithm (IPA), modeling the details of a treatment method, served as a base path optimiser. In the first study, Aslan introduced centrifuge IPA (centIPA) that modifies the plasma collection procedure by guiding the working principles of the centrifuge machine [Reference Aslan13]. Another study published by Aslan and Erkin focused on developing an IPA variant for which multiple populations are run concurrently with the threads [Reference Aslan and Erkin14]. Hospital IPA (hospIPA) that subtly designs how an individual is hospitalised was also introduced by Aslan, and its path planning capabilities on both two- and three-dimensional environments were investigated in detail [Reference Aslan15]. From the detailed investigations, it was concluded that the hospIPA outperforms the other 14 competitors for 70% percent of 20 test cases. Aslan and Demirci integrated a Q-learning-based pandemic measure management approach into the workflow of the IPA and presented Q-LIPA for solving the path planning problem [Reference Aslan and Demirci16]. Aslan and Erkin gave support to the IPA with the power of usage multiple populations and the advantageous sides of a heuristic inherited from the BaF algorithm [Reference Aslan and Erkin17]. In a recent study, Aslan and Erkin changed the solution initialisation schema with a more efficient initialisation schema and then announced the greedy initialiser IPA (gintIPA) [Reference Aslan and Erkin18].

Zhu et al. further improved the spider monkey optimisation (SMO) algorithm with the integration of the cooperation coevolution (CESMO) mechanism that divides the problem into subproblems being solved by a small group of population members [Reference Zhu, Wang and Li19]. They experimented with the CESMO in more than 30 different two-dimensional test cases and reported its superiority when compared to the SMO. Mayfly algorithm (MA) was combined with the adaptive control parameter adjustment strategy, Cauchy mutation and crossover operation for further enhancing the search abilities by Wang et al. and then investigated how the modified MA (modMA) plans paths for a UAV being operated in a two-dimensional environment [Reference Wang, Pan, Yang, Kong, Snášel and Chu20]. The NSEAEO algorithm that is proposed by Niu et al. after embedding the adaptive neighbourhood, updated decomposition and quadratic interpolation operators in the standard AEO was used to calculate two- and three-dimensional UAV paths [Reference Niu, Yan, Wang and Niu21]. Another implementation of the AEO developed by Niu et al. for the path planning problem of UAVs depended on calibrating the instant search space in order to address the disadvantage of the standard AEO regarding slow convergence [Reference Niu, Yan, Wang and Niu22]. Experiments on three-dimensional environments highlighted the excellence of the modernised algorithm over eight other techniques.

Double-layer coding (DLC), an innovative approach for reducing the number of points referenced for drawing a UAV path, was first presented by Jia et al. and then used with a variant of the PSO algorithm [Reference Jia, Qu and Li23]. Experiments conducted over six two-dimensional battlefield scenarios gave sufficient information about the efficiency of the DLC approach. Jia et al. also used the DLC model jointly with the K-neighbourhood-based Fast-Dynamic GWO (K-FDGWO) that is a variant of the GWO executing the K-neighbourhood-based learning, hunger-hunting strategy and fitness distance correlation [Reference Jia, Qu and Li24]. C. Zhang et al. developed a search and rescue (SAR) optimisation algorithm-based path planning technique for which a heuristic crossover accelerating the convergence and maintaining the population diversity is employed [Reference Zhang, Zhou, Qin and Tang25]. Heuristic crossover SAR- (HC-SAR) planned UAV paths for both two- and three-dimensional battlefields, and the obtained results were compared to the results of the SAR and four other meta-heuristics. The first usage of the Aquila optimisation (AO) algorithm for solving the UAV path planning problem was made by Ait-Saadi et al. after supporting it with the simulated annealing (SA) algorithm [Reference Amylia Ait-Saadi, Soukane, Ramdane-Cherif and Benmessaoud Gabis26]. Yu et al. first modified the GWO algorithm, for which the searching routines of the alpha, beta, delta and omega wolves are remodeled, and the DE algorithm, for which the exploitation characteristic is promoted with the help of a rank-based mutation strategy, and then cooperated them for handling the unique difficulties of the path planning problem [Reference Yu, Jiang, Wang and Li27].

Zhang et al. handled the UAV path planning problem with the HDEFWA, which is a strong hybridisation of the DE and fireworks algorithm (FWA) [Reference Zhang, Zhang and Miao28]. The simulations demonstrated the dominance of the HDEFWA against the PSO, DE, FWA and finally the enhanced FWA (EFWA). Honey badger algorithm (HBA) was specialised by Hu with the Bernoulli shift map, horizontal crossing and piecewise decreasing optimal neighbourhood and tested for environments containing circular- or irregular-shaped threat areas [Reference Hu, Zhong and Wei29]. Z. Zhang incorporated the GWO algorithm with the Levy flight to prevent premature convergence and a novel waypoint extraction method based on the cubic B-spline, and validated the potential of the novel technique as a path planner [Reference Zhang, Li, Sun and Huang30]. Q-learning was employed as a selector from multiple search strategies by Ni et al., and its efficiency was analysed over the ABC algorithm. Some simulations containing both two- and three-dimensional environments exhibited the power of the Q-learning-backed search strategy selection approach [Reference Ni, Hu, Fan, Cui and Qi31].

Abdel-Basset et al. converted the conventional description of the geometrical path planning problem into a multi-objective optimisation problem by assuming that the objective function values of the solutions related to the true Pareto front are all zero [Reference Mohamed Abdel-Basset, Sallam, Hezam, Munasinghe and Jamalipour32]. They also solved the mentioned multi-objective description of the path planning problem with an improved slime mould optimisation (SMO) algorithm. For achieving efficient UAV paths in a maritime environment containing the Lamb-Oseen vortex model, Miao et al. represented a white shark optimisation (WSO) algorithm modified by the addition of the rotation-invariant update mechanism. The test carried out on two- and three-dimensional cases illustrated how the WSO-guided path planner outperforms the reptile search algorithm (RSA), spider wasp optimiser (SWO), autonomous group PSO (AGPSO) and standard WSO algorithm [Reference Miao, Li, Yan, Mei, Wu, Zhao, Liu and Zhang33]. Levy flight, opposition-based learning and average-sampling learning were all embedded into the elephant clan optimisation (ECO) by L. Qu et al., and improved ECO (IECO) was announced [Reference Qu, Jia, Li and Fan34]. They controlled the path planning capabilities of the IECO over three battlefield scenarios and proved the obvious advantages of the IECO. Gong et al. first focused on problems with the marine predator algorithm (MPA) stemming from the trapping in the local optimum solutions and premature convergence, and tried to handle them with the circle chaotic mapping, neighbourhood perturbation and lens-imaging-based learning [Reference Gong, Gong, Hong, Li and Xiang35]. They evaluated the path planning potential of the recent MPA (MMPA) and compared the MMPA to the arithmetic optimisation algorithm (AOA), whale optimisation algorithm (WOA), PSO and MPA. Crowned porcupine optimisation (CPO) was chosen by Liu et al. as the base meta-heuristic and then applied to the path planning problem after changing its initialisation schema and candidate generation mechanism with the help of dynamic reverse learning, adaptive step-size perturbation and finally the cross-cutting method [Reference Liu, Ding, Musa and Wu36]. The UAV or UCAV path planners mentioned above are listed chronologically in Table 1.

Table 1.

A summary of the geometrical path planners in chronological order

Table 1. Long description

The table presents a summary of various geometrical path planners listed in chronological order. It includes columns for different battlefield dimensions, path cost factors, and population types. The table has 37 rows and 13 columns. Column headers are: Alg., Two-dim., Three-dim., Enemy thr., Len., Turn., Climb., Obst., Height, Single, and Multiple. Row labels include various algorithms such as CIJADE, RLGWO, HSGWO-MSOS, FC-ABC, NGFPA, IBA, CPSO, MSGSA, GWOLC, PCCGWO, centIPA, CESMO, modMA, NSEAEO, DLCRPSO, HC-SAR, CAOSA, HGWODE, MULIPA, MAEO, HDEFWA, SaCHBA-PDN, DLC-K-FDGWO, WG-GWO, MQABC, hospIPA, HSMA, Q-LIPA, DD-RQIWSO, IECO, MMPA, DUALIPA, GCPO, and gintIPA. Each row indicates whether the algorithm considers two-dimensional and three-dimensional battlefields, various path cost factors (enemy threshold, length, turn, climb, obstacle, height), and population types (single and multiple). Notable trends include the increasing complexity and consideration of multiple factors in more recent algorithms.

3.0 Details of the path planning problem

The mathematical model used to identify an enemy threat when it senses an aerial vehicle, and how a path is calculated and then represented also determines the planning technique being applied. A common model that can be named as the geometrical model utilises a circle with the previously assigned centre coordinate and radius for representing an enemy threat. As easily seen from the representation of an enemy threat by employing a circle, the higher radius values indicate the wider sensing or detecting ranges. When representing a flight path for the geometrical model, a set containing the subtly chosen points that are connected later with the line segments is guided. Assume that a path from the start point, or ${p_s} = \left( {{x_s},{y_s}} \right),$ to the target point, or ${p_t} = \left( {{x_t},{y_t}} \right),$ is calculated for a UAV flying at the fixed altitude by considering the geometrical model. The first operation in the calculation of a path is drawing a line called the reference line between the start and target points [Reference Niu, Yan, Wang and Niu21]. After drawing the reference line, it is divided equally into $D + 1$ line segments with the reference of $D$ segmentation points. The first segmentation point is related to the line ${L_1}$ that passes through the mentioned point and becomes vertical to the reference line, the second segmentation point is related with line ${L_2}$ that passes through the mentioned point and becomes vertical to the reference line, and so on for generating the set $L = \left\{ {{L_1},{L_2}, \ldots,{L_{D - 1}},{L_D}} \right\}$ . The set $L$ has a critical importance on the definition of a UAV or UCAV path. If only one point from each line of the set $L$ is chosen and merged appropriately with the ${p_s}$ and ${p_t}$ , a set of points or $P = \left\{ {{p_s},{p_1}, \ldots,{p_D},{p_t}} \right\}$ can be obtained [Reference Niu, Yan, Wang and Niu21]. By connecting each consecutive pair of points in the set $P$ , a path from the start to the target point can be described.

The horizontal and vertical axis values of the points belonging to the set $P$ can be calculated or assigned immediately with a coordinate system transformation for which the reference line of the original coordinate system corresponds to the horizontal axis of the new coordinate system [Reference Niu, Yan, Wang and Niu21]. When porting the point ${p_k} = \left( {{x_k},{y_k}} \right)$ to the new coordinate system, Equation (1) can be employed [Reference Niu, Yan, Wang and Niu21]. In Equation (1), ${\dot x_k}$ and ${\dot y_k}$ are matched with the $\dot x$ -axis and $\dot y$ -axis values of the point ${\dot p_k}$ representing the transformed counterpart of the point ${p_k}$ . Moreover, while the $\theta $ is used on behalf of the angle between the $x$ -axis and reference line, its value is equal to the result of $arctan(({y_t} - {y_s})/\left( {{x_t} - {x_s}} \right)\!)$ trigonometric operation.

(1) \begin{align}\left[ {\begin{array}{*{20}{l}}{{{\dot x}_k}}\\[3pt]{{{\dot y}_k}}\end{array}} \right] = \left[ {\begin{array}{*{20}{l}}{{cos}{\left( \theta \right)}} \quad {}{{sin}{\left( \theta \right)}}\\[3pt]{ - {sin}{\left( \theta \right)}} \quad {}{{cos}{\left( \theta \right)}}\end{array}} \right] \times \left[ {\begin{array}{*{20}{l}}{{x_k} - {x_s}}\\[3pt]{{y_k} - {y_s}}\end{array}} \right]\end{align}

The coordinate system transformation carried out as detailed above allows the calculation of the $\dot x$ -axis values of the points in the set $P$ . By considering that the lines of the set $L$ pass through the segmentation points dividing the reference line equally, the $\dot x$ -axis value of the $ith$ segmentation point becomes also equal to the $\dot x$ -axis value of a point on the line ${\dot L_i}$ representing the transformed equivalence of the line ${L_i}$ and only a set containing the $\dot y$ -axis values of the determined points, such as $\left\{ {{{\dot y}_s},{{\dot y}_1}, \ldots,{{\dot y}_D},{{\dot y}_t}} \right\}\!,$ is enough to represent a path for the new coordinate system. In Fig. 1, the simplification effect of the coordinate system transformation is depicted visually and two sample paths for a UAV or UCAV system are drawn by connecting the selected points.

Figure 1.

New coordinate system with (a) the discovered UAV paths and (b) their transfer to the initial coordinate system.

The path extracted from the set $P$ should allow the UAV to escape from the sensing or detection ranges of enemy threats, minimise the fuel consumption and handle the turning manoeuvres successfully. In order to evaluate how a path satisfies the requirements about flight safety, fuel consumption and the turning manoeuvres, a score or cost calculation schema detailed with Equation (2) can be taken into account [Reference Niu, Yan, Wang and Niu21]. While the ${C_f}$ term of Equation (2) shows the cost of fuel consumption, the ${C_{th}}$ and ${C_{tr}}$ terms represent the cost of being sensed by the enemy threats and the cost of turning manoeuvres violating the limitations, respectively. For weighting the contribution of the ${C_f}$ , ${C_{th}}$ and ${C_{tr}}$ on the overall path cost abbreviated as $C$ , the ${\lambda _f}$ , ${\lambda _{th}}$ and ${\lambda _{tr}}$ coefficients are utilised by considering that the summation of them must be equal to one [Reference Niu, Yan, Wang and Niu21]. If a path for which the overall cost is less than the overall cost of another path, it is decided that the first candidate is more advantageous by considering at least one of the costs related to fuel consumption, enemy threats and turning manoeuvres.

(2) \begin{align} C = \lambda_{f} C_{f} + \lambda_{th} C_{th} + \lambda_{tr} C_{tr} = \lambda_{f} \int_{0}^{\ell}w_{f}d\ell + \lambda_{th} \int_{0}^{\ell}w_{th}d\ell + \lambda_{tr}\sum_{j=1}^{D}{\varnothing_{j}} \end{align}

The value being assigned to the ${C_f}$ needs the integration of ${w_f}$ from $0$ to the $\ell $ showing the total path length. For integrating the ${w_f}$ from $0$ to the $\ell $ , an approximation with acceptable accuracy that assigns a constant such as $1$ to the ${w_f}$ can be used, and the ${C_f}$ becomes equal to the total length [Reference Niu, Yan, Wang and Niu21]. When the total flight length increases, the value of the ${C_f}$ also increases, emphasising the higher fuel consumption. The integration of the ${w_{th}}$ can be further simplified by driving an approximation. Given that the ${p_i}$ and ${p_j}$ are two adjacent points in the set, $P$ and ${L_{ij}}$ is the length of the line segment between these two points. Moreover, it is important to declare that the line segment of length ${L_{ij}}$ is divided into ten equal partitions, and the first, third, fifth, seventh and ninth partition points are marked. If the $kth$ enemy threat with the grade or danger level of ${t_k}$ detects the UAV tracking the line segment of length ${L_{ij}}$ , the cost related to the $kth$ enemy threat for the considered line segment or ${C_{th,\left( {ij} \right),k}}$ can be determined as in Equation (3) [Reference Niu, Yan, Wang and Niu21]. The distance between the $kth$ enemy threat centre and the first partition point is matched with the $d_{0.1,i,k}^4$ in Equation (3), the distances between the $kth$ enemy threat centre and the other labeled partition points are matched with the $d_{0.3,i,k}^4$ , $d_{0.5,i,k}^4$ , $d_{0.7,i,k}^4$ and $d_{0.9,,k}^4$ for the same equation. By checking all of the enemy threats and line segments with the purpose of whether a UAV or UCAV will be sensed or not and then summing the partial costs, the value of ${C_{th}}$ is estimated.

(3) \begin{align}{C_{th,\left( {ij} \right),k}} = \frac{{{L_{ij}}{t_k}}}{5}\left( {\frac{1}{{d_{0.1,i,k}^4}} + \frac{1}{{d_{0.3,i,k}^4}} + \frac{1}{{d_{0.5,i,k}^4}} + \frac{1}{{d_{0.7,i,k}^4}} + \frac{1}{{d_{0.9,i,k}^4}}} \right)\end{align}

A UAV or UCAV system employed for carrying out the task by flighting on the calculated path should handle the different turning manoeuvres properly. However, each aerial vehicle has some kinematic limitations affecting the turning manoeuvrability. In order to evaluate whether the turning manoeuvre can be handled properly or not, the angle that will be determined with Equation (4) is checked [Reference Niu, Yan, Wang and Niu21]. While the three adjacent points of the set $P$ are showed as ${p_i}$ , ${p_j}$ and ${p_k}$ in Equation (4), $\overrightarrow {{p_i}{p_j}} $ and $\overrightarrow {{p_j}{p_k}} $ are two vectors found by referencing the mentioned points. The ${p_i}$ , ${p_j}$ and ${p_k}$ are replaced with the ${p_s}$ , ${p_1}$ and ${p_2}$ when the first three points are controlled. Similarly, ${p_i}$ , ${p_j}$ and ${p_k}$ are replaced with the ${p_{D - 1}}$ , ${p_D}$ and ${p_t}$ when the last tuple is controlled. If the absolute value of the angle ${A_i}$ or $\left| {{A_i}} \right|$ is less than the previously determined maximum turning angle or ${\emptyset _{max}}$ , any cost because of this manoeuvre is not reflected. Otherwise, the absolute value of the angle ${A_i}$ also assigned to the ${\emptyset _i}$ is added to the ${C_{tr}}$ for stating the failure of the manoeuvre.

(4) \begin{align}{A_i} = arctan\left( {\frac{{\parallel \overrightarrow {{p_i}{p_j}} \times \overrightarrow {{p_j}{p_k}} \parallel }}{{\overrightarrow {{p_i}{p_j}} \cdot \overrightarrow {{p_j}{p_k}} }}} \right)and{\rm{\;\;}}{\emptyset _i} = \left\{\begin{array}{ll}|A_i|, & |A_i| \gt {\emptyset_{\max}},\\[3pt]0, & \textit{otherwise.}\end{array}\right\}\end{align}

4.0 Details of the PPlanner algorithm

The idea behind the definition of a UAV or UCAV path with a set of points whose members are connected later in the geometrical model of the path planning problem opens new gates to researchers for developing heuristics to be used when choosing the path-forming points. The recent BaF algorithm, executing a strong greedy heuristic, was introduced by Aslan, and its capability as a single path planner and positive contribution as a population initialiser for a meta-heuristic algorithm were proven [Reference Aslan2]. The BaF algorithm conducts a preprocessing operation for each member of the set $\dot L$ in a manner that the line ${\dot L_1}$ is divided equally into $D + 1$ subsegments and the subsegmentation points are stored by the set ${\dot P^1}$ , the line ${\dot L_2}$ is divided equally into $D + 1$ subsegments and the subsegmentation points are stored by the set ${\dot P^2}$ and so on. The greedy heuristic of the BaF algorithm selects the point $\dot p_j^i$ from the set ${\dot P^i}$ where index $i$ is equal to or greater than $2$ after assuming that the point $\dot p_j^i$ is outside the effect ranges of all enemy threats and the $\dot p_j^{i - 1}$ from the set ${\dot P^{i - 1}}$ is chosen previously [Reference Aslan2]. When the point $\dot p_j^i$ from the set ${\dot P^i}$ is inside the effect range of an enemy threat, the heuristic searches the other members of the same set to find a point that is the nearest one to the $\dot p_j^{i - 1}$ and outside the ranges of all enemy threats if possible. By executing the mentioned greedy heuristic of the BaF algorithm, the distance between two sequential points and the angle for the turning manoeuvre are tried to be minimised intrinsically while the flight safety is guaranteed fully or partially [Reference Aslan2]. The formal description of how the selection is conducted by the linguistically detailed heuristic for the point set ${\dot P^i}$ where index $i$ is equal to or greater than $2$ is given in Equation (5). In Equation (5), $T$ represents the set of enemy threats and $d$ is a function calculating the Euclidean distance between two points.

(5) \begin{align}{\dot p_i} = \left\{ {\begin{array}{{l}} \quad \quad \quad{\dot p_j^i, \quad \quad \quad \quad \quad \quad\quad \quad \quad\mathop {\quad \quad {d}{\left( {t,\dot p_j^i} \right)}}\limits_{\forall t \in T} \gt {r_t}}\\[5pt]\quad \quad \quad {\dot p_k^i, \quad \quad \quad\mathop {\quad \quad {d}{\left( {t,\dot p_k^i} \right)}}\limits_{\forall t \in T} \gt {r_t} \wedge {d}{\left( {{{\dot p}_{i - 1}},\dot p_k^i} \right)} \lt \mathop {{d}{\left( {{{\dot p}_{i - 1}},\dot p_m^i} \right)}}\limits_{\forall \dot p_m^i \ne \dot p_k^i \in {{\dot P}^i} - \left\{ {\dot p_j^i} \right\}} }\\[5pt]{first{\rm{\;}}of{{\dot P}^i} - \left\{ {\dot p_j^i} \right\},\quad \quad \quad \quad \quad \quad \quad otherwise}\end{array}} \right\}\end{align}

The execution of the heuristic should be managed more carefully for the first line and the set storing the subsegmentation points related to the same line. Because only the transformed start point or ${\dot p_s}$ exists, the heuristic tries to select a point from the set ${\dot P^1}$ that should be the nearest one to the ${\dot p_s}$ and outside the sensing ranges of all enemy threats if possible [Reference Aslan2]. The formal description of how the selection is completed by the executed heuristic for the point set ${\dot P^1}$ is summarised in Equation (6).

(6) \begin{align}{\dot p_1} = \left\{\begin{array}{ll}\dot p_j^1, \quad \mathop {{d}{\left( {t,\dot p_j^1} \right)}}\limits_{\forall t \in T} \gt {r_t} \wedge {d}{\left( {{{\dot p}_s},\dot p_j^1} \right)} \lt \mathop {{d}{\left( {{{\dot p}_s},\dot p_m^1} \right)}}\limits_{\forall \dot p_m^1 \ne \dot p_j^1 \in {{\dot P}^1}},\\ \dot p_1^1, \quad \quad \quad \quad \quad \quad \quad otherwise\end{array}\right\}\end{align}

The path drawn from the start to the target with the help of the chosen points by the heuristic can contain more eligible line segments that are near the start point of the UAV or UCAV system. As an expected result, if the heuristic approach is executed in the reverse direction, the path drawn from the target to the start with the help of the chosen points by the heuristic can contain more eligible line segments that are near to the target point, and two backbone paths being combined later for generating better candidates can be obtained. Assume that the set $\bar P$ contains the chosen points by the heuristic when it executes from the start to the target, and the set $\overline {\bar P} $ contains the chosen points by the heuristic when it executes from the target to the start. In order to further improve the path corresponding to the set $\bar P$ with the assistance of the set $\overline {\bar P} $ , Equation (7) can be served. While ${\bar p_j}$ and ${\overline {\bar p} _j}$ are matched with the $jth$ elements of the $\bar P$ and $\overline {\bar P} $ , the newly calculated $jth$ element being used on behalf of the ${\bar p_j}$ is shown as ${\hat p_j}$ in Equation (7). If the ${\hat p_j}$ improves the overall path quality when it is used for the $jth$ element of the set $\bar P$ , a replacement between the ${\bar p_j}$ and ${\hat p_j}$ is carried out, and useful information provided by the ${\overline {\bar p} _j}$ is transferred sufficiently. The path corresponding to the set $\overline {\bar P} $ can be further improved by simply referencing the procedure used for updating the set $\bar P$ as detailed above. In order to calculate a value for the $jth$ element of the set $\overline {\bar P} $ , Equation (7) can be employed again. If the ${\hat p_j}$ improves the overall path quality when it is taken for the $jth$ element of the set $\overline {\bar P} $ , a replacement between the ${\overline {\bar p} _j}$ and ${\hat p_j}$ is carried out, and some line segments on the path derived from the set $\overline {\bar P} $ are strengthened.

(7) \begin{align}{\hat p_j} = \frac{{\left( {{{\bar p}_j} + {{\overline {\bar p} }_j}} \right)}}{2}{\rm{\;\;}}and{\rm{\;\;}}j = 1,2, \ldots,D\end{align}

The efficiency of the greedy heuristic introduced by the BaF algorithm and the novel procedure proposed to increase the quality of the backbone paths extracted from the sets $\bar P$ and $\overline {\bar P} $ can be improved with the usage of the computational power of a multi-core or multi-threaded processor. If each thread or core becomes responsible for calculating a UAV or UCAV path by executing the mentioned greedy heuristic and subtly designed update procedure with the specialised search space whose lower and upper bounds are determined individually, the probability of finding more robust paths is increased because of the different local and global search capabilities of the threads. Assume there are $N$ threads and the lower and upper bounds of the entire search space for the lines of the set $\dot L$ are marked as the $LB$ and $UB$ , respectively. In order to assign the specialised lower and upper bounds of the thread for which the rank or index is shown as $n$ , Equations (8) and (9) can be considered. For both of these equations, ${\rm{\Delta }}d$ is used to adjust the lower and upper bounds of the search spaces related to the $n$ indexed thread and calculated as $\left( {UB - LB} \right)/\left( {2 \times \left( {N + 1} \right)} \right)$ operation.

(8) \begin{align}L{B_n} = L + \left( {n - 1} \right) \times {\rm{\Delta }}d \\[-28pt] \nonumber \end{align}

(9) \begin{align}U{B_n} = UB - \left( {n - 1} \right) \times {\rm{\Delta }}d\end{align}

The mathematical model used to adjust the bounds overlaps the search spaces of the threads centrally. As an expected result of this subtle configuration, the threads with consecutive indexes or ranks get a chance of continually processing the regions containing the promising path candidates. Another possible contribution of the proposed bound adjustment technique is related to the different local and global search capabilities of the threads. While the threads with the relatively small indexes or ranks try to plan paths by selecting points that are distributed on the longer line segments, the threads with the relatively high indexes or ranks are responsible for finding paths by selecting points that are distributed on the shorter line segments. If the battlefield is protected by enemy threats located close to each other, the probability of finding more eligible paths increases for the threads with the smaller indexes because of their extended lower and upper bounds. On the contrary, if the battlefield is protected by the enemy threats located away from each other, the probability of finding more eligible UAV paths increases for the threads with the higher indexes because of their reduced lower and upper bounds. An illustration of how four threads determine their search spaces and calculate the first backbone paths according to the greedy heuristic for a hypothetical battlefield with the number of segmentation points or $D$ equalised to $5$ is given in Fig. 2.

Figure 2.

Execution of the (a) first, (b) second, (c) third and (d) fourth threads for calculating the backbone paths from ${\dot p_s}$ to ${\dot p_t}$ .

When the search bounds for the threads are assigned, each one performs the heuristic for generating two backbone paths being improved later with the introduced update procedure and the best path of $N$ threads is reported as the final solution. Due to executing a set of simultaneous threads each has its own search bounds for finding UAV or UCAV paths with the inherited selection heuristic and the proposed update procedure. The novel technique is called the PPlanner.

5.0 Experimental studies

The properties of the enemy threats, their numbers, the positions of the start and target points and finally the dimensionality of the path planning problem are all effective on the solving performance of the proposed technique or method. For this reason, three different battlefield scenarios for which the details of enemy threats, start and target points presented in Table 2 were chosen [Reference Niu, Yan, Wang and Niu21]. The number of segmentation points or $D$ was set to $10$ , $15$ , $20$ and $25,$ and four test cases per scenario, for which the ${\lambda _f}$ , ${\lambda _{th}}$ and ${\lambda _{tr}}$ coefficients are fixed to $0.4$ , $0.5$ and $0.1,$ were generated [Reference Niu, Yan, Wang and Niu21]. It is important to declare that the difficulties of the test cases increase not only with higher values being assigned to the $D$ , but also the special description details of the geometrical path planning problem about the line set $L$ and the necessity of selecting points located on the members of the same line set. Even though the values being assigned to the $D$ are relatively small, such as $10$ or $15$ , some of the lines in the set $L$ intersect directly with the circles representing the enemy threats and determining a path-forming point outside the sensing range of the enemy threats is not possible. For each test case, the PPlanner was run by assigning $1$ , $2$ , $4$ , $6$ , $8$ , $12$ , $16$ , $20$ , $24$ , $32$ , $48$ , $56$ and $64$ constants to the number of threads. While the cost of the obtained paths by the PPlanner for Scenario- $1$ was given in Table 3, the costs of the obtained paths by the PPlanner for Scenario- $2$ and Scenario- $3$ were given in Tables 4 and 5, respectively. In Tables 3–5, smaller cost values represent better path candidates calculated after execution of the PPlanner.

Table 2.

Information about the battlefields used in the experiments

Table 2. Long description

A table titled ‘Information about the battlefields used in the experiments’ presents data on three different battlefield scenarios. The table has four columns: Sc., Threat centre, Threat radius, Threat grade, and Start-target point. It contains three rows of data. Row 1: Sc. 1, Threat centre (12, 48), (24, 33), (27, 58), (30, 70), (55, 80), (59, 52), (70, 34), (70, 65), Threat radius 12, 9, 9, 10, 9, 10, 12, 7, Threat grade 1, 12, 3, 2, 7, 9, 13, 5, Start-target point (10, 15) (80, 75). Row 2: Sc. 2, Threat centre (20, 70), (25, 19), (25, 39), (45, 20), (47, 41), (50, 61), (70, 53), (75, 74), (78, 20), Threat radius 20, 9, 9, 9, 9, 9, 9, 9, 20, Threat grade 7, 5, 5, 5, 5, 5, 5, 5, 7, Start-target point (5, 5) (95, 95). Row 3: Sc. 3, Threat centre (10, 50), (20, 20), (30, 42), (30, 80), (50, 55), (60, 10), (60, 80), (65, 38), (75, 65), (90, 80), Threat radius 10, 9, 8, 10, 10, 10, 10, 11, 8, 10, Threat grade 8, 6, 5, 4, 7, 6, 7, 6, 8, 10, Start-target point (10, 0) (80, 100).

Table 3.

Results of the PPlanner with different number of threads for Scenario- $1$

Table 3. Long description

A table titled ‘Results of the PPlanner with different number of threads for Scenario-’ presents the performance of the PPlanner algorithm under varying numbers of threads. The table has 12 rows and 5 columns. The columns are labeled ‘Num. of threads’, ‘10’, ‘15’, ‘20’, and ‘25’. The rows are labeled with the number of threads ranging from 1 to 64. Each cell contains a numerical value representing the cost of the obtained paths by the PPlanner. Notable trends include the cost values generally decreasing as the number of threads increases, with some variations across different thread counts. For example, the cost values for 1 thread are consistently higher compared to those with more threads. The table provides a detailed comparison of how the number of threads affects the performance of the PPlanner algorithm in Scenario.

Table 4.

Results of the PPlanner with different number of threads for Scenario- $2$

Table 4. Long description

A table titled ‘Results of the PPlanner with different number of threads for Scenario-’ presents the performance of the PPlanner algorithm under varying numbers of threads. The table has 12 rows and 5 columns. The columns are labeled with the number of threads (10, 15, 20, 25) and the rows are labeled with the number of threads (1, 2, 4, 6, 8, 12, 16, 20, 24, 32, 48, 56, 64). Each cell contains a numerical value representing the cost of the obtained paths by the PPlanner. Notable trends include the cost values generally decreasing as the number of threads increases, with some variations across different thread counts. For example, the cost values for 1 thread are consistently higher compared to those with more threads. The table provides a detailed comparison of how the number of threads affects the performance of the PPlanner algorithm.

Table 5.

Results of the PPlanner with different number of threads for Scenario- $3$

Table 5. Long description

A table titled ‘Results of the PPlanner with different number of threads for Scenario-’ presents the performance of the PPlanner algorithm under varying conditions. The table has 12 rows and 5 columns. The columns are labeled ‘Num. of threads’, ‘10’, ‘15’, ‘20’, and ‘25’. The rows are labeled with the number of threads used, ranging from 1 to 64. Each cell in the table contains a numerical value representing the cost of the obtained paths by the PPlanner for different numbers of threads. Notable trends include the cost values generally decreasing as the number of threads increases, with some variations across different thread counts. For example, the cost values for 1 thread are consistently higher compared to those with more threads. The table provides a detailed comparison of how the number of threads affects the performance of the PPlanner algorithm in Scenario-.

Figure 3.

The paths of the PPlanner and BaF for (a) $10$ -, (b) $\;15$ -, (c) $20$ - and (d) $25$ -dimensional cases of the Scenario- $1$ .

The results given in Tables 3, 4 and 5 provide critical information about the relationship between the number of threads and qualities of the solutions for the PPlanner algorithm. When the number of threads is increased, the paths found by the PPlanner become more qualified. While the PPlanner should be started with $64$ threads for $15$ - and $20$ -dimensional cases of Scenario- $1$ , $10$ - and $20$ -dimensional cases of Scenario- $2$ , it obtains better paths with $56$ threads for $10$ - and $25$ -dimensional cases of Scenario- $1$ . In addition to this, using $24$ and $32$ threads for $15$ - and $25$ -dimensional cases of Scenario- $2$ and $20$ and $48$ threads for $10$ - and $25$ -dimensional cases of Scenario- $3$ allows the PPlanner to schedule more eligible paths than the other thread configurations. The design principles of the PPlanner focus on utilising the computational power of a multi-threaded system and guaranteeing that each thread has its own search space determined according to the assigned index. The threads with the smaller indexes or ranks are willing to scan path candidates in longer line segments. Also, the threads with the higher indexes or ranks are willing to scan path candidates in narrower line segments. As an expected result of the different local and global search characteristics of the threads, the probability of planning qualified paths is intrinsically boosted with the increasing number of them.

Figure 4.

The paths of the PPlanner and BaF for (a) $10$ -, (b) $\;15$ -, (c) $20$ - and (d) $25$ -dimensional cases of the Scenario- $2$ .

Figure 5.

The paths of the PPlanner and BaF for (a) $\;10$ -, (b) $\;15$ -, (c) $\;20$ - and (d) $25$ -dimensional cases of the Scenario- $3$ .

Another critical extraction from the results reported in Tables 3–5 for the PPlanner is about the effect of the newly introduced update procedure. Even though the threads calculate their backbone paths within the different lower and upper bounds, the qualities of the final paths found by the PPlanner with varying thread configurations are relatively close to each other. The mentioned stability of the PPlanner, although the thread configuration varies, has a direct relationship with the update procedure redesigning the points of the discovered backbone paths. By transferring some points from the first backbone to the second backbone path, if the overall path quality is improved or transferring some points from the second backbone to the first backbone path if the overall path quality is improved, the PPlanner gets a chance to maintain the extra search operations and yield better final solutions than the controlled backbone paths. In Figs 3, 4 and 5, the paths found by the PPlanner with $32$ threads for Scenario- $1$ , Scenario- $2$ and $48$ threads for Scenario- $3$ and the paths found by the standard implementation of the BaF are depicted.

In order to determine the position of the PPlanner among other heuristic or meta-heuristic-based path planners, a set of comparative studies should be carried out. For this purpose, the PPlanner algorithm was compared with the BaF and 14 other meta-heuristic-based path planners, including the ABC, GA, GAPSO, MFO, SSA, PFA, SBO, SCA, ECTLBO, HSGWO-MSOS, CIPSO, GWO, AEO and NSEAEO [Reference Aslan2, Reference Niu, Yan, Wang and Niu21]. When experimenting with the meta-heuristic algorithms, the colony or population size was taken equal to $30$ and the maximum evaluation number used as the termination criterion was set to $6,000$ [Reference Aslan2, Reference Niu, Yan, Wang and Niu21]. Each test case belonging to a battlefield scenario was solved $30$ times by the mentioned meta-heuristics and the best path obtained at the end of a run and its cost were recorded [Reference Aslan2, Reference Niu, Yan, Wang and Niu21]. The path costs of the PPlanner, which started by using $32$ threads, were compared with the path costs of the BaF and the best, worst, mean best path costs found after guiding the recorded values of the meta-heuristic algorithms over Table 6 for the test cases of Scenario- $1$ , Table 7 for the test cases of Scenario- $2$ and finally Table 8 for the test cases of Scenario- $3$ . Because of the deterministic characteristics of the PPlanner and BaF, there is no discrimination between the best, worst and mean best path costs and their standard deviations are equal to zero.

The comparison between the PPlanner and other algorithms over Tables 6–8 shows the promising performance of the PPlanner. The proposed approach outperforms all of the tested techniques and gets ranked as the best path planner for 6 of 12 test cases in total. Moreover, while the PPlanner gets ranked as the second-best planner for two of six test cases and lags only behind the NSEAEO, it gets ranked as the third best path planner and lags behind the AEO and NSEAEO algorithms for four remaining cases and guarantees a place among the top three techniques. A thread of the PPlanner makes $2 \times D + 2$ calls to the function calculating the cost of a path as in the BaF algorithm and consumes $2 \times D + 2$ evaluations until finalising the operations. If the PPlanner is started with $32$ threads for $10$ - and $15$ -dimensional cases of the battlefield scenarios, it consumes $704$ and $1,024$ evaluations. Similarly, if the PPlanner is started with $32$ threads for $20$ - and $25$ -dimensional cases of the battlefield scenarios, it consumes $1,344$ and $1,664$ evaluations. Even though the PPlanner makes roughly $8.5$ and $5.8$ times fewer function calls for $10$ - and $15$ -dimensional test cases and $4.4$ and $3.6$ times fewer function calls for $20$ - and $25$ -dimensional test cases than the executed meta-heuristics, the strong sides inherited from the BaF, usage of different threads searching within the individual bounds determined according to the ranks or indexes and the update procedure transferring the information between the initial paths conform to the challenging aspects of the problem more and let the PPlanner outperform the vast majority of the competitors.

An assumption about that the execution time of the PPlanner should be relatively close to the execution time of the BaF algorithm can be made by considering the parallel working of the threads. However, the fork and join operations of the threads that include the assignment of them to the cores, allocation of memory spaces, execution of the instructions and returning to the main thread bring an extra burden to the completion duration of a run for the PPlanner algorithm. In order to investigate whether or not the extra burden stemming from the existence of multiple threads causes a significant amount of incrementation on the execution time of the PPlanner when compared to the execution time of the BaF, both of them coded in C programming language had  $30$ independent runs. At the end of each run, the time in terms of seconds was recorded. The organisation of the threads for the PPlanner was managed over the pthreads library and a computer with dual Intel Xeon E5-2682 v4 processors was employed. When the average execution times and related standard deviations given in Tables 9–11 are controlled, it is seen that the initial assumption to do with the execution time of the PPlanner keeps the correction if the number of threads is chosen by considering the capabilities and limitation of the used processor. Because each processor in the test system is capable of handling $32$ threads concurrently, the configurations of the PPlanner containing more than $32$ threads can also require a synchronisation between the processors, and a run of the PPlanner takes slightly longer than a run of the same algorithm configured with fewer threads and a run of the BaF. When the PPlanner with $32$ threads takes $0.005$ s longer than the BaF algorithm at most for the test cases of Scenario- $1$ , the same configuration of the PPlanner takes $0.006$ s longer than the BaF algorithm at most for the test cases of Scenario- $2$ and $0.006$ s longer than the BaF algorithm at most for the test cases of Scenario- $3$ . Nevertheless, it is important to declare that the PPlanner with $32$ threads outperforms the BaF for all 12 cases.

Table 6.

Comparison between the PPlanner and other techniques for Scenario- $1$

Table 6. Long description

Panel A: Line graph comparing path costs of PPlanner and BaF against various meta-heuristic algorithms. The x-axis represents different test cases, and the y-axis represents path costs. The graph shows the best, worst, and mean best path costs for each algorithm. Panel B: Bar chart comparing the performance of PPlanner and BaF with other meta-heuristic algorithms. The x-axis lists the algorithms, and the y-axis shows the path costs. The chart highlights the deterministic nature of PPlanner and BaF, with no standard deviation in their path costs.

Table 7.

Comparison between the PPlanner and other techniques for Scenario- $2$

Table 7. Long description

The table compares the performance of the PPlanner algorithm against 15 other meta-heuristic-based path planners across different scenarios. It includes metrics such as best, worst, mean, standard deviation, and rank for each algorithm. The table is divided into sections based on the number of dimensions (D) in the scenario, with sections for 10D, 15D, and 20D. Each section lists the performance metrics for each algorithm, including PPlanner, BaF, ABC, GA, GAPSO, MFO, SSA, PFA, SBO, SCA, ECTLBO, HSGWO-MSOS, CIPSO, GWO, AEO, and NSEAEO. The table also includes an average rank and overall rank for each algorithm. The data is presented in a structured format with rows and columns, where each row represents a different performance metric and each column represents a different algorithm. The table provides a comprehensive comparison of the algorithms’ performance, highlighting the best, worst, and mean path costs, as well as the standard deviation and rank for each algorithm.

Table 8.

Comparison between the PPlanner and other techniques for Scenario- $3$

Table 8. Long description

Panel A: A bar graph comparing the path costs of PPlanner with BaF and other meta-heuristic-based path planners. The x-axis represents different test cases, and the y-axis represents path costs in centimeters. The legend indicates the different algorithms, including ABC, GA, GAPSO, MFO, SSA, PFA, SBO, SCA, ECTLBO, HSGWO-MSOS, CIPSO, GWO, AEO, and NSEAEO. PPlanner shows lower path costs compared to most other algorithms. Panel B: A line graph showing the best, worst, and mean best path costs for PPlanner and BaF across different scenarios. The x-axis represents different scenarios, and the y-axis represents path costs in centimeters. PPlanner consistently shows lower path costs with no standard deviation due to its deterministic nature.

The strong status of the PPlanner among other techniques and its promising performance can be understood from the results reported in Tables 6, 7 and 8. However, it is still important to validate the

Table 9.

Execution times of the PPlanner and BaF in terms of seconds for Scenario- $1$

Table 9. Long description

A table comparing execution times of various algorithms for different scenarios. The table has 16 columns and 25 rows, including headers and row labels. The columns are labeled as HSGWO, PPlanner, BaF, ABC, GA, GAPSO, MFO, SSA, PFA, SBO, SCA, ECTLBO, MSOS, CIPSO, GWO, AEO, and NSEAEO. The rows are labeled with numbers 10, 15, 20, and 25, indicating different scenarios. Each cell contains values for Best, Worst, Mean, Std., and Rank for each algorithm and scenario. The table provides a detailed comparison of the performance of different algorithms in terms of execution times, highlighting the best, worst, mean, and standard deviation values, as well as their respective ranks.

mentioned promising performance of the PPlanner with an appropriate statistical test. For this purpose, the Wilcoxon signed-rank test with the significance level ( $\rho $ ) set to $0.05$ was chosen. If the $\rho $ value calculated after referencing the results of the compared techniques is less than $0.05$ , it is assumed that the difference between them causes a statistical significance in favour of one of these competitors. The indicators belonging to the Wilcoxon signed-rank test for the comparison between the PPlanner, and other techniques were given in Table 12. In Table 12, the $Z$ indicator is used on behalf of the test statistics. Moreover, the representation of the sum of ranks showing the PPlanner is better than its rival is made with the $W - $ term, while the representation of the sum of ranks showing the PPlanner lags behind the other method is made with the $W + $ term. When the results of Table 12 are investigated, it is seen that the PPlanner is statistically better than 13 of all 15 techniques. Only for the difference between the PPlanner and AEO and NSEAEO is not enough to state that the PPlanner is statistically better than AEO or NSEAEO. Nevertheless, it is critical to emphasise that the PPlanner performs better than the AEO for 9 of 12 test cases and better than the NSEAEO for 6 of 12 test cases, even though the AEO and NSEAEO consume at least $3.6$ times more function evaluations than the PPlanner.

Table 10.

Execution times of the PPlanner and BaF in terms of seconds for Scenario- $2$

Table 10. Long description

Table 9 presents the execution times of the PPlanner and BaF algorithms in seconds for different scenarios. The table is divided into multiple rows and columns, with the number of threads ranging from 10 to 64. Each row corresponds to a different number of threads, and each column corresponds to a different scenario. The table includes the mean execution time in seconds and the standard deviation for each combination of threads and scenario. The data shows that the execution time increases with the number of threads and varies across different scenarios. The table provides a detailed comparison of the performance of the PPlanner and BaF algorithms under different conditions.

Table 11.

Execution times of the PPlanner and BaF in terms of seconds for Scenario- $3$

Table 11. Long description

A table comparing execution times of various algorithms for different scenarios. The table has 10 rows and 17 columns. Column headers are D, PPlanner, BaF, ABC, GA, GAPSO, MFO, SSA, PFA, SBO, SCA, ECTLBO, MSOS, CIPSO, GWO, AEO, NSEAEO. Row labels are 10 Best, 10 Worst, 10 Mean, 10 Std., 10 Rank, 15 Best, 15 Worst, 15 Mean, 15 Std., 15 Rank, 20 Best, 20 Worst, 20 Mean, 20 Std., 20 Rank, 25 Best, 25 Worst, 25 Mean, 25 Std., 25 Rank, Average Rank, Overall Rank. The table presents the best, worst, mean, standard deviation, and rank values for each algorithm across different scenarios. Notable trends include the PPlanner and BaF algorithms showing relatively close execution times, with the PPlanner sometimes outperforming the BaF. The table also includes comparisons with other techniques like HSGWO, ABC, GA, GAPSO, MFO, SSA, PFA, SBO, SCA, ECTLBO, MSOS, CIPSO, GWO, AEO, and NSEAEO. The data is presented row-wise, with each row providing specific values for the algorithms and scenarios.

Table 12.

Statistical comparison between the PPlanner and other techiques

Table 12. Long description

A table comparing execution times of PPlanner and BaF across different numbers of threads. The table has 10 columns and 17 rows. The columns are labeled as Num. of threads, 10, 15, 20, and 25. The rows are labeled as BaF, 1, 2, 4, 6, 8, 12, 16, 20, 24, 32, 48, 56, and 64. Each row contains mean execution times in seconds and standard deviations for different numbers of threads. Row 1: BaF, Mean (s) 0.010, 0.010, 0.013, 0.015, Std. 0.001, 0.001, 0.001, 0.002. Row 2: 1, Mean (s) 0.010, 0.010, 0.012, 0.013, Std. 0.001, 0.001, 0.002, 0.002. Row 3: 2, Mean (s) 0.010, 0.011, 0.013, 0.015, Std. 0.001, 0.001, 0.002, 0.002. Row 4: 4, Mean (s) 0.011, 0.012, 0.013, 0.016, Std. 0.001, 0.001, 0.002, 0.002. Row 5: 6, Mean (s) 0.011, 0.012, 0.013, 0.016, Std. 0.001, 0.001, 0.002, 0.002. Row 6: 8, Mean (s) 0.011, 0.013, 0.014, 0.017, Std. 0.001, 0.001, 0.001, 0.002. Row 7: 12, Mean (s) 0.012, 0.014, 0.016, 0.018, Std. 0.001, 0.001, 0.001, 0.002. Row 8: 16, Mean (s) 0.012, 0.014, 0.015, 0.018, Std. 0.001, 0.001, 0.002, 0.002. Row 9: 20, Mean (s) 0.013, 0.014, 0.016, 0.018, Std. 0.001, 0.001, 0.001, 0.002. Row 10: 24, Mean (s) 0.013, 0.015, 0.016, 0.019, Std. 0.001, 0.001, 0.001, 0.001. Row 11: 32, Mean (s) 0.014, 0.016, 0.018, 0.019, Std. 0.001, 0.001, 0.001, 0.002. Row 12: 48, Mean (s) 0.015, 0.017, 0.019, 0.022, Std. 0.001, 0.002, 0.003, 0.001. Row 13: 56, Mean (s) 0.015, 0.017, 0.021, 0.024, Std. 0.001, 0.001, 0.001, 0.001. Row 14: 64, Mean (s) 0.016, 0.018, 0.021, 0.025, Std. 0.001, 0.003, 0.002, 0.001.