特許ウォッチ

公開番号2025085485
公報種別公開特許公報(A)
公開日2025-06-05
出願番号2023199393
出願日2023-11-24
発明の名称計画分析方法及び計画分析システム
出願人株式会社日立製作所
代理人弁理士法人サンネクスト国際特許事務所
主分類G06Q 10/04 20230101AFI20250529BHJP(計算;計数)
要約【課題】計画対象に関する事前のドメイン知識を必要とせずに、最適計画の分析を迅速に実行すること。
【解決手段】複数の制約及び評価指標に基づいて最適化対象が最適化された最適計画を分析する計画分析方法では、計画分析システムは、解析対象とする制約を組合せて複数の最適化パターンを生成する。そして各最適化パターンについて、最適計画においてユーザが注目する注目状態に該当する条件が充足される場合の評価指標に基づく上界及び条件が充足されない場合の上界を算出する。そして条件の下で最適化の実行可能解を探索する。そして上界及び実行可能解に基づいて、条件の下に最適化の最適解が存在するか否かを判定する。
【選択図】図9
特許請求の範囲【請求項１】
複数の制約及び評価指標に基づいて最適化対象が最適化された最適計画を分析する計画分析システムが実行する計画分析方法であって、
前記計画分析システムは、プロセッサとメモリとを有し、
前記プロセッサが、
解析対象とする前記制約を組合せて複数の最適化パターンを生成し、
各前記最適化パターンについて、前記最適計画においてユーザが注目する注目状態に該当する条件が充足される場合の前記評価指標に基づく上界及び該条件が充足されない場合の該上界を算出し、
前記条件の下で前記最適化の実行可能解を探索し、
前記上界及び前記実行可能解に基づいて、前記条件の下に前記最適化の最適解が存在するか否かを判定する
各処理を有することを特徴とする計画分析方法。
続きを表示（約 1,500 文字）【請求項２】
請求項１に記載の計画分析方法であって、
前記プロセッサが、
前記注目状態に基づいて、前記上界の算出及び前記実行可能解の探索における初期条件を決定する
処理を有することを特徴とする計画分析方法。
【請求項３】
請求項１に記載の計画分析方法であって、
前記プロセッサが、
前記条件のそれぞれにおける前記上界及び前記実行可能解を保持し、前記条件のうちの或る条件における前記実行可能解が別の条件における前記上界を超えた場合に、前記最適解において該或る条件が充足されることを示す情報を出力する
処理を有することを特徴とする計画分析方法。
【請求項４】
請求項１に記載の計画分析方法であって、
前記プロセッサが、
前記実行可能解の探索過程で、新たな条件が追加された前記条件の下で前記実行可能解を探索し、
新たな条件が追加された前記条件に基づいて前記上界を更新する
各処理を有することを特徴とする計画分析方法。
【請求項５】
請求項３に記載の計画分析方法であって、
前記プロセッサが、
前記実行可能解の探索の終了条件が充足された場合に、前記実行可能解の探索を終了すると共に、予め定められた例外処理を実行し、前記情報の出力に代えて、該例外処理の実行結果を出力する
処理を有することを特徴とする計画分析方法。
【請求項６】
請求項１に記載の計画分析方法であって、
前記プロセッサが、
前記複数の制約のうちの該制約をより多く含む順序で前記最適化パターンを生成する
ことを特徴とする計画分析方法。
【請求項７】
請求項１に記載の計画分析方法であって、
前記プロセッサが、
別の前記最適化パターンで既に取得されている前記実行可能解が、対象とする前記最適化パターンにおいて前記条件を充足するか否かを判定し、該条件を充足する場合に該実行可能解を該対象とする前記最適化パターンにおける暫定解として保持する
処理を有することを特徴とする計画分析方法。
【請求項８】
請求項１に記載の計画分析方法であって、
前記プロセッサが、
前記実行可能解を探索する際に幅優先探索を実行する
ことを特徴とする計画分析方法。
【請求項９】
請求項１に記載の計画分析方法であって、
前記プロセッサが、
前記最適化パターンにおいて除外された前記制約である除外制約についての逆制約を算出し、
前記最適化パターンについて、前記逆制約を用いて前記実行可能解を探索し、
前記実行可能解の探索時に取得された前記上界又は前記実行可能解と、前記除外制約を含んだ前記最適化パターンについて取得された前記上界又は前記実行可能解のうち同一の前記条件における前記上界又は前記実行可能解とを比較し、値が大きい前記上界又は前記実行可能解を該条件における前記上界又は前記実行可能解とする
各処理を有することを特徴とする計画分析方法。
【請求項１０】
請求項１に記載の計画分析方法であって、
前記プロセッサが、
前記最適化パターンと、該最適化パターンについて前記条件の下で前記最適化の最適解が存在するか否かの判定結果と、を特徴量へ変換して貢献度算出用データに格納し、
前記特徴量に基づいて、前記最適計画に対する各前記制約の貢献度を算出する
各処理を有することを特徴とする計画分析方法。
（【請求項１１】以降は省略されています）
発明の詳細な説明【技術分野】
【０００１】
本発明は、計画分析方法及び計画分析システムに関する。
続きを表示（約 1,200 文字）【背景技術】
【０００２】
デジタル化の進展によりあらゆる情報がデータ化され、例えば人財配置最適化など人生に関わるような重要な意思決定においても、最適化エンジンやエージェントベースシミュレーションが用いられてきている。
【０００３】
一方で最適化エンジンは、目的関数を最大化する解を提示するだけであり、例えば人財配置において、「Ａさんは職場１よりも職場２の適性が高いのに、なぜＡさんは職場１へ配属されるのか」などの、計画の要素の配置理由を提示することができない。社会的責任の大きい業務においては、最適化の結果だけでなく、そのユーザが納得する説明を提示することが重要である。
【０００４】
そこで近年、最適計画における判断根拠を説明する技術であるＸＡＩＰ（eXplainable AI Planning）の研究が急速に進展している。
【０００５】
ＸＡＩＰに分類される技術として、非特許文献１では、計画のある要素を成立させることに対し、入力因子である属性や制約の貢献を明らかにし、その事象にフォーカスして主な原因を説明する方法を提案している。
【０００６】
しかし計画根拠を提示するためには、入力因子に摂動を与えて最適化問題を何度も解き直す感度解析を行う必要がある。これには大きな計算コストがかかり、その説明を参照するために、ユーザは長時間待たなければならなかった。
【０００７】
これに対して、非特許文献１では、入力因子間の階層関係を入力することで、上位階層で全体の傾向を素早く把握した後に、貢献度が高いと期待できる因子についてさらに下位の階層で分析を行う手法が提案されている。各階層で摂動を与える因子の組合せ数を削減することができ、効率的な要因の探索が可能となる。
【０００８】
また非特許文献２では、摂動の組合せをサンプリングする手法が提案されている。Ｓｈａｐｌｅｙ値に基づく貢献度の算出においては、因子単体の影響（主効果）が貢献度としても大きい値を示すという傾向を利用することで、計算に必要な組合せ数を絞りつつ、高精度な近似解が得られる。
【０００９】
また特許文献１では、最適化計算において主流な分枝限定法などにおいて、探索する枝を決定する際に、計算の困難度を判定してその結果に応じて問題を分割することで、効率的に解を探索する手法が提案されている。
【００１０】
また特許文献２では、すでに検出されている解情報を利用することにより、探索処理時間の短縮と探索処理に必要なメモリ量の削減を可能にする手法が提案されている。何度も同じ最適化問題を解く場合には、過去に得られた解を再利用することで、無駄な探索を省くことが可能となる。
【先行技術文献】
【特許文献】
（【００１１】以降は省略されています）

関連特許