August 18-21th, 2009
ICCAS-SICE 2009 Fukuoka, Japan

UnifiedUnified motion
motion planningplanning method
method using
usingrandom
random network
network andand gradientgradient method
methodforfor multifunctional
multifunctional underwater
underwater robots
robotsKoichiro Shiraishi and Hajime Kimura
Department of Maritime Engineering
Graduate School of Engineering
Kyushu University
Fukuoka, Japan

Outline
Outline ofof Presentation
Presentation
1. Introduction
Background and objectives

2. Formulation
Motion planning problems
for multifunctional underwater robots

3. Approach
Unified motion planning method
using random network and gradient method

4. Experiments
Reaching task and thrust force generation task

5. Conclusions
2

Outline
Outline ofof Presentation
Presentation
1. Introduction
Background and objectives

2. Formulation
Motion planning problems
for multifunctional underwater robots

3. Approach
Unified motion planning method
using random network and gradient method

4. Experiments
Reaching task and thrust force generation task

5. Conclusions
3

Introduction
Introduction
Development of robots
Multifunctional underwater robot equipped manipulators

Driving beetle robot

Octopus robot

Features of these robots
z Having the ability of swimming, walking and grasping objects
z Using the manipulator as an arm, an leg, a finger and a fin
Necessary for the robot to generatemotion planning according to the various tasks

4

Problem
Problem inin thethe motion
motion planningplanning
Conventional method

Necessary for the corresponding algorithms for individual tasks
The motion planning require a large amount of time
Swimming task

Motion planning algorithm for swimming task

Walking task

Motion planning algorithm for walking task

Grasping task

Motion planning algorithm for grasping task

Motion planning for each task is annoying
Objective

Development of a unified motion planning method
Swimming task
Walking task

To generate various motion planning
using a single algorithm

Grasping task

Unified motion planning method 5

Outline
Outline ofof Presentation
Presentation
1. Introduction
Background and objectives

2. Formulation
Motion planning problems
for multifunctional underwater robots

3. Approach
Unified motion planning method
using random network and gradient method

4. Experiments
Reaching task and thrust force generation task

5. Conclusions
6

Motionplanning
Problem
Motion PlanningPlanning
Problemplanning problem
problemTarget robot
Multifunctional underwater robot equipped the manipulator
Reaching Task

Thrust force generation task

Feature of Problems

Difference of cost functions according to target tasksz Reaching task : Minimization of an energy consumptionz Thrust force generation task : Maximization of an advancing distance7

Manipulator
Manipulator Coordinate
Coordinate SystemSystem
z The coordinates of the i th link’s tip :z Manipulator posture :z Motion planning :8FluidFluid Drag
Drag Force
Force
Morrison’s Equation

The fluid drag force acting on each linkIn our study, effects of vortices can be neglected.9

Reaching
Reaching Task
Task
Cost function
The energy consumption
caused by the fluid drag force

Optimization problem
Formulating as an optimization problem to minimize the total cost

The positive energy obtained from the current is not considered

Consider as shortest path problems
Obtaining a path that minimizes a sum of a cost function

10

ThrustThrust Force
Force Generation
Generation Task
Task
Modeling of the robot

Optimization problem
Formulating as an optimization problem to maximize the advanced distanceConsider as a infinite horizon problemObtaining a policy to maximize an average reward in an infinite horizon

11

Outline
Outline ofof Presentation
Presentation
1. Introduction
Background and objectives

2. Formulation
Motion planning problems
for multifunctional underwater robots

3. Approach
Unified motion planning method
using random network and gradient method

4. Experiments
Reaching task and thrust force generation task

5. Conclusions
12

Modeling
Modeling ofof thethe Motion
Motion Planning
Planning Problems
Problems
State transition network
Manipulator posture changes
are represented as the networkz Node : A manipulator posturez Arrow : A direction of the posture change
z: A cost (or reward)
State transition network

This problem is considered as a graph search problem
Assuming that Markov property is confirmed

This problem is also modeled as a Markov decision process

The optimal policy is obtained using Dynamic programming 13

Discretization
Discretization ofof State
State SpaceSpace
Conventional technique
The state space isdiscretized in a form of a lattice
Suffering from the “Curse of the dimensionality”

Lattice network

z The number of states increases in exponentiallyz The calculation using dynamic programming is intractable

Proposed technique
To avoid the curse of dimensionality,
the state space is discretized at random
Prevent the exponential increasein the number of states
Random networkz Adjusting the number of states is possiblez Well-balanced discretization of the state space is produced

Degradation of the solution caused by a sparse network14

Modification
Modification Method
MethodObjective

Modification of the obtained solution
with the sparse random network using a gradient method
The locations of the nodes in the solution are modified using
the gradient method to improve the quality of the solution
We can obtain good solutions in high dimensional problemsIllustration of the modification method① Initial solution② Modified solution using
the gradient method③ Improved solution

15Outline
Outline ofof thethe Unified
Unified Motion
Motion Planning
Planning Method
Method
1. Discretize the state space using the random network
2. Formulate the cost function according to the target task
3. Model the motion planning problem as the Markovdecision process
4. Obtain the optimal value function using Dynamicprogramming
5. Determine the optimum policy according to theoptimum value function
6. Modify the obtained solution using the gradient method

Obtaining the optimum motion planningaccording to the tasks using the single algorithm 16

Outline
Outline ofof Presentation
Presentation
1. Introduction
Background and objectives

2. Formulation
Motion planning problems
for multifunctional underwater robots

3. Approach
Unified motion planning method
using random network and gradient method

4. Experiments
Reaching task and thrust force generation task

5. Conclusions
17

Experiment
Experiment 1:
1: Reaching
Reaching Task
Task
Setting for Experiment 1
z A 4-DOF manipulator was used.
z Parameters of the manipulator were as follows.

z Parameters of the underwater environment were as follows.
z The direction of the uniform flow was the left .
Calculation Environment
CPU : Core2Duo E4500 2.2GHz
Memory : 2GB
OS : Windows XP
Program language： Java18

Experiment
Experiment 1:
1: Reaching
Reaching Task
Task
Discretization of state space
The number of nodes The number of links per a node
Lattice network

28,561(=134)

80

Random network

10,00040Motion planning sets
To enable comparison of the results,
three motion planning sets were used.
Minimization

NetworkPlanning 0

Sum of rotation angle―Planning 1

Energy consumption

Lattice network

Planning 2Energy consumption

Random network

Simulation was executed 10 times and the performance19
was evaluated from an average of the results

Results
Results ofof Planning
Planning 00 (Conventional(Conventional Method)Method)

The motion of Planning 0

The motion of Planning 0
applied the modification
20

Results
Results ofof Planning
Planning 00 (Conventional(Conventional Method)
Method)MethodzConventional method
Minimization the sum of
the rotation angle
Trajectory of Planning 0

Time series graph for the cost

Trajectory of Planning 0
applied the modification

21

Results
Results ofof Planning
Planning 11 (Energy,(Energy, Lattice)
Lattice)

The motion of Planning 1

The motion of Planning 1
applied the modification
22

Results
Results ofof Planning
Planning 11 (Energy,(Energy, Lattice)
Lattice)
Methodz Minimization:
The energy consumption
z Discretization:
The lattice network
Trajectory of Planning 1

Time series graph for the cost

Trajectory of Planning 1
applied the modification

23

Results
Results ofof Planning
Planning 22 (Energy,(Energy, Random)
Random)

The motion of Planning 2

The motion of Planning 2
applied the modification
24

Results
Results ofof Planning
Planning 22 (Energy,(Energy, Random)
Random)Methodz Minimization:
The energy consumption
z Discretization:
The random network
Trajectory of Planning 2

Time series graph for the cost

Trajectory of Planning 2
applied the modification

25

Results
Results ofof Experiment
Experiment 11
Results of calculation for the motion planning
Planning (Cost, Network)

Cost [N･m]Calculation time [s]Planning 0 (Angle, ― )1.906±0.0―

Planning 1 (Energy, Lattice)0.311±0.0744.6±0.0

Planning 2 (Energy, Random)

0.536±0.031

150.7±14.1

In Planning 0, the cost was recalculated using the obtained motion.

Results of calculation for the modification
Cost [N･m]Calculation time [s]Modified Planning 00.514±0.0

25.9±0.0

Modified Planning 1

0.291±0.0

1532.5±0.0

Modified Planning 2

0.338±0.018

274.2±76.4

We found the motion which have little consumed energy
when the manipulator moved against the uniform flow.

26

Experiment
Experiment 2:Thrust
2:Thrust Force
Force Generating
Generating Task
Task
Setting for Experiment 2
z A 3-DOF manipulator was used.
z Parameters of the manipulator were as follows.

zParameters of the robot were as follows.
The height and width of the body were 0.2 [m] and 0.3 [m],respectively.

z Parameters of the underwater environment was.

Calculation Environment
CPU : Core2Duo E4500 2.2GHz
Memory : 2GB
OS : Windows XP
Program language： Java

27

Experiment
Experiment 2:Generating
2:Generating Thrust
Thrust Force
Force Task
Task
Discretization of State SpaceThe number of nodes The number of links per a node
Lattice network

1,331(=113)

26

Random network

600

15

Motion planning sets
To enable comparison of the results,
two motion planning sets were used
Reward function

NetworkPlanning 3

Advanced distanceLattice network

Planning 4

Advanced distanceRandom network

Simulation was executed 10 times and the performancewas evaluated from an average of the results
28

Results
Results ofof Planning
Planning 33 (Distance,Lattice)(Distance,Lattice)
The motion of Planning 3

The motion of Planning 3 applied the modification

29

Results
Results ofof Planning
Planning 33 (Distance,Lattice)(Distance,Lattice)
Methodz Maximization:
The advanced distancez Discretization:
The lattice network
Trajectory of Planning 3

Time series graph for thex-coordinate values

Trajectory of Planning 3
applied the modification

30

Results
Results ofof Planning
Planning 44 (Distance,Lattice)(Distance,Lattice)
The motion of Planning 4

The motion of Planning 4 applied the modification

31

Results
Results ofof Planning
Planning 44 (Distance,Random)(Distance,Random)
Methodz Maximization:
The advanced distancez Discretization:
The random network
Trajectory of Planning 4

Time series graph for thex-coordinate values

Trajectory of Planning 4
applied the modification

32

Results
Results ofof Experiment
Experiment 22
Results of calculation for the motion planning
Name of Planning(Reward, Network)

Velocity [m / s]

Calculation time [s]Planning 3(Distance, Lattice)0.0465±0.0509.7±0.0

Planning 4(Distance, Random)

0.0417±0.0065

247.8±3.45

Results of calculation for the modification
Velocity [m / s]

Calculation time [s]Modified Planning 3

0.0724±0.0

5.74±0.0

Modified Planning 4

0.0571±0.0153

4.16±2.291

We obtained the repetitive motion like the flutter kick for swimming
33

Outline
Outline ofof Presentation
Presentation
1. Introduction
Background and objectives

2. Formulation
Motion planning problems
for multifunctional underwater robots

3. Approach
Unified motion planning method
using random network and gradient method

4. Experiments
Reaching task and thrust force generation task

5. Conclusions
34

Conclusions
Conclusionsz The unified motion planning method using Dynamicprogramming was proposed.
z The proposed method can generate motion planningfor very different tasks using the same algorithm.
zTo avoid the curse of dimensionality, we applied arandom network as a state transition network.
z We developed the modification method using thegradient method to improve the depleted solution.
zThe effectiveness of the proposed method wasverified through some numerical experiments.
Thank you very much for your attention 35!!