(57)【要約】【課題】決定変数の解の決定に原因となった制約やその解の制約伝播の原因となった他の解の情報を明示的に出力することにより、制約充足解の求解過程の解析を容易にする。【解決手段】解探索処理装置は、各探索ステップで決定変数の値を選択する際に変化する選択可能なドメインを計算する探索ステップ別制約伝播状況抽出部と、制約伝播を実行する制約伝播実行部と、探索ステップ別制約伝播状況抽出部で計算した結果に基づいて、各ステップで選択された値を教師データとして予測モデルを学習し、選択した値に応じてドメインを更新して、学習する予測モデル学習部と、予測モデルで選択するべき決定変数の値を予測し、制約伝播実行部により選択した値に応じてドメインを更新して、探索処理を行う値予測部と、特定した決定変数の値を予測した場合の原因となる選択可能なドメインの情報を出力する原因説明部を有する。【選択図】図２
2019008499.tif 000002
【特許請求の範囲】
【請求項１】
制約充足問題の求解処理を実行する解探索処理装置であって、
過去の出力解を入力とし、解導出過程の各探索ステップで決定変数の値を選択する際に変化する選択可能なドメインを計算する探索ステップ別制約伝播状況抽出部と、
制約伝播を実行する制約伝播実行部と
前記探索ステップ別制約伝播状況抽出部で計算した結果に基づいて、各ステップでの値選択前の決定変数のドメインを入力とし、各ステップで選択された値を教師データとして予測モデルを学習し、制約伝播実行部により選択した値に応じてドメインを更新して、学習を繰り返し実行する予測モデル学習部と、
各探索ステップで値選択前の選択可能な決定変数のドメインを入力として、前記予測モデル学習部で学習した予測モデルで選択するべき決定変数の値を予測し、制約伝播実行部により選択した値に応じてドメインを更新して、前記決定変数の解の探索処理を繰り返し実行する値予測部とを有することを特徴とする解探索処理装置。
【請求項２】
さらに、前記予測モデル学習部で学習した予測モデルに基づき、原因説明の対象となる決定変数の状態を入力とし、特定した決定変数の値を予測した場合の原因となる選択可能なドメインの情報を出力する原因説明部を有することを特徴とする請求項１記載の解探索処理装置。
【請求項３】
前記予測モデル学習部および前記値予測部では、決定変数の値選択状況と選択可能なドメインを入力として選択するべき決定変数の候補を予測する機械学習モデルに基づき機械学習をおこなうことを特徴とする請求項１記載の解探索処理装置。
【請求項４】
前記機械学習モデルは、畳み込みニューラルネットワークであることを特徴とする請求項３記載の解探索処理装置。
【請求項５】
前記原因説明部は、算出解または解探索途中に選択されている決定変数の値について、前記値予測部で特定の決定変数の値を予測した原因となる他の決定変数の値と制約を提示することを特徴とする請求項１記載の解探索処理装置。
【請求項６】
前記値予測部で特定した決定変数の値と、予測した原因となる他の決定変数の値と制約を、決定変数の選択をノードで表現したツリー上に表示することを特徴とする請求項５記載の解探索処理装置。
【請求項７】
前記値予測部で特定した決定変数の値と、予測した原因となる他の決定変数の値と制約を、決定変数の値を予測した原因と、結果を表記するロジックツリー上に表示することを特徴とする請求項５記載の解探索処理装置。
【請求項８】
車両を決定変数とし、列車をドメインとして、原因と結果をダイヤグラム上に表示することを特徴とする請求項５記載の解探索処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、解探索処理装置に係り、大規模な制約プログラミングにより制約充足解を探索する問題において、最適解を求める過程を解析するのに好適な解探索処理装置に関する。
【背景技術】
【０００２】
制約プログラミングにより制約充足解を探索する問題の応用として、鉄道や資源配置、工場の生産計画などの産業分野における資源の管理や計画の業務を対象とする場合がある。
【０００３】
対象とする業務としては、例えば、鉄道運行管理業務では、通常時には予め定められた列車の運行計画（ダイヤ）に基づいて列車を走行させることが要求されているが、運行当日にダイヤ乱れが発生した場合には、列車運行に支障がないように計画を修正しなければならない。鉄道輸送に必要な計画は列車のダイヤのほかに、ダイヤ上の列車に車両の割り当て計画を定めた車両運用情報や、乗務員の割り当て計画を定めた乗務員運用情報がある。運行当日にダイヤ乱れが発生した場合には、ダイヤの修正に応じて車両運用情報や乗務員運用情報の修正が行われる。
【０００４】
また、例えば、資源配置計画業務では、資源の入出荷によって日次で変動する資源の在庫量に応じて、容量制限のある資源の配置場所に資源を配置する日次計画を立案することが求められる。このとき、出荷のための資源の加工を決められた日時に決められた場所で行う制約や日当たりでの資源を移動させる手段の容量制限の制約など多くの制約を遵守しながら、なおかつ前日の計画とはなるべく変更をしないように日次計画を立案する必要がある。
【０００５】
上記のような計画作成業務では、大規模な制約充足問題の解を導出しなければならず、従来では熟練したオペレータが手動で行っていた。しかしながら、近年では熟練したオペレータの退職に伴い、上記の業務をシステムで代替しようというニーズが顕在化している。熟練者のオペレータの業務を代替するシステムにおいてはオペレータが立案した計画と同等に実用的な制約充足解を実用的な時間内に求解することが求められている。
【０００６】
これまでも、実用的な制約充足解の求解を容易化する技術は提案されている。例えば、特許文献１には、ユーザにより決定変数のドメイン変更などの新たな要求が追加されるたびに、過去の問題解決事例において採用された解と比較し、同一の解が採用された頻度に基づいて解候補の評価値を求め、固定化された制約と追加の要求を満たす中で最も評価値の高い解を出力する技術が記載されている。
【０００７】
また、非特許文献１には、ツリー探索を効率的に行うプログラミングパラダイムの一つとして、制約プログラミングという手法が開示されている。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００３−９９２５９号公報
【非特許文献】
【０００９】
【非特許文献１】Marc Vilain、Henry Kautz、Constraint Propagation Algorithms for Temporal Reasoning、Aaai、1986、pp377-382
【発明の概要】
【発明が解決しようとする課題】
【００１０】
特許文献１に記載の技術は、ユーザが入力した決定変数のドメインの変更に関する要求に対して、過去の問題解決事例において採用された解と比較し、適切な解を出力することができる。ここで、ドメインとは決定変数の取りうる値の範囲をいう。確かに、特許文献１に記載の技術は、小規模な制約充足問題で全探索が終了する場合には過去事例に基づいて望まれる解が出力されるため有効である。しかしながら、制約や決定変数の数が多い大規模な制約充足問題では問題設定の状況に応じて制約充足解の集合を探索すること自体が困難となる。大規模な制約充足問題で決定変数をノードとして決定変数の値をエッジとしたツリー探索を行う場合には全探索を実用的な時間内に行うことは不可能であり、実用時間内に探索できる探索ステップ数内で求解できるように、決定変数のドメイン変更だけではなく、制約式の変更に応じて、適切な探索ルールを設定する必要がある。
【００１１】
また、非特許文献１に記載されているような制約プログラミングでは、ある決定変数のドメインが制約式を介して他の決定変数のドメインを縮小させる影響を制約伝播という演算で特定する。制約伝播により、制約式を介した、互いの決定変数のドメインの影響を考慮し、不要な探索範囲を早めにカットすることにより、効率的に探索領域の絞込みを行う。しかしながら、制約プログラミングにおける解探索においても、探索木の深さ方向の効率化はなされているが、探索木の分岐のうち、どの分岐を優先的に探索するかなど幅方向の効率化はなされていない。そのため、制約プログラミングにおいても、制約式の変更に応じて、実用時間内に制約充足解がみつかるように幅方向にも動的な探索をすることが必要である。
【００１２】
本発明の目的は、制約プログラミングによって解探索を実施する大規模な制約充足問題において、決定変数の解の決定に原因となった制約やその解の制約伝播の原因となった他の解の情報を明示的に出力することにより、制約充足解の求解の過程の解析、デバッグを容易し、もって求解を容易にする解探索処理装置を提供することにある。
【課題を解決するための手段】
【００１３】
本発明の解探索処理装置の構成は、好ましくは、制約充足問題の求解処理を実行する解探索処理装置であって、過去の出力解を入力とし、解導出過程の各探索ステップで決定変数の値を選択する際に変化する選択可能なドメインを計算する探索ステップ別制約伝播状況抽出部と、制約伝播を実行する制約伝播実行部と、探索ステップ別制約伝播状況抽出部で計算した結果に基づいて、各ステップでの値選択前の決定変数のドメインを入力とし、各ステップで選択された値を教師データとして予測モデルを学習し、制約伝播実行部により選択した値に応じてドメインを更新して、学習を繰り返し実行する予測モデル学習部と、各探索ステップで値選択前の選択可能な決定変数のドメインを入力として、予測モデル学習部で学習した予測モデルで選択するべき決定変数の値を予測し、制約伝播実行部により選択した値に応じてドメインを更新して、決定変数の解の探索処理を繰り返し実行する値予測部とを有するようにしたものである。
【００１４】
また、上記解探索処理装置の構成において、さらに、予測モデル学習部で学習した予測モデルに基づき、原因説明の対象となる決定変数の状態を入力とし、特定した決定変数の値を予測した場合の原因となる選択可能なドメインの情報を出力する原因説明部を有するようにしたものである。
【発明の効果】
【００１５】
本発明によれば、制約プログラミングによって解探索を実施する大規模な制約充足問題において、決定変数の解の決定に原因となった制約やその解の制約伝播の原因となった他の解の情報を明示的に出力することにより、制約充足解の求解の過程の解析、デバッグを容易にし、もって求解を容易にする解探索処理装置を提供することができる。
【図面の簡単な説明】
【００１６】
【図１】実施形態１に係る解探索処理装置のハードウェア・ソフトウェア構成図である。
【図２】実施形態１に係る解探索処理装置の処理の全体概要を示す図である。
【図３】探索ステップ別制約伝播状況抽出部１２０の処理を示すフローチャートである。
【図４】過去の探索解の一例を示す図である。
【図５】ステップ別探索情報を示す図である。
【図６】探索ステップ２での各決定変数の値選択状況を表す行列である。
【図７】探索ステップ２での各決定変数の選択可能なドメインを表す行列である。
【図８】予測モデル学習部の教師データの例を示す図である。
【図９】予測モデル学習部の処理を示すフローチャートである。
【図１０】ニューラルネットワークの概念を説明する図である。
【図１１】値予測部１２３と制約伝播実行部１２２の詳細な処理を示すフローチャートである。
【図１２】予測モデルとして入力される値選択状況を表す行列の例を示す図である。
【図１３】予測モデルとして入力される選択可能なドメイン状況を表す行列の例を示す図である。
【図１４】予測モデルから出力される決定変数を表す行列の例を示す図である
【図１５】実施形態１の原因説明部１２４の詳細な処理を示すフローチャートである。
【図１６】予測モデルから出力される決定変数を表す行列の例を示す図である。
【図１７】原因説明の対象とする値選択状況Ｓｋを表す図である。
【図１８】図１６と図１７の行列を原因説明部１２４の入力として、出力される選択可能なドメイン状況Ｄｋを表す図である。
【図１９】原因説明の対象となっている決定変数の値を選択するために選択可能となっているべきドメインの表示を示す図である。
【図２０】実施形態２に係る解探索処理装置のハードウェア・ソフトウェア構成図である。
【図２１】実施形態２に係る解探索処理装置と処理の全体概要を示す図である。
【図２２】制約伝播実行部１２２の詳細な処理を示すフローチャートである。
【図２３】制約伝播実行結果１１３の例を示す図である。
【図２４】実施形態２の原因説明部１２４の詳細な処理を示すフローチャートである。
【図２５】原因説明部の出力画面の例を示す図である（その一）。
【図２６】原因説明部の出力画面の例を示す図である（その二）。
【図２７】原因説明部の出力画面の例を示す図である（その三）。
【図２８】鉄道運行における原因推定結果の出力例を示す図である（その一）。
【図２９】鉄道運行における原因推定結果の出力例を示す図である（その二）。
【発明を実施するための形態】
【００１７】
以下、本発明に係る各実施形態を、図１ないし図２９について説明する。
【００１８】
〔実施形態１〕
以下、本発明の実施形態１を、図１ないし図１９を用いて説明する。
【００１９】
先ず、図１を用いて実施形態１に係る解探索処理装置のハードウェア・ソフトウェア構成について説明する。  
解探索処理装置は、鉄道における車両や乗務員の再割り当てや資源配置計画を自動で行うための装置であり、図１に示されるように、表示部１０１、入力部１０２、ＣＰＵ１０３、通信部１０４、記憶部１０７、メモリ１０５から構成される一般的な情報処理装置で実現される。解探索処理装置のハードウェアとして用いられる情報処理装置は、デスクトップコンピュータ、ラップトップコンピュータ、タブレットやサーバ装置であってもよい。また、解探索処理装置の情報処理装置は、ネットワーク１００を介して他の情報処理装置と通信可能である。
【００２０】
記憶部１０７には、過去の探索情報１１０、ステップ別探索情報１１１、現在の探索情報１１２が格納されている。過去の探索情報１１０は、過去の解と制約式と決定変数のドメインの初期状態で構成される情報である。ステップ別探索情報１１１は、過去の解探索におけると各ステップの決定変数ごとの選択可能なドメインとそのステップで解導出のために選択した決定変数の値との関係を示す情報である。現在の探索情報１１２は、制約式と決定変数のドメインの初期状態で構成される情報であり、問題の解決する対象としている元データである。
【００２１】
また、メモリ１０５には、解探索処理装置の各機能を実行するプログラム１０６が記憶されており、ＣＰＵ１０３に実行されることにより機能が実現される。解探索処理装置は、プログラム１０６を実行することにより、探索ステップ別制約伝播状況抽出部１２０、予測モデル学習部１２１、制約伝播実行部１２２、値予測部１２３、原因説明部１２４の各機能部の機能を実行する。
【００２２】
次に、図２を用いて解探索処理装置の処理の全体概要について説明する。
【００２３】
図２は、実施形態１に係る解探索処理装置の処理の全体概要を示す図である。  
解探索処理装置においては、先ず、探索ステップ別制約伝播状況抽出部１２０において過去の探索情報１１０を受け取り、各探索ステップごとに選択した決定変数の値と決定変数の選択によって変化する選択可能なドメインとの関係を導出し、ステップ別探索情報１１１に保存する。ここで、決定変数とは、問題の対象として、その値を決定するべき変数である。また、ドメインとは、決定変数が取りうる値の範囲（定義域）である。
【００２４】
次に、予測モデル学習部１２１は、ステップ別探索情報１１１における選択可能なドメインを入力とし、選択した決定変数の値を出力とする教師データによって、ニューラルネットワークの予測モデルを学習する。
【００２５】
制約伝播実行部１２２は、各ステップで決定変数の値を選択するごとに制約を介して縮小する他の決定変数の選択可能なドメインの変化を制約伝播によって算出し、決定変数の値選択後の選択可能なドメインの情報を更新する。更新したドメインの情報は予測モデル学習部１２１にフィードバックされる。制約伝播とは、既に説明したように、ある決定変数の値が定まることによりドメインが変化し、制約式を介して他の決定変数のドメインを変化させる事象を算出する演算である。
【００２６】
次に、値予測部１２３は、学習したモデルに基づいて、現在の探索の各ステップで選択可能なドメインを入力として選択するべき決定変数の値を予測し、出力する。その後、学習時での処理と同様に、制約伝播実行部１２２により、決定変数の値選択後の選択可能なドメインの情報を更新し、選択した決定変数の値の情報と更新した値選択後の選択可能なドメインの情報を値予測部１２３にフィードバックする。
【００２７】
原因説明部１２４は、予測モデル学習部１２１で学習したニューラルネットワークの予測モデルを受け取り、値予測部で値の予測に影響する選択可能なドメインを推定するために、選択した決定変数の値をニューラルネットワークの出力部に設定し、設定した値を逆算させた場合に発生する選択可能なドメインの重みベクトルを計算することにより、決定変数の値選択に影響する選択可能なドメインを導出する。
【００２８】
次に、図３ないし図１９を用いて実施形態１に係る解探索処理装置の詳細な処理について説明する。
【００２９】
以下では、本実施形態の解探索処理装置の処理の詳細を、日次での資源配置計画を例にして説明する。日次での資源配置計画は下記のように設定されるものとする。
【００３０】
資源Ａ、Ｂ、Ｃ、Ｄが存在していたときに、それぞれの資源の重量をａ、ｂ、ｃ、ｄとする。あるエリア１に資源Ａ、Ｂ、Ｃ、Ｄを配置する場合を１、配置しない場合を０とした場合に、資源Ａ、Ｂ、Ｃ、Ｄについてエリア１に資源を配置するか否かを示す決定変数ｙ１ｈ（ｈ＝１，２，３，４）は、以下のものとする。
ｙ１１∈{０，１}
ｙ１２∈{０，１}
ｙ１３∈{０，１}
ｙ１４∈{０，１}
このとき、制約の代表例として、エリア１における容量制限ｚ１に関する容量制約が以下のように定められるものとする。
ａｙ１１＋ｂｙ１２＋ｃｙ１３＋ｄｙ１４＜ｚ１
他のエリア２、３、４についても、同様に資源を配置するか否かを示す決定変数ｙ１ｈ、ｙ２ｈ、ｙ３ｈ、ｙ４ｈにより管理する。
【００３１】
また、資源Ａ、Ｂ、Ｃ、Ｄについてどのエリアに配置するかを示す決定変数ｘｈ（ｈ＝１，２，３，４）とし、以下の通り、エリア番号をドメインとする。
ｘ１∈{１，２，３，４}
ｘ２∈{１，２，３，４}
ｘ３∈{１，２，３，４}
ｘ４∈{１，２，３，４}
決定変数ｙ１ｈとｘｈについては、
ｙ１ｈ＝１
ならば
ｘｈ＝ｌ
という関係が成立するものとする。
【００３２】
以下では、このモデルによって各部の詳細な処理について説明する。
【００３３】
先ず、図３ないし図７を用いて探索ステップ別制約伝播状況抽出部１２０の処理と制約伝播実行部１２２の処理の詳細を説明する。  
ステップ別探索情報１１１は、探索ステップｋでの各決定変数の値選択状況と選択可能なドメインで構成され、以下の行列で定義される。
Ｓｋ：探索ステップｋでの各決定変数の値選択状況を表す行列
Ｄｋ：探索ステップｋでの各決定変数の選択可能なドメインを表す行列
行列Ｓｋ、Ｄｋは、行が決定変数ｘｈで、列がその決定変数ｘｈのドメインを示している。Ｓｋの探索ステップｋ＝０での各要素の初期値は０である。
【００３４】
Ｓｋについては、探索ステップｋで
ｘｈ＝ｌ
となっている決定変数ｘｈの行のドメインｌの列に１を選択するものとする。
【００３５】
Ｄｋについては、探索ステップｋ＝０での各要素の初期値は決定変数の初期状態で選択可能となっている決定変数ｘｈのドメインｌを１とし、選択不能となっているものを０としたものである。探索ステップｋ≠０については、Ｓｋの状態での他の決定変数からの制約伝播により、選択可能となった決定変数ｘｈの行のドメインｌの列を１と更新し、選択不能となったものを０と更新する。
【００３６】
探索ステップ２でのＳｋ、Ｄｋの例は、それぞれ図６、図７に示されるようになる。
【００３７】
図４は、過去の決定変数ｘｈ（ｈ＝１，２，３，４）の一例を示したものである。そして、図４に示される（ｘ１，ｘ２，ｘ３，ｘ４）＝（２，２，４，３）の内で、（ｘ１，ｘ２）＝（２，２）まで選択した状況での決定変数の値選択状況を、図６に示されるＳ２で、制約伝播により探索ステップｋ＝２で選択可能なドメインを、図７に示されるＤ２で示したものである。
【００３８】
以上を前提として、図３に示される処理を説明する。探索ステップ別制約伝播状況抽出部１２０は、先ず、処理で過去の探索情報１１０を取得し、ＳｋとＤｋを初期化する（Ｓ１３０）。なお、過去の探索情報１１０は、過去の解と制約式と決定変数のドメインの初期状態で構成される情報である。この初期化においては、Ｓｋについては、零行列に初期化するが、Ｄｋについては決定変数のドメインの初期状態（すなわち、各決定変数が初期状態において選択可能なドメイン）を反映する。
【００３９】
次に、取得した解のうち決定変数の値を一つ選択して、Ｓｋを更新する（Ｓ１３１）。次に、更新したＳｋの状態に基づいて、制約伝播実行部１２２により制約伝播を実施して、Ｄｋを更新する（Ｓ１３２）。その後、最後の決定変数までＳ１３１、Ｓ１３２の処理を実施したかを判定し（Ｓ１３３）、実施していない決定変数がある場合（Ｓ１３３：ＮＯ）には、次の決定変数へと進み、Ｓ１３１、Ｓ１３２の処理を繰り返えし、最後の決定変数までＳ１３１、Ｓ１３２の処理を終了する（Ｓ１３３：ＹＥＳ）と、図５に示されるように、それぞれのステップ番号１４１について、値選択状況１４２に対応するＳｋと選択可能なドメイン１４３に対応するＤｋとを取得できる。
【００４０】
次に、図８ないし図１０を用いて予測モデル学習部１２１の詳細な処理について説明する。
【００４１】
先ず、予測モデル学習部１２１は、探索ステップ別制約伝播状況抽出部１２０において作成した値選択状況Ｓｋと選択可能なドメイン状況Ｄｋをステップ別探索情報１１１から予測モデル学習の入力の教師データとして読み込む（Ｓ１７０）。また、値選択状況１６１のＳｋ−１と選択可能なドメイン１６２のＤｋ−１に対応させて、Ｓｋで選択した決定変数の値を、値選択結果１６３として抽出し、予測モデル学習の出力の教師データとして設定する。そして、設定した教師データに基づいて予測モデルを機械学習によって学習する（Ｓ１７１）。機械学習モデルの例としては、上記のデータを取り扱うことができる畳み込みニューラルネットワークを用いる。学習した予測モデルについては値予測部１２３と原因説明部１２４に出力する。
【００４２】
ここで、畳み込みニューラルネットワークとは、中間層としての複数の畳み込み層（フィルタ部）を有するニューラルネットワークである。フィルタ部ではフィルタ係数（重みベクトル）が設定される。畳み込み層は、入力されたデータにフィルタリングを行う。以上の処理で、畳み込みニューラルネットワークは、画像データなどの２次元のデータを入力し、中間層によりフィルタ係数に基づくフィルタ処理を行って、出力層により識別の判定結果や認識結果などを出力する。
【００４３】
本実施形態でのニューラルネットワークにおいては、図１０に示されるように、各ノードでの値選択状況Ｓｋ、選択可能なドメイン状況Ｄｋの入力、決定変数として出力されるＶｋを教師データとして、ノードにおけるｗｅｉｇｈｔを学習する。ここで、Ｓｋのｗｅｉｇｈｔを表す行列をＷｋ、Ｄｋのｗｅｉｇｈｔを表す行列をＷ′ｋとすると、以下の式が成立する。
Ｖｋ＝ＳｋＷｋ＋ＤｋＷ′ｋ
次に、図１１を用いて値予測部１２３と制約伝播実行部１２２の詳細な処理について説明する。
【００４４】
値予測部１２３は、先ず、現在の探索情報１１２を取得し、ＳｋとＤｋを初期化する（Ｓ１１８）。なお、現在の探索情報１１２は制約式と決定変数のドメインの初期状態で構成される情報である。この初期化については、Ｓｋについては零行列として初期化されており、Ｄｋについては決定変数のドメインの初期状態を反映するものとする。次に、ＳｋとＤｋとを入力として予測モデル学習部１２１で作成した予測モデルの示すｗｅｉｇｈｔによって選択するべき決定変数の値を予測する（Ｓ１８１）。
【００４５】
次に、Ｓ１８１で予測した決定変数の値を選択し、Ｓｋ＋１を更新する（Ｓ１８２）。次に、更新したＳｋ＋１に基づいて、制約伝播実行部１２２により制約伝播を実行し、Ｄｋ＋１を更新する（Ｓ１８３）。次に、最後の決定変数まで値を設定できたか否かを判定し（Ｓ１８４）、最後の決定変数まで値を設定していないときには（（Ｓ１８４：ＮＯ）、処理で次の決定変数に移行し（Ｓ１８５）、以下、Ｓ１８１〜Ｓ１８３を繰り返す。
【００４６】
次に、図１２ないし図１４により、探索ステップｋ＝１での、Ｓ１８１の処理の入出力結果の一例を説明する。
【００４７】
ここで、学習した予測モデルを用いて予測する際に、予測モデルの入力は図１２のＤｋ、図１３のＳｋで、出力は、図１４のＶｋである。Ｖｋは選択するべき決定変数の値を示す予測モデルの出力となる行列である。予測モデルの入力が図１２のＤｋ、図１３のＳｋで与えられたとき、学習した予測モデルで予測される選択するべき決定変数の値を示す出力部の行列Ｖｋは、図１４のように、ＤｋとＳｋ同様に行が決定変数、列がドメインのデータテーブルで示すことができる。Ｖｋのうち、行列の要素の値が高い順に決定変数とその値を選択し、探索過程でバックトラックなどが生じて、別の決定変数の値を選択する必要がある場合には、出力部の行列の要素の値が次に高い値を選択する。図１４に示される例では、探索ステップｋ＝２においては、Ｖｋの値のうち、最も高い値は、行ｘ２、列１の要素ある０．７の値なので、ｘ２の値として、ドメイン１を優先的に選択する。
【００４８】
次に、図１５ないし図１９を用いて原因説明部１２４の詳細な処理について説明する。
【００４９】
原因説明部１２４は、出力解を取得し、取得した出力解について、原因説明の対象とする決定変数の値を選択し、決定変数を表す行列Ｖｋを、予測モデルの出力として設定する（Ｓ１９０）。
【００５０】
次に、Ｓ１９０の処理で選択した決定変数の値を探索した際の値選択状況をＳｋから取得し、予測モデルの入力として設定する（Ｓ１９１）。
【００５１】
次に、Ｓ１９２の処理では、決定変数を表す行列Ｖｋの値を逆算させて、選択可能なドメイン状況Ｄｋの値を算出する。最後に、Ｓ１９３の処理では、算出した選択可能なドメイン状況Ｄｋの値を比較し、Ｄｋが高い値の要素の列を、値選択に関係する選択可能なドメインとして抽出し、値選択の原因として出力する。
【００５２】
以下、図１６ないし図１９を用いて、原因説明部１２４の入出力の例について説明する。図１６、図１７の例では、原因説明部１２４において、ｘ１に２が選択されているときに、ｘ２に１が選択された原因説明を実施することを意味している。図１８の例は、図１６、図１７の行列を、原因説明部１２４の入力とし、予測モデルを逆算して選択可能なドメイン状況Ｄｋを求めた場合の計算結果の例を示している。畳み込みニューラルネットの場合は、オートエンコーダー（G. E. Hinton、 R. R. Salakhutdinov、 Reducing the Dimensionality of Data with Neural Networks、 Science、 Vol313、2006、 pp504-506）で用いられているデコーディングの演算同様に、重みベクトルの転置行列を用いることにより、選択可能なドメイン状況Ｄｋを逆算することができる。選択可能なドメイン状況Ｄｋの各要素の値で０より大きな値となっているものは、原因説明の対象となっている決定変数の値を予測するために選択可能となっているべきドメインである。このドメインを原因説明の対象となっている決定変数の値を選択した原因として出力する。
【００５３】
図１９は、その出力画面例で塗りつぶされている部分が原因説明の対象となっている決定変数の値を選択するために選択可能となっているべきドメインである。ｘ１に２が選択されているときに、ｘ２に１が選択されるためには、図１８の結果によると、ｘ４について１と３が選択可能となっている必要があり、ｘ４について１と３が選択可能となっていることが値選択の原因となっていることがわかる。
【００５４】
〔実施形態２〕
以下、本発明の実施形態２を、図２０ないし図２７を用いて説明する。
【００５５】
実施形態１では、原因説明部１２４において特定の決定変数の値を選択した原因となる選択可能なドメインを抽出して提示したが、本実施形態の解探索処理装置では、原因説明部の出力例として、選択可能なドメインだけではなく、選択可能なドメインに対して制約伝播によって変更を与えた制約および決定変数とその値選択状況を示すようにする。
【００５６】
先ず、図２０および図２１を用いて、実施形態２に係る解探索処理装置のハードウェア・ソフトウェア構成と処理の全体概要について説明する。
【００５７】
実施形態２に係る解探索処理装置では、図２０に示されるように、実施形態１の図１に示す解探索処理装置の記憶部１０７に格納される情報に加えて、制約伝播実行結果１１３が格納される。
【００５８】
図２１に示されるように、制約伝播実行結果１１３には制約伝播実行部１２２から受け取った制約伝播の実行結果が格納され、原因説明部１２４に出力される。
【００５９】
次に、図２２ないし図２７を用いて実施形態２に係る解探索処理装置の詳細な処理について説明する。
【００６０】
先ず、図２２および図２３を用いて制約伝播実行部１２２の詳細な処理の詳細について説明する。  
制約伝播実行部１２２は、先ず、選択する決定変数の値を値予測部１２３から受け取り、制約伝播を実行する（Ｓ２１０）。制約伝播実行部１２２は、次に、制約伝播実行結果１１３として、探索ステップごとに選択した決定変数の値を図２３に示す選択状況２０１の欄に、選択可能なドメインを選択可能なドメイン２０３の欄に、変更を与えた制約を制約２０２の欄に、選択可能なドメインが変化した決定変数を選択可能なドメインが変化した決定変数２０４の欄にそれぞれ記憶する（Ｓ２１１）。
【００６１】
例えば、図２３に示した制約伝播実行結果１１３の例では、値選択状況２０１の欄のｘ１＝２の決定変数の値選択については、対応する選択可能なドメイン２０３の欄に、Ｄ１が記憶されており、選択可能なドメインが変化した決定変数２０４の欄には、ｘ２、ｘ４記憶されている。また、選択可能なドメインが変化した決定変数２０４に対応する制約伝播を引き起こした制約２０２の欄については、制約Ａが記憶されている。日次での資源配置計画問題では、この制約２０２の欄に記憶される制約Ａは、容量制限に関する制約などを意味する。
【００６２】
なお、値選択状況２０１と制約２０２との対応は１対多対応、制約２０２と選択可能なドメインが変化した決定変数との対応は１対多対応となりえる。すなわち、あるステップで、一つの値を選択した場合でも、関連する制約、選択可能なドメインが変化した決定変数の数は複数あるうるということである。
【００６３】
次に、図２４を用いて実施形態２の原因説明部１２４の詳細な処理について説明する。
【００６４】
本実施形態の説明では、主に実施形態１の図１５との相違点について説明する。  
原因説明部１２４は、Ｓ１９２の処理の後に、算出した予測モデルの入力部のＤｋの値から、値選択の原因となっている選択可能なドメインに対応する決定変数を抽出する（Ｓ１９４）。次に、原因説明部１２４は、抽出した決定変数の選択可能なドメインが変化した探索ステップを抽出し（Ｓ１９５）、制約伝播実行結果１１３により選択可能なドメインが変化した決定変数２０４を抽出し、抽出した選択可能なドメインが変化した決定変数に対応する制約２０２欄に記載されている制約と値選択状況２０１に記載されている値選択状況を参照して、選択可能なドメインが変化した原因として出力する（Ｓ１９６）。
【００６５】
次に、図２５ないし図２７を用いて実施形態２の原因説明部１２４の詳細な処理を、図２３に示す制約伝播実行結果１１３の例について適用した場合の具体例を説明する。
【００６６】
例えば、実施形態１の図１８のようにｘ３＝４を予測した原因として、ｘ４について１と３が選択可能なドメインであったことが推定されたとする。この場合、原因となった選択可能なドメインに対応する決定変数はｘ４である。ここで、図２３に示される制約伝播実行結果よりｘ４の選択可能なドメインが変化した制約伝播は、ｘ３＝４以前のものであり、ｘ１＝２を選択した場合の制約Ａによるものであると推定できる。
【００６７】
図２５ないし図２７は、そのときの原因推定結果の画面（図１の解探索処理装置の表示部１０１）への出力例を示したものである。図２５の例では、原因推定の対象となる決定変数とその値がｘ３＝４の場合、原因となる制約が図２３の制約２０２の欄に記載の制約Ａ、原因となる決定変数の選択がｘ１＝２となることをテーブル形式で表示している。
【００６８】
図２６の例では、図２５に表示されている情報を、決定変数の選択をノードで表現したツリー表記で表したものであり、原因推定対象となるノードおよび原因となる決定変数の選択に相当するノードを黒塗りで表記している。原因となる決定変数の選択に相当するノードについては、選択可能な決定変数のドメインに影響を与えた制約伝播を行った制約名も表記する。なお、ツリーの規模が大規模になる場合は、関係のないノードの表記は省略してもよい。
【００６９】
また、原因推定結果の出力例として、図２７のように原因推定対象と原因の関係のみに焦点をあてたロジックツリーで表示してもよい。このロジックツリーでは、矢印の根元が原因となる決定変数の選択であり、矢印の先が原因推定対象であることを示している。
【００７０】
〔その他の実施形態〕
以上、本発明の各実施形態について具体的に説明したが、本発明はこれに限定されるものではなく、その要旨を逸脱しない範囲で種々修正可能である。
【００７１】
実施形態２では、原因推定結果の出力例として，図２５のような探索ツリー、図２７のような原因推定対象と原因の関係のみに焦点をあてたロジックツリーで表示する例を示したが、鉄道運行管理業務や資源配置計画業務などリソース割当業務の作業画面に応じて、原因となる決定変数や制約の表示を各業務のリソースやリソースの運用制約で表示してもよい。
【００７２】
ここで、図２８および図２９を用いて鉄道運行における原因推定結果の出力例を説明する。
【００７３】
鉄道運行における鉄道用語においては、「車両」とは、鉄道車両のハードウェアであり、「列車」とは、ダイヤグラム上の走行（ある駅を何時何分に出発して、他の駅に何時何分に到着）を含む概念である。ここで、列車を決定変数、車両をドメインとする解探索処理問題を考える。制約は、駅の場所、運用時刻である。このときの、鉄道運行における原因推定結果の出力例としては、図２８に示すように、テーブル形式の原因、結果の因果関係を対比して示してもよいし、図２９に示すように、ダイヤグラムの形式で表示してもよい。
【００７４】
上記実施形態では、機械学習を行う予測モデルに畳み込みニューラルネットワークを用いたが、決定変数の値選択状況Ｓｋと選択可能なドメインＤｋを入力として設定可能で、選択するべき決定変数の候補を予測するものであれば、ナイーブベイズ分類器など、その他のモデルであってもよい。
【００７５】
また、上記実施形態では、機械学習を行う予測モデルの入力として、決定変数の値選択状況Ｓｋと選択可能なドメインＤｋを想定したが、他にも、初期状態の選択可能なドメインＤ0を導入するなど、選択可能なドメインの形態について種々のバリエーションが考えられる。
【００７６】
上記実施形態では、選択可能なドメインＤｋについては、ツリー探索の過程でたどってもよい分岐の数を反映させるために、探索ステップｋ≠０の場合、Ｓｋの状態での他の決定変数からの制約伝播により、選択可能となった決定変数ｘｈの行のドメインｌの列を１と更新し、選択不能となったものを０と更新するとしたが、この例に限定する必要はなく、例えば、他の決定変数からの制約伝播という限定を解除して、Ｓｋの状態での自己を含めた決定変数からの制約伝播により、選択可能となった決定変数ｘｈの行のドメインｌの列を１と更新し、選択不能となったものを０と更新するとしてもよいし、探索済みの決定変数の値については選択可能だとしても、０ないし−１などの値で表記してもよい。
【００７７】
上記実施形態では，解が算出された場合に原因説明部１２４を利用する実施形態を示したが，解が算出されない場合で，途中まで解探索が進んでいる場合にも原因説明部１２４をデバッガと活用し，解探索途中の段階で選択されている決定変数の値についても原因説明を行ってもよい。
【００７８】
〔まとめ〕
以上の各実施形態から明らかなように、本発明によれば、制約プログラミングによって解探索を実施する大規模な制約充足問題の中で決定変数だけでなく制約式の変更が与える影響を把握して、動的に選択するべき決定変数の値を変更し、実用上望まれる制約充足解の求解を容易化するように、決定変数の原因となる制約や他の決定変数の選択など明示的に示すことにより、デバッグの手段と問題解決の示唆を与え、問題の解決者に問題解決を容易化するための情報を明示的に表示するツールを提供することができる。
【符号の説明】
【００７９】
１００…ネットワーク
１０１…表示部
１０２…入力部
１０３…ＣＰＵ
１０４…通信部
１０５…メモリ
１０６…プログラム
１０７…記憶部
１１０…過去の探索情報
１１１…ステップ別探索情報
１１２…現在の探索情報
１１３…制約伝播実行結果
１２０…探索ステップ別制約伝播状況抽出部
１２１…予測モデル学習部
１２２…制約伝播実行部
１２３…値予測部
１２４…原因説明部
【図１】
2019008499.tif 000003
【図２】
2019008499.tif 000004
【図３】
2019008499.tif 000005
【図４】
2019008499.tif 000006
【図５】
2019008499.tif 000007
【図６】
2019008499.tif 000008
【図７】
2019008499.tif 000009
【図８】
2019008499.tif 000010
【図９】
2019008499.tif 000011
【図１０】
2019008499.tif 000012
【図１１】
2019008499.tif 000013
【図１２】
2019008499.tif 000014
【図１３】
2019008499.tif 000015
【図１４】
2019008499.tif 000016
【図１５】
2019008499.tif 000017
【図１６】
2019008499.tif 000018
【図１７】
2019008499.tif 000019
【図１８】
2019008499.tif 000020
【図１９】
2019008499.tif 000021
【図２０】
2019008499.tif 000022
【図２１】
2019008499.tif 000023
【図２２】
2019008499.tif 000024
【図２３】
2019008499.tif 000025
【図２４】
2019008499.tif 000026
【図２５】
2019008499.tif 000027
【図２６】
2019008499.tif 000028
【図２７】
2019008499.tif 000029
【図２８】
2019008499.tif 000030
【図２９】
2019008499.tif 000031