干渉を無視した最短経路の重なり具合に着目した
配管経路自動設計法○木村元 安部健介（九州大学）
Automatic Piping Arrangement Design Making Use of Overlapped Shortest Piping Paths
Ignoring Each Other’s Interferences* H. Kimura and K. Ave (Kyushu University)
Abstract－ Piping arrangement design problems are not the same as the shortest path planning problems. Because the pipes have branches, or we should find multiple piping paths simultaneously that minimize total costs under the condition that the pipes do not interfere with each other. In addition, the pipes have many geometrical restrictions. This paper presents a new piping arrangement method making use of information of overlapped shortest
piping paths ignoring each other's interferences. The proposed system is implemented to a computer program, andthe performance of the system is demonstrated through several simulations.
Key Words: Path planning, Piping arrangement, Touch and cross method, Routing

1

はじめに

はこの単純なケースを基本とするが，後半ではソースが１か所でドレインが複数，あるいはドレインが１か所でソースが複数存在する木構造の配管経路において分岐を含むケースについても考察する．

建築物や船舶、プラント等の設備において，配管設計には膨大な作業時間を要する．
作業時間短縮のため，近年では発達した情報処理技術を利用した設計作業の省力化が図られてきた．特に 3 次元 CAD の導入によ
3 配管経路探索問題
り，3 次元データでの設計・解析・生産技術が普及しつつある．機器配置や配管経路を 3 次元空間中に可視
3.1 パイプの制約条件と構成要素化することで設計案の修正が容易となり，作業の効率対象とする配管経路では以下の項目を前提とする：化が進められている．しかし作業そのものは未だに熟【分岐無し配管】始点・終点を一つずつ有し，経路途練者に頼っている．近年では熟練者の確保が困難にな
中で分岐がなく，直径の変化もない配管経路を対象とってきており，若手技術者への技術伝承問題も発生しする．通常，配管経路には分岐点が存在するが，第 2ている．特に配管経路の設計作業は作業時間の多くの章で述べたとおり本手法では分岐点を機器の一種とみ割合を占めており，設計作業全体の効率化を図る上でなすことにより，単純な経路探索アルゴリズムが利用重要な課題である．
可能となる．また，経路を構成するパイプ部材の形状
配管経路の設計問題は，単に始点と終点を最小コスとして以下の 3 つを考慮しなければならない：
トで結ぶ単なる経路探索問題ではなく，互いの管同士【直管】真直ぐに伸びているパイプピース．の干渉を回避しつつ全体としてコストが最小となるよ【ベンド】任意の角度で曲げられたパイプピース．曲
うな配置を求めなければならない．また，経路には分げ半径は一般に管径の 2，3，4 倍など離散値をとる．
岐も存在し，管を配置するにあたりいくつかの限られまた，パイプベンダによる加工の都合上，ベンドピー
た 曲率で管を曲げてカーブを有する構造部材に沿っスの前後には，つかみ代として十分な長さの直管部分て配置するなど自動設計を妨げる要因が多数存在する． がある．圧力損失を減らすため，曲げ半径は大きいほ
本研究では、管の配置が許される経由点候補をあらかうが好ましいが，障害物や他パイプとの干渉を避けるじめ与えた上で分岐を含んだ複数系統の配管の配置をには曲げ半径が小さいほうが都合良い．曲げ半径のと決定するための発見的方法として，まずは管同士の干りうる値や曲がり部前後の直管部の長さは，事前にパ渉を無視して最小コスト経路をすべて列挙し，それらラメータとして設定しておく必要がある．の重なり具合を調べて有望な経路を生成する方法を提【エルボ】90 度に曲がっているパイプピース．ベンド
案する．本手法は，干渉を無視した最短配管経路を生の一種である場合と，曲げ加工ではなく鋳物の場合が成してから１本ずつ経路を引き直して干渉を解消してある．角度が 90 度である以外はベンドと同様である．
いく「タッチアンドクロス法」で安定した解を得るた【経由候補点】
パイプを配置する位置と方向の制約は，めの初期配管経路生成方法として用いる．シミュレー
パイプのサポートやパイプラックに固定する都合によション実験を通じて利点や問題点等の評価を行う．
り発生する場合が最も多い．本研究では，サポート等
2配管設備設計問題

配管設計では，まず対象空間内に存在するバルブやレデューサ等の移動可能な機器の適切な配置を検討しなければならない．本論文ではこの問題を「機器配置問題」と呼び，ここでは扱わない．配管の分岐点も機器として扱うことで，配管問題は始点・終点を一つずつ含む単純な経路決定問題となり，本研究で扱う問題

によりパイプを固定することが想定される箇所の座標と方向を規定するローカル座標系を「経由点候補」として予め与える．パイプの中心は，いずれかの経由候補点の座標を通り，その点を通るパイプの方向は，その経由候補点に定義されたローカル座標系の x,y,z 軸いずれかの方向に平行になる．
このローカル座標系は，サポート材のベースとなる構造部材等の方向に合わせてナナメなど任意の方向へ自由に設定可能である．
3.2 パイプ以外の制約条件と構成要素
さらにパイプ以外に，経路探索を行う前提条件として以下の項目を設定する：【障害物】設計対象空間内に存在する構造部材や機器などが配置される空間．配管経路がこれらの空間に干渉することは許容されない．形状として三角形平面の組合せ，円筒，球および直方体などを想定している．
4配管経路探索問題

4.1 一本の配管経路に対する経路探索アルゴリズム
本研究では１本の配管経路探索問題を「重み付きグラフ上の最小コストの経路探索問題」に帰着して解決を図っており，アルゴリズムとしてダイクストラ法を用いる．Fig.1 に本経路探索の手順概略を示す．

Fig. 1 Process of routing for single pipe-route.

まず設計対象空間において 3.1 節で説明したパイプの経由候補点を配置する．この経由候補点は，構造部材やサポートの位置，管径を考慮して予め与えることを前提とするが，効果的な経由点候補の位置と方向を自動計算で与える方法についても検討中である 4)．
次に，各経由候補点に定義されたローカル座標軸方向（6 方向）から，別の経由候補点の局所座標軸方向へベンド 2 個以下のパイプで接続可能かどうかをチェックする．数学的には、ベンド曲げ角度制約および掴み代のような直管部の長さ制約が無ければ，あらゆる位置と方向の経由点候補はベンド 2 個以下のパイプで接続できる．本研究では，２つの経由候補点 A，B を接続するとき，注目する局所座標軸の方向へ屈曲点まで伸ばした点を A’，B’と表すと，AA’:A’B’:BB’=1:2:1 となるような長さの比率で折れ線を生成し，この折れ線に沿ってベンドを生成する．ただし，ベンドは曲げ半径を持つのでパイプ中心は屈曲点 A’およびB’を通らない．Fig.2 の左側は，２つの経由点候補をベンド 2 個のパイプで接続した例を示す．また，施工やパイプの制約によっては曲げ角度が 90 度に限定されたエルボしか使用できない場合がある．
数学的には，パイプの直管の長さ制約が無ければ 90 度のエルボ 2個以下であらゆる位置と方向の経由点候補を接続可能である．Fig.2 の右側は，左側と同じ２つの経由点候補を 90 度のエルボ 2 個のパイプで接続した例を示す．

Fig.2 Left: A piping example between two waypoints with twobends. Right: A piping example in the same waypoints with two90-degree elbows.

数学的には，ベンド 2 個以下または 90 度エルボ 2個以下のパイプであらゆる経由点候補同士を接続可能だが，実際にはベンドの曲げ半径や最大曲げ角度，曲げ部分同士をつなぐ直管部分長さの最小値などの制約条件が存在するため，接続できない場合がある．
また，障害物との干渉のために接続できない場合もある．本
研究では，全経由点候補の局所座標軸方向（6 方向）をそれぞれグラフのノートとし，それら同士を上記のベンド 2 個またはエルボ 2 個以下のパイプで障害物との干渉無しに接続可能かどうかをチェックし，接続可能ならノード間にエッジ（リンク）を生成してそのエッジにパイプのコストを重みとして設定してグラフを生成する．ただし，グラフが無駄に大きくなることを防止するため，エッジ生成候補となるノードは，元ノードの局所座標軸方向に位置するものに限定し，さらに元ノードの位置からユークリッド距離の近いものを優先してエッジ生成していき，またエッジ生成個数には上限を設ける．また，パイプの種類によっては重力流下可能な配管とするため配管経路の途中がＵ字型になる鳥居配管が許されない場合があり，このような条件からもエッジ生成を制約して対応する．ポンプ圧送を想定したパイプなど，鳥居配管は可能だが避けるべき場合には，重力方向への配管長さ成分に対してコストを追加することで対応する．
ノードとエッジによる重み付きグラフ作成が終了すると，始点-終点間を結ぶ最適経路の探索が行われる．
ここで最適経路とは始点から終点までを結ぶエッジの重みを全て足し合わせたものが最小の経路である．本
システムではダイクストラ法を使用して求めている．
重み付きグラフ上の最適経路探索が終了すると，獲得された経路を設計対象空間内の配管経路へ変換する．
以上の処理により，本システムでは最適な 1 本の配管経路の獲得を可能としている．なお，獲得される経路は以下の 5 つの条件をコスト最小化により満たすものとなり，実用性の高い配管経路を得る：
1) パイプ全長が短い．
2) エルボおよびベンドの数が少ない．
3) 障害物や他の配管と干渉しない．
4) パイプラックやサポートを通過する．
5) 鳥居配管を（極力）回避する．

4.2 複数本の経路探索における２つの問題点
配管設計では通常，複数系統の配管が存在する．だが複数本のパイプを前節の方法で 1 本ずつ配置した場合，最終的な経路案が以下の２つの原因によって大きく変化することがある．

(1) 探索順序による配置設計案への影響
配管設計の現場では，一般に高価なパイプ順に経路探索が行われる．材質が等価な場合，径の大きなパイプから探索・配置される．しかし径が同じパイプが複数存在する場合，処理順序に任意性が生じ，順序の違いによって最終的な経路案が大きく変わる．

下のような経路が考えられる．しかし，Fig.4 下図では
パイプ B の経路の影響によって，後に経路探索されるパイプ A が大きく迂回してしまう．経路探索の序盤では設計対象空間内に障害物となるものが少ないため，より多くの最適経路案が存在する．しかし，これらの経路案の中からどれを選ぶかによって，後のパイプ配置結果が大きく変化していることが分かる．
4.3 タッチアンドクロス法による複数同時経路探索

Fig.3 Influence of routing search orderFig.3 は，径の等しい 2 本の配管経路（パイプ A，パイプ B）の経路探索を行う場合に探索順序によって獲得される配管経路が異なる例である．ただし図では分かりやすくするために，2 次元平面内での経路探索を行う．この場合，2 本のパイプの径は等しいため，Fig.3の上のようにパイプ A から探索する場合と，下のようにパイプ B から探索する場合の 2 通りの順序が考えられる．しかし図で示すように，獲得される経路案はパイプの探索順序によって全く違うものになる．

タッチアンドクロス法とは，まず全てのパイプを互いの干渉を無視した最小コスト経路で配置した後，タッチ（配線同士の接触）とクロス（配線同士の交差）という二つの制約違反状態をペナルティ値として表現し，コスト関数にその値を加えて経路探索処理を複数回反復して行いつつ，設定された制約違反コストの値を徐々に上昇させることで，次第に経路同士が干渉していない解を獲得する方法である 1)．反復して行われる経路探索の過程では，複数の経路中から 1 本を選び再度経路を探索し，その経路が設定されると，他の経路を選択し同様の経路探索処理を行う．このように複数本の経路探索過程では，すべての経路を同時に探索するのではなく，経路１本ずつに焦点を当てているので，既存のダイクストラ法を利用した経路探索手法と容易に組み合わせることができる 2,3,4)．
Fig.5 にタッチアンドクロス法による 2 次元平面上での経路探索例を示す．探索序盤では干渉コストが小さいため，全経路は干渉を無視した単純な最短経路となっている．しかし，探索回数が進むにつれて干渉コストが増大し，徐々に経路同士の干渉が少なくなり，最終的に干渉のない妥当な設計案を獲得している．

Fig.5 Process of routing by Touch and Cross method.

4.4 タッチアンドクロス法の初期解生成法の提案
Fig.4 Influence of selection of optimum routing.

タッチアンドクロス法においても初期解の形状がその後に獲得する設計案の形状を大きく支配する要因に(2) 複数解からの選択による配置設計案への影響なっている．本論文では，管同士の干渉を無視して最1 本の配管経路探索では，経路の最適解として複数小コスト経路をすべて列挙し，それらの重なり具合をの解が存在する場合がある．このとき最適な経路候補調べてタッチアンドクロス法の初期解として有望な経の中から，どの経路を選択するかによって，最終的に路を生成することで，安定した良質の配管経路を獲得得られる配置が大きく変わってしまう場合がある．
する方法を提案する．Fig.6 は提案手法の考え方を簡単
Fig.4 では径の大きなパイプB と径の小さなパイプ Aな例で示したものである。Fig.6 左側は，パイプＡとパの経路探索を 2 次元平面で行う場合を示す．ここで，イプＢの全ての最適経路を半透明で表示し重ね合わせ
パイプ B の最適な経路候補としては図中の上の経路と，たもので，色の濃淡を観察することにより経路として回避しやすい箇所とそうでない箇所が分かる．同一パイプで多数の最適経路が重なる場所は濃い色で示されるので，他のパイプはこのような箇所を極力避けるべきである．Fig.6 右側では，互いに重なり度合いが最小な経路を選択した結果を示す．

重みの値は，更新のたびに w[i]  1ni 1となるよう正規化する．ここで interferedVolRate[i] は，干渉している体積が大きい経路ほど大きな値となるが，最大値は 2，最小値は 1 となるよう干渉度合いを非線形変換したもので，これで重み w[i] を除することにより，干渉している経路としていない経路の重み w の相対的な大きさが更新の回数に対して指数関数的に変化し収束していくことが期待される．
5シミュレーション実験

5.1 タッチアンドクロス法の初期解生成法の検証
Fig.6 A basic concept of the proposed method.

しかし、単に各経路で他のパイプの経路との重なり度合いが小さい経路を選ぶだけでは，異なるパイプ同士が互いを避ける解が存在するにもかかわらず，互いに同じ方向に回避して結局干渉を起こす事例が予備実験で観察された．そこで，パイプ毎の各経路に重みを付加し，（他パイプ経路との重なり度合い）×（他パイプ経路の重み）の値から各経路の重みを更新していく方法を提案する．以下に重み更新方法を説明する：
ある１本のパイプには n 個の最適経路が存在し，その中の i 番目の最適経路が持つ重みを w[i]と表す．i 番目の最適経路が，他パイプの経路と干渉している部分の体積に，その相手の経路が有する重み w を乗じた値を全ての他パイプの全ての最適経路について合計した値
を InterferedVol [i]と表し w[i] を以下のように更新：

4.1 節で提案した初期解生成方法で妥当な解候補を獲得できるかどうかを検証するため，立方体を 3x3x3のグリッドに分割した空間で立方体の対角線をクロスするように設定した２本の配管A, Bの経路を探索する．
管 A は座標(1,1,1)→(3,3,3)を結び，管 B は(1,1,3)→(3,3,1)を結ぶ．Fig.7 左側は，重み更新を 4050 回繰り返した時点で重みが最大の経路を 3D 表示したものである．Fig.8 は管 A（Fig.7 黒色）の経路全ての重みの割合の更新による変化を示す．経路の重みは最初全て同じ値からスタートし，更新 150 回程度でほぼ安定した状態のまま重みの値の比率はほとんど変わらな
いが，4050 回あたりで突然急激な変化を起こし，それ以降は数万回の更新を行った範囲内では変化は起きなかった．Fig.7 右側は，4050 回以降で重みが最大になった経路を示す．

totalInterferedVol  i 1 intererferedVol[i ]ninterferedVolRate[i ]  1.0 w[i ] intererferedVol[i ]totalInterferedVolw[i ]interferedVolRate[i ]Fig.7 Largest weighted paths.

Fig.8 Variation of the proportion of the weight variables of paths in the pipe A.

更新 4050 回以前の安定した状況では，とにかく他のパイプの経路と重なっている体積が少ない経路の重みが大きくなる傾向がみられるが，4050 回以降では重みの大きい他パイプの経路を避ける経路の重みが大きくなる傾向があった．しかし，それぞれのパイプで重み最大の経路を選択した場合，更新 4050 回を超えた後の経路同士では互いに干渉するケースが見られたのに対し，4050 回より前の時点での経路のほうが干渉を避けている場合が多かった．よって，本手法はあまりじっくり時間をかけて収束させないで，収束の途中で打ち切った時点で最大の重みを持つ経路を選択するような使い方が良いと考えられる．
Fig.10 Candidates of waypoints for the φ150 pipe.

5.2 天井および壁へのサポートを考慮した自動設計（１）実 験 設 定
幅 1500 奥行き 4000 高さ 2000 の通路状の空間内部にφ200 のパイプ 2 本，φ150 のパイプ 1 本，φ100 のパイプ 1 本を天井に並んだ状態から片側の壁に沿って並んだ状態へと配置する設計案の自動生成を試みる．ただし天井から 100 および 400 の水平位置 2 段のパイプサポートと，片方の壁側より 100 および 400 の垂直方
向に 2 段のパイプサポートが奥行き方向に 500 間隔で設置と想定し，各径のパイプ探索においてはこのパイプサポートの利用を想定して経由候補点を生成する．
また，サポートの反対側の壁際より幅 800 床より高さ
1300 奥行き 4000 の直方体の領域を仮想的な通路空間として設定し，ここへのパイプ干渉を禁止した．
また，全てのパイプは障害物またはパイプ同士の干渉判定において 30 以上の距離をクリアランスとして確保することを制約とした．
Fig.9,10,11 はそれぞれφ200,φ150,φ100 のパイプが経路探索の際に用いる経由候補点の位置と障害物の配置を表す．半透明の赤みがかったグレーの直方体は通路空間，全体を覆う半透明のグレーの平面は壁面や天井を構成する構造部材を示す．天井部分に 2 段，図の左側面部分に 2 段のパイプサポートを想定しているため，パイプの経由候補点もそのサポートの設置位置と対象とするパイプの径に合わせて位置が調整されている．φ200 のパイプでは 16×7=112 個，φ150 のパイプも 16×7=112 個，φ100 のパイプでは 30×7=210個の経由候補点を用いている．
またほぼ同様な設定だが通路が L 字状に折れ曲がった空間に対しても配管自動設計を試みた．

Fig.11 Candidates of waypoints for φ100 pipes.

φ200 のベンド半径は 400 または 300，φ150 のベンド半径は 300 または 150，φ100 のベンド半径は 200または 100 のどちらかを選択できるものとした．
また，ベンド部分同士をつなぐ直管部分は，どの径でも長さ100 以上を条件としている．ベンド角度は 90 度を最大角度としている．パイプの単位長さあたりのコストはφ200 では 40，φ150 では 22.5，φ100 では 10，ベンド一か所あたりのコストは径や角度によらず一律1000 とした．
（２）実 験 結 果
Table 1 に通常のタッチアンドクロス法で経路探索を行った場合と提案手法で初期化してからタッチアンドクロス法を適用した場合の 20 試行中で干渉を完全に回避できた回数の比較を示す．
Fig.12 はベンドを用いた場合の提案手法で得た配管設計案の失敗例を示す．Fig.13 は任意角度のベンドを用いず，全て 90 度のエルボを用いた場合の自動計算結果である．エルボの曲げ半径やコストの設定はベンドの場合と同じである．
Table 1 Success rate comparison.

提案初期

直線通路

直線通路

角通路

ベンド接続

90°エルボベンド接続

90°エルボ

2／20

14／20

0／20

0／20

0／20

19／20

20/20

0／20

角通路

化無し
提案初期

Fig.9 Candidates of waypoints for φ200 pipes.

化ありFig.16 Overlapped shortest paths using bends.

Fig.12 A result using bends (failed).

Fig.17 Overlapped paths using 90 degree elbows.
6Fig.13 A result using 90 degree elbows.

Fig.16 および 17 は干渉を無視して全パイプの最適経路を重ね合わせた図である．本実験では探索の成功率と最適経路のパターン数には関係が見られなかった．
提案手法は，異なる系統のパイプ同士の干渉を避ける経路を得る目的で，全ての最適経路を重ね合わせた図形を使用したが，逆に分岐を含む同一系統の配管経路の経路探索に利用することもできる．水道やエアダクトなど，始点が同じで複数の異なる終点を持つ分岐配管は，始点と各終点を結ぶ経路長を短く，かつ全体の管長を最短にするよう分岐の位置を決めなければならない．この場合，始点から各終点への最短経路を全て重ね合わせ，互いに重なり度合いが最大の経路を選ぶことで目的の形状を得ることが期待できる．分岐を含んだパイプが複数系統存在する場合の，妥当な自動設計処理手順の確立については今後の課題である．

謝Fig.14 A result using bends.

考 察辞本研究は H28 年度 JST マッチングプランナープログ
ラム「企業ニーズ解決試験」課題番号 MP28116808445
より補助を受けて実施された．ここに謝意を表す．

参考文献
1) 松岡 英俊，
新田 泉：大規模配線システム：GRP, FUJITSU,
50, 6, pp.372 - 377, 1999.
2) 安藤 悠人，木村 元：自動経路探索システムにおける複数本配管への対応，日本船舶海洋工学会論文集，第 20 号,
pp.221-230, 2014.
3) 木村 元：パイプサポートや曲がり船殻に対応した配管自動設計に関する研究，日本船舶海洋工学会講演会論文集
Vol.22, pp.371--376，2016.
4) 木村 元，慶田 航, 佐多 広海：Voxel 図形の塗り潰しと細線化による配管自動設計に関する研究，日本船舶海洋工学会講演会論文集 Vol.22, pp.377--381，2016.

Fig.15 A result using 90 degree elbows (failed).