探索木・Simple AI

Simple AIとは

Simple AIは，Stuart Russel氏とPeter Norvig氏が執筆した 「Artificial Intelligence: A Modern Approach」に掲載されている 人工知能で用いられる伝統的なアルゴリズムを提供するPythonのライブラリです． このライブラリを導入することで， 幅優先探索などの 探索アルゴリズム，遺伝的アルゴリズムなどの 進化的アルゴリズム， 決定木などの 機械学習アルゴリズム を簡単に実装することが可能です． ここでは，授業で紹介したアルゴリズムを Simple AI で実装することで， 知識を定着させ，様々な問題に応用できるようになることを目指します．

ノートブックの作成

Google Colaboratory を起動し，新規にノートブックを作成してください． ノートブックのタイトルは AI-3 とします． ノートブックの作成方法は第1回の資料を参照してください．

最初に Simple AI をインストールします． セルで下記のコマンドを実行してください．

!pip install simpleai

水差し問題

今回は 水差し問題（Jug Problem） を取り上げましょう．

この問題を 状態空間モデル で表現します． 状態空間モデルとは，探索過程の途中経過を 状態， またその状態間の遷移を 行動(操作) として表現したモデルです． 一般に，行動の結果，1通りに状態が定まるとき， 確定システム , 確率的に状態が変化するとき， 確率システム と呼ばれます． 現実世界の事象の多くは 確率システム となりますが， ここではシンプルな 確定システム のみを対象とします．

See the Pen Tower of Hanoi by Naoto Mukai (@nmukai) on CodePen.

実装

クラスの定義

最初にライブラリをインポートします． ここでは，探索問題の型 を表すSearchPrblemと 幅優先探索 を表すbreadth_firstをインポートします（幅優先探索に関しては第4回で解説予定）．

from simpleai.search import SearchProblem, breadth_first

次に 初期状態 と 目的状態 を定義します． 初期状態は両方のコップに水がない状態を表す (0, 0)， 目的状態は4リットルのコップに2リットルの水がある状態を表す(0, 2)です．

START = (0, 0)
GOAL  = (0, 2)

インポートしたSearchProblemクラスをオーバライドして， 水差し問題を表すJogProblemを定義します． オーバライドするメソッドは，actions，result，is_goalの3種類です．

class JugProblem(SearchProblem):

    def actions(self, state):
        ...

    def result(self, state, action):
        ...

    def is_goal(self, state):
        ...

actions(self, state)

このメソッドでは，状態stateで選択可能な行動のリストを返します． ここでは，上記で定義した6つの行動を文字列のリストとして表現します．

def actions(self, state):
  return ["A1", "A2", "A3", "A4", "A5", "A6"]

result(self, state, action)

このメソッドでは，状態stateで，行動actionを実行したときに遷移する次の状態を返します． また，state[0]は3Lのコップの水量，state[1]は4Lのコップの水量を表します． minとmaxは，それぞれ引数の最小値と最大値を選択するメソッドです． if文を利用して，行動actionに応じて，コップの状態を変化させています．

def result(self, state, action):

  if action == "A1":
    s = (3, state[1])
  elif action == "A2":
    s = (state[0], 4)
  elif action == "A3":
    s = (0, state[1])
  elif action == "A4":
    s = (state[0], 0)
  elif action == "A5":
    g1 = max(state[0] - (4 - state[1]), 0) #3Lのコップの水量
    g2 = min(state[1] + state[0], 4) #4Lのコップの水量
    s = (g1, g2)
  elif action == "A6":
    g1 = min(state[0] + state[1], 3) #3Lのコップの水量
    g2 = max(state[1] - (3 - state[0]), 0) #4Lのコップの水量
    s = (g1, g2)

  return s

is_goal(self, state)

このメソッドでは，状態stateが目的状態かどうかを判定します． ここでは，状態stateがGOALと一致すれば目的状態に達したと判断します．

def is_goal(self, state):
  return state == GOAL

解の探索

幅優先探索（探索木）breadth_firstを用いて解を探索します． 解とは初期状態STARTから，目的状態GOALまでのパス（経路）を意味します． 探索過程における冗長な状態を省略するためにgraph_search=Trueという引数を設定していることに注意してください．

problem = JugProblem(initial_state=START)
result = breadth_first(problem, graph_search=True) #幅優先探索

探索が終了したら，最終状態，パス，コストを表示します． 最終状態は(0,2)となっており目的状態に到達できたことがわかります． A1,A5,A1,A5,A4,A5の順にルールを適用した結果， パスは(0, 0), (3, 0), (0, 3), (3, 3), (2, 4), (2, 0), (0, 2)となりました． このとき，初期状態から目的状態までのコスト（ステップ数）は6です．

print("State:", result.state)
print("Path:", result.path())
print("Cost:", result.cost)

State: (0, 2)
Path: [(None, (0, 0)), ('A1', (3, 0)), ('A5', (0, 3)), ('A1', (3, 3)), ('A5', (2, 4)), ('A4', (2, 0)), ('A5', (0, 2))]
Cost: 6

探索木（解の探索過程）

初期状態(0, 0)から目的状態(0, 2)までの探索過程は次の図で表すことができます． 初期状態(0, 0)に適用可能な行動は，A1とA2のいずれかです（その他の行動は状態に変化がないため）． A1を適用すると，3Lのコップに水を満杯にするため，状態は(3, 0)になります． 同様にA2を適用すると，4Lのコップに水を満杯にするため，状態は(0, 4)になります． この新しく生成された状態に対し，さらに適用可能な行動を繰り返し，目的状態(0, 2)に到達すると探索は終了です． この探索は，木の形 に状態が展開されていくことから，探索木 と呼ばれます． 探索過程において，既に探索済みの状態が生成された場合があります． 例えば，状態(3, 0)に，A3を適用すると，3Lのコップを空にするため，初期状態の(0, 0)に戻ってしまいます． (0, 0)は既に探索済みのため，次の行動を適用して，新たな状態を生成する必要はないことになります． この結果，水差し問題において探索した状態数は 12 という結果でした（水差し問題の状態は，到達不可能な状態を除くと，14通り存在する）．

課題

両方のコップが空の状態(0, 0)から始め， 3リットルのコップに正確に1リットルの水を入れた状態(1, 0)に到達するための解を求めなさい．

Google Colaboratoryで作成した AI-3.ipynb を保存し， ノートブック（.ipynb） をダウンロードして提出しなさい． 提出の前に必ず下記の設定を行うこと．

• ノートブックの設定で「セルの出力を除外する」のチェックを外す
• ノートブックの変更内容を保存して固定