ICCAS2013 in Busan

Automatic Pipe Routing
To Avoid Air Pockets

Kyushu University Dep
Dep. of Marine Systems Engineering

Yuto Ando, Hajime Kimura

Outline Introduction
1. Approach
2. Air Pockets
3. Simulations
 Conclusion

ICCAS 2013 in Busan1

Motivations
Oil or Chemical Plants

Microchips
http://www.smtnet.com
http://www.radioirene.com/

http://thumbs.dreamstime.com/

Ship Building

Design of Pipelines
ICCAS 2013 in Busan

2

Motivations
Design of Pipe-Line in Ship Positions of equipment ( valves, etc. ) Piping routes
 Estimation of safety

NewApproach

Experience of Veterans A llott off time
titot design.
d i

Design Complete!

 Veterans are decreasing.

ICCAS 2013 in Busan3

Motivations
Design of Pipe-Line in Ship Positions of equipment ( valves, etc. ) Piping routes
 Estimation of safety

NewApproach

Experience of Veterans A llott off timeti
tot design.
d i

Design Complete!

 Veterans are decreasing.

ICCAS 2013 in Busan3

Motivations
Design of Pipe-Line in Ship Positions of equipment ( valves, etc. ) Piping routes
 Estimation of safety

New
Approach

Experience of Veterans A llott off time
titot design.
d i

Design Complete!

 Veterans are decreasing.

ICCAS 2013 in Busan3

Purpose Automatic Pipe-Line Design System
Automatic
DesignSystem

PID

Final Design

Equipment
Placing System
Equipment
LayoutPipe-Routes

Routing System

ICCAS 2013 in Busan

4

Purpose

Connector(Movable) Automatic Pipe-Line Design System

Pump(Immovable)
Valve
PID
(Movable)

Automatic
DesignSystemFinal Design

Equipment
Placing System
Equipment
LayoutPipe-Routes

Routing System

ICCAS 2013 in Busan

4

Outline Introduction
1. Approach
2. Air Pockets
3. Simulations
 Conclusion

ICCAS 2013 in Busan5

Approach of Routing System
Routing of pipelinesRoutingg in a network

ICCAS 2013 in Busan

6

Approach of Routing System

ICCAS 2013 in Busan

7

Approach of Routing System

Directed andW i ht d Graph
Weighted
Gh
ICCAS 2013 in Busan

7

Approach of Routing System

Dijkstra’s
jMethod

Directed andW i ht d Graph
Weighted
Gh
ICCAS 2013 in Busan

7

Approach of Routing System

The Optimizedp
Pipe RouteDijkstra’sjMethodDirected andW i ht d Graph
Weighted
Gh
ICCAS 2013 in Busan7

Pipe Pieces and Items
Pipe Pieces

StraightgElbow

Bendingg PartICCAS 2013 in Busan

8

Pipe Pieces and Items
Pipe Pieces

In the graph
Next node

Current
node

Edge

Weight of the Edge = (Manhattan distance + Costs of the Pipe Piece)x Diameter
ICCAS 2013 in Busan

9

Pipe Pieces and Items
Pipe Pieces

In the graph
Current
node

Next node

Weight of the Edge = (Manhattan distance + Costs of the Pipe Piece)x Diameter
ICCAS 2013 in Busan

9

Design Objectives
The shortest pathon theth network
tkObstacle
Pipe‐Rack Short Not winding

Aisle

 Avoid
A id aisles
i l Set on pipe racks

ICCAS 2013 in Busan 10

Design Objectives
The shortest pathon theth networktkObstacle
Pipe‐Rack Short Not windingAisle

 SetS t on pipei racksk
 Avoid aisles

Change the weight of edges
ICCAS 2013 in Busan 10

Design Objectives

Obstacle
Pipe‐RackAisle: Light weighted edge
( = Pipe-rackPik): Heavy weighted edge
( = AiAislel )ICCAS 2013 in Busan 10

Design Objectives

 Minimize the total length of piping routes
 Minimize the number of elbows and bending parts
 Avoid aisles as much as possible
 Pass through pipe-rack areas as much as possible

ICCAS 2013 in Busan 11

Design Objectives

 Minimize the total length of piping routes
 Minimize the number of elbows and bending parts
 Avoid aisles as much as possible
 Pass through pipe-rack areas as much as possible

ICCAS 2013 in Busan 11

Design Objectives

 Minimize the total length of piping routes
 Minimize the number of elbows and bending parts
 Avoid aisles as much as possible
 Pass through pipe-rack areas as much as possible

ICCAS 2013 in Busan 11

Design Objectives

 Minimize the total length of piping routes
 Minimize the number of elbows and bending parts
 Avoid aisles as much as possible
 Pass through pipe-racks areas as much as possible

ICCAS 2013 in Busan 11

Design Objectives

 Minimize the total length of piping routes
 Minimize the number of elbows and bending parts
 Avoid aisles as much as possible
 Pass through pipe-racks areas as much as possible= The shortest p
path in the weighted
ggraphg p
ICCAS 2013 in Busan 11Order of Routing
Order of routing in the system = From the largest to the smallest
GObstacle

G

Pipe BSG
Pipe CObstacle

SS

ICCAS 2013 in Busan 12Order of Routing
Order of routing in the system = From the largest to the smallest
GObstacle

G

Pipe BS

Pipe AG

Pipe C
ObstacleSS

ICCAS 2013 in Busan 12Order of Routing
Order of routing in the system = From the largest to the smallest
GObstacle

G

Pipe BS

Pipe AG

Pipe C
ObstacleSS

ICCAS 2013 in Busan 12Order of Routing
Order of routing in the system = From the largest to the smallest
GObstacle

GPipe BS

Pipe AG

Pipe C
ObstacleSS

ICCAS 2013 in Busan 12Order of Routing
 From the largest diameter to the smallest diameter Random choice from pipes with same diameters

Random choice

Random choice
ICCAS 2013 in Busan 13

Outline Introduction
1. Approach
2. Air Pockets
3. Simulations
 Conclusion

ICCAS 2013 in Busan 14

What’s “Pocket” ?
UU-shaped
shaped pipe piece in a vertical direction
 Liquid or gas settle at “Pocket”

Drain traps
Not preferred pipe piecezPump

Enginep
Drain Traps
ICCAS 2013 in Busan 15

What’s “Pocket” ?
UU-shaped
shaped pipe piece in a vertical direction
 Liquid or gas settle at “Pocket”

Drain traps
Undesirable pipe piecezPumpEnginep
Drain Traps
ICCAS 2013 in Busan 15

Algorithm to avoid “Pockets”

Loading of Start and Goal point

Method1 (Restriction Method)

Found!

Route without pockets

Not Found… : At least one pocket in the route
Found!

Method2 (Penalty Method)

Route avoiding pockets
as much as possible

Not Found…

No ppipep route
ICCAS 2013 in Busan 16

Algorithm to avoid “Pockets”

Loading of Start and Goal point

Method1 (Restriction Method)

Found!

Route without pockets

Not Found… : At least one pocket in the route
Found!

Method2 (Penalty Method)

Route avoiding pockets
as much as possible

Not Found…

No ppipep route
ICCAS 2013 in Busan 16

Method1: Restriction Method

Restriction Method- Delete candidates making U-turn- Reduce size of network

No pocket in the route

ICCAS 2013 in Busan 17

Method1: Restriction MethodzCandidates with the highest costs

ICCAS 2013 in Busan 18

Method1: Restriction MethodzCandidates with the highest costs

Route without “Pockets”

Remove from candidates
ICCAS 2013 in Busan 18

Simulation of Restriction Method

Solution by Old System(Without consideration of Pockets)

Solutionby Restriction Method

ICCAS 2013 in Busan 19

Simulation of Restriction Method
Other test case…
Complex route( Route with at least one Pocket))

No solution
by Restriction Method
Pocket is necessary

ICCAS 2013 in Busan 20

Algorithm to avoid “Pockets”

Loading of Start and Goal point

Method1 (Restriction Method)

Found!

Route without pockets

Not Found… : At least one pocket in the route
Found!

Method2 (Penalty Method)

Route avoiding pockets
as much as possible

Not Found…

No ppipep route
ICCAS 2013 in Busan 21

Method2 : Penalty Method
Penalty Method- Add penalties on edges connecting vertically.
- Search horizontal candidates as priority.
py
Route involves “Pockets”
Pockets as few as possiblepossible.

AddPenalty

ICCAS 2013 in Busan 22

Method2 : Penalty Methodz
Start

Goal

Red arrows : With penalties
Blue arrows : NormalCandidates with the highest costs

Avoid moving vertically as much as possible
Increase of search time
Route avoiding Pockets as much as possible
ICCAS 2013 in Busan 23

Method2 : Penalty Methodz
Start

Goal

Red arrows : With penalties
Blue arrows : Normal

Candidates with the highest costs

Avoid moving vertically as much as possible
Increase of search time
Route avoiding Pockets as much as possible
ICCAS 2013 in Busan 23

Method2 : Penalty Method
zStartGoal

Red arrows : With penalties
Blue arrows : Normal

Candidates with the highest costs

Avoid moving vertically as much as possible
Increase of search time
Route avoiding Pockets as much as possible
ICCAS 2013 in Busan 23

Simulation of Penalty Method

Solution by old System

Solution by Penalty Method
ICCAS 2013 in Busan 24

Outline Introduction
1. Approach
2. Air Pockets
3. Simulations
 Conclusion

ICCAS 2013 in Busan 25

Simulations
Purpose of simulations
Comparisons of old and new Systems, different mesh sizes,and orders of routing
Test model•

D i S
DesignSpace : 6 x 6 x 6 [[m]]•Pipes : 0.8[m] x 1, 0.6[m] x 2,0.4[m] x 4, 0.3[m] x 6•Order : From the largest pipe•

Cost of Elbow : 0.1•

Cost of Bending : 0.3•

Penalty of vertical edge : x2
ICCAS 2013 in Busan 26

Simulations
Purpose of simulations
Comparisons of old and new Systems, different mesh sizes,and orders of routing
Test model•

D i S
DesignSpace : 6 x 6 x 6 [[m]]•Pipes : φ 0.8[m] x 1, φ 0.6[m] x 2,φ 0.4[m] x 4, φ 0.3[m] x 6•Order : From the largest pipe•

Cost of Elbow : 0.1•

Cost of Bending : 0.3•

Penalty of vertical edge : x2
ICCAS 2013 in Busan 26

Simulation1 (Comparison of Old and New Systems)

Pocket90 minutes
Old SystemS t(Without consideration of Pockets)

70 minutes
New SNSystemt(With Method 1 and 2)

Succeeded to avoid making Pockets
ICCAS 2013 in Busan 27

Simulation2 ( Comparison of different orders )1 (φ 0.9m)
1 (φ 0.9m)

3 (φ 0.6m)

2 (φ 0.6m)

2 (φ 0.6m)
06 )

3 (φ 0.6m)

Order of routing: Strong influence to the final design.
ICCAS 2013 in Busan 28

Simulation3 (Comparison of mesh sizes)
Mesh: 0.25 [m]Time: 30 [minutes]

Mesh: 0.15 [m]Time: 70 [minutes]

Small Mesh Size

Large Mesh Size•

Accurate Routing•Rough Routing•

Long Search Time•

Short Search TimeMesh Size: Strong influence to the routes.
ICCAS 2013 in Busan 29

New Mesh Dividing Method

Regularg
meshes onlyy

ICCAS 2013 in Busan 30

New Mesh Dividing Method

Regularg
meshes onlyy: Regular Lines: Additional Lines Around obstacles, pipes, aisles
 In pipe-racks
Regular and additional meshes On start and goal points
ICCAS 2013 in Busan 30

New Mesh Dividing Method

Regulargand additional meshes

In short time

Regularg
meshes onlyyIn long time

Increase of items ( ex. Obstacles ) = Increase of additional meshes
ICCAS 2013 in Busan 31

New Mesh Dividing Method

Regular Mesh SystemAdditional Mesh System

Num. of Meshes in Regular Mesh << Num. of Meshes in Add. Mesh
Increase of search time!!
ICCAS 2013 in Busan 32

Outline Introduction
1. Approach
2. Air Pockets
3. Simulations
 Conclusion

ICCAS 2013 in Busan 33

Conclusion
New automatic pipe routing
g systemy Features
Minimize total length,
Minimize number of bending,
Pass through pipe-racks,
Avoid aisles,
Avoid making “Pockets”- Restriction Method ( Reduce the size of graph)- Penalty Method (Add penalty to the vertical edges)
ICCAS 2013 in Busan 34

ConclusionNew automatic pipe routing
g systemy Features
Minimize total length,
Minimize number of bending,
Pass through pipe-racks,
Avoid aisles,
Avoid making “Pockets”- Restriction Method ( Reduce the size of graph)- Penalty Method ( Add penalties to the vertical edges )ICCAS 2013 in Busan 35

Future Tasks

Order of Routing
Ship Hull Search Time More practical routes
 Equipmentq pPlacingg SystemyLarge Curved Pipe

This routing
g systemywill be opened for free at
http://sysplan.nams.kyushu‐u.ac.jp/gen/index.html

Thank you!
ICCAS 2013 in Busan 36