探索木・Simple AI
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-3 とします． ノートブックの作成方法は第1回の資料を参照してください．
水差し問題
今回は 水差し問題（Jug Problem） を取り上げましょう．
水差し問題
3リットルと4リットルのコップ（水差し）がある．
4リットルのコップに正確に2リットルの水を入れるにはどうしたらよいか．
この問題を 状態空間モデル で表現します． 状態空間モデルとは，探索過程の途中経過を 状態， またその状態間の遷移を 行動(操作) として表現したモデルです． 一般に，行動の結果，1通りに状態が定まるとき， 確定システム , 確率的に状態が変化するとき， 確率システム と呼ばれます． 現実世界の事象の多くは 確率システム となりますが， ここではシンプルな 確定システム のみを対象とします．
状態空間モデル
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を定義します．
オーバライドするメソッドは，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で選択可能な行動のリストを返します．
ここでは，上記で定義した8つの行動が該当します．
また，state[0]は3Lのコップの水量，state[1]は4Lのコップの水量を表します．
minとmaxは，それぞれ引数の最小値と最大値を選択するメソッドです．
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
result(self, state, action)
このメソッドでは，状態stateで，行動actionを実行したときに遷移する次の状態を返します．
ここでは，行動actionを，そのまま次の状態として扱います．
def result(self, state, action):
return action
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)となっており目的状態に到達できたことがわかります．
また，パスは(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 という可視化ツールを利用することができます（GraphVizのインストールが必要）． WebViewerを起動すると http://localhost:8000 というURLで結果を確認することができます． 可視化することで目的状態を発見するまでの過程が明確になります． この過程を確認すると，状態が 木の形 に展開されていることがわかります． このため，このような探索手順は 探索木 と呼ばれます．
from simpleai.search.viewers import WebViewer
web_viewer = WebViewer()
result = breadth_first(problem, graph_search=True, viewer=web_viewer)
