GA-based Global Path Planning for Mobile

Robot Employing A* Algorithm

CenZeng,

Dalian University of Technology,Dalian, Liaoning,116024.China

Zengcen2009@yahoo.cn

Qiang Zhang, Xiaopeng Wei

Key Laboratory of Advanced Design and Intelligent Computing (Dalian University),Ministry of Education Dalian,

116622.China

zhangq@dlu.edu.cn

Abstract—Global path planning for mobile robot using

genetic algorithm and A* algorithm is investigated in this

paper. The proposed algorithm includes three steps: the

MAKLINK graph theory is adopted to establish the free

space model of mobile robots firstly, then Dijkstra

algorithm is utilized for finding a feasible collision-free path,

finally the global optimal path of mobile robots is obtained

based on the hybrid algorithm of A* algorithm and genetic

algorithm. Experimental results indicate that the proposed

algorithm has better performance than Dijkstra algorithm

in term of both solution quality and computational time,

and thus it is a viable approach to mobile robot global path

planning.

Index Terms—Dijkstra algorithm, Global path-planning,

Genetic Algorithm,A* Algorithm.

I.

INTRODUCTION

The global optimal path planning as the second factor

for mobile robots have been a hotspot research area for

many years, and several optimization methods such as

potential field method [1-3], visibility graph method [2] ,

grid method [3-5], modified simulated annealing

algorithm[9] and straight line path planning[10] have

been developed to solve this problem. For the grid

method, the main problem is how to determine the size of

grid, which has great influence on both the representation

precision for obstacles and the planned path. In recent

years, many intelligent algorithms were applied to the

path planning for mobile robots, such as fuzzy logic and

reinforcement learning [6], neural network [7], genetic

algorithm [8], and so on.

II.

G

ENETIC

A

LGORITHM

T

ECHNIQUE FOR GLOBAL

R

OBOT

P

ATH

-P

LANNING

The path-planning problem is usually defined as

follows[14]: “Given a robot and a description of an

environment, plan a path between two specific locations.

The path must be collision- free (feasible) and satisfy

certain optimization criteria.”The problem emerges after

all the viewpoints are generated for a given part: find the

minimum-time movement of the eye-in-hand robot to

visit all the viewpoints. It is a reasonable assumption that

the camera completely stops at each viewpoint and the

time to execute an inspection at all viewpoints is the same,

i.e., all equal to a constant time.

Mainly, two factors determine the traverse time: (i) the

trajectory, or time history of joint positions, velocities,

accelerations, and torques, between each pair of

viewpoints: (ii) the order to visit all the viewpoints,global

path planning. Obviously if the number of viewpoints is

big, the ordering of the viewpoints will be the dominant

factor; therefore,both of the factors would be considered

in this paper.

Figure 1.

Path-planning example for local obstacle avoidance,

applied on a subsection of the search space.

Global path planning requires the environment to be

completely known and the terrain should be static. In this

approach the algorithm generates a complete path from

the start point to the destination point before the robot

starts its motion. On the other hand, local path planning

means that path planning is done while the robot is

moving; in other words, the algorithm is capable of

producing a new path in response to environmental

changes. Assuming that there are no obstacles in the

navigation area, the shortest path between the start point

and the end point is a straight line. The robot will proceed

along this path until an obstacle is detected. At this point,

470

JOURNAL OF COMPUTERS, VOL. 7, NO. 2, FEBRUARY 2012

© 2012 ACADEMY PUBLISHER

doi:10.4304/jcp.7.2.470-474

our path-planning algorithm is utilized to find a feasible

path around the obstacle. After avoiding the obstacle, the

robot continues to navigate toward the endpoint along a

straight line. An example of local path planning is shown

in Figure 1.

Genetic algorithms [15,26-28] are a class of adaptive

methods that can be used to solve search and optimization

problems involving large search spaces. The search is

performed using the idea of simulated evolution (survival

of

the fittest). These algorithms maintain and manipulate

“

generations” of potential solutions or “populations”.

With each generation, the best solutions (as determined

by a problem specific fitness function) are genetically

manipulated to form the solution set for the following

generation. As in nature, solutions are combined (via

crossover) and/or undergo random mutation.

Robot path-planning is part of a larger class of

problems pertaining to scheduling and routing, and is

known to be NP-hard(NP-complete) [15]. Thus, a

heuristic optimization approach is recommended as

shown by Hwang [16]. One of these approaches is the use

of genetic algorithms. A genetic algorithm (GA) is an

evolutionary problem solving method, where the solution

to a problem evolves after a number of iterations. A

proposed solution with the GA method to the

path-planning problem is the best feasible path among the

pool of all possible solutions.

There have been several contemporary applications of

genetic algorithms to the robot navigation problem. One

approach is to combine fuzzy logic with genetic

algorithms[17,18,19]. In this approach, the genotype

structure represents fuzzy rules that guide the robot

navigation, so the genetic algorithm evolves the best set of

rules. While this approach can produce a feasible path

through an uncertain environment, the genotype structure

becomes very complex, as it needs to represent a variety

of fuzzy rules. A complex genotype structure can take a

long time to process in a genetic algorithm, which affects

the real-time performance of the robot during navigation.

Another approach is to use genotype structures that

represent local distance and direction, as opposed to

representing an entire path [20,21,22,23]. While these are

simple to process and allow for faster real-time

performance, the local viewpoint of these methods may

not allow the robot to reach its target. Some methods

have relatively simple genotype structures that can

represent feasible paths, but require complex decoders

and fitness functions [24, 14, 25].

Thus, our research has focused on improving the

genetic algorithm performance.

III.

S

PACE

M

ODEL OF

M

OBILE

R

OBOT

’

S

W

ORKING

E

NVIRMENT

A working environment of a mobile robot is illustrated

as shown in figure 1. Between the given starting point S

and goal point T, an area with 500?500 cm2 is enclosed,

robotic diameter is about 36cm,so the motion region

could be divided into 15 ? 15 regional grids . The free

space for the mobile robot in the environment with

obstacles consists of some polygonal areas. For each of

the six obstacles, the black polygon denotes its original

size, and the white margin denotes its expanded part. A

black part plus its white margin constitute a socalled

“grown obstacle”. In Figure 1, the symbols A1, A2, …

and A15 denote respectively the vertices of these grown

obstacles.The (x, y) coordinates of the starting point S

and the goal T are ( 1, 1 ) and ( 15, 15 ), respectively.

Figure 2.

Working environment and its reginal grids

Figure 3.

Network graph for free motion of mobile robot.

Assuming that the symbol l denoted the total number

of the free MAKLINK lines on a MAKLINK graph, these

middle points of these free MAKLINK lines were

denoted respectively by v1,v2, …, vl. If each pair of the

middle points on two adjacent free MAKLINK lines were

connected together, a network graph could be formed,

which gave the possible paths for the free motion of the

mobile robot. In Figure 2, the starting point S and the

JOURNAL OF COMPUTERS, VOL. 7, NO. 2, FEBRUARY 2012

471

© 2012 ACADEMY PUBLISHER

goal point T were also denoted by v0, and vl+1,

respectively. Figure 2 was an undirected graph, we used

G(V, E) to denote it, where V={v0, v1, v2, …,vl, vl+1}

was the set which consisted of S, T, and the middle points

of all the free MAKLINK lines and E was the set which

consisted of the lines connecting each pair of the middle

points on two adjacent free MAKLINK lines, the lines

connecting S (or T) and the middle points on the free

MAKLINK lines adjacent to S (or T). Using the

undirected graph G(V,E) as the free space model, the

global optimal path planning for the mobile robot could

be solved by finding the shortest path between the given

starting point S and goal point T on the graph G(V, E).

IV.

FINDING

FEASIBLE

PATH

USING

DIJKSTRA

ALGORITHM

In this section, to obtain a feasible path, we adopt

Dijkstraalgorithm [14] to find it between the given

starting point S and the goal T on the graph G(V, E) and

find out all the free MAKLINK lines at which the path

intersects at vi (i=1,2,…,l), then connect the obstacle

vertexes corresponding to those free MAKLINK lines,

and S and T to be a closed free-space. This way, we

obtained a sub-search-space where the global optimal

path inside.

Before using the Dijkstra algo rithm, it is necessary to

define the adjacency matrix with weights for the network

graph G(V, E), which is the basis for computing the

shortest path on G(V, E).Each element of the matrix

represents the length of the straight line between two

adjacent path nodes on G(V, E), where a path node means

the intersection of the moving path for the mobile robot

and a free MAKLINK line. And each element of the

adjacency matrix is defined as follows.

?

?

?

?

?

=

other

E

v

v

ifedge

v

v

length

j

i

adjlist

j

i

j

i

,

)

,

(

),

,

(

]

][

[

Figure 4.

Paths generated by Dijkstra algorithm.

Where adjlist[i][j] is the element corresponding to the

ith row and the jth column of the matrix; length (vi , v j)

is the length of the straight line b etween the points vi and

vj ; i and j=0, 1, 2,…,l, l+1.

For the example given in Figure 1, by using Dijkstra

algorithm,the path is obtained as:

S

>

v1

>

v2

>

v4

>

v5

>

v6

>

v7

>

T, and the path of the

moblie robot is shown in Figure 3. The path of the robot

is about 24 grids.

V.

GLOBAL

OPTIMAL

PATH

PLANNING

BASED

GA

ON

GA

AND

A*

ALGORITHM

1)

Genetic Algorithm

GA optimizers classified as global optimizers are

robust and stochastic search methods modeled on

principles and concepts of natural selection and evolution

[12]. A basic task of GA optimizer must be performed is

encoding the solution parameter as genes. The

convergence speed largely depends on the encoding

method. Binary encoding has some disadvantages when

optimized variable dimension is high. Encoding with real

numbers is proposed in this paper, which could improve

precision of the solution. The value of the genes is

denoted by some real number, the length of code depends

on the number of decision-making individuals. Before the

decision is made, the best individuals of current

generation are chosen to contrast against those of the

pre-generation, and the better are kept back for the next

comparison without any operation of GAs [13].

2)

A* algorithm

A* algorithms do the evaluation to each node, in order

to find a the most promising node. The evaluation

function f(n)=g(n)+ h(n) is introduced into the algorithm.

g (n) is the cost value of the shortest path from an initial

node to the current node, h(n) is a cost evaluation of the

optimal path from node n to the goal[11].

3)

Global Optimal Path Planning

The algorithm based on GA and A* algorithm is

described as follows:

Step1. Path Eoder Mode

Initialize starting point S:P0(x0,y0),x0=1, y0=1; and

initialize goal point T :Pn

(

xn,yn

)

, xn =15, yn =15.The

obstacles could be indicated as ORi(i=1, 2,…,q), so there

is a finite set ?

,

?=

{

OR1, OR2,…,ORq

}

The intermediate nodes need to meet 3 points as

follow:

i The nodes should be located outside the obstacle.

ii The nodes should be located in the planning space.

iii The paths should not intersect the obstacles.

So the initial population is the point to point paths.

Step 2.The Fitness Function

The Fitness Function is the important factor to

influence the astringency and stability of Genetic

algorithm.The nodes has met the 3 needs in the globle

path planning during the selection, the robotic length of

the path is still in the consideration when determining the

function

472

JOURNAL OF COMPUTERS, VOL. 7, NO. 2, FEBRUARY 2012

© 2012 ACADEMY PUBLISHER

The evaluation function f* is the core design in A*

algorithm,

)

(

*

)

(

)

(

*

i

h

i

g

i

f

+

=

g

(

i

) is the measurement of the actual cost from source

point to the goal,

h

*(

i

) is the evaluation of minimu m cost

from node P

i

to the goal.

When the valuation functions is the shortest path from

source to the goal, and the network could be viewed as a

planar network,

h

*(

i

) of A* algorithm would be Euclidean

distance from P

i

to the goal.

Based on A* algorithm, set the fitness fuction as

f

=A+B

?

=

=

n

i

i

g

i

h

A

1

));

(

/

)

(

*

(

?

)

))

(

(

......

)

)

(

1

(

(

1

2

2

1

?

?

=

=

+

+

=

n

i

n

i

k

ORq

k

OR

B

?

A is to make sure the path is shortest from source to the

goal,

]

300

,

100

[

?

?

, in this paper

200

=

?

,B is to

make sure the path is safe,

].

5

.

0

,

1

.

0

[

?

?

q

i

r

yi

yk

xi

xk

k

ORi

,...,

2

,

1

)},

)

(

)

((

,

0

min{

)

(

2

2

2

=

?

?

+

?

=

Step3. Genetic Operator

(1)Selection Operator

Force the individual reproduce to the next generation

on the direct proportion according to the fitness.

(2)

Crossover Operator

Use the single-point crossover.First, assume the

crossover probability

p

c

, match the individuals randomly

,

then generate a random number r(r

?

[0,1])for individual,

if

r

<

p

c

, crossover operate the random gene of individual.

(3)

Mutation Operator

Mutation is to add some random vibration in the genes

of the population,the mutation probability p

m

is around

0.001~0.100.

Figure 5.

Computer simulation

1)

Simulation Results

We carry out a computer simulation experiment for the

example illustrated in figure 1 using this paper method.

The simulation parameters are set as: M=30 (population

size), Pc=0.7(initial crossover probability), Pm=0.05

(initial mutation probability), The result of simulation

experiment is shown in Figure 4

.

In figure 4, the shadow part denotes the global optimal

path with the length of 20, which obtained by this paper

method.

T

ABLE

I.

C

OMPARISON OF THREE ALGORITHMS ON GLOBAL OPTIMAL PATH

PLANNING

Dijkstra

This

paper

LENGTH OF PATH

(

GRIDS

)

24

20

EXECUTION TIME

(

S

)

11.857

3.142

To proof the proposed method to be correct, the

comparison results with two methods (Dijkstra algorithm,

and this paper) on the global optimal path planning

problem as shown in figure 1 are given as seen Table 1.

In Table 1, Dijkstra algorithm expends 11.857 s to find

the global optimal one with the length of 24 grids; this

paper method expends 3.142 s to find the global optimal

path one with the length of 20 grids. From the above table,

we can see that, compared with the method in dijkstra

algorithm, the global optimal path obtained in this paper

is shorter and require less time.

VI.

CONCLUSION

In this paper, a method of global optimal path planning

for mobile robots based on GA and A* algorithm is

proposed to solve the problems existing in dijkstra

algorithm .The Dijkstra algorithm is used to find a

feasible path in the graph of mobile robot environment.

A* algorithm was used to overcome its disadvantage of

poor local optimizing. The simulation results show that

the proposed method is correct, its search speed is faster

than Dijkstra algorithm, and its search quality is better

than that of recently reported methods.

R

EFERENCES

[1]

Ge S S, Cui Y J. 2000. New potential functions for mobile

robot path planning. IEEE Transactions on Robotics and

Automation, 16, 5 (Oct. 2000), 615-620.

[2]

LI Lei, YE Tao, TAN Min. 2002. Present state and future

development of mobile robot technology research. Robot,

24,5 (Sept. 2002), 475-480.

[3]

WANG Xing-ce, ZHANG Ru-bo, GU Guo-chang.

2003.Potential grids based on path planning for robots.

Journal of Harbin Engineering University, 24, 2(Apr.

2003), 170-174.

[4]

Boschian V, Pruski A. 1993. Grid modeling of robot cells:

a memory-efficient approach [J]. Journal of Intelligent

and Robotic Systems, 8, 2(Oct. 1993), 201-223.

Algorithm

Performance

JOURNAL OF COMPUTERS, VOL. 7, NO. 2, FEBRUARY 2012

473

© 2012 ACADEMY PUBLISHER

[5]

ZHUANG Hui-zhong, DU Shu-xin, WU Tie-jun. 2004.

Research on path planning and related algorithms for

robots. Bulletin of Science and Technology, 20, 3(May

2004), 210-215.

[6]

Yung N H C. Cang Ye. 1999. An intelligent mobile

vehicle navigator based on fuzzy logic and reinforcement

learning. IEEE Transactions on Systems, Man, and

Cybernetics, Part B: Cybernetics, 29, 2(Apr. 1999),

314-321.

[7]

Lebedev D. 2001. Neural network model for robot path

planning in dynamically changing environment. Modeling

and Analysis of Information Systems, 18,1 (2001),12-18.

[8]

Liu Cai-hong, Hu Ji-quan, Qi Xiao-ning. 2003. Path

design of robot with continuous space based on hybrid

genetic algorithm. Journal of Wuhan University of

Technology (Transportation Science & Engineering), 27,

6 (Dec. 2003),819-821.

[9]

S. Kirkpatrick, C. D. Gelatt Jr., and M. P. Vecchi.

1983.Optimization by Simulated Annealing. Science, 220,

4598(May 1983), 671-680.

[10]

Romeijn H E. Smith R L. 1994. Simulated Annealing for

Constrained Global Optimization. Journal of Global

Optimization, 5, 2 (Sept. 1994), 101-124.

[11]

Zhao Ming-ru,Guo Jian,Sun Yuan.2009. Application of

A* Algorithm in Map Path-Searching. Journal of

Science&Technology Information. 31,6(Oct.2009),411-

413.

[12]

Yahya Rahmat-Samii, Eric Michielssen. 1999.

Electromagnetic Optimization by Genetic Algorithms.

John Wiley & Sons, Inc., New York, USA.

[13]

Ming Zhou, ShuDong Kong. 1999. Genetic

Algorithm:Theory and Applications. National defense

industry publishing company, Beijing

[14]

Sugihara, K. and Smith, J., 1997 . “Genetic Algorithms

for Adaptive Motion Planning of an autonomous Mobile

Robot”, Proceedings of the IEEE International

Symposium on Computational Intelligence in Robotics

and Automation, Monterey, CA, pp. 138-146

[15]

Obitko, M., “Genetic Algorithms”, Internet publication,

1998, http://cs.felk.cvut.cz/~xobitko /ga/main.html

[16]

Hwang, Y.K., Ahuja, N.,September 1992. “Gross Motion

Planning – A Survey”,ACM Computing Surveys, volume

24, issue 3, pp. 219-291.

[17]

Arsene, C.T.C. and Zalzala, A.M.S., 1999. “Control of

Autonomous Robots Using Fuzzy Logic Controllers

Tuned by Genetic Algorithms”, Proceedings of the 1999

Congress on Evolutionary Computation (CEC99), pp.

428-435.

[18]

Kubota, N., Morioka, T., Kojima, F. and Fukuda, T.,

1999. “Perception-Based Genetic Algorithm for a Mobile

Robot with Fuzzy Controllers”, Proceedings of the 1999

Congress on Evolutionary Computation (CEC99), pp.

397-404.

[19]

Pratihar, D.K., Deb, K. and Ghosh, A. 1999.

“Fuzzy-Genetic Algorithms and Mobile Robot Navigation

among Static Obstacles”, Proceedings of the 1999

Congress on Evolutionary Computation (CEC99), pp.

327-334.

[20]

Cazangi, R.R. and Figuieredo, M., 2002. “Simultaneous

Emergence of Conflicting Basic Behaviors and Their

Coordination in an Evolutionary Autonomous Navigation

System”, Proc. 2002 IEEE Conf. on Evol. Comp. (CEC

'02), IEEE.

[21]

Di Gesu, V., Lenzitti, B., Lo Bosco, G. and Tegolo, D.,

2000. “A Distributed Architecture for Autonomous

Navigation of Robots”, Proceedings Fifth IEEE

International Workshop on Computer Architectures for

Machine Perception, pp. 190 – 194.

[22]

Gallardo, D. and Colomina, O., “A Genetic Algorithm for

Robust Motion Planing”, Eleventh International

Conference on Industrial and Engineering Applications of

Artificial Intelligence and Expert Systems, Castellon,

Spain, June, pp. 115-121, 1998.

[23]

Vadakkepat, P. and Chen, T.K., “Evolutionary Artificial

Potential Fields and Their Application in Real Time

Robot Path Planning”,Proceeding of the 2000 Congress

on Evolutionary Computation, San Diego, CA, pp.

256-264, 2000.

[24]

Hocaoglu, C. and Sanderson, A.C., "Planning Multiple

Paths with Evolutionary Speciation", IEEE Trans.

Evolutionary Computation,vol. 5, no. 3, pp. 169-191, June

2001.

[25]

Xiao, J. and Zhang, L., “Adaptive Evolutionary

Planner/Navigator for Mobile Robots”, IEEE Transactions

on Evolutionary Computation, Vol. 1, No. 1, pp. 18-28,

April 1997.

[26]

Trivedi, N., Lai, W. and Zhang, Z., “Optimizing Windows

Layout by Applying a Genetic Algorithm”, Proceedings

of the 2001 Congress on Evolutionary Computation,

Seoul, Korea, pp. 431-435, 2001

[27]

Filho, J.L.R. and Treleaven, P.C., “Genetic Algorithm

Programming Environment”, IEEE Computer, pp. 28-43,

June 1994.

[28]

Srinivas, M. and Patnaik, L.M., “Genetic Algorithms: A

survey”,IEEE computer, pp. 17-26, June 1994.

CenZeng

,Liaoning Province, Dalian,

China. Birthdate: July, 1983. is mechanical

design Ph.D candidate at Dalian University

of Technology, China. Her research areas

include robotic path-planning, Genetic

Algorithm.

Email:

Zengcen2009@yahoo.cn

Qiang Zhang

is a professor at Dalian

University, Dalian, China. His research

interests are computer animation, intelligent

computing. Now he has served as editorial

boards of seven international journals and

has edited special issues in journals such as

Neurocomputing and International Journal

of Computer Applications in Technology.

Email:

zhangq@dlu.edu.cn

Xiaopeng Wei

is a professor at

Dalian University of Technology and

Dalian University, Dalian, China. His

research areas include computer animation,

intelligent CAD. So far, he has (co-)

authored about 160 papers published.

Email:

xpwei@dlu.edu.cn

474

JOURNAL OF COMPUTERS, VOL. 7, NO. 2, FEBRUARY 2012

© 2012 ACADEMY PUBLISHER