🗃

Math＆Julia #13｜強化学習 » Q学習 » 迷路探索

2025/11/29に公開

 はじめに強化学習（Reinforcement Learning）による迷路探索を実装します。この迷路探索では迷路の構造（通路，壁，ゴール）を学習した後であれば、どこにスタート地点を設定してもゴール地点までの最適経路を割り出すことができます。

 Q学習による迷路探索迷路探索のアルゴリズムとして、強化学習の一種であるQ学習（Q-learning）を採用します。Q学習において、エージェントは環境から得られる報酬を最大化するように行動を学習します。Q学習には、ヒューマノイド制御，アルファ碁，創薬などの応用に通じる基本的な概念が凝縮されており、強化学習を学ぶ最初のステップとして適しています。ここでは、誰にでも馴染みのある迷路探索を通じてQ学習の基本原理を見ていきます。

 実行サンプル本節を読み進めるための視覚的な手掛かりとして、ハンズオンの学習フェーズと推論フェーズからそれぞれ1枚ずつ画像を選んで図 1にまとめました。左側はQテーブルのヒートマップで、右側はスタート地点を (5,10) に設定したときの最適経路を推論したものです。


図 1　実行サンプル（左：学習フェーズ、右：推論フェーズ）

 基本要素
 エージェント（agent）エージェントは迷路を探索する主体です。エージェントは環境との相互作用を通じて、状態と行動の組(s,a)に対してQ値を更新します。

 環境（environment）環境はエージェントが作用する世界で、エージェントがとった行動aに対して報酬rを返します。迷路探索では、迷路の構造（通路，壁，ゴール）が環境です。

 状態（state）： \bold{s∈S}
状態sは、エージェントが迷路内のどこにいるのかを行列座標(r,c)で表します。

 行動（action）： \bold{a∈A}
行動aは、エージェントが迷路内でとれる行動（⇧，⇩，⇦，⇨）を表します。

 報酬（reward）： \bold{r∈R}
報酬rは、行動aに対して環境から即座に受け取るフィードバックで、Q値を更新するときの基礎になります。迷路探索で得られる報酬は、ゴール到達で大きな正の値、壁にぶつかった場合は負の値（ペナルティ）、それ以外の行動には小さな負の値（時間経過ペナルティ）とします。これにより、エージェントは壁を避けることを学習し、早くゴールする経路を好むようになります。

 Q値（Q-value）： \bold{Q(s,a)}
Q値 Q(s,a) は、状態sにおいて行動aを選んだときに将来得られる報酬の期待値を表します。最大Q値を持つ行動aを選ぶことは、今わかっている最善手を選ぶことになります。

 方策（policy）： \boldsymbol{π(s)}
エージェントは探索的な行動（新しい道を探す）と活用的な行動（今わかっている最善手を選ぶ）をバランス良く選択する必要があります。探索的（ランダム）な行動は、今は価値が低く見えていても実は価値の高い行動の発見を促し、局所最適解に陥るのを防ぎます。良く使われる方策であるε-greedy法では、探索的な行動と活用的な行動のバランスをハイパーパラメータの探索率εで調整します。

 エピソード（episode）エージェントはゴールを目指して「1. 行動選択 → 2. 報酬獲得 → 3. Q値更新」の手順を繰り返します。この繰り返しにより実際にゴールするか、もしくはステップ数の上限に達するまでを1エピソードとします。

 ハイパーパラメータ
 学習率： \boldsymbol{α}\enspace(0<α≤1)
学習率αは、新しい経験（TD誤差）をどれだけQ値に反映させるかを調整します。α が 1に近いほど新しい経験に対して積極的になり、0に近いほど保守的になります。一般的に、αが大き過ぎると学習が不安定になり、小さ過ぎると収束が遅くなります。

 割引率： \boldsymbol{γ}\enspace(0≤γ<1)
割引率γは、報酬の時間的な価値を調整します。γ が 1に近いほど将来の報酬を重視し、0に近いほど目先の報酬を重視します。迷路探索では 1に近い値を設定して、目先の報酬に頼らない探索を促します。

 探索率： \boldsymbol{ε}\enspace(0<ε≤1)
探索率εは、探索的な行動と活用的な行動のバランスを調整します。ε が 1に近いほど探索的になり、0に近いほど活用的になります。学習初期は ε を大きくしてランダムな探索を優先し、学習が進むにつれて ε を小さくして活用を優先します。本稿では実装を簡素化するために ε を固定します。

 ステップ数： \textbf{maxsteps}
1エピソードにおけるステップ数の上限を決めます。上限があると、極端に悪い状況に陥った場合でもやり直しの機会を得ることができます。これは、様々な経路を試す機会の増加にもつながります。

 エピソード数： \textbf{episodes}
エピソード数を適切に設定して学習に区切りをつけます。この区切りが、学習プロセスの分析と改善のタイミングになります。

 Qテーブルの構造Qテーブルは、状態と行動の組(s,a)に対するQ値を記録しておく辞書です。次の表は実際のQテーブルから最初の 4件を抽出したものです。


状態s

行動 (1) ⇧
行動 (2) ⇩
行動 (3) ⇦
行動 (4) ⇨


(4, 6)
–0.0439003
–0.0464883
–0.0364779
–0.0512670

(9, 3)
  0.0
  0.0
  0.0
  0.0

(5, 5)
–0.0236914
–0.0312670
  0.1465530
–0.0230647

(7, 8)
  0.2591130
  0.2130950
  0.2512060
  0.3735140

エージェントの現在地（状態s）が (5,5)であるとすれば、Q値が最大になっているのは行動 (3)なので、現在地での最適な行動は ⇦（左へ移動）であることが分かります。また、エージェントは壁 (9,3)に移動できないのでQ値は初期値の 0.0のまま更新されていません。

 学習フェーズ（迷路探索）​学習フェーズでは、1エピソードが終了するまでのあいだ次の1〜3の手順を繰り返すことでゴールを目指します。十分なエピソード数を繰り返すと​、ゴール地点に至る最適経路のQ値が高まった状態で安定（収束）します。

 行動選択エージェントは方策に従って現在地（状態s）での行動aを選択します。本稿で採用する方策はε-greedy法で次のように表されます。

   \tag{1}
   行動\,a=
   \begin{cases}
   \,ランダムな行動&確率\,ε&（探索）\\[4pt]
   \,\argmax_{a}Q(s,a)&確率\,1-ε&（活用）
   \end{cases}
   \argmax_{a}Q(s,a)は、現在地（状態s）においてQ値が最大になっている行動a\in\{1,2,3,4\}を選択します。

 報酬獲得選択した行動aを実行に移すと新しい状態s^{\prime}に遷移し、その結果として報酬rを獲得します。

 Q値更新Q値の更新にはTD誤差（Temporal Difference Error）を用います。TD誤差δ_{t}は次のように表されます。
\tag{2}δ_{t}=\underbrace{r+γ\,\max_{a^{\prime}}\,Q(s^{\prime},a^{\prime})}_{\footnotesize\text{目標のQ値}}-\underbrace{Q(s,a)}_{\footnotesize\text{現在のQ値}}\max_{a^{\prime}}\,Q(s^{\prime},a^{\prime})は、新しい状態s^{\prime}において最も価値の高い行動a^{\prime}のQ値（例: 0.12345）です。

 
Q値を更新するには、TD誤差δ_{t}に学習率αを掛けて現在のQ値に足します。
\tag{3}Q(s,a)←Q(s,a)+α\,δ_{t}
Q値の更新は Q(s^{\prime},a^{\prime})ではなく Q(s,a)に対して行われるため、ゴールで得られた高い報酬はスタート地点に向かって徐々に伝播していきます。

 推論フェーズ（経路検索）推論フェーズにおいて、スタート地点からゴール地点までの最適経路を辿るには、常に最大Q値を持つ行動aを選択します。このときの最適方策π^{*}(s)は次のように表されます。
π^{*}(s)=\argmax_{a}\,Q^{*}(s,a)記号の右肩に付いている^*は、強化学習の文脈においてその関数が「最適」であることを表しています。

 推論性能の向上エージェントは学習時に設定されたスタート地点からゴール地点までの最適な経路を探索するので、価値の低い経路の探索は手薄になります。もし推論フェーズにおいて、学習フェーズとは異なる場所にスタート地点を設定したいのであれば、探索範囲の網羅性を確保する必要があります。その方法として本稿のハンズオンでは、1つのQテーブルをスタート地点の異なる複数のQ学習で共有する方法（経験の再利用）を採用します。ただし、この方法では学習順序による偏りが懸念されるので、その場合は、1度のQ学習のなかで複数のスタート地点をバランス良く試す方法（マルチスタート学習）を検討しても良いと思います。Q学習はオフポリシーアルゴリズムであるため、どちらの方法をとってもQテーブルの整合性は保たれます。

 実装実装は、核心部と可視化部の 2つに分けて掲載します。

 核心部核心部は、次の 3つの主要な関数で構成されています。

Environment関数 — 環境，ステップ（行動，報酬）を管理します。

agent!関数 — 学習フェーズにおいて、迷路探索を行うエージェントです。

search_path関数 — 推論フェーズにおいて、最適経路を割り出します。

 
Julia
using CairoMakie, Random

@kwdef struct Q_parameter    # Q学習のハイパーパラメータ（デフォルト値）
    α = 0.1                  # 学習率
    γ = 0.9                  # 割引率
    ε = 0.2                  # 探索率 
    episodes = 400           # 学習エピソード数の上限
    maxsteps = 200           # 1エピソードにおける行動数の上限
end

const Qtable = Dict{Tuple{Int,Int}, Vector{Float64}}  # Qテーブルの型を定義
rc2xy(r, c) = (c, r)         # 行列座標を画像座標に変換

# 環境（迷路の構造＝通路，壁，ゴール）
function Environment(maze::Matrix, goal)
    rows, cols = size(maze)
    clip(r, c) = clamp(r, 1, rows), clamp(c, 1, cols)  # 移動範囲を迷路内に制限
    function step(s, act)
        function action()                    # 行動
            r, c = clip((s .+ act)...)       # 新しい場所を計算
            maze[r, c] == 1 ? s : (r, c)     # 新しい場所が壁であればその場に滞留
        end
        function reward(s′)                  # 報酬
            if s′ == goal
                ( 1.0,  true )               # ゴール → 報酬
            elseif s′ == s
                (-0.05, false)               # 滞留 → ペナルティ
            else
                (-0.01, false)               # 通路 → 時間経過ペナルティ
            end
        end
        s′ = action()
        s′, reward(s′)...                    # 状態（s′）, 報酬（r）, 終了フラグ（done）
    end
end

# エージェント（迷路探索）
function agent!(Q::Qtable, p::Q_parameter, actions::Vector, maze::Matrix, start, goal)
    step::Function = Environment(maze, goal)
    n = length(actions)
    ε_greedy(s) = rand() < p.ε ? rand(1:n) : argmax(Q[s])     # 方策
    δ(s,a,r,s′) = p.α * (r + p.γ * maximum(Q[s′]) - Q[s][a])  # TD誤差
    for _ in 1:p.episodes
        s = start                              # スタート地点に配置
        for _ in 1:p.maxsteps
            a = ε_greedy(s)                    # 行動を選択
            s′, r, done = step(s, actions[a])  # 新しい場所に移動して報酬を獲得
            Q[s][a] += δ(s,a,r,s′)             # Q値を更新
            done && break                      # ゴールなら1エピソード終了
            s = s′
        end
    end
end

# 経路検索（Qテーブルを参照して最適な経路を割り出す）
function search_path(Q::Qtable, actions::Vector, maze::Matrix, start, goal)
    step::Function = Environment(maze, goal)
    maxlog = 50
    s = start                                # スタート地点に配置
    log = Point2i[s]                         # 経路ログ
    while length(log) ≤ maxlog               # ログに異常な肥大化がない間だけ繰り返す
        a = argmax(Q[s])                     # Q値が一番大きいものを次の行動（移動方向）とする
        s′, _, done = step(s, actions[a])    # 次の行動
        push!(log, s′)                       # 新しい場所を経路ログに記録する
        done && break                        # ゴールなら経路の割り出しに成功
        (s′ == s || s′ in log) && break      # 滞留または経路がループしたら検索を打ち切る
        s = s′
    end
    log
end

 可視化部可視化部は、次の 2つの主要な関数で構成されています。

vis_heatmap_qtable関数 — 学習フェーズにおいて、Qテーブルをヒートマップ化します。

vis_maze_path関数 — 推論フェーズにおいて、迷路内に最適経路を描きます。

 
Julia
# 終端（スタート、ゴール）を描画
function draw_terminal(ax, start, goal)
    start′ = rc2xy(start...)
    goal′  = rc2xy(goal...)
    scatter!(ax, start′, marker=:circle, markersize=36, color=:green)
    scatter!(ax, goal′,  marker=:circle, markersize=36, color=:red3)
    text!(ax, "S", position=start′, align=(:center,:center), fontsize=22, color=:white)
    text!(ax, "G", position=goal′,  align=(:center,:center), fontsize=22, color=:white)
end

# Qテーブルをヒートマップで可視化
function vis_heatmap_qtable(Q::Qtable, mesh::Matrix, start, goal)
    function draw_heatmap(ax)           # ヒートマップを描画
        heatmap = [maximum(Q[rc]) for rc in mesh]  # QテーブルからQ値の最大値を抽出
        heatmap!(ax, heatmap', colormap=:gnuplot)
        hlines!(ax, [r + 0.5 for r in axes(mesh,1)], color=:black, linewidth=0.5)
        vlines!(ax, [c + 0.5 for c in axes(mesh,2)], color=:black, linewidth=0.5)
    end
    fig = Figure(size=(400,400), backgroundcolor=:gray)
    ax = Axis(fig[1,1], aspect=1, spinewidth=1.5)
    ax.yreversed = true                 # デカルト座標系から画像座標系に変更
    hidedecorations!(ax)
    tightlimits!(ax)
    draw_heatmap(ax)                    # ヒートマップを描画
    draw_terminal(ax, start, goal)      # 終端を描画
    display(fig)
    fig
end

# 迷路と最適経路を可視化
function vis_maze_path(path::Vector, maze::Matrix, start, goal)
    function plot_path(ax)              # 最適経路をプロット
        path′ = [rc2xy(rc...) for rc in path]
        lines!(ax, path′, color=:red3, linewidth=2)
        scatter!(ax, path′, color=:orange, strokecolor=:red3, strokewidth=2, markersize=8)
    end
    function draw_maze(ax)              # 迷路を描画
        colormap = [:wheat, :darkolivegreen]
        heatmap!(ax, maze', colormap=colormap, colorrange=(0,1))
        hlines!(ax, [r + 0.5 for r in axes(maze,1)], color=:gray, linewidth=0.5)
        vlines!(ax, [c + 0.5 for c in axes(maze,2)], color=:gray, linewidth=0.5)
    end
    fig = Figure(size=(400,400), backgroundcolor=:gray)
    ax = Axis(fig[1,1], aspect=1, spinewidth=1.5)
    ax.yreversed = true                 # デカルト座標系から画像座標系に変更
    hidedecorations!(ax)
    tightlimits!(ax)
    draw_maze(ax)                       # 迷路を描画
    plot_path(ax)                       # 最適経路をプロット
    draw_terminal(ax, start, goal)      # 終端を描画
    display(fig)
    fig
end

 ハンズオンハンズオンは、初期設定，学習フェーズ，推論フェーズの 3つで構成されています。

 初期設定迷路の構造を変更したい場合はmaze行列の定義を変更します。また、ゴール地点を変更したい場合はgoalタプルの定義を変更します。
Julia
# 迷路を定義（0:通路, 1:壁）
maze = [
    0 0 0 0 0 0 0 0 0 0;
    1 1 0 1 1 1 1 1 0 0;
    0 0 0 0 0 0 1 0 0 0;
    0 1 1 1 0 0 1 0 1 0;
    0 1 0 0 0 1 1 0 1 0;
    0 1 0 1 0 0 0 0 1 1;
    0 0 0 1 1 1 1 0 0 0;
    0 1 0 0 0 0 1 1 1 0;
    0 1 1 1 1 0 0 0 0 0;
    0 0 0 0 0 0 1 1 0 0
]

Random.seed!(3407)
mesh = tuple.(axes(maze, 1), (axes(maze, 2))')             # 迷路の要素を指定するための格子点
actions = [(-1,0), (1,0), (0,-1), (0,1)]                   # 移動量を定義（上・下・左・右）
Q = Qtable(rc => zeros(length(actions)) for rc in mesh)    # Qテーブルを作成
p = Q_parameter()
goal = (10, 6)                                             # ゴール地点を設定

 学習フェーズ（迷路探索）学習フェーズでは探索範囲の網羅性を高める工夫をします。その方法として、ゴール地点 (10,6)を固定した状態で、2つの異なるスタート地点から探索を開始します（経験の再利用）。
Julia
starts = [ (start = (1,  1), fname = "13-heat-a.png"),     # 左上端から探索開始
           (start = (1, 10), fname = "13-heat-b.png") ]    # 右上端から探索開始
for s in starts
    agent!(Q, p, actions, maze, s.start, goal)             # 迷路探索
    fig = vis_heatmap_qtable(Q, mesh, s.start, goal)       # Q値をヒートマップで可視化
    save(s.fname, fig)    
end
1回目の学習ではスタート地点を左上端 (1,1)に設定します。その結果を図 2aのヒートマップで確認すると、右上付近の探索が手薄になっているのが分かります。


図 2a　Qテーブルのヒートマップ、スタート地点(1,1)
2回目の学習では 1回目で使用したQテーブルを再利用するとともに、スタート地点を右上端 (1,10)に変更します。その結果を図 2bのヒートマップで確認すると、1回目の学習結果が引き継がれて 2回目の学習結果も反映されており、迷路全体についての網羅性が高まっているのが分かります。


図 2b　Qテーブルのヒートマップ、スタート地点(1,10)
Qテーブルのヒートマップ（図 2a,b）を確認することで、ゴール地点の高い報酬が徐々にスタート地点の方向へと伝播し、迷路全体に「Q値の勾配」が形成されていることが分かります。

 推論フェーズ（経路検索）推論フェーズではQテーブルを参照して最適経路を検索します。スタート地点を 4箇所設定して、それぞれについてゴール地点までの最適経路を検索します。
Julia
starts = [ (start = (1,  7), fname = "13-maze-a.png"),
           (start = (5,  1), fname = "13-maze-b.png"),
           (start = (3,  6), fname = "13-maze-c.png"),
           (start = (5, 10), fname = "13-maze-d.png") ]
for s in starts
    path = search_path(Q, actions, maze, s.start, goal)    # 経路検索
    fig  = vis_maze_path(path, maze, s.start, goal)        # 迷路と最適経路を可視化
    save(s.fname, fig)
end
スタート地点が (1,7)の場合の最適経路：



図 3a　経路検索、スタート地点(1,7)
スタート地点が (5,1)の場合の最適経路：



図 3b　経路検索、スタート地点(5,1)
スタート地点が (3,6)の場合の最適経路：



図 3c　経路検索、スタート地点(3,6)
スタート地点が (5,10)の場合の最適経路：



図 3d　経路検索、スタート地点(5,10)
一度Qテーブルが適切に学習されれば、迷路内のどこにスタート地点を設定しても、再学習なしでゴールまでの最適経路を割り出せることを確認できました（図 3a~d）。これは、エージェントが単なる「手順」を記憶したのではなく、環境全体の「構造と価値」を把握したことを意味します。

 おわりにQテーブルの構造を理解したところで数式とのつながりが見えて、一気に全体の見通しが良くなりました。その流れで、Qテーブルをヒートマップ化したところ、学習中に何が起こっているのか把握できるようになり、結果的に推論性能の向上につながりました。また、Qテーブルを参照していくつかの最適経路を割り出してみましたが、不自然なところは見当たらないので目先の目標を達成できたと理解しました。

Math＆Julia #13｜強化学習 » Q学習 » 迷路探索

はじめに

Q学習による迷路探索

実行サンプル

基本要素

エージェント（agent）

環境（environment）

状態（state）： $\bold{s∈S}$

行動（action）： $\bold{a∈A}$

報酬（reward）： $\bold{r∈R}$

Q値（Q-value）： $\bold{Q(s,a)}$

方策（policy）： $\boldsymbol{π(s)}$

エピソード（episode）

ハイパーパラメータ

学習率： $\boldsymbol{α}\enspace(0<α≤1)$

割引率： $\boldsymbol{γ}\enspace(0≤γ<1)$

探索率： $\boldsymbol{ε}\enspace(0<ε≤1)$

ステップ数： $\textbf{maxsteps}$

エピソード数： $\textbf{episodes}$

Qテーブルの構造

学習フェーズ（迷路探索）

行動選択

報酬獲得

Q値更新

推論フェーズ（経路検索）

推論性能の向上

実装

核心部

可視化部

ハンズオン

初期設定

学習フェーズ（迷路探索）

推論フェーズ（経路検索）

おわりに

Discussion

状態 $s$	行動 (1) ⇧	行動 (2) ⇩	行動 (3) ⇦	行動 (4) ⇨
(4, 6)	–0.0439003	–0.0464883	–0.0364779	–0.0512670
(9, 3)	0.0	0.0	0.0	0.0
(5, 5)	–0.0236914	–0.0312670	0.1465530	–0.0230647
(7, 8)	0.2591130	0.2130950	0.2512060	0.3735140

はじめに

Q学習による迷路探索

実行サンプル

基本要素

エージェント（agent）

環境（environment）

状態（state）： \bold{s∈S}

行動（action）： \bold{a∈A}

報酬（reward）： \bold{r∈R}

Q値（Q-value）： \bold{Q(s,a)}

方策（policy）： \boldsymbol{π(s)}

エピソード（episode）

ハイパーパラメータ

学習率： \boldsymbol{α}\enspace(0<α≤1)

割引率： \boldsymbol{γ}\enspace(0≤γ<1)

探索率： \boldsymbol{ε}\enspace(0<ε≤1)

ステップ数： \textbf{maxsteps}

エピソード数： \textbf{episodes}

Qテーブルの構造

学習フェーズ（迷路探索）​

行動選択

報酬獲得

Q値更新

推論フェーズ（経路検索）

推論性能の向上

実装

核心部

可視化部

ハンズオン

初期設定

学習フェーズ（迷路探索）

推論フェーズ（経路検索）

おわりに

Discussion

状態（state）： $\bold{s∈S}$

行動（action）： $\bold{a∈A}$

報酬（reward）： $\bold{r∈R}$

Q値（Q-value）： $\bold{Q(s,a)}$

方策（policy）： $\boldsymbol{π(s)}$

学習率： $\boldsymbol{α}\enspace(0<α≤1)$

割引率： $\boldsymbol{γ}\enspace(0≤γ<1)$

探索率： $\boldsymbol{ε}\enspace(0<ε≤1)$

ステップ数： $\textbf{maxsteps}$

エピソード数： $\textbf{episodes}$

学習フェーズ（迷路探索）