平成13年度〔2001〕№46
宮崎県工業技術センター・宮崎県食品開発センター研究報告

動的計画法を用いた板金構造物の展開図作成手法＊
外山

眞也＊１

Dynamic Programming for Generating of a Sheet Metal Development
Masaya TOYAMA
本研究は、板金構造物の多種多様な展開図を作成する手法について報告するものである、手法として与えられた二つの断面を点群で近似表現しなおし、目的関数として二つの断面の点間距離の総和と結線によって生成された側面の法線ベクトルの角度変化の滑らかさを評価した。この評価関数の実用性を検証するた
めに遺伝的アルゴリズムを用いた手法を開発し、評価関数の有用性を示すことができた。また、分枝限定法等を用いた手法の開発を行い、より良い手法の検討を実施した。
本研究では、分枝限定法における暫定値、下界値の計算に動的計画法を用いることにより最適解を得る方法について検討し、計算量を減少させることができたので報告する。
キーワード：動的計画法、板金展開図、最適化問題、CAD
１ はじめに流体や気体の流れの方向を制御するダクトや配によりその展開図を求めることができる。そして平板形状のものを折り曲げ加工した板金を組み合管の形状は多種多様であり、現状のCADシステ
q２

ムでは対応できず、現場では経験やカンに頼ってq１

Upsideqn作業を行うことが多いのが現状である。そこで、

q３qj

展開図作成のための結線を最適化問題として定式化し、上面・下面の二つの断面形状を与えさえす

pm

れば、断面間の結線と構造物側面の最適な形状の生成を自動的に行い、その構造物における展開図p１を生成する手法を研究してきた。

p２

本研究では、分枝限定法における暫定値、下界Downside

pi値の計算に動的計画法を用いることにより最適解
図１を得る方法について検討し、計算量を減少させる結線の例ことができたので報告する。
表１２ 開発方法
流体の流れを制御するダクト等の板金構造物には、必ず流体の入口と出口がある。このような板金構造物に関しては、その入口と出口をつなぐ側面を三角形平板で構成し直し、平面に広げること＊＊１123…

j…

n1110000020010000

対象とする問題

板金展開図自動設計CADの研究（第２報）
機械電子・デザイン部

Points of Exit

２−１

結線状態の行列表現例
Points of Entrance

30011000…

00０…

000i0001

100…

00001…

1m100000165動的計画法を用いた板金構造物の展開図作成手法

わせて、結線部を溶接して板金構造物を製作してを０−１で表現している。なお、△（pi−１, pi , qj）

いる。と△（pi , pi＋１, qj）、及び▽（pi , qj , qj−１）と▽（pi

そこで、その入口と出口の各形状を点群で直線, qj＋１, qj）の組合せの場合には、各断面形状の隣近似された形状として定義し、その二つの形状間接する三点は一直線上にはないので、 対応するを結ぶ側面三角形平板を生成することを考える。

a△△, i, j及びa▽▽, i, jは常に図１に対象とする形状例を示す。下部断面形状を

以下では、a△△, i, j 及びa▽▽, i, j の表記を用いず、そ表現するm個の点をpi（i＝1, …, m）, 上部断面形の代わり、数値状を表現するn個の点をq（j＝1,…, n）としたとj▽（pi , qj＋１, qj）の面積S▽, i, jを要素とする定数行

き、結線する線の数は、m＋n個となり、結線状列S▽＝（S▽, i, j）及び△（pi , pi＋１, qj）の面積S△, i, j

態は表１の行列X＝（xi, j）で表現できる。この表を要素とする定数行列S△＝（S△, i, j）を作成する。

は、上部断面形状の点群を行、下部断面形状の点また、三角形▽（pi , qj＋１, qj）の単位法線ベクト群を列方向に並べ、その対応する２点を結線する

ルn▽i, jのXY平面上での方向角度θ▽, i, jを求め、注場合は行列要素が目している側面の両側に隣接する二つの側面の方1となっている。そして、11である。このため、を用いる。そして、三角形一方の断面形状の点のうちの１点と、もう一方の向角度の平均値とθ▽, i, j の偏差を断面形状の点のうちの隣り合う２点との都合３点求めている。

で一つの三角形平板が定義され、側面は全部でここで、XY平面は、下部形状を表現する点群のm＋n個の三角形平板によって生成されることに重心を原点とし、原点と上部形状を表現する点群なる。また、各結線は隣り合う二つの三角形平板の重心を結ぶ線分がZ軸上となるようにしたの辺として共有される線分となるため。生成されX-Y-Z三次元直交座標系のXY平面である。

θ▽, i, j としてθ△, i, jも同様にして求められる。

る結線の数は三角形平板の数と同じくm＋nとな

この板金構造物の展開図の結線決定問題を、結る。ただし、隣接する二つの三角形平板が同一平線の長さの総和flと、側面構成要素の単位法線ベ面上にある場合は、一つの四角形として展開図をクトルを用いて側面の方向変化の滑らかさを評価作成する。

する関数fv を用いて、 結線状態を表す行列X＝２−２（xi, j）の各要素の値を決定する０−１計画問題と問題の定式化

展開図作成において、曲げ加工線の長さは短いほど（曲げ加工部の面積は小さく）、加工の点で好ましい。また、側面の形状において急激な凹凸の変化は少ないほうが良い、そこで、展開図の結線決定問題をこの二つの規準を用いた最適化問題として定式化する。まず一つの規準は結線長さの総和の評価であり。もう一つの規準は生成された側面の法線ベクトルによる方向変化の滑らかさの評価である。
下部と上部の形状を表現する点において、各点pi qj間の距離li, jを求めた行列L＝（l i, j）、０−１定数行列A△▽＝（a△▽, i, j）, A▽△＝（a▽△, i, j）を作成する。
ここで、a△▽, i, jは隣接する三角形△（pi−１, pi , qj）,▽（pi , qj＋１, qj ）の単位法線ベクトルが一致するとき0、そうでないとき1となる０−１定数である。同様に、a▽△, i, j は▽（pi , qj , qj−１）と△（pi , pi＋１, qj）の二つの隣接する三角形において、単位法線ベクトルが一致しているかどうか66して、以下のように定式化する。

動的計画法を用いた板金構造物の展開図作成手法

ここで、S▽, i, jは▽（pi , qj＋１, qj），S△, i, jは△（pi ,pi＋１ , qj ） の 面 積 で あ る。 一 方 、

θ△, i, j 及 びθ▽, i, jは、各々△（pi , pi＋１, qj）及び▽（pi , qj＋１,qj）の単位法線ベクトルによる方向角度と、そのここで、n△i, j，n▽i, jはそれぞれ△（pi , pi＋１, qj）

両側に隣接する三角形側面の単位法線ベクトルに及び▽（pi , qj＋１, qj）の単位法線ベクトルである。

よる方向角度との偏差である。XY平面における目的関数の第一項flは結線長さの総和を、第二方向角度θ▽, i, j は▽（pi , qj＋１ , qj ）の単位法線ベ

項fvは側面構成要素の単位法線ベクトルを用いて

クトルn▽i, j のX成分（n▽i, j, X）、Y成分（n▽i, j, Y ）を側面の方向変化の滑らかさを評価するものである。

用いて（24）式で求められる。なお、Z成分の変化０， ０ は正または０であり、問題例を与える段階で決定される目的関数の各項の加重である。
ここで、側面を構成する三角形の中に、同一平は無視できるものとしている。
同様に、△（pi , pi＋１ , qj ）の単位法線ベクトルn△i, jを用いて、θ△, i, jは次式で求められる。

面にあるような隣接する三角形が一組でもある場

側面を構成する三角形において、隣接する三角合には、その二つの三角形の境界線は加工線とは形が同一平面に一組も無い通常の場合は、例えばならず四角形の側面上の対角線となるため、flに△（pi , pi＋１, qj）において、左右に隣接する三角その長さを含まないように定式化している。そこ

形は各々二通りあり得るので、で、目的関数の第一項flを、上下二つの断面形状際の場合の数は４となる。一方、隣接する三角形における各節点間の距離li, j と結線状態を示したが同一平面内に存在する場合は、その二つの三角，行列Xの要素xi, j及び０−１定数行列A△▽＝（a△▽, i, j）

形で形成される四角形を一つの面としてA▽△＝（a▽△, i, j）の各要素を用いて定式化している。

を求める必要がある。隣接する三角形が同一平面

この定式化により、例えば線pi pi＋１ と線qj−１ qj が内にある場合を含めると、平行であるとき、この二つの側面三角形は一つの際の場合の数は16となる。このすべての場合を考四角形平面として取り扱い、境界となっている結慮して線部分の長さli, j を結線長さの総和の計算に含めている。このようにして、ないようにできる。また、２点pi , qjが結線され（X）は、結線状態を表す行列X＝（xi, j）の各要素た場合に、隣接する二つの三角形の組み合わせは、を変数とする関数として表現できる。

△△、△▽、▽△、▽▽の４通りあるが、そのす次に制約条件について述べる。

べての場合に対応できる。

θ△, i,（X）、 同様にj

制約条件、目的関数の第二項fvは、側面構成要素の単位法･･･及び

θ△, i, jを求める

θ△, i, j

θ△, i,（X）を求めるjθ▽, i,（X）を求めj
θ△, i,（X）、jθ▽, i, j

式は結線数の式は結線で側面が形成されるための条件である。

････

･

線ベクトルのXY平面上への射影のX軸からの方式を満たすことにより側面は上下断面形状のど向角度θを求め、それとその側面構成要素の両側ちらか一方の一点と他方の隣り合う２点との三点に隣接する二つの側面構成要素における単位法線で決定される三角形で構成される。

ベクトルのXY平面上への射影のX軸からの方向角度の平均値との偏差｜･及び式は結線状態の制約条件である。

θ｜により評価していまたγ△i, j, i', j'は、三角形側面が交差しないためのる。各三角形側面に対し、単位法線ベクトルが定制約条件で、下断面形状の一辺を底辺とする三角まる。そこで、この単位法線ベクトルが隣接する形側面に、上下の断面間を結線する線分が貫通す側面間でなめらかに変化するかどうかを評価するるのかを判定した０−１定数である。線分pi pi＋１以下の関数 fvを目的関数に加え、外観を考慮してを底辺とする△（pi , pi＋１, qj ）と線分pi' qj'が交差最適な結線状態を求めるようにした。三角形側面した場合には側面を展開できない。このとき、線の面積が大きい程、外観への影響が大きいという分pi' qj'を含む直線が△（pi , pi＋１, qj ）を含む平面判断から、三角形側面の面積を加重として用いてと交差する点rは△（pi , pi＋１, qj）内に存在し、をいる。

満たす。このときγ△i, j, i', j'＝１とした。このよう
67

動的計画法を用いた板金構造物の展開図作成手法にして〜式の条件を満たせば展開図作成に必

また、側面の平滑性の評価関数fvにおいては、要な結線状態が得られる。

xi, j xi＋１, j ＝ １ の と きxi, j xi, j＋１ ＝ ０ とな る の で 、２−３Δθ▽, i, j ＝０となる。同様に、xi, j xi, j＋１ ＝１のと動的計画法の適用

展開図作成に必要なすべての結線を決定する過きΔθ△, i, j＝０となる。いま、xi, j xi＋１, j＝１の場合

程は、各一つの結線を決定する素過程に分解できを考えると、（xi−１, j−１xi, j−１＝１, xi, j−２xi, j−１＝１,る。また、各決定の評価値は、a）一つの結線のxi−１, j−１xi−１, j＝１, xi−２, j xi−１, j＝１）の内のいずれ長さと、b）一つの三角形（または四角形）側面か一つと（xi＋１, j＋１xi＋２, j＋１＝１, xi＋１, j＋１xi＋１, j＋２＝の法線ベクトルとその両側に隣接する二つの三角

１, xi＋２, j xi＋２, j＋１＝１, xi＋２, j xi＋３, j＝１）の内のい形（または四角形）の法線ベクトルを元に計算でずれか一つとの組合せの16通りが有り得る。しかきる。この計算において、xi, j＝１のとき、xi−１, j＝し、一つの断面を点群で近似するとき、直線はそ

xi＋１, j＝ 1、またはxi−１, j＝xi, j＋１＝ 1、またはxi, j−１＝の両端点を、円弧の場合は指定された分割数によ

xi＋１, j x ＝１、またはxi, j−１＝xi, j＋１＝１となる。こる分割点を用いた点群を使用するので、一つの断の四つの場合は結線する点を、下断面形状の点を面形状において隣接する三点は一直線状に存在す

左から順番に、次に、上断面形状の点を左から順ることはないので、図２のa）の場合で示す組み番に並べることで、各々（i-1, i, i＋1, j, j, j）、（i−合わせの数は６通りである。そして、図２のa）1, i, i, j, j, j＋1）、（i, i, i＋1, j−1, j, j）、（i, i, i, j−及びb）で示す組合せの数は12通りとなる。この11, j, j＋1）となり６次元空間の超格子点として表2通りの場合は、結線する点を下断面形状の点を現できる（図２参照）。

左から順番に、次に、上断面形状の点を左から順

図２68

結線のシステム状態の例

動的計画法を用いた板金構造物の展開図作成手法

番に並べることで、12次元空間の超格子点として作成される。

表現できる。xi, j xi, j＋１＝１の場合にも、同様に12次元空間の超格子点として表現できる。

各最短経路問題では、地点（システムの状態）iから直接到達できる地点の集合をN（i）で示すと、そして、結線の順番を上断面形状から下断面形状を見て反時計回りとすると、一番最初から一番地点iから最終地点までの距離（評価値）の総和の最小値は、最後までの結線順番を決めることができる。この一番最後の結線を「決定」とみなし、12次元空間の超格子点を「システムの状態」とみなす。決定によるシステムの状態変化は、超格子点のベクトル表示において、下断面形状の点に相当する要素と表せる。 ここで、 ti, j は地点jからiまでの距離の部分で、最初の結線に相当する要素を削除して、（評価値）を示す。下断面形状の点数m、上断面その他を一つ左にずらし、最後に新たな結線に相形状の点数nの時、結線行列Xにおいて、当する要素を書き、同様な処理を上断面形状の点なる要素の個数はm＋nとなる。そして、m×n個に相当する要素の部分で行うことで実現する。その行列要素において、超格子点で表現できるすべ

して、決定の評価値は、結線の長さの総和flにおけてのシステムの状態を作成し、状態番号を割り当る該当する一つの項と側面の平滑性の評価関数fvて、各状態から状態変化できる状態番号を求める。

における該当する一つの項を、各々 ，（≧０）をそして、最短経路問題の動的計画法による解法［1］

加重として、加重和することで計算できる。

を用いて、各最短経路問題について、最終状態か上記のシステム状態は有限個である。そこで、

1とら始めて各状態での最適決定を初期状態まで順次求めていき、今度は初期状態から順に各状態での各超格子点に状態番号を与えることができる。
〜

最適決定をたどることにより最適解が得られる。

式とした最適化問題は、次のような部分問題に

上記最短経路問題の解法では、二つの断面形状分解できる。部分問題は、結線行列Xの１行目のの重心位置のXY座標が大きくずれている場合に、要素のうち１つをx1, j ＝１とし、冗長性を回避す生成された側面が交差する場合が発生し解を求めるため、x１, j−１＝０とした12個の超格子点のうちられなくなることがある。このとき、二つの断面１つを初期状態とし、xm, j＝１で、初期状態と矛形状の重心位置のXY座標が一致するように平行盾しない２個のうち１個の超格子点を最終状態と移動を行って解を求めることが可能となる。

そして、式を目的関数とし、制約条件をした12n個の最短経路問題として作成できる。そして、この12n個の各最短経路問題を解いて、得３

結果及び考察られた各最適解の中で目的関数値が最小となる解

上下の断面形状を表現する節点間の最適な結線を求めることにより、最適化問題として解ける。

状態を本法で求めた。得られた結果を図３に示す。

ここで、上記最短経路問題の数の説明を三角形曲線を含むあらゆる形状を節点で表現することに側面の形状の観点で補足する。冗長性を回避する

より、様々な形状の適正な結線を行い側面を生成ため、上記x１, j−１＝０に起因して、△形状の三角し、展開図を作成できる実用上の意義は大きい。

形側面１つを前提条件としているため、結線開始

本研究の例では、各項の平均値flave，fvaveを求める

位置でのシステム状態数は12となり、そのため、ためにランダム発生させる実行可能解の数は500

最終結線位置のシステム状態においても、△形状とした。本研究では、 COMPAQ製Professionalの三角形側面１つを前提条件としているため、シWorkstation AP550 CPU1GHz（メモリ512MB）

ステム状態数は12となる。最終状態から状態変化を計算に用いた。

で遷移できる初期状態数は２である。また、初期結線の結線行列における位置がnとおりある。このため、問題Pに対する最短経路問題は、12n個
69動的計画法を用いた板金構造物の展開図作成手法

図３

動的計画法を適用して求めた展開図例

４ まとめい。しかし、展開不可の側面が発生するのは、二板金構造物の展開図作成で上下断面形状を表現

つの断面形状の重心位置のXY座標が大きくずれする節点間の最適な結線状態を決定する最適化問ている場合であるので、平行移動を行い重心位置題を、動的計画法を基本として解くためのアルゴを一致させて求めることが可能になることがわかっリズムを開発した。目的関数としては、結線長さた。このことにより、問題が解けるようになったの総和と、側面構成要素三角形の法線方向の角度だけでなく、高速に最適解を求められるようになっ変化の滑らかさの二つの関数の加重和を用いた。

た。

ここで、生成された側面が展開可能なものであるかどうかの判定は、動的計画法では処理できな70

なお、今回行った種々の検証実験の結果から、本法は十分実用レベルにあると考えられる。

動的計画法を用いた板金構造物の展開図作成手法

５ 参考文献遺伝的アルゴリズムを用いた板金構造物の展開

１）松永省吾,「システム工学入門」, 東京電機大

図のための結線手法, 日本オペレーションズ・リサーチ学会論文誌, Vol.44-3, （2001）, 230-学出版局, 1987, 71-73.
２）M. C.

Gan,

Generating andS. T.

TanandW. Chan

249.

Flattening of Developable

６）外山眞也, 冨田重幸, 吉冨康成：動的計画法

Surfaces, DE-Vol, 69-1, Advances in Designを用いた板金構造物の展開図作成のための結線

Automation, 359-366,（1994）.

決 定 法 , 日 本 応 用 数 理 学 会 , Vol.12, No.1,

３）三谷由香, 入口健二, 加藤清敬：板金部品の設計システム, 特開平7-56974,（1995）.
４）繁山俊雄：板金製缶展開板取りの実際, 理工学社,（1973）.
５）外山眞也, 冨田重幸, 吉冨康成, 春成嘉弘：2002．
７）Yu-Long

LinandD. C. H. Yang : Auto-matic Development Generation for ThinWalled Objects, DE-Vol, 69-1, Advances inDesign Automation, 367-377,（1994）.

71