Open Source Robotics

高品質なオープンソースロボティクスプロジェクト、ツール、ソフトウェアの厳選コレクション。

Monte Carlo Tree Search

  • 別名: MCTS
  • カテゴリ: Planning & manipulation › Task-level
  • タグ: planning, tree-search, decision-making, pomdp, sampling-based

モデルから多数の軌道をシミュレーションして探索木を成長させ、その収益を使って最も有望な行動を選ぶオンライン計画アルゴリズム。

定義

モンテカルロ木探索(Monte Carlo tree search、MCTS)は、シミュレーションによる経験から探索木を少しずつ構築し、次に何をするかを決める計画アルゴリズムの一群である。各反復は 4 つのステップから成る。選択(selection)では現在の状態から木をたどって下り、推定価値の高い行動と数回しか試していない行動のバランスをとる規則で子ノードを選ぶ。展開(expansion)では 1 つ以上の新しいノードを追加する。シミュレーション(simulation、またはロールアウト)では新しいノードの価値を推定する。古典的にはランダムまたは単純なデフォルト方策をエピソードの終わりまで実行する。バックプロパゲーション(backpropagation)では経路上のすべてのノードの訪問回数と価値推定を更新する。時間または反復の予算が尽きると、アルゴリズムは最も多く訪問された、または価値が最も高いルートの行動を採用し、次の状態から同じことを繰り返す。この用語は 2006 年に Rémi Coulom によって導入され、同じ年に Kocsis と Szepesvári が UCT(Upper Confidence bounds applied to Trees)を発表した。UCT は選択に UCB1 バンディット規則を用いる、最も広く使われている変種である。

MCTS に必要なのは生成モデル、すなわち状態と行動を与えるとサンプリングされた次の状態と報酬を返すシミュレータだけである。明示的な遷移行列も、微分可能なモデルも、手書きのヒューリスティックも必要としない。また、MCTS はエニタイムアルゴリズムであり、計算を増やすほど良い決定が得られ、答えが必要になった時点でいつでも探索を止められる。適切な条件のもとでは、シミュレーション回数が増えるにつれて UCT は最適な行動に収束するが、実際には決定の質は予算、ロールアウト方策、そして探索の誘導の仕方に大きく依存する。AlphaGo と AlphaZero は、ランダムなロールアウトを学習した価値推定に置き換え、学習した方策で選択にバイアスをかけると、探索がはるかに効率的になることを示した。

ロボティクスでは、MCTS は結果が不確かな、ある時間幅にわたる決定に使われる。POMCP とその変種 POUCT は、行動と観測の履歴の上で探索することで UCT を部分観測問題に拡張したものであり、物体探索、能動知覚、情報収集を POMDP として定式化した問題の一般的なソルバーとなっている。連続な状態と行動には追加の工夫が必要である。プログレッシブワイドニング(progressive widening)は、ノードの訪問回数が増えるにつれてのみ新しい子行動やサンプリングした観測を追加する。多くのロボットシステムでは代わりに、離散的なマクロ行動や動作プリミティブの集合の上で探索し、連続的な動作は下位のプランナーに任せる。

重要な理由

次にどこを見るか、どの物体を先に動かすかといったロボットの多くの決定は、結果が数ステップ後にしか現れず、不確かな観測に左右される。MCTS はシミュレータだけでそのような時間幅にわたって計画する実用的な方法を提供し、MDP や POMDP 全体をオフラインで解くことが手に負えない問題にもスケールする。

主な用途

  • POMDP として定式化した物体探索と能動知覚
  • タスク・アンド・モーション・プランニングにおける記号的行動の順序の選択
  • 交差点や合流での自動運転の意思決定
  • マルチロボットの協調と探索
  • AlphaZero 型システムのような、学習したモデルを用いた計画

実際の使われ方

モバイルマニピュレータが、散らかった部屋でいくつかの物体を見つけなければならない。チームはこのタスクを POMDP としてモデル化する。物体の位置に対する信念、観察視点へ移動するためのマクロ行動と検出行動、そしてカメラの観測モデルを用意する。各決定で、POUCT は固定の時間予算内に現在の信念から数千回のシミュレーションを実行し、生成モデルを使って物体の位置と検出結果をサンプリングする。ロボットは価値が最も高いルートの行動を実行し、実際の検出結果で信念を更新して、再び計画する。エンジニアは探索定数、ロールアウト方策、探索ホライズンを調整し、予算内で木が深く成長できるようにマクロ行動の集合を十分に小さく保つ。

よくある誤解

  • MCTS は学習アルゴリズムである — MCTS はモデルまたはシミュレータを必要とする計画手法である。学習した価値ネットワークや方策ネットワークと組み合わされることが多いが、探索そのものは方策を学習しない
  • MCTS にはエピソードの終わりまでのランダムなロールアウトが必要である — ロールアウトの代わりに、ヒューリスティックな方策、打ち切った時間幅、または学習した価値関数を使える
  • MCTS は連続な行動にそのまま使える — 標準的な UCT は有限の行動集合を前提とするため、連続な問題にはプログレッシブワイドニング、サンプリング、または離散的なマクロ行動の集合が必要である
  • MCTS は最適な行動を見つける — シミュレーション回数が増えるにつれて最適な行動に近づくだけであり、リアルタイムの予算では結果は近似的で、探索の誘導の仕方に依存する

知っておくべき人

  • 計画・意思決定のエンジニア
  • POMDP と能動知覚に取り組む研究者
  • タスク・アンド・モーション・プランニングの開発者
  • 探索と学習を組み合わせる強化学習の実務者

関連技術

  • UCT
  • POMCP
  • AlphaZero
  • プログレッシブワイドニング(Progressive Widening)
  • 上側信頼限界(Upper Confidence Bound、UCB1)

関連用語

  • Markov Decision Process (MDP)
  • Partially Observable Markov Decision Process (POMDP)
  • Belief-Space Planning
  • Task and Motion Planning
  • Robotic information gathering
  • Reinforcement Learning

関連プロジェクト

  • BehaviorTree.CPP: C++ behavior tree library for robot task planning, powering Nav2 and ROS 2 systems
  • OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications

動画

  • Monte Carlo Tree Search: John Levine
  • AI 101: Monte Carlo Tree Search: AI and Games

このウェブサイトにはJavaScriptが必要です。オープンソースロボティクスプロジェクトを閲覧するにはJavaScriptを有効にしてください。