Transcript Path Planning of Robot in Three-dimensional Grid

Path Planning of Robot in Threedimensional Grid Environment
based on Genetic Algorithms
Hua Zhang, Manlu Liu, Ran Liu,
Tianlian Hu
Intelligent Control and Automation, 2008. WCICA 2008.
7th World Congress on
25-27 June 2008 Page(s):1010 - 1014
Presented by：曹憲中
Outline





INTRODUCTION
ENVIRONMENT MODEL
PATH PLANNING
EXPERIMENTAL ANALYSIS
CONCLUDING REMARKS
INTRODUCTION









Framework Space Approach
Topology
Grid method
Free-Space method
Neural Network
Artificial Potential Field
Fuzzy Theory
Genetic Algorithm
……
Outline





INTRODUCTION
ENVIRONMENT MODEL
PATH PLANNING
EXPERIMENTAL ANALYSIS
CONCLUDING REMARKS
ENVIRONMENT MODEL

Supposing that the robot can surpass
obstacle the height of which is H(h<H<2h), so
the robot can surpass first level obstacle or
climb up to first level obstacles and then
surpass second level obstacles ,and could
also move downwards in turn.
ENVIRONMENT MODEL

where point a and b are reachable in
2(1), 2(2) and 2(3), but 2(4) and 2(5) are
not.
ENVIRONMENT MODEL
Outline





INTRODUCTION
ENVIRONMENT MODEL
PATH PLANNING
EXPERIMENTAL ANALYSIS
CONCLUDING REMARKS
PATH PLANNING

A. Coding
0->10->20->30->40->50->60->61->62>63->64->65->66->67->68->79->89>99
(0,0) (0,1) (0,2) (0,3) (0,4) (0,5) (0,6)
(1,6) (2,6) (3,6) (4,6) (5,6) (6,6) (7,6)
(8,6) (9,7) (9,8) (9,9)
(0000, 0000) (0000, 0001) (0000,
0010) … (1001, 1001)
PATH PLANNING

before Population Initialization
1) Height trap
2) Connected domain
PATH PLANNING

before Population Initialization
3) Median Interpolation
If D=1, pk and pk+1 are continuous, otherwise noncontinuous.
PATH PLANNING

B. Population Initialization
{0,30,99} {0,12,20,32,55,87,92,99 } {0,44,68,99}.
Step1: Detecting points in the intermittent path;
there are four connectivity domains
which each point is in:
a. solid obstacles, U3;
b. first level obstacles, U1i;
c. second level obstacles, U2i;
d. free grids, U0.
PATH PLANNING

B. Population Initialization
Step2: Supposing there are two serial numbers, a and b.
If a∈U3, delete it directly;
If a∈U0, b∈U0 or a∈U1i, b∈U1j (i≠j) or a∈U0, b∈U1,
connects two points according to median
interpolation method in U0 and U1;
If a∈U1i, b∈U1i or a∈U2i, b∈U2i, connects two points
according to median interpolation method
in this
connected domain;
If a∈U2i, b∈U1j and U1j is adjacent with U2i
connects two points according to median
interpolation method in U1j and U2i;
PATH PLANNING

B. Population Initialization
Step2:
If a∈U0, b∈U2 or a∈U2i, b∈U2j (i≠j) or a∈U1i, b∈U2i
(U1i isn’t adjacent with U2j ), search c (c∈U1) that is
adjacent with U2 and is the
shortest distance to b.
The method is:
Where xb, xci, yb, yci is Cartesian coordinates of
b andci; Si is the distance between b andci; S
is the shortest distance.
Repeat Step2 until path is continuous.
PATH PLANNING
B. Population Initialization
Step3: Deleting operator When path is
continuous, redundant serial numbers that
are between two identical serial numbers
in an individual must be deleted, and one
of two identical serial numbers also is
deleted.

PATH PLANNING

C. Evaluation of Individual
Loss of time and energy isn’t considered, and
height of obstacle is excluded in the path
length. In the paper, evaluation function of
individual is
Where n is the sum of grid number of
individual and A is total straight distance
between adjacent serial number in the
individual; f and A are positive proportional.
PATH PLANNING

D. Genetic Manipulation



1) Choice: roulette method.
2) Cross-operation: coincidence inter-cross.
3) Mutation: Deleting it or replaced by a
stochastic serial number.
Outline





INTRODUCTION
ENVIRONMENT MODEL
PATH PLANNING
EXPERIMENTAL ANALYSIS
CONCLUDING REMARKS
EXPERIMENTAL ANALYSIS


algorithm is simulated in JCreater, and
the inserting and deleting operator are
designed by JAVA language.
one chromosome is {0, 13, 34, 76, 99}
in the initial population, and continuous
path is produced in Fig.4 after the
inserting and deleting operation.
EXPERIMENTAL ANALYSIS
EXPERIMENTAL ANALYSIS






Supposing population size is 30;
the length of chromosome is 100;
the probability of inter-cross is 0.3;
the probability of aberrance is 0.01;
the distance of adjacent grid is 10 in the
horizontal and vertical direction;
the distance of adjacent grid is 14 in the
diagonal direction.
EXPERIMENTAL ANALYSIS
The optimal path is shown in Fig.5 after 50 generations.
The value of fitness function is f=201.29.
EXPERIMENTAL ANALYSIS
The optimal path is shown in Fig.6 after 55 generations.
The value of fitness function is f=195.
Outline





INTRODUCTION
ENVIRONMENT MODEL
PATH PLANNING
EXPERIMENTAL ANALYSIS
CONCLUDING REMARKS
CONCLUDING REMARKS



This paper proposes a path planning
method in three-dimensional
environment.
Gird method is used to establish the
work environment of robot.
Combining with the actual situation,
improved GA is presented to optimize
path planning.
CONCLUDING REMARKS


The algorithm this paper adopts solves
the problem that the robot falling into
the height trap effectively.
Experiment results testify the
effectiveness and feasibility of the
algorithm in three-dimensional
environment.
Thank you for your attention.