自動定理証明を問題縮小に利用する高性能プランニングアルゴリズムの開発

点击翻译按钮获取中文摘要

本研究では古典的なドメイン非依存プランニング問題を解くアルゴリズムの高性能化に取り組んだ。人工知能エージェントが活動するにあたってどのような手順で行動すれば目標を達成できるかを考える問題をプランニング問題といい、エージェントの能力や外部環境なども入力として与えられる問題をドメイン非依存プランニングと呼ぶ。本年度は昨年度とは異なり、問題を解くアルゴリズムの高速化ではなく、プランニング問題を構成する要素のうち不要なものを自動的に探しだし（すなわち要素が不要であることを証明し）、問題を簡約する二つのアルゴリズムを開発した。まず一つ目の簡約アルゴリズムは削除効果緩和問題の不要な要素を取り除く簡約手法である。削除効果緩和問題は、プランニング問題を分枝限定法などによって解くにあたり、各状態から目標状態までのコストを見積もるために非常によく利用されている緩和問題である。この緩和問題を自動的に簡約する手法をプランニングアルゴリズムと組み合わせることにより従来よりも高速に問題を解くことができるようになると期待される。二つ目の簡約アルゴリズムは、緩和問題ではなく一般の問題を簡約するためのアルゴリズムである。この手法では、問題を構成する要素の相互の関係を利用して不要な要素を判別している。この簡約手法は問題を解くためのプランニングアルゴリズムの構造とは無関係であるため、広く一般のプランニングアルゴリズムを高速化できるものと考えられる。