A path planning method using modified harris hawks optimization algorithm for mobile robots

Environment modeling and problem description

Typically, the grid method, topological map, and geometric method are used for environment modeling (Chen et al., 2020b; Zhang et al., 2021). In this article, the simulation environment is constructed using the grid method. The grid platform represents a two-dimensional environment where the mobile robot moves on the grid platform. On the platform, the moving area is represented by grid cells with binary information, indicated by “1” for the obstacle grid and “0” for the free grid. Figure 1 indicates a typical grid environment with a size of 20 × 20, where the blue grids denote obstacles and the white grids represent free space, respectively. When a mobile robot is in a white grid with no obstacles around, there are eight directions in which the mobile robot could move, as shown in Fig. 2.

For mobile robots, the grid-based path planning approach can be expressed as follows: beginning with the starting grid, path planning seeks to find a path that avoids the obstacle behavior to reach the end grid with a short path and in less time. In the process of optimization, the path is optimized by the path length. Consequently, the problem of path planning can be considered as an engineering optimization problem, and intelligent optimization algorithms could be used to address the problem.

HHO algorithm

As a novel optimization algorithm, the HHO algorithm is also obtained by the evolution of nature, which mainly simulates the cooperative hunting process of Harris hawks. There are two phases in the HHO algorithm: the exploration phase and the exploitation phase (Çetinbaş, Tamyürek & Demirtaş, 2021; Heidari et al., 2019). The detailed process is expressed as follows.

The exploration phase is represented as Heidari et al. (2019) and Kardani et al. (2021): (1)${\displaystyle x\left(t+1\right)=\left\{\begin{array}{c}{x}_{\mathrm{rand}}\left(t\right)-r_1\left|x_{\mathrm{rand}}\left(t\right)-2r_{2}x\left(t\right)\right|,p\ge 0.5\hfill \\ \left(x_{\mathrm{prey}}\left(t\right)-x_m\left(t\right)\right)-r_3\left(L_b+r_4\left(U_b-L_b\right)\right),p<0.5,\hfill \end{array}\right.}$ (2)${\displaystyle x_{\mathrm{avg}}\left(t\right)=\frac{1}{N}\sum _{i=1}^N{x}_i\left(t\right),}$ where x(t) and x(t + 1) represent the position of the current iteration and the next iteration, respectively. x_rand(t) denotes a randomly chosen position, x_prey(t) represents the prey position, L_b and U_b represent the minimum and maximum values of the solution space, respectively. r₁, r₂, r₃, r₄, and p represent the randomly assigned numbers in (0,1), and N is the number of total hawks.

The escape energy of each prey plays a critical role in the algorithmic search process, expressed as in Eq. (3). The value of the prey energy escaping determines whether the exploration phase ($\left|E\right|\ge 1$) or the exploitation phase ($\left|E\right|<1$) is executed. (3)${\displaystyle E=2E_0\left(1-t/T_{\max }\right),}$ where E₀ denotes the random initial escape energy, t and T_max are the current and maximum number of iterations, respectively.

In the exploitation phase, the HHO algorithm implements four different processes, which are mainly the soft besiege, hard besiege, soft besiege with progressive rapid dives, and hard besiege with progressive rapid dives processes. Prey attempted to escape depending on the environment, and r is used to denote the probability of escape. The HHO algorithm employs a soft besiege to move closer to prey when the prey has enough escape energy ( $\left|E\right|\ge 0.5$) but is still unable to escape from the encirclement ( r ≥ 0.5). The process is represented as: (4)${\displaystyle x\left(t+1\right)=\Delta x\left(t\right)-E\left|J_{\mathrm{prey}}{x}_{\mathrm{prey}}\left(t\right)-x\left(t\right)\right|,}$ (5)${\displaystyle \Delta x\left(t\right)=x_{\mathrm{prey}}\left(t\right)-x\left(t\right),}$ (6)${\displaystyle J_{\mathrm{prey}}=2\left(1-r_5\right),}$ where r₅ denotes a random number, and J_prey is the energy of jumping.

In the hard besiege process, the rabbit consumes so much energy that it does not have sufficient energy to escape ( r ≥ 0.5 and $\left|E\right|<0.5$). (7)${\displaystyle x\left(t+1\right)=x_{\mathrm{prey}}\left(t\right)-E\left|\Delta x\left(t\right)\right|.}$ For the soft besiege with progressive rapid dives process, the rabbit retains enough strength to escape from the capture ( r < 0.5 and $\left|E\right|\ge 0.5$). The process is expressed as: (8)${\displaystyle Y_1=x_{\mathrm{prey}}\left(t\right)-E\left|J_{\mathrm{prey}}{x}_{\mathrm{prey}}\left(t\right)-x\left(t\right)\right|,}$ (9)${\displaystyle Z_1=Y_1+S\times \mathrm{Levy}\left(n\right),}$ (10)${\displaystyle x\left(t+1\right)=\left\{\begin{array}{c}{Y}_1,\mathrm{fitness}\left(Y_1\right)<\mathrm{fitness}\left(Z_1\right)\hfill \\ Z_1,\mathrm{fitness}\left(Y_1\right)>\mathrm{fitness}\left(Z_1\right)\hfill \end{array}\right.,}$ where S indicates a random-generation vector, Levy represents the Levy flight function (Iacca, Dos Santos Junior & Veloso de Melo, 2021), n is the dimension of the problem, and fitness represents the fitness function.

For the hard besiege with progressive rapid dives process, the energy of prey is almost depleted and the prey is unable to escape safely. The process is expressed as: (11)${\displaystyle x\left(t+1\right)=\left\{\begin{array}{c}{Y}_2,\mathrm{fitness}\left(Y_2\right)<\mathrm{fitness}\left(Z_2\right)\hfill \\ Z_2,\mathrm{fitness}\left(Y_2\right)>\mathrm{fitness}\left(Z_2\right)\hfill \end{array}\right.,}$ (12)${\displaystyle Y_2=x_{\mathrm{prey}}\left(t\right)-E\left|J_{\mathrm{prey}}{x}_{\mathrm{prey}}\left(t\right)-x_{\mathrm{avg}}\left(t\right)\right|,}$ (13)${\displaystyle Z_2=Y_2+S\times \mathrm{Levy}\left(n\right).}$

Modified HHO algorithm

A modified HHO algorithm with three strategies for path planning is proposed. The LPS strategy is used to optimize the path, which produces the smooth and short paths. The nonlinear control strategy is applied to the HHO algorithm to enhance the convergence speed. The local search update strategy is used for the HHO algorithm to improve the convergence accuracy.

1. Linear path strategy

The LPS strategy means linearly achieving path planning as much as possible, which can generate a high-quality path and reduce the algorithm runtime (Fareh et al., 2020; Zhang, He & Yang, 2021). The process of LPS mainly completes the search for obstacles and the optimization of paths, as displayed in Fig. 3. The details are illustrated as follows.

Step 1: Start from the beginning of the path and generate three points sequentially.

Step 2: Calculate the distance of the generated points, determine the distance range, and search for obstacles within that range.

Step 3: When there is no obstacle in this scope, the second point is removed and the first and third points are connected to generate the path. Otherwise, the process terminates and continues the linearization of the path.

2. Nonlinear control strategy

To speed the convergence and obtain a low algorithm runtime, a nonlinear control strategy is proposed for the HHO algorithm for path planning (Chen, Wang & Zhao, 2020). The control parameter is given by (14)${\displaystyle \omega =2\times e^{-{\left(8t/T_{\max }\right)}^2}.}$ After applying the nonlinear control strategy, Eqs. (8) and (9) are updated as follows: (15)${\displaystyle Y_1=\omega x_{\mathrm{prey}}\left(t\right)-E\left|J_{\mathrm{prey}}{x}_{\mathrm{prey}}\left(t\right)-x\left(t\right)\right|,}$ (16)${\displaystyle Z_1=\omega Y+S\times \mathrm{Levy}\left(D\right).}$ Moreover, Eqs. (12) and (13) are changed as follows: (17)${\displaystyle Y_2=\omega x_{\mathrm{prey}}\left(t\right)-E\left|J_{\mathrm{prey}}{x}_{\mathrm{prey}}\left(t\right)-x_{\mathrm{avg}}\left(t\right)\right|,}$ (18)${\displaystyle Z_2=\omega Y_2+S\times \mathrm{Levy}\left(D\right).}$

3. Local search update strategy

For the robot path planning, the HHO algorithm easily obtains local optimal solutions and could not achieve the optimum of the path design. Thus, a local search update method is proposed to avoid being trapped in a local optimum. The local search update strategy focuses on randomly searching each dimension of the path and calculating the fitness value after the search. If the fitness value after the search is lower than the fitness value before the search, the previous path is updated with the search result. Otherwise, the search update path is discarded and the previous path is maintained.

The flowchart of the proposed algorithm with the three strategies is displayed in Fig. 4.

Complexity analysis of MHHO algorithm

The computational complexity of HHO depends on three main processes: initialization, fitness calculation and individual position update. Assuming that population size is N, the maximum number of iterations is T_max, and the search space dimension is D, the computational complexity of HHO can be calculated as follows (Chen et al., 2020a): (19)${\displaystyle O\left(\mathrm{HHO}\right)=O\left(N\times \left(1+T_{\max }+T_{\max }\times D\right)\right).}$ Many aspects are mainly responsible for the computational complexity of the MHHO, which are initialization, fitness calculation, updating of individuals, LPS strategy, nonlinear control strategy and local search update strategy. The time complexity of LPS is O(T_max × N²). The time complexity of the local search update strategy is O(T_max × N). The nonlinear control strategy only increases the calculation of the weights, and the increased computational complexity of the algorithm is negligible. Therefore, the whole computational complexity of MHHO is (20)${\displaystyle O\left(\mathrm{MHHO}\right)=O\left(N\times \left(1+T_{\max }\times \left(2+D+N\right)\right)\right).}$

Implement path planning for the MHHO algorithm

For mobile robots, the path planning for executing the MHHO algorithm is described as follows:

Step 1: The simulation environment model is constructed and optimization algorithm parameters are set. The path length is chosen as the fitness function for the optimization algorithm.

Assuming that the coordinates of a node of the path are denoted as P_i(x_i, y_i), and the path length is given by (21)${\displaystyle f_{\mathrm{path}\text{\_}\mathrm{length}}=\sum _{i=0}^k\sqrt{{\left(x_{i+1}-x_i\right)}^2+{\left(y_{i+1}-y_i\right)}^2},}$ where k is a node of the path.

The calculation of path length is employed as the fitness function, and the LPS is also used to compare the lengths of the different paths during the optimization iterations to select the optimal path.

Step 2: Initialization of the proposed algorithm. The population individuals are randomly generated, the fitness function values of the population individuals are calculated, and the optimal individual is selected.

Step 3: Implementation of the exploration phase and the exploitation phase of the MHHO algorithm.

Step 4: The criteria for algorithm termination iterations. If the maximum number of iterations is reached, the algorithm stops iterating and outputs the optimal position. Otherwise, the algorithm continues to find the best position.

Simulation environment and parameters setting

To validate the effectiveness of the proposed algorithm, simulation experiments are performed in two different environments. To effectively display the path finding results, the grid map size of the simulation environments is set to 20 × 20, as displayed in Fig. 1. In the grid map, the starting grid and the ending grid were at the left bottom corner and top right corners, respectively.

In this study, several optimization algorithms are applied to the path planning of robots. ACO, HHO, ISSA, and MHHO were simulated under the same conditions. All simulations were carried out using a Huawei computer equipped with AMD Ryzen 5 @ 3 GHz and 16 GB of RAM. All algorithms were simulated employing MATLAB R2018b software. To ensure the effective comparison of the algorithms, all algorithms have the same population size and iteration numbers. The parameters of each algorithm are listed in Table 1.

Evaluation criterion

Path planning for mobile robots aims at the best time and shortest path, so it is necessary to use several indicators for path evaluation. We chose two indicators to evaluate the path quality: the optimum path and the execution time (Deng et al., 2021; Montiel, Sepúlveda & Orozco-Rosas, 2014).

The optimum path is the length of the best search path obtained by the algorithm. The execution time of the algorithm is the time taken by the algorithm to achieve the optimal path.

Simulation results analysis

To prove the stability and efficiency of the proposed algorithm, experiments with the MHHO, HHO, ACO, and ISSA were carried out in the same environment. The results of ACO, HHO, ISSA, and MHHO algorithms in Environment 1 are listed in Table 2. Figures 5 and 6 respectively show the optimum path diagram and the convergence curve with different algorithms in Environment 1. From Table 2, the execution time of ACO, HHO, ISSA, and MHHO algorithms are 1.97 s, 0.41 s, 1.23 s, and 0.89 s, respectively. From Fig. 5, the path achieved with the MHHO algorithm has good path length and path smoothness compared with ACO, HHO, and ISSA algorithms. As displayed in Fig. 6, the MHHO algorithm achieves high convergence accuracy when the number of iterations is small. The MHHO algorithm has the fastest convergence speed compared to the ACO, HHO, and ISSA algorithms.

In Environment 2, the experiment was performed with the same parameters, and the results of different algorithms are listed in Table 3. The optimum path chart and the convergence curve are shown in Figs. 7 and 8, respectively. From Table 3, the execution time of the ACO, HHO, ISSA, and MHHO algorithms are 1.45 s, 0.38 s, 0.76 s, and 0.69 s, respectively. From Figs. 7 and 8, the optimum path and the convergence rate of the MMHO algorithm are also superior to the ACO, HHO, and ISSA algorithms.

Performance comparison

Swarm intelligence algorithm has a certain randomness when used to address practical engineering problems. To prove the adaptability and robustness of the proposed algorithm, the simulation experiments of the ACO, HHO, ISSA, and MHHO algorithms are conducted 50 times independently in Environments 1 and 2, respectively. The indicators of the optimum path and the implementation time of the four algorithms are achieved.

Figures 9 and 10 display the results of the four algorithms with the two indicators in Environment 1. As seen in Fig. 9, the MHHO algorithm obtains the optimal path and the length of the path has small fluctuations. The paths obtained by the HHO algorithm have large fluctuations. The optimum path of the MHHO algorithm outperforms other algorithms. From Fig. 10, the ACO algorithm has longest execution time and the HHO algorithm has the shortest execution time compare with other algorithms. The implementation time of the MHHO algorithm is slightly increased concerning the HHO algorithm due to the inclusion of multiple strategies in the algorithm.

In Environment 2, the results of the four algorithms are displayed in Figs. 11 and 12. From Fig. 11, the length of obtaining the optimal path is increased due to the increase in the number of obstacles. The MMHO algorithm still has a good optimum path compare with other algorithms. As displayed in Fig. 12, the MMHO and ISSA algorithms have similar execution times, and the HHO algorithm achieves the minimum execution time.

To further discuss the capabilities of the MHHO algorithm, we count the test results of the path planning in different environments. Table 4 shows the results of the algorithms in different environments. In Environment 1, the MHHO algorithm has the best performance for the optimum path, and ISSA algorithms have similar execution times, and the HHO algorithm has the minimum execution time. In Environment 2, the MHHO algorithm also obtains the optimal path. In addition, the MHHO algorithm outperforms the ISSA algorithm in terms of path optimization and algorithm execution time. Therefore, the MHHO algorithm is an effective method for robotic path design.