はじめに

この記事は「imtakalab Advent Calendar 2025」の 24日目の記事です．
本日はクリスマスイブです．クリスマスイブといえば恋人と過ごすというのが通例化しており，多くの人が自分との相性などを見ることで将来のパートナーを探しているのではないでしょうか？そう，つまりクリスマスイブといえば探索ですよね！そこで今回は探索手法について，強化学習という分野以外にもあると最近思ったため，強化学習やゲーム，ロボットなど様々な「探索」について記事を書かせていただければと思います．

目次

• はじめに
• 探索とは？
• 強化学習の探索
• ロボットの探索
• 動物の探索
• ゲームの探索
• おわりに

探索とは？

強化学習の探索

強化学習では，エージェントが環境と相互作用しながら，報酬を最大化する行動方策を学習します．この過程で，探索と活用のバランスが重要になります．

• 探索: 未知の行動や状態を試すことで，より良い方策を見つける可能性を広げる
• 活用: 現在の知識に基づいて，既知の最適な行動を選択する

探索が不十分だと，局所最適解に陥ってしまいます．一方，探索しすぎると学習が遅くなります．

1. ε-greedy / Boltzmann探索

最も基本的な探索戦略です．

ε-greedy探索では，確率εでランダム行動を選択し，確率(1-ε)で最適とされる行動（貪欲行動）を選択します．学習が進むにつれてεを減衰させ，探索から活用へと移行します．

if np.random.random() < epsilon:
    action = env.action_space.sample()  # ランダム行動
else:
    action = argmax(Q_values)  # 貪欲行動

Boltzmann探索（ソフトマックス探索）では，温度パラメータτを用いて，Q値に基づいた確率分布から行動をサンプリングします．

action_probs = softmax(Q_values / temperature)
action = sample(action_probs)

2. Intrinsic Curiosity Module (ICM)

ICMは，**内発的好奇心（Intrinsic Curiosity）**に基づく探索手法です．エージェントは，予測誤差が大きい状態（新しい・予測困難な状態）に対して内在的報酬を与えることで，積極的に探索を促進します．

ICMは以下の2つのモデルで構成されます：

• Forward Model: 現在の状態と行動から，次の状態を予測
• Inverse Model: 現在の状態と次の状態から，取った行動を予測

予測誤差が大きいほど，その状態は「新しい」と判断され，探索ボーナスが与えられます．

# 予測誤差を計算
predicted_next_state = forward_model(state, action)
forward_error = ||predicted_next_state - actual_next_state||²

# 探索ボーナスとして報酬に追加
reward += curiosity_coef * forward_error

3. Random Network Distillation (RND)

RNDは，ランダムネットワークの蒸留に基づく探索手法です．

• ターゲットネットワーク: ランダムに初期化され，固定されたネットワーク
• 予測ネットワーク: ターゲットネットワークの出力を予測するように学習

新しい状態では，予測ネットワークがターゲットネットワークの出力を正確に予測できないため，予測誤差が大きくなります．この誤差を内在的報酬として使用します．

target_features = target_network(state)  # 固定
predicted_features = predictor_network(state)  # 学習
prediction_error = ||predicted_features - target_features||²

reward += rnd_coef * prediction_error

4. Count-based Exploration

Count-based探索は，状態の訪問回数に基づいて探索を促進します．訪問回数が少ない状態ほど大きな探索ボーナスを与えます．

visit_count[state] += 1
bonus = bonus_coef / sqrt(visit_count[state])
reward += bonus

この手法は，状態空間が離散的で，状態をハッシュ化できる環境（MiniGridなど）に適しています．

5. Hindsight Experience Replay (HER)

HERは，Goal-conditioned RLにおける探索手法です．目標達成に失敗したエピソードも，後から目標を再定義することで，成功した経験として再利用します．

例えば，ゴールAに向かって失敗したエピソードでも，実際に到達した地点Bを新しいゴールとして設定することで，「Bに到達する方法」を学習できます．

# 失敗したエピソードでも
for transition in failed_episode:
    # 実際に到達した地点を新しいゴールとして設定
    new_goal = transition['achieved_goal']
    # 経験を再利用
    replay_buffer.add(transition, goal=new_goal)

ロボットの探索

ロボットでも同じように探索というのが行われています．特にSLAMによる環境のmappingという面で探索が行われています．

SLAMとは？

**SLAM（Simultaneous Localization and Mapping）**は，ロボットが未知環境を移動しながら，同時に以下の2つの問題を解決する技術です：

1. Localization（自己位置推定）: ロボットが現在どこにいるかを推定する
2. Mapping（地図構築）: 環境の地図を構築する

SLAMは，ロボットが環境を探索する過程で，センサー（LiDAR，カメラなど）から得た情報を統合し，自己位置と環境の地図を同時に推定します．この過程で，ロボットは未知領域を探索し，既知領域の地図を拡張していきます．

マップを埋めるための探索

SLAMにおいて，効率的に環境の地図を構築するためには，未知領域を探索する戦略が重要です．単にランダムに移動するのではなく，戦略的に未知領域を探索することで，地図構築の効率が大幅に向上します．

Frontier exploration

**Frontier exploration（フロンティア探索）**は，効率的に環境を探索するための手法です．

この手法では，以下の手順で探索を行います：

1. 既知領域と未知領域の境界（フロンティア）を検出: 地図上で，既知の領域と未知の領域の境界を特定します
2. フロンティアを連結: 検出したフロンティアを連結して，探索すべき領域を決定します
3. 中心に向かって進む: 連結されたフロンティアの中心に向かってロボットを移動させます

この手法により，ロボットは未知領域を効率的に探索し，地図を埋めていくことができます．強化学習における探索と同様に，未知領域への探索と既知領域の活用のバランスが重要です．

動物の探索

動物の探索行動も，強化学習やロボティクスと同様の原理に基づいています．

レヴィーウォーク（Levy Walk）

レヴィーウォークは，多くの動物が採餌行動で使用する探索パターンです．これは，以下の特徴を持つランダムウォークです：

• 長距離移動と局所探索の組み合わせ: 短い距離を頻繁に移動し，時折長距離の移動を行う
• べき乗則に従う移動距離分布: 移動距離の分布がべき乗則に従う
• 効率的な探索: ランダムウォークよりも効率的に広い領域を探索できる

レヴィーウォークは，餌がまばらに分布している環境で特に効果的です．局所的に集中的に探索し，餌が見つからない場合は長距離移動して新しい領域を探索します．

この探索パターンは，強化学習におけるε-greedy探索やBoltzmann探索と類似しており，探索と活用のバランスを取った戦略と言えます．

ゲームの探索

ゲーム開発における探索は，バグ発見という重要な側面があります．

ゲームのバグ発見における探索

ゲームのテストでは，可能な限り多くのゲーム状態や行動パターンを探索し，バグや不具合を発見する必要があります．この過程は，強化学習の探索と非常に類似しています：

• 状態空間の探索: ゲームの様々な状態（レベル，アイテム，敵の配置など）を探索
• 行動空間の探索: プレイヤーが取る様々な行動（移動，攻撃，アイテム使用など）を探索
• エッジケースの発見: 通常のプレイでは発生しない，特殊な状況や組み合わせを探索

自動テストと探索

ゲームの自動テストでは，以下のような探索手法が使用されます：

• ランダム探索: ランダムに行動を選択してゲームをプレイし，バグを発見する
• カバレッジベース探索: 未探索のコードパスや状態遷移を優先的に探索する
• 強化学習ベース探索: 強化学習エージェントがゲームを探索し，異常な状態や報酬を発見する

これらの手法により，人間のテスターでは発見困難なバグや，特定の条件でのみ発生するバグを効率的に発見できます．

おわりに

本記事では，様々な分野における「探索」について紹介しました．

• 強化学習: エージェントが環境を探索し，最適な方策を学習
• ロボティクス: 未知環境をマッピングし，経路を探索
• 動物行動: 生存のための探索戦略
• ゲームAI: ゲーム木を探索し，最適な手を選択

特に強化学習の探索戦略については，各手法の特徴と適用場面を理解できました．言い訳として，Stable Baseline3をminigrid環境で動かしたけどなんか学習がうまくいかなかった．

探索は，未知の可能性を発見するための重要なプロセスです．クリスマスイブに新しい出会いを探すように，AIも未知の状態や行動を探索することで，より良い方策を見つけることができます．