(57)【要約】    【課題】予め与えられた変数の中から所定の複数の制約条件を充足する制約充足解を求める制約充足問題において、制約充足解が存在しない場合の原因を特定すること。    【解決手段】制約条件管理モジュールは、制約条件データベース１から全ての制約条件を読み出し、優先順位が最上位の制約条件のみを要素として含む部分集合を筆頭とし、これに残りの制約条件を優先順位の高い順に１つずつ要素として追加してなる制約条件の部分集合を全て作成し、各制約条件の部分集合の制約充足解の探索を制約充足エンジン４に実行させ、前記制約充足エンジン４における探索の実行結果から制約充足解が存在しない部分集合のうち要素数が最小の部分集合を特定し、該要素数が最小の部分集合内で優先順位が最下位の制約条件を特定し、これを制約充足問題における解が存在しない原因として特定する。【選択図】図１
2006004156.tif 000002
【特許請求の範囲】
【請求項１】
予め与えられた変数の中から所定の複数の制約条件を充足する制約充足解を求める制約充足問題における解が存在しない場合の原因を特定する原因特定方法であって、
所定の複数の制約条件及び原因特定のための各制約条件の優先順位を保持する制約条件データベースと、変数及びその変域を保持する変数変域データベースと、制約条件を充足する制約充足解の探索を変数変域データベースに保持された変数の変域において実行する制約充足エンジンとを用い、
前記制約条件データベース、変数変域データベース及び制約充足エンジンを制御する制約条件管理モジュールが、
制約条件データベースから全ての制約条件を読み出し、優先順位が最上位の制約条件のみを要素として含む部分集合を筆頭とし、これに残りの制約条件を優先順位の高い順に１つずつ要素として追加してなる制約条件の部分集合を全て作成するステップと、
前記各制約条件の部分集合の制約充足解の探索を制約充足エンジンに実行させるステップと、
前記制約充足エンジンにおける探索の実行結果から制約充足解が存在しない部分集合のうち要素数が最小の部分集合を特定し、該要素数が最小の部分集合内で優先順位が最下位の制約条件を特定し、これを制約充足問題における解が存在しない原因として特定するステップとを含む
ことを特徴とする原因特定方法。
【請求項２】
予め与えられた変数の中から所定の複数の制約条件を充足する制約充足解を求める制約充足問題における解が存在しない場合の原因を特定する原因特定方法であって、
所定の複数の制約条件及び原因特定のための各制約条件の優先順位を保持する制約条件データベースと、変数及びその変域を保持する変数変域データベースと、制約条件を充足する制約充足解の探索を変数変域データベースに保持された変数の変域において実行する制約充足エンジンとを用い、
前記制約条件データベース、変数変域データベース及び制約充足エンジンを制御する制約条件管理モジュールが、
制約条件データベースから所定の複数の制約条件のうち優先順位が最下位の制約条件を除く全ての制約条件を読み出し、優先順位が最上位の制約条件のみを要素として含む部分集合を筆頭とし、これに残りの制約条件を優先順位の高い順に１つずつ要素として追加してなる制約条件の部分集合を全て作成するステップと、
前記各制約条件の部分集合の制約充足解の探索を制約充足エンジンに実行させるステップと、
前記制約充足エンジンにおける探索の実行結果から制約充足解が存在しない部分集合のうち要素数が最小の部分集合を特定し、該要素数が最小の部分集合内で優先順位が最下位の制約条件を特定し、これを制約充足問題における解が存在しない原因として特定し、前記制約充足エンジンにおける探索の実行結果から制約充足解が全ての部分集合で存在する場合は制約条件データベース中で優先順位が最下位の制約条件を制約充足問題における解が存在しない原因として特定するステップとを含む
ことを特徴とする原因特定方法。
【請求項３】
予め与えられた変数の中から所定の複数の制約条件を充足する制約充足解を求める制約充足問題における解が存在しない場合の原因を特定する原因特定方法であって、
所定の複数の制約条件及び原因特定のための各制約条件の優先順位を保持する制約条件データベースと、変数及びその変域を保持する変数変域データベースと、制約条件を充足する制約充足解の探索を変数変域データベースに保持された変数の変域において実行する制約充足エンジンとを用い、
前記制約条件データベース、変数変域データベース及び制約充足エンジンを制御する制約条件管理モジュールが、
制約条件データベースから優先順位が最上位の制約条件を読み出し、当該最上位の制約条件のみを含む制約条件の部分集合を作成する第１のステップと、
制約条件の部分集合の制約充足解の探索を制約充足エンジンに実行させる第２のステップと、
前記探索の実行結果が解有りか解無しかを判定する第３のステップと、
実行結果が解無しであれば直前に制約条件データベースから読み出した制約条件を制約充足問題における解が存在しない原因として特定する第４のステップと、
実行結果が解有りであれば制約条件データベースから読み出していない制約条件が優先順位最下位の制約条件のみであるか否かを判定する第５のステップと、
制約条件データベースから読み出していない制約条件が優先順位最下位の制約条件のみであれば当該最下位の制約条件を制約充足問題における解が存在しない原因として特定する第６のステップと、
制約条件データベースから読み出していない制約条件が優先順位最下位の制約条件のみでなければ制約条件データベースから次に優先順位の高い制約条件を読み出し、前記制約条件の部分集合に追加して新たな制約条件の部分集合を作成し、第２のステップに戻る第７のステップとを含む
ことを特徴とする原因特定方法。
【請求項４】
請求項１乃至３いずれか記載の原因特定方法において、前記に加え、
変数変域データベースに保持された変数の変域をさらに限定するための外部条件を保持する外部条件保持部を用い、
制約充足エンジンは制約条件を充足する制約充足解の探索を変数変域データベースに保持された変数の変域のうち前記外部条件によってさらに限定された変域において実行する
ことを特徴とする原因特定方法。
【請求項５】
予め与えられた変数の中から所定の複数の制約条件を充足する制約充足解を求める制約充足問題における解が存在しない場合の原因を特定する原因特定装置であって、
所定の複数の制約条件及び原因特定のための各制約条件の優先順位を保持する制約条件データベースと、
変数及びその変域を保持する変数変域データベースと、
制約条件を充足する制約充足解の探索を変数変域データベースに保持された変数の変域において実行する制約充足エンジンと、
制約条件データベースから全ての制約条件を読み出し、優先順位が最上位の制約条件のみを要素として含む部分集合を筆頭とし、これに残りの制約条件を優先順位の高い順に１つずつ要素として追加してなる制約条件の部分集合を全て作成し、各制約条件の部分集合の制約充足解の探索を制約充足エンジンに実行させ、当該制約充足エンジンにおける探索の実行結果から制約充足解が存在しない部分集合のうち要素数が最小の部分集合を特定し、該要素数が最小の部分集合内で優先順位が最下位の制約条件を特定し、これを制約充足問題における解が存在しない原因として特定する制約条件管理モジュールとを備えた
ことを特徴とする原因特定装置。
【請求項６】
予め与えられた変数の中から所定の複数の制約条件を充足する制約充足解を求める制約充足問題における解が存在しない場合の原因を特定する原因特定装置であって、
所定の複数の制約条件及び原因特定のための各制約条件の優先順位を保持する制約条件データベースと、
変数及びその変域を保持する変数変域データベースと、
制約条件を充足する制約充足解の探索を変数変域データベースに保持された変数の変域において実行する制約充足エンジンと、
制約条件データベースから所定の複数の制約条件のうち優先順位が最下位の制約条件を除く全ての制約条件を読み出し、優先順位が最上位の制約条件のみを要素として含む部分集合を筆頭とし、これに残りの制約条件を優先順位の高い順に１つずつ要素として追加してなる制約条件の部分集合を全て作成し、各制約条件の部分集合の制約充足解の探索を制約充足エンジンに実行させ、当該制約充足エンジンにおける探索の実行結果から制約充足解が存在しない部分集合のうち要素数が最小の部分集合を特定し、該要素数が最小の部分集合内で優先順位が最下位の制約条件を特定し、これを制約充足問題における解が存在しない原因として特定し、前記制約充足エンジンにおける探索の実行結果から制約充足解が全ての部分集合で存在する場合は制約条件データベース中で優先順位が最下位の制約条件を制約充足問題における解が存在しない原因として特定する制約条件管理モジュールとを備えた
ことを特徴とする原因特定装置。
【請求項７】
予め与えられた変数の中から所定の複数の制約条件を充足する制約充足解を求める制約充足問題における解が存在しない場合の原因を特定する原因特定装置であって、
所定の複数の制約条件及び原因特定のための各制約条件の優先順位を保持する制約条件データベースと、
変数及びその変域を保持する変数変域データベースと、
制約条件を充足する制約充足解の探索を変数変域データベースに保持された変数の変域において実行する制約充足エンジンと、
制約条件データベースから優先順位が最上位の制約条件を読み出し、当該最上位の制約条件のみを含む制約条件の部分集合を作成し、この部分集合の制約充足解の探索を制約充足エンジン部に実行させ、解が無ければ直前に制約条件データベースから読み出した制約条件を制約充足問題における解が存在しない原因として特定し、解が有り且つ制約条件データベースから読み出していない制約条件が優先順位最下位の制約条件のみであれば当該最下位の制約条件を制約充足問題における解が存在しない原因として特定し、解が有り且つ制約条件データベースから読み出していない制約条件が優先順位最下位の制約条件のみでなければ制約条件データベースから次に優先順位の高い制約条件を読み出し、前記制約条件の部分集合に追加して新たな制約条件の部分集合を作成し、この新たな部分集合の制約充足解の探索を前記同様に制約充足エンジン部に実行させ、以下、解が無く直前に制約条件データベースから読み出した制約条件を制約充足問題における解が存在しない原因として特定できるか又は制約条件データベースから読み出していない制約条件が最下位の制約条件のみとなり、当該最下位の制約条件を制約充足問題における解が存在しない原因として特定できるまで制約条件の読み出し及び部分集合への追加並びに制約充足解の探索を繰り返す制約条件管理モジュールとを備えた
ことを特徴とする原因特定装置。
【請求項８】
請求項５乃至７いずれか記載の原因特定装置において、前記に加え、
変数変域データベースに保持された変数の変域をさらに限定するための外部条件を保持する外部条件保持部を備え、
制約充足エンジンは制約条件を充足する制約充足解の探索を変数変域データベースに保持された変数の変域のうち前記外部条件によってさらに限定された変域において実行する
ことを特徴とする原因特定装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、予め与えられた変数の中から所定の複数の制約条件を充足する制約充足解を求める制約充足問題の解決に際し、解が存在しない場合の原因を特定する技術に関する。
【背景技術】
【０００２】
従来より、鉄道・バスなどのダイヤ作成、倉庫における荷物の配置、高等学校・大学・専門学校・研修センターにおける時間割作成や教室の割当て等、制約条件が多岐に亘るリソース（資源）割当問題を、人工知能の分野である制約充足問題として解くことが広く行われており、これら制約充足問題による解法において、制約条件を充足する解を導くための手法についての検討が行われている（特許文献１参照）。
【特許文献１】特開平１０−２４０５３４号公報（「制約充足問題解決装置およびその方法」）
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかし、従来の制約充足問題解決方法では、複数の制約条件を充足する制約充足解が存在しない場合、複数ある制約条件をまとめて「制約を充足しない」ということを示すだけであり、その原因を特定することはできなかった。制約充足問題の考え方をリソース割当問題に組み入れる場合、制約充足解が存在しない時に制約条件の充足が不可能となった原因、つまり解導出のボトルネックとなった制約条件を示せなければ、どのような対処を施せば良いのか解らない。
【０００４】
必ず制約を充足する解があることを前提とする場合は問題ないが、制約を充足する解が存在するとは限らない問題に制約充足による解法を適用する場合、制約を充足する解が存在しない原因を特定できないという問題点があった。
【０００５】
このため、本発明では、制約条件を充足する解が存在しない場合に、充足が不可能である原因を特定することを目的とする。
【課題を解決するための手段】
【０００６】
図１は本発明の原因特定方法を実施する装置のハードウェア構成の概要を示すもので、図中、１は制約条件データベース、２は変数変域データベース、３は外部条件保持部、４は制約充足エンジン、５は制約条件管理モジュールである。
【０００７】
制約条件データベース１は、所定の複数の制約条件、例えばｃ（１），ｃ（２），…，ｃ（ｎ）（但し、ｎは制約条件の総数）及び原因特定のための各制約条件の優先順位を保持する。変数変域データベース２は、変数及びその変域を保持する。制約充足エンジン４は、制約条件を充足する制約充足解の探索を変数変域データベース２に保持された変数の変域において実行する。制約条件管理モジュール５は、制約条件データベース１、変数変域データベース２、外部条件保持部３及び制約充足エンジン４を後述する如く制御し、制約充足問題における解が存在しない原因を特定する。外部条件保持部３については後述する。
【０００８】
なお、制約条件の優先順位は、解決すべき問題や各制約条件の内容、制約条件と変数との関係等に応じて、制約充足問題における解が存在しない原因を特定できるように設定するものとする。また、前述した所定の複数の制約条件及びその優先順位や変数及びその変域は予め、図示しない入力装置あるいは通信媒体もしくは記録媒体から、各データベースに入力されあるいは伝送されもしくはコピーされ、保持されているものとする。
【０００９】
図２は制約条件管理モジュール５における処理フローを示すものであり、以下、これに沿って本発明の原因特定方法について説明する（請求項１）。
【００１０】
まず、制約条件管理モジュール５は、制約条件データベース１から制約条件ｃ（１），ｃ（２），…，ｃ（ｎ）を読み出し、優先順位が最上位の制約条件のみを要素として含む部分集合を筆頭とし、これに残りの制約条件を優先順位の高い順に１つずつ要素として追加してなる制約条件の部分集合
Ｃ（１）＝｛ｃ（１）｝，Ｃ（２）＝｛ｃ（１），ｃ（２）｝，…，Ｃ（ｎ）＝｛ｃ（１），ｃ（２），…ｃ（ｎ）｝
を全て作成する（ｓ１）。次に、制約条件管理モジュール５は、各部分集合の制約充足解の探索を制約充足エンジン４に実行させる（ｓ２）。最後に、制約条件管理モジュール５は、制約充足エンジン４における探索の実行結果から、制約充足解が存在しない部分集合のうち要素数が最小の部分集合Ｃ（ｋ）を特定し、該部分集合Ｃ（ｋ）内で優先順位が最下位の制約条件、言い換えれば部分集合Ｃ（ｋ−１）から部分集合Ｃ（ｋ）を作る際に追加された制約条件ｃ（ｋ）を特定し、これを制約充足問題における解が存在しない原因として特定する（ｓ３）。なお、部分集合Ｃ（ｋ）の制約充足解を探索するとは、ｃ（１）∧ｃ（２）∧…∧ｃ（ｋ）を充足する解を見つけることである。
【００１１】
なお、本発明の原因特定装置は、前記制約条件データベース１、変数変域データベース２、制約充足エンジン４とともに、前述したフローに従う各処理を実行する機能を備えた制約条件管理モジュール、即ち制約条件データベース１から全ての制約条件を読み出し、優先順位が最上位の制約条件のみを要素として含む部分集合を筆頭とし、これに残りの制約条件を優先順位の高い順に１つずつ要素として追加してなる制約条件の部分集合を全て作成し、各制約条件の部分集合の制約充足解の探索を制約充足エンジン４に実行させ、当該制約充足エンジン４における探索の実行結果から制約充足解が存在しない部分集合のうち要素数が最小の部分集合を特定し、該要素数が最小の部分集合内で優先順位が最下位の制約条件を特定し、これを制約充足問題における解が存在しない原因として特定する制約条件管理モジュール５とにより構成される（請求項５）。
【００１２】
本発明により、リソース割当問題を制約充足問題として解を導出する上で、制約を充足する解が存在しない場合に原因を特定することが可能となる。
【００１３】
なお、本発明は制約充足解を求めるための探索アルゴリズムがどのようなものであっても適用可能である。
【００１４】
ここで、前述した部分集合のうち、Ｃ（ｎ）＝｛ｃ（１），ｃ（２），…ｃ（ｎ）｝は、制約充足問題における所定の複数の制約条件に他ならない。従って、部分集合Ｃ（ｎ）に対する制約充足解の探索は、所定の複数の制約条件を充足する制約充足解の探索そのものであり、本発明の実施の前提となる制約充足問題解決において既に実行され、制約充足解が存在しないことが分かっている処理である。
【００１５】
そこで、部分集合作成の際、制約条件データベース１中で優先順位が最下位の制約条件を除外し、部分集合としては
Ｃ（１）＝｛ｃ（１）｝，Ｃ（２）＝｛ｃ（１），ｃ（２）｝，…，Ｃ（ｎ−１）＝｛ｃ（１），ｃ（２），…ｃ（ｎ−１）｝
を作成し、また、原因の特定に際しては、制約充足解が存在しない部分集合がある場合はそのうちの要素数が最小の部分集合を特定し、該要素数が最小の部分集合内で優先順位が最下位の制約条件を制約充足問題における解が存在しない原因として特定する点は同様であるが、制約充足解が全ての部分集合で存在する場合は制約条件データベース１中で優先順位が最下位の制約条件、即ちｃ（ｎ）を制約充足問題における解が存在しない原因として特定するようにしても良い。この場合の制約条件管理モジュール５における処理フローを図３に示す（請求項２，６）。
【００１６】
また、前述した各処理のうち、最も負荷が大きい処理は制約充足解の探索である。従って、全ての部分集合に対して制約充足解の探索を行うのではなく、必要最小限の部分集合、それもなるべく処理負荷の小さい部分集合、つまり制約条件の数が少ない部分集合に対して探索を行うのみで済むようにすることが望ましい。そこで、部分集合の作成を含めて制約充足解の探索を行う毎に制約充足問題における解が存在しない原因の特定が可能かどうかを判断し、可能であればその時点で処理を終了するようにした制約条件管理モジュール５における処理フローを図４に示す（請求項３，７）。
【００１７】
即ち、制約条件管理モジュール５は、制約条件データベース１から優先順位が最上位の制約条件、即ちｃ（１）を読み出し、当該最上位の制約条件のみを含む制約条件の部分集合Ｃ（１）を作成する（ｓ１１）。次に、制約条件管理モジュール５は、作成した制約条件の部分集合、ここではＣ（１）の制約充足解の探索を制約充足エンジン４に実行させる（ｓ１２）。次に、制約条件管理モジュール５は、前記探索の実行結果が解有りか解無しかを判定し（ｓ１３）、実行結果が解無しであれば直前に制約条件データベース１から読み出した制約条件、ここでは優先順位が最上位の制約条件ｃ（１）を制約充足問題における解が存在しない原因として特定し（ｓ１４）、処理を終了する。
【００１８】
一方、実行結果が解有りであれば、制約条件管理モジュール５は、制約条件データベース１から読み出していない制約条件が優先順位最下位の制約条件、つまりｃ（ｎ）のみであるか否かを判定する（ｓ１５）。ここで、制約条件データベース１から読み出していない制約条件が優先順位最下位の制約条件のみであれば当該最下位の制約条件ｃ（ｎ）を制約充足問題における解が存在しない原因として特定し（ｓ１６）、処理を終了する。
【００１９】
また、一方、制約条件データベース１から読み出していない制約条件が優先順位最下位の制約条件のみでなければ、制約条件管理モジュール５は、制約条件データベース１から次に優先順位の高い制約条件、例えばｃ（２）を読み出し、前記制約条件の部分集合に追加して新たな制約条件の部分集合Ｃ（２）を作成し、ステップｓ１２に戻って処理を続行する（ｓ１７）。
【００２０】
このようにすれば、制約充足問題における解が存在しない原因である制約条件の優先順位が高い程、部分集合に対する制約充足解の探索の処理負荷が少なくて済む。
【００２１】
なお、制約充足問題によっては変数変域データベース２に保持された変数のうちのいくつかについて、予め外部条件によりその変域がさらに限定される場合がある。そこで、外部条件保持部３に前記外部条件を保持させ、制約充足エンジン４には制約条件を充足する制約充足解の探索を実行させる際、変数変域データベース１に保持された変数の変域のうち前記外部条件によってさらに限定された変域において実行させるようにすれば良い（請求項４，８）。なお、この外部条件も制約条件等と同様、図示しない入力装置あるいは通信媒体もしくは記録媒体から、外部条件保持部３に入力されあるいは伝送されもしくはコピーされ、保持されるものとする。
【発明の効果】
【００２２】
本発明によれば、制約充足問題を適用したリソース割当問題において、制約を充足する解が存在しない場合の原因の制約条件を特定することが可能となるという効果を生じる。また、特定した原因の制約条件から、対処方法を導くことが可能となり、適切な対処を実施することができるようになるという効果を生じる。
【発明を実施するための最良の形態】
【００２３】
以下、本発明を実施するための最良の形態について図面を参照して説明する。
【００２４】
なお、本発明の原因特定方法の実施に際して用いるハードウェア資源や本発明の原因特定装置を構成するハードウェア資源は、従来の制約充足問題解決方法の実施に際して用いるハードウェア資源や従来の制約充足問題解決装置を構成するハードウェア資源とほとんど共通するため、以下の説明では、本発明の原因特定方法を含む制約充足問題解決方法全体、並びに本発明の原因特定装置を含む制約充足問題解決装置全体について説明する。
【００２５】
図５は本発明の原因特定方法を含む制約充足問題解決方法を実施する装置のハードウェア構成の一例を示すもので、図中、１は制約条件データベース、２は変数変域データベース、３は外部条件保持部、４は制約充足エンジン、５は制約条件管理モジュール、６は入力装置、７は表示装置である。
【００２６】
図６は本発明を適用する資源割当問題の一例、ここではユーザに光ファイバを利用するサービスを提供するための資源（設備）を割り当てる（選定する）資源割当問題を説明するもので、通信設備ビル内の通信装置（α−ＯＬＴ，β−ＯＬＴ，γ−ＯＬＴ）からユーザ宅までの間に設備を割り当てる。割り当てる設備（変数）は、通信装置パッケージ（ＰＫＧ）、所内通信設備（装置側所内光ファイバ、スプリッタ、所外側所内光ファイバ）、所外光設備（所外光ファイバ）であり、これらの情報は入力装置６から入力され、変数変域データベース２に保持される。
【００２７】
また、ユーザに設備を割り当てるための制約条件を以下に示す。
（Ｐ１）所外光ファイバは、ユーザ宅近傍の電柱により決定される。
（Ｐ２）所外光ファイバと所外側所内光ファイバは、同一光配線盤に収容されているファイバ同士でなければ接続できない。同一光配線盤内に収容されているもの同士であれば、任意に接続可能である。
（Ｐ３）サービス種別に適合した分岐数を持つスプリッタを経由する。
（Ｐ４）所外側所内光ファイバと装置側所内光ファイバは、同一中間架に収容されているファイバ同士でなければ接続できない。同一中間架内に収容されていれば、任意に接続可能である。
（Ｐ５）装置側所内光ファイバと通信装置は、装置ＰＫＧで接続される。
（Ｐ６）サービス種別により、サービス提供可能な装置種別は決定される。
【００２８】
これらの制約条件Ｐ１〜Ｐ６は原因特定のための優先順位、例えばＰ１→Ｐ６→Ｐ２→Ｐ３→Ｐ５→Ｐ４（注：左側ほど順位が高い）とともに入力装置６から入力され、制約条件データベース１に保持される。図６の資源割当問題を制約充足問題として捉えた場合の変数と制約条件との関係を表す制約ネットワークを図７に示す。
【００２９】
さらにまた、ユーザに割り当てる設備は、ユーザ宅の位置及び提供するサービス種別によって限定されるから、ユーザ宅近傍の電柱及びサービス種別が外部条件として入力装置６から入力され、外部条件保持部３に保持される。
【００３０】
図８は本発明の原因特定方法を含む制約充足問題解決方法を実施する制約条件管理モジュール５における処理フローを示すものであり、以下、これに沿って説明する。
【００３１】
制約条件管理モジュール５は、変数変域データベース２に保持された設備情報のうち、外部条件保持部３に保持された外部条件によって限定された設備情報及び制約条件データベース１に保持された制約条件Ｐ１〜Ｐ６を制約充足エンジン４へ渡し、全ての制約条件を充足する制約充足解の探索を実行させる（ｓ２１）。制約条件管理モジュール５は、制約充足エンジン４から返送される前記探索の実行結果について制約充足解が存在するか否かを判定し（ｓ２２）、制約充足解が存在すれば当該制約充足解、即ち制約を充足する設備の情報を表示装置７に提示し（ｓ２３）、一方、制約充足解が存在しなければ本発明の原因特定のための処理に移行する。
【００３２】
まず、制約条件管理モジュール５は、制約条件データベース１から優先順位が最下位の制約条件Ｐ４を除く制約条件Ｐ１，Ｐ２，Ｐ３，Ｐ５，Ｐ６を読み出し、優先順位が最上位の制約条件Ｐ１のみを要素として含む部分集合Ｃ（１）を筆頭とし、これに残りの制約条件を優先順位の高い順に１つずつ要素として追加してなる制約条件の部分集合
(i)Ｃ（１）＝｛Ｐ１｝
(ii)Ｃ（２）＝｛Ｐ１，Ｐ６｝
(iii)Ｃ（３）＝｛Ｐ１，Ｐ６，Ｐ２｝
(iv)Ｃ（４）＝｛Ｐ１，Ｐ６，Ｐ２，Ｐ３｝
(v)Ｃ（５）＝｛Ｐ１，Ｐ６，Ｐ２，Ｐ３，Ｐ５｝
を作成する（ｓ２４）。次に、制約条件管理モジュール５は、前記各部分集合Ｃ（１）〜Ｃ（５）の制約充足解の探索を制約充足エンジン４に実行させる（ｓ２５）。最後に、制約条件管理モジュール５は、制約充足エンジン４における探索の実行結果から、(i)〜(v)の順に制約を充足する解があるか否かを判定し、制約充足問題における解が存在しない原因を特定する。
【００３３】
即ち、(i)の段階で制約を充足する解がない場合（ｓ２６）、原因が「Ｐ１を充足しない（所外光ファイバがない）」であることを特定し、これを表示装置７に提示する（ｓ２７）。これによって、Ｐ１を充足するようにリソース（設備）を準備する必要があることが判明する。
【００３４】
同様に、(ii)、(iii)、(iv)、(v)の各段階で制約を充足する解がない場合（ｓ２８，ｓ３０，ｓ３２，ｓ３４）、原因がそれぞれ「Ｐ６が充足しない（サービス提供可能装置ＰＫＧがない）」、「Ｐ２が充足しない（所外光ファイバと接続可能な所外側所内光ファイバがない）」、「Ｐ３が充足しない（サービス提供可能な分岐数のスプリッタがない）」、「Ｐ５を充足しない（装置と接続可能な装置側所内ファイバがない）」であることを特定し、これらを表示装置７に提示する（ｓ２９，ｓ３１，ｓ３３，ｓ３５）。これによって、それぞれＰ６、Ｐ２、Ｐ３、Ｐ５を充足するようにリソース（設備）を準備する必要があることが判明する。
【００３５】
また、(v)の段階で制約を充足する解が存在する場合には、原因が「Ｐ４を充足しない（接続可能な所外側所内光ファイバと装置側所内ファイバがない）」であることを特定し、これを表示装置７に提示する（ｓ３６）。これによって、Ｐ４を充足するようにリソース（設備）を準備する必要があることが判明する。
【００３６】
図６において、方面Ｂのユーザに装置種別β−ＯＬＴで提供するサービスβを提供する場合、方面Ｂに敷設していて且つ装置種別β−ＯＬＴに接続できる設備、つまり全ての制約条件Ｐ１〜Ｐ６を充足する設備（解）は存在しない。ここで、原因特定の処理に移行する。原因特定の処理から、Ｃ（３）＝｛Ｐ１，Ｐ６，Ｐ２｝を充足する解が存在しない、つまりＣ（３）が要素数最小の制約条件の集合となる。よって、Ｐ２を充足しない、つまり所外光ファイバと接続可能な所外側所内光ファイバが存在しないことが制約を充足しない原因とわかる。Ｐ２の制約を充足するように設備を準備すること、つまり所外光ファイバと接続可能な所外側所内光ファイバを準備することで制約を解消することができ、サービスの提供が可能となることが判明する。
【図面の簡単な説明】
【００３７】
【図１】本発明の原因特定方法を実施する装置の概要を示すハードウェア構成図
【図２】制約条件管理モジュールにおける処理フローの一例を示す図
【図３】制約条件管理モジュールにおける処理フローの他の例を示す図
【図４】制約条件管理モジュールにおける処理フローのさらに他の例を示す図
【図５】本発明の原因特定方法を含む制約充足問題解決方法を実施する装置の一例を示すハードウェア構成図
【図６】本発明を適用する資源割当問題の一例を示す説明図
【図７】図６の資源割当問題における変数と制約条件との関係を表す制約ネットワークを示す説明図
【図８】本発明の原因特定方法を含む制約充足問題解決方法を実施する制約条件管理モジュールにおける処理フローの一例を示す図
【符号の説明】
【００３８】
１：制約条件データベース、２：変数変域データベース、３：外部条件保持部、４：制約充足エンジン、５：制約条件管理モジュール、６：入力装置、７：表示装置。
【図１】
2006004156.tif 000003
【図２】
2006004156.tif 000004
【図３】
2006004156.tif 000005
【図４】
2006004156.tif 000006
【図５】
2006004156.tif 000007
【図６】
2006004156.tif 000008
【図７】
2006004156.tif 000009
【図８】
2006004156.tif 000010