International Journal of Control, Automation and Systems 15(X) (2017) 1-16 http://dx.doi.org/10.1007/s12555-016-0443-6

ISSN:1598-6446 eISSN:2005-4092 http://www.springer.com/12555

Heterogeneous-ants-based Path Planner for Global Path Planning of Mobile Robot Applications Joonwoo Lee Abstract: Mobile robots can be applied to a wide range of problems, and the demand for these applications has risen in recent years, increasing interest in the study of mobile robotics. Many studies have examined the path planning problem, one of the most important issues in mobile robotics. However, the grid paths found by traditional planners are often not the true shortest paths or are not smooth because their potential headings are artificially constrained to multiples of 45 degrees. These paths are unfit for application to mobile robots because the high number of heading changes increases the energy required to move the mobile robot. Some studies have proposed a post-processing step to smooth the grid path. However, in this case, the post-smoothed path may not necessarily find the true shortest path because the post-smoothed path is still constrained to headings of multiples of 45 degrees. This study attempts to develop a global path planner that can directly find an optimal and smoother path without postprocessing to smooth the path. We propose a heterogeneous-ants-based path planner (HAB-PP) as a global path planner to overcome the shortcomings mentioned above. The HAB-PP was created by modifying and optimizing the global path planning procedure from the ant colony optimization (ACO) algorithm. The proposed algorithm differs from the traditional ACO path planning algorithm in three respects: modified transition probability function for moving ants, modified pheromone update rule, and heterogeneous ants. The simulation results demonstrate the effectiveness of the HAB-PP. Keywords: Ant colony optimization (ACO), global path planning (GPP), heterogeneous ants (HA), mobile robot applications.

1.

INTRODUCTION

Mobile robots are currently applied in a wide range of applications, and the demand for these applications has risen in recent years, resulting in an increase in the study of mobile robotics. Many studies related to mobile robotics have been published on subjects such as map building, localization, path planning, path tracking, and control of the mobile robot. This study develops a new method to solve path planning problems. Solving a path planning problem involves finding a collision-free and optimal path for a mobile robot from a starting point to a goal point using the available environmental information. The study of path planning can be divided into local and global path planning. In the case of global path planning (GPP) [1–5], the environmental model is precisely defined, and the planning is based on previously provided information. This planning improves the convergence toward the goal point. The main objective of the GPP approach is to find a feasible and optimal path to the goal point. Therefore, in studies of GPP, the computation time is less important than the quality of the path, which is not true for local path planning. On the other hand, local path planning [6–11] is

based on the real-time information of sensors embedded in the robot (e.g., ultrasonic, infrared, laser range finder, and camera). This approach helps the robot to avoid obstacles that appear suddenly or that move around the robot. This paper proposes a method based on the ant colony optimization (ACO) algorithm to solve a GPP problem. To solve the GPP problem, the environment must be expressed in an intelligible way. There are generally four different types of representation [12]. Among them, the composite-space map method is most widely used because it is highly efficient. A space is discretized into a grid of rectangular cells (or voxels), and each cell presents an obstacle or a non-obstacle in the composite-space map method. In this case, a path is a consecutive sequence of cells from a starting point cell to a goal point cell. The complexity of a certain area is expressed by the number of cells in the map, n. Many path planning algorithms use the composite-space map method, such as A∗ (A-star) search algorithms [13–15], genetic algorithms (GAs) [16–19], and ACO algorithms [20–22]. These planners use discrete state transitions that artificially constrain the movement of an agent to multiples of 45 degrees, as shown in Fig. 1. Therefore, the grid paths are often not the true shortest

Manuscript received July 22, 2016; revised January 26, 2017; accepted April 20, 2017. Recommended by Associate Editor Kang-Hyun Jo under the direction of Editor Fuchun Sun. Joonwoo Lee is with the Department of Electrical Engineering, Kyungpook National University (KNU), 80 Daehakro, Bukgu, Daegu 41566, Korea (e-mail: [email protected]).

c ⃝ICROS, KIEE and Springer 1

2

Joonwoo Lee

Fig. 1. Example of movement constrained to multiples of 45 degrees on composite-space map (black cell is obstacle). paths or are not smooth paths, making them unfit for mobile robots because the high number of heading changes increases the energy required to move the mobile robot. To overcome this shortcoming, this paper proposes a new path planner. Many algorithms have been used to solve the GPP problem in the composite-space map. The A∗ search algorithm is widely used in path finding and, until now, has been considered the most efficient method of heuristic search [13–15]. This algorithm conducts an enumerative search in the environment through heuristic functions to find the optimal path. Particle Swarm Optimization (PSO) algorithms [23, 24] are also used as global path planners. The PSO algorithm is a computational method that finds a solution by iteratively trying to improve a candidate solution on the basis of a given measure of quality by moving the particle using simple mathematical formula. Many stochastic optimization algorithms have also been developed to solve the GPP problem. GA is a representative algorithm based on stochastic search [16–19]. The GA is an evolutionary algorithm that finds the optimal path using techniques inspired by natural evolution. ACO algorithms are also frequently used to solve GPP problems [20–22, 25], and they are often compared with GA algorithms to demonstrate their superior performance. Path planning using the ACO algorithm is based on the behavior of real ants. While moving, ants find food deposit pheromones on the way to their nests, and the other ants then follow these deposited pheromones. Although pheromones evaporate as time passes, the ants cooperate to choose a path heavily laden with pheromones. In this way, ants can search for the shortest path from their nest to a food source using only pheromone information. Apart from these algorithms, there are algorithms based on natural processes, such as the artificial bee colony (ABC) algorithm [26] and the immune network algorithm (INA) [27]. However, as mentioned above, the grid paths found by these algorithms are not true optimal paths and are

not smoothed paths because of the characteristics of the composite-space map method, i.e., the heading angle constraint. Some studies propose that a post-processing step be used to smooth the path obtained by a typical algorithm in a post-processing step [25, 27]. In this case, if the path obtained before post-processing is not the shortest or optimal path, then the post-processed path may be smoothed, but it will not necessarily be the optimal path. The proposed heterogeneous-ants-based path planner (HAB-PP) simultaneously finds the shortest and smoothest path without any post-processing step. Although the HAB-PP is based on the ACO algorithm, this algorithm is optimized for better performance as a global path planner [28, 29]. The first ant system (AS) [30] algorithm was successfully applied to combinatorial optimization problems, such as the traveling salesman problem (TSP) [31] and the quadratic assignment problem (QAP) [32]. Traditional path planners using ACO algorithms simply followed previous studies and are not optimized as global path planners. The proposed algorithm differs from the traditional ACO path planning algorithm in three respects. The transition probability function (TPF) and the pheromone update rule (PUR) were modified for improved performance. We also proposed the first introduction of the heterogeneous ants (HA) in the ACO algorithm. Section 3 provides a detailed description of the proposed path planner. This paper presents three simulations. The first simulation shows the expected effects of each proposed HAB-PP scheme in comparison with a conventional ACO (CACO) algorithm. The second simulation compares the performance of the HAB-PP with that of other algorithms, such as the A∗ search algorithm and the GA and CACO algorithms. Finally, the HAB-PP is applied to various GPP problems with a variety of sizes and complexities to verify the effectiveness of the proposed path planner. This paper is organized as follows: Section 2 briefly introduces the CACO path planning algorithm. Section 3 describes the proposed HAB-PP in detail. Section 4 provides a discussion and an overview of the simulation results. Finally, Section 5 presents conclusions regarding the ability of the proposed HAB-PP as a global path planner. 2.

CONVENTIONAL ACO ALGORITHM FOR GPP

This section briefly introduces the CACO algorithm for GPP. The ACO algorithm is a natural metaphor algorithm based on the behavior of real ants. While moving, ants that find food deposit pheromones on the way to their nests, and the other ants then follow these deposited pheromones. Although pheromones evaporate as time passes, they allow ants to cooperate and choose a path that is heavily laden with pheromones. In this way, ants search for the shortest path from their nest to a food source

Heterogeneous-ants-based Path Planner for Global Path Planning of Mobile Robot Applications

Algorithm 1 CACO Algorithm for Global Path Planning. 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28:

GetIn f ormation(Map); SetParameters(NA , NI , NR , α , β , ρ , Q); Initialize(τ , IA , LR ); nI ← 0; ▷ nI : Iteration Number while nI ≤ NI do // New iteration start. nI ← nI + 1; nR ← 0; ▷ nR : Rank List Number while nR ≤ NR do for k = 1 to NA do // Ant k’s travel start. j ← RouletteSelect(pkj ); IA,k ← j; PathPruning( j); if j = g then ▷ g: Goal Point nR ← nR + 1; LR (nR ) ← IA,k ; Initialize(IA,k ); end if end for end while // Sort and Cut LR by NR . Sort(LR (1), · · · , LR (2NR )); LR ← Cut(LR (1), · · · , LR (NR )); // Update pheromone. U pdatePheromone(τ ); end while return LR (1);

using only pheromone information [33]. The basic mathematical model of the ACO algorithm was first applied to the TSP [31]. Conventional path planners using ACO algorithms simply followed the lead of this research on TSP and did not optimize the algorithm to improve its performance as a global path planner. Algorithm 1 shows a universal CACO algorithm for GPP [20–22, 25]. The algorithm is divided into two parts. The first part represents preparation and parameter initialization, and the second part contains a double loop. The first stage of the algorithm collects position information from the map, such as the presence of obstacles and the locations of the starting point and goal point. Afterward, the adjustable user parameters are set, i.e., the number of ants (NA ) and iterations (NI ), the length of the rank list (NR ), and the characteristic parameters for the ACO algorithm (α , β , ρ ). After the parameters are set, the pheromone field τ , which stores the amount of pheromones laid by ants at each location on the map, is initialized with random values, and the array IA , which stores the paths of each ant, is determined with the starting point as the initial value. We also declare the array LR , which stores the paths taken by ants that arrived at the goal point.

3

After this process is completed, the ants begin their travel to find the path from the starting point to the goal point. NA ants take turns moving once from the current point i to the next point j. At this time, each ant chooses the next position randomly by roulette wheel selection with a probability consistent with the distance between the current point and the goal point and consistent with the pheromone intensity. The transition probability from point i to point j for the k-th ant is as follows:  [τ j (nI )]α [η jg ]β   , if j ∈ C,  ∑ [τc (nI )]α [ηcg ]β (1) pkj (nI ) =  c∈C   0, otherwise, where C = {c | c = (8 points around point i)} and is the set of 8 candidate points around the current point i as shown in Fig. 1. The parameters α and β are constants that express the relative influence of the pheromone and the heuristic factor, respectively, on the decision of the ant. The variable η jg is the heuristic desirability, and the visibility is η jg = 1/d jg , where d jg is the Euclidean distance between point j and the goal point g. The variable τ j is the amount of pheromone trail on point j of the grid map. After the kth ant completes its selection, we check whether the path of the k-th ant is a closed-loop, and if so, we prune off the closed-loop path. If the k-th ant arrives at the goal point, then the path found by the k-th ant is stored in the array LR and the k-th ant starts again at the initial point. After the array LR is filled up to NR , we evaluate the NR paths of surviving ants found for an iteration nI until iteration nI − 1 using (2).

∑

fEval (nR ) =

di j ,

(2)

i, j ∈ LR (nR )

where di j is the Euclidean distance between two consecutive points, point i and point j, of the nR -th path in array LR . Next, we determine the ranking of 2 × NR and cut the NR paths in order. These paths are stored again in array LR . After determining the ranking, the pheromone trail amounts are updated. The pheromone trail amount τ j , with a value at point j in the entire grid map, is determined according to the following formula:

τ j (nI + 1) = (1 − ρ ) · τ j (nI ) + ∆τ j ,

(3)

where ρ is the local pheromone decay parameter and ρ ∈ (0, 1) (i.e., the pheromone evaporates as time goes on). The pheromone field (or matrix) is updated after each iteration finishes. Thus, this equation describes the method used to update the pheromone amounts at iteration nI + 1 if iteration nI is the time of the previous update. ∆τ j is the additional pheromone trail amount at iteration nI + 1, given as follows: ∆τ j =

NR

∑ ∆τ nj , R

nR =1

(4)

Joonwoo Lee

4

where ∆τ nj R is the amount of pheromone trail at point j of the nR -th path between iteration nI and iteration nI + 1, given as follows:  Q  , if nR -th path passes point j, ∆τ nj R = fEval (nR )  0, otherwise, (5) where Q is a constant determined by the user based on the grid size of the map. This iteration process continues until the termination conditions are satisfied (e.g., when a certain number of iterations (NI ) have been achieved or when the best path does not change for several iterations). 3. HETEROGENEOUS-ANTS-BASED PATH PLANNER (HAB-PP) As mentioned previously, traditional global path planners using the ACO algorithm are not optimized to solve the path planning problem. Traditional path planners simply followed the lead of previous research. However, the proposed HAB-PP is optimized for better performance and finds the shortest and smoothest path at the same time without any post-processing steps, unlike most path planners. The proposed algorithm differs from the traditional ACO path planning algorithm in three respects. We modified the TPF and PUR. We also introduced the HA concept to the ACO algorithm for the first time. This section first illustrates in detail these differences between the proposed HAB-PP and traditional global path planners and then describes the entire HAB-PP process. 3.1. Modified TPF (MTPF) As mentioned in Section 2, the TPF calculates the probability that an ant will select one of the candidate points as the next point. Traditional path planners used a similar function to solve the TSP, as shown in Eq. (1). However, we supplement and amend this function to effectively deal with the GPP problem [34]. The modified transition probability from point i to point j for the k-th ant is as follows:

p˜kj (nI )

    =

[τ˜ j (nI )]α [η˜ jg ]β [ξ˜ j ]γ ˜ , if j ∈ C, ∑ [τ˜c (nI )]α [η˜ cg ]β [ξ˜c ]γ

˜   c ∈ C 0,

otherwise, (6)

˜ = {c | c = (points in sight-window around point i)}, where C and the sight-window is determined by the dynamic sight expansion principle as introduced in Section 3.3. The variable τ˜ j is the amount of pheromone trail at point j and is determined by the modified PUR that will be introduced in Section 3.2. The variable η˜ jg is the value of the

modified visibility field from the goal point g to point j, and it will be described in more detail later. The variable ξ˜ j is the angle change factor that was newly added to the MTPF, and this will also be treated in more detail in the following section. The parameter α describes the influence of the pheromone on the decision of the ant, while β and γ describe the influence of the heuristic factors. This new MTPF is significantly different in the following three respects. 3.1.1 Factor normalization The value η is a heuristic factor calculated by the Euclidean distance between a certain point and the goal point and is strongly influenced by the size of the map. The amount of pheromone trail, τ , also changes frequently as the pheromone trail is updated. The ants in the ACO algorithm move selectively depending on the probability calculated from the values of these factors. The user parameters α and β are the weighted values of the factors, i.e., the amount of pheromone trail and the visibility value, and these parameters are determined by the user considering map information such as the size and complexity. As mentioned above, however, we cannot know how much the values τ and η change from the map or the environmental information. Therefore, the only way to determine the parameters α and β is through a great deal of trial and error with many experiments whenever a new map is used. It is difficult to know intuitively the effect of each factor (i.e., the amount of pheromone trail and the visibility value) with different weights on the transition probability, because the values τ and η have different ranges and sizes depending on factors such as the number of ants and the size of the map. Therefore, we proposed using the normalized factors to calculate the TPF in this paper. In statistics, data are most frequently normalized to compare two or more groups with different units, ranges and sizes by normalizing the data to the same range [0, 1] by the following formula. For a data set x = {xmin , · · · , x, · · · , xmax }, the numeric variable x is normalized to xnew as shown below. xnew =

x − xmin . xmax − xmin

(7)

As in statistics, we normalize all factors of the TPF in the proposed HAB-PP to enable the user to intuitively select the weighting values α , β and γ by considering the effect of each of the normalized factors, i.e., the values τ˜ , η˜ and ξ˜ on the transition probability at different weighting values. 3.1.2 Modified visibility field The larger the visibility value at a point, the more likely an ant is to select that point. Fig. 2(a) shows the visibility field η used in the universal CACO algorithm for GPP. As shown in the figure, the change in the value, i.e., the

Heterogeneous-ants-based Path Planner for Global Path Planning of Mobile Robot Applications

5

and is computed as follows:

η˜ A, j = 1 −

d jg , max dig

(9)

i∈A

where d jg is the Euclidean distance between point j and the goal point g, and the value dig is the Euclidean distance between point i included in the set A, and the goal point g. The value η˜ A is the normalized value and is computed using the additive inverse concept. The value η˜ R is the value of the repulsive visibility field and is computed as follows:

η˜ R, j = 1 −

Rj , max Ri

(10)

i∈A

where

Fig. 2. Visibility field: (a) traditional visibility field η (b) modified visibility field η˜ .

slope, is very small around the starting point, and the slope rises rapidly around the goal point. In this situation, ants will explore various directions around the starting point by random chance, resulting in a significant amount of time wasted by unnecessary exploration because there is no strong attraction to the goal point. Furthermore, ants around the goal point quickly converge to the goal point without any additional exploration by chance. These problems lead to an imbalance between exploration and exploitation. The modified visibility field (MVF) was proposed to solve these problems and was inspired by the potential field concept in which the total force on the robot is the sum of the attractive force and the repulsive force [35]. The MVF results in an entirely gentle slope toward the goal point wherever ants travel, creating a balance between exploration and exploitation, as shown in Fig. 2(b). In addition, as the MVF uses the potential field concept, we can consider the robot size to plan the global path. The MVF is computed according to the following formula: { kmix · η˜ A, j + (1 − kmix ) · η˜ R, j , η˜ jg = 0,

) (  1 1  1 − , R j = d jo 2 d jo d0  1,

if d jo < d0 , if d jo ≥ d0 ,

where d jo is the minimal distance from the point j to the obstacle, and d0 is the distance over which the obstacle has an influence. This value can be adjusted to consider the robot size. The value η˜ R is also normalized like the value η˜ A , using the additive inverse concept. 3.1.3 Added angle change factor In the HAB-PP, we proposed to add the angle change factor in the TPF to produce a smooth and straight-line path by reducing the number of sudden changes in direction. It is close to impossible for most real mobile robots to suddenly change heading by an angle of more than 90 degrees with a steady speed. However, the traditional global path planners using the ACO algorithm frequently plan zigzag paths that are unfit to apply to real mobile robots because they do not consider this problem with sudden changes in direction. We considered the solution of this problem and the proposed angle change factor ξ˜ j is computed as follows:  θj  1− , if 0 ≤ θ j < π /2, ˜ ξj = (11) π 0.00001, if π /2 ≤ θ ≤ π , j

if j ∈ A, if j ∈ Ac , (8)

where kmix is a constant determined by the user, A is the set of the non-obstacle cells and Ac is the set of obstacle cells in the map. The value η˜ A is the value of the attractive visibility field

where θ j is the angle formed by the straight line including the previous point i − 1 and the current point i and the vector from the point i to the candidate point j as the next point, as shown in Fig. 3. The value θ j is computed by the second law of cosine. The value of the angle change factor ξ˜ is divided into two values by the standard that the value θ j is 90 degrees, the maximum change of direction that can be accomplished suddenly. In the range of 0 ≤

6

Joonwoo Lee

Fig. 3. Angle for angle change factor (black cell is obstacle).

θ j < π /2, the value ξ˜ is also normalized using the additive inverse concept like the other factors in the MTPF. The constant 0.00001 was used instead of 0 to allow for escape when an ant is faced with a dead-end street. 3.2. Modified PUR In the HAB-PP, the PUR was changed significantly to allow for a more efficient solution to the GPP problem. We changed the timing for the updating of the pheromone field and limited the cumulative quantity of pheromone trail at each cell to the range [0.01, 1] for each pheromone update to accommodate the frequent pheromone updating and the change in timing. We also proposed the Path Crossover (PC) scheme and introduced it into the HABPP. Finally, the pheromone trail value was also normalized to the range [0, 1]. These changes will be described in detail in the following text. 3.2.1 Change of timing for pheromone update As mentioned above, the traditional path planners using the CACO algorithm updated the pheromone field when the rank list LR was filled by the ants that arrived at the goal after one iteration. On the other hand, whenever (an) ant(s) arrived, the pheromone field was updated with the information of the arrived ant(s) to achieve rapid convergence, and then the arrived ants restarted their travel at the starting point. We did not use the iteration concept used in the CACO algorithm in which the pheromone field is continuously updated. This method might hinder the exploration role of the planner. To compensate for this problem and control the galloping amount of the pheromone trail at each cell because of the frequent pheromone update, we also limited the maximum and minimum values of the cumulative quantity of pheromone to the range [0.01, 1] for each pheromone update. This limitation could preserve the diversity of paths and the ability to explore. In addition, we were able to reuse abandoned paths that did not reach the goal point at the end of one iteration but still had good portions.

Fig. 4. Example of path crossover. 3.2.2 Path crossover We proposed a path crossover (PC) scheme [36,37] and applied it to the HAB-PP. The PC scheme was inspired by the crossover of GAs, but the proposed scheme was different from that used in the GAs. In the HAB-PP, the PC scheme makes a new path by replacing part of the path with an alternative path for evaluation using the evaluation function in (13)), which compares the paths between the two cross points where the two paths found by different ants meet. This scheme is useful and feasible because all paths that are the gapless sequence from the starting point to the goal point, meet at more than two points. After one movement of the NA ants is complete, the PC scheme is performed on the paths of ants that arrived at the goal point and on several high ranking paths (NP ) of the rank list LR . The number of high ranking paths of array LR that will be used for the PC scheme is determined by the user before the planner begins. Some paths only use the PC scheme to reduce the computation time. Using the PC scheme with all paths is not necessary and takes a considerable amount of time. Fig. 4 presents an example of the PC scheme. In terms of the entire path, the evaluation shows that the path that ant k − 1 found is worse than that found by ant k and that it follows a zigzag path. However, comparing the parts of these paths between two cross points, there are obviously some parts where the part of ant k − 1 is better than that of ant k, such as between point ® and point ¯ and between point ° and point ± in the center of Fig. 4. The PC

Heterogeneous-ants-based Path Planner for Global Path Planning of Mobile Robot Applications

scheme also makes a new and improved path, as shown in the red-square box in Fig. 4, by comparatively evaluating paths between cross points and using the better parts of each path. This scheme allows the path search task to rapidly converge to a good path. This scheme makes a new improved path without additional exploration or exploitation by ants, gaining a significant advantage by combining the better parts of paths that might be abandoned by relying on evaluation of the entire path. In addition, this scheme reduces the frequency of zigzag paths. After the PC scheme, the rank list array LR is filled again with the paths that existed in previous rank list LR , the paths found by the ants that just arrived and the paths made by the PC scheme. Then, we evaluate the paths in the rank list LR in terms of the quality of the entire path. We determine the ranking and cut the NR paths in order. After these tasks are complete, we update the pheromone field with the new rank list. We will discuss this step in detail again when the entire HAB-PP algorithm is described. 3.2.3 Normalized pheromone trail value & evaluation function As mentioned above, the pheromone trail value τ was also normalized by replacing (3) with the following (12). We will describe the practical use of this equation again in detail in Section 3.3. { fEval (nR ), if nR -th path passes point j, ∆τ˜ nj R = 0, otherwise. (12) We also modified the evaluation function to make a smoother and shorter path with fewer changes in direction as follows: fEval (nR ) = wL ·

values of this factor indicating a better path. On the other hand, larger total evaluation values fEval are desirable. The values wL , wA , and wP are constants determined by the user as weighted factors, and the total of these values is 1. The value fL (1) is the best value to evaluate the length of the path, the value fA (1) is the best value to evaluate in terms of the total changes of heading angle, and the value fP (1) is the best value to evaluate the number of passing points in the rank list LR . These values may not lead on exactly the same rankings of the best paths as the total evaluation value LR . These steps are taken to normalize each factor; therefore, the evaluation value fEval has the range [0, 1] and can be used as the normalized pheromone trail value. 3.3. Heterogeneous ants As mentioned above, we proposed the first introduction of the HA approach to the ACO algorithm, and we used it in the HAB-PP to obtain a shorter and smoother path [36]. Fig. 5 shows the species of ants used in the HAB-PP. In the case of the CACO algorithm, all ants move one cell per unit time, like a shortsighted ant in Fig. 5. However, the five different species of ants in the HAB-PP have different ranges of vision and speed. The shortsighted ant (SA) is a type of ant generally used in traditional path planners using the ACO algorithm. The range of sight is around 1 √ cell, and the speed is only 1 or 2 per unit time because of the constrained heading angle. These ants carry out exploration. The general ant (GA) has various sight range and speed, resulting in more candidates for the selection of the next position. The introduction of this GA ant required some modification to the model, so we proposed and introduced the dynamic sight expansion principle and the pheromone interpolation method in the HAB-PP. We will describe the details of these schemes later. The GA

fL (1) fA (1) fP (1) + wA · + wP · , fL (nR ) fA (nR ) fP (nR ) (13)

where  wL + wA + wP = 1,     fL (nR ) =  ∑ di j ,    i, j ∈ LR (nR ) fA (nR ) = ∑ θi ,   i ∈ LR (nR )     f (n ) =  P R ∑ 1,  i ∈ LR (nR )

where fL (nR ) is a factor of the length of the nR -th path in the rank list LR , and di j is the Euclidean distance between two consecutive points. The factor fA (nR ) is related to the extent of the change in direction along the nR -th path, and θ is the angle in Fig. 3, mentioned in the discussion of the added angle change factor. The factor fP (nR ) is the number of passing points in the nR -th path, with smaller

7

Fig. 5. Species of Ants in HAB-PP.

8

Joonwoo Lee

makes a smoother path. The far-sighted ant (FA) has a far sight range and a high speed and reduces the computation time of the algorithm. The remaining two species are super ants that move to the point with the highest probability value among the candidates for the next position. The super general ant (SGA) has various sight ranges and speeds like the GA, makes a smoother path at the end of the algorithm, and plays the role of exploitation. The super far-sighted ant (SFA) also has a far sight range and high speed like the FA. This ant reduces the computation time and makes a smoother path. We proposed two additional schemes to enable the use of this heterogeneous ant population. One is the dynamic sight expansion principle for selecting the next point without colliding into obstacles, and the other is a method to interpolate the pheromone amount between two points. These schemes are described in detail below. 3.3.1 Dynamic sight expansion principle To employ a HA population and freely apply the PC scheme to HAB-PP, we must determine how to expand the sight of the ants (i.e., the number of candidate points for the next point) without leading them to collide into obstacles. The ants in the ACO algorithm do not have full map information and have to select the next point using local information such as the Euclidean distance from the candidate point to the goal point and the information left by previous ants. Ants cannot thoughtlessly expand the sight window because this could lead to a path that passes through obstacles. Therefore, ants must gradually expand their sight from their current point while checking whether an obstacle exists in the sight window. Fig. 6 shows the principle of sight expansion. First, ants expand their sight window (red dashed-line square in the first figure in Fig. 6) or include a line in one of the four directions in the sight window. Then, the ants confirm whether an obstacle cell exists in the expanded sight window. If an obstacle cell is included in the sight window, ants cannot further expand the window in the direction of the obstacle and can only expand the window in the other directions. Ants continuously expand the sight window until all directions are constrained by obstacles. In this paper, we refer to this method as the "dynamic sight expansion principle". Fig. 6(a) illustrates the principle for the GA and SGA, and Fig. 6(b) illustrates the principle for the FA and SFA. Except for the obstacle cells, all cells in the red area including the sight window are candidate points for the next movement. As mentioned before, different species have different sight windows, and the size of this window determines the speed of the ant. SAs have eight cells around the current point as their sight window, and all cells except for the obstacle cells are candidate points for other ants.

Fig. 6. Dynamic sight expansion principle: (a) For general ants and super general ants (b) For far-sighted ants and super far-sighted ants. 3.3.2 Pheromone interpolation between points Using the heterogeneous ants but excluding SAs leads to a minor problem. The fact that ants skip one or many

Heterogeneous-ants-based Path Planner for Global Path Planning of Mobile Robot Applications

9

Algorithm 2 HAB-PP for Global Path Planning.

Fig. 7. Pheromone interpolation between points. cells means that no pheromone information is deposited in the cells that ants skip, hindering the ability of the next ants to select cells and generate a consecutive path. To solve this problem in this paper, we proposed pheromone interpolation between points, a method that fills empty cells with the same pheromone trail values as the current point or next point, as shown in Fig. 7. This method does not affect the path information and only interpolates the pheromone information in the pheromone field. This interpolation is also useful for the PC scheme. 3.4. HAB-PP algorithm This section describes the overall outline of the HABPP. The HAB-PP is divided into two parts like the CACO algorithm for GPP, as shown in Algorithm 2. The first part consists of preparation and parameter initialization. First, we collect position information from the map such as obstacles and the starting and goal points. Next, we set the adjustable user parameters. The HAB-PP has more parameters than the CACO algorithm because it uses different species of ants. We set the adjustable user parameters, i.e., the number of SAs (NSA ), GAs (NGA ), SGAs (NSGA ), FAs (NFA ), SFAs (NSFA ) and paths for the PC scheme (NP ), the length of the rank list (NR ), the characteristic parameters for the ACO algorithm (α , β , ρ ), the parameter for the added angle change factor (γ ), the weighted factor for the MVF (kmix ), the parameter related to the influence of an obstacle on the MVF (d0 ), and the weighted factors for the evaluation function (wL , wA , wP ). After the parameters are set, the values of the visibility field ahead are calculated and stored in the matrix η˜ , and the pheromone field τ˜ is initialized with the values of the visibility field η˜ . The array IA is determined with the starting point as the initial value. We also declare the array LR . After this process is completed, the ants begin their travel to find a path from the starting point to the goal point. NA ants, where NA is the total number of ants and NA = NSA + NGA + NSGA + NFA + NSFA , take turns moving once from the current point i to the next point j. At this time, each ant chooses its next position randomly by roulette wheel selection according to the probability function in Eq. (6). After the k-th ant finishes its selection, we

1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29:

GetIn f ormation(Map); SetParameters(NSA , NGA , NFA , NSGA , NSFA , NP , NR ); SetParameters(α , β , γ , ρ , kmix , d0 , wL , wA , wP ); Initialize(τ˜ , η˜ , IA , LR ); nI ← 0; ▷ nI : Iteration Number while Termination condition doesn’t meet do nI ← nI + 1; nR ← 0; ▷ nR : Rank List Number for k = 1 to NA do ▷ NA : # of Total Ants // Ant k’s travel start. j ← RouletteSelect( p˜kj ); IA,k ← j; PathPruning( j); if j = g then ▷ g: Goal Point nR ← nR + 1; LR (NR + nR ) ← IA,k ; Initialize(IA,k ); end if end for if Arrived ant(s) exist then ▷ nR > 0 PathCrossover(LR (1), · · · , LR (NP ), LR (NR + 1), · · · , LR (NR + nR )); end if // Sort and Cut LR by NR . Sort(LR (1), · · · , LR (NR + nR ), · · · , LR (NR + nR + NP )); LR ← Cut(LR (1), · · · , LR (NR )); // Update pheromone. U pdatePheromone(τ ); end while return LR (1);

check whether the path of k-th ant has a closed-loop path or not, and if so, we prune off the closed-loop portion of the path as in the CACO algorithm. If the k-th ant arrives at the goal point, the path found by the k-th ant is stored in the array LR and the k-th ant starts the tour again at the starting point. From here, the HAB-PP differs from the CACO algorithm. After completing the movement of NA ants once, if one or more ants arrive at the goal point, we execute the PC scheme with the paths found by the arrived ants and the NA high ranking paths from the rank list LR . If the arrived ants are first in the rank list, then the PC scheme is skipped. After implementing the PC scheme, the rank list LR is filled again with the NR paths that survived from the previous rank list LR , the nR paths found by the ants that just arrived, and the NP paths made by the PC scheme. Then, we evaluate the paths using Eq. (13) and determine the ranking of the NR + nR + NP paths. We cut the NR paths in order and store them in the rank list LR again. After determining the rankings, the pheromone trail

Joonwoo Lee

10

amounts in the pheromone field are updated. The pheromone trail amount τ˜ j , with the value at point j in the entire grid map, is determined according to the following formula:

τ˜ j (nI + 1) = (1 − ρ ) · τ˜ j (nI ) + ∆τ˜ j ,

(14)

where ρ is the local pheromone decay parameter and ρ ∈ (0, 1). ∆τ˜ j is the added pheromone trail amount at the iteration nI + 1, given as follows: NR

∆τ˜ j =

∑

∆τ˜ nj R ,

Table 1. Characteristics of HAB-PP. Characteristic Modified Transition Probability Function (MTPF)

(15)

nR =1

∆τ˜ nj R

where is the amount of pheromone trail at point j of the nR -th path between iteration nI and iteration nI + 1, given as (12). This iteration process continues until the termination conditions are satisfied, which in the HAB-PP occurs when the rank list LR no longer changes after the pheromone update. Thus far, we described the characteristics of the HABPP in detail and showed how the method is implemented and applied. Table 1 summarizes the characteristics of the HAB-PP algorithm and its effects. All the proposed schemes act in concert, resulting in improved performance when applied together. 4.

SIMULATION RESULTS AND DISCUSSION

This section presents some experimental results and evaluates the performance of the HAB-PP. We implemented the simulation in MATLAB. All simulations were implemented on a PC with an Intel Core i5 CPU 760 @ 2.80GHz and 4GB of RAM. Three simulations were conducted in this study. The first simulation shows the expected effect of each proposed scheme in the HAB-PP by comparison with the CACO algorithm. In the second simulation, the performance of the HAB-PP is compared with that of other algorithms, such as the A∗ search algorithm and the GA and CACO algorithms. Finally, we apply the HAB-PP to various GPP problems with a variety of sizes and complexities to verify the effectiveness of the proposed path planner. The following subsections present the detailed results and discussion for each simulation. 4.1. Verification for effects of proposed schemes In the first simulation, we verify the expected effect of each proposed scheme by comparing a base CACO planner with each scheme added one by one to the planner. It is actually difficult to verify the expected effect of all the schemes proposed in this paper as given in Table 1. Because most of the schemes that affect the internal performance are intimately connected to the other schemes and work to improve the performance of the HAB-PP, it is

Modified pheromone update rule (MPUR)

Scheme Factor normalization Modified visibility field (MVF) Added angle change factor Change of timing for pheromone update Limit of cumulative pheromone quantity

Expected effect Instinctive parameter value selection Reduce computation time Consideration of robot size Straight-line path Fast convergence Path diversity and exploration

Path crossover (PC)

Fast convergence Additional path obtained widthout search

Normalized pheromone trail value

Instinctive parameter value selection

Reduce computation time Stright-line path Stright-line path Dynamic sight Support path crossover expansion principle scheme Pheromone Support path interpolation crossover scheme between points Various species of ants

Heterogeneous ant (HA)

Table 2. Method for verifying expected effects of proposed schemes. Scheme Modified visibility field (MVF)

Expected effect Rdulce computation time Consider robot size

Added angle change factor Strsight-line path (ACF) Path Crossover (PC) Heterogeneous ant (HA)

Verification method Computation time Path figure Path figure Path length Total heading angle change / Number of times

Fast convergence

Computation time

Reduce compuation time

Computation time

Straight-line

Path figure Path length Total heading angle change / Number of times

not easy to confirm the expected effect of each scheme individually by the superficial results of the simulation such as the path, path length, and computation time. Therefore, we will only consider schemes as verified if their effects can be confirmed by the superficial results of the simulation and if they make a significant contribution to the proposed HAB-PP. Table 2 shows the schemes used in the simulations, their expected effects and the method used to

Heterogeneous-ants-based Path Planner for Global Path Planning of Mobile Robot Applications

11

Table 3. Computation time (sec) as first simulation results. Sim1 CACO ACO with MVF ACO with PC ACO with HA

Min 550.7641

Max 995.7778

Mean 730.6264

S.D. 150.1885

151.4515

242.9154

195.5897

33.9797

51.4634

69.4085

60.8969

6.7336

60.0861

81.7251

68.7169

6.8281

Table 4. Path length as first simulation results. Sim1 CACO ACO with ACF ACO with HA

Min 80.3259

Max 87.9828

Mean 84.2614

S.D. 2.1536

76.6690

80.6690

78.6761

1.5645

72.4619

76.6685

74.5733

1.1160

Table 5. Total heading angle change (degree) / number of times as first simulation results. Sim1 CACO ACO with ACF ACO with HA

Min 1755.0 / 49 1440.0 / 48 220.8 / 18

Max 2115.0 / 57 1620.0 / 52 256.7 / 20

Mean 1944.0 / 53.0 1530.0 / 49.9 233.9 / 18.8

S.D. 115.8 / 2.7 73.5 / 1.7 11.8 / 0.8

verify their effects. The map for the first simulation is a 50 × 50 grid size map as shown in Fig. 8. The black cell is an obstacle, the red square is the starting point, and the blue square with a white star is the goal point. In the first simulation, each condition was tested with 30 runs. First, the expected effects of using the MVF in the TPF are to reduce the overall computation time and to enable path finding considering the robot size without additional map information, e.g., expanding the obstacle size based on the robot size. These effects can be verified using the path figure and comparing the computation time with the planner using the CACO algorithm. The parameters for the CACO planner were set as follows: NA = 100, NI = 50, NR = 50, α = 2, β = 1, ρ = 0.1, and Q = 100. For the ACO planner using the MVF, parameters shared with the original were set equally, and MVF parameters were selected as follows: kmix = 0.5, d0 = 2 (without considering the robot size), and d0 = 5 (considering the robot size). Table 3 shows the overall computation time required to find a final path using each scheme. From Table 3, using the MVF improved the computation time by about 73% compared to the original. Fig. 8 shows the paths found using each scheme, where the dashed black line is the path determined considering the robot size and the bold green line is the path without considering the size. The dashed black line demonstrates that the MVF enables the consideration of the robot size.

Fig. 8. First simulation results using each scheme: (a) CACO algorithm (b) Using modified visibility field (with and without considering robot size) (c) Using angle change factor (d) using heterogeneous ant. Next, for the ACO planner with the ACF added in the TPF, the expected effect of this scheme is a path with fewer zigzags compared to the path determined using the original TPF. This effect can be verified by comparing the path figure, the path length, and the total amount and number of heading angle changes. For the parameter setting of the ACO planner using the ACF, parameters in common with the original were set equally, and γ was set to 1 in the ACF. The path in Fig. 8(a) was found using the CACO planner and the path in Fig. 8(c) was obtained using the ACO planner with the ACF. Although there seems to be little difference in the figures, the path length in Table 4 and the total amount and number of heading angle changes in Table 5 show that the ACO planner using the ACF has improved the path, with a 6.6% reduction in the path length and about 21% and 5.8% decreases in the total amount and number of heading angle changes, respectively, compared to the original. The expected effect of the PC scheme is rapid convergence to an optimal path. The quality of the optimal path must be preserved despite the rapid convergence. However, as mentioned before, the PC scheme alone, cannot guarantee the quality of the result path. For this reason, this simulation checks whether the PC scheme reduces the computation time as compared to the original. For the ACO planner using the PC, the parameters in common with the original were set equally, and the additional

12

Joonwoo Lee

parameter for the PC scheme was set as NP = 5. As shown in Table 3, the computation time of the ACO planner using the PC is about 92% less than that of the original. Therefore, it is possible to effectively implement the PC scheme. Finally, the expected effects of the HA are a reduction the computation time and the production of a straight-line path with fewer changes in heading angle, compared to the CACO planner. These facts can be verified by comparing the computation time, the path figure, the path length, and the total amount and number of heading angle changes. The additional parameters of the ACO planner with the HA were set as follows: NSA = 50, NGA = 20, NFA = 20, NSGA = 5, and NSFA = 5. The remaining parameters in common with the CACO planner were set equally. First, Table 3 shows that the ACO planner with the HA has a computation time about 91% less than the original. Moreover, as shown in Fig. 8(d), the quality of the path has clearly improved compared with the path found by the CACO planner in Fig. 8(a). This improvement can be also verified by comparing the path length and the total amount and number of heading angle changes. Table 4 shows that the length of the path determined by the ACO planner with HA was reduced by about 11%. In addition, from Table 5, this planner reduced the total amount and number of heading angle changes by about 88% and 65%, respectively, in comparison with the original. The first simulation verified the expected effects of various schemes that substantially contribute to the performance of the HAB-PP. As mentioned above, all proposed schemes are intimately connected to the other schemes and work in conjunction to improve the overall performance of the HAB-PP. The remaining simulations will characterize the overall performance of the proposed HAB-PP. 4.2. Comparison with other planners In the second simulation, we compare the HAB-PP with several well-known planners. As mentioned in the introduction, the computation time is less important in GPP than in local path planning as both methods must avoid obstacles in real time. Instead, finding a high quality path within enough time is more important than reducing the computation time as much as possible. A good quality path in GPP means not only the shortest path but also the path that minimizes the total amount and number of heading angle changes when a mobile robot travels along the path. The frequency of heading angle changes is directly related to sharp energy consumption by the real mobile robot, which has limited energy. Therefore, considering this property of GPP, we verify the performance of the HAB-PP by results that compare the quality of the paths chosen by various planners. The second simulation compares the HAB-PP with the most widely used path planners: the A∗ algorithm, used as a global path planner; a path planner based on GAs,

Table 6. Path length as second simulation results using Sim2Map1. Sim2Map1 A* GA CACO HAB-PP

Min 32.3848 32.3848 32.3848 31.8964

Max 32.3848 38.6274 37.6274 33.2013

Mean 32.3848 34.8061 35.3304 32.0975

S.D. 0 2.2446 1.9962 0.7753

Table 7. Total heading angle change (degree) / number of times as first simulation results using Sim2Map1. Sim2Map1 A* GA CACO HAB-PP

Min 495.0 / 18 405.0 / 17 450.0 / 17 225.0 / 13

Max 495.0 / 18 585.0 / 21 540.0 / 20 245.4 / 15

Mean 495.0 / 18 495.0 / 18.5 504.0 / 18.3 236.1 / 13.8

S.D. 0/ 0 67.1 / 1.4 41.4 / 1.1 6.8 / 0.6

a common model that is thought to be comparable with ACO algorithms; and the path planner using the conventional ACO algorithm mentioned in the previous simulation. The GA used here is a state-of-the-art GA GPP [19]. Two maps were used for the simulation. The first map, Sim2Map1, is a simple 20 × 20 grid as shown in Fig. 9, and the other map is a complex 30 × 30 grid as shown in Fig. 11. The black cells in the maps represent obstacles, the red square is the starting point, and the blue square is the goal point. The second simulation was run 30 times to generate statistical repeats. The parameters for the HABPP were set as follows: NSA = 50, NGA = 20, NFA = 20, NSGA = 5, NSFA = 5, NP = 5, NR = 30, α = 2, β = 1, γ = 1, ρ = 0.1, kmix = 0.8, d0 = 2, and wL = wA = wP = 0.333. According to the result of the simulation using Sim2map1, the A∗ planner and the HAB-PP performed better than the other planners in terms of the path length as given in Table 6. However, with respect to the total heading angle changes and the number of angle changes, the proposed planner performed the best as shown in Table 7. Fig. 9 shows the paths found by each planner. As the results show, the paths can be classified into two groups, i.e., the upper paths (found by the CACO planner and the HAB-PP) and the lower paths (found by the A∗ planner and the GA planner) around the vertical rectangle at the center of the right side of the map. A direct calculation of the length of the two paths, as shown in Fig. 10, showed that the upper path (length: 31.7098) is shorter than the lower path (length: 32.9499). If a planner uses a post-processing step to make a smoother path after finding a path like the lower path, it cannot guarantee that the obtained path is the optimal one. Therefore, the HAB-PP selected the upper path and outperformed other planners without requiring a post-processing step.

Heterogeneous-ants-based Path Planner for Global Path Planning of Mobile Robot Applications

13

Table 9. Total heading angle change (degree) / number of times as first simulation results using Sim2Map2. Sim2Map2 A* GA CACO HAB-PP

Min 405.0 / 30 504.0 / 30 630.0 / 32 149.5 / 16

Max 405.0 / 30 720.0 / 34 810.0 / 34 189.7 / 20

Mean 405.0 / 30 639.0 / 32 724.5 / 33.5 164.8 / 17.6

S.D. 0/ 0 66.4 / 1.8 57.9 / 1.0 12.2 / 1.6

Fig. 9. Second simulation results comparing with other path planners using Sim2Map1.

Fig. 11. Second simulation results comparing with other path planners using Sim2Map2. Fig. 10. Paths obtained from visibility graph: (a) Used by CACO and HAB-PP (b) Used by A∗ and GA. Table 8. Path length as second simulation results using Sim2Map2. Sim2Map2 A* GA CACO HAB-PP

Min 42.7696 43.9411 44.7696 42.7117

Max 42.7696 47.7696 49.0122 43.9774

Mean 42.7696 46.0553 47.4495 43.0921

S.D. 0 1.3026 1.4335 0.4981

For Sim2map2, the A∗ planner and the HAB-PP also found shorter paths than the other planners, as given in Table 8. Furthermore, the HAB-PP also outperformed other planners with respect to the total heading angle change and the number of changes, as given in Table 9. Fig. 11 depicts the paths obtained by each path planner. The second simulation compared the performance of

the HAB-PP with several other planners. These simulation results lead us to the conclusion that the path obtained by the HAB-PP is of a higher quality than paths obtained by other planners. 4.3. Simulations in various environments In the third simulation, we conduct path planning with the HAB-PP under six different environments, as shown in Fig. 12. Sim3Map1 is a small and simple 52 × 52 grid, Sim3Map2 is a small and complex 50 × 44 map, Sim3Map3 is a large and simple 100 × 100 map, and Sim3Map4 is a large and complex 100 × 100 map. Sim3Map5 and Sim3Map6 are real case maps with a 100 × 100 grid size in an office environment and a 160 × 170 grid size in an apartment environment, respectively. In each map, the black cells represent obstacles, the red square is the starting point, and the blue square is the goal point. The simulation was performed for 30

14

Joonwoo Lee

Table 10. Path length as third simulation results. Sim3 Sim3Map1 Sim3Map2 Sim3Map3 Sim3Map4 Sim3Map5 Sim3Map6

Min 71.4870 59.9405 116.6936 119.7864 127.5754 225.8972

Max 75.2570 64.8450 121.2549 121.6060 137.4370 239.6275

Mean 73.2190 62.6821 118.3059 120.6369 131.3110 231.9677

S.D. 1.2968 1.7230 1.5754 0.6368 3.5609 5.0876

environments, and the results showed that the HAB-PP exhibited acceptable and, in fact, outstanding performance as a global path planner. 5.

Fig. 12. Third simulation results applying HAB-PP to various environments. runs. The parameters of the HAB-PP for Sim3Map1 and Sim3Map2 were set as follows: NSA = 50, NGA = 20, NFA = 20, NSGA = 5, NSFA = 5, NP = 5, NR = 30, α = 2, β = 1, γ = 1, ρ = 0.1, kmix = 0.8, d0 = 2, and wL = wA = wP = 0.333. The parameters of the HAB-PP for Sim3Map3 and Sim3Map4 were set as follows: NSA = 80, NGA = 30, NFA = 30, and the rest of the parameters were set the same as in the previous case. The parameter settings for Sim3Map5 were the same as the previous case except for β = 2. Finally, for Sim3Map6, the parameters were set as follows: NSA = 100, NGA = 30, NFA = 30, NSGA = 5, NSFA = 5, NP = 5, NR = 30, α = 2, β = 1, γ = 1, ρ = 0.1, kmix = 0.8, d0 = 2, and wL = wA = wP = 0.333. Fig. 12 shows the paths found by the HAB-PP under each environment. The obtained paths are entirely smooth and feasible and would be acceptable for use by a real mobile robot. Most planners have difficulties finding a feasible and optimal path in maps that require a reversal of direction, such as Sim3Map5, but the HAB-PP is able to find the appropriate path. Table 10 reports the length of each path. The third simulation applied the HAB-PP to different

CONCLUSIONS

This paper reported the development of a global path planner that can directly find an optimal and smooth path without post-processing to smooth the path. The paths found by traditional planners based on the grid representation of the map were often not truly the shortest paths or were not smooth paths because their heading choices are artificially constrained to multiples of 45 degrees. These grid paths are unfit for applications with mobile robots because they require many heading changes, thereby significantly increasing the energy required to move the mobile robot. Some studies have proposed the use of a postprocessing step to smooth the grid path. However, these paths smoothed by post-processing may not be the shortest path because they are based on a path found with headings constrained to multiple of 45 degrees. This paper proposed the HAB-PP as a global path planner to overcome these drawbacks. The HAB-PP is created by modification and optimization of the ACO algorithm for GPP. The proposed algorithm differed from the traditional ACO algorithm for path planning in three respects. We modified the TPF and PUR for better performance. We also proposed the first introduction of HA in the ACO algorithm. Three simulations characterized the performance and demonstrated the effectiveness of the HAB-PP. The first simulation verified the expected effects of several schemes that make significant contributions to the performance of the HAB-PP. As mentioned above, all the proposed schemes are intimately connected to the other schemes and work together to improve the overall performance of the HAB-PP by helping one another. The second simulation compared the performance of the HAB-PP with several well-known planners, and the simulation results lead us to the conclusion that the path obtained by the HAB-PP is superior in quality to those obtained using other planners. Finally, the third simulation applied the HAB-PP to various environments, and the simulation results showed that the HAB-PP had not only acceptable but also outstanding performance as a global path planner.

Heterogeneous-ants-based Path Planner for Global Path Planning of Mobile Robot Applications

REFERENCES [1] G. Chesi and Y. S. Hung, “Global Path-planning for constrained and optimal visual servoing,” IEEE Trans. on Robotics, vol. 23, no. 5, pp. 1050-1060, October 2007. [click] [2] J.-W. Lee, D.-H. Lee, and J.-J. Lee, “Global path planning using improved ant colony optimization algorithm through bilateral cooperative exploration,” Proc. of the 5th IEEE Int. Conf. on Digital Ecosystems and Technologies, Daejeon, pp. 109-113, May-June 2011. [3] D. R. Parhi and J. C. Mohanta, “Navigational control of several mobile robotic agents using Petri-potential-fuzzy hybrid controller,” Applied Soft Computing, vol. 11, no. 4, pp. 3546-3557, June 2011. [click] [4] M. Davoodi, M. Abedin, B. Banyassady, and P. Khanteimouri, “An optimal algorithm for two robots path planning problem on the grid,” Robotics and Autonomous Systems, vol. 61, no. 12, pp. 1406-1414, December 2013. [click] [5] S. Panov and S. Koceski, “Metaheuristic global path planning algorithm for mobile robots,” Int. J. of Reasoningbased Intelligent Systems, vol. 7, no. 1-2, pp. 35-41, 2015. [click] [6] S.-H. Park and B.-H. Lee, “A new analytical representation to robot path generation with collision avoidance through the use of the collision map,” Int. J. of Control, Automation, and Systems, vol. 4, no. 1, pp. 77-86, February 2006. [7] D. H. Kim, “Escaping route method for a trap situation in local path planning,”, Int. J. of Control, Automation, and Systems, vol. 7, no. 3, pp. 495-500, June 2009. [8] B.-S. Choi, J.-W. Lee, J.-J. Lee, and K.-T. Park, “A hierarchical algorithm for indoor mobile robot localization using RFID sensor fusion,” IEEE Trans. on Industrial Electronics, vol. 58, no. 6, pp. 2226-2235, June 2011. [click] [9] Q. Zhu, J. Hu, W. Cai, and L. Henschen, “A new robot navigation algorithm for dynamic unknown environments based on dynamic path re-computation and an improved scout ant algorithm,” Applied Soft Computing, vol. 11, no. 8, pp. 4667-4676, December 2011. [10] X. Gao, Y. Ou, Y. Fu, Z. Li, D. Dai, L, Cui, Y. Zhou, and W. Guo, “A novel local path planning method considering both robot posture and path smoothness,” Proc. of the IEEE Int. Conf. on Robotics and Biomimetics, Shenzhen, pp. 172178, December 2013. [11] U. A. Syed, F. Kunwar, and M. Iqbal, “Guided autowave pulse coupled neural network (GAPCNN) based real time path planning and an obstacle avoidance scheme for mobile robots,” Robotics and Autonomous Systems, vol. 62, no. 4, pp. 474-486, April 2014. [click]

15

[14] J. Yao, C. Lin, X. Xie, A. j. Wang, and C.-C. Hung, “Path planning for virtual human motion using improved A* star algorithm,” Proc. of Seventh Int. Conf. on Information Technology: New Generations, Las Vegas, pp. 1154-1158, April 2010. [click] [15] J.-H. Seok, J.-W. Lee, J.-H. Wang, J.-J. Lee, and H. J. Lee, “A temporal path planner for solving information inconsistency in an integrated path planner,” Int. J. of Control, Automation, and Systems, vol. 11, no. 6, pp. 1232-1240, December 2013. [click] [16] T. W. Manikas, K. Ashenayi, and R. L. Wainwright, “Genetic Algorithms for Autonomous Robot Navigation,” IEEE Instrumentation and Measurement Magazine, vol. 10, no. 6, pp. 26-31, December 2007. [click] [17] J. Zhao, L. Zhu, G. Liu, G. Liu, and Z. Han, “A modified genetic algorithm for global path planning of searching robot in mine disasters,” Proc. of IEEE Int. Conf. on Mechatronics and Automation, Changchun, pp. 49364940, August 2009. [18] J. Berger, K. Jabeur, A. Boukhtouta, A. Guitouni, and A. Ghanmi, “A hybrid genetic algorithm for rescue path planning in uncertain adversarial environment,” IEEE Congr. on Evolutionary Computation, Barcelona, pp. 1-8, July 2010. [19] S. C. Yun, V. Ganapathy, and L. O. Chong, “Improved Genetic Algorithms based Optimum Path planning for Mobile Robot,” Proc. of IEEE 11th Int. Conf. on Control Automation Robotics and Vision, Singapore, pp. 1565-1570, December 2010. [20] D. Zhao and J. Yi, “Robot planning with artificial potential field guided ant colony optimization algorithm,” Int. Conf. of Natural Computation, Xian, pp. 222-231, September 2006. [click] [21] M. A. Porta Garcia, O. Montiel, O. Castillo, R. Sepulveda, and P. Melin, “Path planning for autonomous mobile robot navigation with ant colony optimization and fuzzy cost function evaluation,” Applied Soft Computing, vol. 9, no. 3, pp. 1102-1110, June 2009. [click] [22] K. Ioannidis, G. Ch. Sirakoulis, and I. Andreadis, “Cellular ants: A method to create collision free trajectories for a cooperative robot team,” Robotics and Autonomous Systems, vol. 59, no. 2, pp. 113-127, February 2011. [click] [23] H. Mo and L. Xu, “Research of biogeography particle swarm optimization for robot path planning,” Neurocomputing, vol. 148, pp. 91-99, January 2015. [click] [24] B. Tang, Z. Zhu, and J. Luo, “Hybridizing particle swarm optimization and differential evolution for the mobile robot global path planning,” Int. J. of Advanced Robotic Systems, vol. 13, pp. 1-17, May 2016.

[12] S. Bandi and D. Thalmann, “Space discretization for efficient human navigation,” Computer Graphic Forums, vol. 17, no. 3, pp. 195-206, August 1998.

[25] H. Duan, Y. Yu, X. Zhang, and S. Shao, “Three-dimension path planning for UCAV using hybrid meta-heuristic ACODE algorithm,” Simulation Modeling Practice and Theory, vol. 18. no. 8, pp. 1104-1115, September 2010.

[13] P. Melchior, B. Orsoni, O. Lavialle, A. Poty, and A. Oustaloup, “Consideration of obstacle danger level in path planning using A∗ and Fast-Marching optimisation: comparative study,” Signal Processing, vol. 83, no. 11, pp. 2387-2396, November 2003. [click]

[26] M. A. Contreras-Cruz, V. Ayala-Ramirez, and U. H. Hernandez-Belmonte, “Mobile robot path planning using artificial bee colony and evolutionary programming,” Applied Soft Computing, vol. 30, pp. 319-328, May 2015. [click]

16

Joonwoo Lee

[27] Y. Lan, J. Huang, and X. Chen, “Research on intelligent vehicle path planning based on artificial immune network algorithm,” J. of Information & Computational Science, vol. 12, no. 16, pp. 6023-6032, November 2015. [28] J.-W. Lee, Y.-I. Cho, M. Sugisaka, and J.-J. Lee, “Study of novel heterogeneous ant colony optimization algorithm for global path planning,” IEEE Int. Symp. on Industrial Electronics, Bari, pp. 1961-1966, July 2010. [29] J.-W. Lee, B.-S. Choi, K.-T. Park, and J.-J. Lee, “Comparison between heterogeneous ant colony optimization algorithm and genetic algorithm for global path planning of mobile robot,” IEEE Int. Symp. on Industrial Electronics, Gdansk, pp. 881-886, June 2011. [click] [30] M. Dorigo, V. Maniezzo, and A. Colorni, “Ant system: optimization by a colony of cooperating agents,” IEEE Trans. on Systems, Man, and Cybernetics - Part B, vol. 26, no. 1, pp. 29-41, February 1996. [click] [31] M. Dorigo and L. M. Gambardella, “Ant colony system: a cooperative learning approach to the traveling salesman problem,” IEEE Trans. on Evolutionary Computation, vol. 1, no. 1, pp. 53-66, April 1997. [click] [32] L. M. Gambardella, E. D. Taillard, and M. Dorigo, “Ant colonies for the quadratic assignment problem,” J. of the Operational Research Society, vol. 50, no. 2, pp. 167-176, February 1999. [33] J.-W. Lee, B.-S. Choi, and J.-J. Lee, “Energy-efficient coverage of wireless sensor networks using ant colony optimization with three types of pheromones,” IEEE Trans. on Industrial Informatics, vol. 7, no. 3, pp. 419-427, August 2011. [click] [34] J.-W. Lee, J.-J. Kim, B.-S. Choi, and J.-J. Lee, “Improved ant colony optimization algorithm by potential field concept for optimal path planning,” Proc. of 8th IEEE-RAS Int. Conf. on Humanoid Robots, Daejeon, pp. 662-667, December 2008.

[35] R. Siegwart and Illah R. Nourbakhsh, Introduction on Autonomous Mobile Robots, MIT Press, 2004. [36] J.-W. Lee and J.-J. Lee, “Novel ant colony optimization algorithm with path crossover and heterogeneous ants for path planning,” IEEE Int. Conf. on Industrial Technology, Viña del Mar, pp. 559-564, March 2010. [click] [37] J.-W. Lee, J.-J. Kim, and J.-J. Lee, “Improved ant colony optimization algorithm by path crossover for optimal path planning,” IEEE Int. Symp. on Industrial Electronics, Seoul, pp. 1996-2000, July 2009. [click]

Joonwoo Lee received his B.S. degree in electronics and electrical engineering from Pusan National University, Busan, Korea, in 2007, and an M.S. degree in robotics from Korea Advanced Institute of Science and Technology, Daejeon, Korea, in 2009, where also received his Ph.D. degree in electrical engineering, in 2014. From 2014 to 2015, he worked as a postdoctoral researcher in the department of robotics and mechatronics, Advanced Manufacturing Systems Research Division, Korea Institute of Machinery and Materials (KIMM). He is currently working as an assistant professor in the department of electrical engineering, Kyungpook National University (KNU) since Sep. 2015. His research interests include swarm intelligence, swarm robotics, metaheuristics, intelligence control, and smart machine.