強化学習・タクシーゲーム

Image from Gyazo

ノートブックの作成

Jupyter Notebook を起動し,新規にノートブックを作成してください. ノートブックのタイトルは AI-16 とします. ノートブックの作成方法は第1回の資料を参照してください.

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

> !pip install gym

また,OpenAI Gymに加え,下記のライブラリも導入しておきましょう.

import gym
import numpy as np
import random
import time
from google.colab import output
from tqdm.notebook import tqdm

タクシーゲーム(Taxi)

タクシーゲーム(Taxi)は,乗車地まで移動し,お客を乗せて(Pickup),降車地まで移動し,お客を降ろす(Drop off)ことを目的としたゲームです.

環境は下記のように$5\times5$で表されます. R(Red)G(Green)Y(Yellow)B(Blue) は, お客の乗車地,または,降車地です. また,| は壁であり,タクシーが通過することはできません.

+---------+
|R: | : :G|
| : | : : |
| : : : : |
| | : | : |
|Y| : |B: |
+---------+

タクシーが観測できる情報は,タクシーの位置座標taxi_rowtaxi_col,お客の乗車位置(状態)pass_loc,お客の降車位置dest_idxです.

タクシーの位置座標は,行列の番号で表され,$5\times5=25$パターンがあります. お客の乗車位置(状態)は下記の$5$パターンがあります. Taxi(4) は,お客がタクシーに乗車している状態を表します.

お客の降車位置は下記の$4$パターンがあります.

よって,タクシーゲームにおける状態の組み合わせは$25 \times 5 \times 4 = 500$パターンです.

また,タクシーは下記のいずれかの行動をとることが出来ます.

実装

環境の初期化

最初に対象とする環境を作成します. ここでは,タクシーゲーム(Taxi-v3)を指定します. このゲームの 行動 は6種類の離散値, また,状態空間 は500種類の離散値であることが確認できます.

env = gym.make('Taxi-v3') # 環境の初期化
print(env.action_space)
print(env.observation_space)
Discrete(6)
Discrete(500)

ここで,実行結果の理解を簡単にするため, 下記のように辞書PASSENGERDESTINATIONSACTIONSを定義しておきます.

PASSENGER = {
    0: "Red",
    1: "Green",
    2: "Yellow",
    3: "Blue",
    4: "Taxi"
}

DESTINATIONS = {
    0: "Red",
    1: "Green",
    2: "Yellow",
    3: "Blue"
}

ACTIONS = {
    0: "South",
    1: "North",
    2: "East",
    3: "West",
    4: "Pickup",
    5: "Drop-off"
}

プレイヤーの行動

環境を初期化して,env.render()でタクシーの環境を文字列で可視化します. ここで,観測された状態stateは,env.decode()でタクシーの位置座標taxi_rowtaxi_col,お客の乗車位置(状態)pass_loc,お客の降車位置dest_idxに変換します.

state = env.reset()
env.render()

taxi_row, taxi_col, pass_loc, dest_idx = env.decode(state)
print(f"taxi_row={taxi_row} taxi_col={taxi_col} pass_loc={PASSENGER[pass_loc]} dest_idex={DESTINATIONS[dest_idx]}")
+---------+
|R: | : :G|
| : | : : |
| : : : : |
| | : | : |
|Y| : |B: |
+---------+

taxi_row=3 taxi_col=0 pass_loc=Yellow dest_idex=Red

次に,step()を利用して,行動を選択します. ここでは,タクシーを南に移動させてみます. step()の引数に「南に移動する」を表す 0(=SOUTH) を指定します. この行動の結果は下記の情報で表されます.

タクシーは南に移動したため,taxi_row3から4に変化していることがわかります.報酬はお客を正しく乗車,降車させたときに20,異なる場所で乗車,降車したときは-10,それ以外は-1に設定されています.

action = 0 # 南に移動
next_state, reward, done, info = env.step(action)
taxi_row, taxi_col, pass_loc, dest_idx = env.decode(next_state)
env.render()
print(f"action={ACTIONS[action]}")
print(f"taxi_row={taxi_row} taxi_col={taxi_col} pass_loc={PASSENGER[pass_loc]} dest_idex={DESTINATIONS[dest_idx]}")
print(f"reward={reward}")
print(f"done={done}")
+---------+
|R: | : :G|
| : | : : |
| : : : : |
| | : | : |
|Y| : |B: |
+---------+
  (South)
action=South
taxi_row=4 taxi_col=0 pass_loc=Yellow dest_idex=Red
reward=-1
done=False

ランダムにタクシーを移動

ランダムにタクシーを移動させてみます. random.choice()は引数で与えられたリストからランダムに一つを選びます. ここでは,[0, 1, 2, 3, 4, 5]を引数とするため,上下左右と乗車・降車から一つが選択されます. この結果,報酬は-1,終了状態はFalseであることがわかります.

state = env.reset()

for i in range(10):
  action = random.choice([0, 1, 2, 3, 4, 5])
  next_state, reward, done, info = env.step(action)
  taxi_row, taxi_col, pass_loc, dest_idx = env.decode(next_state)
  output.clear()
  env.render()
  time.sleep(1)

  if done:
    break

print(f"taxi_row={taxi_row} taxi_col={taxi_col} pass_loc={PASSENGER[pass_loc]} dest_idex={DESTINATIONS[dest_idx]}")
print(f"reward={reward}")
print(f"done={done}")
+---------+
|R: | : :G|
| : | : : |
| : : : : |
| | : | : |
|Y| : |B: |
+---------+
  (South)
taxi_row=4 taxi_col=2 pass_loc=Green dest_idex=Blue
reward=-1
done=False

Q学習

Qテーブル

価値$Q(s,a)$を記録するための辞書を作成します. $s$は,taxi_rowtaxi_colpass_locdest_idxのタプルで表現され.500パターンが存在します. $a$は$0,1,2,3,4,5$の6パターンが存在します. よって,$500 \times 6 = 3000$パターンの$Q$を記録する必要があります. 全ての$Q$は0.01で初期化しておきます.

qtable = {}

for taxi_row in range(5):
  for taxi_col in range(5):
    for pass_loc in range(5):
      for dest_idx in range(4):
        #print(f"{taxi_row} {taxi_col} {pass_loc} {dest_idx}")
        state = (taxi_row, taxi_col, pass_loc, dest_idx)
        qtable[state] = [0.01, 0.01, 0.01, 0.01, 0.01, 0.01]

$Q$を設定するための関数setQ()と, $Q$を取得するための関数getQ()を定義しておきます.

def setQ(state, action, value):
  qtable[state][action] = value

def getQ(state, action):
  return qtable[state][action]

Q値の更新

$Q$の更新式を表すupdateQ()を定義します. 割引率$\alpha$は0.1,割引率$\gamma$は0.9に設定します. np.max()で最大の$Q$を選択していることに注意してください.

alpha = 0.1 # 学習率
gamma = 0.9 # 割引率

def updateQ(state, action, next_state, reward):
  max_value = np.max([getQ(next_state, 0), getQ(next_state, 1), getQ(next_state, 2), getQ(next_state, 3), getQ(next_state, 4), getQ(next_state, 5)])
  value = (1 - alpha) * getQ(state, action) + alpha * (reward + gamma * max_value)
  setQ(state, action, value)

行動戦略

プレイヤーの行動は$\epsilon$-グリーディ戦略で決定します. $\epsilon$-グリーディ戦略では,確率$\epsilon$でランダムに行動を選択し, 確率$1-\epsilon$で$Q$が最大となる行動を選択します.

def greedyAction(state, epsilon):    

    if epsilon > np.random.rand():
        action = random.choice([0, 1, 2, 3, 4, 5])
    else:
        action = np.argmax([getQ(state, 0), getQ(state, 1), getQ(state, 2), getQ(state, 3), getQ(state, 4), getQ(state, 5)])

    return action

学習プロセス

プレイヤーの行動を繰り返すことで$Q$を学習します. プレイヤーは終了判定がTrueになるまで,最大100回まで行動を繰り返します. このプレイヤーの行動を10000回繰り返します. env.decode()はリストを返すため,tuple()でタプルに変換していることに注意してください. $\epsilon$は0.2に設定しています. また,tqdm()は繰り返しの進捗を表すプログレッシブ・バーを表示するための関数です.

epsilon = 0.2

for episode in tqdm(range(10000)):
  state = env.reset()

  for i in range(100):
    action = greedyAction(tuple(env.decode(state)), epsilon)
    next_state, reward, done, info = env.step(action)
    updateQ(tuple(env.decode(state)), action, tuple(env.decode(next_state)), reward)
    state = next_state

    if done:
      break

学習したQを利用してプレイヤーを行動させます. $\epsilon$を0に設定し,常に$Q$が最大の行動を選択します. この結果,お客をG(=Green)に送り届け,報酬として20を受け取り,終了判定がTrueになっていることが確認できます.

epsilon = 0

state = env.reset()

for i in range(100):
  action = greedyAction(tuple(env.decode(state)), epsilon)
  next_state, reward, done, info = env.step(action)
  state = next_state
  output.clear()
  env.render()
  time.sleep(1)

  if done:
    break

taxi_row, taxi_col, pass_loc, dest_idx = env.decode(next_state)
print(f"taxi_row={taxi_row} taxi_col={taxi_col} pass_loc={PASSENGER[pass_loc]} dest_idex={DESTINATIONS[dest_idx]}")
print(f"reward={reward}")
print(f"done={done}")
+---------+
|R: | : :G|
| : | : : |
| : : : : |
| | : | : |
|Y| : |B: |
+---------+
  (Dropoff)
taxi_row=0 taxi_col=4 pass_loc=Green dest_idex=Green
reward=20
done=True

課題

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

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