Sage Journals: Discover world-class research

Abstract

The traditional Harris Hawks optimization algorithm is prone to the local shortest path, slow search speed and poor path accuracy in indoor mobile robot path planning. For the above problems, a multi-strategy improvement of the Harris Hawks optimization algorithm (MIHHO) is proposed. In this study, a Chebyshev chaotic mapping strategy is used to increase the diversity of the Harris Hawk population, improve the global search performance of the Harris Hawk algorithm, and prevent being trapped in the locally optimal path. A fusion exploration mechanism is proposed to fuse the discovery mechanism of the sparrow algorithm with the exploration mechanism of the HHO. Then the influence factor E is improved to improve the algorithm’s search accuracy and search efficiency, and finally, in the design of a dynamic Lévy flight strategy, which accelerates the convergence speed of the algorithm and improves the robot planning speed. Simulation results show that the proposed MIHHO method exhibits better search performance in path planning, improved planning efficiency, and superior quality of planned paths.

Keywords

Chebyshev chaos mapping Harris Hawks optimization algorithm improved energy factor mobile robot path planning

Introduction

In indoor mobile robots, path planning is an important technique that essentially plans the shortest path from the current to the target position with specific application requirements or optimization criteria (stability, path minimization, energy consumption, etc.).Path planning techniques are used in many fields, such as indoor sweeping robots,¹ logistics robots,² food delivery robots,³ agricultural robots,⁴ etc. Path planning is further divided into local planning and global planning. The traditional international path planning methods include A* algorithm,^5,6 Dijkstra algorithm,^7,8 RRT algorithm,^9,10 etc. Local path planning is when the robot collects information about the current environment and moves from the current position to the next node. Standard local path planning methods include the APF^11,12 and DWA.^13,14 Traditional planning methods have good robustness, but the computation is more complex, and the computation time increases exponentially as the map increases; some are only suitable for some simple scenario planning, and the generality is poor.

Intelligent bionic algorithms are widely used in path planning, for example, particle swarm algorithm (PSO),^15,16 grey wolf algorithm (GWO),^17,18 and whale algorithm (WOA),^19,20 due to their simple structure better performance for easy understanding, less reliance on mathematical models, and high exploration and exploitation capabilities. The algorithm searches and shortens the planned paths by seeking the optimal iterations until it reaches the maximum number of iterations set and solves a short and feasible path, which gradually becomes the heuristic branch of the path planning method. HHO^21,22 is a new intelligent bionic algorithm characterized by fewer parameters, generality for easy application and simple structure. It is suitable for using and exploring various complex environments and is widely used in various engineering problems. Harun²³ and Chen²⁴ improved the search speed of the algorithm by reducing the position update strategy in the HHO and adding the DE mechanism in the search phase, respectively, but did not take into account the problem of balancing the global and local search of the algorithm, and the search accuracy was low. Vikram²⁵ and Kashif et al. ²⁶ both fused HHO with the Sine Cosine Algorithm (SCA) to strengthen the exploration ability in the development phase of the algorithm and through comparison with other algorithms and application engineering problems, it was concluded that the exploration performance of the algorithm was improved – still, the algorithm’s ability to solve multidimensional and complex issues needed to be stronger. Li et al. ²⁷ added the improved Rosenbrock method to the development phase of the HHO. Kang²⁸ added an improved Brownian motion strategy in the development phase, and Zhou²⁹ added a differential evolution strategy and an update strategy based on the bioenergy consumption pattern. All three methods improve the local search ability of the algorithm to avoid falling into the local optimums. Still, the weak global search ability in the search phase of the algorithm has yet to be considered, which is prone to significant errors.

Wang³⁰ and Guo³¹ used an elite-based non-dominated sorting mechanism to select the optimal solution set strategy for the Harris hawk population, respectively, and added quasi-inverse learning and quasi-reflective learning strategies to HHO and verified that the global search ability of the two improved algorithms was improved through test functions and engineering problems. Still, due to the complexity of the computational process, the algorithms have reduced the search speed, and it is more time-consuming in the face of more complex nonlinear problems. Liu³² set up a multi-subgroup square neighborhood topology and fixed replacement probability to guide the individuals in the subgroups to be able to forage randomly in both vertical and horizontal directions to strengthen the information exchange among the individuals in each subgroup. Wu³³ introduced a flexible decreasing strategy in HHO. The two improved algorithms improved the balanced performance of the global and local searches. Still, the overall search capability of the algorithms was reduced, and the accuracy could have been better.

The analysis of the already improved HHO algorithms mentioned above concludes that they still need to improve in solving a wide range of unknown and complex problems. In this paper, an improved Harris Hawkes optimization algorithm (MIHHO) is proposed with the following main contributions:

Using Chebyshev chaotic mapping initial Harris Hawk population and introducing the discoverer mechanism of Sparrow’s algorithm in the exploratory phase to enrich the population’s diversity and improve the algorithm’s global search capability.

Improve the energy factor E to strengthen the regulation of global search and local search by adjusting the occupancy ratio to enhance the generality and universality of the algorithm.

introduce a dynamic nonlinear strategy to regulate the Levy flight to improve the algorithm search stability and efficiency.

Using eight test functions in MATLAB to do adaptation degree-seeking comparison experiments and three different complexity indoor environments to do path planning simulation comparison experiments, it is verified that MIHHO is better in adaptation degree-seeking ability. The problems of local shortest path and search performance of the robot in path planning are effectively improved. The path quality is significantly enhanced by comparing with the three improved HHO^34–36 four other types of algorithms.^16,18,20,37

The remaining chapters of this paper are organized as follows: Chapter 2 introduces the basic principles and mathematical model of the Harris Hawks algorithm; Chapter 3 analyzes the shortcomings of the Harris Hawks algorithm and proposes improvement strategies; Chapter 4 verifies the effectiveness of the improvements by testing functions and path planning experiments; Chapter 5 concludes.

HHO algorithm

The Harris Hawks optimization algorithm²² was proposed in 2019 by Heidari et al. The algorithm mimics the predatory behavior of the Harris Hawks. The predatory tactics of this animal are mainly surprise attacks, taking into account the ability and state of escape of the prey, using different forms of encirclement and swooping to kill, divided into three main phases: the search phase, the search and exploitation conversion phase, and the exploitation phase. The search phase mainly performs a global search, the search and exploitation conversion phase reconciles the global and local tracking, and the exploitation phase conducts a provincial examination. Based on the energy factor E variation, alternating global and regional exploration is performed, E∈[−2,2].

(1) Exploration phase. At this time|E|≥1, the Harris Hawks move, observe and search for prey or are perched among the Hawks with the following specific mathematical model expression:

X (t + 1) = {\begin{matrix} \begin{matrix} X_{rand} (t) - r_{1} | X_{rand} (t) - 2 r_{2} X (t) | & q \geq 0.5 \end{matrix} \\ \begin{matrix} (X_{rabbit} (t) - X_{m} (t)) - r_{3} (lb + r_{4} (ub - lb)) & q < 0.5 \end{matrix} \end{matrix}

(1)

Where: $X (t)$ means the position of the Harris Hawks in the tth generation. $X (t + 1)$ means the position of the Harris Hawks at generation t + 1. $r_{1} r_{2} r_{3} r_{4}$ are random numbers between [0,1].ub indicates the upper limit of the population.lb denotes the lower limit of the population. $X_{rand}$ means a random individual position in the current population. $X_{rabbit}$ means the position of the best individual in the current population. $X_{m} (t)$ represents the average part of the population in generation t. The expression is as follows:

X_{m} (t) = \sum_{i = 1}^{N} \frac{X_{i} (t)}{N}

(2)

Where: N means the population size and i denotes the i-th Harris Hawks.

(2) Exploration and exploitation transition phase. The Harris Hawks switch between the search and exploitation phases according to the escape energy of the prey, controlled by the energy factor E. The mathematical model expression is as follows:

E = 2 E_{0} (1 - t / T)

(3)

Where: t means the current number of iterations, T means the maximum number of iterations, and $E_{0}$ means a random number between [−1,1].

(3) Exploitation stage. At this point|E| < 1, the Harris Hawks search phase was converted to the exploitation phase. According to the type of prey caught and the different prey escape abilities, Heidari scholars designed four types of roundups: hard roundup, soft roundup, progressive fast dive soft roundup, progressive fast dive hard roundup and based on the energy factor E and the change of random number r between [0,1] to choose which roundup to use.

Soft roundup

When 0.5<|E|≤1 and r ≥0.5, the escape energy of the prey is relatively vital, and a period of roundup is needed to consume the prey energy, and then the Harris Hawks find the right time to capture, and the specific mathematical model expression is as follows:

X (t + 1) = Δ X (t) - E | J X_{rabbit} (t) - X (t) |

(4)

Where: $X (t)$ means the difference in distance between the current Harris Hawks position and the prey position, and J means a random number between [0,2].

Hard siege

When |E|<0.5 and r ≥0.5, the prey energy is low, and the Harris Hawks can quickly be successfully rounded up and surrounded by a strong attack form with the following specific mathematical model expressions:

X (t + 1) = X_{rabbit} (t) - E | Δ X (t) |

(5)

Progressive fast swoop soft siege

When 0.5<|E|≤1 and r <0.5, the prey has the energy to escape, then the Harris Hawks flock adopts encircling siege to consume the prey’s energy and wait for an opportunity to attack, and its specific mathematical model expression is as follows:

Y = X_{rabbit} (t) - E | J X_{rabbit} (t) - X (t) |

(6)

If the prey roundup fails, the Harris Hawks flock performs a random wandering whose specific mathematical model expression is as follows:

Z = Y + S \times LF (D)

(7)

Where: LF (D) means the D-dimensional Lévy flight function and S means the random vector on $(0, 1)^{D}$ .The mathematical model merges the expressions as follows:

X (t + 1) = {\begin{matrix} Y \begin{matrix} F (Y) < F (X (t)) \end{matrix} \\ Z \begin{matrix} F (Z) < F (X (t)) \end{matrix} \end{matrix}

(8)

Progressive fast swoop hard roundup

When |E|<0.5 and r <0.5, the prey energy is too low and can quickly be rounded up, at which time the Harris Hawks flock directly attacks with the following specific mathematical model expressions:

Y = X_{rabbit} (t) - E | J X_{rabbit} (t) - X_{m} (t) |

(9)

If there is a failed roundup, the random wandering is continued and refer to “(7)” is executed. The mathematical model merges the expressions as follows:

X (t + 1) = {\begin{matrix} Y \begin{matrix} F (Y) < F (X (t)) \end{matrix} \\ Z \begin{matrix} F (Z) < F (X (t)) \end{matrix} \end{matrix}

(10)

Problem analysis and improvement strategies

Chebyshev chaos mapping strategy

When HHO computationally solves the optimization problem, it takes a random way to initialize the population, which cannot guarantee the uniformity of population distribution, and the global exploration ability³⁰ and search accuracy of the algorithm are low,³³ and it is easy to fall into local optimum,²⁹ resulting in sub-optimal paths planned by the robot. Chebyshev chaotic mapping has good disorder and ergodicity, which is applied in the initial population of HHO to improve the population distribution, the algorithm’s global exploration ability and the optimization-seeking accuracy. As shown in Figure 1, the random distribution of Chebyshev chaotic mapping in the interval of [−1,1] has a good overall effect.

Figure 1.

Chebyshev chaos mapping diagram.

The specific mathematical expression to apply to the initial population is as follows:

X (t + 1) = \cos (\cos^{- 1} \cdot X (t))

(11)

Where: $X (t)$ means the position of the Harris Hawks in the tth generation and $X (t + 1)$ means the position of the Harris Hawks in the t + 1th generation.

Fusion sparrow algorithm discoverer strategy

The sparrow optimization algorithm divides the population into discoverer and follower. As the food searcher in the population, the discoverer sparrow plays the role of global search of the algorithm with good global search performance while guiding the follower sparrow to explore. The exploration phase in the Harris Hawks algorithm is influenced by the random number $r_{1} r_{2} r_{3} r_{4}$ , and random individual $X_{rand}$ . It lacks population exploration directivity, resulting in a less efficient algorithm search. In this paper, the discoverer mechanism of the sparrow optimization algorithm is introduced into the exploration phase of the Harris Hawks to optimize the exploration phase of the Harris Hawks, and the specific mathematical model expression for the improvement is as follows:

X (t + 1) = {\begin{matrix} \begin{matrix} (X_{rand} (t) - r_{1} | X_{rand} (t) - 2 r_{2} X (t) |) \cdot e^{(\frac{t}{α . T})} & q \geq 0.6 \end{matrix} \\ \begin{matrix} (X_{rabbit} (t) - X_{m} (t)) - Q \cdot L & q < 0.6 \end{matrix} \end{matrix}

(12)

Where: $α$ means a random number in the range [0,1], Q means a normally distributed random number, and L means a matrix of 1xD with each element being 1.

Improved energy factor strategy

In the HHO algorithm, the energy factor E influences the transition from the search phase to the development phase of the algorithm, and the overall trend of |E| decreases linearly from 2 to 0. The algorithm transforms from global search to local search. The linear decreasing of E leads to a poor balance between global and local search, which cannot adapt to the exploration and development of multi-complexity cases, and the generality of the algorithm is low. As shown in Figure 2, when 2≥|E|≥1, the algorithm performs the search phase, after 250 iterations, the algorithm begins to convert to the development phase until the end of the iteration, the number of global searches is equal to the number of local searches, after fusion with the sparrow algorithm, the search phase has a certain amount of bootstrap search performance enhancement, but the algorithm in search of high latitude and complex environment, due to the energy factor E linear rapid decrease, resulting in global detection is not comprehensive and fall into the local optimum.

Figure 2.

Distribution of energy factor E.

In this paper, we propose a nonlinear trend energy factor that increases the number of global explorations by slowing down the rate at which E decreases. As shown in Figure 3, the value of E drops to 1 around 330 iterations, the algorithm is converted to the development stage, and the number of global searches is improved by about 32% compared with the original energy factor E. It can better adapt to the investigation in a multi-dimensional complex environment, and the generality is enhanced to avoid falling into suboptimal values. The specific mathematical model expression of E is as follows:

E = 2 \cdot (1 - \sin ({(0.5 \cdot \frac{t}{T})}^{2.5}) \cdot π) r

(13)

Where: T means the maximum number of iterations.

Figure 3.

Distribution of the improved energy factor E.

Nonlinear weights to improve the Lévy flight strategy

In the local development stage of the Harris Hawks roundup, the prey energy is high, and there will be a fleeing situation when the Harris Hawks will carry out Levi’s flight of random wandering. This wandering approach increases local exploration capabilities in the early iterations of the development phase because of the extensive search range. With the late iteration of the Harris Hawks flock found the target and gathered to hunt, the effective search range gradually reduced; some Harris Hawks need to continue to adjust the state for hunting because they did not catch the prey; if they continue to perform the Lévy flight random wandering, resulting in Harris Hawks flying out of the effective search range, this wandering way will lead to a reduction in search accuracy and search efficiency, so a non-linear weighting strategy is introduced, and its specific mathematical model expression is as follows:

w (t) = 1 - {(\frac{t}{T})}^{4}

(14)

As shown in Figure 4, a nonlinear plot of W. In iterations 300–500 for local search, when the prey escapes, the Harris Hawks perform a random wandering of Lévy flight. As the number of iterations increases, the weighting strategy leads to smaller and smaller ranges of Lévy flights, reducing the random search range of Harris Hawks and improving the search accuracy and contraction speed.

Figure 4.

Non-linear convergence curve.

The mathematical model expression for the improved Harris Hawks random wandering is as follows:

Z = Y + S \times LF (D) \cdot w (t)

(15)

The block diagram of MIHHO is shown in Figure 5.

Figure 5.

Flow chart of MIHHO algorithm.

Test function experiments and path planning experiments

Test function experiments

To verify the effectiveness of the MIHHO improvement, the algorithm is compared with HHO, three other improved HHOs and four other types of algorithms in eight test functions for merit-seeking experiments and three different simulation environments for path planning experiments. The various parameters of the algorithm in the simulation experiment are set as shown in Table 1.

Table 1.

Algorithm parameter settings.

Parameter name	Parameter value
Population size N	30
Search Dimension $\dim$	30
Maximum number of iterations $T_{\max}$	500
$r_{1}, r_{2}, r_{3}, r_{4}$	Random number in the range [0,1]
The cut-off value q in the MIHHO search phase	0.6
The remaining parameters of the MHHO algorithm	Referring to the literature 34
The remaining parameters of the IHHO algorithm	Referring to the literature 35
The remaining parameters of the CEHHO algorithm	Referring to the literature 36
The remaining parameters of the HHO algorithm	Referring to the literature 21
The remaining parameters of the SOA algorithm	Referring to the literature 37
The remaining parameters of the GWO algorithm	Referring to the literature 18
The remaining parameters of the WOA algorithm	Referring to the literature 20
The remaining parameters of the PSO algorithm	Referring to the literature 16

The test function has a better evaluation function for the algorithm to find the best test. The smaller the value the algorithm searches under the same conditions, the stronger the search and development performance. This paper selects eight functions in three categories of single-peak, multi-peak and fixed dimension for algorithm performance testing, as shown in Table 2.

Table 2.

Standard test functions.

Standard functions	Dimensionality	Search space	Minimum value
$F_{1} = \sum_{i = 1}^{n - 1} [100 {(x_{i + 1} - x_{i}^{2})}^{2} + {(x_{i} - 1)}^{2}]$	30	[−30, 30]	0
$F_{2} = \sum_{i = 1}^{30} (\| x_{i} + 0.5 \|)^{2}$	30	[−100, 100]	0
$F_{3} = \sum_{i = 1}^{30} i x_{i}^{4} + r a n d o m [0, 1)$	30	[−1.28,1.28]	0
$F_{4} = - 20 \exp (- 0.2 \sqrt{\frac{1}{30} \sum_{i = 1}^{30} x_{i}^{2}}) - \exp (\frac{1}{30} \sum_{i = 1}^{30} \cos 2 π x_{i}) + 20 + e$	30	[−32, 32]	0
$F_{5} = \frac{π}{30} {10 si n^{2} (π y_{1}) + \sum_{i = 1}^{29} {(y_{i} - 1)}^{2} [1 + 10 si n^{2} (π y_{i + 1})] + {(y_{n} - 1)}^{2}} + \sum_{i = 1}^{30} u (x_{i}, 10, 100, 4)$	30	[−50, 50]	0
$F_{6} = 0.1 {si n^{2} (π 3 x_{1}) + \sum_{i = 1}^{29} {(x_{i} - 1)}^{2} [1 + si n^{2} (3 π x_{i + 1})] + {(x_{n} - 1)}^{2} [1 + si n^{2} (2 π x_{30})]} + \sum_{i = 1}^{30} u (x_{i}, 5, 100, 4)$	30	[−50, 50]	0
$F_{7} = {[\frac{1}{500} + \sum_{j = 1}^{25} \frac{1}{j + \sum_{i = 1}^{2} {(x_{i} - a_{ij})}^{6}}]}^{- 1}$	30	[−65.536, 65.536]	1
$F_{8} = \sum_{i = 1}^{11} [a_{i} - \frac{x_{i} (b_{i}^{2} + b_{i} x_{2})}{b_{i}^{2} + b_{i} x_{3} + x_{4}}]^{2}$	30	[−5,5]	0.0003075

Analysis of experimental results

The MIHHO is compared with three improved HHO algorithms, MHHO, IHHO, CEHHO, HHO and four other types of algorithms, SOA, GWO, WOA, and PSO, to do test function comparison experiments, and the specific convergence curves are shown in Figure 6. In the three single-peak test function convergence curves in Figure 6(a) to (c), MIHHO solves better fitness values compared to the original HHO and the three improved HHO algorithms, HHO performs the worst performance in its class, and the other four algorithms have a more significant gap with MIHHO overall. In (a), MIHHO performs well and explores the new minimum fitness value after 220 iterations. In (b)(c), MIHHO has a stronger search and exploitation capability and explores the minimum value with multiple orders of magnitude difference compared to other algorithms, due to the introduction of chaotic mapping into the algorithm to enhance the global exploration capability.

Figure 6.

Convergence curves of 8 test functions: (a) F1 test function, (b) F2 test function, (c) F3 test function, (d) F4 test function, (e) F5 test function, (f) F6 test function, (g) F7 test function, and (h) F8 test function.

The (d), (e), and (f) multi-peak test functions in Figure 6 mainly test the algorithm’s ability to jump out of the local optimum. In the (d) test function, except for WOA, GWO, and PSO, which do not add up in performance ability, the rest of the algorithms almost search for the optimal value in the current environment, but MIHHO searches for the optimal value with fewer iterations and faster search speed. In (e) and (f) all algorithms converge and keep searching for new minimum fitness values in the first 100 iterations, but MIHHO jumps out of the local optimum and searches for smaller fitness values after 150 and 175 iterations, respectively, the sparrow algorithm discoverer strategy is introduced in MIHHO to make the algorithm more capable of searching.

(g) and (h) of Figure 6 show the fixed-dimensional multi-peak test functions. WOA and SOA perform poorly in (g), and the rest of the algorithms find the optimal value, but MIHHO searches for the optimal value after six iterations, and the search speed is faster. In (h), both MIHHO and CEHHO can search for the optimal value the GWO curve keeps converging after 500 iterations without finding the optimal value, and the searchability is weak. MIHHO finds the optimal value after 61 iterations, thanks to the introduction of nonlinear energy factor strategy and nonlinear weight strategy in MIHHO to balance the global search and local search and speed up the search speed.

To verify the stability and robustness of the MIHHO improvement, nine algorithms were used to solve the eight test functions, and each process was run 30 times to obtain the mean and standard deviation, as shown in Table 3. The mean and standard deviation of MIHHO among the eight test functions was the most minor compared to other algorithms, and the algorithms were superior. In the F4 test function, MIHHO, MHHO, IHHO, CEHHO, HHO, and SOA all searched for the same minimum value with a standard deviation 0. However, the number of iterations in the test function is lower, and the search is faster, as shown in the (g) plot in Figure 6.

Table 3.

Experimental results of standard test functions.

Function Name	Statistical results	MIHHO	MHHO	IHHO	CEHHO	HHO	SOA	GWO	WOA	PSO
F1	Average value	2.68E − 03	7.05E − 03	1.20E − 02	6.96E − 03	1.11E − 02	2.88E + 01	2.72E + 01	2.80E + 01	8.29E + 03
F1	Standard deviation	3.67E − 03	8.41E − 03	1.49E − 02	1.06E − 02	1.28E − 02	3.72E − 02	9.29E − 01	4.54E − 01	4.99E + 03
F2	Average value	5.21E − 06	6.28E − 06	1.75E − 04	1.67E − 05	1.50E − 04	2.72E + 00	8.66E − 01	4.88E − 01	2.35E + 01
F2	Standard deviation	7.79E − 06	8.00E − 06	2.73E − 04	2.68E − 05	2.93E − 04	9.22E − 01	3.56E − 01	3.39E − 01	7.84E + 00
F3	Average value	1.48E − 05	7.34E − 05	8.63E − 05	1.76E − 04	2.12E − 04	2.20E − 04	1.71E − 03	3.63E − 03	4.83E − 01
F3	Standard deviation	5.50E − 05	6.45E − 05	9.22E − 05	2.29E − 04	2.54E − 04	2.24E − 04	9.71E − 04	3.08E − 03	9.28E − 01
F4	Average value	8.88E − 16	8.88E − 16	8.88E − 16	8.88E − 16	8.88E − 16	8.88E − 16	1.05E − 13	4.09E − 15	5.39E + 00
F4	Standard deviation	0	0	0	0	0	0	1.58E − 14	2.35E − 15	5.82E − 01
F5	Average value	4.58E − 07	1.18E − 06	8.24E − 06	1.76E − 06	1.08E − 05	2.94E − 01	3.79E − 02	3.04E − 02	8.09E + 00
F5	Standard deviation	5.55E − 07	1.84E − 06	1.65E − 05	2.82E − 06	1.37E − 05	2.96E − 01	1.73E − 02	3.04E − 02	3.10E + 00
F6	Average value	1.35E − 05	2.00E − 05	1.58E − 04	2.45E − 05	1.02E − 04	8.56E − 01	6.05E − 01	5.16E − 01	3.03E + 01
F6	Standard deviation	1.92E − 05	3.22E − 05	2.88E − 04	2.77E − 05	1.64E − 04	4.78E − 01	3.19E − 01	3.27E − 01	4.36E + 01
F7	Average value	1.13E + 00	1.75E + 00	1.36E + 00	1.36E + 00	1.59E + 00	6.33E + 00	3.58E + 00	3.48E + 00	1.90E + 00
F7	Standard deviation	1.16E + 00	1.69E + 00	1.26E + 00	2.91E + 00	1.50E + 00	4.65E + 00	3.37E + 00	3.59E + 00	1.30E + 00
F8	Average value	3.33E − 04	3.74E − 04	3.91E − 04	5.65E − 04	4.65E − 04	2.16E − 03	1.15E − 03	8.28E − 04	7.25E − 03
F8	Standard deviation	1.79E − 04	8.17E − 04	4.72E − 04	3.55E − 04	3.79E − 04	1.99E − 03	3.64E − 03	5.48E − 04	8.73E − 03

Path planning experiments and analysis

Raster maps have good environment expression capability, and path-planning environments are often built using raster. As the raster map shown in Figure 7, set the length of each raster to 1. The white area represents the feasible environment, and the black area represents the obstacle environment. To facilitate the calculation of the path length planned by the robot, each grid is numbered in the order of top to bottom from left to right, and the ith grid position is described as ( $X_{i}, Y_{i}$ ).

Figure 7.

20 × 20 raster map.

Using the path length as the fitness function of the algorithm for solving the path planning problem, the robot plans the path length calculated by the following formula:

H = \sum_{t = 0}^{n - 1} \sqrt{{(X_{i + 1} - X_{i})}^{2} + {(Y_{i + 1} - Y_{i})}^{2}}

(16)

In this paper, we design three types of raster maps of 15 × 15, 20 × 20 and 40 × 40 and set obstacles of different sizes in the environment as the simulation environment for robot path planning in MATLAB 2018a, and uniformly set the top left corner of the map as the starting point and the bottom right corner as the target point.

Indoor path planning simulation experiments for the same type of algorithm

As shown in Figures 8 and 9, the path planning experiments of the same algorithm are performed in a 15 × 15 raster map, and the map complexity is low in a simple raster map. All five algorithms searched for the minimum value. Still, MIHHO required the smallest number of iterations to search for the shortest path in a simple environment and searched for the minimum value after 15 iterations, due to the increase in search efficiency by adding a dynamic weighting strategy to the algorithm.

Figure 8.

Simple environmental path planning for 15 × 15.

Figure 9.

Path iteration curve at 15 × 15.

The path standard deviation and path mean of MIHHO are lower, and the algorithm is more stable. The path mean length is reduced by 3.6%, 3.7%, 2.8%, and 5.7% compared to MHHO, IHHO, CEHHO, and HHO, respectively, as shown in Table 4.

Table 4.

Experimental results of environment 1 scenario.

Evaluation criteria	MIHHO	MHHO	IHHO	CEHHO	HHO
Average length of path	29.067	30.267	30.133	29.867	30.733
Path standard deviation	1.688	1.914	1.928	1.825	2.159
Average number of iterations	40	82	92	84	120

As shown in Figures 10 and 11, the path planning experiments of the same algorithm were conducted in a 20 × 20 raster map with varying obstacle sizes and medium environmental complexity for this environment. In the first few raster planned paths, IHHO, CEHHO, and HHO three algorithms appear invalid turn paths; MIHHO planned a relatively short path, the middle and late paths compared with other algorithms, there is no invalid turn, after 225 iterations to detect the new shortest path, this is because the algorithm development stage to integrate the sparrow algorithm discoverer strategy, the searchability is enhanced, the improvement of the energy factor E, so that the algorithm better search in complex environments.

Figure 10.

20 × 20 medium environment path planning.

Figure 11.

Iteration curve of the path under 20 × 20.

As shown in Table 5, MIHHO has the minimum values of path average length, path standard deviation and average number of iterations, where the path average length is reduced by 5.3%, 7.3%, 4.7%, and 9.1% compared to MHHO, IHHO, CEHHO and HHO, respectively.

Table 5.

Experimental results of environment 2 scenarios.

Evaluation criteria	MIHHO	MHHO	IHHO	CEHHO	HHO
Average length of path	41.133	44.267	43.067	42.2	44.867
Path standard deviation	1.607	2.620	2.719	2.187	2.617
Average number of iterations	72	99	110	101	150

As shown in Figures 12 and 13, the path planning experiments for the same algorithm were performed in a 40 × 40 raster map, which has a larger area and more obstacles than the previous two environments. The path of MIHHO planning is smoother, and the path is shortest compared with other algorithms. At 480 iterations, the algorithm is developed again to find the new shortest path, which is due to the introduction of a dynamic weighting strategy in the algorithm to reduce the randomness of the Levy flight and increase the local search ability and search speed of the algorithm.

Figure 12.

40 × 40 complex environment path planning.

Figure 13.

Path iteration curve under 40 × 40.

The average path length was reduced by 9.0%, 20.0%, 20.0%, and 34.3% compared with MHHO, IHHO, CEHHO, and HHO, respectively, as shown in Table 6.

Table 6.

Experimental results of environment 3 scenarios.

Evaluation criteria	MIHHO	MHHO	IHHO	CEHHO	HHO
Average length of path	97.067	105.8	116.467	104	130.4
Path standard deviation	7.289	10.255	26.101	18.461	26.889
Average number of iterations	98	134	165	148	197

Indoor path planning simulation experiments with different types of algorithms

To further verify the performance of MIHHO improvement, path planning comparison experiments will be conducted in different algorithms. In this paper, four algorithms with better performance in path planning, Seagull Algorithm (SOA), Gray Wolf Algorithm (GWO), Whale Algorithm (WOA) and Particle Swarm Algorithm (PSO), are used for further comparison experiments.

As shown in Figures 14 and 15, the path planning simulation experiments are performed for MIHHO with four different types of algorithms in a 15 × 15 raster environment. The three algorithms GWO, WOA and PSO can search for the shortest path in a simple environment. The number of iterations to solve the optimal path is 245, 239 and 403, respectively, which is higher in convergence and lower in exploration ability compared with MIHHO. The optimal iteration curve of SOA has been converging until the shortest path searched is 30 after 500 iterations, and the overall path planning performance is weaker compared with MIHHO.

Figure 14.

Different types of path planning for 15 × 15.

Figure 15.

Path iteration curve under 15 × 15.

As shown in Table 7, the average length of the paths solved by SOA and PSO after 30 experiments is high, and the standard deviation of SOA paths is relatively large, and the path planning is unstable. MIHHO has the minimum value and the average number of iterations in all three metrics is significantly differs from the other four algorithms with fast convergence. The average length of paths is reduced by 11.9%, 2.8%, 1.6%, and 7.1% compared to SOA, GWO, WOA, and PSO, respectively.

Table 7.

Experimental results of environment 1 scenario.

Evaluation criteria	MIHHO	SOA	GWO	WOA	PSO
Average length of path	29.067	32.533	29.867	29.533	31.133
Path standard deviation	1.688	4.951	1.784	1.750	1.765
Average number of iterations	40	120	75	98	86

As shown in Figures 16 and 17, the path planning simulation experiments are performed for MIHHO with four different types of algorithms in a 20 × 20 raster environment. In the moderately complex environment, the paths planned by SOA and PSO are relatively poor, with an average path length close to 50 and unstable, and the intermediate courses planned 30 times by GWO and WOA are closer. Still, the path standard deviation of GWO is more extensive, and the algorithm is less stable. As the environment becomes more extensive and the complexity increases, MIHHO pulls away from the other four algorithms in the three metric experiments by an increasing margin, with the strongest overall search performance.

Figure 16.

Different types of algorithmic path planning for 20 × 20.

Figure 17.

Iteration curve of the path under 20 × 20.

As shown in Table 8, MIHHO has the smallest value under all three metrics, reducing the average path length by 21.4%, 12%, 8.6%, and 16.9% compared to SOA, GWO, WOA and PSO, respectively.

Table 8.

Experimental results of environment 2 scenario.

Evaluation criteria	MIHHO	SOA	GWO	WOA	PSO
Average length of path	41.133	49.933	46.267	44.667	48.067
Path standard deviation	1.607	4.575	6.213	2.560	4.633
Average number of iterations	72	208	105	156	132

As shown in Figures 18 and 19, the path planning simulation experiments are performed for MIHHO with four different types of algorithms in a 40 × 40 raster environment, which has high complexity and dense obstacles. Introducing Chebyshev chaos mapping and fused sparrow algorithm discoverer mechanism in MIHHO allows the algorithm to have enhanced search capability in the search phase. MIHHO develops new optimal paths after 480 iterations, jumping out of the local optimum.

Figure 18.

Different types of algorithmic path planning for 40 × 40.

Figure 19.

40 × 40 path iteration curve.

As shown in Table 9, MIHHO is the smallest value under all three metrics, with a 33.3%, 23.2%, 14.07%, and 21.8% reduction in average path length compared to SOA, GWO, WOA and PSO, respectively.

Table 9.

Experimental results for the environment 3 scenario.

Evaluation Criteria	MIHHO	SOA	GWO	WOA	PSO
Average length of path	97.067	129.4	119.6	110.733	118.2
Path standard deviation	7.289	54.265	28.661	14.944	18.56
Average number of iterations	98	255	159	225	195

Conclusion

Aiming at the problems of low and unstable efficiency and poor path quality in path planning for mobile robots, this paper proposes an improved Harris hawk optimization algorithm (MIHHO). The Chebyshev chaotic mapping strategy is added to the HHO to initialize the population of Harris Hawk. Integrate the exploration phase of HHO with the discoverer mechanism of the sparrow algorithm to improve the global planning ability of the robot. Improve the factor E of HHO to strengthen the balance between local and global planning of the robot and improve the path accuracy, and incorporate the dynamic adjustment of the Levy flight strategy in the development phase to improve the planning speed of the robot. Through further validation with the same type of algorithms and different types of algorithms in test functions and path planning experiments, MIHHO has improved the search efficiency, enhanced robustness, and significantly improved quality of paths in path planning. In this study, experiments are conducted in three raster maps, and further experiments in more different types of maps are subsequently needed to verify the improvement.

Footnotes

Declaration of conflicting interests

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This study was supported by the Natural Science Foundation of Xinjiang Uygur Autonomous Region (Grant No. 2021D01C052), the State Key Laboratory for Manufacturing System Engineering (Xi’an Jiaotong University) (Grant No.sklms2021010).

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

ORCID iD

Qing Si

References

Pan

Xie

Jiang

. Sweeping Robot Based on Laser SLAM. Procedia Comput Sci 2022; 199: 1205–1212.

Lubov

Andrey

Sergei

. Hybrid trajectory optimization method for service logistics robots. Transp Res Procedia 2022; 63: 2151–2157.

Gong

Niu

Zhang

. Multi-objective path planning for campus food delivery robot based on local dimensionality reduction Dijkstra algorithm. J Shandong Univ Technol 2021; 35(4): 75–80.

Wang

Cao

, et al. Coverage path planning for kiwifruit picking robots based on deep reinforcement learning. Comput Electron Agric 2023; 205(14): 157–168.

Sun

Tang

, et al. Path planning for mobile robots based on an improved A* algorithm. J Hunan Univ 2017; 44(4): 94–101.

Liu

Zhang

. ASL-DWA: an improved A-Star algorithm for indoor cleaning robots. IEEE Access 2022; 10(1): 99498–99515.

Zhang

Wang

. Optimization of the shortest path of urban roads by Dijkstra’s algorithm. J Chang Univ 2005; 25(6): 62–65.

Wolfgang

Baker

Brooks

, et al. Globally optimal rover traverse planning in 3D using Dijkstra’s algorithm for multi-objective deployment scenarios. Planet Space Sci 2019; 179: 612–631.

Cui

Wang

, et al. Global path planning of kiwifruit picking robot based on improved RRT algorithm. J Agric Mach 2022; 53(6): 151–158.

10.

Duan

, et al. A probability smoothing Bi-RRT path planning algorithm for indoor robot. Future Gener Comput Syst 2023; 143: 349–360.

11.

Ning

. Ship path planning and tracking control based on improved artificial potential field method. Journal of Harbin Engineering University 2022; 43(10): 1414–1423.

12.

Zhu

Yin

Lyu

. Automatic collision avoidance algorithm based on route-plan-guided artificial potential field method. Ocean Eng 2023; 271: 158–176.

13.

Chen

, et al. Improved A^(*) and dynamic window method for mobile robot path planning. Comput Integr Manuf Syst 2022; 28(6): 1650–1658.

14.

Xiang

Liu

, et al. Parameter Fuzzy self-adaptive dynamic window approach for local path planning of wheeled robot. J Intell Transp Syst 2022; 3: 1–6.

15.

Zhang

Huang

. A multi-strategy adaptive multi-objective particle swarm algorithm based on population partitioning. J Autom 2022; 48(10): 2585–2599.

16.

. Three-dimensional path planning for AUVs in ocean currents environment based on an improved compression factor particle swarm optimization algorithm. Ocean Eng 2023; 280: 325–346.

17.

Liu

Yuan

, et al. Path planning for mobile robots using improved grey wolf algorithm. Journal of Xi’an Jiaotong University 2022; 56(10): 49–60.

18.

. A local opposition-learning golden-sine grey wolf optimization algorithm for feature selection in data classification. Appl Soft Comput 2023; 142(12): 78–97.

19.

Liu

Multiple

. Swarm longitudinal and bidirectional learning and information swapping for whale optimization algorithms. j electron inf 2021; 43(11): 3247–3256.

20.

Huang

Zhang

, et al. A novel path planning approach for AUV based on improved whale optimization algorithm using segment learning and adaptive operator selection. Ocean Eng 2023; 280: 114–133.

21.

Tansel

Ayça

Hakan

. A robust multiobjective Harris’ Hawks Optimization algorithm for the binary classification problem. Knowl Based Syst 2021; 227: 107–125.

22.

Zhan

Wang

Liu

. A hybrid strategy improved Harris Hawks optimization algorithm and its application. J Sens Technol 2022; 35(10): 1394–1403.

23.

Harun

Haydar

. An improved Harris Hawks optimization algorithm for continuous and discrete optimization problems. Eng Appl Artif Intell 2022; 113(13): 104–138.

24.

Chen

Heidari

Chen

, et al. Multi-population differential evolution-assisted Harris hawks optimization: Framework and case studies. Future Gener Comput Syst 2020; 111: 175–198.

25.

Vikram

Ayani

NAB

Shivani

. An intensify Harris Hawks optimizer for numerical and engineering optimization problems. Appl Soft Comput 2020; 89: 106–128.

26.

Kashif

Nabil

William

, et al. An efficient hybrid sine-cosine Harris hawks optimization for low and high-dimensional feature selection. Expert Syst Appl 2021; 176: 566–581.

27.

Chen

, et al. Enhanced Harris hawks optimization with multi-strategy for global optimization tasks. Expert Syst Appl 2021; 185: 115–142.

28.

Kang

Liu

Yao

, et al. Improved Harris hawks optimization for non-convex function optimization and design optimization problems. Math Comput Simul 2023; 204: 619–639.

29.

Zhou

Bian

. Multi-mechanism-based modified bi-objective Harris Hawks optimization for sustainable robotic disassembly line balancing problems. Eng Appl Artif Intell 2022; 116: 318–342.

30.

Wang

Song

, et al. Hybrid multi-objective Harris Hawk optimization algorithm based on elite non-dominated sorting and grid index mechanism. Adv Eng Softw 2022; 172(23): 359–388.

31.

Guo

Dai

, et al. Improved Harris hawks optimization algorithm based on random unscented sigma point mutation strategy. Appl Soft Comput 2021; 113: 108–136.

32.

Liu

Liang

. Harris eagle optimization algorithm based on square neighborhood and random array. Control Decis Mak 2021; 37(10): 2467–2476.

33.

Liu

. Parameter identification of PV cell engineering model based on IHHO algorithm. J Metrol 2021; 42(2): 221–227.

34.

Guo

Liu

Gao

, et al. Improved harris hawks optimization algorithm with multiple strategies. Microelectron Comput 2021; 38(7): 18–24.

35.

Chen

Zeng

Huang

, et al. A HHO algorithm incorporating mutualistic symbiosis and lensing imaging learning. Comput Eng Appl 2022; 58(10): 76–86.

36.

Andy

Han

, et al. Chaotic elite harris hawks optimization algorithm. SPE Comput Appl 2021; 41(8): 2265–2272.

37.

Gaurav

Krishna

Mukesh

, et al. A new multi-objective seagull optimization algorithm. Expert Syst Appl 2021; 167: 114–135.

A robot path planning method using improved Harris Hawks optimization algorithm

Abstract

Keywords

Introduction

HHO algorithm

Soft roundup

Hard siege

Progressive fast swoop soft siege

Progressive fast swoop hard roundup

Problem analysis and improvement strategies

Chebyshev chaos mapping strategy

Fusion sparrow algorithm discoverer strategy

Improved energy factor strategy

Nonlinear weights to improve the Lévy flight strategy

Test function experiments and path planning experiments

Test function experiments

Analysis of experimental results

Path planning experiments and analysis

Indoor path planning simulation experiments for the same type of algorithm

Indoor path planning simulation experiments with different types of algorithms

Conclusion

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References