Means-End Analysis

概要

  • 初期状態から目標状態までの変化が一気にできないときに、中間目標を作って徐々に目標に近づいていける問題解決（Problem solving）の手法
  • 探索AIで一般的に用いられる
  • Forward searchとBackward searchを混合した手法とされる
  • 1959年のAllen NewellらによるGPS（General Problem Solver）というAIプログラムで初めて実装された

アルゴリズム

要素

  • ドメインの表現方法（状態など）
  • 表現を操作するための演算子
  • どの演算子が何を軽減できるかの情報

流れ

  1. 現在の状態と最終の状態の差を評価する
    • 差がなければ終了
  2. 使用可能な演算子のセットから、現在の状態に適用して現在の状態と目標の状態の差を減らすことができる演算子を選択
    • なければ失敗
    • あれば、演算子を適用して再度1.へ

GPS（Global Problem Solver）

  • 1959年にNewell、Shaw、Simonにより発表されたプログラム
  • ある程度までは、もともとある演算子のセットから新しい演算子を構築し、どの演算子がどの差異を軽減したかを学習することもできた
  • 当初、アルゴリズム上、場合によっては無限ループに入ることもあったが、演算子に条件を加えることで回避した
    （if-then 形式の命令：productions）

論文で挙げられた具体例

http://bitsavers.informatik.uni-stuttgart.de/pdf/rand/ipl/P-1584_Report_On_A_General_Problem-Solving_Program_Feb59.pdf

参考

項目調査まとめAI

Posted by ttnt