2015年5月20日

SCI2015 ＠大阪

配管経路自動設計に関する研究

九州大学
州大学 大学院大学院工学研究院
学研究院
海洋システム工学部門
准教授 木村 元
九州大学 大学院工学府
海洋システム工学専攻
博士課程3年 安藤 悠人

1

研究目的
• 現状：ベテラン設計者頼み・人海戦術• 船舶の配管：狭隘空間に無理やり詰め込む

解決策：
自動配管設計システムの構築築2

先行研究

 Asmara等の研究:
等の研究 Delft‐Pipelf i• 配管設計問題をグラフ上の経路探索問題に帰着させた• ダイクストラ法を適用し、最小コストの経路を探索• 空間をメッシュ状に分割する際の間隔が空間をメ シ 状に分割する際の間隔がパイプの直径以上に制約される※Paulo等，Ito等

3

先行研究
Goal Point Asmara等の研究:
等の研究 Delft‐Pipelf i• 配管設計問題をグラフ上の経路探索問題に帰着させた
Obstacle

Obstacle• ダイクストラ法を適用し、最小コストの経路を探索• 空間をメッシュ状に分割する際の間隔が空間をメ シ 状に分割する際の間隔がパイプの直径以上に制約されるパイプの直径が大きい場合

×配管設計問題において大きな制約条件※Paulo等，Ito等

Start Point

4

Outline

 研究背景・目的究背景
的1 配管1本における経路探索
1.
• アプロ
アプローチ
チ

2 複数配管における経路探索
2.
• ダイクストラ法

3 シミュレーション実験
3.
シミ レ シ• 各パイプピース
ン実験
 結論

• パイプラック空間と通路空間• 鳥居配管• メッシュ分割
5

アプローチ
配管設計問題
研究対象
配管経路探索問題• 設計対象空間

機器配置問題：パイプを設置可能な空間の範囲
パイプを設置可能な空間の範囲
本研究では直方体座標及びそ からパイプが• パイプの始点・終点
パイプ 始点 終点 ：座標及びそこからパイプが伸びるベクトル• 対象とするパイプ：分岐を持たず、始点から終点まで6直径が変化しないパイプ

アプローチ
配管経路探索問題
管経路探索問題 ＝ グラ
グラフ上の最短経路探索問題
最短経路探索問題ダイクストラ法

空間を離散化

グラフ化
メッシュの分割幅はパイプ径に依存せず

ダイクストラ法で7最短経路探索空間の離散化について（曲面を持つ船殻への対応）
Goal

Start

ローカル座標系を持つ基準点を配置

空間の離散化について（曲面を持つ船殻への対応）
Goal

Start

ローカル座標系を持つ基準点を配置

隣接する基準点同士を各座標軸方向に隣接する基準点同 を各座標軸方向
ベンド2個以下のパイプで繋がるかどうか判定

空間の離散化について（曲面を持つ船殻への対応）
Goal

Start

ローカル座標系を持つ基準点を配置

隣接する基準点同士を各座標軸方向に隣接する基準点同 を各座標軸方向
ベンド2個以下のパイプで繋がるかどうか判定

グラフ化

ダイクストラ法で最短経路探索空間の離散化について（曲面を持つ船殻への対応）
Goal

Goal

Start

Start

ローカル座標系を持つ基準点を配置

パイプ配置

隣接する基準点同士を各座標軸方向に隣接する基準点同 を各座標軸方向
ベンド2個以下のパイプで繋がるかどうか判定

グラフ化

ダイクストラ法で最短経路探索

ダイクストラ法“ダイクストラ法”とは…
グラフ構造の問題に対して任意の２点間を結ぶ最小コストの経路を求めるアルゴリズム．
エッジに非負の重みが設定されている場合，最短経路の獲得が保証されている．の獲得が保証されている
C1とC7を結ぶ最小コストの経路は？
75C110C23C3678C4735C58C67C75C110C23C3678C4735C516C78C612アプローチ

グラフ構造 置き換える利点
グラフ構造へ置き換える利点• ダイクストラ法などの経路探索の利用 → 確実に最適解が獲得される• エッジの重みとして，設計項目のコストを反映
エッジの重みとして 設計項目のコストを反映 → 実用的な経路の獲得（設計項目：実際の設計者が作業中に考慮している点）

13

アプローチエルボベンド鳥居配管パイプ
ラック

通路

グラフ構造 置き換える利点
グラフ構造へ置き換える利点• ダイクストラ法などの経路探索の利用 → 確実に解が獲得される• エッジの重みとして，設計項目のコストを反映
エッジの重みとして 設計項目のコストを反映 → 実用的な経路の獲得（設計項目：実際の設計者が作業中に考慮している点）

14

各パイプピース
パイプピ ス：配管経路を構成するパイプのパ ツ
パイプピース：配管経路を構成するパイプのパーツ
システム内で考慮されているパイプピース
システム内で考慮されているパイプピス
直管：真直ぐに延びたパイプピース
エルボ：90度に曲がるパイプピース
曲率等のパラメータ有り
ベンド：局所的に斜めに通過するパイプピース
ベド 局所的 斜め 通過するパイプピ
曲率等のパラメータ有り
15

エルボ

d ≧F
d2
Node P

Temporary
node

d 1d1
 ≧RF

Current node
Diameter：D16

エルボInterference Check!
Temporarynode

Current node17

エルボ

Recording Costs

Next node

Current node

18

ベンド
“ベンド”とは…
• ベンドとはエルボよりも曲げ半径が大きなパイプピース．
• エルボだけでは対処できない個所に使用される．
エルボだけでは対処できない個所に使用される

名村テクニカルレビューより

19

ベンド

Goal Point

Start Point

20

ベンド

Goal Point

Start Point

21

ベンド

 1,  2, d を設定（本研究では、 1  5,  2  0, d  R と設定）




d  2   1 D2  1
  arcsin  arcsin 22 D  (2  1)  ( 2)  (2  1) 2  ( 2) 2 L  (21 Rsin)  (2 Rcos)

L ：ベンドを設置するのに必要な最小距離22

各パイプピースのコスト
Straight

Node
Straight
CurrentNodeElbow

Bend

NodeElbow
Node
Bend23

各パイプピースのコスト

直管のコスト( CS ) : d×D
エルボのコストボ( CE ) : (d + 0.1)×D
ベンドのコスト ( CB ) : ((d + 0.3 ))×D

Node
Straight
Current
Node

ただし，d: ノード間のマンハッタン距離
D: パイプの直径

NodeElbow
CSCECB

NodeBend24

各パイプピースのコスト

直管のコスト( CS ) : d×D
エルボのコストボ( CE ) : (d + 0.1)×D
ベンドのコスト ( CB ) : ((d + 0.3 ))×D

Node
Straight
Current
Node

ただし，d: ノード間のマンハッタン距離
D: パイプの直径

NodeElbow
CSCECB

NodeBend25

Start Point

シミュレーション実験

Goal Point• 目的
障害物が多数配置された設計対象空間内の経路探索を行うことで本手法の動作を確認する• 問題設定・設計対象空間
設計対象空間 ：Size
Si X 16.75m,16 75 Si
Size Y 33m, Si
Size Z 33m
・格子分割幅：Size X 0.25m, Size Y 0.25m, Size Z 0.25m

・始点座標および向き：( 0.5m, 1.75m, 1.5m), x+・終点座標および向き：( 16.5m,, 1. 5m,, 1.5m),, x・障害物として10個の直方体を配置

27

鳥居配管の回避“鳥居配管”とは…
• 配管が上向きに，もしくは下向きにU字になっている箇所．
液体・気体が内部に溜まるため気体が内部に溜まるため，ドレイン抜き，ガス抜きを設置する．
ドレイン抜き ガス抜きを設置する• 液体• 意図的でないものは設計上好ましくない．
ガス抜き

28

鳥居配管の回避
目的
システム内での鳥居配管の取り扱い
システム内での鳥居配管の取り扱い．

結果
溜りの発生を可能な限り抑えた設計案を獲得．
溜り
発 を 能 限り抑設計案を獲得

鳥居配管を考慮しない場合

鳥居配管を考慮した場合（垂直方向にコストを割増） 29

配管1本の経路探索

Obstacle

パイプラック通路・ パイプ長・ エルボおよびベンドの数
・ パイプラック空間

グラフ構造におけるコスト値

・ 通路空間・ 鳥居配管の発生（垂直方向への移動）

ダイクストラ法（単目的最適化）30

Outline

 研究背景・目的究背景
的1 配管1本における経路探索
1.
2 複数配管における経路探索
2.
3 シミュレーション実験
3.
シミ レ シ• 複数本の探索における問題点
ン実験• タッチアンドクロス法の利用

 本研究の成果• 焼きなまし法の利用

31

複数本の探索における問題点
 径の大きいパイプからルーティング 同じ径のパイプはランダムで選択

Random choice

Random choice32

複数本の探索における問題点
太いパイプから1本ずつルーティングG

ObstacleG

Pipe BS

Pipe AGPipe C
ObstacleSS

33

先行研究での複数本の取り扱い
太いパイプから1本ずつルーティングG

ObstacleG

Pipe BS

Pipe AG

Pipe C
ObstacleSS

34

複数本の探索における問題点
太いパイプから1本ずつルーティングG

ObstacleG

Pipe BS

Pipe AG

Pipe C
ObstacleSS

35

複数本の探索における問題点
経路が複数本ある場合，実用的な解を獲得できる保証がない．

×○・ 経路を探索する順序の影響
・ 1本の経路中で最適解が複数個ある場合の，解の選択による影響
本 経路中 最適解が複数個ある場合
解 選択
る影響
36

探索順序による影響

ΦA = ΦB

最終的に得られる経路が，探索の順序により異なる．
37

探索順序による影響

ΦA = ΦB

38

探索順序による影響

ΦA = ΦB

最終的に得られる経路が，探索の順序により異なる．
39

探索順序による影響

1

2

3

3
1

2・ 過去のシミュレーションで観察された，経路探索の順序による影響．
過去のシミュレ ションで観察された，経路探索の順序による影響．
・ 青のパイプから探索するか，緑のパイプから探索するかで設計案が異なっている．
40

解の選択による影響

ΦA < ΦB41

解の選択による影響

ΦA < ΦB42

解の選択による影響

ΦA < ΦB

解の選択によって．経路が変更されている．
43
始点・終点距離が短いパイプから探索するべきか？

解の選択による影響

Detour

過去のシミュレーションで観察された，最適解の選択による影響．
エルボの位置によって細い経路が迂回している．

44

複数本の経路探索
経路が複数ある場合の問題点
・ 経路を探索する順序
・ 解の選択影響を可能な限り取り除きたい・タッチアンドクロス法の適用
・焼きなまし法の適用
45タッチアンドクロス法の適用“タッチアンドクロス法”とは…
• 集積回路の配線問題を解決するために松岡・新田（1998）によって提案された手法．
• ペナルティ関数法における外点法に分類される．
• 経路同士の干渉に対してペナルティを設定し，複数回の経路探索を行う
中で，干渉コストを徐々に上昇させる．
f(x) + t g(x)t：大f(x)が支配的
t 大t：大g(x)が支配的
ただし，拡張目的関数：f(x) + t g(x)g(x)が支配的

制約条件

目的関数 ：f(x)ペナルティ関数：g(x)46パラメータ ： t （探索が進むと上昇）タッチアンドクロス法の適用“タッチアンドクロス法”とは…
• 集積回路の配線問題を解決するために松岡・新田（1998）によって提案された手法．
• ペナルティ関数法における外点法に分類される．
• 経路同士の干渉に対してペナルティを設定し，複数回の経路探索を行う
中で，干渉コストを徐々に上昇させる．
t：小f(x) + t g(x)f(x)が支配的g(x)が支配的
ただし，拡張目的関数：f(x) + t g(x)t：小g(x)が支配的

制約条件

目的関数 ：f(x)ペナルティ関数：g(x)47パラメータ ： t （探索が進むと上昇）タッチアンドクロス法の適用“タッチアンドクロス法”とは…
• 集積回路の配線問題を解決するために松岡・新田（1998）によって提案された手法．
• ペナルティ関数法における外点法に分類される．
• 経路同士の干渉に対してペナルティを設定し，複数回の経路探索を行う
中で，干渉コストを徐々に上昇させる．
t：中f(x) + t g(x)f(x)が支配的

ただし，t：中g(x)が支配的g(x)が支配的
拡張目的関数：f(x) + t g(x)

制約条件

目的関数 ：f(x)ペナルティ関数：g(x)48パラメータ ： t （探索が進むと上昇）タッチアンドクロス法の適用“タッチアンドクロス法”とは…
• 集積回路の配線問題を解決するために松岡・新田（1998）によって提案された手法．
• ペナルティ関数法における外点法に分類される．
• 経路同士の干渉に対してペナルティを設定し，複数回の経路探索を行う
中で，干渉コストを徐々に上昇させる．
t：大f(x) + t g(x)t：大f(x)が支配的g(x)が支配的
ただし，拡張目的関数：f(x) + t g(x)g(x)が支配的

制約条件

目的関数 ：f(x)ペナルティ関数：g(x)49パラメータ ： t （探索が進むと上昇）タッチアンドクロス法の適用“タッチアンドクロス法”とは…
• 経路同士の干渉に対してコストを設定し，複数回の経路探索を行う中で，干渉コストを徐々に上昇させる．

CTotal = ∑CPipe
CPipe = CParts × RSpace ＋ CInterference
パイプピースの使用コスト

通路・パイプラック空間による割引率

経路同士の干渉コスト（探索が進むにつれて値が増加）

50タッチアンドクロス法の適用

CInterference

2次元平面図での探索イメージ

Num. of repetition

探索序盤
・ 干渉コスト：小さい・ 各経路は最短経路で結ばれている
各経路は最短経路で結ばれている．
51

タッチアンドクロス法の適用

CInterference

2次元平面図での探索イメージ

Num. of repetition

探索中盤～終盤
・ 干渉コスト：大きい・ 干渉状態を避けている
干渉状態を避けている．
52

タッチアンドクロス法の適用

CInterference

2次元平面図での探索イメージ

Num. of repetition

探索終盤
・ 干渉コスト：大きい・ 干渉状態を避けている干渉状態を避けている．
53

タッチアンドクロス法の適用

CInterference

2次元平面図での探索イメージ

Num. of repetition

探索終盤
・ 干渉コスト：大きい・ 干渉状態を避けている
干渉状態を避けている．
54タッチアンドクロス法の適用
T.C.法（タッチアンドクロス法）の課題
 回路設計のための手法なため，経路がすべて結ばれたらその時点で探索を終了してしまう．
 山登り法が基本であるため、探索が行き詰る．

複数配管経路の最適な最終設計案を獲得するためには不十分．

探索の後戻りを許し，探索の行き詰りを避ける．
を許し 探索の行き詰りを避ける
焼きなまし法の導入
焼法 導入
55

焼きなまし法の適用
焼きなまし法とは…
• 局所解にとらわれず，大域的な解候補を探索するための手法．
• 温度Tを徐々に小さくしていく中で，現在の解のランダムな近傍の解をもとめる．
解をもとめるCTotal• 温度Tが大きい内は解の移動が大きく，Tが小さくなると収束する．
T局所解
局所解
最適解

パラメ タ
パラメータ

繰り返し回数56

焼きなまし法の適用
焼きなまし法とは…
• 局所解にとらわれず，大域的な解候補を探索するための手法．
• 温度Tを徐々に小さくしていく中で，現在の解のランダムな近傍の解をもとめる．
解をもとめるCTotal• 温度Tが大きい内は解の移動が大きく，Tが小さくなると収束する．
T

パラメ タ
パラメータ

繰り返し回数57

焼きなまし法の適用
焼きなまし法とは…
ΔC = Cn+1 – C n• 局所解にとらわれず，大域的な解候補を探索するための手法．

P = exp( -ΔC/T )CTotal• 温度Tを徐々に小さくしていく中で，現在の解のランダムな近傍の• C n+1 > C nの場合は遷移確立Pに従って，解候補を取得．
解をもとめる
解をもとめる．
• 取得後は，温度関数Tを減少させる．
• 温度Tが大きい内は解の移動が大きく，Tが小さくなると収束する．
• Tが大きなうちは解が大きく変更され，小さくなるにつれて収束する．

T
温度関数：大解の入れ替え幅：大現在の解パラメータ

繰り返し回数58

焼きなまし法の適用
焼きなまし法とは…
ΔC = Cn+1 – C n• 局所解にとらわれず，大域的な解候補を探索するための手法．

P = exp( -ΔC/T )CTotal• 温度Tを徐々に小さくしていく中で，現在の解のランダムな近傍の• C n+1 > C nの場合は遷移確立Pに従って，解候補を取得．
解をもとめる
解をもとめる．
• 取得後は，温度関数Tを減少させる．
• 温度Tが大きい内は解の移動が大きく，Tが小さくなると収束する．
• Tが大きなうちは解が大きく変更され，小さくなるにつれて収束する．

T
温度関数：中解の入れ替え幅：中
現在の解

パラメータ

繰り返し回数59

焼きなまし法の適用
焼きなまし法とは…
ΔC = Cn+1 – C n

• 局所解にとらわれず，大域的な解候補を探索するための手法．

P = exp( -ΔC/T )CTotal• 温度Tを徐々に小さくしていく中で，現在の解のランダムな近傍の• C n+1 > C nの場合は遷移確立Pに従って，解候補を取得．
解をもとめる
解をもとめる．
• 取得後は，温度関数Tを減少させる．
• 温度Tが大きい内は解の移動が大きく，Tが小さくなると収束する．
• Tが大きなうちは解が大きく変更され，小さくなるにつれて収束する．

T
温度関数：小解の入れ替え幅：小現在の解パラメータ

繰り返し回数60

焼きなまし法の適用
焼きなまし法とは…
ΔC = Cn+1 – C n

• 局所解にとらわれず，大域的な解候補を探索するための手法．

P = exp( -ΔC/T )CTotal• 温度Tを徐々に小さくしていく中で，現在の解のランダムな近傍の• C n+1 > C nの場合は遷移確立Pに従って，解候補を取得．
解をもとめる
解をもとめる．
• 取得後は，温度関数Tを減少させる．
• 温度Tが大きい内は解の移動が大きく，Tが小さくなると収束する．
• Tが大きなうちは解が大きく変更され，小さくなるにつれて収束する．

T
温度関数：小解の入れ替え幅：小現在の解パラメータ

61
繰り返し回数T.C.法・焼きなまし法を組み合わせた探索手法
データ読み込み
ルーティング（Pipe 1）
全パイプに対して経路探索

設計案の比較 選択
設計案の比較・選択ルーティング（Pipe 2）・温度下降
・CInterference 上昇

設計案の比較・選択

温度が最終値以上

ルーティング（Pipe N）
温度が最終値以下

最終設計案を獲得

様々な設計案を比較し，妥当な最終解を獲得可能

62

各パイプピース
温度関数：Tk+1 = Tk × α / (nβ)（α = 1, β = 0.01）

干渉コスト：CInterference = T0/T × VPipe（T0: Tの初期値，VPipe: 干渉しているパイプピースに外接する立方体の体積）
T, CInterference:T: CInterferece

温度関数：T
干渉コスト：CInterfere

Repeat counts : nn

63

Outline

 研究背景・目的究背景
的1 配管1本における経路探索
1.
2 複数配管における経路探索
2.
3 シミュレーション実験と考察
3.
シミ レ シ ン実験と考察
 本研究の成果
64

シミュレーション実験
実験１
設計対象空間 x 6 x 6 [m]設計対象空間：6
直径 x 本数：0.8[m] x 1, 0.6[m] x 2, 0.4[m] x 4,0.3[m] x 5
通路空間3個，パイプラック2個，障害物3個

実験２
設計対象空間：8 x 12 x 4 [m]
直径 x 本数：0.9[m]
本数x 1, 0.7[m] x 1, 0.5[m] x 1,0.3[m] x 1

65

シミュレーション実験1最終設計案
パイプラック空間

通路空間

 同じ条件で実験を5回行い，5回とも探索結果の中では最良な解が獲得された
 探索時間：およそ9時間（Windows7, Intel Core i7 3.4Ghz, 8.00GB）

66

シミュレーション実験1

探索ステップ探索
テップ

k=1, T=100
 探索序盤のため，最短経路で結ばれている．
温度67

シミュレーション実験1

探索ステップ探索
テップ

k=18, T=70
 探索中盤，経路同士が互いに避け始めている．
温度68

シミュレーション実験1

探索ステップ探索
テップ

k=95, T=3
 探索終盤，経路同士が互いに避けている．
温度69

シミュレーション実験170

シミュレーション実験1
経路同士の干渉あり（制約違反）

経路同士の干渉なし

 探索ステップが23付近で収束．
探索ステ プが 付近で収束
 CTotal は拡張目的関数のため，探索ステップと共に増加

71

シミュレーション実験2
最終設計案

 干渉の無い最終設計案が確認された．
 探索時間：およそ18時間（Windows7, Intel Core i7 3.4Ghz, 8.00GB） 72

シミュレーション実験2

探索ステップ探索
テップ

k=1, T=100
 探索序盤のため，最短経路で結ばれている．
ば
温度73

シミュレーション実験2

探索ステップ探索
テップ

k=50, T=29
 探索中盤，経路の干渉が減少している．
温度74

シミュレーション実験2

探索ステップ探索
テップ

k=110, T=1
 探索終盤，経路同士の干渉はなくなっている．
温度75

シミュレーション実験276

シミュレーション実験2
経路同士の干渉あり（制約違反）

経路同士の干渉なし

 探索ステップが31付近で収束．
探索ステ プが 付近で収束
 CTotal は拡張目的関数のため，探索ステップと共に増加

77

考察

探索結果 妥当性
探索結果の妥当性• 実験1では最良解の獲得が可能．
• 実験2ではばらつきあり．（ただし，実用的な範囲）

探索時間• 実験1,2でそれぞれ9時間，18時間．
実験
れぞれ 時時• 機器配置システムとの連動を考えると，短縮の必要あり．
• 経路探索アルゴリズムの変更（A*サーチ，複数の計算機の同時使用等）
経路探索アルゴリズムの変更（ *サ チ 複数の計算機の同時使用等）
78

考察
配管設計支援システム実用化へ向けた課題

Ship Hull 経路探索• 船殻に沿った斜めの配管 → 斜めメッシュの追加
幾何学的経路探索• コストの妥当性（各条件下でのコストの割増，割引）

 機器配置• タッチアンドクロス法との併用 → 機器配置と経路探索の同時進行

 その他• 施工性の評価 → フランジ割り問題の定式化• 設計修正システム → 設計者が作成した設計案を自動修正する機能．
79• 設計意図やルールの指示方法 → ソースコードに触れずに簡単指示

Outline

 研究背景・目的究背景
的1 配管1本における経路探索
1.
2 複数配管における経路探索
2.
3 シミュレーション実験と考察
3.
シミ レ シ ン実験と考察
 本研究の成果
80本研究の成果

 パイプ1本の経路探索問題において，メッシュの細かさがパイプの直径にパイプ1本の経路探索問題において メ シ の細かさがパイプの直径に依存せず、実用的な項目（各パイプピース，各空間，鳥居配管）を考慮して最適経路を得るアルゴリズムを提案したこと．
最適経路を得る
ゴリズムを提案した と 配管経路が複数ある場合を想定し，経路探索の順序と解の選択による影響を抑えるため，タッチアンドクロス法と焼きなまし法を組み合わせた経路探索アルゴリズムを提案したこと．
 バラストポンプルーム，デッキ裏スペースを想定した設計対象に対して，シミュレーション実験を行い，提案手法の有用性を確認．
81