Multi-objective path planning for mobile robot with an improved artificial bee colony algorithm

1.   Introduction

Mobile robots have been gaining widespread attention as intelligent products. They are applied in many fields, such as industrial manufacturing, agricultural production, medical services, smart home, and automatic driving ^[1,2]. In our daily life, home service robot is a type of mobile robot that performs a wide range of tasks, including patrolling, taking care of the elderly and children, delivering goods to the server, and so on ^[3,4,5]. Thus, path planning (PP) has become essential for home service robots to complete service tasks. PP problem involves finding one or more feasible paths to the target location from the starting position with a given configuration space. In the real application, robust PP methods could minimize the robot's operation time, while saving labor and material resources. Currently, PP has been one of the most researched problems in robot technology ^[6,7].

The classical methods for solving the PP problem include the probabilistic roadmap planner (PRM) ^[8], rapidly exploring random tree (RRT) algorithm and its variants ^[9,10], artificial potential field methods ^[11], A* algorithm ^[12] and Dijkstra algorithm ^[13]. These algorithms have achieved some typical applications in many different fields. However, most of them optimize only one objective, such as path length. Real scenarios bring many constraints, including dangerous obstacles in the environment and structural constraints of the mobile robot itself. Hence, a solution that considers only a single objective is not always accurate. In our opinion, path length and other objectives (e.g., path safety) should be simultaneously considered. The path length is related to the motion time of the mobile robot, from the starting point to the target point. Path safety is related to the concept of a collision-free path that represents a path's safety degree. The solution of a single-objective PP problem is uniquely determined, while a multi-objective PP problem yields a set of solutions with advantages and disadvantages that cannot be directly compared. These solutions are called the Pareto optimal solution set ^[14,15,16].

Swarm intelligence optimization algorithms ^{[17,18,19,20,21,22]} are currently attracting wide attention from scholars, who have applied them to deal with PP problems. For example, Masehian et al. ^[23] combined the PSO algorithm with PRM to propose a novel multi-objective PP framework that optimizes path length and path smoothness objectives. Davoodi et al. ^[24] presented an improved NSGA-II to solve path length and path clearance in discrete space. The improved NSGA-II used an innovative family of path refiner operators, in addition to standard genetic operators. Duan et al. ^[25] proposed a multi-objective PP optimization method was mainly implemented by an improved firefly algorithm that optimized path length and path smoothness objectives. Pareto-dominance was employed to balance the performance of the optimized solutions. In addition, an elite record library was created to reserve the non-dominance solutions. Guo et al. ^[26] investigated a multi-objective PP problem based on a hybrid algorithm. They weighted path length and path safety objectives using the entropy method to obtain a short and safe path. Gong et al. ^[27] proposed an improved global PP method using a multi-objective particle swarm optimization algorithm that considered path length and path danger level. In this algorithm, a self-adaptive mutation operation was mainly designed to improve the feasibility of a new path. Similarly, Zhang et al. ^[28] investigated the PP problem based on the particle swarm optimization algorithm in an uncertain environment. They selected path risk level and path length the two objectives to be optimized and mostly introduced a membership function to evaluate the riskiness of the path and several new operators to improve the algorithm performance. Mac et al. ^[29] introduced a hierarchical global PP method that designs a three-level structure, which optimizes the path length and the path smoothness, consequently realizing an optimal path. However, most of these studies used schemes that combined multiple objectives into a weighted function, despite claiming that they solved the multi-objective PP problem. These methods produced different optimal solutions according to the weighted value distribution, which are difficult to precisely predict in real problems. In other words, the optimal solution obtained by the weighted multi-objective optimization algorithm may be a better one in a particular situation, but a worse one in another case.

Many works dealt with the PP problem in a multi-objective simultaneous optimization manner, producing multiple non-dominated solutions in a single run instead of balancing the weight coefficients of each objective. For instance, Hidalgo-Paniagua et al. ^[30] proposed the multi-objective firefly algorithm to solve the multi-objective PP problem, in which path length, path safety, and path smoothness related to the robot's energy consumption are simultaneously optimized. Pareto dominance was employed to evaluate the solution fitness. Similarly, Hidalgo-Paniagua et al. ^[31] also investigated another algorithm, called the shuffled frog-leaping algorithm, to deal with the multi-objective PP problem. Although state-of-the-art algorithms have achieved considerable achievements, a gap remains in the multi-objective PP problem. In our opinion, path length and path smoothness are linearly correlated in the PP problem. They are usually regarded as two objectives that are not completely in conflict. In our experimental verification, we found that the path with a shorter path length has better smoothness. On the contrary, path length and path safety are two admitted conflicting objectives. In addition, existing evolutionary strategies used by the previous algorithms focused on the macro update of the path segment, and lacked an effective local search strategy. What's more, most of them lacked an effective elimination and regeneration mechanism for stagnated solutions over a period of time.

Proposed by Karaboga in 2005, the artificial bee colony (ABC) algorithm is a swarm intelligence optimization algorithm that aims to solve multivariate function optimization problems ^[32]. The ABC algorithm imitates the bees' behavior of finding the best honey source and has strong global optimization-seeking ability, fast convergence speed, and fewer parameters. It has been applied to many applications, including the flow shop scheduling problem ^{[33,34,35,36]} and neural network parameter optimization ^[37,38,39], achieving excellent results. It has also been applied to solve the mobile robot PP problem. Based on the ABC algorithm, Saffari and Mahjoob ^[40] proposed a novel method used to optimize the path length objective in a real-time PP problem. They focused on designing a rule for building an initial collision-free path and utilized a swarm algorithm for path optimization. Bhattacharjee et al. ^[41] presented an improved ABC algorithm to minimize the path length of multiple robots. Using the ABC algorithm, a local trajectory planning scheme was developed to optimally obtain the next position of all robots in the world map from their current positions, such that the local paths of n robots become sufficiently small. The ultimate goal was to minimize the path length of all robots. However, few scholars have used the ABC algorithm to deal with the multi-objective PP problem.

Considering the characteristic of the ABC algorithm and the problems mentioned above, we proposed herein an improved ABC algorithm to solve the multi-objective PP problem of the home service robot, which uses the Pareto dominance to evaluate the deeply evolved solution sets. The decision-maker could select an appropriate scheme from these candidate solutions according to the current specific application requirements. In this study, path length and path safety are considered as two optimized objectives. The contributions of this study are as follows:

1) A new hybrid initialization strategy is proposed. This strategy uses the RRT algorithm and the space segmentation method to jointly generate a high-quality initial population. The RRT explores the configuration space through a tree structure from the starting point and incrementally extends the tree of collision-free paths, which generates initial solutions randomly, so as to enhance the distribution of the population. The space segmentation method utilizes the line between the starting and the target points as the axis to conduct space segmentation, which ensures the feasibility of the solutions, meanwhile, this method is conducive to finding these initial solutions with better objective characteristics.

2) A variable neighborhood local search strategy is developed. In each iteration, the proposed variable neighborhood local search strategy changes searching neighborhoods of path nodes according to the closest distance between the current node and the obstacle. This operation can effectively ensure the reachability of the line segments on both sides of the node, so as to avoid lots of time-consuming collision detection.

3) A new global search strategy is presented. During the iteration, solutions with long-time evolutionary stagnation are removed from the population. For new individuals, this global search strategy mainly completes two aspects of work. Firstly, the individuals in the Pareto non-dominated solution set are used to carry out crossover operation to form new ones, which inherits the excellent characteristics of the current solutions. Secondly, new solutions are also randomly generated to ensure the global search ability of the algorithm. Compared with the original ABC algorithm, this strategy significantly accelerates the convergence speed of the algorithm.

The rest of this paper is organized as follows. Section 2 introduces the kinetic model of a home service robot, environment modeling, path encoding, and mathematical model of the optimization objective required for PP. Section 3 presents the algorithmic framework of the IMO-ABC algorithm and the detailed evolutionary strategy. Section 4 describes the simulation environments, performance metrics, effectiveness analysis of the algorithm, and comparative analysis with NSGA-II and MO-PSO. Finally, Section 5 presents the concluding remarks.

2.   Path planning

This section presents the kinetic model of a home service robot, environment modeling, path encoding, and the two objectives for optimization.

2.1.   Kinetic model of a home service robot

Figure 1 shows the kinetic model of a home service robot ^[42]. The two drive wheels are distributed in the front. The two universal wheels are at the back. Taking $P$ point as the motion reference point and the linear and angular velocities of the robot as $v$ and $w$, we obtain:

Supposing the centroid of the robot $C$ is similar to the geometric center of the box body, the distance from the particle to point $P$ is $d$. The centroid coordinates are as follows.

Taking the derivative of Eq (2.2) and combining Eq (2.1), the equation of the centroid motion of the robot is obtained as

The robot is driven by two driving wheels. The direct control is that the speeds of the two driving motor wheels are $w_1$ and $w_2$. Supposing the distance between the two driving wheels is $l$, the radius is represented as $R$, and the following formula is obtained.

2.2.   Environmental model

Building an environment model that is easy to understand and compute is important in the PP process of mobile robots. In this work, a two-dimensional (2D) map was rasterized with grids containing all the map information. Each grid has a fixed value that indicates the current environmental conditions of the grid. We used occupancy to indicate the degree of the presence of grid obstacles. The occupancy values of the current grid are represented by 0 and 1 if no obstacle is present in the grid and if a grid is fully occupied by obstacles, respectively. However, if an obstacle partially occupies a grid, then its occupancy in the current grid is represented by a value between 0 and 1. The mobile robot occupies a certain physical space; hence, we appropriately extended the obstacles in the map to more reasonably calculate the path safety through the grid. Figure 2(a) shows the rasterized map, where the black grids represent the obstacles. Figure 2(b) presents the map after two obstacle layers had been extended, with the lighter color indicating reduced danger. The obstacles were expanded by three layers, each with 0.7, 0.4, and 0.1 values.

2.3.   Path coding

The path coding is a path representation. This section represents the path by several 2D points and sequential line segments connecting the points. The first point represents the start point of the path, while the last point depicts its target point. The number of other points between is a variable. Two consecutive points corresponded to a line segment of the path. Table 1 is a tabular description of the path coding.

2.4.   Path length objective

Choosing the shortest path is the best option when a robot moves from a starting point to a target point. The path length objective is to obtain the shortest possible path. Expressed mathematically, it is the sum of the lengths of each line segment of a path. Therefore, the line segment formed by any two points is calculated based on the Euclidean distance, where $P$ = [$P_0$, $P_1$, …, $P_i$, $P_{i + 1}$, … $P_n$, $P_{n + 1}$] represents the path $P$. Let $S$ = $P_0$ represent the start point and $T$ = $P_{n + 1}$ be the target point. Equations (2.5) and (2.6) calculate path length objective.

where $P_i$ = ($x_i$, $y_i$) and $P_{i + 1}$ = ($x_{i + 1}$, $y_{i + 1}$) are the two consecutive points in the path, $d$ ($P_i$, $P_{i + 1}$) is the segment distance in the path; $Length$ ($P$) denotes the total path length obtained by summing up all line segments; and $n$ denotes the number of points in the path.

2.5.   Path safety objective

Path safety objective means that the robot should avoid touching or moving away from the obstacles in the environment as it moves through space. It is calculated by adding the occupancy (Subsection 2.2) of the stepped cells of the grid by the robot along the path. In this work, the robot was considered to have the same size as the grid representing the environment. Equation (2.7) calculates the path safety objective as follows:

where $SCells_i$ is the sum of the grid occupancy that the robot travels through the $i$th segment of the path, and $n$ represents the number of points in the path.

3.   IMO-ABC algorithm

This section presents the proposed IMO-ABC algorithm used to solve the multi-objective PP problem. First, the framework of the IMO-ABC algorithm is described. Then, the hybrid initialization strategy and path optimization operators are presented. Subsequently, the variable neighborhood local search strategy and the global search strategy are given, respectively.

3.1.   The framework of IMO-ABC algorithm

Algorithm 1 presents the framework of IMO-ABC algorithm. Compared with the original ABC algorithm, the detailed improvements are described as follows. In the population initialization stage, the IMO-ABC algorithm employs a new hybrid initialization strategy (cf. Subsection 3.2) instead of random initialization to generate the initialization population. To enhance the quality of the initial solutions, the path-shortening operator (cf. Subsection 3.3) is implemented to remove excess polylines from the feasible path. In the employed bee stage, individuals in the population are implemented by the path-crossing operator (cf. Subsection 3.4) and the variable neighborhood local search strategy (cf. Subsection 3.5) sequentially which aims to generate new individuals. Individuals with better objective values are retained based on Pareto dominance and then are thrown to the next stage. It can be noted that the variable neighborhood local search strategy proposed in this study changes the searching neighborhoods of path nodes according to the surrounding environment, which can effectively enhance the local search ability of the algorithm. In the onlooker bee stage, excellent individuals are implemented by the variable neighborhood local search once again to improve the convergence speed of the algorithm. In the scout bee stage, the original ABC algorithm directly removes individuals with long-time evolutionary stagnation, and then generate random solutions to maintain the scale of the population. Similar but different implementation in this study is that global search strategy (cf. Subsection 3.6) provides an effective mechanism for generating new individuals. For the new individuals, one group of individuals is generated by inheriting the excellent individuals in the current Pareto set, and another group of individuals is generated randomly. Compared with the original ABC algorithm, this mechanism can not only enhance the global search ability of the algorithm, but also significantly accelerate the convergence speed of the algorithm.

3.2.   Hybrid initialization strategy

In general, initial individuals with good characteristics are beneficial to accelerate the convergence speed of the algorithm. In this study, we present a hybrid initialization strategy to generate the initial population, which implements based on the RRT algorithm and the space segmentation method of Reference ^[28]. Feasible paths generated by the RRT algorithm have a wide range of randomness. The RRT algorithm explores the configuration space through a tree structure from the start point and incrementally extends the nodes to find a collision-free path until the branches of the tree close to the target point. The steps of the RRT algorithm are described as follows. First, generate a random point in space, traverse the tree nodes from the tree containing the start point, and find the nearest tree node to the random point. Next, a new node is formed by extending a fixed step from the nearest tree node toward the random point; a random point is regenerated if an obstacle exists between the new and nearest nodes, otherwise, a new node is added to the tree. Finally, the abovementioned expansion process is repeated until the distance between the new generated node and the target point is less than the step length. A path connecting the start point to the target point is found.

Figure 3 shows the space segmentation method used to generate initial paths. The black entities are obstacles in the configuration space. $S$ and $T$ represent the start and target points of the robot, respectively. Connect $S$ and $T$ and divide a number of equal-length vertical lines $l_1$, $l_2$, …, $l_n$. Randomly choose points $P_1$, $P_2$, …, $P_n$ on each vertical line and sequentially connect these points to form a new path. This method has a certain directionality from the start to the target point. Hence, it is advantageous for finding these initial solutions with better objectives.

The hybrid initialization strategy is implemented as follows:

Step 1: the RRT algorithm and the space segmentation method are used to generate two solutions.

Step 2: the fitness of the initial solutions generated by these two algorithms is evaluated. The solutions are sorted according to the fitness and deposited in the set $Hc$ = $\{ h_1$, $h_2 \}$ where $h_i = \{1, 2\}$ denotes the $i$th initialization method. The fitness of each solution is deposited in $Fc$ = $\{ f_1$, $f_2 \}$. Equation (3.1) shows the fitness calculation method:

where $O_{CL}$ and $O_{CS}$ represent path length and safety objective values, respectively, after the normalization of the two solutions generated in Step 1, and $O_{IL}$ and $O_{IS}$ are those, respectively, after the normalization of the ideal reference point. The ideal reference point is optimal in each dimension. The ideal value of path length should be the Euclidean distance from the start point to the target point. Path safety is expressed herein by the degree of obstacle possession in the grid. Therefore, the absence of obstacles in the grid indicates a safer path. With this, the ideal safest path value is 0.

Step 3: define a variable $AT_i$ that indicates the number of times each initialization method $h_i$ is used in population initialization. Equation (3.2) is the $AT_i$ calculation method, where $P_s$ is the number of initial solutions desired to be generated.

Step 4: $AT_i$ solutions are generated with $h_i$ until the population size reaches $P_s$.

3.3.   Path-shortening operator

The number of points of each solution in the population is variable; thus, the purpose of executing the path-shortening operator is to reduce redundant points and facilitate solution evolution. The shortening operator is implemented as follows. Sequentially traverse each path in the population and randomly select two nonadjacent points from the path. These two points are directly connected if they satisfy collision detection. The intermediate points and the line segments between these two points are deleted. The new path is saved. If collision detection is not satisfied, the path is saved, and the next path is continuously traversed until the end of the traversal. Figure 4 illustrates the process of the path-shortening operator.

3.4.   Path-crossing operator

Select the two closest points, except for the starting and target points, in the two paths to implement the path-crossing operator and reduce the collision detection risk. The path-crossing operator procedure is performed as follows. Two adjacent paths are sequentially selected from the population. A point is randomly selected from the first path. Then, points on the second path are sequentially traversed to find the closest point to the point selected by the first path for a crossover to form new solutions. If collision detection is not satisfied between the two points, the next closest point from the second path is selected until it is satisfied. If all points on the second path do not satisfy collision detection with the point selected on the first path, another point is randomly selected from the first path, and the abovementioned operations continue. Figure 5 illustrates the process of the path-crossing operator.

3.5.   Variable neighborhood local search strategy

The employed bee and onlooker bee stages used a new variable neighborhood local search strategy for the path points to enhance the algorithm's exploitation capability. The variable neighborhood local search strategy is implemented as follows:

Step 1: determine the proportion of points on the path that participating in the variable neighborhood local search. In this study, this proportion $K_L$ is a variable, which is calculated based on the number of iterations and numerical interval. Equation (3.3) calculates $K_L$ as follows:

where $K_{min}$ and $K_{max}$ are the upper and lower bounds of the numerical interval that directly affects the variable neighborhood local search probability $K_L$. At least $K_{min}$ of the points in a path are selected for local search. At most, $K_{max}$ are selected. $I_c$ is the current number of iterations. $I_{max}$ is the maximum number of iterations.

Step 2: the path points that require local search are selected with probability $K_L$. The nearest distance $d_x$ to the obstacle is calculated for each point. The $d_x$ is used as the radius of the neighborhood of this point. New points are generated in this neighbor range.

Step 3: if the new point satisfies collision detection with the adjacent points of the original point, it is connected with the adjacent points of the original point to form a new path; otherwise, it will be regenerated in the neighbor range.

Step 4: each new solution performs the path-shortening operator with a certain probability. Note that the probability size has no effect on the population evolution. The number of points in each path is not fixed; thus, redundant points must be deleted.

Figure 6 shows the evolution process by using the variable neighborhood local search strategy.

3.6.   Global search strategy

In the traditional ABC algorithm, the scout bee will be allowed to randomly generate the solution if a certain individual that has not improved after reaching $L_m$ exists. However, useful information about the current solution will be lost. We developed a new global search strategy embedded in the scout bee stage, which can effectively utilize the information collected in the previous iterations. The strategy is presented in detail in the following steps. All solutions that are not updated after the $L_m$ iterations are eliminated. Accordingly, there is 50% probability of generating a new solution using the hybrid initialization strategy and 50% probability of generating a new solution using Eq (3.4).

where operator $\otimes$ is the path-crossing operator in Subsection 3.4; $p_{l\max }^{{I_c}}$ is the solution with the largest path length objective value in the Pareto solution set at the current iteration of $I_c$; $p_{s\max }^{{I_c}}$ is the solution with the largest path safety objective value in the Pareto solution set at the current iteration of $I_c$; and $\eta _{new}^{{I_c}}$ is the new solution. A better solution is selected based on the Pareto dominance relationship.

4.   Simulation results and discussion

4.1.   Experimental configuration

Four characteristic maps shown in Figure 7 were used for the simulation test. Map1 shows a structured environment with low-density obstacles. Map2 depicts a scenario with trapped obstacles. Map3 scenario is symmetrical and contains many obstacles. Lastly, Map4 gives a real environment map that cites from Reference ^[31]. Table 2 shows the coordinate distributions of the starting and target points in the tested maps.

4.2.   Performance metrics

The obtained Pareto solution set was analyzed using the performance metrics hypervolume ($Hv$) and set coverage ($SC$) to verify the performance of the proposed algorithm. The $Hv$ metric represents the volume covered by the solutions of the Pareto solution set in the objective function space. The concept related to the $Hv$ metric is as follows: in a $d$-dimensional solution space, $A$ = $\{ a_1$, $a_2$, $a_3$, …, $a_n \}$ is the set of non-dominated solutions and $r$ = $\{ r_1$, $r_2$, $r_3$, …, $r_d \}$ denotes the reference points. The hypercube for each element $a_i$ in set $A$ is calculated as $h({a_i}) = [{a_{i1}}, {r_1}] \times [{a_{i2}}, {r_2}] \times... \times [{a_{id}}, {r_d}]$. The hypervolume of $A$ can be obtained using the union of $\left| A \right|$ hypercubes, the repeatedly covered hypercubes are counted once. Equation (4.1) calculates the hypervolume. Equation (4.2) computes the $SC$ metric.

where $B$ is a set of non-dominated solutions $\{ b_i \}$ covered by the non-dominated solutions $\{ a_i \}$ in $A$. $SC$($A$, $B$) = 0 means that none of the solutions in $B$ is dominated by the solutions in $A$. By contrast, $SC$($A$, $B$) = 1 shows that all solutions in $A$ dominate the solutions in $B$. The dominance relationship between solution sets $A$ and $B$ is asymmetric; hence, $SC$($A$, $B$) and $SC$($B$, $A$) are simultaneously computed.

Finally, the algorithm metrics are analyzed by calculating the reference points in each map. An ideal reference point and a reference point at the nadir are chosen. The nadir point represents the worst in each dimension. Table 3 lists the reference points in each map.

4.3.   Experimental parameter analysis

In general, parameters significantly affect the algorithm performance. The experimental parameters include the population size $P_s$ ^{[23,24,25,29,43]}, maximum number of non-updating iterations $L_m$ ^[44], and variable neighborhood local search variables, $K_{min}$ and $K_{max}$. The population size $P_s$ and the maximum number of non-updating iterations $L_m$ should be appropriately adjusted. Excessively large Ps and Lm could occupy too much computational space and affect the running speed, while excessively small $P_s$ and $L_m$ could result in low-quality solutions beyond our expectations. $K_{min}$ and $K_{max}$ are closely related; thus, they were set as an interval variable [$K_{min}$, $K_{max}$]. Fewer intermediate points exist in each path at the late stage of the experimental evolution. To more precisely perform a local search for the solution, the existence of one point of each path is basically guaranteed to execute the variable neighborhood local search strategy. Therefore, the [$K_{min}$, $K_{max}$] value should be set moderately. We refer to the parameter settings of other multi-objective PP problems and set an appropriate level classification for each parameter. Table 4 shows the suitable parameter levels, the [1.0, 1.0] indicates that 100% of all intermediate points in the path executes the variable neighborhood local search strategy, while [0.1, 0.5] indicates that as the number of iterations increases, a minimum of 10% to a maximum of 50% of the intermediate points in the path are selected to execute the variable neighborhood local search strategy. We used the Taguchi method ^[45] to find the best parameter combination and achieve optimal algorithm performance. Table 5 lists the orthogonal array $L_{16}(4^3)$ to determine the parameter combination. Each combination is run 30 times independently using the IMO-ABC algorithm to obtain statistical results. Figure 8 shows the factor-level trends of these two parameters. Based on the result analysis, we set the appropriate parameter values as $P_s$ = 100, $L_m$ = 15, and [$K_{min}$, $K_{max}$] = [0.1, 0.5].

4.4.   Performance of each part of the proposed algorithm

4.4.1.   Effectiveness of the hybrid initialization strategy

We analyze the performance of the hybrid initialization strategy by implementing two different types of IMO-ABC algorithm: one that includes all the components discussed in Section 3 (IMO-ABC algorithm) and another that embeds all components, except for the hybrid initialization strategy (IMO-ABC-NH). We apply the relative percentage increase (RPI) as a performance measure ^[46]. The results obtained by the two comparison algorithms are collected in 30 independent runs. Equation (4.3) calculates the RPI as follows:

where $Hv_b$ denotes the best $Hv$ value obtained by all comparison algorithms and $Hv_c$ is the best $Hv$ value obtained by the specified algorithm. Table 6 presents the experimental results of both algorithms. The first column shows the different map scenarios. The second column gives the best average $Hv$ values for the two algorithms run independently for 30 times. The last two columns calculate the RPI values of both algorithms.

We performed a multifactor analysis of variance (ANOVA) ^[47] to evaluate whether or not the differences between the two algorithms were significant. Figure 9 shows the ANOVA results of the two algorithms, showing that the hybrid initialization strategy improved the performance of the IMO-ABC algorithm. The hybrid initialization strategy produced an initial population with a better distribution, while the high-quality solution facilitated a rapid population evolution.

4.4.2.   Effectiveness of the variable neighborhood local search strategy

We analyze the performance of the variable neighborhood local search strategy by implementing two different types of IMO-ABC algorithms. We implement two different types of IMO-ABC algorithms: one that includes all the components discussed in Section 3 (referred to as the IMO-ABC algorithm) and one that embeds all the components except the variable neighborhood local search strategy (referred to as IMO-ABC-NV). Table 7 presents the experimental results of both algorithms, and Figure 10 shows their ANOVA results. The proposed variable neighborhood local search strategy can improve the local search capability of the algorithm. The algorithm can adaptively change the search intensity in the evolution using the dynamic probability $K_L$ and the variable search neighborhood, allowing for a detailed exploitation process in the early stages of evolution or an extensive exploration in the later stages.

4.4.3.   Effectiveness of the global search strategy

We analyze the performance of the new global search strategy by implementing two different types of IMO-ABC algorithms: the IMO-ABC and IMO-ABC-NG algorithms. In the IMO-ABC-NG algorithm, the scout bee randomly generates solutions as a global search process. Table 8 presents the experimental results of both algorithms, while Figure 11 shows their ANOVA results. The proposed new global search strategy obtains better results than the random method, utilizing the useful information of solutions in the current Pareto solution set to generate a new solution. In summary, the new global search strategy can improve exploration ability.

4.5.   Algorithm comparison results

We validate the performance of the proposed algorithm by comparing it with those of several other well-known algorithms. All results are the average values of 30 independent runs of the three algorithms, with 100 iterations each. Table 9 presents the mean and standard deviation values of the knee point (solution) of NSGA-II ^[24], MO-PSO ^[28] and IMO-ABC in different maps. The knee point refers to the solution with the smallest distance normalized to the ideal point in the obtained set of non-dominated solutions. All algorithms are characterized by randomness in PP. The data in front of "±" denote the average objective value. The data after "±" show the standard deviation. The data in bold emphases are optimum. The running time is the result of each algorithm after 100 iterations. The IMO-ABC algorithm outperforms the two multi-objective optimization algorithms (i.e., NSGA-II and MO-PSO) in terms of path length, path safety, and running time. The standard deviation values of all objectives in the four maps are the smallest, directly reflecting the better robustness of the proposed algorithm.

We also compare the $Hv$ and $SC$ parameter metrics of the three algorithms. Figure 12 shows the Hv values of the three algorithms in the four maps. The average $Hv$ values of the proposed algorithm are better than the other two algorithms, indicating that the Pareto optimal solution set obtained by IMO-ABC covers a greater area of the solution space. The proposed algorithm converges well and reflects its good robustness from the side. In conclusion, the proposed IMO-ABC is always better than NSGA-II and MO-PSO in solving the PP problem. Table 10 shows the average $SC$ results achieved by the compared algorithms, which indicate that the proposed IMO-ABC covers a higher number of NSGA-II and MO-PSO solutions. Similarly, the proposed algorithm is a better choice than NSGA-II and MO-PSO in solving the PP problem.

Figure 13 shows the approximate Pareto solution sets obtained by the IMO-ABC, NSGA-II and MO-PSO algorithms in different maps. The red points depict the approximate Pareto solution sets obtained by the present algorithm. The green and black points are the approximate Pareto solution sets of NSGA-II and MO-PSO, respectively. The red points have better distribution and are closer to the ideal reference point than the other points. The yellow ideal reference points are not exact because the coordinate range is limited. Table 3 presents detailed data. The figures relatively intuitively show that the proposed IMO-ABC algorithm has advantages over the other two algorithms in solving the PP problem. Figure 14 illustrates the knee point (solution) of the proposed algorithm. The knee point is a solution with a minimum distance from the ideal point. Equation (3.1) gives the distance calculation method. The pink square represents the start point. The red pentagram represents the target point.

We conducted a detailed comparison of the IMO-ABC, NSGA-II, and MO-PSO algorithms to demonstrate the convergence performance of the present algorithm. Figure 15 depicts the convergence curves in the $Hv$ metric for the four scenarios. The red line denotes the convergence curve of the proposed algorithm. The blue line is the convergence curve of the NSGA-II algorithm. Lastly, the green line represents the convergence curve of the MO-PSO algorithm. The IMO-ABC algorithm provides the best initial results for the $Hv$ values compared to the other two algorithms, indicating the effectiveness of the hybrid initialization strategy used in the population initialization stage to generate a high-quality initial population. In addition, it can converge to the optimal value faster, proving that the variable neighborhood local search strategy can find better solutions faster, and that the global search strategy can uncover more valuable solutions and avoid the population from falling into a local optimum. Based on this analysis, the IMO-ABC algorithm is proven to better balance the global search and the local exploitation of the population.

5.   Concluding remarks

In this work, we proposed an improved ABC algorithm to solve the multi-objective PP problem of mobile robots. Two objectives, i.e., path length and path safety, are optimized simultaneously. First, a hybrid initialization strategy employs the RRT algorithm and the space segmentation method to generate the initial population. The RRT algorithm was stochastic, and the solutions it produced basically covered the entire initial population, while the space segmentation method facilitated finding the initial solution with better objective characteristics. The proposed hybrid initialization strategy ensures the diversity of the initial population and the quality of individuals. Then, we adopted the variable neighborhood local search and global search strategies to improve the algorithm exploitation and exploration during the population evolution. The variable neighborhood local search strategy changed searching neighborhoods of path nodes according to the closest distance between the current node and the obstacle in each iteration. The global search strategy utilizes the information of edge solutions in the current Pareto front to generate new solutions to replace the solutions with long-time evolutionary stagnation. Thus, this strategy benefited the population to get rid of the local optimum. In the simulation, we used four representative maps, including a real environment to verify the effectiveness of the proposed algorithm. Taguchi method was employed for parametric analysis to find suitable parameter combinations of the IMO-ABC algorithm. In addition, the effectiveness of each proposed strategy was examined one by one. Compared with the well-known NSGA-II and MO-PSO algorithms, the solution obtained by the proposed algorithm has outstanding advantages in the $Hv$ and $SC$ metrics. Results also indicated that the proposed IMO-ABC algorithm has faster convergence and better robustness than the other two algorithms. Therefore, the proposed algorithm could be an alternative method to solve the multi-objective PP problem for later decision-makers.

This study focused on finding as many feasible paths as possible to provide multiple options for a mobile robot or a decision-maker. The robot or the decision-maker could choose the best path that is more conducive to completing the service task according to the current application scenario. Once a feasible path is selected, the path smoothing module can further smooth the discounted path segments formed by the point set to facilitate path tracking for the service robot. Besides, the static environment was considered in this work, indeed, the PP problem in dynamic environments has been a hot topic in recent years. Therefore, in subsequent studies, the future work mainly focuses on two aspects: 1) design a path smoothing module to produce a path that is easy for the robot to follow; 2) apply the multi-objective optimization methods to solve the considered PP problems under dynamic environments.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (52205529, 61803192), the Natural Science Foundation of Shandong Province (ZR2021QE195, ZR2021MD090, ZR2018BD008, and ZR2016FL13), and the Special Fund Plan for Local Science and Technology Development Lead by Central Authority, and the Guangyue Youth Scholar Innovation Talent Program support received from Liaocheng University (LCUGYTD2022-03).

Conflict of interest

The authors declare that there is no conflict of interest.