Sage Journals: Discover world-class research

Abstract

In complex environment with hybrid terrain, different regions may have different terrain. Path planning for robots in such environment is an open NP-complete problem, which lacks effective methods. The paper develops a novel global path planning method based on common sense and evolution knowledge by adopting dual evolution structure in culture algorithms. Common sense describes terrain information and feasibility of environment, which is used to evaluate and select the paths. Evolution knowledge describes the angle relationship between the path and the obstacles, or the common segments of paths, which is used to judge and repair infeasible individuals. Taken two types of environments with different obstacles and terrain as examples, simulation results indicate that the algorithm can effectively solve path planning problem in complex environment and decrease the computation complexity for judgment and repair of infeasible individuals. It also can improve the convergence speed and have better computation stability.

Keywords

path planning hybrid terrain common sense evolution knowledge genetic algorithm

1. Introduction

Global path planning for a mobile robotic is defined as finding a most reasonable collision-free route from a start location to a destination in the environment with obstacles. This route is generally optimal in some aspects, such as shortest distance or motion time. In most of researches on global path planning, only known or unknown obstacles are considered in the environment as the terrain is simple. However, different regions of the real environment usually have different terrain, such as sandlot, grassplot and so on. So how to find a reasonable path for a mobile robotic meeting the need of above criterions and escaping from obstacles in such complex environment with hybrid terrain is an open problem.

In global path planning, how to exactly describe environment is the base. Up to now, many effective ways have been used[1], such as mapping method, free-space method, generalized Vornooi, grid method, fuzzy logic[2] and so on. The former three modeling methods adopt mesh or map to describe environment. Though the optimal path obtained based on these environment is more precise, the computation complexity of the methods are in direct proportion to the number of obstacles, which limits their applications. Grid method is easier to be realized[3]. So it has been widely used. However, above environmental models do not take terrain into account. Aiming at the environment with rough terrain, Tarokh considers height and size of obstacles and adopts fuzzy logic to obtain fuzzy roughness of cells[2]. Fries studies traversability of some environment with diverse terrain by fuzzy representation[4]. Considering the important influence of terrain condition on path planning, this paper discusses modeling methods combing no-supervise learning with fuzzy logic aiming at certain environment with hybrid terrain and obstacles.

It is well known that path planning problem is NP-complete, and thus many heuristic approaches are used to solve the problem[2][5], such as evolutionary algorithm[6–7], genetic algorithm[8–9], particle swarm optimization[10], ant colony algorithm[11–12] and so on. Though each method has its own strength over others in certain aspects, their performances are limited because domain knowledge about the problems are not used enough. So Hu[13] adopts knowledge-based genetic algorithm to global path planning, which incorporating domain knowledge into its specialized operators. Here, domain knowledge only describes the information about obstacles. Implicit knowledge embodied in optimization process of path planning is not extracted and utilized enough. And complex terrain in the environment is not considered. Therefore the application of this method is limited.

It has been proved that implicit knowledge extracted from evolution process can be used to induce evolution operators so as to improve the performance of algorithms[13–14]. In order to obtain and use implicit knowledge rationally, culture algorithm is put forward by Reynolds[15]. The algorithm adopts dual evolution structure to simulate cultural evolution mechanism[16]. This provides a general framework for extraction and utilization of knowledge during the evolution process.

Based on above theories, a knowledge-based global path planning method for mobile robotics in rough environment with hybrid terrain is proposed in the paper. In the method, knowledge is classified into two kinds according to their characteristics, including common sense and evolution knowledge. Common sense integrates terrain and obstacles information so as to construct a novel environmental model. Evolution knowledge extracts the common segments among paths and the relationship between the paths and the obstacles, which are used to judge and repair the infeasible paths. The goal of the method is to decrease computation complexity and improve the convergence speed and the precision of the solutions by adopting various knowledge.

2. Description about Problem

Environment modeling is the basis of global path planning. In the paper, environment is described by grid. Assume that a robot is regard as a particle. That means its cubage is not considered. The robot moves in a limited planar space denoted by $Ω : {(x, y) | x \in [\underline{x}, \bar{x}], y \in [\underline{y}, \bar{y}]}$ . And it can move in any direction by step size St. According to the step size, the space is partitioned into uniform grids along X-axis and Y-axis. So in each axis, the number of grid is $N_{x} = (\bar{x} - \underline{x}) / S t or N_{y} = (\bar{y} - \underline{y}) / S t$ . Here, $\bar{x}$ , $\underline{x}$ are the lower and upper bound of space along X-axis. Each grid is labeled by an integer $g_{l}, l \in [0, N_{x} \times N_{y}]$ or the coordination of the grid's midpoint $(x_{g l}, y_{g l})$ .

x_{g_{l}} = ⌊ \frac{l}{N_{y}} ⌋ + \frac{1}{2} S t

(1)

y_{g l} = \frac{g_{l} - ⌊ l / N_{y} ⌋ N_{x}}{N_{x}} + \frac{1}{2} S t

(2)

In the environment, there are usually some obstacles distributed. They can be described by a convex polygon and the height of them is ignored. Suppose the obstacle set is B = {b^k, k = 1, 2, …| B|}. |B| denotes the number of obstacles.

In the paper, complex environment with hybrid terrain is considered. That means terrain in different regions may be diverse. Because the resistance to robots under diverse terrain are different, the friction coefficient is used to reflect diverse terrain, expressed by M = {m^l, l = 1, 2, …, |M|}. |M| denotes the kinds of terrain.

In above-mentioned environment, the goal of global path planning is to find an optimal or near-optimal path from starting location o_s to the destination o_e escaping from obstacles. Suppose $p^{i} = (o_{1}^{i}, \dots o_{j}^{i}, \dots, o_{| p^{i} |}^{i})$ is a path. $o_{j}^{i}, j = 1, 2, \dots, | p^{i} |$ denotes the location composing of a path. |pⁱ| is the number of the locations in i-th path. So the optimal path is shown as follows.

\begin{array}{l} p^{b e s t} = \underset{i}{arg min} D^{i} \\ s . t . p^{i} \cap b^{k} = ϕ \\ o_{1}^{i} = o_{s}, o_{| p^{i} |}^{i} = o_{e} \end{array}

(3)

where Dⁱ denotes a certain criterion used to evaluate a path.

It is obvious that global path planning is a kind of constrained optimization problem. A path is an individual composing of the population. Each individual is described by two forms. One is to express an individual by serial number of grids. That is, $o_{j}^{i} = g_{l}$ . This form saves the memory capability and can be used to express population and knowledge. The other form is to express an individual by the coordination of grids, shown as $o_{j}^{i} = (x_{g l}^{j}, y_{g l}^{j})$ . It is used for evolution operators and fitness evaluation.

At present, many researches have been done aiming at global path planning. However, there lacks the effective methods for path planning in complex environment with hybrid terrain. And implicit knowledge embodied in evolution process are not utilized enough. These make the computation complexity and performance of the method limited. So in the paper, various knowledge are analyzed and utilized. A novel global path planning method integrating common sense and evolution knowledge is proposed.

3. Modeling of hybrid terrain

Much research effort has been focused on modeling complex environment with hybrid terrain[17]. In the paper, fuzzy logic are adopted to extract terrain information.

Suppose a typical image of a natural terrain is taken into account. Its color and gray image are shown in Fig.1. In the environment, two kinds of terrain and three obstacles are contained. In order to realize path planning in above environment, Grander AS-RE mobile robot is used. It has a panorama vidicon which can obtain whole image about environment. In general, this kind of robot moves in planar space because it only can cross the obstacles which height is less than 3cm. Considering above character of the robot, the height of obstacles is not considered. That means as long as a region is covered by any obstacles, the path of robot must escape from it.

Fig. 1.

A typical image of a natural terrain

Based on above assumption, the image is divided into 500times500 grids according to step size of AS-RE mobile robot. Different terrain and obstacles has different gray level[2]. According to the valleys among gray level of above three terrain, they are partition along with its boundary, as shown in Fig.1(c). Obviously traversability of each terrain is related to two main attributes as follows:

The rigidity of terrain is more, robot is easy to move. Here, the rigidity is fuzzified using three fuzzy sets, HI(Hard), MD(Neutral), and LO(Soft).

Each terrain covers the larger area, the robot is easy to move. That means the curvature of terrain is less, it is easier to be crossed. Here, the curvature is fuzzified using three fuzzy sets, HI(Large), MD(medium), and LO(Small).

Assume that δ(g_l) is the rigidity of terrain in a grid. ζ(g_l) is the curvature of terrain in a grid. The traversability of each terrain in a grid is obtained from

If δ(g_l) is RigiditySet

then ζ(g_l) is CurvatureSet then M(g_l) is TraversabilitySet.

Here, RigiditySet and CurvatureSet denotes one of the fuzzy sets defined above. And TraversabilitySet is one of the fuzzy set expressing traversability. This fuzzy set is define as HI(high), MD(medium), and LO(low). Obviously, the traversability of each terrain in a grid is the friction coefficient mentioned in section.2.

4. Knowledge-based Global Path Planning Method in Complex Environment

In the method, various knowledge are extracted and utilized by adopting dual evolution structure of culture algorithms in order to improve the evolution performance and decrease computation complexity. The structure of the method is shown in Fig.2.

Fig. 2.

The structure of knowledge-based global path planning method

In population space, evolution operators, including selection, crossover and mutation, are implemented. The performance of each path is evaluated. And their feasibility is judged and repaired. In belief space, samples are selected from evaluated individuals in population space by sample-selection function. Evolution knowledge are extracted from samples by knowledge-extraction function and stored in the evolution-knowledge database. They influence the evolution process by evolution-inducing function. In common sense database, integrated information about environment are stored. They are used to evaluate the performance of the paths. It is obvious that the keys of the method are how to describe, extract and utilize knowledge and how to judge and repair the infeasible individuals.

4.1. Description And Utilization of Common Sense

In complex environment with hybrid terrain, because the location and shape of static obstacles as well as the covered region and characteristics of different terrain are known in advance, they are called common sense.

The shape of obstacles may be regular or irregular. According to the shape and location of obstacles, the grids in the environment are classified into two types: feasible and infeasible. Suppose F and IF are feasible and infeasible grid sets. The feasibility degree of a grid E(g_l) is defined by

{\begin{array}{l} E (g_{l}) = 1 & {g_{l} \in F | b^{k} \cap g_{l} = ϕ} \\ E (g_{l}) = 0 & {g_{l} \in I F | (x_{g_{l}}, y_{g_{l}}) \subset g_{l} = ϕ} \end{array}

(4)

That means the grid is infeasible if an obstacle covers it fully or covers its midpoint. If there are no obstacles lying in a grid, we call it a feasible grid.

Taken terrain information into account, each grid may have different friction coefficient, expressed by M(g_l) ∈ [0, 1]. So the integrated feasibility degree of a grid is

E^{'} (g_{l}) = E (g_{l}) \times M (g_{l})

(5)

Taken 2×2 environment as an example, according to the distribution of obstacles, the feasibility degree of grids are known as Fig.3.A. Suppose there are two kinds of terrain. According to section.3, their friction coefficients are 0.2 and 0.9 respectively. The distribution of each terrain is given in Fig.3.B. Based on formula(5), the integrated feasibility degree of current environment is shown in Fig.3.C. obviously both right grids are infeasible. Though left grids are feasible, their traversability is different.

Fig. 3.

The feasibility degree of grids

Common sense are used to constrain environment and evaluate the feasibility and traversability of the paths in order to select the more reasonable paths.

In complex environment, an optimal path is the most reasonable collision-free path. Here, weighted length is adopted as the criterion used to evaluate a path. Suppose $s_{j, j + 1}^{i}$ is the j-th segment of i-th path.

D^{i} = \sum_{j = 1}^{| p^{i} | - 1} D_{j}^{i}

(6)

where $D_{j}^{i}$ denotes weighted length of $s_{j, j + 1}^{i}$ . Because a segment may cross different terrain, a segment is divided into sub-segments, expressed by $l_{k, k + 1}^{i}$ . Each sub-segment must cover same terrain. Therefore, weighted length of the segment is to sum up the weighted length of each sub-segments.

D_{j}^{i} = \sum_{k = 1}^{2 | S_{j}^{i} | + 1} \bar{E} (l_{k, k + 1}^{i}) ‖ o_{k + 1}^{i} - o_{k}^{i} ‖ = \sum_{k = 1}^{2 | S_{j}^{i} | + 1} \bar{E} (l_{k, k + 1}^{i}) \sqrt{{(s_{g l}^{k + 1} - x_{g l}^{k})}^{2} + {(y_{g l}^{k + 1} - y_{g l}^{k})}^{2}}

(7)

where $\bar{E} (l_{k, k + 1}^{i}) = E (o_{k}^{i})$ is the feasibility degree of sub-segment $l_{k, k + 1}^{i} . | s_{j}^{i} |$ denotes the kinds of terrain covered segment $s_{j, j + 1}^{i}$ .

4.2. Extraction And Utilization of Evolution Knowledge

1. Judgment And Repair Operators Based on Evolution Knowledge

If any segment of a path between two adjacent locations crosses the infeasible grid or any obstacle, the path is infeasible.

Existing methods normally penalize infeasible individuals by lower their fitness, and then repair them by inserting a feasible location. However, because the inserted location is randomly selected, the repaired path may be still infeasible. So the path should be repaired again and again until the feasibility of the repaired path is satisfied. This will consume large computation time and lower the performance of the algorithms. As shown in Fig.4, the shadow region denotes an obstacle. The dashed line between two locations ( $o_{j}^{i}$ and $o_{j + 1}^{i}$ ) denotes the segment of i-th path. It is obvious that the segment $s_{j, j + 1}^{i}$ is infeasible. After a feasible location $r_{j, j + 1}^{i}$ is inserted, the repaired segment $s_{j, r}^{i}$ is still infeasible.

Fig. 4.

Traditional repair operator

Otherwise, judgment and repair in existing methods are two independent operators, which increases the computation complexity. In order to effectively integrate judgment and repair process, a novel judgment and repair strategy based on angle information is proposed.

Angle information describes the angle relationship between a path and the tangent line of an obstacle, as shown in Fig.5. The tangent lines derived from $o_{j}^{i}$ cross the obstacle b^k at the tangent points $c_{k, j}^{i}$ . The angles between the tangent line and the x-axis are called tangent angles θ_k,j.

ᶿ_{k, j}^{i} = arctan (\frac{y_{c_{k, j}^{i}} - y_{o_{j}^{i}}}{x_{c_{k, j}^{i}} - x_{o_{j}^{i}}})

(8)

Fig. 5.

Angle information

That is, tangent angle is the arc tangent of a tangent line. If there are two tangent lines derived from $o_{j}^{i}$ , the maximum and minimum tangent angles are expressed by $\bar{ᶿ_{k, j}^{i}}$ and $\underline{ᶿ_{k, j}^{i}}$ respectively.

Suppose $α_{j, j + 1}^{i}$ is the path angle formed by the segment $s_{j, j + 1}^{i}$ and the X-axis.

α_{j, j + 1}^{i} = arctan (\frac{y_{o_{j + 1}^{i}} - y_{o_{j}^{i}}}{x_{o_{j + 1}^{i}} - x_{o_{j}^{i}}})

(9)

According to the relationship between the path angle and the tangent angles, judgment rule based on above angle information is obtained.

{\begin{array}{l} p^{i} & c r o s s b^{k} & \underline{ᶿ_{k, j}^{i}} < α_{j, j + 1}^{i} < \bar{ᶿ_{k, j}^{i}} \\ p^{i} & \neg c r o s s b^{k} & e l s e \end{array}

(10)

It is obvious that as long as the path lies between two tangent lines, the path must cross obstacle. That is, this path is infeasible.

In order to choose a rational inserted location ensuring the feasibility of the repaired paths, a repair operator based on angle information is proposed. According to the judgment rules, as long as the path angle of the repaired segments satisfy the judgment condition of feasibility simultaneously, the repaired path must be feasible. For example, the infeasible segment $s_{j, j + 1}^{i}$ is divided into two repaired segments: $s_{j, r}^{i}$ and $s_{r, j + 1}^{i}$ after the inserted location $r_{j, j + 1}^{i}$ is inserted, as shown in Fig.6.

Fig. 6.

Repair operator

In order to ensure the feasibility of the repaired path, $r_{j, j + 1}^{i}$ and $s_{r, j + 1}^{i}$ shall out of the obstacle simultaneously. That is, not only the path angle $α_{j, r}^{i}$ of $s_{j, r}^{i}$ must satisfy the ‘cross’ condition with tangent angle of $o_{j}^{i}$ , but also the path angle $α_{r, j + 1}^{i}$ of $s_{r, j + 1}^{i}$ must satisfy the ‘cross’ condition with tangent angle of $o_{j + 1}^{i}$ . Therefore, if the inserted location lies in the region, which satisfied above ‘cross’ conditions simultaneously, all repaired segments must be feasible. This region is called feasible region, as the grey region shown in Fig.7.

\begin{array}{l} Ω_{F_{k}^{i}} \subseteq (Ω_{F_{k}^{i}}^{j} \cap Ω_{F_{k}^{i}}^{j + 1}) \\ Ω_{F_{k}^{i}}^{j} : {α_{j, r}^{i} | (α_{j, r}^{i} \geq ᶿ_{k, j}^{i}) \cup (α_{j, r}^{i} \leq \bar{ᶿ_{k, j}^{i}})} \\ Ω_{F_{k}^{i}}^{j + 1} : {α_{j + 1, r}^{i} | (α_{j + 1, r}^{i} \geq ᶿ_{k, j + 1}^{i}) \cup (α_{j + 1, r}^{i} \leq \bar{ᶿ_{k, j + 1}^{i}})} \end{array}

(11)

Fig. 7.

Feasible region

Because the inserted location chosen from feasible region can ensure the feasibility of two repaired segments of a path, there is no need to repair path once more. So this repair method can combine judgment with repair based on angle information. It has lower computation complexity and better performance than other methods.

2. Extraction And Utilization of Common Segments Based on Evolution Knowledge

In evolution process, the common segments contained in the paths with shorter length are called evolution knowledge. Suppose g_v and g_u are the start location and end location of the common segments. The common segment is expressed as follows.

K = {s_{v, u} | s_{v, u} = (g_{v}, g_{u})}

(12)

Common segments is obtained from sample database by statistical learning method. Suppose ρ_{s
_j,j+1} is the survival probability of a segment s_v,u .N_m denotes the size of sample database. Common segments is the segment with maximum survival probability.

s_{v, u} = \underset{j}{arg max} ρ_{s_{j, j + 1}}

(13)

ρ_{s_{j, j + 1}} = \frac{1}{N_{m}} \sum n_{s_{j, j + 1}}

(14)

\begin{array}{l} n_{s_{j, j + 1}} = {\begin{array}{l} 1 & s_{j, j + 1}^{i} = s_{j, j + 1}^{k} \\ 0 & s_{j, j + 1}^{i} \neq s_{j, j + 1}^{k} \end{array}, \\ w h e r e i \neq k, i, k \in [1, N_{m}] \end{array}

(15)

Samples are selected from population according to the individuals' fitness because individuals with higher fitness are likely to embody more effective information. Suppose N is the population size. β denotes the sample-selection proportion. Therefore, the number of samples selected in each iteration is βN.

Common segments are used to form sub-population. Suppose γ is the knowledge-inducing proportion. i is the knowledge-inducing interval. The detail knowledge-inducing process is shown as follows. Step1:

When current iteration equal to the integer multiples of knowledge-inducing interval, new individuals are formed based on common segments. That is,

p^{i^{'}} = (o_{s}, \dots, o_{v}, o_{u}, \dots, o_{e}), \exists t = λ τ, λ = 1, 2, \dots

(16)

Step2:

Infeasible or worse individuals are substituted by new individuals according to the knowledge-inducing proportion so as to implement local search near the common segments.

5. Simulation and analysis

In order to validate the rationality and feasibility of the path planning strategy proposed in the paper, two kinds of environments are used. One is a simple virtual environment with two types of obstacles, denoted by EnI. And it is partitioned into 80times80 grids, as shown in Fig.8. Obviously in this environment, two kinds of terrain are contained. In region I, the friction coefficient of terrain I is 0.2. In region II, the friction coefficient of terrain II is 1. The other is the natural complex environment as shown in Fig.1, denoted by EnII.

Fig. 8.

A simple virtual environment with two types of terrain

In evolution process, stochastic tournament selection combining with elite strategy is adopted. That is, two individuals are chosen from the population stochastically. And then the path with shorter length is selected as better individual from two individuals. Single-point crossover operator and mutation operator for real number[18]–[19] are used, shown as follows.

\begin{array}{l} {x^{'}}_{i, j} = x_{i, j} \pm 0.5 (x^{U} - x^{L}) \sum_{m = 0}^{q - 1} \frac{a (m)}{2}, \\ {y^{'}}_{i, j} = y_{i, j} \pm 0.5 (y^{U} - y^{L}) \sum_{m = 0}^{q - 1} \frac{a (m)}{2} \\ w h e r e a (m) = {\begin{array}{l} 1 & 0 < r a < \frac{1}{m} \\ 0 & \frac{1}{m} < r a < 1 \end{array} \end{array}

(17)

ra ∈[0, 1] is a random number. m normally equals to 20. Main parameters used in the method are listed in Table.1. In order to analyze the performance of the method, three indices are adopted. Assume that M1 is the average convergence iteration during twenty run times. M2 is the average iteration as the optimal solutions appeared firstly during twenty run times. M3 expresses average length of the optimal paths during twenty run times.

Table 1.

Main parameters used in the strategy

Probability of crossover	N	St	β	Run times	Sample-population size	Probability of mutation	N _x	N _y	o _s	o _e	Termination iteration
0.6	20	1	0.4	20	20	0.03	20	20	(1,1)	(20,20)	150

5.1. Performance Analysis About Proposed Path Planning Method

Evolution knowledge obtain implicit information embodied in evolution process from updated sample database. Parameters involved in this process shall influence the performance of the proposed method.

1. Comparison of The Performance with Different Sample-selection Proportion

Sample-selection proportion has a direct impact on the update speed of samples. Adopted parameters in Tab.1, the performances of the method under two types of environments are compared in Tab.2.

Table 2.
Comparison of performance with different Sample-selection proportion

Env EnI with regular obstacles EnI with irregular obstacles EnII

β M1 M2 M3 M1 M2 M3 M1 M2 M3

0.2 15.55 7.55 185.0212 15.55 7.55 184.6008 12.75 10 168.88

0.3 14.8 6.85 184.9991 14.8 6.85 184.5953 12.7 9.95 168.38

0.4 14.3 5.65 184.8362 14.3 5.65 184.5396 14.65 12 168.37

0.5 13.65 5.3 184.7644 13.65 5.3 184.4664 11.8 8.6 168.48

Env	EnI with regular obstacles	EnI with irregular obstacles	EnII
0.2	15.55	7.55	185.0212	15.55	7.55	184.6008	12.75	10	168.88
0.3	14.8	6.85	184.9991	14.8	6.85	184.5953	12.7	9.95	168.38
0.4	14.3	5.65	184.8362	14.3	5.65	184.5396	14.65	12	168.37
0.5	13.65	5.3	184.7644	13.65	5.3	184.4664	11.8	8.6	168.48

The average fitness of population and the optimal solution with different sample-selection proportion in one run are plotted in Fig.9, Fig.10 and Fig.11.

Fig. 9.

Environment I with regular obstacles

Fig. 10.

Environment I with irregular obstacles

Fig. 11.

Environment II

It is obvious that no matter what sample-selection proportion is, the shortest collision-free path is obtained by the proposed method. And along with the increasing of the sample-selection proportion, the convergence speed is faster and the length of the optimal path is shorter. The reason for above phenomena is that if less sample-selection proportion is used, the sample database is updated slowly. Evolution knowledge are mainly depended on the former samples, which is easy to induce the evolution process into local convergence. However, larger sample-selection proportion can speed up the update of evolution knowledge, but the computation time increases at the same time. So β=0.5 in the paper.

2. Comparison of The Performance with Different Knowledge-inducing Interval

The influence of evolution knowledge on population with different knowledge-inducing interval is different. Adopted parameters in Tab.1, the performances of the method under two environments are compared in Tab.3.

Table 3.
Comparison of performance with different knowledge-inducing interval

Env EnI with regular obstacles EnI with irregular obstacles EnII

i M1 M2 M3 M1 M2 M3 M1 M2 M3

2 10.6 4.05 184.77 11.15 4.75 184.7837 12.5 5.8 168.40

3 12.3 5.5 184.83 11.6 4.95 184.7983 14.8 6.9 168.56

4 13.9 6.7 184.85 14.5 7.5 184.8242 14.45 6.5 168.96

Env	EnI with regular obstacles	EnI with irregular obstacles	EnII
2	10.6	4.05	184.77	11.15	4.75	184.7837	12.5	5.8	168.40
3	12.3	5.5	184.83	11.6	4.95	184.7983	14.8	6.9	168.56
4	13.9	6.7	184.85	14.5	7.5	184.8242	14.45	6.5	168.96

The average fitness of population and the optimal solution with different knowledge-inducing interval in one run are plotted in Fig.12, Fig.13 and Fig.14.

Fig. 12.

Environment I with regular obstacles

Fig. 13.

Environment I with irregular obstacles

Fig. 14.

Environment II

It is obvious that larger knowledge-inducing interval makes the convergence speed slower and the length of optimal path longer. Along with the increasing of the knowledge-inducing interval, population induced by knowledge is less. That means evolution knowledge can not lead population to do local search in time, which results in the slower convergence speed. So knowledge-inducing interval is equal to 2.

3. Comparison of The Performance with Different Knowledge-inducing Proportion

Different number of individuals are induced by evolution knowledge under different knowledge-inducing proportion. Adopted parameters in Tab.1, the performances of the method under two environments are compared in Tab.4.

Table 4.
Comparison of performance with different knowledge-inducing proportion

Env EnI with regular obstacles EnI with irregular obstacles EnII

γ M1 M2 M3 M1 M2 M3 M1 M2 M3

0.1 16.7 9.4 184.7641 13.25 6.8 184.2155 13.7 7.8 168.45

0.4 11.25 6.5 184.1139 11 5.65 183.7893 11.1 5.6 168.01

0.7 74.1 47.3 184.2771 52.2 31.8 184.1485 40.1 15.9 168.39

Env	EnI with regular obstacles	EnI with irregular obstacles	EnII
0.1	16.7	9.4	184.7641	13.25	6.8	184.2155	13.7	7.8	168.45
0.4	11.25	6.5	184.1139	11	5.65	183.7893	11.1	5.6	168.01
0.7	74.1	47.3	184.2771	52.2	31.8	184.1485	40.1	15.9	168.39

The average fitness of population and the optimal solution with different knowledge-inducing proportion in one run are plotted in Fig.15, Fig.16 and Fig.17.

Fig. 15.

Environment I with regular obstacles

Fig. 16.

Environment I with irregular obstacles

Fig. 17.

Environment II

If knowledge-inducing proportion is too lager or too small, the performance of the algorithm and the length of optimal path become worse. By analyzing the results, we know that individuals influenced by evolution knowledge realize the exploitation of the search space. Larger knowledge-inducing proportion will enhance the local search of population, which is easy to make evolution process falling into local convergence. Otherwise, if knowledge-inducing proportion is too small, knowledge can not induce evolution process effectively. It will slow the convergence speed. In order to consider the exploitation and the exploration ability simultaneously, γ = 0.4 in the paper.

5.2. Comparison of The Performance Between Different Methods

In order to validate the rationality and validity of the method proposed in the paper, it is compared with traditional genetic algorithm[5]. Adopted parameters in Tab.1, the performances of the method under two environments are compared in Tab.5. Here, M4 expresses variance of the optimal solutions during twenty run times.

Table 5.
Comparison of performance between different methods

Env method M1 M2 M3 M4

EnI with regular GA 16.1 8.55 185.9071 1.4127

obstacles KBPP 11.65 4.85 185.5664 0.5859

EnI with irregular GA 15.4 10.2 184.6769 0.2478

obstacles KBPP 12.3 6.95 184.4499 0.2463

EnII GA 13.4 12 169.53 0.1455

KBPP 11.4 5 168.39 0.0016

Env	method	M1	M2	M3	M4
EnI with regular	GA	16.1	8.55	185.9071	1.4127
obstacles	KBPP	11.65	4.85	185.5664	0.5859
EnI with irregular	GA	15.4	10.2	184.6769	0.2478
obstacles	KBPP	12.3	6.95	184.4499	0.2463
EnII	GA	13.4	12	169.53	0.1455
KBPP	11.4	5	168.39	0.0016

The average fitness of population and the optimal solution with different method in one run are plotted in Fig.18 and Fig.19.

Fig. 18.

Average fitness

Fig. 19.

Optimal feasible path

It is obvious that the convergence speed and the precision of the solution by the proposed method are better. That is, the length of the optimal path is shorter. And the variance of the optimal solutions are less. This means the proposed method has the better stability.

5.3. Influence of Common Sense on Path Planning

Common sense is used to evaluate the length of a path. If terrain is considered, a path is evaluated by formula(7). Otherwise, the length of a path is computed by formula (18) as terrain is not taken into account.

D^{i} = \sum_{j = 1}^{| p^{i} | - 1} ‖ o_{j + 1}^{i} - o_{j}^{i} ‖ = \sum_{j = 1}^{| p^{i} | - 1} \sqrt{{(x_{g l}^{j + 1} - x_{g l}^{j})}^{2} + {(y_{g l}^{j + 1} - y_{g l}^{j})}^{2}}

(18)

In order to understand the role of common sense, the optimal paths obtained based on different evaluation functions are compared aiming at the environment I shown in Fig.20. Here, the solid line and dashed line expresse the optimal path considering terrain or not.

Fig. 20.

Optimal feasible path

Comparison of the length of two optimal paths, it is obvious that the optimal path considering terrain is more reasonable. That is, robots always attempt to move along the region with least friction coefficient. This indicates common sense play a reasonable guidance role in path planning.

In a word, global path planning in complex environment is effectively solved by utilizing common sense and evolution knowledge to induce the evolution process. This knowledge-based path planning method can improve the convergence speed and the stability of the solutions.

6. Conclusions

Aiming at global path planning in complex environment with different terrain and obstacles, a novel knowledge-inducing path planning method is proposed. The algorithm adopts dual evolution structure in culture algorithms to integrate common sense and evolution knowledge. Common sense describes the distribution of terrain and obstacles in complex environment, and thus it reflects feasibility and traversability of environment. This kind of knowledge is used to evaluate the length of the paths so as to guide selection of the paths. Evolution knowledge describes the angle relationship between the path and the obstacles, or the common segments of paths.

It is used to judge and repair infeasible path. Taken three kinds of environments with different terrain and obstacles as examples, simulation results indicate that the algorithm proposed in the paper can effectively solve path planning problem in complex environment. And the computation complexity for judgments and repair of infeasible path is lower than existing path planning method adopting evolutionary algorithms. The algorithm also can improve the convergence speed. Computation stability of solutions are better.

Path planning method for mobile robots in the uncertain environment with dynamic or unknown obstacles is the next problem to be solved in future.

Footnotes

7.

This work was supported by National Natural Science Foundation of China (Grant No. 60805025) and the 863 Project of China (Grant No.2007AA12Z162).

References

Alexopoulos

Griffin

P M

, “Path planning for a mobile robot,” IEEE Transactions on Systems, Man and Cybernetics, vol.22, pp. 318–3221, 1992.

Tarokh

, “Hybrid intelligent path planning for articulated rovers in rough terrain,” Journal of Fuzzy sets and Systems, pp. 1–11, 2008.

Haitao

Guo

Qingbao

Zhu

Shoujiang

, “Rapid-Exploring Random Tree Algorithm for Path Planning of Robot Based on Grid Method,” Jounral of Nanjing Normal University, vol.7, pp. 58–61, 2007.

Fries

Terrence P.

. “Autonomous Robot Motion Planning in Diverse Terrain Using Soft Computing”. IEEE Mountain Workshop on Adaptive and Learning Systems. pp.177–182, 2006.

Hani Hagras a, Tarek Sobh, “Intelligent learning and control of autonomous robotic agents operating in unstructured environments,” Information Sciences., vol.145, pp.1–12, 2002.

Daokui

Zhenjun

Dianguo

, “Study on Path Planning Method of Mobile Robot,” Robotics, vol.30, pp. 97–102, 2008.

Hocaoglu

Sanderson

A.C.

, “Planning multiple paths with evolutionary speciation”, IEEE Trans. Evolutionary Comput. vol.52, pp.161–191, 2001.

Qing

Zhang

Wei

Yin

Yixin

, “An improved genetic algorithm of optimum path planning for mobile robots,” in Proc. of the Sixth International Conference on Intelligent Systems Design and Applications. 2006, pp. 637–642

Yang

, “Genetic algorithm based path planning for a mobile robot,” in Proc. of IEEE International conference on Robotics and Automation, 2003, pp. 1221–1226

10.

Lei

Kaiyou

Qiu

Yuhui

, “A novel path planning for mobile robots using modified particle swarm optimizer,” in 1st International Symposium on Systems and Control in Aerospace and Astronautics, 2006, pp. 981–984

11.

Tan

Guan-Zheng

Huan

Sloman

Aaron

, “Ant colony system algorithm for real-time globally optimal path planning of mobile robots,” Acta Automatica Sinica, vol.33, pp. 279–285, 2007.

12.

Tewolde

Girma S.

Sheng

Weihua

, “Robot path integration in manufacturing processes: Genetic algorithm versus ant colony optimization,” IEEE Transactions on Systems, Man, and Cybernetics, vol.38, pp. 278–287, 2008.

13.

Yan-rong

Yang

Simon X.

, “A knowledge based genetic algorithm for path planning of a mobile robot,” in Proc. of the 2004 IEEE international Conference on Robotics & Automation, 2004, pp.4350–4355.

14.

Yi-nan

Guo

Dun-wei

Gong

, “Extraction and utilization about knowledge in hierarchical interactive genetic algorithms,” Control and Decision, vol. 22, pp.1329–1335, 2007.

15.

Reynolds

Robert G.

. “A Self-adaptive Approach to Representation Shifts in Cultural Algorithms.” Proceedings of IEEE International Conference on Evolutionary Computation, pp.94–99, 1996.

16.

Peng

Bin

, “Knowledge and population swarms in cultural algorithms for dynamic environments,” Ph.D. dissertation. Detroit: Wayne State University, 2005.

17.

Karlsen

Robert E.

, “Terrain Understanding for Robot Navigation,” Proceedings of the 2007 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 895–900, 2007.

18.

Lin

Wang

, Intelligent optimization algorithms with applications. Beijing: Tsinghua University. 2005.

19.

Wang

Zhang

Zheng

DZ.

An effective hybrid genetic algorithm for flow shop scheduling with limited buffers. Computers & Operations Research, 2006, 33(10): 2960–2971

Knowledge-inducing Global Path Planning for Robots in Environment with Hybrid Terrain

Abstract

Keywords

1. Introduction

2. Description about Problem

1. Judgment And Repair Operators Based on Evolution Knowledge

1. Comparison of The Performance with Different Sample-selection Proportion

Footnotes

7.

References