探索木・Simple AI

Image from Gyazo

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) を取り上げましょう.

水差し問題

3リットルと4リットルのコップ(水差し)がある. 4リットルのコップに正確に2リットルの水を入れるにはどうしたらよいか. Image from Gyazo

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

状態空間モデル

3リットルのコップの水の量を$x$, 4リットルのコップの水の量を$y$と表し, この組み合わせを状態と定義する. $$ (x, y) $$ コップに対する行動(操作)として下記の6つを定義する.

  • A1: 3Lのコップを満杯にする
  • A2: 4Lのコップを満杯にする
  • A3: 3Lのコップを空にする
  • A4: 4Lのコップを空にする
  • A5: 3Lのコップの水を溢れないように4Lのコップに移す
  • A6: 4Lのコップの水を溢れないように3Lのコップに移す

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を定義します. オーバライドするメソッドは,actionsresultis_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のコップの水量を表します. minmaxは,それぞれ引数の最小値と最大値を選択するメソッドです. 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が目的状態かどうかを判定します. ここでは,状態stateGOALと一致すれば目的状態に達したと判断します.

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

Image from Gyazo

課題

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

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

参考書籍

愛知県名古屋市にある椙山女学園大学 文化情報学部 向研究室の公式サイトです. 専門は情報科学であり,人工知能やデータベースなどの技術要素を指導しています. この公式サイトでは,授業で使用している教材を公開すると共に, ベールに包まれた女子大教員のミステリアスな日常を4コマ漫画でお伝えしていきます. サイトに関するご意見やご質問はFacebookまたはTwitterでお問い合わせください.