(57)【要約】【課題】多値決定グラフ(MDD)を用いた多状態システムの診断方法及び診断装置を提供する。【解決手段】多状態システムは、構造関数と呼ばれる多値論理関数としてみなすことができ、その構造関数は多くの場合、単調増大関数であるため、EVMDDでコンパクトに表現することができる。しかしながら、EVMDDを用いた多状態システムの解析・診断は、通常のMDDを用いた方法とは違い単純ではない。 EVMDDを用いることにより、構造関数を通常のMDDを用いた既存手法よりもコンパクトに表現でき、なおかつ既存手法と同程度の計算時間でシステムを解析することができ、この解析方法を用いれば効率のよい診断方法及び診断段装置が実現できる。【選択図】図６
2014099021.tif 000002
【特許請求の範囲】
【請求項１】
多状態システムの構造関数を表現する、重み付き枝を有する多値決定グラフ（EVMDD）と、システム内の各構成要素における各状態の発生確率Pc、診断するシステムの状態s、診断する構成要素xiとその状態 cを入力とし、条件付確率P(f = s | xi = c)を出力とする多状態システムの診断方法であって、以下のステップをEVMDDの根節点から再帰的に各節点vで実行し、根節点でのf = sにおける確率を答とすることを特徴とする多状態システムの診断方法。
ステップS1：EVMDDの読み込み処理。
ステップS2：ディスク又はキーから、各部品における各状態の発生確率、診断するシステムの状態sおよび部品xiとその状態cが入力される。
ステップS3：多状態システムの診断が行われる。これは再帰処理にてなされ、引数として、EVMDDの根節点、各状態の発生確率Pc、システムの状態s、部品xiとその状態cが使用され、結果（戻り値）としてシステムの各状態の条件付確率が得られる。
ステップS4：上記条件付確率が表示装置にて表示される。
【請求項２】
前記ステップS3における再帰処理が以下のステップからなることを特徴とする請求項１記載の多状態システムの診断方法。
ステップS3-1：訪れた節点vが訪問済みか否かを判断する。訪問済み（true）ならば、ステップS3-2へ進み、そうでなければ(false)、ステップS3-3へ進む。
ステップS3-2：節点vが表現する部分関数fvにおける各状態の発生確率を戻り値としてリターン。
ステップS3-3：節点vが終端節点か否かを判断する。終端節点Tならば(true)、ステップS3-4へ進み、そうでなければ(false)、ステップS3-5へ進む。
ステップS3-4：定数関数0における状態の発生確率Ps(fT = 0) = 1を戻り値としてリターン。
ステップS3-5：節点vの変数がxiか否かを判断する。変数がxiならば(true)、ステップS3-6へ進み、そうでなければ(false)、ステップS3-7へ進む。
ステップS3-6：xi = cの枝につながっている子節点ucだけに対して以下に示す部分処理A（ステップS3-6-1）を実行する。
ステップS3-7：節点vの全ての子節点ujに対して以下に示す部分処理B（ステップS3-7-1）を実行する。
ステップS3-8：節点vを訪問済みとし、計算で得られた各状態の発生確率を戻り値としてリターン。
前記部分処理Aは以下のステップからなる。
ステップS3-6-1：子節点ucを、部分EVMDDの根節点とした再帰処理を行うために、ステップS3-1に戻る。再帰処理からリターン後、次のステップS3-6-2へ進む。
ステップS3-6-2：ステップS3-6-1の処理で戻り値として得られた各状態suc に対して、以下の処理を繰り返す。
ステップS3-6-3：状態sucに枝の重みecを加えた状態の発生確率Ps(fv = suc + ec)と、ステップS3-6-1で得られた値との和をとり、それを新たな発生確率Ps(fv = suc + ec)とする。
ステップS3-6-4：ステップS3-6-1の処理で戻り値として得られた全ての状態に対してステップS3-6-3の処理が終わると、計算した発生確率を戻り値として、ステップS3-8へ進む。終了してなければ、次の状態に対して、ステップS3-6-2へ戻り、処理を続ける。
前記部分処理Bは以下のステップからなる。
ステップS3-7-1：全ての子節点ujに対して、以下の処理を繰り返す。
ステップS3-7-2：ujを部分EVMDDの根節点とした再帰処理を行うために、ステップS3-1に戻る。再帰処理からリターン後、次のステップS3-7-3へ進む。
ステップS3-7-3：ステップS3-7-2の処理で戻り値として得られた各状態sujに対して、以下の処理を繰り返す。
ステップS3-7-4：ステップS3-7-2で得られた確率Psに節点ujが選ばれる確率Pcをかける。
ステップS3-7-5：状態sujに枝の重みejを加えた状態の発生確率Ps(fv = suj + ej)と、ステップS3-7-4で得られた値との和をとり、それを新たな発生確率Ps(fv = suj + ej)とする。
ステップS3-7-6：ステップS3-7-2の処理で戻り値として得られた全ての状態に対してステップS3-7-4,S3-7-5の処理が終わると、ステップS3-7-7へ進み、終了してなければ、次の状態に対して、ステップS3-7-3へ戻り、処理を続ける。
ステップS3-7-7：引数として与えられた全ての子節点に対して、S3-7-2からS3-7-6の処理が終わると、計算した発生確率を戻り値として、ステップS3-8へ進む。終了してなければ、次の子節点に対して、ステップS3-7-1へ戻り、処理を続ける。
【請求項３】
多状態システムの構造関数を表現する、重み付き枝を有する多値決定グラフ（EVMDD）と、システム内の各構成要素における各状態の発生確率Pc、診断するシステムの状態s、診断する構成要素xiとその状態 cを入力とし、条件付確率P(f = s | xi = c)を出力とする多状態システムの診断装置であって、重み付き枝を有する多値決定グラフ（EVMDD）ファイル及び状態の発生確率ファイルを格納するディスクと、診断するシステムの状態及び診断する部品とその状態を入力する入力部と、解析診断部と、該解析診断部にて得られた結果を表示する表示部とを備え、前記解析診断部は、データ転送回路、前記ディスクから前記データ転送回路を介してEVMDDが書き込まれる第１メモリ、前記ディスクから前記データ転送回路を介して各部品の状態の発生確率が書き込まれる第２メモリ、前記第１及び第２メモリのデータの入出力、アクセス、再帰処理を制御する制御回路、該制御回路とともに再帰処理を行うためのスタックメモリ、各節点における状態の発生確率を格納する第３メモリ、前記制御回路にて制御され、前記第２メモリ及び前記第３メモリからのデータを入力して確率の計算を行うとともに計算結果を前記第３メモリに格納する実数加算・乗算器、計算結果を前記表示部に出力する計算結果出力回路よりなることを特徴とする多状態システムの診断装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、多状態システムの診断方法及び診断装置に関する。
【背景技術】
【０００２】
近年、コンピュータサーバ、電話通信網、水・ガス・電気の配給システムなどの様々な大規模システムが故障や障害に耐性(フォールトトレラント)を持っており、仮にシステム内に故障が生じたとしても、システムの完全停止には至らず、許容可能な、あるいは、低下した性能レベルで稼働しつづけるように設計されている。そのため、従来のシステムとは異なり、稼働中と停止中の2状態だけでこれらのシステムをモデル化することができなくなっている。また、技術の進歩にともない、システムの各構成要素(部品)自体もフォールトトレラントになっており、そのような複雑なシステムのモデル化には、多状態システム（非特許文献１、２、３）がしばしば利用されている。
【０００３】
多くの場合、フォールトトレラントは、システム内の部品を多重化することで実現されているが、むやみな部品の多重化は、システムのコストが上がるだけで耐故障化にとって非効率的なだけでなく、無駄な部品の多重化で安心してしまい、重要な部品の多重化漏れなどの致命的な設計ミスを引き起こす原因となりうる。特に、航空管制システムや原子力発電所などの安全性が最優先されるシステムで、このような想定外の設計ミスがあってはならない。そのため、どの部品がシステムの耐故障化に不可欠であるのかを把握し、その部品に対して多重化などの適切な対策をとることが重要である（非特許文献４）。
【０００４】
システムの脆弱性や耐故障化にとって重要な部品を特定(診断)するためには、様々な評価尺度を用いて、多様な観点から多状態システムを評価・解析する必要がある（非特許文献１）。
その評価・解析の中でも多状態システムにおける各状態の発生確率の評価が、高信頼なフォールトトレラントシステムの設計に不可欠であり（非特許文献２、３）、 これまでに様々な発生確率の評価・解析手法が提案されている。
【０００５】
しかし、提案されている多くの手法がマルコフモデルに基づいており（非特許文献５）、
その計算量はO(m3n)であるため、システムの状態数mやシステム内の部品数nが大きな大規模多状態システムの解析に、それらの手法は実用的ではない（非特許文献４）。そのため、近年、大規模多状態システムを解析するために提案された二分決定グラフ(BDD: Binary Decision Diagram)（非特許文献６、４、７、３）や多値決定グラフ(MDD: Multi-valued Decision Diagram)（非特許文献８、９、２）を用いた手法が注目を集めている。
【０００６】
多状態システムは、構造関数と呼ばれる多値関数とみなすことができるため、BDDやMDDによって多状態システムを表現でき、そのBDDやMDDを用いることで、各状態の発生確率を決定グラフ内の節点数に比例した計算量で効率良く求めることができる。BDDでは、多値関数として与えられた構造関数をワンホットエンコーディングなどで、一旦、二値関数の集合に変換してからシステムを表現しているため、二状態システムで確立された様々な解析手法を多状態システムに直接適用できるという利点がある（非特許文献３）。しかし二値関数の集合に変換すると二値変数の数や関数の数が増え、大きなBDDが必要になってしまうため、MDDを用いて与えられた構造関数をそのまま表現する方が自然であり、大規模多状態システムの表現に、より有効である。
【０００７】
なお本発明者らは、EVMDDを用いた多状態システムの解析方法について、既に出願している（特許文献１）。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特願２０１２−２５０４１号
【非特許文献】
【０００９】
【非特許文献１】J. E. Ramirez-Marquez andD.W.Coit, “Composite importance measures formulti-state systems with multi-state components,”IEEETrans. on  Reliability,Vol.54.No.3,pp.517-529,Sept,2005.
【非特許文献２】L.Xing and Y. Dai, “A new decision-diagram-based method for efficient analysis onmultistate systems,”IEEE Transactions on Dependableand Secure Computing, Vol.6,No.3, pp.161-174,2009.
【非特許文献３】X. Zang, D. Wang, H. Sun,and K.S.Trivedi, “A BDD-based algorithm for analysis ofmultistate systems with multistate components,”IEEETransactions on Computers, Vol.52,No.12,pp.1608-1618, Dec.2003.
【非特許文献４】Y.-R. Chang,S.Y.Amari,andS.-Y.Kuo,”Reliability evaluation of multi-state systemssubject to imperfect coverage using OBDD,”Proc. ofthe 2002 Pacific Rim International Symposiumon Dependable Computing (PRDC’02), pp. 193-200, 2002.
【非特許文献５】S. A.Doyle,J.B.Dugan, andF. A. Patterson-Hine,”A combinatorial approach tomodeling imperfect coverage,”IEEE Transactions onReliability, Vol. 44,No.1,pp.87-94,Mar.1995.
【非特許文献６】J.D.Andrews andS.J.Dunnett,”Event-tree analysis using binary decisiondiagrams,”IEEE Transactions on Reliability, Vol.49,No.2,pp.230-238, June 2000.
【非特許文献７】S. A. Doyle and J. B.Dugan,“Dependability assessment using binary decisiondiagrams (BDDs),”25th InternationalSymposium on Fault-Tolerant Computing (FTCS), pp.249-258, June 1995.
【非特許文献８】T.W.Manikas,M.A.Thornton,and D.Y.Feinstein,”Using multiple-valued logicdecision diagrams to model system threat probabilities,”41st International Symposium on Multiple-Valued Logic, pp. 263-267, May 2011.
【非特許文献９】L.Xing and J. B. Dugan,”Dependability analysis using multiple-valued decision diagrams,”Proc. of 6th International Conference on ProbabilisticSafety Assessment and Management, June 2002.
【非特許文献１０】S. Nagayama, T. Sasao,and J. T. Butler,”A systematic design method fortwo-variable numeric function generators using multiple-valued decisiondiagrams,”IEICE Trans. on Information and Systems, Vol. E93-D, No. 8, pp. 2059-2067, Aug. 2010.
【非特許文献１１】S. Nagayama and T. Sasao,”Complexities of graph-based representations forelementary functions,”IEEE Trans. on Computers, Vol. 58, No. 1, pp. 106-119, Jan. 2009.
【非特許文献１２】T.Sasao,SwitchingTheory for Logic Synthesis, Kluwer Academic Publishers 1999.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
近年の大規模かつ複雑な多状態システムの解析・診断では、システムをさらにコンパクトに表現できる決定グラフが求められている。多状態システムの構造関数は、多くの場合、単調増大関数である（非特許文献９）ため、EVMDD (Edge-Valued MDD：枝重み付けMDD)でコンパクトに表現することができる（非特許文献１０）。しかしながら、EVMDDを用いた多状態システムの解析や診断は、通常のMDDを用いた方法とは違い単純ではなく、その解析方法や診断方法はいまだ実現されていない。
【００１１】
本発明は、EMBDDを用いることにより、効率的な多状態システムの診断方法及び診断装置を提供するものである。すなわち、先に出願したEVMDDを用いた多状態システムの解析方法を利用した診断方法及び診断装置を提供するものである。
【課題を解決するための手段】
【００１２】
本発明に係る多状態システムの診断方法は、多状態システムの構造関数を表現する、重み付き枝を有する多値決定グラフ（EVMDD）と、システム内の各構成要素における各状態の発生確率Pc、診断するシステムの状態s、診断する構成要素xiとその状態 cを入力とし、条件付確率P(f = s | xi = c)を出力とする多状態システムの診断方法であって、以下のステップをEVMDDの根節点から再帰的に各節点vで実行し、根節点でのf = sにおける確率を答とすることを特徴とするものである。
ステップS1：EVMDDの読み込み処理。
ステップS2：ディスク又はキーから、各部品における各状態の発生確率、診断するシステムの状態sおよび部品xiとその状態cが入力される。
ステップS3：多状態システムの診断が行われる。これは再帰処理にてなされ、引数として、EVMDDの根節点、各状態の発生確率Pc、システムの状態s、部品xiとその状態cが使用され、結果（戻り値）としてシステムの各状態の条件付確率が得られる。
ステップS4：上記条件付確率が表示装置にて表示される。
【００１３】
本発明において、前記ステップS3における再帰処理は、以下のステップにて構成することができる。
ステップS3-1：訪れた節点vが訪問済みか否かを判断する。訪問済み（true）ならば、ステップS3-2へ進み、そうでなければ(false)、ステップS3-3へ進む。
ステップS3-2：節点vが表現する部分関数fvにおける各状態の発生確率を戻り値としてリターン。
ステップS3-3：節点vが終端節点か否かを判断する。終端節点Tならば(true)、ステップS3-4へ進み、そうでなければ(false)、ステップS3-5へ進む。
ステップS3-4：定数関数0における状態の発生確率Ps(fT = 0) = 1を戻り値としてリターン。
ステップS3-5：節点vの変数がxiか否かを判断する。変数がxiならば(true)、ステップS3-6へ進み、そうでなければ(false)、ステップS3-7へ進む。
ステップS3-6：xi = cの枝につながっている子節点ucだけに対して以下に示す部分処理A（ステップS3-6-1）を実行する。
ステップS3-7：節点vの全ての子節点ujに対して以下に示す部分処理B（ステップS3-7-1）を実行する。
ステップS3-8：節点vを訪問済みとし、計算で得られた各状態の発生確率を戻り値としてリターン。
【００１４】
前記部分処理Aは以下のステップからなる。
ステップS3-6-1：子節点ucを、部分EVMDDの根節点とした再帰処理を行うために、ステップS3-1に戻る。再帰処理からリターン後、次のステップS3-6-2へ進む。
ステップS3-6-2：ステップS3-6-1の処理で戻り値として得られた各状態suc に対して、以下の処理を繰り返す。
ステップS3-6-3：状態sucに枝の重みecを加えた状態の発生確率Ps(fv = suc + ec)と、ステップS3-6-1で得られた値との和をとり、それを新たな発生確率Ps(fv = suc + ec)とする。
ステップS3-6-4：ステップS3-6-1の処理で戻り値として得られた全ての状態に対してステップS3-6-3の処理が終わると、計算した発生確率を戻り値として、ステップS3-8へ進む。終了してなければ、次の状態に対して、ステップS3-6-2へ戻り、処理を続ける。
【００１５】
前記部分処理Bは以下のステップからなる。
ステップS3-7-1：全ての子節点ujに対して、以下の処理を繰り返す。
ステップS3-7-2：ujを部分EVMDDの根節点とした再帰処理を行うために、ステップS3-1に戻る。再帰処理からリターン後、次のステップS3-7-3へ進む。
ステップS3-7-3：ステップS3-7-2の処理で戻り値として得られた各状態sujに対して、以下の処理を繰り返す。
ステップS3-7-4：ステップS3-7-2で得られた確率Psに節点ujが選ばれる確率Pcをかける。
ステップS3-7-5：状態sujに枝の重みejを加えた状態の発生確率Ps(fv = suj + ej)と、ステップS3-7-4で得られた値との和をとり、それを新たな発生確率Ps(fv = suj + ej)とする。
ステップS3-7-6：ステップS3-7-2の処理で戻り値として得られた全ての状態に対してステップS3-7-4,S3-7-5の処理が終わると、ステップS3-7-7へ進み、終了してなければ、次の状態に対して、ステップS3-7-3へ戻り、処理を続ける。
ステップS3-7-7：引数として与えられた全ての子節点に対して、S3-7-2からS3-7-6の処理が終わると、計算した発生確率を戻り値として、ステップS3-8へ進む。終了してなければ、次の子節点に対して、ステップS3-7-1へ戻り、処理を続ける。
【００１６】
本発明は、多状態システムの構造関数を表現する、重み付き枝を有する多値決定グラフ（EVMDD）と、システム内の各構成要素における各状態の発生確率Pc、診断するシステムの状態s、診断する構成要素xiとその状態 cを入力とし、条件付確率P(f = s | xi = c)を出力とする多状態システムの診断装置であって、重み付き枝を有する多値決定グラフ（EVMDD）ファイル及び状態の発生確率ファイルを格納するディスクと、診断するシステムの状態及び診断する部品とその状態を入力する入力部と、解析診断部と、該解析診断部にて得られた結果を表示する表示部とを備え、前記解析診断部は、データ転送回路、前記ディスクから前記データ転送回路を介してEVMDDが書き込まれる第１メモリ、前記ディスクから前記データ転送回路を介して各部品の状態の発生確率が書き込まれる第２メモリ、前記第１及び第２メモリのデータの入出力、アクセス、再帰処理を制御する制御回路、該制御回路とともに再帰処理を行うためのスタックメモリ、各節点における状態の発生確率を格納する第３メモリ、前記制御回路にて制御され、前記第２メモリ及び前記第３メモリからのデータを入力して確率の計算を行うとともに計算結果を前記第３メモリに格納する実数加算・乗算器、計算結果を前記表示部に出力する計算結果出力回路よりなることを特徴とするものである。
【発明の効果】
【００１７】
本発明によれば、EVMDDを用いて多状態システムを表現し、そのEVMDD上でシステムを解析・診断するものであるため、システムの構造関数をコンパクトに表現することができる。さらに、その節点数の減少、従って計算量を減らすことができ、既存の診断方法より効率的な診断方法及び診断装置を実現することができる。
【図面の簡単な説明】
【００１８】
【図１】配電システムをモデル化した多状態システムを説明するための概略図である。
【図２】構造関数fを表現しているMDDの図である。
【図３】構造関数fを表現しているEVMDDの図である。
【図４】MDDに関する定理を証明するための図である。
【図５】EVMDDを用いた多状態システムの解析方法を説明するための図である。
【図６】本発明の実施形態に係る診断方法の全体を示すフローチャートである。
【図７】本発明の実施形態に係る診断方法の再帰処理部分を示すフローチャートである。
【図８】本発明の実施形態に係る診断方法の再帰処理部分の一部分（部分処理A）の処理を示すフローチャートである。
【図９】本発明の実施形態に係る診断方法の再帰処理部分の一部分（部分処理B）の処理を示すフローチャートである。
【図１０】本発明の実施形態に係る診断装置のブロック図である。
【図１１】EVMDDを用いた条件付確率の計算を説明するための図である。
【図１２】互いに独立した部品で構成される多状態システムのベイジアンネットワークを示す図である。
【発明を実施するための形態】
【００１９】
諸定義
本発明では、多状態システムとその構造関数及び構造関数の表現に用いるMDDを定義する。
【００２０】
多状態システムと構造関数
定義 １．多状態システムとは、システムの性能や信頼性などのレベルを状態として(通常は三つ以上の状態数で) 表現するシステムモデルである。多状態システムでは、システムの各構成要素(以下「部品」という)の性能や信頼性レベルも同様に状態としてモデル化される。
【００２１】
定義２．多状態システム全体の状態が、システムを構成している部品の状態の組合せだけで決定されると仮定すると、n個の部品から成る多状態システムは、n変数多値関数f(x1, x2,…,xn)
: R1 × R2 ×…× Rn→ Mとみなすことができる。ここで、各多値変数xi は状態数がri の部品を表現し、Ri = {0, 1,…, ri −1} はその部品の状態の集合である。同様に、M = {0, 1,…, m - 1} は、状態数がmのシステムの状態集合である。この多値関数fを多状態システムの構造関数という。
【００２２】
定義 ３．多値関数f(x1, x2,…,xn)が任意の変数xiにおいて、以下の性質を満たすとき、かつそのときに限り、fを単調増大関数という。
【数１】
2014099021.tif 000003
【００２３】
ただし∀α、β∈Ri、かつα ≦βである。
【００２４】
多くの応用分野において、多状態システムおよびその部品の状態には全順序関係があり、
システム内の部品の劣化や性能低下がシステム全体の劣化や性能低下をもたらす。そのため、最悪の状態に0、最良の状態にm −1またはri −1を割り当てることによって、多くの構造関数は、単調増大関数になる。
【００２５】
例１．配電システムをモデル化した多状態システムの例を図1に示す。この図で、発電所x1, x2, x3および変電所x4には電力供給量を表す三つの状態: 0(完全停止)、1(部分供給)、 2(完全供給)がある。そしてシステムには、停電になっている街の地域の割合を表す6つの状態: 0(全地域停電)、1(90%の地域停電)、2(60%の地域停電)、3(30%の地域停電)、4(10%の地域停電)、5(0%の地域停電)がある。
【００２６】
このように、各状態に昇順で値を割り当てることによって得られる構造関数fは、表１に示されているように、単調増大関数になる。
【表１】
2014099021.tif 000004
【００２７】
多値決定グラフ(MDD:
Multi-valued Decision Diagram)
定義 ４．多値決定グラフ(MDD: Multi-valued Decision Diagram)は、多値関数f を表現している根付きの非巡回有向グラフであり、多値関数にシャノン展開を繰り返し適用することで得られる。MDDは、関数値を表現する終端節点と、多値変数に値を割り当てることで得られるfの部分関数を表現する非終端節点から成る。各非終端節点は、変数値に対応する重み無しの枝を持ち、MDD内の多値変数には順序付けがされている(つまり、根から終端節点まで、どのパスを通っても同じ順序で変数が表れる)。各多値変数の定義域が異なってもよい関数を表現するMDDを、ヘテロジニアスMDDという。以下では、簡単のため、ヘテロジニアスMDDを単にMDDと略記する。
【００２８】
定義 ５．EVMDD
(Edge-Valued MDD) は、MDDを拡張したグラフであり、0を表現する一つの終端節点と、重み付きの枝を持った非終端節点から成る。ただし、枝の重みは整数値であり、0-枝の重みは0である。EVMDDで関数値は、終端節点ではなく、根から終端節点まで辿った際に通過する枝の重みの和として表現されている。
【００２９】
例 ２．例1の構造関数fを表現している通常のMDDとEVMDDを図２及び図３にそれぞれ示す。読みやすくするために、MDDの一部の終端節点は共有されない状態で図示している。 
【００３０】
構造関数を表現するMDDとEVMDD
次に、構造関数を表現するMDDとEVMDDの節点数における上界を導出する。 説明の簡単化のために、以下の定理では統一的に、多状態システム内の全ての部品xiが同じ状態数r
(すなわち、全ての多値変数xiが同じ定義域)を持つものと仮定する。しかし、各多値変数xiがそれぞれ異なる定義域を持つ場合への一般化は容易である。
【００３１】
定理１．構造関数を表現するMDDの節点数の上界UBMは以下の式で得られる。 
【数２】
2014099021.tif 000005
【００３２】
ここで、lは、rn-l ≧ mrlを満たす最大の整数、mはシステムの状態数、nはシステム内の部品数、rは部品の状態数を表している。
【００３３】
この証明は以下の通りである。
図４に示されるように、MDDを２分割する。このとき、下部ではl変数多値関数が表現され、上部では、それらの中から一つを選択する関数が表現されている。上部は、完全多分木のとき節点数が上限に達し、そのときの節点数は、初項を１、公比をrとした等比数列の和1 + r + r2 + … + rn-l-1で得られるため、次の式となる。
【数３】
2014099021.tif 000006
【００３４】
下部は全てのl変数多値関数が表現されたとき、節点数が最大となる。全てのl変数多値関数の数は、次の数式で表される。
【数４】
2014099021.tif 000007
【００３５】
各関数が終端節点を含む１つの節点で表現されるため、これが下部での最大節点数になる。数式３、４よりMDDの節点数は高々
【数５】
2014099021.tif 000008
【００３６】
となり、下部で表現可能な多値関数の数は、上部で選択可能な関数の数rn-lを超えないため、次の関係を得る。
【数６】
2014099021.tif 000009
【００３７】
定理1は、MDDの上界はmとn、及びrの値だけに依存し、構造関数の単調性(形状)には無関係に定まるということを示している。この上界UBMは任意の多値関数におけるMDDの上界であるが、MDDのように複数の終端節点をもつ決定グラフでは関数の単調性をうまく表現することができないため、UBMは単調関数におけるタイトな上界といえる。
【００３８】
先に述べたように、多くの応用分野で、構造関数は通常、単調増大関数になるため、関数の単調性をうまく表現できる、単調関数に適した決定グラフが、構造関数の表現には望ましい。 EVMDDは単調関数をコンパクトに表現できることが知られている（非特許文献１０）ため、EVMDDは多くの構造関数の表現に適しているといえる。
【００３９】
定義
６．N0を非負整数の集合とし、p を N0の要素としたとき、0 ≦f(X+1)−f(X) ≦pかつf(0)=0を満たす整数関数f(X):N0→N0をMp単調増大関数という。すなわち、Mp単調増大関数f(X)は、f(0)=0であり、なおかつ、Xが1増えると関数値fが高々p増える関数である。このときpを増加値と呼ぶ。
【００４０】
単調な多値関数は、多値変数xiの集合を
【数７】
2014099021.tif 000010
【００４１】
のように、r値ベクトルとみなすことによって、Mp単調増大関数に変換することができ、 Mp単調増大関数と同じ複雑さのEVMDDで表現することができる（非特許文献１０）。そのため、単調な多値関数から変換して得られたMp単調増大関数を表現するEVMDDの上界を次の定理で示す。
【００４２】
定理 ２．単調な多値関数から変換して得られたMp単調増大関数を表現するEVMDDの節点数の上界UBEは以下の式で得られる。
【数８】
2014099021.tif 000011
ここで、lはrn-l ≧ (p + 1)rl-1を満たす最大の整数、nは元の多値関数での多値変数の数、pは増加値、rは部品の状態数を表す。
この証明は、二分決定グラフ(EVBDD)における証明（非特許文献１１）をMDDに拡張することで、同様に証明できる。
【００４３】
定理２は、EVMDDの上界はシステムの状態数mではなく、増加値pの値に依存するということを示している。そのため、システムの状態数mが多くても、増加値pの値が小さければEVMDDの節点数は少ない。今後、システムはさらに複雑になり、状態数mは増えることが容易に予想できるが、そのような複雑なシステムの表現に、通常のMDDを用いると多くの節点数が必要になってしまう。一方、EVMDDは、そのようなシステムでも、増加値pの値が小さければ、コンパクトに表現できる。
【００４４】
増加値pの値は、部品の劣化に対するシステム全体の劣化の度合を表しているため、システムが複雑になり状態数が増えても、増加値pの値が今後、急激に増えることは考えにくい。むしろ技術の進歩により、部品のわずかな性能劣化がシステム全体の性能に影響しないようになり、小さい値に抑えられる可能性が高い。そのため、EVMDDは今後の複雑なシステムの表現により適している。
【００４５】
MDDを用いた解析法とEVMDDを用いた解析法
次に、多状態システムの解析問題を定式化し、その後、その問題をEVMDDを用いて解くアルゴリズムについて説明する。
【００４６】
定義 ７．多状態システムfの状態がsになる確率をPs(f = s)、ただし、s∈ {0, 1,…, m-1}で表す。同様に、システム内の部品xiの状態がcになる確率をPc(xi = c)、ただし、c∈ {0,1,…,ri −1}で表す。
【００４７】
多状態システムの構造関数fとシステム内の各部品がとる各状態の確率Pc(xi = c)が与えられたとき、与えられた多状態システムにおける各状態の発生確率Ps(f = s)を求める。ただし、各部品の状態は他の部品の状態とは独立に発生するものとする。
【００４８】
MDDを用いた解析方法
この場合、MDDの平均パス長を算出するために導入された節点通過確率を用いて効率良く解くことができる。
【００４９】
定義８．MDDにおいて、根から終端節点までの経路をパスという。パスが節点viを通過する確率を節点通過確率とよび、NTP(vi)で表す。
【００５０】
構造関数を表現するMDDの終端節点は多状態システムの状態を表現しているため、終端節点の節点通過確率はシステムの状態の発生確率に等しい。節点通過確率は、MDDの各節点を幅優先順で一度だけ訪れれば求まるため、この解析法の計算量はO(NM)となる。ただしNMはMDDの節点数を表す。計算量がO(NM)である他の既存解析手法も、節点通過確率という用語は用いていないが、同様の方法で多状態システムを解析している（非特許文献８、９、２）。
【００５１】
例３．この例では、図２のMDDにおける各節点の節点通過確率を求める。ただし、簡単のために、各部品での状態の発生確率は全て等しい1/3と仮定する。まず最初に、根節点は全てのパスが必ず通過するため、根節点v1の節点通過確率NTP(v1)=1が求まる。次に、幅優先順に節点を訪問し、NTP(v2)=NTP(v1)×1/3、NTP(v3)=NTP(v1)×1/3、NTP(v4)=NTP(v1)×1/3を計算する。同様に、節点通過確率をトップダウン的に計算することで、NTP(v5)=NTP(v2)/3、NTP(v6)=NTP(v2)/3、NTP(v7)=NTP(v4)/3を得る。節点v8では分岐が再収斂しているので、親節点から受け取る節点通過確率が全て積算され、NTP(v8)=2×NTP(v5)/3+NTP(v6)/3となる。最終的に終端節点の節点通過確率NTP(0)=29/81、NTP(1)=14/81、NTP(2)=14/81、NTP(3)=1/9、NTP(4)=10/81、NTP(5)=5/81が得られる。 
以上の解析から、この配電システムでは、約36%（NTP(0)=29/81）の確率で街の全地域が停電になることがわかる。  
【００５２】
EVMDDを用いた解析方法
EVMDDで関数値は、終端節点ではなく、枝の重みの和によって表現されている。そのため、 MDDのように節点通過確率だけを用いて前述の問題を解くことができず、新たな別の解析方法が必要になる。そこで、各部分関数における確率を順次、ボトムアップに計算する方法を提案する。
本実施形態で提案する解析アルゴリズムを以下に示す。
入力：多状態システムの構造関数を表現するEVMDDとシステム内の各部品における各状態の発生確率Pc(xi = c)
出力：多状態システムにおける各状態の発生確率Ps(f = s)
手順：以下のステップによる処理をEVMDDの根節点から再帰的に各節点で実行する。
S1.訪れた節点vが訪問済みならば、節点vが表現する部分関数fvにおける各状態の発生確率を戻り値としてリターン。そうでなければ、次のステップS2へ。
S2.節点vが終端節点Tならば、定数関数0における状態の発生確率Ps(fT = 0) = 1を戻り値としてリターン。そうでなければ、次のステップS3へ。
S3.全ての子節点uiを訪問し、子節点uiが表現する部分関数fui における各状態の発生確率を求める。
S4.ステップS3で得られた部分関数における各状態の発生確率Ps(fui = s)に、部品xiがその部分関数(子節点)を選択する確率Pc(xi = c)をかける。
S5.子節点uiでの各関数値fui = sは、枝の重みeiのため、親節点vではfv = s+eiとなる。そのため、ステップS4で得られた確率Ps(fui = s)×Pc(xi=c)は、Ps(fv = s+ei) の確率として加えられ、fvの関数値毎に積算される。
S6.積算された確率を節点vの親節点に返す。
【００５３】
このアルゴリズムは、根から深さ優先順に各節点を一度だけ訪れ、各節点で表現されている部分関数を再帰的に解析する。各節点で表現されている部分関数における状態の発生確率は、子節点で表現されている部分関数での発生確率を一つにまとめることによって得られるため、根節点でまとめられた発生確率が、求めるシステムでの各状態の発生確率となる。各節点を一度だけ訪問すれば、システムの解析が終わるので、提案アルゴリズムの計算量はEVMDDの節点数NE に比例したO(NE)となる。
【００５４】
例４．この例では、 図３のEVMDDを用いて多状態システムにおける各状態の発生確率を求める。先の例と同じく、各部品での状態の発生確率を全て1/3と仮定する。
【００５５】
まず、終端節点Tで定数関数0における状態の発生確率Ps(fT = 0) = 1を得る。次に、図５の節点v1での部分関数における確率を算出する。この節点の子節点は全て終端節点であり、重みが1の枝が二本あるので下記数式となり、
【数９】
2014099021.tif 000012
【００５６】
節点v1での状態fv1 = 1の発生確率は、下記数式となる。
【数１０】
2014099021.tif 000013
【００５７】
状態fv1 = 0の発生確率は、節点v1の0-枝だけから得られるため、その発生確率はPs(fv1
= 0) = 1/3となる。そのため、節点v1での確率は、図５に示されているように、Ps(fv1 = 0)=1/3、Ps(fv1 = 1)= 2/3になる。
【００５８】
節点v2では、終端節点と節点v1での確率がそれぞれ1/3倍されたあと、各関数値毎に積算され、Ps(fv2=0)=5/9、Ps(fv2=1)=4/9が得られる。同じ計算を各節点で深さ優先順に繰り返すことによって、最終的に根節点での6状態の発生確率Ps(f = 0) = 29/81、 Ps(f = 1) = 14/81、Ps(f = 2) = 14/81、Ps(f = 3) = 1/9、Ps(f = 4) =10/81、Ps(f = 5) = 5/81が得られ、この結果は、例3でMDDを用いて得た結果と一致する。
【００５９】
この方法は、構造関数が単調増大関数ならば、 EVMDDの節点数NEはより小さくなるため、 計算時間もより短くなるが、構造関数が単調増大関数でない場合も同様に、この方法を適用することができる。
【００６０】
実験結果   
前述の解析方法の効率を示すために、様々な構造関数を用いて実験を行った。しかし、残念ながらベンチマークとなる多状態システムの構造関数は、入手できなかった。そのため、多くの構造関数が単調増大関数であることから、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状態システムの実験結果を表２に示す。
【表２】
2014099021.tif 000014
【００６１】
表２から、全ての構造関数においてEVMDDの節点数はMDDよりも少ないことがわかる。 特に、システムの状態数mが大きくなるにつれ、EVMDDの節点数はMDDよりも、はるかに少なくなる。今後、システムはさらに複雑になり、状態数mは増えると予想されるため、サイズが状態数に依存しないEVMDDの方が、より有効であるといえる。しかし、状態数mがとても小さいシステムには、計算時間がより短く、節点数も十分に少ないMDDの方が適している。表２で、m = 3のとき、EVMDDの節点数はMDDの節点数よりも2節点少ないだけである。これは終端節点が2つ減っただけなので、このような状態数の少ないシステムにEVMDDを用いるのは効果的とはいえない。
【００６２】
計算時間に関しても、EVMDDを用いた方法は、MDDを用いた既存方法に匹敵する時間でシステムを解析することができる。そのため、EVMDDは、文字通り多くの状態を持つ多状態システムのコンパクトな表現と効率的な解析に適していると結論付けることができる。
【００６３】
EVMDDを用いた診断方法
次に、EVMDDを用いて、システム障害を引き起こした原因として最も可能性の高いものを、 前述の解析方法で得られたシステムの確率から推測する方法について説明する。本実施形態では、そのような原因を条件付き確率(事後確率ともいわれる)を計算することで推測する。
【００６４】
定義 ９．条件付き確率とは、ある事象Bが起こったという条件の下で別の事象Aが起こる確率であり、P(A | B)と表記する。
この定義において、事象Bをシステムの状態、Aを部品の状態とすると、条件付き確率は、 部品の状態Aがシステムの状態Bの原因となる確率とみなすことができる。そして、その条件付き確率から最も可能性の高い原因を推測することで、多状態システムの診断を行う。
条件付き確率は、ベイズの定理により、以下のように計算することができる。
【数１１】
2014099021.tif 000015
【００６５】
ベイジアンネットワークは、この定理に基づき、様々な事象の原因を推測している。
先に述べたように、多状態システムの診断では、Aは部品の状態(xi = c)、Bはシステムの状態(f = s)なので、ベイズの定理は以下のように書き換えることができる。
【数１２】
2014099021.tif 000016
【００６６】
この式で、Pc(xi = c)は予め与えられ、Ps(f = s)は前述の解析方法で得られるため、P(f = s | xi = c)さえ得られれば、P(xi = c | f=s)を求めることができる。そのため、本実施形態では、条件付き確率P(f = s | xi = c)を効率よく計算するためのアルゴリズムを提案する。
【００６７】
EVMDDを用いて条件付き確率を計算する診断アルゴリズム
条件付き確率の定義から、P(f = s | xi = c)は、xi = cのときのシステムがf = sである確率に等しい。そのため、xi = cにおけるfの制限(コファクタ)（非特許文献１２）を取り、そのコファクタの関数値がsとなる確率を計算することで、条件付き確率P(f = s | xi = c)を求めることができる。コファクタは決定グラフを用いることで、非常に効率良く求めることができるため、求めたコファクタに前述のアルゴリズムを適用することで、P(f = s | xi = c)を効率良く計算することができる。
EVMDDを用いて条件付き確率P(f = s | xi = c)を計算するアルゴリズムを以下に示す。
【００６８】
図６は、その全体のフローチャートを示し、次のようなステップで処理される。
ステップS1：EVMDDの読み込み処理。
ステップS2：ディスク１（図１０）又はキーボード７（図１０）から、各部品における各状態の発生確率Pc、診断するシステムの状態sおよび部品xiとその状態cが入力される。
ステップS3：多状態システムの診断が行われる。これは再帰処理にてなされ、引数として、EVMDDの根節点、各状態の発生確率Pc、システムの状態s、部品xiとその状態cが使用され、結果（戻り値）としてシステムの各状態の条件付確率が得られる。
ステップS4：上記条件付確率が表示装置にて表示される。
【００６９】
図７を参照して、ステップS3における再帰処理の詳細を説明する。
ステップS3-1：訪れた節点vが訪問済みか否かを判断する。訪問済み（true）ならば、ステップS3-2へ進み、そうでなければ(false)、ステップS3-3へ進む。
ステップS3-2：節点vが表現する部分関数fvにおける各状態の発生確率を戻り値としてリターン。
ステップS3-3：節点vが終端節点か否かを判断する。終端節点Tならば(true)、ステップS3-4へ進み、そうでなければ(false)、ステップS3-5へ進む。
ステップS3-4：定数関数0における状態の発生確率Ps(fT = 0) = 1を戻り値としてリターン。
ステップS3-5：節点vの変数がxiか否かを判断する。変数がxiならば(true)、ステップS3-6へ進み、そうでなければ(false)、ステップS3-7へ進む。
ステップS3-6：xi = cの枝につながっている子節点ucだけに対して以下に示す部分処理A（ステップS3-6-1）を実行する。
ステップS3-7：節点vの全ての子節点ujに対して以下に示す部分処理B（ステップS3-7-1）を実行する。
ステップS3-8：節点vを訪問済みとし、計算で得られた各状態の発生確率を戻り値としてリターン。
【００７０】
前記部分処理Aについて、図８を参照して説明する。
ステップS3-6-1：子節点ucを、部分EVMDDの根節点とした再帰処理を行うために、ステップS3-1に戻る。再帰処理からリターン後、次のステップS3-6-2へ進む。
ステップS3-6-2：ステップS3-6-1の処理で戻り値として得られた各状態suc に対して、以下の処理を繰り返す。
ステップS3-6-3：状態sucに枝の重みecを加えた状態の発生確率Ps(fv = suc + ec)と、ステップS3-6-1で得られた値との和をとり、それを新たな発生確率Ps(fv = suc + ec)とする。
ステップS3-6-4：ステップS3-6-1の処理で戻り値として得られた全ての状態に対してステップS3-6-3の処理が終わると、計算した発生確率を戻り値として、ステップS3-8へ進む。終了してなければ、次の状態に対して、ステップS3-6-2へ戻り、処理を続ける。
【００７１】
前記部分処理Bについて、図９を参照して説明する。
ステップS3-7-1：全ての子節点ujに対して、以下の処理を繰り返す。
ステップS3-7-2：ujを部分EVMDDの根節点とした再帰処理を行うために、ステップS3-1に戻る。再帰処理からリターン後、次のステップS3-7-3へ進む。
ステップS3-7-3：ステップS3-7-2の処理で戻り値として得られた各状態sujに対して、以下の処理を繰り返す。
ステップS3-7-4：ステップS3-7-2で得られた確率Psに節点ujが選ばれる確率Pcをかける。
ステップS3-7-5：状態sujに枝の重みejを加えた状態の発生確率Ps(fv = suj + ej)と、ステップS3-7-4で得られた値との和をとり、それを新たな発生確率Ps(fv = suj + ej)とする。
ステップS3-7-6：ステップS3-7-2の処理で戻り値として得られた全ての状態に対してステップS3-7-4,S3-7-5の処理が終わると、ステップS3-7-7へ進み、終了してなければ、次の状態に対して、ステップS3-7-3へ戻り、処理を続ける。
ステップS3-7-7：引数として与えられた全ての子節点に対して、S3-7-2からS3-7-6の処理が終わると、計算した発生確率を戻り値として、ステップS3-8へ進む。終了してなければ、次の子節点に対して、ステップS3-7-1へ戻り、処理を続ける。
【００７２】
このアルゴリズムは、P(f = s|xi = c)だけでなく、多状態システムの全ての状態における条件付き確率P(f=0|xi=c),P(f=1|xi=c),..,P(f=m-1|xi=c)を同時に求めることができるため、部品の状態xi=cがシステムに与える影響を効率良く診断することができる。また、このアルゴリズムは前述の解析アルゴリズムを基にしているため、コファクタを計算する処理以外は、解析アルゴリズムとほぼ同じ処理である。そのため、その計算量も解析アルゴリズム同様、EVMDDの節点数NEに比例したO(NE)になる。
【００７３】
診断装置
図１０は、図６に示すステップS1〜S4を実行する診断装置を示す。図中、１は、EVMDDファイル及び状態の発生確率ファイルを格納するディスク、２は、解析診断部、３は、得られた結果を表示する表示部である。これらはすべてコンピュータにて構成される。
【００７４】
解析診断部２において、４は、データ転送回路、５は、EVMDDを格納する第１メモリ、６は、各部品の状態の発生確率を格納する第２メモリで、これら第１、第２メモリ５、６にデータ転送回路４を介して、ディスク１から、それぞれEVMDD及び発生確率が書き込まれる。７は、診断するシステムの状態及び診断する部品とその状態を入力する入力部となるキーボードで、これらの入力信号もまたデータ転送回路４を介して第１、第２メモリ５、６へ送信される。
【００７５】
８は、第１、第２メモリ５、６のデータ入出力、アクセス及び再帰処理を制御する制御回路、９は、再帰処理を行うためのスタックメモリ、１０は、各節点における状態の発生確率を格納する第３メモリ、１１は、第２、第３メモリ６、１０からのデータを入力して確率の計算を行う実数加算・乗算器で、計算結果は、第３メモリ１０へ格納される。第３メモリ１０の発生確率情報は、計算結果出力回路１２を介して表示部３にて表示される。実数加算・乗算器１０及び計算結果出力回路１２は制御回路８にて制御される。
【００７６】
前述したステップS1、S2の処理は、ディスク１、キーボード７及びデータ転送回路４にて、またステップS3の処理は、制御回路８及びスタックメモリ９にて実行され、ステップS4の結果は表示部３にてなされる。
【００７７】
例 ５．この例では、図３に示すEVMDDを用いてx4 = 0における多状態システムの各状態の条件付き確率を求める。先の例と同じく、各部品での状態の発生確率を全て1/3と仮定する。まず、終端節点Tでの状態の発生確率Ps(fT = 0) = 1を得る。次に、図１１の節点v1での部分関数における確率を算出する。この節点の変数はx4なので、x4 = 0を意味する0-枝につながった子節点のみを訪問する。この子節点は終端節点なので、v1での確率は、図１１に示されているように、Ps(fv1 = 0)=1となる。
【００７８】
節点v2では、終端節点とv1での確率がそれぞれ1/3倍されたあと、各関数値毎に積算され、Ps(fv2=0)=1が得られる。同じ計算を各節点で深さ優先順に繰り返すことによって、最終的に根節点でPs(f=0)=1,Ps(f=1)=0,Ps(f=2)=0,Ps(f=3)=0,Ps(f=4)=0,Ps(f=5)=0が得られ、P(f=0|x4=0)=1となる。数式１２のベイズの定理より、下記数式が得られ、これから、変電所の停止(x4 = 0)が街の全地域停電(f =0)の原因となる確率は約93%であることがわかる。
【数１３】
2014099021.tif 000017
【００７９】
他の部品(x1, x2, x3)の各状態についても同様の診断を行うことで、この多状態システムでは、直観通り、変電所の停止が街の全地域停電の原因として最も確率が高いことがわかる。そのため、このシステムの耐故障性の向上には、変電所の多重化などによる耐故障性の改善が最も有効であることがわかる。 
【００８０】
ベイジアンネットワークとの比較
ベイジアンネットワークは、各部品を頂点で表現し、部品とシステムの因果関係を辺で表現した有向グラフであり、システムの解析や診断にしばしば利用されているベイジアンネットワーク上でシステムの解析(各状態の発生確率の計算)は、以下の式で行われる。
【数１４】
2014099021.tif 000018
【００８１】
ここで、Rnは各変数xiへの値の割り当てc の集合を意味し、P(f = s, x1, x2,…,xn)は、 f =sと(x1,x2,…,xn)=c=(c1,c2,…,cn)がどちらも起こる同時確率 (結合確率とも言う) を意味している。本実施形態で対象としている多状態システムでは、全ての部品が互いに独立しているので、それをベイジアンネットワークで表現すると図１２に示すようになり、同時確率P(f =s,x1=c1,x2=c2,…,xn=cn)は以下の式で求められる。
【数１５】
2014099021.tif 000019
【００８２】
この式において、fはx1, x2,…, xnの関数なので、式内の条件付き確率P(f = s| x1, x2,…,xn)は、以下の数式で求められる。
【数１６】
2014099021.tif 000020
【００８３】
これにより、多状態システムの解析(数式１４の計算)は、f = sとなる入力ベクトルc ∈ Rnの確率を積算することで行われ、その計算量は、部品数の指数関数O(rn)となる。
【００８４】
多状態システムの診断は、システムの解析結果Ps(f = s)を用いて数式１２のベイズの定理で行われるが、ベイジアンネットワークを用いた多くの診断方法が、ベイズの定理内の条件付き確率P(f = s | xi = c)は与えられているものとして診断を行なっている。しかし、P(f = s | xi = c)が常に与えられているとは限らず、またそれを求める計算も容易ではない。
【００８５】
それに対し、本発明に係るEVMDDを用いた診断方法では、P(f=s|xi=c)が与えられていなくても、前述したアルゴリズムにより効率良く計算でき、数式１２のベイズの定理により診断を行うことができる。本発明診断方法は、解析(Ps(f = s)の計算)も診断(P(f = s|xi=c)の計算)もどちらもO(NE)の計算量だけを要するため、解析のみでもO(rn)を要するベイジアンネットワークに基づく従来方法よりも明らかに効率が良いことがわかる。
【００８６】
本発明では、全ての部品が互いに独立であると仮定したが、相互依存の部品で構成されている多状態システムも同様に、MDDベースの方法で効率良く解析できる。
【００８７】
結論
本発明は、システムの解析結果から多状態システムをEVMDDを用いて効率的に診断する方法を提供するものであり、この診断方法では、システムの状態が枝の重みの和として表現されているため、通常のMDDを用いた既存の手法よりもやや複雑になるが、実際の計算時間は、既存手法に匹敵するものである。これは、本発明診断方法の計算量が漸近的にEVMDDの節点数に比例し、EVMDDの節点数が通常のMDDよりも少ないことに起因する。多くの状態を持つシステムではEVMDDの節点数がMDDよりも、はるかに小さくなるため、この方法は、そのようなシステムに対して特に有効である。EVMDDは、構造関数が単調でないとしても、そのサイズがMDDより大きくなることはない。そのため、この方法は、多様な構造関数に対して有効であるといえる。また、本発明に係る診断方法では、システム障害を引き起こした原因として最も可能性の高いものを、現在のシステムの解析・診断に広く利用されているベイジアンネットワークに基づく手法よりも効率良く推測することができる。
【産業上の利用可能性】
【００８８】
本発明は、水道、ガス、電力等の供給システム、コンピュータサーバ、電話通信網等に利用して有用である。
【符号の説明】
【００８９】
１          ディスク
２          解析診断部
３          表示部
４          データ転送回路
５          第１メモリ
６          第２メモリ
７          キーボード
８          制御回路
９          スタックメモリ
１０        第３メモリ
１１          実数加算・乗算器
１２          計算結果出力回路
【図２】
2014099021.tif 000021
【図３】
2014099021.tif 000022
【図４】
2014099021.tif 000023
【図８】
2014099021.tif 000024
【図１２】
2014099021.tif 000025
【図１】
2014099021.tif 000026
【図５】
2014099021.tif 000027
【図６】
2014099021.tif 000028
【図７】
2014099021.tif 000029
【図９】
2014099021.tif 000030
【図１０】
2014099021.tif 000031
【図１１】
2014099021.tif 000032