強化学習を用いた迷路探索part1

プログラミング

記事構成

本記事では、強化学習のプログラムをいきなり実装するわけではなく、まずはどの方向にも同確率でランダムに進むAIとは関係はないアルゴリズムを実装します。

その後part2, part3にて強化学習による迷路探索の実装を行い、比較をするという内容になります。

教科学習のみに興味ある方はpart1, はスキップし,part2, part3へ移動してください。

強化学習とは

強化学習(きょうかがくしゅう、: reinforcement learning)とは、ある環境内におけるエージェントが、現在の状態を観測し、取るべき行動を決定する問題を扱う機械学習の一種。エージェントは行動を選択することで環境から報酬を得る。強化学習は一連の行動を通じて報酬が最も多く得られるような方策(policy)を学習する。環境はマルコフ決定過程として定式化される。代表的な手法としてTD学習Q学習が知られている。

wikipedia

と記述があります。

例えば、迷路で言うならば、マス目に報酬(お金など)を置き、そこを優先して進む手法です。

迷路探索と強化学習

迷路はどのようにして解く?

以下のような迷路があった時、どのようにしてSTARTからGOALへ向かいますか?

おそらく多くの方は以下のように青い経路黒い経路の2つの最短経路を選択したはずです。

これを機械に探索させると「STARTから右の位置にも進み、GOALまでの最短経路ではなく、ランダムに進んだ結果GORLに辿り着く」となります。なお、本記事Part1で扱う内容はランダムでGOALに行くアルゴリズムになります。

これを機械にも、人間と同じようにGOALまで行って欲しいと思った結果出てくるのがPart2, Part3に出てくる強化学習を経たAIとなります。詳細は、Part2, Part3で紹介します。

本記事で扱う迷路図

Pythonを用いて迷路を記述しました。

以下の迷路を扱います。

Pythonで実装

迷路を描く

import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline # jupyter notebook用

fig = plt.figure(figsize=(5, 5))
ax = plt.gca()

## 障害となる壁の記述
plt.plot([1, 2], [2, 2], color="r", linewidth=3)
plt.plot([2, 2], [2, 3], color="r", linewidth=3)
plt.plot([1, 3], [1, 1], color="r", linewidth=3)

## マス目の記述
plt.text(0.5, 2.5, 'S0', size=14, ha='center')
plt.text(1.5, 2.5, 'S1', size=14, ha='center')
plt.text(2.5, 2.5, 'S2', size=14, ha='center')
plt.text(0.5, 1.5, 'S3', size=14, ha='center')
plt.text(1.5, 1.5, 'S4', size=14, ha='center')
plt.text(2.5, 1.5, 'S5', size=14, ha='center')
plt.text(0.5, 0.5, 'S6', size=14, ha='center')
plt.text(1.5, 0.5, 'S7', size=14, ha='center')
plt.text(2.5, 0.5, 'S8', size=14, ha='center')
plt.text(0.5, 2.3, 'START', ha='center')
plt.text(2.5, 0.3, 'GOAL', ha = 'center')

ax.set_xlim(0, 3)
ax.set_ylim(0, 3)
plt.tick_params(axis='both', which='both', bottom='off', top='off',
                labelbottom='off', right='off', left='off', labelleft='off')

line, = ax.plot([0.5], [2.5], marker="o", color='y', markersize=60)

実行すると、迷路図が出力されます。

各マスの行動条件

人間には、マス目があり、壁があり、STARTとGOALという字があり、それを見ただけでこれが迷路だとわかり、どのようにするべきか、判断できますが、

コンピュータからすれば、ただのグラフです。

そこで各マスにおける行動条件を記します。

# 以下の配列の中身は↑, →, ↓, ←の順に表しておりそれぞれの方向に進めるかどうかを記しています。
# 1は進めるnp.nan進めない。 
behavioral_condition = np.array([[np.nan, 1, 1, np.nan], #S0
                    [np.nan, np.nan, np.nan, 1], #S1
                    [np.nan, np.nan, 1, np.nan], #S2
                    [1, 1, 1, np.nan],      #S3
                    [np.nan, 1, np.nan, 1], #S4
                    [1, np.nan, np.nan, 1], #S5
                    [1, 1, np.nan, np.nan], #S6
                    [np.nan, 1, np.nan, 1], #S7
])

各マスにおける行動の確率を算出

# やっていることは、behavioral_conditionにそれぞれ進める方向の数で割った値を出力しているだけです。
# 例えば、S0だと進める方向は2なので2で割ると[0, 0.5, 0.5, 0]という感じです。
def calculate_probability(behavioral_condition):

  [m, n] = behavioral_condition.shape
  probability = np.zeros((m, n))
  for i in range(0, m):
    probability[i, :] = behavioral_condition[i, :] / np.nansum(behavioral_condition[i, :])
  probability = np.nan_to_num(probability)

  return probability

probability = calculate_probability(behavioral_condition)

ではprobabilityの中身を出力してみましょう

print(probability)

以下の出力が表示されます

array([[0.        , 0.5       , 0.5       , 0.        ],
       [0.        , 0.        , 0.        , 1.        ],
       [0.        , 0.        , 1.        , 0.        ],
       [0.33333333, 0.33333333, 0.33333333, 0.        ],
       [0.        , 0.5       , 0.        , 0.5       ],
       [0.5       , 0.        , 0.        , 0.5       ],
       [0.5       , 0.5       , 0.        , 0.        ],
       [0.        , 0.5       , 0.        , 0.5       ]])

行動した時の状態

次のマスに移った時にコンピュータ側にどのように読み込ませるかの記述を行います。

先にコードを見せます。

def get_next_s(probability, s):
  direction = ["up", "right", "down", "left"]

  next_direction = np.random.choice(direction, p = probability[s, :])

  if next_direction == "up":
    s_next = s - 3
  elif next_direction == "right":
    s_next = s + 1
  elif next_direction == "down":
    s_next = s + 3
  elif next_direction == "left":
    s_next = s - 1

  return s_next

まず、行動をコードで記述するときに二次元だし、壁あるしって考えると考えることが多くなり、頭がパンクしてしまいます。

1つ1つ分けて考えることが重要です。実は壁の条件は上の方でしました。

え?どこで??=>>各マスでの行動条件です。

じゃ、進んだ時どのように扱うのか!!

迷路の壁を全部取った状態で、二次元を一次元に変換した図を考えます。

一次元にします。

そうするとS0の位置を初期値とした時にS0よりどれくらい右に進むとS8に行くのかを考えると、、

S0->S8の間で+8となります。つまり、S0からS8に進むのに+8すれば良いのです。

S0の状態を0と考えると合計のMAXは8になります。そして8になったときにゴールになることが明らかだと思います。

それを考慮にして二次元での行動を考えると、左右に進むのは+-1で問題ないでしょう。

上下に進むのは+-3とすると二次元の座標で移動したことになります。

ゴールまでのプロセス

各マスにおける行動確率、各マスにおける状態の記述が済んでいるので、あとは、簡単です。

それを繋いでゴールに着くまでひたすらループさせます。

def process_to_goal(probability):
  # 初期条件
  s = 0
  history = [0]
  # 移動を繰り返す
  while (1):
    next_s = get_next_s(probability, s)
    history.append(next_s)  # 行動を記録
    # ゴールに着いたら終了
    if next_s == 8:
      break # ゴールに着いたら終了
    else:
      s = next_s # ゴールでなければ繰り返す

  return history

では、ゴールまでのプロセスを出力します

history = process_to_goal(probability)
print(history)
print("迷路を解くのにかかったステップ数は" + str(len(history) - 1) + "です")

出力結果は毎回ランダムです。同じ結果にはならなくても安心してください。

[0, 3, 0, 1, 0, 3, 0, 1, 0, 1, 0, 3, 0, 3, 4, 5, 2, 5, 4, 3, 6, 7, 6, 7, 6, 3, 6, 7, 6, 3, 0, 1, 0, 1, 0, 3, 6, 7, 6, 3, 4, 5, 4, 5, 4, 3, 0, 3, 0, 1, 0, 1, 0, 3, 4, 5, 2, 5, 4, 5, 4, 3, 6, 7, 6, 3, 4, 3, 6, 7, 6, 7, 8]
迷路を解くのにかかったステップ数は72です

ゴールまでのプロセスを可視化

from matplotlib import animation
from IPython.display import HTML


def init():
  line.set_data([], [])
  return (line, )

def animate(i):
  state = history[i]
  x = (state % 3) + 0.5
  y = 2.5 - int(state / 3)
  line.set_data(x, y)
  return (line,)


anim = animation.FuncAnimation(fig, animate, init_func=init, frames = len(history), interval=200, repeat=False)
HTML(anim.to_jshtml())

以上で本記事は終わりです。

この知識を踏まえてPart2, Part3にて強化学習の説明をします。

コメント

タイトルとURLをコピーしました