/w=3840,quality=90,fit=scale-down)
※本記事は、スタンフォード大学のシドニー・カッツ氏（Sydney Katz）による講義「Stanford AA228V I Validation of Safety Critical Systems I Falsification through Planning」の内容を基に作成されています。講義の詳細情報は https://aa228v.stanford.edu/ でご覧いただけます。また、参考テキストは https://algorithmsbook.com/validation/ からアクセスできます。
シドニー・カッツ氏はスタンフォード大学のポスドク研究員で、詳細なプロフィールは https://sydneymkatz.com/ でご覧いただけます。
本講義に関する詳細情報や受講登録については、https://online.stanford.edu/courses/a... をご参照ください。本記事では講義内容を要約しております。なお、正確な情報や文脈については、オリジナルの講義をご視聴いただくことをお勧めいたします。
1. 前回の復習：最適化による失敗探索
1.1 最適化問題の設定
Sydney Katz：前回の講義で話した内容から始めましょう。前回は最適化を使って失敗を見つける方法について説明しました。そこでは、変数として初期状態と一連の外乱を決定する最適化問題を設定しました。目的関数として「失敗への近さ」を表す何かを最小化し、軌道τがその初期状態と外乱の列によるロールアウトであるという制約条件を満たすようにしました。
目的関数については、第3章で学んだ「堅牢性（robustness）」がまさに私たちが欲しかったもの、つまり「失敗への近さ」を表現できるということを思い出しました。勾配を必要とする最適化アルゴリズムを使用する場合は、滑らかな堅牢性（smooth robustness）を使うことになります。そこで私たちは堅牢性を目的関数として使うことにしたのですが、講義の最後の方で、それが問題を引き起こす可能性があることを議論していました。というのも、非常に起こりにくい軌道を生み出してしまう可能性があるからです。
単に堅牢性を最小化するよう指示すると、アルゴリズムは堅牢性をできるだけ小さくするためにどんなことでもしようとします。しかしその過程で、非常に起こりにくいことをしてしまう可能性があります。例えば、外乱分布からサンプリングするこの軌道を見てみましょう。この外乱は分布によると非常に確率が低く、とても起こりにくいものです。そのようなことを多数行えば、倒立振子を倒すことは可能で、軌道を失敗させることはできます。しかし、これは非常に起こりにくく、私たちが必ずしも興味を持っているタイプの失敗ではないかもしれません。
そこで前回言ったように、解決策としては目的関数に尤度（likelihood）を組み込むことです。そのためには、軌道の尤度をどのように評価するかを知る必要があります。ここから再開していきましょう。
1.2 目的関数の問題点
Sydney Katz：前回の講義で議論したように、単純に堅牢性を最小化する目的関数には重大な問題があります。アルゴリズムが堅牢性をできるだけ小さくするために何でもしようとすると、非常に起こりにくい軌道を生成してしまう可能性があるのです。
例として倒立振子の例を見てみましょう。外乱分布からサンプリングしたこの軌道を考えると、ここにある外乱は分布上で確率が非常に低いことがわかります。しかし、このような低確率の外乱を複数回加えることで、実際に振子を倒すことはできます。つまり軌道を失敗させることは可能なのです。
しかし、このような失敗は現実世界ではほとんど起こり得ないものであり、私たちが本当に関心を持つべき種類の失敗シナリオではないかもしれません。システムの安全性を適切に評価するためには、合理的に発生し得る失敗シナリオを見つける必要があります。
そのため、私たちは単に「失敗する軌道」を見つけるだけでなく、「起こりやすい失敗軌道」を見つけることが重要です。このようなシナリオこそが、実世界の安全性評価において真に価値があります。前回の講義の終わりで述べたように、この問題に対する解決策は、目的関数に軌道の尤度（likelihood）を組み込むことです。
1.3 尤度を目的関数に組み込む
Sydney Katz：目的関数に尤度を組み込むには、まず軌道の尤度をどのように評価するかを理解する必要があります。軌道の尤度は、サンプリングした初期状態の尤度と、その後にサンプリングしたすべての外乱の尤度の積として表せます。
具体的に見ていきましょう。これまで何度も見てきた同じ軌道を例にとり、サンプリングしたものとその発生尤度を追跡します。p(τ)で軌道τの確率を表すと、これはまずサンプリングした初期状態の確率密度になります。そして次のステップでは、最初の時間ステップの外乱をサンプリングします。この外乱の確率密度も掛け合わせていきます。このプロセスを続け、次の状態に移り、次の外乱をサンプリングし、その尤度も積に加えていきます。これを軌道の最終深さまで繰り返し、最後にサンプリングした外乱までを含めます。
つまり、軌道の尤度はこれらすべての要素の積になります。コードで表すと、各時間ステップにおける状態、行動、観測が与えられた場合の外乱のそれぞれの積になります。これをさらに細かく分解すると、エージェントの外乱、環境の外乱、センサーの外乱の3つに分けられ、これらを掛け合わせます。
教科書のコードでは、対数PDF（確率密度関数）を実装しています。これは単に上記の積の対数をとったものです。小さな数値を多数掛け合わせると非常に小さな数値になり、数値的な安定性の問題が生じる可能性があるため、対数を使用しています。対数を使えば、掛け算の代わりに足し算ができるようになります。
このlog_pdfという関数では、最終的にはexpを取って確率密度を返していますが、基本的には対数を扱っています。初期状態の対数確率を計算し、各時間ステップで発生した外乱の対数PDFを加算していくのです。
これで軌道の尤度を計算する方法がわかりました。これを目的関数に組み込むことで、起こりやすい失敗を見つけられるようになります。
1.4 目的関数設計の考慮点
Sydney Katz：新しい目的関数を設計する際には、いくつかの重要な点を考慮する必要があります。ここでは2つの場合に分けて考えます。最初のケースは軌道が失敗している場合です。数学的には「τ∉Ψ」と表記します。これは「軌道τが仕様Ψを満たさない」、つまり軌道が失敗していることを意味します。
この場合、目的関数は軌道の負の尤度を返します。これにより、失敗軌道を見つけた場合、その尤度を最大化するよう促します。言い換えれば、負の尤度を最小化することで、最も起こりやすい失敗を見つけようとするのです。
二つ目のケースは、軌道が失敗していない場合です。この場合、まだ尤度は気にせず、軌道を失敗に近づけることだけを考えます。つまり、軌道が失敗でない場合は、引き続き堅牢性を最小化します。
理論的には、この目的関数のグローバル最小値が最も起こりやすい失敗に対応するという素晴らしい性質があります。しかし、最適化アルゴリズムが常にグローバル最小値を見つけられるとは限らないため、実際にはいくつか課題があります。
まず、失敗軌道の目的関数値が成功軌道の値よりも常に低くなければなりません。そうでないと、アルゴリズムが失敗を見つけることを奨励しない可能性があります。成功よりも良い失敗が見つかるかもしれないのです。
これは一見問題なさそうに見えます。成功軌道では堅牢性が0より大きいので正の値を返し、失敗軌道では負の尤度を返すので常に負の値になるからです。しかし、実際には数値的な安定性の問題があります。軌道の確率p(τ)は多くの小さな数値の積であり、非常に小さな値になる可能性があります。これは最適化アルゴリズムにとって数値的に不安定になる可能性があります。
対数を取って数値的安定性を改善することも考えられますが、今度は対数尤度が0より小さくなる可能性があり、その負の値が0より大きくなる可能性があります。これにより、最初の要件が破られてしまいます。
これらの理由から、理論的には理想的な目的関数でも、実際には別の目的関数の方がうまく機能することがあります。実践的には、2つのケースを1つにまとめ、堅牢性と負の対数尤度のトレードオフを取る方法がよく使われます。例えば、堅牢性、対数尤度、そしてこの2つの重み付けを行うλというパラメータを使います。このパラメータは調整が必要で、最適化の結果を見て、失敗が見つかっていないならλを調整するといった対応が必要になるでしょう。
1.5 最適化アルゴリズムの概要
Sydney Katz：目的関数を定義した後は、最適化を行う必要があります。教科書で提供しているアルゴリズムは非常にシンプルに見えますが、これは多くの詳細を抽象化しているからです。基本的に何が起きているかというと、何らかの目的関数（堅牢性や尤度の目的関数など）を指定し、最適化器を与えます。この最適化器の部分は大きく省略されていますが、これは問題を最適化問題として定式化したことで、既に実装された様々なアルゴリズムを使用できるからです。
例えば、Juliaでは「optim.jl」や「JMP」などの最適化パッケージがあり、これらを使って最適化を行うことができます。しかし、この「最適化器」という黒い箱について少し詳しく説明しておきましょう。モデル構築の講義でも少し触れましたが、基本的に最適化器は目的関数とパラメータを入力とし、最適解を出力します。今回のケースでは、パラメータは初期状態と一連の外乱であり、最適化器はこれらを選択します。
最適化手法には大きく分けて2つのカテゴリがあります。1つ目は局所降下法（local descent methods）です。これらの手法は、ある初期推定値から始めて、徐々に最小値に向かって移動します。例えば倒立振子の場合、初期推定値は完全な軌道であり、これを少しずつ最小値に向けて移動させます。
局所降下法の一般的な問題は、初期推定値に結果が依存することです。この図を見ると、目指しているのはこのグローバル最小値ですが、もしこちら側から降下を始めると、このローカル最小値に捕まってしまう可能性があります。つまり、常にグローバル最小値が保証されるわけではありません。
この問題を改善する一つの方法は、1つのサンプルだけでなく、サンプルの集団（population）を維持し、それらを様々な最小値に向けて移動させることです。これにより入力空間のより多くの部分をカバーできます。
局所降下法の中にも、一次メソッドと二次メソッドがあります。これらについて詳しく知る必要はありませんが、いくつか名前だけ挙げておきます。勾配降下法は機械学習モデルのトレーニングでよく使われるもので、同様にAdamやLBFGS（一般的な二次メソッド）などがあります。重要なのは、これらの手法は勾配を必要とするということです。つまり、目的関数の勾配を入力に関して計算する必要があります。例えば堅牢性や尤度の目的関数を、入力に関して微分する必要があるのです。
これは完全なロールアウト関数を通じて微分する必要があることを意味し、モデルのダイナミクスを完全に理解している必要があります。つまり、2回目の講義で話したようなブラックボックスモデルでは、この方法は現実的ではありません。数学的な詳細がわからないため、勾配を計算できないからです。ただし、もし可能であれば、これらの手法は非常に強力です。何百万ものパラメータを持つ機械学習モデルを訓練できるほどです。
もし勾配が計算できなくても、まだゼロ次メソッド（zero order methods）または直接メソッド（direct methods）と呼ばれるものが使えます。これらは関数評価だけに基づいて降下を行います。つまり、入力を与えて目的関数値を得ることができれば十分です。間で何が起きているかを知る必要はありません。Hooke-JeevesやNelder-Meadなどがこの直接メソッドの例です。これらの素晴らしい点は、ブラックボックスシステムでも機能することです。
例えば、大規模で複雑なシミュレータがあり、その仕組みがわからなくても、初期状態と外乱を与えて軌道を得られれば、目的関数を評価できます。そうすれば、これらの手法を使ってシステムの失敗を見つけることができるのです。
具体例を見てみましょう。これは勾配降下法の例で、各点は外乱を表しています。初期化では、初期状態を0とし、すべての外乱も0としているため、振子は完全に垂直のままです。ステップを踏むと、これらの外乱をわずかに変化させて、軌道を失敗に向けて移動させます。さらにステップを進めると、徐々に外乱を調整して、最終的に振子を倒すことができます。
これに対して集団法では、異なる軌道のサンプル全体を維持します。ステップごとに、すべてのサンプルを更新して失敗に向けて移動させます。時間が経つと、システムの複数の失敗を見つけることができます。集団法の興味深い点は、局所降下法の勾配降下では軌道を片側だけに傾けた1つの失敗モードしか見つけられませんでしたが、集団法では母集団が様々な最小値に広がることを促すため、倒立振子の両方の失敗モードを見つけることができるのです。
これは最適化という広大な分野のごく簡単な概要です。この講義ではこれで十分ですが、これらの手法の間のトレードオフを理解し、既製のツールを使って誤動作探索を行えるようになることが目標です。特にブラックボックスか勾配が必要かという違いを理解することが重要です。最適化は非常に興味深く有用な分野なので、まだ受講していない方は、次学期にMichaelが教える最適化のクラスを取ることをお勧めします。
2. 計画を通じた誤動作探索
2.1 逐次的アプローチの利点
Sydney Katz：この講義では誤動作探索について引き続き話しますが、少し違った視点から取り上げます。前回は最適化を使用し、外乱などを設定して誤動作を探索しましたが、今回は計画を通じた誤動作探索について説明します。
この話題を小さな実話から始めたいと思います。私たちはなぜ定期的に作業を保存するのでしょうか？これは修辞的な質問ですが、皆さんはおそらくこの話の行方を想像できるでしょう。つい最近の休暇中、私と夫は家族を訪ねていました。夫は休暇の日数があまり多くなかったので、旅行中もリモートで仕事をしていました。ある日、私たちは父の台所でリモート作業をしていて、仕事を終えて父と夕食に出かける準備をしていました。
突然、夫の側から騒ぎが聞こえてきました。見ると、彼は「コンピュータがクラッシュして全てを失った！もう夕食には行けない！」と言っていました。私は「コンピュータを再起動してみよう。最後に保存したのはいつ？」と聞きました。彼の返事は？「3時間前」でした。
普段は親切で思いやりのある妻だと思っていますが、その瞬間、何かが私を襲い、「3時間も保存してないの？それはあなたの責任よ」と言ってしまいました。もちろん、これは3時間の作業を失った人に言うべきことではありませんでした。すぐに優しい妻の役割に戻り、「大丈夫よ、解決できるわ。夕食の後でやればいいじゃない。全部やり直せるから心配しないで」と言いました。
でも、これは考えさせられます。なぜ私たちは定期的に作業を保存するのでしょうか？私は5秒ごとにCtrl+Sを押しているようなタイプですが、夫の3時間間隔とは大きく異なります。定期的に保存するのは、最初と最後だけでなく、何か問題が起きた場合（例えば方向性が気に入らなくなったり、コンピュータがクラッシュしたりした場合）に以前の状態に戻れるようにするためです。
この講義の考え方は、一度にすべてを構築するよりも、何かを段階的に構築する方が簡単な場合があるということです。これが計画アルゴリズムで話すことの基本的な考え方です。
前回の講義を思い出すと、初期状態と軌道内の各時間ステップでの外乱の全空間にわたって最小化する最適化問題を設定しました。この最適化問題は、τ＝ロールアウトという形で書き換えることもできます。このような最適化問題は、すでに何度か述べたように、非常に高次元の空間で探索することを通常伴います。
例えば、倒立振子の場合、初期状態は2次元で、各外乱も2次元ですが、各時間ステップに1つずつあります。この外乱の列は2×D次元になります。例えば深さ21（以前見ていた41よりも小さい）の場合、探索空間は44次元になります。これはすでにかなり大きく、しかもこれはそれほど大きな問題ではありません。より大きな状態や外乱を持つ大きな問題では、数百次元を探索しなければならない可能性があります。
これは一度に行うにはかなり多くの次元です。計画アルゴリズムが私たちに提供するのは、この軌道を代わりに反復的に構築する能力です。
2.2 ツリー探索の基本概念
Sydney Katz：今日の講義の計画として、かなりの部分をツリー探索と呼ばれる手法のカテゴリについて話します。個人的に、私たちが作成した教科書の素晴らしい貢献の一つは、様々な種類のツリー探索を2つのステップに統一したフレームワークだと思います。このフレームワークについて説明し、その後、いくつかの具体的な実装について話します。ヒューリスティック探索、モンテカルロツリー探索、強化学習について少し触れ、これらの手法を使用する場合のシミュレータの要件についても説明します。
まずはツリー探索から始めましょう。こちらはそのグルーブを探すツリーです（笑）。これはMichael（Kochenderfer教授）が、スタンフォードのツリーマスコットとして夢を叶えた様子です。
しかし、今日の講義で話すのはそのようなツリーではなく、こちらのタイプのツリーです。
この講義で見ていくツリーの構造では、ツリーの各ノードはシステムの状態を表します。そして、各遷移または各エッジはノード間の遷移を表します。この状態からこの状態に移るには、この外乱があり、それが観測O、行動A、そして最終的には次の状態Sをもたらしました。
この講義で多く使用する例は、「連続世界（continuum world）」と呼ぶものです。これは教科書の後半にあります。基本的な考え方は、グリッドワールド問題の連続バージョンです。このエージェントは空間内を移動でき、障害物を避けながらこのゴールに到達する必要があります。
グリッドワールドと同様に、上下左右の行動をとることができ、それぞれの方向に1単位移動します。しかし、グリッドワールドと同様に滑りやすいのです。ただし、今回は正確に4つの方向のいずれかに滑るのではなく、例えば「上に移動する」と言っても、ちょうど上ではなく、上に近いが少し角度のある方向に滑る可能性があります。この場合の外乱は、滑る原因と滑る量を表します。
この連続世界のツリーを見てみましょう。ツリーの各ノードは異なる状態を表しています。ここでは、ノードが実際にある場所を示しています。このノードは連続世界内のこの正確な位置を表しています。エッジは状態間の可能な遷移です。例えば、ルートノードでは、ある外乱はこの状態に、別の外乱は別の状態に導くでしょう。
2.3 ツリー探索のフレームワーク
Sydney Katz：具体的な問題を見たので、典型的なツリー探索アルゴリズムの反復がどのように見えるかについて話しましょう。私たちは現在維持しているツリーがあります。最初に行うのは、焦点を当てたいノードを選択することです。例えば、このノードを選択します。後ほどこれをどのように選択するかについて説明しますが、これが最初のステップです。
ノードを選択したら、「拡張（Extend）」と呼ばれるステップを行います。ここで起きることは、新しい外乱をサンプリングし、それが新しい観測・行動をもたらし、異なる状態に導きます。
要約すると、ツリー探索アルゴリズムには基本的に2つのステップがあります。1つは「選択（Select）」ステップで、現在ツリーにあるノードの中から拡張するノードを選びます。もう1つは「拡張（Extend）」ステップで、実際にそのノードを拡張します。これらがどのように機能するかについてはまだ説明していませんが、これら2つのステップだけで、話す予定のさまざまなタイプのツリー探索を統一できる一般的なツリー探索アルゴリズムを作成できます。
このアルゴリズムでは、何らかの方法でツリーを初期化します。そして、アルゴリズムの各ステップで、ノードを選択し、それを拡張します。これから話すすべてのアルゴリズムは、この選択と拡張のステップをどのように実装するかという点でのみ異なります。どのノードを選択するか、そしてそれを拡張するためにどの外乱を選択するかをどのように決定するかです。
質問がありましたね。ここでのS（状態）は何かという質問ですが、これらの各Sは異なる可能な状態です。ルートノードは初期状態であり、これらの他のすべてのSはそこから到達できる状態です。例えば、ここ、ここ、ここの深さは3になります。
これがツリー探索の基本です。次に、これらの選択と拡張のステップを実装するさまざまな方法について説明します。
2.4 連続世界の例
Sydney Katz：先ほど少し触れた連続世界の例について、もう少し詳しく説明しましょう。これは本質的にグリッドワールドの連続バージョンと考えることができます。この世界では、エージェントは2次元の連続空間内を移動します。エージェントの目標は、赤い障害物を避けながら緑のゴール領域に到達することです。
グリッドワールドと同様に、エージェントは上下左右の4方向に移動することができ、それぞれの方向に1単位移動します。しかし、この世界は「滑りやすい」という特性があります。グリッドワールドでは滑るとき正確に4つの基本方向（上下左右）のいずれかに滑りますが、連続世界ではより現実的です。例えば、エージェントが「上に移動する」と決めても、完全に上方向ではなく、少し角度のある方向に滑る可能性があります。
この連続世界での「外乱」は、エージェントが意図した方向からどれだけ、どの方向に滑るかを表します。例えば、エージェントが上に移動しようとすると、外乱は上方向からの偏差を表します。大きな外乱は大きな滑りを意味し、小さな外乱は意図した方向に近い移動を意味します。
この連続世界のツリーを見ると、各ノードは空間内の特定の位置を表しています。ツリーの視覚化では、ノードの位置は実際の空間内の位置に対応しています。ツリーのエッジは、ある状態から別の状態への可能な遷移を表します。例えば、ルートノード（初期位置）から始めると、ある外乱によってこの位置に移動し、別の外乱によって別の位置に移動する可能性があります。
ツリー探索アルゴリズムを実行すると、このツリーは徐々に成長し、空間内のより多くの部分を探索していきます。アルゴリズムの反復ごとに、既存のノードの一つを選択し（選択ステップ）、そこから新しい外乱をサンプリングして新しいノードを追加します（拡張ステップ）。
この連続世界の例は、これから説明する様々なツリー探索アルゴリズムの動作を視覚的に理解するのに役立ちます。特に、どのようにして効率的に空間を探索し、失敗（この場合は障害物への衝突）を見つけるか、そしてどのようにして最も起こりやすい失敗経路を特定するかを示すのに適しています。
3. ヒューリスティック探索
3.1 RRT (Rapidly-exploring Random Trees)
Sydney Katz：最初に説明するのはヒューリスティック探索です。ヒューリスティック探索は、その名の通り、可能な軌道の空間を探索するためにヒューリスティック（発見的手法）を使用します。この手法は「急速探索ランダムツリー（Rapidly-exploring Random Trees）」、略してRRTとも呼ばれています。
RRTがどのように機能するかを説明するには、前述の2つのステップ（選択と拡張）をどのように実装するかを見ていく必要があります。選択ステップから始めましょう。
まず最初に、目標状態をサンプリングします。状態空間からランダムに状態をサンプリングするだけです。これが目指すべき目標となります。次に、現在のツリー内の各ノードに対して、ある種の目的関数を計算します。ツリー内のそれぞれの状態に対して、目標状態に基づいた目的関数を計算します。まだこの目的関数が何かは説明していませんが、目標状態に基づいて計算します。そして、最も低い目的関数値を持つノードを選択します。
ノードを選択したら、それを拡張したいノードとします。拡張するために、外乱を選択し、選択したノードからその選択した外乱を使ってステップを踏み、その結果をツリーに追加します。このプロセスを繰り返してツリーを構築していきます。
具体例を見てみましょう。連続世界を使って、選択ステップから始めます。これが現在持っているツリーだとします。最初に行うのは目標状態をサンプリングすることです。RRTの最もシンプルなバージョンでは、状態空間全体からランダムな状態をサンプリングし、それを目標状態とします。ここに目標状態があります（黄色い星）。
次に、目標状態に基づいて、ツリー内の各ノードに対して目的関数を計算します。ここで使用できる非常にシンプルな目的関数の一つは、目標までの距離です。この目標を見て、ツリー内の各ノードまでの距離を計算します。そして、最も低い目的関数値を持つノード、つまりこの目標状態に最も近いノードを選択します。これが拡張するために選択したノードです。
ここで拡張ステップに移ります。非常にシンプルな方法は、ランダムな外乱をサンプリングすることです。このノードでは、エージェントは上に行きたいと思っています。外乱は、この上への行動に対して何らかの滑りを表します。ランダムな外乱をサンプリングするだけなので、少し右に滑らせます。その外乱に従ってステップを踏み、その結果をツリーに追加します。
そして、また最初からやり直します。質問がありますか？
実は、ここで行っていることは少し奇妙かもしれません。なぜなら、ただ空間内のどこかからランダムに目標状態をサンプリングしているだけだからです。最低目的関数を選ぶのは、その目標状態に近づこうとしているからです。サンプリングした目標状態（どこでもいい）に近づけるような目的関数を選んでいるのです。最低目的関数は単にこの目標状態に近いということを意味します。
他にも質問があるようですね。これを見ると、拡張したノードだけを見ているように見えるかもしれませんが、実際にはそうではありません。目標状態に最も近いノードだけを拡張しているように見えるかもしれませんが、目標状態はランダムにサンプリングされるのです。例えば、もし目標状態がこの位置（根本に近い場所）だったとしたら、ルートノードを拡張することになるでしょう。サンプリングした目標状態がどこにあるかによって、どのノードでも拡張する可能性があるのです。
また、拡張ステップで新しいノードが追加されると、次の反復ではそのノードも考慮されます。新しいツリーを基に、また目標状態をサンプリングし、全てのノード（新しく追加されたものも含む）から最も近いものを選びます。
3.2 選択ステップと拡張ステップ
Sydney Katz：ヒューリスティック探索の2つの基本ステップについてより詳しく見ていきましょう。まず選択ステップから始めます。前述したように、RRTの選択ステップでは3つの主要なタスクを実行します：
- 目標状態のサンプリング：最も基本的なRRTでは、単純に状態空間全体からランダムにサンプリングします。これは空間を効率的に探索するための単純な方法です。
- 各ノードの目的関数の計算：サンプリングした目標状態に基づいて、ツリー内の各ノードに対して目的関数を計算します。最も単純な場合、この目的関数はノードから目標状態までのユークリッド距離です。
- 最低目的関数値を持つノードの選択：計算した目的関数値に基づいて、最も値が低いノード（目標に最も近いノード）を選択します。
この選択ステップの目的は、ツリーをどの方向に拡張するかを決定することです。ランダムな目標状態をサンプリングすることで、アルゴリズムは空間の様々な部分を探索するよう導かれます。
次に拡張ステップです。選択したノードを拡張するために：
- 外乱の選択：基本的なRRTでは、単にランダムな外乱をサンプリングします。連続世界の例では、エージェントが取りたい行動（例えば上方向への移動）に対して、何らかの滑りをランダムにサンプリングします。
- ステップの実行：選択した外乱を使って、選択したノードから一歩進みます。これにより新しい状態に到達します。
- 結果の追加：この新しい状態をツリーに新しいノードとして追加し、選択したノードから新しいノードへのエッジも追加します。
これらのステップを繰り返すことで、ツリーは徐々に成長し、状態空間の探索が進みます。各反復で、ツリーは新しい状態に拡張され、それが次の反復での選択候補となります。
アルゴリズムの動作を視覚化すると、各反復でサンプリングされる目標状態が変わるため、ツリーは様々な方向に成長します。空間内の異なる場所から目標状態がサンプリングされるたびに、ツリー内の異なるノードが選択され、異なる方向に拡張されます。これにより、ツリーは空間全体に広がっていきます。
ただし、ノートとして付け加えると、この基本的なRRTの実装では、拡張ステップでは完全にランダムな外乱を使用しているため、目標に向かって効率的に移動することが保証されているわけではありません。これについては後ほど改善策を説明します。
3.3 アルゴリズム改善手法
Sydney Katz：基本的なRRTアルゴリズムを実装して実行すると、アルゴリズムは各反復で様々な目標状態をサンプリングし、ツリーを異なる方向に拡張していきます。約100回の反復後、アルゴリズムはこのように空間をかなり探索していることがわかります。
興味深い観察として、なぜ赤い障害物に当たらず、常に緑のゴールに向かう傾向があるのかという質問が出るかもしれません。これは完全にランダムではなく見えるかもしれませんが、実際には外乱をサンプリングする際に名目上の外乱分布からサンプリングしているからです。つまり、ここで上に行きたい場合、実際に上方向に導く外乱が得られる可能性が高いのです。そのため、これらのランダムにサンプリングされた外乱によって、システムが通常進むと予想される方向にツリーが成長する傾向があります。
しかし、空間を探索することはできましたが、失敗（障害物への衝突）を見つけることはできませんでした。ただ空間をできるだけ多く探索し、失敗が見つかることを期待していましたが、見つかりませんでした。もう少し長く実行して失敗を見つけることを期待することもできますが、もう少しスマートな方法があるはずです。
アルゴリズムにいくつかの改善を加えてみましょう。1つ目の改善策はすでに言及しました。選択ステップでは、これまで各反復で状態空間全体からランダムに目標をサンプリングしていたため、どこでも目標を得る可能性がありました。しかし、私たちの目標は失敗を見つけることです。なので、なぜ毎回失敗領域から目標状態をサンプリングしないのでしょうか？
そういうわけで、空間全体からではなく、常に失敗領域（この場合は障害物）から目標状態をサンプリングするという改善策を導入します。なぜこれを最初からしなかったのかというと、すべてのシステムが簡単に識別できる失敗領域を持っているわけではないからです。この連続世界は、これらの概念を示すには非常に適した問題です。しかし、特に時間的性質が関わる他のシナリオでは、「この状態に到達すれば確実に失敗」というのを言うことができないかもしれません。そのため、常にこの方法が使えるわけではありませんが、使える場合はアルゴリズムのパフォーマンスを大幅に向上させることができます。
次に、拡張ステップでの改善です。これまでは名目上の軌道分布から外乱をサンプリングしているだけでした。目標に近いノードを拡張するように選択することで目標を考慮していましたが、その後はただランダムな外乱を選んでいました。目標に向かって操縦するような外乱を選ぶこともできます。
例えば、左下の隅にズームインしてみましょう。ここが目標だとして、これが拡張するノードだとします。目標にできるだけ近づくような外乱をサンプリングしようとすることができます。一つの方法は、多くの外乱をサンプリングし、目標に最も近づくものを次のステップのために選ぶことです。
質問がありましたか？ええ、良い質問です。前の講義では最も起こりやすい失敗を見つけようとしていました。それは最適化では目的関数のオプションでしたし、一般的に良い目的関数です。通常、これが見つけたいものです。しかし、これまで提示してきたものはその目的関数を使用していません。しかし後ほど、どのように使用できるかについて説明します。
別の質問として、この方法は一般的に最も起こりやすい失敗軌道を見つけるわけではなく、探索する全体的な空間を最小化するために検索を操作しているだけだということについてですが、そのとおりです。現在の目的は単に見つけられる失敗を見つけることです。
また、外乱について、目標状態までの距離を測定し、そこに向かうものを常に選択しているのかという質問ですが、この特定のケースではそうです。実際の目標は、選択できるすべての可能な外乱の中から、目標状態に最も近づくものを選ぶことです。それを行う一つの方法は、多くの外乱をサンプリングし、最も近づくものを選ぶことです。より高度な最適化を使用して、その外乱を見つけることもできますが、この場合は単にサンプリングしています。サンプルを多く取れば取るほど、計算コストは高くなりますが、より良い結果が得られます。そこにトレードオフがあります。
これら2つの改良を加えると、アルゴリズムがより効率的に実行され、失敗を見つけることができるようになります。しかも、かなり速く見つけることができます。
3.4 目標領域のサンプリング改善
Sydney Katz：RRTアルゴリズムの効率を高める最初の重要な改善は、目標状態のサンプリング方法を変更することです。基本的なRRTでは、各反復で状態空間全体からランダムに目標状態をサンプリングします。これは空間の探索を促進しますが、特定の関心領域（この場合は失敗領域）を見つけるのに効率的でない場合があります。
私たちのケースでは失敗を見つけることが最終目標なので、状態空間全体からランダムにサンプリングする代わりに、直接失敗領域（障害物のある領域）から目標状態をサンプリングする方がはるかに合理的です。この方法を使うと、ツリーが失敗領域に向かって成長するよう誘導され、失敗を素早く見つけることができます。
この改善の背後にある考え方は単純です。もし何を見つけようとしているのか知っているなら、その方向に探索を集中させるべきです。全体の空間をランダムに探索するよりも、知識を活用して探索を導くのです。
ただし、この改善策はいつでも適用できるわけではないという重要な注意点があります。なぜ最初からこの方法を使わなかったのかというと、すべてのシステムが簡単に識別できる明確な失敗領域を持っているわけではないからです。この連続世界の例では、赤い障害物エリアが明確な失敗領域として容易に識別できますが、これは単純な例です。
より複雑なシステムでは、特に時間的性質が関わる場合、どの状態が失敗に対応するかを事前に判断するのは難しいかもしれません。たとえば、「この状態に到達したら確実に失敗」と言えるような明確な状態集合がない場合があります。失敗が複数の状態にわたる挙動やパターンである場合、単一の状態だけを見ても失敗かどうか判断できないことがあります。
また、状態空間が非常に高次元で、失敗領域が複雑な形をしている場合、失敗領域から効率的にサンプリングすることも技術的に難しくなります。
そのため、失敗領域からのサンプリングは常に可能というわけではありませんが、可能な場合はアルゴリズムのパフォーマンスを大幅に向上させることができる強力な改善策です。この改善によって、失敗を見つけるために必要な反復回数を大幅に減らすことができます。
この連続世界の例では、失敗領域（赤い障害物）から常に目標状態をサンプリングすることで、アルゴリズムがより効率的に障害物に向かって探索を集中させるようになります。結果として、ずっと少ない反復回数で失敗経路を見つけることができるのです。
3.5 拡張ステップの改善
Sydney Katz：2つ目の重要な改善点は、拡張ステップでの外乱の選択方法に関するものです。基本的なRRTでは、選択したノードを拡張する際に、単に名目上の外乱分布からランダムに外乱をサンプリングしていました。これまでの方法では、目標に近いノードを選ぶことで目標を考慮していましたが、その後の外乱選択では目標に向かって積極的に操縦しようとはしていませんでした。
この部分を改善するために、目標に向かって積極的に導くような外乱を選択するアプローチを導入できます。例えば、連続世界の左下隅を見てみましょう。ここが目標状態で、これが拡張しようとしているノードだとします。この場合、目標にできるだけ近づくような外乱を選びたいと考えます。
これを実現する一つの効果的な方法は、多数の外乱候補をサンプリングし、それぞれがどの新しい状態に導くかをシミュレートした後、目標状態に最も近づく外乱を選択するというものです。これは一種の局所的な最適化で、次のステップで最も目標に近づく外乱を見つけるものです。
より具体的には、以下のようなプロセスになります：
- 選択したノードから、多数の可能な外乱（例：数十〜数百）をサンプリングします
- 各外乱に対して、エージェントがどの新しい状態に移動するかをシミュレートします
- 各新状態と目標状態の間の距離を計算します
- 目標状態に最も近い新状態をもたらす外乱を選択します
- その外乱を使用して実際にノードを拡張し、ツリーに新しいノードとエッジを追加します
このアプローチの計算コストとパフォーマンスの間にはトレードオフがあります。サンプリングする外乱の数が多いほど、目標に近づく可能性が高くなりますが、計算コストも増加します。実装時には、このトレードオフを考慮して適切なサンプル数を選ぶ必要があります。
さらに高度なアプローチとしては、ランダムサンプリングに頼るのではなく、目標に向かって導く外乱を直接見つけるための最適化手法を使用することもできます。例えば、目標に近づく度合いを目的関数として、その目的関数を最小化する外乱を見つけるための局所的な最適化を行うことができます。
これら2つの改善策（失敗領域からの目標サンプリングと目標指向の外乱選択）を組み合わせると、アルゴリズムの効率は大幅に向上します。視覚化したデモを見ると、改善したアルゴリズムは基本バージョンよりもずっと速く失敗を見つけることができます。特に失敗領域に向かって効率的に探索を集中させ、各ステップで目標に向かって積極的に進むことができるようになります。
これらの改善は実装が比較的簡単で、多くの問題設定で適用できるため、RRTを用いた誤動作探索の実践で非常に価値があります。プロジェクト1でスコアを向上させたい場合は、これらの改善を検討することをお勧めします。
4. 代替目的関数
4.1 コスト関数の定義
Sydney Katz：多くの方が質問していたように、より複雑な目的関数を使用してRRTを改良する方法について説明しましょう。これまで説明した改善策に加えて、代替目的関数を導入することで、特定のタイプの失敗経路（例えば最も可能性の高い失敗や最短経路の失敗）を見つけることができます。
まず、選択ステップでの目的関数の計算方法を変更することで、代替目的関数を組み込むことができます。以前、目標状態に基づいて各ノードの目的関数を計算するステップがありました。この計算方法を変更することで、別の目的を考慮できるようになります。
具体的なコスト関数を定義してみましょう。これは2つの要素から構成されます：
- 現在コスト（Current cost）：これは現在のノードに到達するのに必要なコストです。つまり、ここまで来るのにかかったコストです。
- 行くコスト（Cost to go）：これは現在のノードから目標に到達するのに必要な残りのコストです。
ただし、この「行くコスト」には問題があります。というのも、実際にはこれを正確に知ることができないからです。例えば、目標に到達するパスがこのように進むのか、あるいはこのように進むのか、残りのパスが何なのかを知らないのです。もし何が残っているのか知っていれば、すでに問題を解決していることになります。なぜなら、目標に行く方法をすでに知っていることになるからです。
そこで、通常はヒューリスティック関数H（heuristic function）を使って「行くコスト」を推定します。例えば、現在の状態と目標状態の間のユークリッド距離をヒューリスティックとして使用できます。これが「行くコスト」の推定値になります。
例えば、最短の失敗パスを見つけたい場合、「現在コスト」はツリー内の現在のノードまでの距離（この図のピンク部分）になります。そして「行くコスト」は、目標までの直線距離（鳥が飛ぶような最も直接的な経路の距離）になります。これらを足し合わせることでコスト関数を作ります。ツリー内の異なるノードすべてに対してこれを計算し、最も小さい値を持つノードを次に拡張します。
この図を見て、どのノードを次に拡張するかを考えると、ピンク部分と紫部分を足した値が最も小さいノードを選ぶことになります。見るのは少し難しいですが、6番のノードが最も値が小さくなるでしょう。1番目のノードは近いように見えますが、行ったり来たりするようなパスを通ったため、6番目のノードの方がコスト関数の値が低くなります。
これが最短パスを見つけるためのコスト関数ですが、多くの方が知りたがっていた「最も起こりやすい失敗」を見つけるためには、このコスト関数を別の形で定義する必要があります。それについては次のセクションで説明します。
4.2 最短経路探索
Sydney Katz：最短の失敗経路を見つけるためのコスト関数について詳しく見ていきましょう。ここで使用するコスト関数は、「現在コスト」と「行くコスト」の2つの要素から構成されています。
最短経路を探索する場合、「現在コスト」は初期状態から現在のノードまでの実際の移動距離（パスの長さ）になります。図で示したピンク色の部分がこれに相当します。これは、ツリーの根から現在のノードまで実際にたどったパスの総距離を計算することで求められます。
「行くコスト」は、現在のノードから目標状態までの推定残り距離です。実際の残り距離は知ることができないため、ヒューリスティックな推定値を使用します。最も一般的なのは、現在のノードから目標状態までの直線距離（ユークリッド距離）を使用することです。これは、鳥が飛ぶような最短経路の距離と考えることができます。図では紫色の部分がこれに相当します。
全体のコスト関数は、この「現在コスト」と「行くコスト」の合計です： コスト = 現在コスト + 行くコスト
ツリー内の各ノードに対してこのコスト関数を計算し、最も値が小さいノードを次の拡張対象として選択します。このアプローチは、最短経路優先探索に似ていますが、目標までの推定距離を含めることで、より効率的に目標に向かって探索を導きます。
図の例で考えてみましょう。ここにはいくつかのノードがあり、それぞれに対して「現在コスト」（ピンク）と「行くコスト」（紫）の合計を計算します。見た目からは判断しづらいですが、計算すると6番のノードが最小のコスト値を持つことがわかります。1番のノードは目標に近いように見えますが、そこに至るパスが行ったり来たりしているため、全体のコストは高くなっています。一方、6番のノードは効率的なパスで到達でき、目標までの残り距離も合理的であるため、トータルのコストが最も低くなっています。
最短経路探索のアプローチをRRTに組み込むと、アルゴリズムは空間内で最も効率的なパスを優先的に探索するようになります。連続世界の例では、最短経路の失敗を見つけると、エージェントが障害物に直接向かうようなパスが生成されることがわかります。
ただし、この最短経路アプローチには一つの欠点があります。それは、生成される失敗パスが必ずしも「起こりやすい」ものではないということです。最短経路を実現するために、非常に起こりにくい大きな外乱をサンプリングすることになるかもしれません。そのため、現実的なシステムの安全性評価という観点からは、最も起こりやすい失敗を見つける方が多くの場合重要になります。それについては次のセクションで説明します。
4.3 最も起こりやすい失敗の探索
Sydney Katz：多くの方が質問していた「最も起こりやすい失敗」を見つける方法について説明します。最も起こりやすい失敗を見つけるためには、コスト関数を尤度に基づいて定義する必要があります。
この場合、「現在コスト」は軌道の負の対数尤度となります。最小化したいのはコストなので、尤度の負の値を使います。ここで重要な注意点があります。探索が終了することを保証するためには、コストが常に正の値である必要があります。コストが負になる可能性があると、アルゴリズムが無限にループし続ける可能性があります。例えば、永遠に円を描き続けることでコストを下げられるかもしれません。
しかし、負の対数尤度は実際には負の値になる可能性があります。確率密度は常に正の値ですが、その対数は負になることがあるのです。そこで、コストが確実に正になるように、何らかの定数を加える必要があります。通常は、起こり得る最大の対数尤度のような値を加えて、どのケースでも負のコストが発生しないようにします。
次に「行くコスト」ですが、これは残りの経路の負の対数尤度を推定する必要があります。これを正確に推定するのは簡単ではありません。様々なアプローチがありますが、明確な最適な方法はありません。
一つのアプローチとしては、目標までの距離を負の対数尤度の代わりに使用することです。これは、目標までの距離が短いほど、そこに到達するのに必要な時間ステップが少なく、サンプリングする外乱も少なくなるため、尤度が高くなるという考えに基づいています。つまり、短いパスは一般的に尤度が高いという仮定を置いています。
これはあくまでヒューリスティックであり、探索を導くための推定値に過ぎません。完全に正確である必要はなく、探索を適切な方向に導くのに役立つ近似値であれば十分です。
実際には、ヒューリスティックの設計には多くの場合ドメイン知識が必要です。この連続世界の例では全てが明確ですが、他のドメインではそれほど明確でない場合があります。時には「距離」という概念すら明確に定義できないドメインもあります。
このような最も起こりやすい失敗を見つけるためのコスト関数を使用すると、アルゴリズムは尤度の高い失敗軌道を優先的に探索するようになります。連続世界の例では、最も起こりやすい失敗を探索すると、エージェントが名目上のパス（外乱なしの場合の経路）に近い場所を進み、最後の部分でのみ障害物に向かって逸れるようなパスが生成されます。
この方法は、単に「失敗する」だけでなく、「現実的に発生し得る失敗」を見つけることができるため、安全性検証において非常に価値があります。システムの本当の脆弱性を特定するには、起こりそうな失敗シナリオを見つけることが重要だからです。
4.4 離散問題におけるA*アルゴリズム
Sydney Katz：ここで特筆すべきことがあります。もしヒューリスティック関数が「許容的（admissible）」であり、状態空間と外乱空間の両方が離散的である場合、このアルゴリズムはA*探索に変わります。これは非常に興味深い性質です。
許容的なヒューリスティックとは何でしょうか？それは、目標状態に到達するためのコストを決して過大評価しないことが保証されているヒューリスティックです。これを設計するには再びドメイン知識が必要で、常に簡単に設計できるわけではありません。
ここで、離散的な問題であるグリッドワールドの例を考えてみましょう。状態空間と外乱空間が離散的である必要があるので、連続問題から離散問題に切り替えます。この場合、許容的なヒューリスティックがどのように見えるか考えてみましょう。
例えば、このノードに対して「行くコスト」を推定する必要があるとします。非常に一般的な許容的ヒューリスティックは、直線距離（鳥が飛ぶような距離）、つまり現在の状態と目標状態の間のユークリッド距離を使用することです。
これが許容的であることがわかる理由は、実際の目標到達コストを決して超えないからです。このグリッドワールドでは、実際には直線的に移動することはできず、セル間を離散的に移動する必要があります。最短経路は実際にはこのようになります（格子に沿った動き）。三角形の性質から、直線距離は常に実際の経路よりも短くなることがわかります。
同様に、これは遭遇するどの状態からも当てはまります。そのため、ユークリッド距離はここでは許容的なヒューリスティックとなります。
このような条件が整うと、アルゴリズムはA*探索になり、最適経路を見つけることが保証されます。RRTでは、これらの良い経路を見つけることを促していましたが、保証はありませんでした。しかし、これらの特定の条件下では、最短経路または最も起こりやすい失敗を見つけることを実際に保証できます。
グリッドワールドでのA*アルゴリズムの実行結果を見ると、最短経路の場合は障害物に直接向かうようなパスが生成されます。一方、最も起こりやすい失敗を探す場合は、名目上のパスに沿って進み、最後の部分でのみ下に逸れて障害物に衝突するようなパスが生成されます。
Aアルゴリズムが許容的なヒューリスティックを使用する理由についての直感的な説明ですが、これは完全性と最適性の保証に関係しています。ヒューリスティックが目標までのコストを過大評価しないことで、アルゴリズムは最適解を見逃すことなく、効率的に探索できるのです。詳細に興味がある方は、A探索に関する良いYouTubeビデオがありますので、ぜひ確認してみてください。これらを見ると、なぜこれらの要素が組み合わさるとA*になるのかが明確になるでしょう。
5. モンテカルロツリー探索
5.1 探索と活用のバランス
Sydney Katz：次に説明するのは、モンテカルロツリー探索（Monte Carlo Tree Search、MCTS）です。MCTSの特徴的な点は、探索（exploration）と活用（exploitation）のバランスを明示的に取る方法があることです。
ここでの考え方は、可能な軌道の空間を探索したいという欲求と、失敗に導く可能性が高いと分かっている軌道を活用したいという欲求の間でバランスを取ることです。いくらかの探索を行った後、ある種の軌道は他よりも失敗に導く可能性が高いことがわかります。そういった知識を活用したいのです。
MCTSでは、ツリーの各ノードに対して価値推定（value estimate）を維持することで、有望なパスを特定します。この価値推定をQと呼びます。ここで混乱を避けるために注意点があります。他の講義、例えばAA228では、多くの場合、価値を最大化しようとします。しかし、これまで話してきたすべてのコストとの一貫性を保つため、この講義ではQを最小化したいと考えます。
興味深いことに、MCTSも同じように選択ステップと拡張ステップという枠組みで表現できることを示しました。選択ステップでは、高いレベルで何が起きているかというと、探索と活用のバランスを取るヒューリスティックに基づいて、現在ツリーにあるノードを拡張するために選択します。拡張ステップでは、外乱をサンプリングしてツリーに追加し、結果を上方向に伝播します。これが具体的に何を意味するのかをこれから説明します。
再び、これまでに構築してきたツリーがあると仮定します。各ステップで何が行われるのかを見ていきましょう。まず選択ステップから始めます。
MCTSでは、先ほど述べたように、ツリー内の各ノードに対して価値関数（またはその推定値）を維持します。これがQです。各ノードには何らかのQが関連付けられており、低い値が「より良い」ことを意味します。例えば、このノードは失敗に非常に近いため、かなり低い値を持っています。
また、ツリー内の各ノードに対して、N（訪問回数）も維持します。これは、ツリー探索の中でそのノードを訪問した回数です。ここでは、ツリー探索がすでにしばらく進行していると仮定しているので、これらのノードにはいくつかのNとQの値があります。
さて、MCTSのもう一つの反復を行いたいとします。最初に行うのは選択ステップです。その仕組みは、このスペースにいるとイメージして、このツリーに沿って歩くというものです。ルートノードから始めます。
各選択ステップの最初に行うのは、現在のルートノードの子ノードの数が、この式の値以下かどうかを確認することです。ここでNは現在いるノードの訪問回数で、Kとαはハイパーパラメータです。αは0から1の間の値であるべきですが、一般的には、これらを選択するとノードを拡張するか、ツリーの深部に進むかのトレードオフを制御します。
子ノードの数がこの数より少ない場合、そのノードにはもっと子ノードが必要であることを意味します。その場合は「はい」となり、そのノードを選択して拡張ステップに進みます。そうでない場合は、以下の式を最小化する子ノードに移動します。これについては後ほど詳しく説明します。
要するに、「はい」ならそのノードを拡張して拡張ステップに進み、「いいえ」ならツリーの探索を開始します。
5.2 選択ステップの実装
Sydney Katz：ツリーを探索する場合、つまり子ノードの数が十分にある場合、ここで探索と活用のバランスを取ります。現在の位置から行ける場所をすべて見るために、持っているすべての子ノードを見ます。そして、子ノードごとにこの値を計算します。この値は2つの要素の組み合わせです。
最初の要素はQ_childです。これが活用の部分です。子ノードのQ値が既に低い場合（私たちは最小化を目指しています）、そのノードに行くのは良い考えかもしれません。なぜなら、それは有望なパスである可能性が高いからです。しかし、常に既知の情報だけを活用したいわけではありません。まだ知らない、もっと良い何かがあるかもしれないからです。そこで、この2つ目の項がそのバランスを取るのです。
この2つ目の項は、その子ノードをあまり訪問していない場合、この値が大きくなります。そのため、「探索ボーナス」と呼ばれるものが大きくなります。そうすると、「Q値はそれほど良くないかもしれないが、あまりそこに行っていないので、そのノードを探索してみよう」と判断することになります。
これら2つの要素のバランスを取る方法は、「探索ボーナス」と呼ばれるこの要素によって制御されます。これにより、何をしたいかに応じて、探索と活用のバランスを調整できます。
質問がありますか？ええ、分子と分母が同じなのかという質問ですね。分子のNは現在いるノードの訪問回数です。今あなたは子ノードを見て、どこに行くか決めようとしています。分母のNは、訪問するかどうかを決めようとしている子ノードの訪問回数です。
では例を見てみましょう。例えば、パラメータK=1、α=0.5とします。これらは問題が解けるように選んだだけです。この式にNを代入すると、2.82が得られます。子ノードの数（3）は2.82未満でしょうか？いいえ、そうではありません。したがって、こちらのパスに沿って進みます。
ここで各子ノードを見て、次にどのノードに移動するかを決めるために、各子ノードに対してこの値を計算する必要があります。例えばこの子ノードでは、Q_childとNの値を代入すると、9.26が得られます。この子ノードでは0.78、この子ノードでは11.26になります。
最も低い値を持つノードに移動するので、このノード（0.78）を選びます。ちなみに、これは時々「下限信頼区間（Lower Confidence Bound）」と呼ばれます。AA228では逆にQを高くしたいので、ここでプラスを使い、それは「上限信頼区間（Upper Confidence Bound）」と呼ばれます。
したがって、最も低い値のノードを選び、そのノードに移動してこのプロセスを繰り返します。再びK=1、α=0.5として計算します。計算すると、値は2になるはずです（スライドの数字は更新されていません）。子ノードの数は2なので、2≤2が成り立ちます。したがって、この不等式は満たされ、このノードを選択して拡張ステップに進みます。
質問がありますか？
Kとαについて少し混乱しているという質問ですが、これらは本質的にヒューリスティックで、ノードに多くの子ノードがあるかどうかを決定するために使われます。多くの子ノードがある場合、おそらくもっとサンプリングする必要はなく、ツリーの深部に進みたいと思うでしょう。この式は基本的にその目的のバランスを取ります。子ノードが多ければ、おそらくその一つに行きたいと思うでしょう。これは、ツリーをさらに探索するステップに従うことを意味します。しかし、十分な子ノードがない場合は、その特定のノードで拡張ステップに行きたいでしょう。
この条件は連続世界で必要なのかという質問ですが、離散的な数の結果がない場合、これを行う必要があります。連続的な場合、ノードから次のノードに切り替わるときに無限に子ノードをサンプリングし続ける可能性があります。なぜなら、外乱の空間が連続的だからです。各外乱は異なり、可能性のある事象の連続的な空間があります。そのため、このようにして子ノードの数を制御する必要があります。離散的なMCTSのバージョンでは、これを心配する必要はありません。
これは「プログレッシブワイドニング（progressive widening）」と呼ばれる技術です。
5.3 プログレッシブワイドニング
Sydney Katz：モンテカルロツリー探索（MCTS）の重要な構成要素の一つが、プログレッシブワイドニング（progressive widening）と呼ばれるテクニックです。これは特に連続的な状態空間や行動空間を扱う際に不可欠なメカニズムです。
なぜプログレッシブワイドニングが必要なのでしょうか？連続世界のような連続的な問題では、各ノードから理論的には無限の可能な行動（外乱）が存在します。離散的な問題では、例えば上下左右のみに移動できるグリッドワールドのように、可能な行動の数は有限で少数です。しかし連続空間では、わずかに異なる角度や強度の外乱を考えるだけでも、無限の可能性があります。
このような状況では、特に計算リソースが限られている中で、どれだけの「子ノード」（つまり、異なる行動や外乱から生じる新しい状態）を考慮すべきかを決定する方法が必要です。ここでプログレッシブワイドニングが役立ちます。
プログレッシブワイドニングの基本的な考え方は、ノードの「訪問回数」に基づいて、そのノードに許可される子ノードの数を動的に制御することです。つまり、あるノードをより頻繁に訪問するほど、そのノードから考慮する異なる行動（子ノード）の数を増やすことができるというものです。
具体的には、以下の式を使用します：
子ノードの最大数 ≤ K × (N)^α
ここで：
- Nはノードの訪問回数
- Kは定数パラメータ
- αは0と1の間のパラメータ（通常は0.5程度）
この式は、ノードを頻繁に訪問するほど、より多くの子ノードを探索することを許可します。しかし、その増加率はα（アルファ）によって制御されます。α=1の場合、子ノードの数は訪問回数に比例して線形に増加しますが、α<1（例えば0.5）の場合、子ノードの数は訪問回数が増えるにつれてより緩やかに増加します。
選択ステップでは、現在のノードの子ノードの数がこの式の右辺以下かどうかをチェックします。もしそうなら、このノードにはまだ十分な子ノードがないと判断し、新しい子ノードを追加するために拡張ステップに進みます。そうでない場合は、既存の子ノードの中から次に探索するノードを選びます。
例えば、K=1、α=0.5、N=4（現在のノードの訪問回数）の場合： 最大子ノード数 ≤ 1 × 4^0.5 = 1 × 2 = 2
現在のノードの子ノードが2個以下なら、新しい子ノードを追加するために拡張ステップに進みます。それ以上なら、既存の子ノードの中から最適なものを選びます。
このメカニズムにより、訪問回数の少ないノードでは少数の行動のみを考慮し、そのノードが有望と判断されてより多く訪問されるようになると、より多くの行動を考慮するようになります。これにより、計算リソースを効率的に使用しながら、連続空間をうまく探索することができます。
プログレッシブワイドニングのパラメータK、αの選択は、探索の深さと幅のトレードオフに影響します。Kを大きくしたりαを大きくしたりすると、より多くの子ノードが生成され、探索の幅が広がりますが、同時にツリーの深さは制限されます。一般的には、K=2、α=0.5が推奨されますが、問題に応じて調整が必要な場合もあります。
5.4 UCB (Upper Confidence Bound)の使用
Sydney Katz：プログレッシブワイドニングにより、子ノード数が十分だと判断されると、次に訪問する子ノードを選択する必要があります。ここで、探索と活用のバランスを取るための重要なメカニズムとしてUCB（Upper Confidence Bound）が登場します。ただし、私たちの場合はコストを最小化したいので、LCB（Lower Confidence Bound）と呼ぶ方が適切かもしれません。
各子ノードに対して、以下の値を計算します：
LCB値 = Q_child - C * √(log(N) / N_child)
この式には2つの主要な要素があります：
- Q_child：これは「活用」の部分です。Q値はそのノードの価値推定値で、低いほど良いと考えます（失敗に近いことを意味します）。Q値が低いノードを選ぶと、既に有望だと知っているパスを活用することになります。
- C * √(log(N) / N_child)：これは「探索」のボーナスです。N_childはその子ノードの訪問回数、Nは親ノードの訪問回数です。子ノードの訪問回数が少ないほど、この項は大きくなります。Cは探索の度合いを制御する定数パラメータです。
この式では、マイナス記号がついていることに注意してください。これはQ値を最小化したいからです。AA228などの他の文脈では、通常Q値を最大化したいため、プラス記号を使い、「UCB（Upper Confidence Bound）」と呼びます。
実際の例で見てみましょう。3つの子ノードがあり、それぞれのQ値と訪問回数が与えられています。LCB値を計算すると：
- 子ノード1：9.26
- 子ノード2：0.78
- 子ノード3：11.26
最も低い値である0.78を持つ子ノード2を選択します。
この方法の背後にある直感は次のとおりです：
- Q値が低い（良い）ノードを選ぶと、既知の有望なパスを活用することになります。
- あまり訪問していないノードには大きな探索ボーナスが与えられ、未知の可能性を探索することを促します。
- 訪問回数が増えるにつれて、探索ボーナスは減少し、アルゴリズムはより活用に傾きます。
- 親ノードの訪問回数が増えるほど、子ノードの探索ボーナスが増加し、新しい可能性を考慮することを促します。
Cパラメータは探索と活用のバランスを直接制御します：
- Cが大きいほど、探索が重視されます（訪問回数の少ないノードが選ばれやすくなる）
- Cが小さいほど、活用が重視されます（Q値の低いノードが選ばれやすくなる）
最適なCの値は問題に依存します。Q値のスケールや、解空間の複雑さによって適切な値は変わります。一般的には1から2の間の値がよく使われますが、特定の問題に合わせて調整する必要があります。
このUCB/LCBの使用により、MCTSは木全体での探索と活用のバランスを効果的に取ることができます。単に最もQ値の低いノードを常に選ぶのではなく、訪問回数の少ないノードも適切に考慮することで、局所的な最適解に陥ることを避け、より広い解空間を探索することができます。
5.6 実行例と視覚化
Sydney Katz：モンテカルロツリー探索の実行例を見てみましょう。これは私が教科書で最も気に入っている図の一つです。ここでお見せするのは、この失敗（障害物への衝突）に到達しようとするモンテカルロツリー探索の実行です。より頻繁に訪問されるノードやより頻繁に辿られるエッジは、あまり辿られないものよりも少し暗く表示されます。これにより、探索と活用のバランスを視覚的に確認することができます。
（アニメーションが表示されます）
これは非常に興味深い結果です。この視覚化から、モンテカルロツリー探索がどのように動作するかがよくわかります。最初は空間全体をかなり広く探索していますが、有望なパスが見つかるにつれて、それらのパスをより集中的に探索するようになります。
特に注目すべきは、よく訪問される経路が暗く表示されていることです。これらの経路は、アルゴリズムが「有望」と判断したもので、より多くの計算リソースが割り当てられています。一方、あまり頻繁に訪問されない経路は薄く表示されています。これは、それらの経路があまり有望ではないと判断されたか、または十分に探索された後に有望ではないと判断されたことを示しています。
また、探索は空間全体に広がっていますが、特に障害物の周りと、エージェントの初期位置から障害物への潜在的な経路に集中していることがわかります。これは、アルゴリズムが目標（この場合は失敗を見つけること）に関連する領域に効率的に計算リソースを割り当てていることを示しています。
モンテカルロツリー探索の強みは、この探索と活用のバランスにあります。完全にランダムな探索だけでは、非効率的で時間がかかりすぎるでしょう。逆に、有望と思われるパスだけを活用すると、局所的な最適解に陥ってしまう可能性があります。MCTSは、確率的な探索と価値に基づく活用を組み合わせることで、広範囲を探索しながらも有望な領域に計算リソースを集中させるという優れたバランスを実現しています。
この視覚化は、MCTSが安全重視システムの検証において、特に失敗モードを見つける際にいかに効果的かを示しています。システムが複雑で高次元になるほど、このようなインテリジェントな探索戦略の価値は高まります。
