機器配置の自動化手法の開発

2020年1月14日作成、1月31日、2月1日、4月30日、2021年3月13日変更
三木設計 三木秀樹

1 設備設計の自動化

設備モデルの設計は、主に下記の作業から構成される。
負荷計算
システム選定
流量計算
機器(容量、台数)選定
機器配置
経路配置
経路(サイズ)選定
これらの中で、機器配置と経路配置だけは、作業の処理方法(アルゴリズム)が明確になっていない。すなわち、機器配置と経路配置の処理方法が明確になれば、設計を自動化する基盤が整う。
すでに、経路配置に関しては、経路長さや曲がり数などの簡単な評価項目のもとで、障害物を避けて経路を自動的に生成する手法を試行した。評価項目を増やすことにより、実用化も可能と考える。
そのため、機器配置に関しても、以下に試行する。

2 機器配置の自動化手法

2.1 ポリオミノ

機器配置は、限られた領域内に一定の大きさを持つ機器を複数配置する問題である。機器配置の評価手法はひとまず置き、まずは配置できるか否かの計算手法を検討する。
題材として、いくつかの正方形を組み合わせた部材をセルの中に隙間なく配置するゲームであるポリオミノ(Poly-omino) を考える。このゲームは昔から市販されているため、想像が容易と思われる。例を写真1に示す。
写真1 ポリオミノの例
写真1の例におけるセルの巾と奥行は、セルおよび部材を構成する正方形を基準として、それぞれ8個分、部材数と大きさは、全部材のうち12個が5個分、残り1個が4個分である。
計算にはマイクロソフト社のExcel 2020を用いる。写真1の例におけるセルと部材をExcelのシートに表現したものを図1に示す。
図1 ポリオミノのExcelでの表現

2.2 部材の特性

写真1の例における部材の名称、形状、座標(部材座標)および線対称・点対称の区分などを表1に示す。
部材の名称は便宜的なものである。
部材の定義に用いる座標系は部材の左下を原点(1,1)とし、右方向をx、上方向をyとする。
部材は90度単位の回転および反転ができる。すなわち、部材の見かけの形状は8通りになる。ただし、部材が線対称または点対称である場合、8通りの中に同一の形状が含まれる。
表1 部材の一覧
No. 名称 形状 座標 対称 No. 名称 形状 座標 対称
1 I (1,1)
(2,1)
(3,1)
(4.1)
(5,1)
線2
点1
2 L (1,1)
(1,2)
(2,1)
(3,1)
(4.1)
 
3 Y (1,1)
(2,1)
(2,2)
(3,1)
(4.1)
  4 N (1,1)
(2,1)
(3,1)
(3,2)
(4.2)
 
5 V (1,1)
(1,2)
(1,3)
(2,1)
(3,1)
線1 6 T (1,1)
(2,1)
(2,2)
(2,3)
(3,1)
線1
7 X (1,2)
(2,1)
(2,2)
(2,3)
(3,2)
線2
点3
8 Z (1,1)
(1,2)
(2,2)
(3,2)
(3,3)
点1
9 W (1,1)
(2,1)
(2,2)
(3,2)
(3,3)
  10 F (1,1)
(1,2)
(2,2)
(2,3)
(3,2)
 
11 U (1,1)
(1,2)
(2,1)
(3,1)
(3,2)
線1 12 P (1,1)
(1,2)
(2,1)
(2,2)
(3,1)
 
13 O (1,1)
(1,2)
(2,1)
(2,2)
線2
点3
         
計算の前処理として、部材に対して下記をおこなう。
基点の調整
90度単位の回転および反転
回転および反転による同一形状の削除
すなわち、部材を定義する場合は、座標の基点、回転方向などを考慮することなく、1形状のみを定義すれば良い。

2.3 配置の計算方法

配置の計算に用いる座標系は部材と同じく、セルの左下を原点(1,1)とし、右方向をx、上方向をyとする。Excelのシートに表示する時には、y方向は上下が逆になる。
配置の計算は部材およびその回転、反転、位置の条件を総当たりでおこなう。写真1の例おける部材数は13、回転は最大4通り、反転は最大2通り、位置xは最大8通り、位置yは最大8通りである。総当たりのイメージを図2に示す。
図2 計算のイメージ
個々のセルには部材同士の干渉を判別するためのフラグを設定する。例えば、部材を配置したセルのフラグをTrue、それ以外はFalseとする。
まず、部材1を回転・反転・位置x・位置yの値に初期値を与えて、セルに配置する。部材1を配置する時には、他の部材は存在しないため、干渉によって部材を配置できないことはない。ただし、部材の一部がセル外へ出る場合には、位置x・位置yを進める。部材を配置できた時には、回転・反転・位置x・位置yの値を保管し、配置したセルのフラグを設定する。
続いて、部材2も同様に配置するが、すでに部材1が存在するため、干渉が生じて配置できないことがある。部材を配置できない時には、部材の回転・反転・位置x・位置yの条件を進めて、計算を続ける。部材を配置できた時には、以下同様に残りの部材を配置する。
最後まで部材を配置できた時には、一つの解を求められる。解のイメージを図3に示す。
図3 解のイメージ
最後まで部材を配置できた時には、一つ前の部材に遡り、その時の条件を進めて、計算を続ける。
部材を配置できなかった時には、部材の回転・反転・位置x・位置yの条件を進めて計算するが、全ての条件においても部材を配置できないことがある。この時、一つ前の部材に遡り、その時の条件を進めて計算を続ける。
一つ前の部材に遡り、その時の条件を進めて計算を続けても、部材を配置できない時には、さらに一つ前の部材に遡る。これを続けることにより、全ての部材における全ての条件を総当たりで計算することができる。解法のフローを図4に示す。
図4 解法のフロー
以上の解法を模式的に図5に示す。探索木と言われるものである。
図5 探索のイメージ
全ての部材における全ての条件を総当たりで計算した時に、計算を終了する。

3 機器配置の計算

3.1 計算画面

計算画面を図6に示す。
図6 計算画面
図6におけるボタン列の上部は計算条件、下部は計算結果を示す。計算条件として領域の寸法(Cell x、Cell y)、部材数(Parts)、計算時間の上限(Calc sec max)などを設定し、計算実行ボタン(Calc)を押すと、計算が実行される。計算結果として、計算時間(Calc sec.)、解数(Sol no.)、計算中の部材番号(Parts no.)などが表示される。なお、解数は途中解を含む。
全ての部材における全ての条件を総当たりで計算するため、計算の量は多大になる。そのため、計算時間の上限を設定し、設定した時間を超過した場合には、計算を終了できるようにしている。また、計算を終了する時には、計算結果を保存し、次は保存時の条件から計算を継続できるようにしている。

3.2 計算結果

計算結果の例を図7に示す。
図7 計算画面
図7では、60秒の計算で7個の部材(I、L、Y、N、V、T、X)が配置され、8個目の部材(Z)が計算中である。
しかし、この例では8個目の部材(Z)を配置できない。すると、7個目の部材(X)を配置し直して、再度8個目の部材が計算される。しかし、それでも8個目の部材(Z)を配置できない。すると、6個目の部材(T) を配置し直して、再度7個目以降の部材が計算される。
また、この例では左下隅に死領域すなわち、周囲を境界または部材に囲まれ、部材を配置できる広さがない空きセルが存在する。そのため、4個目の部材(N)を配置し直すまで、部材を配置できる可能性がないが、計算は続く。
そのため、計算の時間が多大になる。

3.3 問題点

死領域を判別できれば、このような計算を回避でき、計算の時間を短縮できる。探索において可能性のない条件を適宜排除するという基本的な考え方である。個々のセルには部材同士の干渉を判別するためのフラグを設定しているため、これらを用いて空きセルの周囲に部材があるかどうかを判別できる。
図7でも、図8に示すような一つの空きセルを死領域として判別していた。しかし、図9に示すような二つ以上連続した空きセルも死領域として判別しなければ不十分と考えられる。
図8 死領域 図9 死領域

3.4 問題点の改善

二つ以上連続した空きセルを死領域として判別するには、まず、二つ以上連続した空きセルを抽出する必要がある。
例えば一つのセルの周囲から順に、空きセルを探し、見つかればリストに加え、次に、リストから空きセルを取り出し、周囲の空きセルを探し、見つければリストに加える。以下同様に、空きセルを探し、空きセルを見つけられなければ、終了する。空きセルを抽出するフローを図10に示す。
図10 解法のフロー
二つ以上連続した空きセルを抽出した後、死領域であるかどうかを判別する必要がある。
死領域には、部材を置けない場合だけではなく、部材を置けても残り部分が死領域になる場合も含まれる。
仮に全ての部材が同じ大きさであれば、部材を組み合わせて求められる大きさは、一部材の大きさの倍数であるため、死領域の大きさを一部材の大きさで除して、余りがあれば死領域と判別できる。
しかし、写真1の例における部材数と大きさは、全部材のうち12個が5個分、残り1個が4個分であるため、これらの部材を組み合わせて求められる大きさ、すなわち4、5、9、14・・のような数を求める必要がある。このような数を求めるフローを図11に示す。
図11 解法のフロー
以上により、二つ以上連続した空きセルを死領域として判別できる。

3.5 再計算結果

二つ以上連続した空きセルを死領域として判別するように改善した計算結果の例を図12に示す。
図12 計算画面
図12では、60秒の計算で6個の部材(I、L、Y、N、V、T)が配置され、7個目の部材(X)が計算中である。
部材は死領域を作らないように配置されている。
右上隅に7個目の部材を配置できる大きさの空きセルがあるが、どの空きセルが使われても死領域ができるため配置できない。そのため、以降の計算は打ち切られ、6個目の部材を配置し直す。
しかし、部材(L)と部材(Y)の間に三つの空きセルがあるが、この空きセルを埋められる部材は既にない。そのため、部材(Y)を配置し直すまで、部材を配置できる可能性がないが、計算は続く。すなわち、死領域の大きさを判別するだけでは、なお不十分である。
さらに計算を続けた時の、計算結果の例を図13に示す。
図13 計算画面
図13では、全ての部材が配置されて、1個の解が求められ、解数(Sol no.)が一つ増えて「2」が表示されている。
図13における最終の13番目の部材(O)と直前の12番目の部材(P)を入れ替えることにより、別の解が求まる。このような例は頻繁に生じる。ただし、13番目の部材と12番目の部材の場合を除き、計算の途中で部材を入れ替えることは、計算の条件の順序を乱すため、妥当ではない。
さらに計算を続けた時の、計算結果の例を図14に示す。
図14 計算画面
図14では、10時間の計算で8個の解が求められている。死領域を判別する方法を改善しても、計算時間が短いとは言えない。
図14で示される8個の解を図15に示す。
図15 計算結果
求められた解は計算画面における前進表示ボタン(Forward)または後進表示ボタン(Backward)を押すことにより順次表示される。

4 考察

4.1 計算時間
写真1に示すゲームの解数は、メーカーによると対称となるものを除いて65通りである。図14では、1個の解を求めるために平均で1時間以上を要している。65通りの全てを計算するには、相当の日数を要すると想定され、さらなる計算時間の短縮が望まれる。
短縮方法として、例えば、死領域を判別する方法を、大きさではなく形状でおこなうことが考えられる。図4に示すフローを再帰的に利用することにより可能と考えられる。
また、計算の進捗を確認するために1秒ごとに部材を表示しているが、確認が不要になれば、表示を停止または削減することも考えられる。

4.2 計算終了条件
終了条件は全ての組合せを計算した時である。しかし、相当の計算時間を必要とするため、未だ途中までしか計算できていない。

4.3 部材の定義方法
現状の部材の定義データを図15に示す。
図16 部材定義
「name」列には部材の名称を定義する。部材の名称は計算画面における部材の表示に使用する。
「element」列には部材を構成する正方形の数を定義する。
「rotation」列および「mirror」列には部材を回転および反転させるかどうかを定義する。現状は、全ての部材を回転および反転するように定義しているが、実際の機器において、例えば、反転ができないことがある。そのため、反転を禁止することができる。
「x」列および「y」列には部材を構成する正方形の座標を定義する。
「image」列には定義データから計算した部材の形状を参考として記載している。本来は形状から「element」「x」「y」を自動生成することが望ましい。

4.4 領域の面積と部材の面積
写真1に示すゲームでは、領域の面積と部材の面積は一致する必要がある。そのため、両者が一致しない場合には計算をおこなわない。
しかし、実際の機器配置では、通常、領域の面積と部材の面積は一致しない。そのため、面積が一致しない場合の計算方法を検討する必要がある。例えば、領域の面積が大きい場合には、空きセルの領域を指定するか(現状でも障害物を配置することで可能)、空きセルが連続するような条件を与えることが考えられる。

4.5 三次元化
写真1に示すゲームでは、二次元の扱いで足りるが、実際の機器配置では三次元の扱いが必要になる。三次元への拡張は可能であり、また必須である。
三次元化の際に、合わせてVRML化をおこなう。
機器によっては、床置き、天井吊りなどの条件を付加する必要がある。

4.6 計算結果の評価
写真1のゲームにおける解の総数は、対称となるものを除くと65通りである。ゲームとして見れば評価基準はないため、解に優劣は生じない。しかし、機器配置として見れば、例えば下記のような項目は評価基準となり、解に優劣が生じる。
空調系機器と衛生系機器、同形の機器、あるいは主機と補機のように、特定の複数の機器間の距離が短いこと(グループ化)
大型の機器と搬入口の距離が短いこと
維持管理の動線が短いこと
複数の評価基準を総合的に判別するには、個々の評価基準に重み付けを与えればよい。より多くの評価基準を与えることが望ましい。

4.7 維持管理領域
機器の周囲には維持管理領域が必要である。維持管理領域を含めて部材の大きさを定義することも考えられるが、隣り合う機器の維持管理領域は重なってもよいため、本来は別途定義する必要がある。

4.8 計算の正しさ
複数(500以上)の解を求められることを確認できたが、全ての解を求められるかどうかは未だ確認できていない。しかし、現状では全ての解を求めるためには、相当の計算時間が必要である。計算時間を短縮することは本試行の主旨ではないが、改善が望まれる。

4.9 計算のアルゴリズム
人が機械室へ機器を配置する場合には、本計算のように総当たりの配置をおこなうことはおそらくない。その理由は、機械室の面積が機器の面積の合計より比較的大きいため、厳密に検討しなくても配置が可能であること、同時に必ずしも最適な解を必要としていないこと、人の頭の中に何らかの評価基準があって、妥当でない解を早期に排除していること、などが考えられる。このような理由を明確にルール化できれば、計算時間の短縮に寄与する。

以上