Transcript Research area Robot motion planning Multi Objective Enhanced

Multi-objective Motion Planning
Presented by
Khalafalla Elkhier
Supervised by
Dr. Yasser Fouad
• Research area
• Robot motion planning
• Multi Objective Enhanced
Genetic Algorithm by modified
the A* search algorithm.
• Other implementation for the
MGA with A*.
Research area
Problem:
Multi-objective Motion Planning can be
formalized as a Multi-objective
optimization problem ,involving more
than one objective function to be
optimized simultaneously
Solution:
A perfect multi-objective solution that
simultaneously optimizes each objective
function is almost impossible.
A reasonable solution to a multi-objective
problem is to investigate a set of solutions, each
of which satisfies the objectives at an acceptable
level without being dominated by any other
solution.
A solution is called non-dominated, or Pareto
optimal, if none of the objective functions can
be improved in value without degrading some of
the other objective values
Examples:
In network design we are concerned with its cost,
capacity, reliability; in investments we care about
return and risk; in radiation therapy we care about
the effects on the tumor on the one hand, and
healthy organs on the other.
Definition:
Zitzler and Thiele, 1999
Robot motion planning
Robotic motion planning is a promising study
issue in the field of robotics. most significant
research objectives can be categorized around
attaining
Safety
Accuracy
Path length
Efficiency
Future prediction
Smooth path
Run time
Stability
Control
Less computation cost
Current research can be generally divided in two
main methods: classical and heuristic.
The classic approaches suffer from high time
complication in high dimensions, and catching in
local minima.
Consequently, the application of the heuristic
approaches was extended due to their achievement
in addressing problems such as computational
complexity, exploration and local minima.
Classical
Heuristic.
Artificial potential field Genetic algorithms
(APF)
Roadmap
Particle swarm optimization
Cell decomposition
Simulated annealing
Mathematical
programming
Neural networks,
Ant colony optimization
Multi Objective Enhanced Genetic
Algorithm by modified the search
A* algorithm
First Paper :
Multi Objective Optimization of Trajectory
Planning of Non-holonomic Mobile Robot in
Dynamic Environment Using Enhanced GA by
Fuzzy Motion Control and A*
Objective:
Enhance the searching ability of robot movement
towards optimal solution state in static and
dynamic environments, by minimizing travelling
distance, travelling time, smoothness and security,
avoiding the static and dynamic obstacles in the
workspace.
Method:
A new hybrid approach based on Enhanced
Genetic Algorithm by modified the search A*
algorithm and fuzzy logic system
1. A global optimal path with avoiding obstacles
is generated initially.(Off-line)
2. Then, global optimal trajectory is fed to fuzzy
motion controller to be regenerated into time
based trajectory.(On-line)
Parameter specification:
The environment model :
A closed workspace (indoor area) without and
with different numbers of obstacles. This area is
described by a 2D static map (20 × 20); the
starting point is S=(1, 1), and the target point is
T=(19, 19) for a path. The positions of the
obstacles are randomly chosen.
Shortcut or decreased operator:
This operator will eliminate obstacles nodes from
map at the beginning of the algorithm.
Initial population:
classical method and modified A* is used for
generating a set of the sub optimal feasible paths in
simple map and complex map, respectively.
Then, the paths obtained are used for establishing the
initial population for the GA optimization.
The A* algorithm fitness function.
F(n) =( g(n)+ h(n)).
In the study the accumulated cost and heuristic
cost are the Euclidean distance between two
nodes.
The robot selection of the next node depends on
the minimum value of F(n) .
The modified A* method
F(n) =Rand*( g(n)+ h(n)).
in order to avoid the use of shortest path which it
could affect the path performance in terms of
multi objective (length, security and smoothness)
in initial stage.
Optimization by modified GA:
A chromosome represents the path and its length
varies depending on the case at hand.
Start position P(x0,y0) =(1, 1)
Via-points P(x1,y1) and P(xi+1,yi+1)
Target position P(xn,yn) =(19, 19)
All chromosomes will be evaluated by fitness
function a chromosome with the minimum fitness
has a considerably higher probability than the
others to select and reproduce by means of GA
operators in the next generation.
These steps are repeated until the maximum
number of iterations is reached
The total cost of fitness (or objective) function of
feasible path P with n points is obtained by a linear
combination of the weighted sum of multi objectives
F1(P) is the total length of path
F2(P) is the path smoothness
F3(P) is the path clearance or path security
F4(P) represents the total consumed time
ω‘s represent the weight of each objective. They
are tuned through simulation and try and errors,
with best found values
GA operators:
Selection:
Two parents randomly are selected based on their
fitness by using the Roulette wheel selection
method.
Crossover Operator:
Single point crossover is used.
This operation results feasible paths, because the
nodes before crossover point in the first parent and
the nodes after crossover point in the second parent
and in opposite, are valid nodes.
Mutation Operator:
The parental chromosome is chosen according to
selection method.
The parents start and target nodes are not mutated.
The mutation operation is done by selecting an
intermediate node in the parent according to
mutation probability. These nodes are chosen
randomly to replace the mutated node.
Enhanced Mutation :
It is served as a key role to diversity the solution
population, we proposed to enhance mutation
operator by adding traditional A* search method
to mutation. The enhanced mutation method is
used to avoid fall into a local minimum, improve
and decrease the distance of the partially path,
between two randomly points (i and j) included
in the main path
Deletion operator:
It proposed to eliminate the repeated genes
(redundant) from an individual (path). For specific
gene, the approach reversely check if this is equal
to others and this is done for each gene
Sort operation:
This operator sorts the chromosomes of population
according to their fitness at each generation. The
feasible chromosomes are organized in ascending
order according to their fitness, and secondly, if a
group of chromosomes has an equal fitness values,
they are again sorted, in ascending order.
Fuzzy Motion Planning
The proposed fuzzy controller contains an obstacle
avoidance strategy. It has two inputs.
The first input is the optimum velocity from the GA
and the second one is the obstacle when the robot
detects new moving obstacle in its path.
The output is the final velocity of the robot.
The fuzzy control might control the robot speed
based on detection of any dynamic object.
Not only the robot it can reduce the
speed in case the dynamic object gets more
close to robot, but also the control has ability to
increase the speed when the robot becomes safe
away from the dynamic obstacle.
fuzzy membership functions for input velocity
has 9 linguistic variables. (Z: Zero, VVL:
very very low, VL: very low, L: low, Medium, H:
High, VH: very high, VVH: very
very high, Maximum).
The second input has 5 linguistic variables (
No, Far, Medium, Close, Very Close). It should
be noted that the input 2 is normalized. For
the output 9 membership functions have been
used (Z: Zero, VVL: very very low, VL: very low,
L: low, Medium, H: High, VH: very high, VVH:
very very high, Maximum).
Other implementation for the MGA
with A*.
Second Paper:
Towards a Heterogeneous Navigation
Team of Aerial-Ground Robots Based on
Fuzzy Image Processing
Method:
The blimp robot will scan the environment to
detect the GR and the obstacles. The fuzzy edge
detection and the shape-color features technique
have been used to scan the environment and
detect the objects. These maps will send directly to
the ground station which has the proposed
approach using Enhanced Genetic Algorithm
modified by the search A* algorithm to find the
optimal trajectory and path for the GR.
Third Paper:
Integrated Motion Planning and control of multi
objectives Optimization and Multi Robots
Navigation
Objective:
The goal of this study is to drive multi mobile
robots from the start point to the target point
with the possible multi objective optimal path
with avoiding the collision risk among them and
the static obstacle in the environment
Method:
The proposed model includes two stages:
The first is motion planner, which used to generate
multi objective optimal path and trajectory for each
robot independently from the start to the goal
position using the MGA with A*.
The second one is motion controller, which used to
establish a movement strategy to let the robots drive
around with avoiding the collision with each other
using Sugeno fuzzy controller
Five objective functions are used to minimize
travelling length, time, smoothness, security and
trajectory and to reduce the energy consumption for
mobile robots by using Cubic Spline interpolation
curve fitting for optimal planned path.
References :
1\ A Review on Motion Planning and Obstacle
Avoidance Approaches in Dynamic Environments,
Adv Robot, Autumn 2015.
2\Classic and Heuristic Approaches in Robot
Motion Planning – A Chronological Review
3\Multi Objective Optimization of Trajectory
Planning of Non-holonomic Mobile Robot in
Dynamic Environment Using Enhanced GA by
Fuzzy Motion Control and A*
4\Towards a Heterogeneous Navigation Team of
Aerial-Ground Robots Based on Fuzzy Image
Processing
5\Integrated Motion Planning and control of multi
objectives Optimization and Multi Robots
Navigation
Thank You