Robot Path Planning Based on A Hybrid Approach

Abstract

In this paper, an optimal method based on combination of improved genetic algorithm (IGA) and improved artificial potential field (IAPF) for path planning of mobile robot is proposed. This method consists of two steps. Firstly, free space model of mobile robot is established by using grid-based method and IGA is employed to find a global optimal collision-free path which is usually the shortest through known static environment. Secondly, according to the path obtained by IGA, IAPF is utilized to generate a real-time path to avoid dynamic obstacles. This ensures that robot can avoid obstacles as well as move along the optimal path. Simulation experiments are carried out to verify the superiority of the proposed algorithm.

1 Introduction

Recently, how to solve the robot path planning problem has aroused increasing interest of many researchers. Robot needs to automatically generate an optimal collision-free path which is from the start location to the goal location with respect to some given criteria. In this work, we focus the research on optimum path planning problem on real-time obstacle-avoidance and shortest distance criteria.

Various optimization methods have been proposed to solve this conundrum, which are classified as two major categories: traditional methods and intelligent methods. Notable conventional path planning methods include artificial potential field method [1] and visibility graph method [2]. Prominent intelligent path planning methods include particle swarm optimization [3], ant colony algorithm [4] and genetic algorithm [4,5,6,7,8,9]. Each method has its own merits and shortcomings. We can’t find a way to solve this problem completely. So, researchers have been continuously exploring to improve existing methods or combine different methods to learn the advantages of the those algorithms.

Recently, because of the strong power of algorithms (GA) to find global optimum for optimization problems, GA have been widely used as an alternative method to generate the optimal path. Hu and Yang. [10] proposed a knowledge-based GA. A parallel elite GA for global path planning is proposed in [11]. However, there are some problems associated with these methods. Firstly, the initial population is not chosen very well, which can make GA behave poorly. Secondly, there are not sufficient heuristic knowledge based genetic operators. Thirdly, GA has a poor real-time property to respond to emergency situations that may be encountered. In this paper, to circumvent these drawbacks of conventional GA, we present a hybrid method based on the combination of IGA and IAPF.

In this paper, a robot path planner based on IGA and IAPF is proposed, which can ensure that robot can find the optimal path and avoid obstacles in real time by taking the advantages of the hybrid algorithm.The remainder of this paper is organized as follows: In Sect. 2, an IGA is proposed to find a global optimal collision-free path. Section 3 elucidates the procedure of how to combine IGA and IAPF to get a real-time obstacle-avoidance path. Section 4 shows the results of some simulations to demonstrate the performance and merit of the proposed methods. The conclusions are given in Sect. 5.

2 Proposed Improved Genetic Algorithm

This section presents an effective IGA which can solve the global path planning problem.

2.1 Environment Modeling and Chromosome Encoding

In IGA, a grid-based representation is used for the work space of robot motion, as shown in Fig. 1. The shadow grids represent obstacle areas and the blank grids represent free areas. In order to treat the robot as a point, the girds’ boundaries equal to their real boundaries add to a safety distance that is defined with consideration of the size of the robot. Therefore, a path can be encoded as a sequence of coordinates which starts from the initial grid and ends at the goal grid with a series of intermediate grids. For example, if coordinates (1, 1) are the start coordinates and coordinates (20, 20) are the goal coordinates, then the feasible path shown in Fig. 1 can be encoded as a series of coordinates {(1, 1), (1, 14), (17, 14), (20, 20)}. The coordinates encoding (17, 14) represents the grid of 17th rows and 14th columns in grid map. The individual uses the real coordinates as genes, which can reduce calculation time because no time is costed for encoding and decoding of the genes in the population.

Fig. 1.

Grid-based environment with obstacles

2.2 Initialization of the Population and Cost Function

The initial population is generated using the approach proposed in [12]. This method uses the greedy algorithm based on heuristic Euclidean distance which can help build initial paths fast and feasibly. The convergent speed of GA can be speeded up by reasonable initialization.

In the case of robot path planning, the optimal path should be shortest and collision-free. To take into account these criteria, a cost function is used and this problem becomes a search for a path which has a lower cost. The cost function is defined as follows:

$$\begin{aligned} F_{cost} = \sum _{i=1}^N (d_i+\beta _iC) \end{aligned}$$

(1)

where N denotes the number of path segments in a individual, $d_i$ is the length of the $i_{th}$ path segment, C is a constant to penalize the infeasible solution, $\beta _i$ represents the feasibility of the segment, and if the $i_{th}$ path segment is feasible, $\beta _i$ equals to 0, else it equals to 1.

2.3 Genetic Operators

Crossover. We developed a new smart operator based on one-point random crossover, it randomly select a node denoted as X excluding the starting and ending points from Parent 1, and the distance between node X and the each node which is in Parent 2 excluding the start and goal is compared, the node Y in Parent 2 which has the minimum distance with node X is selected as the crossover point of Parent 2, then cross operation is performed between X and Y. Through this operation, we can try to ensure that the population after crossing is more reasonable.

Mutation. Mutation is a significant operator to avoid the phenomenon of premature because it can increase the diversity of the population. In mutation operator, randomly choose one node and replace it with a new node which is not the obstacle node and not in the original path.

Improvement. This operation is designed to improve the quality of a path. One node P is chosen randomly, perform a local search in the neighboring grids of P, for each node, the cost function is calculated and P is replaced by the best node which has a minimum cost.

Deletion. Deletion is applied to decrease the cost of a path. Randomly choose one node Z in the path and remove it, then connect its two adjacent nodes, if the cost of the new path is lower, delete the node Z.

These operators are very significant during evolution. They ensure that the algorithm runs quickly in a desired direction.

2.4 Outline of the Improved Genetic Algorithm

A flow chart of the proposed IGA is shown in Fig. 2. Initial population are generated randomly through the greedy method. Then perform the genetic operators on them until some stop criterion is satisfied. The termination conditions are that algorithm reach the maximum generation or the optimal solution remains unchanged for certain generations. To speed up the convergence rate of IGA, reproduction strategy with elite policy is performed, $20\%$ of the best individuals called elites are duplicated immediately to next generation. In order to increase the powerful ability to find global optimal solution, increasing the diversity of population by adding random initial population is very important. So in each generation, $20\%$ of new random initial individuals are put in the population pool.

Fig. 2.

Flow chart of proposed improved genetic algorithm

3 Collision Avoidance of Proposed Hybrid Algorithm

During the running of the robot, some unexpected dynamic obstacles may be encountered which may cause the planning path to become infeasible, so it is significant for robots to have the ability to avoid real-time obstacles. Because artificial potential field has elegant mathematical analysis and it is easy to calculate, this method is attractive in real-time obstacle avoidance. In this section, a new potential function is adopted and a hybrid algorithm is proposed.

3.1 Potential Function and Virtual Force

Attractive Potential Function and Virtual Force. In this paper, attractive potential function proposed in [1] is adopted, which is defined as a function of distance and velocity between the robot and the goal.

Repulsive Potential Function and Virtual Force. A new repulsive potential function is proposed to avoid moving obstacles. The new repulsive potential function is defined as follows:

$$\begin{aligned} U_{rep}(q,v)\,=\,{ \left\{ \begin{array}{lr} 0,\,\, \text{ if }\ (\rho _{obs}-R_{obs})>\rho _0\ \text{ or }\, v_{ro}\le 0 \\ \alpha _q(\frac{1}{\rho _{obs}-R_{obs}}-\frac{1}{\rho _0})(X-X_g)^2+\alpha _vv_{ro}, \,\, \text{ else } \\ \end{array} \right. } \end{aligned}$$

(2)

where $\rho _{obs}$ is the distance from robot to the center of obstacle, $R_{obs}$ is the radius of obstacle, $\rho _0$ is a constant which denotes the distance of influence that the obstacle has on the robot. $(X-X_g)^2$ represents the square of distance from robot to goal, by introducing this distance, the potential field can be guaranteed to be minimum at the target point, $\alpha _q$ and $\alpha _v$ are scale coefficients, $v_{ro}$ denotes the relative velocity in the direction from robot to obstacle between robot and obstacle.

By computing the negative gradient of the repulsive potential function with regard to position and velocity, the virtual repulsive force is obtained as follows:

(3)

The total virtual force obtained by adding the attractive force and repulsive force can guide the robot without collision.

3.2 Proposed Hybrid Algorithm

A flow chart of the proposed hybrid algorithm is shown in Fig. 3. First, IGA is performed to get a global optimum path such as {$P_0$, $P_1$,...,$\,P_i$,..., $P_n$} which is usually shortest, $P_0$ is the beginning and $P_n$ is the destination. Then follow this path for real-time obstacle avoidance by using IAPF. For example, $P_1$ is initially set as the local target point of IAPF, and robot moves toward the point $P_1$, if robot arrives $P_1$, then next point $P_2$ is set as the local target point, this operator is repeated until robot arrives the goal point.

Fig. 3.

Flow chart of proposed hybrid algorithm

4 Simulation Results

In this section, some simulation studies are presented to validate the superiority of the hybrid algorithm.

Fig. 4.

The global optimum path obtained by IGA

4.1 Simulation Experiments of Proposed IGA

A simulation is performed to compare IGA with the conventional genetic algorithm (CGA), the parameter setting for both GA is same as: population size is 50, probability for mutation is 0.1, and probability for rest genetic operators is 0.9. The number of max generations is 50. The choice of parameters is determined by performance and efficiency of the algorithm. The length of optimal path which is showd in Fig. 4 found by IGA is 27.4171, whereas the length of optimal path found by CGA is 34.3092, and sometimes CGA can not converge to feasible solution.

Fig. 5.

The path obtained by hybrid algorithm (Color figure online)

Fig. 6.

The trajectories of robot and obstacles (Color figure online)

4.2 Simulation Experiments of Proposed Hybrid Algorithm

A simulation is performed to verify that the robot can avoid real-time obstacle. The path obtained by hybrid algorithm is shown in Fig. 5. As shown in the left part of Fig. 5, the triangles denotes local target point obtained by IGA, the blue line segments represent global optimal path, and the red curve trajectory is the path obtained by hybrid algorithm when a dynamic obstacle is not encountered. The right part of Fig. 5 represents the real trajectory while a dynamic obstacle is encountered. A series of pink circles indicate the trajectory of the dynamic obstacle whose initial position is (8, 14) and direction of motion is downward. In Fig. 5, robot walks almost along the global optimal path and when a obstacle is encountered abruptly, robot can adjust its path to avoid obstacles in real time. As shown in Fig. 6, when robot moves into the vicinity of dynamic obstacle, robot turns in order to avoid obstacle.

5 Conclusions

In this paper, a hybrid algorithm based on the combination of IGA and IAPF is proposed. This method can make full use of known environmental information to find a global optimal path. It can also cope with the dynamic obstacles encountered suddenly in the process of robot motion. So this ensures that the robot can avoid obstacles in real time as well as move along the optimal path. The results of simulation experiments demonstrate the effectiveness of path planning based on the hybrid algorithm.