「水差し問題」の実装

Image from Gyazo

Simple AIとは

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

最初に,Simple AI をインストールします. pydotとflaskは探索過程を可視化ためのライブラリです. インストールには pip というパッケージ管理コマンドを利用します. インストールしたフォルダで,PowerShellを起動し,下記のコマンドを実行してください(Shiftキーを押しながら右クリック).

> .\Scripts\pip install simpleai
> .\Scripts\pip install pydot
> .\Scripts\pip install flask

ノートブックの作成

Jupyter Notebook を起動し,新規にノートブックを作成してください. ノートブックのタイトルは AI-1 とします.

Image from Gyazo

水差し問題

今回は 水差し問題(Jug Problem) を取り上げましょう.

水差し問題

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

この問題を 状態空間モデル で表現します.

状態空間モデル

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

  • A1: 3Lのコップを満杯にする
  • A2: 4Lのコップを満杯にする
  • A3: 3Lのコップを空にする
  • A4: 4Lのコップを空にする
  • A5: 3Lのコップを4Lのコップに移し満杯にする
  • A6: 4Lのコップを3Lのコップに移し満杯にする
  • A7: 3Lのコップの水を全て4Lのコップに移す
  • A8: 4Lのコップの水を全て3Lのコップに移す

実装

クラスの定義

最初にライブラリをインポートします. ここでは,探索問題の型 を表す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種類です.

actions(self, state)

このメソッドでは,状態stateで選択可能な行動のリストを返します. ここでは,上記で定義した8つの行動が該当します. また,state[0]は3Lのコップの水量,state[1]は4Lのコップの水量を表します. minmaxは,それぞれ引数の最小値と最大値を選択するメソッドです.

result(self, state, action)

このメソッドでは,状態stateで,行動actionを実行したときに遷移する次の状態を返します. ここでは,行動actionを,そのまま次の状態として扱います.

is_goal(self, state)

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

class JugProblem(SearchProblem):

    def actions(self, state):

        a1 = (3, state[1])
        a2 = (state[0], 4)
        a3 = (0, state[1])
        a4 = (state[0], 0)

        g1 = max(state[0] - (4 - state[1]), 0) #3Lのコップの水量
        g2 = min(state[1] + state[0], 4) #4Lのコップの水量
        a5 = (g1, g2)

        g1 = min(state[0] + state[1], 3) #3Lのコップの水量
        g2 = max(state[1] - (3 - state[0]), 0) #4Lのコップの水量
        a6 = (g1, g2)

        a7 = (0, min(state[1] + state[0], 4))
        a8 = (min(state[0] + state[1], 3), 0)

        list = [a1, a2, a3, a4, a5, a6, a7, a8]

        return list

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

    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)となっており目的状態に到達できたことがわかります. また,パスは(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)), ((3, 0), (3, 0)), ((0, 3), (0, 3)), ((3, 3), (3, 3)), ((2, 4), (2, 4)), ((2, 0), (2, 0)), ((0, 2), (0, 2))]
Cost: 6

探索過程の可視化

最後に探索過程を可視化してみましょう. Simple AIでは,WebViewer という可視化ツールを利用することができます. WebViewerを起動すると http://localhost:8000 というURLで結果を確認することができます. 可視化することで目的状態を発見するまでの過程が明確になります.

from simpleai.search.viewers import WebViewer

web_viewer = WebViewer()
result = breadth_first(problem, graph_search=True, viewer=web_viewer)

Image from Gyazo

課題

3リットルのコップに正確に1リットルの水を入れるための解を求めなさい. 作成したノートブックを HTML(.html) 形式でダウンロードし提出しなさい.

参考書籍

スポンサーリンク