(57)【要約】【課題】多値決定グラフ(MDD)を用いた多状態システムの新たな解析方法を提供する。【解決手段】多状態システムは、構造関数と呼ばれる多値論理関数としてみなすことができ、 その構造関数は多くの場合、単調増大関数であるため、EVMDDでコンパクトに表現することができる。しかしながら、EVMDDを用いた多状態システムの解析は、通常のMDDを用いた方法とは違い単純ではない。  EVMDDを用いることにより、構造関数を通常のMDDを用いた既存の解析方法よりもコンパクトに表現でき、なおかつ既存の方法と同程度の計算時間でシステムを解析することができる。【選択図】図５
2013161411.tif 000002
【特許請求の範囲】
【請求項１】
重み付き枝を有する多値決定グラフ（EVMDD）とシステム内の各部品における各状態の発生確率P(xi = c)を入力とし、多状態システムにおける各状態の発生確率P(f = s)を出力とする多状態システムの解析方法であって、
訪れた節点が訪問済みならば、その節点における各状態の発生確率を戻り値としてリターンするとともに、そうでなければ、次の処理へ進む第１ステップと、
訪れた節点が終端節点ならば、状態の発生確率P(f = 0) = 1.0を戻り値としてリターンするとともに、そうでなければ、次の処理へ進む第２ステップと、
訪れた節点の各枝iに対して、以下の処理を繰り返す第３ステップと、
(ア)i番目の枝に繋がる節点を、 部分EVMDDの新たな根節点とみなし、ステップ1に戻る。
(イ)前記(ア)の処理で戻り値として得られた各状態sに対して、以下の処理を繰り返す。
(a) 状態sに枝の重みeiを加えた状態の発生確率P(f=s+ei)と、前記(ア)の処理で得られた確率P(f=s)に枝iが選ばれる確率P(x=i)をかけた値との和をとり、それを新たなP(f=s+ei)の値とする。 
(b) 前記 (ア)の処理で戻り値として得られた全ての状態に対して前記aの処理が終わると次のステップ(ウ)へ進み、そうでなければ、次の状態をsとして前記aへ戻る。
(ウ)節点の全ての枝に対して、前記(ア)（イ)の処理が終わると次の第４ステップへ進むとともに、そうでなければ、次の枝をiとして前記(ア)へ戻る。
計算された各状態の発生確率を、この節点からの戻り値とし、節点を訪問済みにしてリターンする第４ステップと、
を含むことを特徴とする多状態システムの解析方法。
【請求項２】
重み付き枝を有する多値決定グラフ（EVMDD）とシステム内の各部品における各状態の発生確率P(xi = c)を入力とし、多状態システムにおける各状態の発生確率P(f = s)を出力とする多状態システムの解析装置であって、重み付き枝を有する多値決定グラフ（EVMDD）ファイル及び状態の発生確率ファイルを格納するディスクと、解析部と、該解析部にて得られた結果を表示する表示部とを備え、前記解析部は、データ転送回路、前記ディスクから前記データ転送回路を介してEVMDDが書き込まれる第１メモリ、前記ディスクから前記データ転送回路を介して各部品の状態の発生確率が書き込まれる第２メモリ、前記第１及び第２メモリのデータの入出力、アクセス、再帰処理を制御する制御回路、該制御回路とともに再帰処理を行うためのスタックメモリ、各節点における状態の発生確率を格納する第３メモリ、前記制御回路にて制御され、前記第２メモリ及び前記第３メモリからのデータを入力して確率の計算を行うとともに計算結果を前記第３メモリに格納する実数加算・乗算器、計算結果を前記表示部に出力する計算結果出力回路よりなることを特徴とする多状態システム解析装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、多状態システムの解析方法及び解析装置に関する。
【背景技術】
【０００２】
近年、コンピュータサーバ、 電話通信網、水・ガス・電気の配給システムなどの様々な大規模システムは、故障や障害に耐性(フォールトトレラント)を持っており、仮にシステム内に故障が生じたとしても、システムの完全停止には至らず、 許容可能な、あるいは、低下した性能レベルで稼働しつづけるように設計されている。 そのため、稼働中と停止中の2状態だけでこれらのシステムをモデル化することができなくなっている。また、技術の進歩にともない、システムの各構成要素(部品)自体もフォールトトレラントになっており、そのような複雑なシステムのモデル化には、多状態システム（非特許文献15、 18、 20）がしばしば利用されている。
【０００３】
多くの場合、フォールトトレラントは、システム内の部品を多重化することで実現されているが、むやみな部品の多重化は、システムのコストが上がるだけで耐故障化にとって非効率的なだけでなく、無駄な部品の多重化で安心してしまい、重要な部品の多重化漏れなどの致命的な設計ミスを引き起こす原因となりうる。特に、航空管制システムや原子力発電所などの安全性が最優先されるシステムで、このような設計ミスがあってはならない。 そのため、どの部品がシステムの耐故障化に不可欠であるのかを把握し、その部品に対して多重化などの適切な対策をとることが重要である（非特許文献2）。
【０００４】
システムの脆弱性や耐故障化にとって重要な部品を特定するためには、様々な評価尺度を用いて、多様な観点から多状態システムを評価・解析する必要がある（非特許文献15）。 その評価・解析の中でも多状態システムにおける各状態の発生確率の評価が、高信頼なフォールトトレラントシステムの設計に不可欠であり（非特許文献18、20）、 これまでに様々な発生確率の評価・解析手法が提案されている。
【０００５】
しかし、提案されている多くの手法がマルコフモデルに基づいており（非特許文献3）、その計算量はO(m3n)であるため、システムの状態数mやシステム内の部品数nが大きな大規模多状態システムの解析に、それらの手法は実用的ではない（非特許文献2）。そのため、近年、大規模多状態システムを解析するために提案された二分決定グラフ(BDD: Binary Decision Diagram) （非特許文献1、2、4、20）や多値決定グラフ(MDD: Multi-valued Decision Diagram) （非特許文献6、17、18）を用いた手法が注目を集めている。
【０００６】
多状態システムは、構造関数と呼ばれる多値論理関数とみなすことができるため、BDDやMDDによって多状態システムを表現でき、そのBDDやMDDを用いることで、各状態の発生確率を決定グラフ内の節点数に比例した計算量で効率良く求めることができる。BDDでは、多値論理関数として与えられた構造関数をワンホットエンコーディングなどで一旦、二値論理関数の集合に変換してからシステムを表現しているため、二状態システムで確立された様々な解析手法を多状態システムに直接適用できるという利点がある（非特許文献20）。 しかし二値論理関数の集合に変換すると二値変数の数や関数の数が増え、大きなBDDが必要になってしまうため、MDDを用いて与えられた構造関数をそのまま表現する方が自然であり、 大規模多状態システムの表現に、より有効である。
【０００７】
しかし、近年の大規模かつ複雑な多状態システムの解析では、システムをさらにコンパクトに表現できる決定グラフが求められている。多状態システムの構造関数は、多くの場合、単調増大関数である（非特許文献17）ため、EVMDD (Edge-Valued MDD：枝重み付けMDD)でコンパクトに表現することができる（非特許文献10、12、13、14）。しかしながら、EVMDDを用いた多状態システムの解析は、通常のMDDを用いた方法とは違い単純ではなく、その解析方法はいまだ実現されていない。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】J. D. Andrews and S. J. Dunnet, “Event-tree analysis using binary decision diagrams,”IEEE Transactions on Reliability, Vol. 49、 No. 2. pp. 230-238, June 2000.
【非特許文献２】Y.-R.Chang、 S. Y. Amari、 and S.-Y. Kuo, “Reliability evaluation of multi-state systems subject to imperfect coverage using OBDD,”Proc. of the 2002 Pacific Rim International Symposium on Dependable Computing (PRDC’02), pp. 193-200, 2002/
【非特許文献３】S.A. Doyle, J. B. Dugan, and F. A. Patterson-Hine, “A combinatorial approach to modeling imperfect coverage,”IEEE Transactions on Reliability, Vol. 44, No. 1、 pp. 87-94, Mar. 1995.
【非特許文献４】S. A. Doyle and J. B. Dugan, “Dependability assessment using binary decision diagrams (BDDs),”25th International Symposium on Fault-Tolerant Computing (FTCS), pp. 249-258, June 1995.
【非特許文献５】T. Kam, T. Villa, R. K. Brayton, and A. L. Sangiovanni-Vincentelli, “Multi-valued decision diagrams: Theory and applications,”Multiple-Valued Logic: An International Journal, Vol. 4, No.1-2, pp. 9-62, 1998.
【非特許文献６】T. W. Manikas, M. A. Thornton, and D. Y. Feinstein、”Using multiple-valued logic decision diagrams to model system threat probabilities,” 41st International Symposium on Multiple-Valued Logic, pp.236-267,May 2011.
【非特許文献７】S. Nagayama and T. Sasao, “Compact representations of logic functions using heterogeneous MDDs,”IEICE Trans, on Fundamentals, Vol. E86-A, No. 12, pp. 3168-3175, Dec. 2003.
【非特許文献８】S. Nagayama, A. Mishchenko, T. Sasao, and J. T. Butler, “Exact and heuristic minimization of the average path length in decision diagrams,”Journal of Multiple-Valued Logic and Soft Computing, Vol. 11, No. 5-6, pp. 437-465, Aug. 2005.
【非特許文献９】S. Nagayama and T. Sasao, “On the optimization of heterogeneous MDDs,” IEEE Trans, on Comput,-Aided Des, Integr, Circuits Syst,  Vol. 24, No. 11, pp. 1645-1659, Nov. 2005.
【非特許文献１０】S. Nagayama and T. Sasao, “Representations of elementary functions using edge-valued MDDs,”37th International Symposium on Multiple-Valued Logic, 2007.
【非特許文献１１】S. Nagayama and T. Sasao, “Complexities of graph-based representations for elementary functions,” IEEE Transactions on Computers, Vol. 58, No. 1、 pp. 106-119, Jan. 2009.
【非特許文献１２】S. Nagayama, T. Sasao, and J. T. Butler, “Floating-point numerical function generators using EVMDDs for monotone elementary functions,”39th International Symposium on Multiple-Valued Logic, May 2009.
【非特許文献１３】S. Nagayama、 T. Sasao、 and J. T. Butler, “Floating-point numerical function generators based on piecewise-split EVMDD,” 40th International Symposium on Multiple-Valued Logic, pp. 223-228, May 2010.
【非特許文献１４】S. Nagayama, T. Sasao, and J. T. Butler, “A systematic design method for two-variable numeric function generators using multiple-valued decision diagrams,” IEICE Trans, on Information and Systems, Vol. E93-, No. 8, pp. 2059-2067. Aug. 2010.
【非特許文献１５】J. E. Ramirez-Marquez and D. W. Coit, “Composite importance measures for multi-state systems with multi-state components,”IEEE Trans, on Reliability, Vol. 54, No. 3, pp. 517-529, Sept. 2005.
【非特許文献１６】T. Sasao and M. Fujita (eds.), Representations of Discrete Functions, Kluwer Academic Publishers, 1996.
【非特許文献１７】L. Xing and J. B. Dugan,”Dependability analysis using multiple-valued decision diagrams、”Proc, of 6th International Conference on Probabilistic Safety Assessment and Management, June 2002.
【非特許文献１８】L. Xing and Y. Dai, “A new decision-diagram-based method for efficient analysis on multistate systems,”IEEE Transactions on Dependable and Secure Computing, Vol. 6, No. 3, pp. 161-174, 2009.
【非特許文献１９】S. N. Yanushkevich, D. M. Muller, V. P. Shmerko, and R. S. Stankovic, Decision Diagram Techniques for Micro and Nanoelectronic Design, CRC Press, Taylor & Francis Group, 2006.
【非特許文献２０】X. Zang、 D. Wang、 H. Sun, and K. S. Trivedi, “A BDD-based algorithm for analysis of multistate systems with multistate components,”IEEE Transactions on Computers, Vol. 52, No. 12, pp. 1608-1618, Dec. 2003.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
BDDにおいて、二値論理関数の集合に変換すると、二値変数の数や関数の数が増え、大きなBDDが必要になってしまうという問題がある。またMDDでは、節点数が増大し計算量が大きくなるという問題がある。
【００１０】
本発明は、EVMDDを用いることによりこれらの問題を解決する解析方法及び解析装置を提供するものである。
【課題を解決するための手段】
【００１１】
請求項1に係る多状態システムの解析方法は、重み付き枝を有する多値決定グラフ（EVMDD）とシステム内の各部品における各状態の発生確率P(xi = c)を入力とし、多状態システムにおける各状態の発生確率P(f = s)を出力とする多状態システムの解析方法であって、
訪れた節点が訪問済みならば、その節点における各状態の発生確率を戻り値としてリターンするとともに、そうでなければ、次の処理へ進む第１ステップと、
訪れた節点が終端節点ならば、状態の発生確率P(f = 0) = 1.0を戻り値としてリターンするとともに、そうでなければ、次の処理へ進む第２ステップと、
訪れた節点の各枝iに対して、以下の処理を繰り返す第３ステップと、
（ア）i番目の枝に繋がる節点を、 部分EVMDDの新たな根節点とみなし、ステップ1に戻る。
（イ）前記(ア)の処理で戻り値として得られた各状態sに対して、以下の処理を繰り返す。
(a) 状態sに枝の重みeiを加えた状態の発生確率P(f=s+ei)と、前記(ア)の処理で得られた確率P(f=s)に枝iが選ばれる確率P(x=i)をかけた値との和をとり、それを新たなP(f=s+ei)の値とする。 
(b) 前記 (ア)の処理で戻り値として得られた全ての状態に対して前記aの処理が終わると次のステップ(ウ)へ進み、そうでなければ、次の状態をsとして前記aへ戻る。
（ウ）節点の全ての枝に対して、前記(ア)（イ)の処理が終わると次の第４ステップへ進むとともに、そうでなければ、次の枝をiとして前記(ア)へ戻る。
計算された各状態の発生確率を、この節点からの戻り値とし、節点を訪問済みにしてリターンする第４ステップと、よりなるものである。
【００１２】
請求項２に係る多状態システムの解析装置は、重み付き枝を有する多値決定グラフ（EVMDD）とシステム内の各部品における各状態の発生確率P(xi = c)を入力とし、多状態システムにおける各状態の発生確率P(f = s)を出力とする多状態システムの解析装置であって、EVMDDファイル及び状態の発生確率ファイルを格納するディスクと、解析部と、該解析部にて得られた結果を表示する表示部とを備え、前記解析部は、データ転送回路、前記ディスクから前記データ転送回路を介してEVMDDが書き込まれる第１メモリ、前記ディスクから前記データ転送回路を介して各部品の状態の発生確率が書き込まれる第２メモリ、前記第１及び第２メモリのデータの入出力、アクセス、再帰処理を制御する制御回路、該制御回路とともに再帰処理を行うためのスタックメモリ、各節点における状態の発生確率を格納する第３メモリ、前記制御回路にて制御され、前記第２メモリ及び前記第３メモリからのデータを入力して確率の計算を行うとともに計算結果を前記第３メモリに格納する実数加算・乗算器、計算結果を前記表示部に出力する計算結果出力回路よりなるものである。
【発明の効果】
【００１３】
本発明によれば、EVMDDを用いて多状態システムを解析するものであるため、構造関数をコンパクトに表現することができる。さらに、その節点数の減少、従って計算量を減らすことができることから、システム解析を短時間で行うことができる。
【図面の簡単な説明】
【００１４】
【図１】多状態システムを説明するための概略図である。
【図２】構造関数fを表現しているMDDの図である。
【図３】構造関数fを表現しているEVMDDの図である。
【図４】構造関数fを表現しているMDDに関する定理を証明するための図である。
【図５】本発明の実施形態に係る解析方法の全体を示すフローチャートである。
【図６】本発明の実施形態に係る解析方法の再帰処理部分を示すフローチャートである。
【図７】本発明の実施形態に係る解析方法の再帰処理部分を示すフローチャートである。
【図８】本発明に係るEVMDD を用いた多状態システムの解析方法を説明するための図である。
【図９】本発明に係るEVMDD を用いた多状態システムの解析方法の一実施例を説明するためのブロック図である。
【図１０】同実施例に対応する多状態システムを示す図である。
【図１１】同実施例に対応する多状態システムを表現するEVMDDを示す図である。
【図１２】同実施例に対応するEVMDDを用いた多状態システムの解析方法を説明するための図である。
【発明を実施するための形態】
【００１５】
諸定義
本発明では、多状態システムとその構造関数、および構造関数の表現に用いるMDDを定義する。
【００１６】
多状態システムと構造関数
定義 1. 多状態システムとは、システムの性能や信頼性などのレベルを状態として(通常は三つ以上の状態数で) 表現するシステムモデルである。多状態システムでは、システムの各構成要素(部品)の性能や信頼性レベルも同様に状態としてモデル化される。
【００１７】
定義 2. 多状態システム全体の状態が、システムを構成している部品の状態の組合せだけで決定されると仮定すると、n個の部品から成る多状態システムは、n変数多値論理関数f(x1、 x2、…、 xn) : R1 × R2 ×… × Rn → M とみなすことができる。ここで、各多値変数xi は状態数がri の部品を表現し、Ri = {0、 1、…、 ri - 1}はその部品の状態の集合である。同様に、M = {0、 1、…、 m - 1}は、状態数がmのシステムの状態集合である。この多値論理関数fを多状態システムの構造関数という。
【００１８】
定義 3. 多値論理関数f(x1、 x2、 …、 xn)が任意の変数xiにおいて、以下の性質を満たすとき、かつそのときに限り、fを単調増大関数という。
【数１】
2013161411.tif 000003
【００１９】
ただし∀α、 β∈ Ri、 かつα ≦ β
【００２０】
多くの応用分野において、多状態システムおよびその部品の状態には全順序関係があり、システム内の部品の劣化や性能低下がシステム全体の劣化や性能低下をもたらす。そのため、最悪の状態に0、最良の状態にm - 1またはri - 1を割り当てることによって、多くの構造関数は、単調増大関数になる。
【００２１】
多くの応用分野において、多状態システムおよびその部品の状態には全順序関係があり、システム内の部品の劣化や性能低下がシステム全体の劣化や性能低下をもたらす。そのため、最悪の状態に0、最良の状態にm - 1またはri - 1を割り当てることによって、多くの構造関数は、単調増大関数になる。
【００２２】
これらの各状態に昇順で値を割り当てることによって得られる構造関数fは、表１に示されるように単調増大関数になる。
【表１】
2013161411.tif 000004
【００２３】
多値決定グラフ(MDD: Multi-valued Decision Diagram)
定義 4. 多値決定グラフ(MDD: Multi-valued Decision Diagram)は、多値論理関数f を表現している根付きの非巡回有向グラフであり、多値論理関数にシャノン展開を繰り返し適用することで得られる（非特許文献5）。MDDは、関数値を表現する終端節点と、多値変数に値を割り当てることで得られるfの部分関数を表現する非終端節点からなる。各非終端節点は、変数値に対応する重み無しの枝を持ち、MDD内の多値変数には順序付けがされている。すなわち、根から終端節点まで、どのパスを通っても同じ順序で変数が表れる。各多値変数の定義域が異なってもよい関数を表現するMDDを、ヘテロジニアスMDD（非特許文献7、 9）という。以下では、簡単のため、ヘテロジニアスMDDを単にMDDと略記する。
【００２４】
定義 5. EVMDD (Edge-Valued MDD)（非特許文献10、 12、 14）は、MDDを拡張したグラフであり、0を表現する一つの終端節点と、重み付きの枝を持った非終端節点からなる。ただし、枝の重みは整数値であり、0-枝の重みは0である。EVMDDで関数値は、終端節点ではなく、根から終端節点まで辿った際に通過する枝の重みの和として表現されている。
【００２５】
例 ２
表1の構造関数fを表現している通常のMDDとEVMDDを、図2 及び図3 にそれぞれ示す。
【００２６】
構造関数を表現するMDD及びEVMDD
構造関数を表現するMDD及びEVMDDの節点数における上界を導出する。説明の簡単化のために、以下の定理では統一的に、多状態システム内の全ての部品xiが同じ状態数r (すなわち、全ての多値変数xiが同じ定義域)を持つものと仮定する。しかし、各多値変数xiがそれぞれ異なる定義域を持つ場合への一般化は容易である。
【００２７】
定理 1. 構造関数を表現するMDDの節点数の上界は、以下の式で得られる。
【数２】
2013161411.tif 000005
【００２８】
ここで、 lは、 rn-l ≧ mrlを満たす最大の整数、mはシステムの状態数、nはシステム内の部品数、rは部品の状態数を表している。
【００２９】
この証明は以下の通りである。
図４に示されるように、MDDを上下に二分割する。このとき、下部ではl変数多値論理関数が表現され、上部では、それらの中から一つを選択する関数が表現されている。上部は、完全多分木のとき節点数が上限に達し、そのときの節点数は、初項を1、公比をrとした等比数列の和1 + r + r2 + … + rn-l-1で得られるため、次の式となる。
【数３】
2013161411.tif 000006
【００３０】
下部は、全てのl変数多値論理関数が表現されたとき、節点数が最大となる。全てのl変数多値論理関数の数は、次の数式で表される。
【数４】
2013161411.tif 000007
【００３１】
各関数が終端節点を含む1つの節点で表現されるため、これが下部での最大節点数になる。以上より、 MDDの節点数は高々
【数５】
2013161411.tif 000008
【００３２】
となり、下部で表現可能な多値論理関数の数は、上部で選択可能な関数の数rn-lを超えないため、次の関係を得る。
【数６】
2013161411.tif 000009
【００３３】
定理1は、MDDの上界はmとnおよびrの値だけに依存し、構造関数の単調性(形状)には無関係に定まるということを示している。しかし、先に述べたように、多くの応用分野で、構造関数は、通常、単調増大関数になるため、関数の単調性を表現できる単調関数に適した決定グラフが、構造関数の表現には望ましい。EVMDDは、単調関数をコンパクトに表現できることが知られている（非特許文献14）ため、EVMDDは多くの構造関数の表現に適しているといえる。
【００３４】
単調な多値論理関数は、多値変数xiの集合を
【数７】
2013161411.tif 000010
【００３５】
のように、r値ベクトルとみなすことによって、Mp単調増大関数に変換することができ、Mp単調増大関数と同じ複雑さのEVMDDで表現することができる（非特許文献14）。そのため、単調な多値論理関数から変換して得られたMp単調増大関数を表現するEVMDDの上界を次の定理で示す。
【００３６】
定理 2. 単調な多値論理関数から変換して得られたMp単調増大関数を表現するEVMDDの節点数の上界は、以下の式で得られる。
【数８】
2013161411.tif 000011
【００３７】
ここで、lはrn-l ≧ (p + 1)r l-1を満たす最大の整数、nは元の多値論理関数での多値論理変数の数を表す。
【００３８】
定理２は、二分決定グラフにおける証明（非特許文献11）をMDDに拡張することで、同様に証明できる。定理2は、EVMDDの上界はシステムの状態数mではなく、pの値に依存するということを示している。そのため、システムの状態数mが多くても、pの値が小さければEVMDDの節点数は少ない。
【００３９】
今後、システムはさらに複雑になり、状態数mは増えることが予想されるが、そのような複雑なシステムの表現に、通常のMDDを用いると多くの節点数が必要になる。EVMDDは、そのようなシステムでも、pの値が小さければ、コンパクトに表現できる。
【００４０】
pの値は、部品の劣化に対するシステム全体の劣化の度合を表しているため、システムが複雑になり状態数が増えても、pの値が、今後、急激に増えることは考えにくい。むしろ技術の進歩により、部品のわずかな性能劣化がシステム全体の性能に影響しないようになり、小さい値に抑えられる可能性が高い。そのため、EVMDDは今後の複雑なシステムの表現に、より適しているといえる。
【００４１】
MDDを用いた解析法とEVMDDを用いた解析法
次に、多状態システムの解析問題を定式化し、続いてこれを、EVMDDを用いて解くアルゴリズムについて説明する。
【００４２】
定義 7. 多状態システムfの状態がsになる確率をP(f = s)、ただし、s ∈ {0、 1、…、m1}で表す。同様に、システム内の部品xiの状態がcになる確率をP(xi = c)、ただし、c ∈ {0、 1、…、 ri1}で表す。
多状態システムの構造関数fとシステム内の各部品がとる各状態の確率P(xi = c)が与えられたとき、与えられた多状態システムにおける各状態の発生確率P(f = s)を求める。ここで、各部品の状態は他の部品の状態とは独立に発生すると仮定する。
【００４３】
MDDを用いた解析方法
この場合、MDDの平均パス長を算出するために導入された節点通過確率を用いて効率良く解くことができる（非特許文献8）。
【００４４】
定義 8. MDDにおいて、根から終端節点までの経路をパスという。パスが節点viを通過する確率を節点通過確率とよび、NTP(vi)で表す。
【００４５】
構造関数を表現するMDDの終端節点は多状態システムの状態を表現しているため、終端節点の節点通過確率はシステムの状態の発生確率に等しい。節点通過確率は、MDDの各節点を幅優先順で一度だけ訪れれば求まるため、この解析法の計算量はO(NM)となる。ただしNMはMDDの節点数を表す。計算量がO(NM)である他の既存の解析方法も、節点通過確率という用語は用いていないが、同様の方法で多状態システムを解析している（非特許文献6、 17、 18）。
【００４６】
例３
この例では、図2のMDDにおける各節点の節点通過確率を求める。ただし、簡単のために、各部品での状態の発生確率は全て等しい1/3と仮定する。最初に、根節点は全てのパスが必ず通過するため、根節点v1の節点通過確率NTP(v1) = 1.0が求まる。次に、幅優先順に節点を訪問し、下記数式９を計算する。
【数９】
2013161411.tif 000012
【数１０】
2013161411.tif 000013
【００４７】
数式１０を計算し、最終的に終端節点の節点通過確率NTP(0) = 0.309、 NTP(1) = 0.370、 NTP(2) = 0.123、 NTP(3) = 0.111、 NTP(4) = 0.074、 NTP(5) = 0.012が得られる。
【００４８】
EVMDDを用いた解析方法
EVMDDで、関数値は終端節点ではなく、枝の重みの和によって表現されている。そのため、 MDDのように節点通過確率だけを用いて問題を解くことができず、新たな別の解析方法が必要になる。
【００４９】
以下本発明実施形態に係る解析方法について説明する。
図５は、その全体のフローチャートを示し、次のようなステップにて処理される。
ステップS1:EVMDDの読み込み処理。
ステップS2：ディスク又はキーから、各部品における各状態の発生確率が入力される。
ステップS3：多状態システムの解析が行われる。これは再帰処理にてなされ、各状態の発生確率が求められる。
ステップS4:求められた発生確率が表示装置にて表示される。
【００５０】
以下本発明実施形態に係る解析方法について説明する。
図５は、その全体のフローチャートを示し、次のようなステップにて処理される。
ステップS1:EVMDDの読み込み処理。
ステップS2：ディスク又はキーから、各部品における各状態の発生確率が入力される。
ステップS3：多状態システムの解析が行われる。これは再帰処理にてなされ、各状態の発生確率が求められる。
ステップS4:求められた発生確率が表示装置にて表示される。
【００５１】
第１ステップS31：訪れた節点が訪問済みならば、その節点における各状態の発生確率を戻り値としてリターンするとともに、そうでなければ、次へ進む。
第２ステップS32：訪れた節点が終端節点ならば、状態の発生確率P(f = 0) = 1.0を戻り値としてリターンするとともに、そうでなければ、次の第３ステップS33処理へ進む。
第３ステップS33：訪れた節点の各枝iに対して、以下の処理を繰り返す。
（ア）i番目の枝に繋がる節点を、部分EVMDDの新たな根節点とみなし、再帰処理に移る。
（イ）前記(ア)の処理で戻り値として得られた各状態sに対して、以下の処理を繰り返す。
（a） 状態sに枝の重みeiを加えた状態の発生確率P(f=s+ei)と、前記(ア)の処理で得られた確率P(f=s)に枝iが選ばれる確率P(x=i)をかけた値との和をとり、それを新たなP(f=s+ei)の値とする。すなわち、以下の式を計算する。
P(f=s+ei) = P(f=s+ei) + P(f=s) × P(x=i)
（b） 前記 (ア)の処理で戻り値として得られた全ての状態に対して前記（a）の処理が終わると次のステップ(ウ)へ進み、そうでなければ、次の状態をsとして前記（a）へ戻る。
（ウ）節点の全ての枝に対して、前記(ア)（イ)の処理が終わると次の第４ステップS34へ進むとともに、そうでなければ、次の枝をiとして前記(ア)へ戻る。
第４ステップS34：計算された各状態の発生確率を、この節点からの戻り値とし、節点を訪問済みにしてリターンする。
【００５２】
解析装置
図７において、１は、EVMDDファイル及び状態の発生確率ファイルを格納するディスク、２は、解析部、３は、得られた結果を表示する表示部である。これらはすべてコンピュータにて構成される。
【００５３】
解析部２の構成をさらに詳述する。４は、データ転送回路、５は、EVMDDを格納する第１メモリ、６は、各部品の状態の発生確率を格納する第２メモリで、これら第１、第２メモリ５、６にデータ転送回路４を介して、ディスク１から、それぞれEVMDD及び発生確率が書き込まれる。
【００５４】
７は、第１、第２メモリ５、６のデータ入出力及びアクセス、再帰処理を制御する制御回路、８は、再帰処理を行うためのスタックメモリ、９は、各節点における状態の発生確率を格納する第３メモリ、１０は、第２、第３メモリ６、９からのデータを入力して確率の計算を行う実数加算・乗算器で、計算結果は、第３メモリ９へ格納される。第３メモリ９の発生確率情報は、計算結果出力回路１１を介して表示部３にて表示される。実数加算・乗算器１０及び計算結果出力回路１１は制御回路７にて制御される。
【００５５】
前述したステップS1、S2の処理は、ディスク１及びデータ転送回路４にて、またステップS3の処理は、制御回路７及びスタックメモリ８にて実行され、ステップS4の結果は表示部３にてなされる。
【００５６】
本発明に係る解析方法では、根から深さ優先順に各節点を一度だけ訪れ、各節点で表現されている部分関数を再帰的に解析する。各節点で表現されている部分関数における状態の発生確率は、子節点で表現されている部分関数での発生確率を一つにまとめることによって、得られるため、根節点でまとめられた発生確率が、求めるシステムでの各状態の発生確率となる。各節点を一度だけ訪問すれば、システムの解析が終わるので、アルゴリズムの計算量はEVMDDの節点数NE に比例したO(NE)となる。
【００５７】
例 ４
この例では、図3のEVMDDを用いて多状態システムにおける各状態の発生確率を求める。先の例と同じく、各部品での状態の発生確率を全て1/3と仮定する。
【００５８】
図８において、終端節点で定数関数0における状態の発生確率P(f=0)=1.0を得る。次に節点v1での部分関数における確率を算出する。この節点の子節点は全て終端節点であり、重みが1の枝が二本あるので、それらの部分関数における状態の発生確率はともにP(f=0+1)=1.0となる。 これに部品での確率1/3をかけて和をとったものが、節点v1での状態1の発生確率P(f= 1) = 2/3になる。状態0の発生確率は、0-枝から得られるため、節点v1での二つの状態0、 1の発生確率はそれぞれP(f=0)=1/3、P(f=1)=2/3となる。同様に、節点v2での三つの状態0、 1、 2の発生確率は、P(f=0)=1/3、P(f=1)=1/3、P(f=2)=1/3となり、節点v3で、今まで得られた各状態の発生確率がそれぞれ1/3倍され、同じ状態の発生確率が積算される。
【００５９】
その結果、 節点v3での3状態0、 1、 2の発生確率は、P(f=0)=5/9、P(f=1)=1/3、P(f=2)=1/9となる。 同じ計算を各節点で深さ優先順に繰返すことによって、最終的に根節点での6状態の発生確率P(f=0)=25/81、P(f=1)= 10/27、P(f=2)=10/81、P(f=3)=1/9、P(f=4)=6/81、P(f= 5)=1/81が得られ、この結果は、例3でMDDを用いて得た結果と一致する。
【００６０】
本発明に係る解析方法では、構造関数が単調増大関数ならば、EVMDDの節点数NEはより小さくなるため、計算時間もより短くなるが、構造関数が単調増大関数でない場合（非特許文献18、20）も同様に、本発明方法を適用することができる。
【００６１】
実験結果
本発明に係る解析方法の効率を示すために、様々な構造関数を用いて実験を行った。多くの構造関数が単調増大関数であることから、M1単調増大関数をランダムに生成し、実験で使う構造関数とした。MDDとEVMDDに基づく解析アルゴリズムをC言語で実装し、以下の計算機環境で実行した。
【００６２】
CPU: Intel Core2 Quad Q6600 2.4GHz、メモリ:4GB、OS: CentOS 5.7、Cコンパイラ: gcc O2 (バージョン4.1.2)。 ランダムに生成したn個の3状態部品からなるm状態システムの実験結果を表２に示す。
【表２】
2013161411.tif 000014
【００６３】
この表から、全ての構造関数においてEVMDDの節点数はMDDよりも少ないことがわかる。 特に、システムの状態数mが大きくなるにつれ、EVMDDの節点数はMDDよりも、はるかに少なくなる。今後、システムはさらに複雑になり、状態数mは増えると予想されるため、サイズが状態数に依存しないEVMDDの方が、より有効であるといえる。しかし、状態数mが非常に小さいときには、計算時間がより短く、節点数も十分に少ないMDDの方が適している。表２で、m = 3のとき、EVMDDの節点数はMDDの節点数よりも2節点少ないだけである。 これは終端節点が2つ減っただけなので、このような状態数の少ないシステムにEVMDDを用いるのは効果的とはいえない。
【００６４】
計算時間に関しても、EVMDDを用いた方法は、MDDを用いた既存の方法に匹敵する速度でシステムを解析することができる。そのため、EVMDDは、文字通り多くの状態を持つ多状態システムのコンパクトな表現と効率的な解析に適していると結論づけることができる。
【実施例】
【００６５】
本発明に係る解析方法を、配電システムに適用した場合につき、その具体的な例を説明する。
【００６６】
図９において、火力発電所x3は、フル稼働時には、500万キロワットの電力を供給でき、 故障が生じても、予備の発電機を稼動することで300万キロワットの電力を供給することができるものとし、水力発電所x2及び風力発電所x1も同様に、予備機により、故障が生じても電力の供給が、すぐには停止にならず、表３のように電力を供給することができるものとする。
【表３】
2013161411.tif 000015
【００６７】
3つの発電所x1、x2、x3で作られた電力は変電所x0を通じて街yへと送られる。 このとき、 供給された電力量の合計が400万キロワット以上ならば、電力不足にはならないが、その数字を下回ったときは、多くの電力を消費する工場への電力を停止するなどの対策が必要になる。電力量に対する対策の例を表４に示す。
【表４】
2013161411.tif 000016
【００６８】
このシステムで、各発電所x1、x2、x3での故障発生確率が与えられたとき、どのぐらいの確率で街yは全戸停電となり、電力を安定供給できる確率はどのぐらいになるかを解析する。ただし、この例においては、説明を簡単にするために、送電線や変電所では障害が発生しないものと仮定する。
【００６９】
多状態システムの例
図９に示す配電システムを数学的にモデル化ものが多状態システムであり、各発電所x1、x2、x3で供給可能な電力量および街yでの状況を「状態」として扱う。図９は、図１０に示す多状態システムで表現できる。
【００７０】
火力発電所x3、水力発電所x2、風力発電所x1での状態(フル稼働、予備機稼動、完全停止)を2、 1、0の数字で表し、街yでの状態(過剰供給、安定供給、工場停電、交通機関停止、住宅街部分停電、全戸停電)も5、4、3、2、1、0の数字で表すことにより、各発電所で供給可能な電力量と街での状況との関係を表５のように表すことができる。この表に示されている関係が多状態システムの構造関数である。
【表５】
2013161411.tif 000017
【００７１】
EVMDDを用いた解析の例
表５の構造関数をEVMDDで表現すると図１１のようになる。このEVMDDを使って、街yでの各状態の発生確率を求める。この例では、説明を簡単にするために、発電所での各状態の発生確率はみな等しい、すなわちフル稼働も予備機稼動も完全停止も全て1/3の確率で発生すると仮定する。
【００７２】
まず、終端節点における状態の発生確率を求める。終端節点は、街yがまだ電力供給を受けていない状態を表しているので、全戸停電の確率が1.0、つまりPT(y = 0) = 1.0となる。
【００７３】
次に、図１２に示す節点v1で確率を計算する。風力発電が稼動すれば、街yの状態は部分停電の状態になり、予備を含め風力発電が稼働中の確率は2/3なので、全戸停電の確率Pv1(y = 0) = 1/3、部分停電の確率Pv1(y = 1) = 2/3となる。
【００７４】
節点v2では、水力発電がフル稼働であれば、街yは交通機関停止の状態となり、水力が予備稼動かつ風力が稼働中でも、 街yは同じ状態になる。 水力が予備稼動か風力が稼働中のいずれかであれば、街yは部分停電の状態になり、いずれも停止中であれば、全戸停電となる。そのため、節点v2では、全戸停電の確率Pv2(y = 0) = 1/9、部分停電の確率Pv2(y = 1) = 1/3、交通機関停止の確率Pv2(y = 2) = 5/9となる。これは節点v2の各枝で以下のように計算することで得られる。
【００７５】
２．1-枝も節点v1につながっているため、v1での各状態の発生確率に1/3をかけた値を、 v1での状態番号に枝の重み1を加えた状態の確率として計算する。すなわち、下記式を計算する。
【数１２】
2013161411.tif 000018
【００７６】
３．2-枝は終端節点につながっているため、終端節点での状態0の発生確率に1/3をかけた値を、終端節点での状態番号0に枝の重み2を加えた状態の確率として計算する。すなわち、下記式を計算する。
【数１３】
2013161411.tif 000019
【００７７】
４．上記の計算で得られた値を状態番号ごとに足し合わせることで、節点v2での状態発生確率を得る。
【数１４】
2013161411.tif 000020
【００７８】
以下同様に、EVMDDの終端節点から根節点に向かい各節点で状態の発生確率を計算することにより、最終的に根節点でシステム全体の状態発生確率を得ることができ、各状態の発生確率は以下のようになる。
【００７９】
０(全戸停電)の確率1/27、１(部分停電)の確率1/9、２(交通機関停止)の確率5/27、３(工場停電)の確率1/9、４(安定供給)の確率10/27、５(過剰供給)の確率5/27。
【００８０】
以上の解析から、この配電システムでは、過剰供給を含め約56%の確率でしか街に十分な電力を供給することができないということがわかる。この確率は、例えば、火力発電での故障発生確率をフル稼働：90%、予備稼動：9%、完全停止：1%に改善することで、街への十分な電力供給の確率を約96%まで改善できる。
【００８１】
上記の例は、あくまで一例であり、多状態システムでモデル化できるシステムであれば、 どのようなシステムでも本発明解析法を適用することができる。上記以外の代表的な応用例として、コンピュータサーバ、電話通信網、水道・ガスの配給システム、航空機制御システムなどがある。
【００８２】
以上のように、本発明に係る解析方法では、 システムの状態が枝の重みの和として表現されているため、通常のMDDを用いた既存の解析方法よりもやや複雑になるが、実際の計算時間は、既存方法とほとんど変わらない。これは、本発明方法の計算量が漸近的にEVMDDの節点数に比例し、EVMDDの節点数が通常のMDDよりも少ないことに起因する。多くの状態を持つシステムではEVMDDの節点数がMDDよりも、はるかに小さくなるため、本発明方法は、そのようなシステムに対して特に有効である。EVMDDは、構造関数が単調でないとしても、そのサイズがMDDより大きくなることはなく、多様な構造関数に対して有効である。
【産業上の利用可能性】
【００８３】
本発明は、水道、ガス、電力等の供給システム、コンピュータサーバ、電話通信網等に利用して有用である。
【符号の説明】
【００８４】
１          ディスク
２          解析部
３          表示部
４          データ転送回路
５，６，９    メモリ
７          制御回路
８          スタックメモリ
１０          実数加算・乗算器
１１          計算結果出力回路
【図１】
2013161411.tif 000021
【図２】
2013161411.tif 000022
【図３】
2013161411.tif 000023
【図４】
2013161411.tif 000024
【図５】
2013161411.tif 000025
【図６】
2013161411.tif 000026
【図７】
2013161411.tif 000027
【図８】
2013161411.tif 000028
【図９】
2013161411.tif 000029
【図１０】
2013161411.tif 000030
【図１１】
2013161411.tif 000031
【図１２】
2013161411.tif 000032
【手続補正書】
【提出日】平成24年10月17日(2012.10.17)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００５０
【補正方法】変更
【補正の内容】
【００５０】
図６を参照して、ステップS3における再帰処理を以下に説明する。