Annual Spring Meeting 2014 in Sendai, May 26-27

タッチアンドクロス法を利用した配管自動ルーティング
Automatic pipe-routing system using Touch and Cross method
九州大学大学院海洋システム工学専攻
安藤 悠人

木村 元 准教授

Outline

 研究背景・目的
1. 配管1本における経路探索
2. 複数配管における経路探索

3. シミュレーション実験
 結論

研究背景と研究目的
研究背景
・ 配管設計に潜む複数の検討課題- 機器をどこに配置するか？
- どのような経路で結ぶか？
- 安全性，etc.

・ ベテラン設計者の減少

設計が困難に！
https://www.flickr.com

研究背景と研究目的
研究目的

配管設計問題の解決へ向けて，設計作業の支援を行うシステムを構築すること．

配管経路自動設計システム
・ ダイクストラ法・ タッチアンドクロス法
・ 焼きなまし法

Outline

 研究背景・目的
1. 配管1本における経路探索
2. 複数配管における経路探索

3. シミュレーション実験
 結論

配管1本における経路探索
配管経路探索問題 ＝ 迷路探索問題
ダイクストラ法
ネットワーク上の2点間の最短経路を効率よく探索するアルゴリズム

配管1本における経路探索
システムの特徴・エルボ，ベンド，鳥居配管，パイプラック，通路空間を考慮
エッジの重みを変化させる
単純な最短経路ではなく，実用的な経路を探索できる．

配管1本における経路探索
システムの特徴・エルボ，ベンド，鳥居配管，パイプラック，通路空間を考慮
エッジの重みを変化させる
単純な最短経路ではなく，実用的な経路を探索できる．

鳥居配管の除去

パイプラック空間の通過

Outline

 研究背景・目的
1. 配管1本における経路探索
2. 複数配管における経路探索

3. シミュレーション実験
 結論

先行研究での複数本探索への対応
 径の大きいパイプからルーティング 同じ径のパイプはランダムで選択

Random choice

Random choice

先行研究での複数本探索への対応
太いパイプから1本ずつルーティングG

ObstacleG

Pipe BS

Pipe AG

Pipe C
ObstacleSS

先行研究での複数本探索への対応
太いパイプから1本ずつルーティングGObstacle

G

Pipe BS

Pipe AG

Pipe C
ObstacleSS

先行研究での複数本探索への対応
太いパイプから1本ずつルーティングG

ObstacleG

Pipe BS

Pipe AG

Pipe C
ObstacleSS複数本探索における問題点
経路が複数本ある場合，最適解を獲得できる保証がない．

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

経路探索の順序による影響

ΦA = ΦB

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

経路探索の順序による影響

ΦA = ΦB

経路探索の順序による影響

ΦA = ΦB

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

経路探索の順序による影響
12

3

3
12

・ 過去のシミュレーションで観察された，経路探索の順序による影響．

・ 青のパイプから探索するか，緑のパイプから探索するかで設計案が異なっている．

1本の経路中における解の選択による影響

ΦA < ΦB

1本の経路中における解の選択による影響

ΦA < ΦB

1本の経路中における解の選択による影響

ΦA < ΦB

解の選択によって．経路が変更されている．

始点・終点距離が短いパイプから探索するべきか？

1本の経路中における解の選択による影響

Detour

過去のシミュレーションで観察された，最適解の選択による影響．

エルボの位置によって細い経路が迂回している．

複数本の配管経路探索
経路が複数ある場合の問題点
・ 経路を探索する順序
・ 解の選択影響を可能な限り取り除きたい・タッチアンドクロス法の適用
・焼きなまし法の適用

タッチアンドクロス法（T.C.法）の適用
タッチアンドクロス法とは…
• 集積回路の配線問題を解決するために松尾らによって提案された手法．
• 経路同士の干渉に対してコストを設定し，複数回の経路探索を行う中で，干渉コストを徐々に上昇させる．

CTotal = CPipe × RSpace ＋ CInterference
CTotal : 経路の総コスト

CPipe ： パイプピースの使用コスト
RSpace : 通路・パイプラック等の空間による割引率
CInterference ： 経路同士の干渉コスト

タッチアンドクロス法（T.C.法）の適用

CInterference

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

Num. of repetition

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

タッチアンドクロス法（T.C.法）の適用

CInterference

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

Num. of repetition

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

タッチアンドクロス法（T.C.法）の適用

CInterference

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

Num. of repetition

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

タッチアンドクロス法（T.C.法）の適用

CInterference

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

Num. of repetition

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

タッチアンドクロス法（T.C.法）の適用

CInterference

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

Num. of repetition

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

タッチアンドクロス法（T.C.法）の適用
T.C.法の課題
 回路設計のための手法なため，経路がすべて結ばれたらその時点で探索を終了してしまう．

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

繰り返しのプロセスの中で，幅広い設計案を比較する必要がある．

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

パラメータ

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

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

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

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

繰り返し回数焼きなまし法
焼きなまし法とは…
ΔC = Cn+1 – C n

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

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

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

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

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

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

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

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

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

繰り返し回数T.C.法と焼きなまし法を組み合わせた探索手順
1回目の探索結果，CTotal, 1含まれる全パイプの経路探索（始点・終点間距離の短いもの順）

・・・n回目の探索結果，CTotal, n• 遷移確立Pに従って，解候補を入れ替え．
• 取得後は，温度関数Tを減少させ，干渉コスト値を上昇させる（T.C.法）．

n+1回目の探索結果，CTotal, n+1・・・様々な設計案を比較し，妥当な最終解を獲得可能

温度関数と干渉コスト関数
温度関数：Tk+1 = Tk × α / (nβ)（α = 1, β = 0.01）

干渉コスト：CInterference = T0/T

（T0: Tの初期値）

T, CInterference:T: CInterferece

温度関数：T
干渉コスト：CInterferenRepeat counts : nOutline

 研究背景・目的
1. 配管1本における経路探索
2. 複数配管における経路探索

3. シミュレーション実験
 結論

シミュレーション実験
実験１
設計対象空間：6 x 6 x 6 [m]
直径 x 本数：0.8[m] x 1, 0.6[m] x 2, 0.4[m] x 4,0.3[m] x 6
通路空間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

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

パイプラック空間

通路空間

 同じ条件で実験を5回行い，5回とも妥当な結果が獲得された

 探索時間：およそ18時間（Windows7, Intel Core i7 3.4Ghz, 8.00GB）

シミュレーション実験１

繰り返し回数

T=100, n=1
温度

 探索序盤のため，最短経路で結ばれている．

シミュレーション実験１

繰り返し回数

T=60, n=25
温度

 探索中盤，経路同士が互いに避け始めている．

シミュレーション実験１

繰り返し回数

T=3, n=95
温度

 探索終盤，経路同士が互いに避けている．

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

 妥当な最終設計案が確認された．

 探索時間：およそ18時間（Windows7, Intel Core i7 3.4Ghz, 8.00GB）

シミュレーション実験２

繰り返し回数

T=100, n=1
温度

 探索序盤のため，最短経路で結ばれている．シミュレーション実験２

繰り返し回数

T=40, n=38
温度

 探索中盤，経路の干渉が減少している．

シミュレーション実験２

繰り返し回数

T=1, n=111
温度

 探索終盤，経路同士の干渉はなくなっている．

Outline

 研究背景・目的
1. 配管1本における経路探索
2. 複数配管における経路探索

3. シミュレーション実験
 結論

結論と今後の課題
結論
 配管設計の自動化を目標に，自動的に経路を探索するシステムを提案
 配管経路が複数ある場合でも妥当な設計案を獲得する手法を提案

・ ダイクストラ法・ タッチアンドクロス法（干渉コスト，短いもの順）

・ 焼きなまし法（解の入れ替え）

探索順序による影響，解の選択による影響を抑えることが可能．

結論と今後の課題
今後の課題
・ 現在の温度関数および干渉コスト関数の妥当性
可能な限り，問題依存にならないような関数の設定

・ 他の条件下でのシミュレーション実験

・ 探索時間の短縮
・ 斜め配管の対応

Ship Hull

本研究は，日本学術振興会科学研究費補助金基盤研究(B) 課題番号23360388より補助を受けた．