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

ノートブックの作成

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_row，taxi_col，お客の乗車位置（状態）pass_loc，お客の降車位置dest_idxです．

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

Red(0)
Green(1)
Yellow(2)
Blue(3)
Taxi(4)

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

Red(0)
Green(1)
Yellow(2)
Blue(3)

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

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

South(0): 南に移動
North(1): 北に移動
East(2): 東に移動
West(3): 西に移動
Pickup(4): 乗車
Drop-off(5): 降車

実装

環境の初期化

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

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

Discrete(6)
Discrete(500)

ここで，実行結果の理解を簡単にするため，下記のように辞書PASSENGER，DESTINATIONS，ACTIONSを定義しておきます．

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_row，taxi_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_row, taxi_col, pass_loc, dest_idex
報酬reward
終了判定done
その他の情報info（ここでは利用しない）

タクシーは南に移動したため，taxi_rowが3から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_row，taxi_col，pass_loc，dest_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） をダウンロードして提出しなさい．提出の前に必ず下記の設定を行うこと．

ノートブックの設定で「セルの出力を除外する」のチェックを外す
ノートブックの変更内容を保存して固定

参考書籍

Top Back

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