Automatic Designfor Pipe Arrangement
Considering Valve Operationality
Hajime Kimura
Satoshi Ikehira(Kyushu University, Japan）(Kyushu University, Japan)
Shipbuilding ICCAS 2009

Overview
1. Motivation and Purpose
2. Evaluation Algorithm for Pipe Operationality
Accessibility
Possibility of Valve Handling

3. Multi-Objective Optimization Algorithm
Coding for Genetic Algorithm (Only Valves)
Multi-Objective Genetic Algorithm: NSGA-Ⅱ
Routing Pipes and Making Branches

4. Experiments

5. Conclusion and Future Works

Pump

A Ballast Pump RoomValveA handle forvalve operation
It is operatedusing a rod fromupper pathway

From upper pathwayUpper Pathway

PumpLadderMotivation
3D-CAD contributes
PipeArrangement

designing efficiency

But…

Needs sophisticated skills
Automatic designＷｈｙ？

[Reason 1] Obscurity of the design evaluation
Not only to arrange shortest pipes between equipments!
ex.) Easy to operate valves, easy for maintenance, etc.
Answer → 1) Define numerical evaluation for all items
2) Formulate as a multi-objective optimization[Reason 2] A Problem in designing algorithms
It is no use that the algorithm gives only one solution!
GeneticAnswer → Show plural solutions
algorithm
Designer selects one of them as he needs.

Motivation
3D-CAD contributes
PipeArrangement

designing efficiency

But…

Needs sophisticated skills
Automatic designＷｈｙ？

[Reason 1] Obscurity of the design Criteria
Not only to arrange shortest pipes between equipments!
ex.) Easy to operate valves, easy for maintenance, etc.
Answer1) Define numerical evaluation for all items
2) Formulate as a multi-objective optimization[Reason 2] A Problem in designing algorithms
It is no use that the algorithm gives only one solution!
GeneticAnswer → Show plural solutions
algorithm
Designer selects one of them as he needs.

Motivation
3D-CAD contributes
PipeArrangement

designing efficiency

But…

Needs sophisticated skills
Automatic designＷｈｙ？

[Reason 1] Obscurity of the design Criteria
Not only to arrange shortest pipes between equipments!
ex.) Easy to operate valves, easy for maintenance, etc.
Answer1) Define numerical evaluation for all items
2) Formulate as a multi-objective optimization[Reason 2] A Problem in designing algorithms
It is no use that the algorithm gives only one solution!
GeneticAnswer
Show plural solutions
algorithm
Designer selects one of them as he needs.

Motivation
3D-CAD contributes
PipeArrangement

designing efficiency

But…

Needs sophisticated skills
Automatic designＷｈｙ？

[Reason 1] Obscurity of the design Criteria
Not only to arrange shortest pipes between equipments!
ex.) Easy to operate valves, easy for maintenance, etc.
Answer1) Define numerical evaluation for all items
2) Formulate as a multi-objective optimization[Reason 2] A Problem in designing algorithms
It is no use that the algorithm gives only one solution!
GeneticAnswer
Show plural solutions
algorithm
Designer selects one of them as he needs.

Overview
1. Motivation and Purpose
2. Evaluation Algorithm for Valve Operationality
Accessibility
Possibility of Valve Handling

3. Multi-Objective Optimization Algorithm
Coding for Genetic Algorithm (Only Valves)
Multi-Objective Genetic Algorithm: NSGA-Ⅱ
Routing Pipes and Making Branches

4. Experiments

5. Conclusion and Future Works

Valve Operationality
Evaluation of the space from pathways to valves
Good Arrangement

Fair Arrangement(2) Crew needs to get
down to go through thenarrow place

Accessible,
But…

Accessible

The valve can beoperated by hands(1) The valve can beoperated by some tools

Valve Operationality
Evaluation of the space from pathways to valves
Good Arrangement

Fair Arrangement(2) Crew needs to get
down to pass throughthe narrow place

Accessible,
But…

Accessible

The valve can beoperated by hands(1) The valve can beoperated by a rod

Valve Operationality
Evaluation of the space from pathways to valves
Bad Arrangement

Not Accessible!

All pipes and valvesmust be arranged not
only to put without
interference each otherbut also to make spacefrom pathways to valves
so that crew can accessthe valves.

Implicit and Obscure so far!

To apply optimization algorithms,
Numerical evaluation for the valve
operationality is needed.

Evaluation Algorithm for Valve Operationality
Accessibility
Crew can move to a position where the valve can beoperated by hands or by some tools.

Possibility of Valve Handling
The valve can be operated by hands.

The design space is partitioned into regular grids,
and recognize accessible segments
Evaluation

Recursive Fill Algorithm

Valve operationality is calculated inthis grid space by summing up theminimum distance from each valve toaccessible segments that are locatedin the direction of the axis of thevalve’s handle or four directions
perpendicular to that axis.

Finding Accessible Segments:
Recursive Fill Algorithm
ValvesWorker segment Matrix:
Imitating shape of the crew
(worker)

Sweep

Pathway
Obstacles:
Pipes, hull,pump, etc.

Finding Accessible Segments:
Recursive Fill Algorithm
ValvesWorker segment Matrix:
Imitating shape of the crew
(worker)

Pathway
Obstacles:
Pipes, hull,pump, etc.

Finding Accessible Segments:
Recursive Fill Algorithm
ValvesWorker segment Matrix:
Imitating shape of the crew
(worker)

Pathway
Obstacles:
Pipes, hull,pump, etc.

Finding Accessible Segments:
Recursive Fill Algorithm
ValvesWorker segment Matrix:
Imitating shape of the crew
(worker)

Pathway
Obstacles:
Pipes, hull,pump, etc.

Finding Accessible Segments:
Recursive Fill Algorithm
Able to handle by hand

Crew can movethis swept area

Able to handle by a rod
Distance (cost)= 3 segments

Obstacles:
Pipes, hull,pump, etc.

Divide into regulargrids, and judge
all segments.
Find inaccessible
segments using
the recursive fillalgorithm

Evaluate all valves,and sum up

DEMOFeatures of the Evaluation Algorithm
Accessible 1. Crew can move to a position wherethe valve can be operated by hands.
2. Crew can move to a position wherethe valve can be operated by a rod,but cannot be operated by hands.

Good
Cost = 0Fair
Cost= distance

Inaccessible

Crew cannot move to a position wherethe valve can be operated because
obstacles surround valves.

Expert’s Obscure or Implicit Criterion ofBad
Cost= 10000

Summing overall valves

Valve-Operationality is clearly numerically defined.

Overview
1. Motivation and Purpose
2. Evaluation Algorithm for Valve Operationality
Accessibility
Possibility of Valve Handling

3. Multi-Objective Optimization Algorithm
Coding for Genetic Algorithm (Only Valves)
Multi-Objective Genetic Algorithm: NSGA-Ⅱ
Routing Pipes and Making Branches

4. Experiments

5. Conclusion and Future Works

Motivation
3D-CAD contributes
Pipe
Arrangement

designing efficiency

But…

Needs sophisticated skills
Automatic design
Ｗｈｙ？

[Reason 1] Obscurity of the design Criteria
Not only to arrange shortest pipes between equipments!
ex.) Easy to operate valves, easy for maintenance, etc.
Answer1) Define numerical evaluation for all items
2) Formulate as a multi-objective optimization[Reason 2] A Problem in designing algorithms
It is no use that the algorithm gives only one solution!
GeneticAnswer
Show plural solutions
algorithm
Designer selects one of them as he needs.

Motivation

But…

3D-CAD contributes
Pipe
Arrangement

Needs sophisticated skills
designing efficiency Automatic design
Ｗｈｙ？
[Reason 1] Obscurity of the design criteria
Not only to arrange shortest pipes between equipments!
ex.) Easy to operate valves, easy for maintenance, etc.
Answer1) Define numerical evaluation for all items
2) Formulate as a multi-objective optimization[Reason 2] A Problem in designing algorithms
It is no use that the algorithm gives only one solution!
GeneticAnswer
Show plural solutions
algorithm
Designer selects one of them as he needs.

Multi-Objective Genetic Algorithm (MOGA)
crossover

Generating
new solutions

parentsmutationchildrenselection

survival

Generation t

Cost2
Cost 1
Pareto optimum solutions:Suited for showing plural solutions!

Generation t+1NSGA-Ⅱ
NSGA-Ⅱ： Nondominated Sorting Genetic Algorithms Ⅱ
Multi-objective Genetic algorithm
１． Efficient calculation in
Nondominated Sorting
２． Crowding distance
３． Elite strategy
NondominatedSorting

Reference
Kalyanmoy Deb:
A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-Ⅱ,IEEE Transactions on Evolutionary Computation, vol. 6, No. 2, (2002)

Crowding distance

Rank 3

Rank 3

Rank 2

Rank 2

Rank 1

Rank 1

Elite strategy

Problem Formulation
Pipe diagram

Pipeline
FROM – TO List

P&ID

Given
Equipment
Dim. & Loc.

Plot PlanEquipment arrangement list

Search SpaceParameters for VALVES
locationsdirections

Minimize

Valve
Operationality(cost)

Parameters for PIPES
locationsdirections
branchesandCost ofMaterials

patterns
locationsMaterial Cost
Material Cost Function

Weight of the kth pipe

Length of the kth pipe
Diameter of the kth pipe
Number of pipes

Coding for the Genetic Algorithm (GA)Parametersof Valvescoordinates
directions

The parameters of valves are dominant
to the parameters of pipes, because thepipes are routed between valves.

Coordinates of valves
Three parameters
Directions of valvesx axisy axisz axis

12 patterns

Only the parameters of the valves areencoded as the genes for the GA.
⎡θ1 θ 2⎢x x
12Gene Matrix: ⎢⎢ y1 y 2⎢⎣ z1 z 2L θn ⎤L x n ⎥⎥L yn ⎥⎥L zn ⎦

One point crossover

Pipes are arranged by local searchalgorithms after the parameters of valves
are determined. (Routing and Branching)Routing Pipes (1)Valves, pumps, connections or branches.
Each point has location and direction

Pipe Routing between
two points is limited tofinite patterns

Rigtht-angledSame
Vectors at start point andend point are opposite

Routing Pipes (2)Modification for Interfered Pipes

Pipes areInterferedInfeasible!

Routing Pipes (2)Modification for Interfered Pipes

Pipes areInterferedInfeasible!

Also the smaller diameter
pipes have the higher priority.

The more interferedpipes, the higher
priority to remove

Modification Operator
The green pipe is removed

All Pipes areSeparatedFeasible!

Maintain the shapeas similar as possible

Not Changed

Generating Branches of Pipes
Problems
How to Generate
T- branch efficiently?
Increasing elbows

Infeasible elbow

End point 1Branchcandidates?

End point 2
Start point
Main routeGenerating Branches of Pipes
Problems
How to Generate
T- branch efficiently?
Increasing elbows

Infeasible elbow

Answer:
Generate a T-branch on
an elbow on the mainroute of the pipeline

Branchcandidates

End point 1

End point 2
Start point
Main routeOverview
1. Motivation and Purpose
2. Evaluation Algorithm for Valve Operationality
Accessibility
Possibility of Valve Handling

3. Multi-Objective Optimization Algorithm
Coding for Genetic Algorithm (Only Valves)
Multi-Objective Genetic Algorithm: NSGA-Ⅱ
Routing Pipes and Making Branches

4. Experiments

5. Conclusion and Future WorksExperiments
Pipeline list

Total

Equipment arrangement list

Valves:5

Equipments:

1

Connections:3

Pipelines:

5

Pipes:

10

Parameters:

45

Combination over 1012

Results
Material Cost

Material Cost

badgood

Valve Operationality

Valve Operationality

After 400 generations（calculation time: 60 minutes）

Initial Population

Calculation Environment
In the MOGA, children are generated by:CPU:

Pentium 4 2.40GHz: One Point Crossover

Memory:512MB: Randomly Generated

OS:

Windows XP

Program Language： JavaObtained 3D Models

Material Cost = 8.12
Cost of Valve
Operationality = 0

Material Cost= 5.50
Cost of Valve Operationality= 10001

Multi-Objective Optimization algorithm enables us toshow plural Pareto-Optimal solutions simultaneously.

3D Models in the other settings

Narrow space

More Complex Pipeline

The more Improvement of the optimization algorithm is needed.

Overview
1. Motivation and Purpose
2. Evaluation Algorithm for Valve Operationality
Accessibility
Possibility of Valve Handling

3. Multi-Objective Optimization Algorithm
Coding for Genetic Algorithm (Only Valves)
Multi-Objective Genetic Algorithm: NSGA-Ⅱ
Routing Pipes and Making Branches4. Experiments

5. Conclusion and Future Works

Conclusions and Future Works
Conclusions
Make obscure criteria to be clear
1. supposition in Automatic Pipe Arrangement :Treat as multi-objective problem

2. Valve Operationality Evaluation Algorithm is proposed.
3. An Implementation of Multi-objective GA for pipe arrangement is proposed.

Future Works
1. Algorithm Improvement taking in the expert’s designing
procedure that the pipe routing is determined first,
thereafter, valves are set in the arranged pipes.

2. Evaluation Algorithm for Easiness of Pipe MaintenanceOpen Source

RemarksProposed System
Multi-Objective
Optimization
Algorithm

zPipe diagramzEquipment Arrangement list
zFrom-To list (Pipeline list)
zGeometric shapes of Hull,Equipments, and pipes

Expert’s knowledge forgenerating plans is stored

text file
Locations and directions ofPipes and Valves
Viewer

Evaluation Algorithms
text fileExpert’s knowledge for
evaluating plans is stored

CAD Operator

CAD System