2025-04-08 Stanford AA228V: 非線形システムのリーチャビリティ解析 - 区間演算から高次テイラーモデルへの道

※本記事は、スタンフォード大学のコース「AA228V Validation of Safety Critical Systems」の講義「Reachability for Nonlinear Systems」の内容を基に作成されています。講義の詳細情報はコースウェブサイト https://aa228v.stanford.edu/ でご覧いただけます。また、教科書「Algorithms for Decision Making」は https://algorithmsbook.com/validation/ で入手可能です。本記事では、講義の内容を要約しております。

講師はSydney Katz博士（スタンフォード大学ポスドクスカラー）です。Sydney Katz博士の詳細は https://sydneymkatz.com/ でご覧いただけます。

なお、本記事の内容は原講義の見解を正確に反映するよう努めていますが、要約や解釈による誤りがある可能性もありますので、正確な情報や文脈については、オリジナルの講義やコースへの参加をお勧めいたします。コースの詳細や登録については https://online.stanford.edu/courses/ をご参照ください。スタンフォードオンラインを通じて、スタンフォード大学が提供する学位プログラム、単位取得可能な教育、専門家向け証明書プログラム、無料公開コンテンツなどにアクセスすることができます。

1. 線形リーチャビリティの復習

1.1. 頂点数の指数関数的増加の問題

Sydney Katz：前回の講義では線形システムのリーチャビリティについて議論しました。そこで直面した問題は、線形方程式を通じてポリトープを伝播させる際、各時間ステップで頂点の数が蓄積されていくことでした。この頂点数は指数関数的に増加していきます。例えば、初期集合から時間とともにリーチャブル集合を計算していくと、各ステップで頂点数が増えていき、ある深さまでの計算を行うと膨大な数の頂点を扱わなければならなくなります。

これはすぐに計算上扱いきれなくなる問題を引き起こします。この問題に対処するひとつの方法として、ゾノトープという表現を使用することを提案しました。ゾノトープでは、ジェネレータの数が深さに対して線形に増加するため、頂点数の指数関数的増加よりもはるかに計算効率が良くなります。

しかし、ゾノトープには限界もあります。すべてのポリトープをゾノトープとして表現できるわけではないので、常にこの方法が適切とは限りません。そのため、講義の最後に別のアプローチとして「過大近似（オーバーアプロキシメーション）」について触れました。これは実際のリーチャブル集合を含むより単純な集合を用いる方法です。

実際の応用では、このような計算コストの問題に対処するため、数ステップごとに一度リーチャブル集合を過大近似し、より少ない頂点を持つ集合で置き換えるという手法を取ることがあります。これにより頂点数の増加速度を抑えることができます。もちろん、この過大近似のプロセスによって精度と計算効率のトレードオフが生じますが、形式的手法による安全性保証を維持しながら計算可能性を確保するために必要な妥協点です。

1.2. 集合の過大近似（オーバーアプロキシメーション）

Sydney Katz：過大近似（オーバーアプロキシメーション）は、ある集合に対して、その集合を完全に含む別の集合を見つけるというアプローチです。例えば、頂点数が多すぎるポリトープがあった場合、それを少ない頂点数のポリトープで過大近似することができます。数学的には、集合Sの過大近似S̄は、S⊆S̄となるような集合として定義され、通常は上部にバーを付けて表記します。

この過大近似の重要な点は、形式的手法による安全性保証を維持しながら計算効率を向上させることができる点です。例えば、リーチャブル集合の過大近似が回避すべき集合（avoid set）と交わらない場合、真のリーチャブル集合も回避すべき集合と交わらないことが保証されます。これにより、システムの安全性を証明することができます。

一方、過大近似が回避すべき集合と交わる場合、システムが安全かどうかについての結論を出すことはできません。過大近似の範囲内にあるというだけで、真のリーチャブル集合が実際に回避すべき集合と交わるかどうかは不明だからです。このような場合は「結論が出せない（inconclusive）」状態となります。

実際の応用では、計算コストを抑えるために、数ステップごとに一度リーチャブル集合を過大近似し、以降の計算はこの過大近似された集合から始めるという方法が取られます。これにより頂点数が急速に増加する問題を緩和できますが、過大近似によって精度が失われるというトレードオフが生じます。つまり、計算効率と過大近似の精度（または保守性）のバランスを取る必要があります。

システムが安全であることを証明したい場合、過大近似は保守的なアプローチとして有効です。過大近似されたリーチャブル集合が安全であると判断できれば、実際のシステムも安全であることが保証されるからです。しかし、過大近似が大きすぎると、安全なシステムでも「結論が出せない」という結果になってしまう可能性があります。

1.3. LazySetsパッケージによる自動過大近似

Sydney Katz：実際の応用では、リーチャブル集合の頂点数が増えすぎる問題に対処するため、定期的に過大近似を行うプロセスが必要です。幸いなことに、Juliaプログラミング言語の「LazySets」パッケージを使えば、このプロセスを自動化することができます。

LazySetsパッケージでは、過大近似を効率的に実装するためのアルゴリズムが提供されています。このアルゴリズムの基本的な考え方は、指定した頻度でリーチャブル集合を過大近似することです。例えば、3ステップごとに過大近似を行うように設定できます。

コード実装では、まず「frequency」というパラメータを設定します。これは何ステップごとに過大近似を行うかを指定します。そして、LazySetsが提供する「overapproximate」関数を呼び出し、エラー許容度を指定します。この関数は自動的に集合を過大近似し、より少ない頂点を持つ集合を返します。

図で説明すると、例えば3ステップごとに過大近似を行う場合、初期集合からスタートして2つ目の時間ステップまでは通常通り計算します。そして3つ目の時間ステップで、計算されたリーチャブル集合（これは多くの頂点を持つ可能性があります）を、例えば4つの頂点だけを持つ多角形で過大近似します。その後は、この過大近似された集合を新たな出発点として、次の時間ステップのリーチャブル集合を計算します。

過大近似の精度は、許容する頂点数によって調整できます。より多くの頂点を許容すれば、より精密な過大近似が可能ですが、計算コストが増加します。少ない頂点数を指定すれば計算は効率的になりますが、過大近似の誤差が大きくなります。

このアプローチを使用すると、当然ながらトレードオフが生じます。過大近似を使うことで、計算量と精度（または保守性）のバランスを取る必要があります。過大近似された集合から次のリーチャブル集合を計算するため、時間が経つにつれて誤差が蓄積していく可能性があります。

LazySetsが提供するoverapproximateアルゴリズムの詳細については、教科書に記載されています。このアルゴリズムは、与えられた集合を効率的に過大近似するために、方向の選択を最適化する賢い方法を使用しています。プロジェクト3では、小さな問題でリーダーボードのスコアを最適化したい場合は、これらの方向の選び方を工夫するとよいでしょう。単に合格するだけなら、箱型の近似（box approximation）でも十分です。

1.4. サポートベクトルの概念

Sydney Katz：集合を過大近似する方法の背後にある重要な概念は「サポートベクトル」です。サポートベクトルは数学的には少し混乱しやすいかもしれませんが、直感的には非常に理解しやすい概念です。

数学的に定義すると、サポートベクトルは方向ベクトルをインプットとして受け取り、ベクトルを返す関数です。サポートベクトル関数σ(d)は、方向dにおけるサポートベクトルを与えます。具体的には、集合内のすべての点xについて、x・d（ドット積）を最大化する点xを返します。これは方向dに最も「遠い」点を見つけるプロセスと考えることができます。

視覚的に説明すると、まず空間内の方向dを指定します。例えば、2次元平面上で特定の方向を選びます。次に、その方向に垂直な直線を考えます。この直線を、方向dに沿って集合から離れる方向に、集合との接点がなくなるギリギリまで押していきます。最終的に、この直線が集合と接する点がサポートベクトルとなります。

このプロセスの重要な点は、サポートベクトルによって半空間が定義されることです。サポートベクトルを通り、方向dに垂直な平面によって空間が2つに分割されます。集合はこの平面のある側にすべて含まれることになります。つまり、サポートベクトルは集合を含む半空間の境界を定義しています。

さらに、異なる方向でこのプロセスを繰り返すことで、集合を含む複数の半空間の交差を得ることができます。例えば、3つの異なる方向でサポートベクトルを計算すれば、3つの半空間の交差によって三角形の境界（ポリトープ）が得られます。これが集合の過大近似となります。

より多くの方向でサポートベクトルを計算するほど、より精密な過大近似が得られますが、結果として得られるポリトープの頂点数も増加します。ここでも計算コストと精度のトレードオフが生じます。

LazySetsパッケージのoverapproximateアルゴリズムは、与えられた集合を効率的に過大近似するために、これらの方向を賢く選択する方法を実装しています。方向の選び方によって過大近似の質が大きく変わるため、適切な方向の選択は重要です。

これがサポートベクトルの基本的な概念です。サポートベクトルを理解することで、集合の過大近似だけでなく、次のセクションで説明する最適化技術によるサポートベクトルの直接計算の基礎も理解できます。

1.5. 最適化技術によるサポートベクトルの直接計算

Sydney Katz：サポートベクトルによって集合を境界付ける方法を見てきましたが、これまではまず集合を伝播させ、その後でサポートベクトルを求めていました。しかし実は、集合伝播を行わなくても、サポートベクトルを直接計算することが可能です。これには最適化問題を解くアプローチを使います。

具体的には、ある方向dにおけるリーチャブル集合のサポートベクトルを見つけるために、次の最適化問題を解きます：

max d・s_d 制約条件：

1. s_0 ∈ S_0（初期状態は初期集合に属する）
2. w_t ∈ W_t, t = 0,1,...,d-1（各時間のディスターバンスはそのディスターバンス集合に属する）
3. s_{t+1} = f(s_t, w_t), t = 0,1,...,d-1（システムのダイナミクス方程式を満たす）

ここでs_dは深さdでの状態、S_0は初期状態集合、W_tは時間tでのディスターバンス集合、fはシステムの状態遷移関数です。

この最適化問題は、以下の点を考慮しています：

• 目的関数は、深さdでの状態ベクトルと方向ベクトルdのドット積を最大化します
• 初期状態と各時点でのディスターバンスに対する制約があります
• システムのダイナミクスに従う必要があります（軌跡が物理的に可能であること）

これらの制約を満たしながら目的関数を最大化することで、方向dにおけるリーチャブル集合の「最も遠い点」を特定できます。

重要なのは、これが線形システムの場合、かつS_0とW_tがポリトープである場合、この問題は線形計画問題（LP）となり、効率的に解くことができるということです。線形計画法の解法アルゴリズムについての詳細は、来学期のAA 222コースで学ぶことができます。

この最適化アプローチの最大の利点は、集合伝播を全く行わなくても、特定の方向におけるリーチャブル集合の境界を直接求められることです。複数の方向で最適化問題を解くことで、リーチャブル集合の過大近似を構築できます。

さらに、教科書では説明していませんでしたが、もし「リーチャブル集合が回避すべき集合と交わるかどうか」だけを知りたい場合、集合の形状を計算しなくても、最適化問題を変形して直接その質問に答えることができます。その場合は、リーチャブル集合内の点と回避すべき集合内の点との距離を最小化する問題を解き、その距離がゼロになるかどうかをチェックします。

さまざまな方向でサポートベクトルを計算することの効果を見るために、教科書の最後の図では、異なる方向選択戦略の比較を行っています。軸に沿った4つの方向（上下左右）を使うと単純な境界ボックスが得られますが、過大近似の誤差は大きくなります。ランダムな10方向や50方向を使うと精度は向上しますが、最も効果的なのは主成分分析（PCA）を用いて方向を選ぶ方法です。サンプル点からPCAを行い、データの主要な変動方向を特定することで、わずか4つの方向でも非常に精度の高い近似が可能になります。

2. 非線形システムの課題

2.1. 非線形演算子のポリトープへの適用の難しさ

Sydney Katz：前回の講義では線形システムのリーチャビリティについて説明しましたが、今回は非線形システムのリーチャビリティに焦点を当てます。線形システムでは、ポリトープに線形演算子を適用することが比較的容易でした。具体的には、ポリトープに行列乗算や加算といった線形演算を適用できました。しかし、非線形演算子をポリトープに適用する場合、状況は格段に複雑になります。

この難しさを具体的な例で説明しましょう。まず線形の場合を考えてみます。2つの頂点を持つポリトープ（つまり線分）があり、これに「2x+1」という線形演算を適用すると、結果もまた線分となります。これは計算が比較的簡単で、結果も扱いやすいポリトープのままです。

しかし、同じ線分に「sin(x)+1」のような非線形演算を適用すると、結果はもはやポリトープではなくなってしまいます。さらに、結果の集合は凸集合ですらなくなる可能性があります。図で示したように、結果の集合から2点を選び、それらを結ぶ線分を引くと、その線分が集合に完全に含まれないことがあります。これは非凸集合の特徴です。

非凸集合は扱いが非常に難しくなります。例えば、2つの非凸集合の和や積といった演算が単純に定義できなくなりますし、計算コストも著しく増加します。非線形システムのリーチャビリティ解析が難しい根本的な理由はここにあります。

実際には、非線形関数による変換後の集合を正確に表現することは困難なため、代わりにこれらの非凸集合をポリトープなどの扱いやすい形状で過大近似するアプローチを取ります。これが本講義の残りの部分で説明する手法の基本的な考え方です。様々な過大近似技術を使って、非線形システムのリーチャブル集合を扱いやすく近似していきます。

非線形システムにおけるポリトープの演算の難しさは、計算効率と表現能力のトレードオフをもたらします。正確な結果を得るためには複雑な集合表現が必要になりますが、それは計算コストの増加を意味します。一方、単純な表現を使えば計算は効率的になりますが、過大近似による誤差が大きくなります。このトレードオフを適切に管理することが、非線形システムのリーチャビリティ解析における主要な課題です。

2.2. 非凸集合の扱いの複雑さ

Sydney Katz：非線形システムにおいて直面する大きな課題の一つは、非凸集合の扱いの複雑さです。先ほど説明したように、非線形関数をポリトープに適用すると、結果として非凸集合が生じることがあります。

非凸集合は、凸集合と比較して数学的に扱うのがはるかに難しくなります。凸集合では、任意の2点を選んでその間の線分を引くと、その線分上のすべての点も必ず集合に含まれるという性質があります。この性質により、凸集合は表現や操作が比較的簡単になります。例えば、凸集合は有限個の頂点や半空間の交わりとして効率的に表現できます。

しかし、非凸集合ではこの性質が成り立ちません。任意の2点を選んでその間の線分を引いたとき、その線分上に集合に含まれない点が存在する可能性があります。この特性により、非凸集合の表現や操作は著しく複雑になります。例えば、非凸集合を正確に表現しようとすると、多くの場合、複数の凸集合の和集合として表現する必要があり、計算コストが急増します。

非凸集合の複雑さは、以下のような具体的な問題を引き起こします：

1. 表現の難しさ：非凸集合を正確に表現するために必要なデータ量が膨大になりがちです。
2. 演算の複雑さ：非凸集合同士の和、積、ミンコフスキー和などの演算が計算上非常に難しくなります。
3. メモリ使用量の増加：非凸集合を保存するために必要なメモリ量が大きくなります。
4. アルゴリズムの複雑化：非凸集合を扱うアルゴリズムは、凸集合を扱うものよりも複雑になります。

これらの理由から、非線形システムのリーチャビリティ解析では、非凸集合を直接扱うのではなく、それを凸集合（特にポリトープやその他の単純な形状）で過大近似するアプローチがよく用いられます。サポートベクトルを使えば非凸集合も境界付けることが可能です。例えば、非凸集合に対してサポートベクトルを評価する場合、特定の方向で「最も遠い点」は依然として定義できます。その結果、非凸集合も凸集合で過大近似できます。

しかし、これは当然のことながら精度と計算効率のトレードオフをもたらします。過大近似によって計算は効率化されますが、結果の精度は低下します。リーチャビリティ解析の目的が安全性の証明であれば、過大近似は保守的なアプローチとして適していますが、過大近似が大きすぎると「結論が出せない」ケースが増えてしまうというデメリットもあります。

このような非凸集合の扱いの複雑さが、非線形システムのリーチャビリティ解析を線形システムのそれよりもはるかに困難にしている主要な理由の一つです。

2.3. 過大近似による解決アプローチ

Sydney Katz：非線形システムにおけるリーチャブル集合の非凸性とその扱いの複雑さに対処するため、主に過大近似（オーバーアプロキシメーション）に基づくアプローチが用いられます。この方法の基本的な考え方は、複雑な非凸集合を、より単純で扱いやすい凸集合で近似することです。

過大近似による解決アプローチの中心的な考え方は次のとおりです：

1. 非凸集合を含む単純な形状（ポリトープや超矩形など）を見つける
2. この単純な過大近似を用いて以降の計算を行う
3. 安全性の保証を維持しながら計算効率を向上させる

このアプローチの主な利点は、計算の簡素化にあります。非凸集合を直接扱うのではなく、それを包含する凸集合を使用することで、演算が大幅に簡略化されます。例えば、サポートベクトルの概念を用いると、任意の集合（非凸でも）に対して、特定の方向における「最も遠い点」を見つけ、その方向での境界を定義することができます。異なる方向でこのプロセスを繰り返すことで、元の集合を完全に含む凸多面体（ポリトープ）を構築できます。

講義の残りの部分では、非線形システムのリーチャブル集合を過大近似するための様々な手法を紹介します。具体的には以下のアプローチを扱います：

1. 区間演算（インターバル算術）：状態変数の可能な値の範囲を区間として表現
2. 包含関数（インクルージョン関数）：関数の出力範囲を過大近似する手法
3. テイラーモデル：関数をテイラー級数で近似し、リーチャブル集合を表現

過大近似アプローチは常に保守的な結果をもたらします。つまり、実際のリーチャブル集合は必ず過大近似された集合に含まれます。これは安全性検証において重要な性質です。もし過大近似された集合が危険な状態（避けるべき集合）と交わらなければ、実際のシステムも安全であることが保証されます。

ただし、過大近似が大きすぎると、実際には安全なシステムでも「結論が出せない」という結果になってしまう可能性があります。過大近似と回避すべき集合が交わる場合、実際のリーチャブル集合が危険な状態と交わるかどうかは不明だからです。そのため、過大近似の精度と計算効率のバランスを取ることが重要になります。

これらの過大近似手法を組み合わせることで、非線形システムのリーチャビリティ解析を実行可能にします。線形システムのように完全に正確な結果は得られませんが、安全性の保証という観点からは十分に有用な結果を得ることができます。

3. 区間演算（インターバル算術）

3.1. 区間の基本概念

Sydney Katz：非線形システムのリーチャビリティ解析において、我々はポリトープを非線形関数に通すことが難しいという問題に直面しました。この問題に対する最初のアプローチとして、区間演算（インターバル算術）を導入します。

区間は、おそらく皆さんが想像する通りのものです。1次元の変数xに対する区間は、[x]と表記され、下限値x（アンダーラインで表記）と上限値x̄（オーバーラインで表記）によって定義されます。数学的に表現すると：

これは単純に、下限値x以上、上限値x̄以下のすべての実数の集合を表します。例えば、区間[1, 3]は、1以上3以下のすべての実数（1, 1.5, 2, 2.7, 3など）を含む集合です。

区間の基本的な考え方は、変数の正確な値ではなく、その値が取りうる範囲を表現することです。これにより、不確実性や変動を持つシステムを扱う際に、確定的な値ではなく範囲として変数を扱うことができます。

区間の重要な特徴として、それらは常に凸集合（具体的には1次元の場合は線分）であることが挙げられます。これにより、区間同士の演算や区間に関数を適用するなどの操作が比較的扱いやすくなります。

区間の表現は非常にコンパクトで、単に下限値と上限値の2つの数値だけで完全に定義されます。これは、多数の頂点を持つ可能性のあるポリトープよりも格段に効率的な表現です。後述しますが、この表現の簡潔さは、非線形システムのリーチャビリティ解析において大きな利点となります。

区間の概念は、後のセクションで紹介する区間ボックス（多次元区間）や、様々な演算の区間対応物の基礎となります。非線形システムのリーチャビリティ解析において区間演算がなぜ重要なのかというと、非線形関数を通した後の集合が複雑な形状になりうる中で、区間（あるいは多次元の場合は区間ボックス）という単純な形状で過大近似することで、計算を効率化できるからです。

区間の基本概念は単純ですが、これを基に構築される区間演算の体系は、非線形システムの解析において強力なツールとなります。

3.2. 区間ボックス（超矩形）

Sydney Katz：一次元の区間の概念を多次元空間に拡張すると、区間ボックス（interval box）または超矩形（hyperrectangle）という概念になります。区間ボックスは、複数の一次元区間のデカルト積（Cartesian product）として定義されます。

数学的には、n次元の区間ボックスは次のように表現されます：

ここで、[xᵢ]はi番目の次元に対応する一次元区間を表し、×はデカルト積を表します。表記としては、太字の変数を使用して[x]のように書きますが、これは一次元区間[x]と区別するために、xがベクトルであることを示しています。

視覚的に説明すると、二次元の場合、区間ボックスは二つの一次元区間[x₁]と[x₂]のデカルト積になります。例えば、[x₁] = [-1, 1]と[x₂] = [0, 2]のデカルト積は、x₁軸に沿って-1から1までの範囲、x₂軸に沿って0から2までの範囲の長方形領域になります。三次元では直方体、それ以上の次元では超矩形となります。

区間ボックスの重要な特性は、それが軸に平行な辺（または面、超平面）を持つということです。この特性により、区間ボックスは表現が非常に効率的で、2n個の数値（各次元の下限と上限）だけで完全に定義することができます。例えば、100次元の空間における任意の形状のポリトープを表現するには多数の頂点や面が必要ですが、区間ボックスなら200個の数値だけで表現できます。

この表現の効率性は、非線形システムのリーチャビリティ解析において大きな利点となります。非線形関数を通した結果の集合は複雑な形状になることが多いですが、それを区間ボックスで過大近似することで計算を大幅に簡略化できます。

ただし、区間ボックスの制約として、それが常に軸に平行であるため、斜めに伸びるような集合を密接に近似することが難しいという点があります。例えば、細長い楕円形の集合を区間ボックスで近似すると、多くの「無駄な」空間を含むことになります。この制約は、後ほど議論する過大近似の誤差に繋がります。

最後に用語の整理をしておくと、「区間ボックス」という用語は区間演算の文脈でよく使われますが、「超矩形」という用語も同じ概念を指します。また、二次元に限れば単に「長方形」、三次元では「直方体」と呼ぶこともあります。いずれにせよ、これらは数学的には同じ構造を持つ、軸に平行な箱状の形状を表しています。

3.3. 基本算術演算の区間対応物

Sydney Katz：これまで区間と区間ボックスの概念について説明しましたが、次はこれらの区間に対して基本的な算術演算をどのように定義するかを見ていきましょう。単一の数値ではなく区間に対して加減乗除などの演算を適用するとどうなるのか、そのルールを定義します。

まず、2つの区間の加算を考えてみましょう。区間[x]と区間[y]の和は、次のように定義されます：

つまり、一方の区間から任意の値xを取り、もう一方の区間から任意の値yを取って、それらを足し合わせたすべての可能な結果の集合が、区間の和となります。

具体例で説明すると、区間[-1, 1]と区間[2, 4]の和を考えてみましょう。この2つの区間からあらゆる組み合わせの値を取り出して足し合わせると、結果として得られる値は最小でも-1+2=1、最大でも1+4=5となります。したがって、[-1, 1] + [2, 4] = [1, 5]となります。

一般的な形で表すと、区間[x, x̄]と区間[y, ȳ]の加算は次のように計算されます： [x, x̄] + [y, ȳ] = [x + y, x̄ + ȳ]

つまり、下限同士を足して新しい下限を得、上限同士を足して新しい上限を得ます。この演算を「加算の区間対応物」と呼びます。

同様に、他の基本演算も区間に対して定義できます。例えば、減算の場合： [x, x̄] - [y, ȳ] = [x - ȳ, x̄ - y]

ここで注意すべき点は、減算では一方の区間の下限から他方の区間の上限を引き、一方の区間の上限から他方の区間の下限を引く点です。これは区間の定義から導かれる自然な結果です。

乗算と除算はやや複雑になります。乗算の場合： [x, x̄] × [y, ȳ] = [min(xy, xȳ, x̄y, x̄ȳ), max(xy, xȳ, x̄y, x̄ȳ)]

すなわち、境界点同士のすべての組み合わせの積を計算し、その中から最小値と最大値を選びます。区間が正の値のみ、または負の値のみを含む場合には、この式は簡略化できますが、区間がゼロをまたぐ場合には、すべての組み合わせをチェックする必要があります。

除算も同様に、境界点のすべての組み合わせをチェックする必要がありますが、除数の区間にゼロが含まれる場合は定義されません。これは実数において0による除算が定義されないのと同じ理由です。

これらの区間演算の定義は非常に自然で、プログラミング言語で容易に実装できます。実際、これらの演算は区間演算ライブラリの基本機能として提供されています。これにより、従来の数値計算アルゴリズムを簡単に「区間化」して、不確実性を持つシステムや範囲で表現された入力に対応させることができます。

3.4. 初等関数の区間対応物

Sydney Katz：基本的な算術演算（加減乗除）に加えて、指数関数、対数関数、三角関数などの初等関数にも区間対応物を定義することができます。これにより、区間演算の枠組みをより広範な関数に拡張できます。

一般的に、関数fに対する区間対応物は次のように定義されます：

f([x]) = {f(x) | x ∈ [x]}

つまり、区間[x]のすべての点xにfを適用したときの値の集合です。実用的には、この集合を包含する最も狭い区間が区間対応物となります。それを以下のように表記します：

f([x]) = [min{f(x) | x ∈ [x]}, max{f(x) | x ∈ [x]}]

具体例として、指数関数e^xを考えてみましょう。この関数は単調増加なので、区間[1, 2]に適用する場合、最小値はf(1) = e^1、最大値はf(2) = e^2となります。したがって、e^([1, 2]) = [e^1, e^2] ≈ [2.72, 7.39]となります。

単調増加または単調減少する関数の場合、区間対応物を計算するのは比較的簡単です。関数が区間上で単調増加なら、区間対応物は[f(x), f(x̄)]で与えられます。一方、関数が区間上で単調減少なら、区間対応物は[f(x̄), f(x)]となります。したがって、区間の端点における関数値だけを評価すれば十分です。

ただし、関数が区間内で単調でない場合、状況はより複雑になります。例えば、正弦関数や二次関数などは区間内で極値を持つことがあります。そのような場合、区間の端点だけでなく、その区間内の極値も考慮する必要があります。

具体例として、関数x²を区間[-1.5, 1]に適用する場合を考えましょう。単純に端点の値を計算すると、f(-1.5) = 2.25、f(1) = 1となりますが、これだけでは不十分です。なぜなら、この関数はx = 0で最小値f(0) = 0を持つからです。正しい区間対応物は[0, 2.25]となります。

図示すると、区間[-1.5, 1]に対してx²の区間対応物を求める場合：

1. x = -1.5での関数値：(-1.5)² = 2.25
2. x = 1での関数値：1² = 1
3. x = 0での関数値（極小値）：0² = 0 よって、x²([-1.5, 1]) = [0, 2.25]となります。

同様に、sin(x)のような三角関数の区間対応物を計算する場合も、区間内の極値を考慮する必要があります。例えば、sin([0, 4π])を計算する場合、単に端点の値だけでなく、区間内に存在する最大値1と最小値-1も考慮して、[-1, 1]という結果を得ます。

これらの初等関数の区間対応物の計算ルールは、数学的に導出され、区間演算ライブラリに実装されています。したがって、ユーザーは通常、これらの詳細を気にする必要はなく、標準的な関数を区間に適用するだけで、ライブラリが適切な区間対応物を計算してくれます。

初等関数の区間対応物の概念を理解することは、次に説明する包含関数の基礎となり、最終的には非線形システムのリーチャビリティ解析に応用されます。

3.5. IntervalArithmetic.jlパッケージ

Sydney Katz：これまで説明してきた区間演算の概念は、実際のプログラミングで実装する必要がありますが、幸いなことに、我々自身でこれらの機能をすべて実装する必要はありません。Julia言語には「IntervalArithmetic.jl」という優れたパッケージが存在し、これを使用することで区間演算を簡単に行うことができます。

IntervalArithmetic.jlパッケージは、区間の基本的な表現と操作に加えて、前節で説明した基本算術演算の区間対応物や初等関数の区間対応物をすべて実装しています。このパッケージを使うことで、通常のJuliaの関数（sin、exp、log、二乗など）を区間に対して直接適用することが可能になります。

例えば、以下のようなコードで区間に対して様々な操作を行うことができます：

using IntervalArithmetic

# 区間の定義
x = interval(-1, 1)  # [-1, 1]の区間
y = interval(2, 4)   # [2, 4]の区間

# 基本算術演算
z1 = x + y  # 結果は[1, 5]
z2 = x - y  # 結果は[-5, -1]
z3 = x * y  # 結果は[-4, 4]

# 初等関数の適用
z4 = sin(x)  # 結果は約[-0.84, 0.84]
z5 = exp(y)  # 結果は約[7.39, 54.6]
z6 = x^2     # 結果は[0, 1]

このパッケージの強力な点は、通常のJuliaの計算とシームレスに統合されることです。区間を含む複雑な式を記述すると、パッケージは適切な区間演算を適用して結果を計算します。これは、Juliaの多重ディスパッチ機能によって実現されています。

また、IntervalArithmetic.jlは、丸め誤差を考慮した厳密な計算を行います。つまり、計算結果の区間は、真の数学的結果を必ず含むことが保証されています。これは、浮動小数点演算の不確かさを考慮するため重要です。

さらに、IntervalArithmetic.jlは多次元の区間ボックスもサポートしています。これにより、複数の状態変数を持つシステムのリーチャビリティ解析が可能になります。

非線形システムのリーチャビリティ解析においては、このパッケージを使用することで、システムのダイナミクスを表す関数に区間を通すことができます。例えば、倒立振子システムのような非線形システムでも、状態変数と外乱を区間で表現し、それらを通常のシステム関数に通すだけで、次の状態の区間が計算できます。

以下のセクションでは、これらの区間演算の概念を拡張して、より複雑な非線形関数に対する包含関数や、より高精度なテイラー包含関数について説明していきます。しかし、基本的な区間演算の実装としては、IntervalArithmetic.jlのような既存のライブラリを活用することで、効率的に解析を進めることが可能です。

4. 包含関数（インクルージョン関数）

4.1. 包含関数の定義

Sydney Katz：区間演算の概念を理解したところで、次に「包含関数（インクルージョン関数）」について説明します。区間演算は単純な初等関数に対しては効果的ですが、より複雑な関数に対しては適用が難しくなります。例えば、倒立振子システムのような非線形システムのダイナミクスは、単純な初等関数の組み合わせで構成されており、そのまま区間演算を適用することは容易ではありません。

包含関数は、このような複雑な関数に対して区間演算の概念を拡張するものです。まず、関数の「区間対応物」を思い出してください。関数f(x)の区間対応物f([x])は、区間[x]の任意の点にfを適用したときの値の集合を包含する最も狭い区間として定義されました。

一方、「包含関数」fは、この区間対応物f([x])を包含することが保証された区間として定義されます。つまり：

f([x]) ⊆ f

ここで重要なのは、包含関数は必ずしも最も狭い区間ではなく、区間対応物よりも広い（過大近似される）可能性があるという点です。区間対応物が正確な範囲を表す「厳密な境界」であるのに対し、包含関数は「保証された境界」を提供します。

包含関数と区間対応物を区別するため、包含関数は関数名fの周りに括弧を付けて[f]のように表記します。例えば、sin関数の包含関数は[sin]と表記します。

視覚的に説明すると、ある関数f(x)の区間対応物f([x])が実際にはf(x)のとりうる値の範囲（最小値から最大値まで）を表すのに対し、包含関数fはこの範囲を包含するより広い区間になります。

なぜ包含関数が必要なのでしょうか？それは、多くの複雑な関数に対して、正確な区間対応物を計算することが難しいか不可能な場合があるからです。そのような場合でも、真の範囲を過大近似する包含関数なら比較的容易に計算できることが多いです。また、計算効率と精度のトレードオフを考慮する際、厳密な境界を求めるより、保証された（ただし過大近似された）境界を効率的に計算する方が実用的な場合もあります。

包含関数の重要な性質は、それが常に真の関数値の範囲を包含することを数学的に保証できる点です。これは、非線形システムのリーチャビリティ解析において、安全性の保証を維持しながら計算効率を向上させるために不可欠な性質です。

次のセクションでは、区間対応物と包含関数の関係についてより詳しく説明し、その後、リーチャビリティ関数に包含関数を適用する方法について解説します。

4.2. 区間対応物と包含関数の関係

Sydney Katz：区間対応物と包含関数の関係をより深く理解するために、両者の違いと関連性について詳しく説明します。

区間対応物f([x])は、関数fを区間[x]上のすべての点に適用したときの結果の集合を表す最も狭い区間です。数学的に表現すると：

f([x]) = [{f(x) | x ∈ [x]}]

ここで、外側の括弧は、結果の集合を包含する最も狭い区間を表します。区間対応物は理論的に「最適」な結果であり、過大近似や過小近似は存在しません。

一方、包含関数fは、区間対応物f([x])を必ず含む区間です：

f([x]) ⊆ f

包含関数は、区間対応物よりも広い区間である可能性がありますが、それでも真の関数値の範囲を確実に包含します。このような関係を「保守的」あるいは「健全（sound）」と表現することもあります。

区間対応物と包含関数の関係を具体例で説明しましょう。関数f(x) = x - sin(x)を区間[0, π]に適用することを考えます。正確な区間対応物を求めるには、この関数の最小値と最大値を特定する必要があります。この関数は0からπまでの範囲で単調増加ではないため、単純に端点の値だけを見るだけでは不十分です。

厳密に計算すると、f([0, π]) = [0, π-sin(π)] = [0, π] となります（sinの値が0からπの範囲で-1から1に変化することを考慮）。しかし、このような計算は一般的な関数では難しい場合があります。

これに対し、包含関数のアプローチでは、例えば「自然包含関数」という手法を用いると：

f = [0, π] - sin = [0, π] - [-1, 1] = [0, π] - [-1, 1] = [-1, π+1]

この結果は真の範囲[0, π]よりも広くなっていますが、確実に真の範囲を含んでいます。

区間対応物と包含関数の関係において重要な点は、以下のとおりです：

1. 区間対応物は理論的に最適ですが、多くの複雑な関数では計算が困難です。
2. 包含関数は計算が容易である場合が多く、実用的なアプローチを提供します。
3. 包含関数は常に区間対応物を含み、したがって真の関数値の範囲も含みます。
4. 包含関数の計算精度を上げると、区間対応物により近づけることができますが、計算コストが増加します。

リーチャビリティ解析の文脈では、区間対応物の正確な計算が難しい場合でも、包含関数を用いることで保証された境界を効率的に計算できるという利点があります。次のセクションでは、この概念をリーチャビリティ関数に適用する方法について説明します。

4.3. リーチャビリティ関数への適用

Sydney Katz：包含関数の概念をリーチャビリティ解析に適用するために、まずリーチャビリティ関数を確認し、それに包含関数をどのように適用するかを説明します。

非線形システムのリーチャビリティ解析の目標は、前回の講義と同様に、深さdでのリーチャブル集合R_dを計算することです。これは以下のように定義されます：

R_d = {s_d | s_d = reach(s_0, w_0, ..., w_{d-1}), s_0 ∈ S_0, w_t ∈ W_t for t = 0, ..., d-1}

ここで、s_dは深さdでの状態、reach関数はシステムのロールアウト関数（ある初期状態とディスターバンスの列から、d時間ステップ後の状態を計算する関数）、S_0は初期状態の集合、W_tは時間tでのディスターバンスの集合です。

前回の講義では、reach関数が線形だったため、ポリトープをそのまま伝播させることができました。しかし、今回は非線形関数を扱うため、そのアプローチは適用できません。

そこで、この講義ではreach関数をrと単純化して表記し、さらにこの関数を複数の出力コンポーネントに分解します。システムの状態がn次元である場合、r関数をn個の関数r_1, r_2, ..., r_nに分解します。ここで、r_i(s_0, w_0, ..., w_{d-1})は深さdでのi番目の状態変数の値を出力します。

例えば、倒立振子システムでは状態はθ（角度）とω（角速度）の2つの変数からなりますので、r_1は深さdでのθの値を、r_2は深さdでのωの値を出力します。

この分解により、各関数r_iに対して包含関数を定義できるようになります。つまり、初期状態S_0とディスターバンスW_0, ..., W_{d-1}を区間（または区間ボックス）として表現し、各r_i関数に対する包含関数[r_i]を計算します：

r_i

この計算の結果、i番目の状態変数が取りうる値の区間が得られます。そして、すべてのi = 1, ..., nについてこの計算を行い、結果の区間のデカルト積を取ることで、深さdでのリーチャブル集合の超矩形（ハイパーレクタングル）による過大近似が得られます。

つまり、リーチャブル集合R_dの過大近似R̄_dは次のように計算されます：

R̄d = [r_1]([s_0], [w_0], ..., [w{d-1}]) × ... × r_n

ここで×はデカルト積を表します。

この方法の限界として、得られるリーチャブル集合の過大近似は常に超矩形（区間ボックス）の形状に制限されるという点があります。実際のリーチャブル集合がより複雑な形状である場合、超矩形による近似は大きな過大近似誤差をもたらす可能性があります。しかし、実装が比較的容易であり、非線形システムに対するリーチャビリティ解析の出発点として適しています。

次のセクションでは、包含関数を構築するための具体的な方法、特に「自然包含関数」について説明します。

5. 自然包含関数

5.1. 自然包含関数の定義

Sydney Katz：包含関数を構築するための最も直感的な方法として、「自然包含関数」というアプローチがあります。この方法は、複合関数の各要素を区間対応物で置き換えるという単純な原理に基づいています。

自然包含関数の定義を説明するために、具体例を考えてみましょう。関数f(x) = x - sin(x)を考えます。この関数は、恒等関数（identity function）x、正弦関数sin(x)、および減算演算子から構成されています。自然包含関数は、これらの各要素を対応する区間演算で置き換えることで構成されます：

[f]_N([x]) = [x] - sin

ここで[f]_Nは関数fの自然包含関数を表し、添え字Nはnatural（自然）を意味します。[x]は区間としての入力を表し、[sin]は正弦関数の区間対応物を表します。この式は、区間[x]に恒等演算を適用し、同じ区間[x]に正弦関数の区間対応物を適用した後、それらの結果の区間同士の減算を行うことを意味します。

一般的に、関数がp個の基本演算子や初等関数φ1, φ2, ..., φ_pの合成として表現できる場合：

f(x) = φp(... φ2(φ_1(x)))

自然包含関数は以下のように定義されます：

[f]N([x]) = [φp]N(... [φ2]N([φ1]_N([x])))

要するに、各基本演算子や初等関数をその区間対応物で置き換え、同じ順序で合成するというアプローチです。

自然包含関数の主要な利点は、その定義が非常に直感的で、実装が容易である点です。特に、すでに基本演算や初等関数の区間対応物が実装されているIntervalArithmetic.jlのようなライブラリを使用すれば、ほとんど追加作業なしに自然包含関数を構築できます。

例えば、Juliaコードでは以下のように記述できます：

function f(x)
    return x - sin(x)
end

# 通常の関数を区間入力で呼び出すだけで自然包含関数として機能する
natural_inclusion_result = f(interval(0, π))

IntervalArithmetic.jlの多重ディスパッチ機能により、区間入力を渡すだけで自動的に対応する区間演算が適用されます。

しかし、自然包含関数にはいくつかの限界があります。特に、元の関数内で同じ変数が複数回現れる場合、自然包含関数は過大な近似を行う傾向があります。これは「依存効果」と呼ばれる問題であり、次のセクションで詳しく説明します。

5.2. 依存効果（dependency effect）の問題

Sydney Katz：自然包含関数の最大の欠点は「依存効果（dependency effect）」と呼ばれる問題です。これは、元の関数内で同じ変数が複数回出現する場合に、変数間の依存関係が失われることで過大な近似が発生する現象です。

依存効果を理解するために、例として関数f(x) = x - sin(x)を考えましょう。この関数では変数xが2回登場しています：一度は恒等関数の中、もう一度は正弦関数の引数としてです。実際の関数評価においては、両方の場所に同じ値xが使用されます。

ところが、自然包含関数では、区間[x]を関数の各部分に独立に代入します：

[f]_N([x]) = [x] - sin

ここで問題が発生します。区間[x]の中の異なる値が、関数の異なる部分で独立に選択されるかのように計算が行われるのです。例えば、[x] = [0, π]の場合、自然包含関数の計算過程では、減算の左辺にある[x]からの値と、正弦関数に入力される[x]からの値が、同一である必要がないかのように扱われます。

具体的に計算すると：

1. sin = sin = [-1, 1]（区間[0, π]上での正弦関数の値の範囲）
2. [f]_N([x]) = - sin = [0, π] - [-1, 1] = [-1, π+1]

しかし、実際の関数f(x) = x - sin(x)の[0, π]上での真の値域を厳密に計算すると（x = 0のとき0、x = πのときπ、その間で単調とは限らない）、結果は[0, π]となります。自然包含関数の結果[-1, π+1]は、真の値域を大幅に過大評価しています。

この過大近似は、各変数の出現を独立に扱うことで生じます。実際には、xの特定の値（例えば0）に対しては、sin(x)も特定の値（sin(0) = 0）をとりますが、自然包含関数の計算では、xが0であっても、sin(x)は[-1, 1]の任意の値をとりうると想定しています。これが依存効果の本質です。

教科書の例8.2でより詳細に説明されていますが、依存効果の問題は、一般に以下のような状況で特に顕著になります：

1. 同じ変数が複数回出現する関数（例：x²、x - sin(x)など）
2. 関数がキャンセレーション（相殺）を含む場合（例：x - xなど）
3. 区間の幅が広い場合（狭い区間では影響が小さくなる傾向がある）

依存効果は、自然包含関数が直感的で実装が容易である一方、その正確性に大きな制約をもたらします。次のセクションでは、実際の非線形システムのリーチャビリティ解析において、自然包含関数を用いた場合にどのような過大近似が生じるかを見ていきます。

5.3. 過大近似の増加

Sydney Katz：自然包含関数の依存効果による過大近似は、非線形システムのリーチャビリティ解析においてさらに深刻な問題となります。特に、時間ステップが増えるにつれて過大近似が累積的に増大する傾向があります。

この問題を具体的に示すために、倒立振子システムを例に考えてみましょう。倒立振子は2つの状態変数（角度θと角速度ω）を持つ非線形システムです。このシステムのダイナミクスは次のように表されます：

θnext = θ + Δt・ω ωnext = ω + Δt・(g/l・sin(θ) + 1/m・l²・u)

ここで特に注目すべきは、sin(θ)の項による非線形性です。時間ステップを重ねるごとに、この非線形項が繰り返し適用され、計算には前のステップの結果が使われます。そのため、1ステップ目での過大近似が2ステップ目の入力となり、2ステップ目ではさらに過大近似が加わります。

実際にコードで実装すると、IntervalArithmetic.jlを使って区間を自然に関数に渡すことができます。倒立振子システムのロールアウト関数を実装し、初期状態と各ステップのディスターバンスを区間として表現して、この関数に通すだけです。

図で示すと、倒立振子システムの自然包含関数による過大近似の累積は次のようになります：

1. 初期ステップでは、比較的正確な近似が得られます
2. 2ステップ目では、過大近似がすでに顕著になり始めます
3. 3ステップ目では、過大近似が非常に大きくなり、結果の境界が画面から外れてしまうほどです

この現象の原因は、各時間ステップで発生する依存効果による過大近似が、次のステップの入力となって計算されるためです。また、時間が経つにつれて、非線形項の影響がより複雑になることも原因の一つです。例えば、1ステップ目ではsin(θ)だけが非線形項ですが、2ステップ目では前の結果に再びsin関数が適用されるため、sin(θ + Δt・ω)のように「非線形関数の非線形関数」となり、複雑さが増します。

このような過大近似の累積により、わずか数ステップ後には、リーチャブル集合の近似が非常に広くなり、回避すべき集合と交わってしまう可能性が高くなります。その場合、システムが実際には安全であっても、「結論が出せない（inconclusive）」という結果になってしまいます。

倒立振子の例では、サンプル点（モンテカルロシミュレーションによる軌跡の集合）を見ると、実際のリーチャブル集合はまだ回避すべき集合と交わっていないようですが、自然包含関数による過大近似は回避すべき集合と交わってしまっています。

このように、自然包含関数は実装が容易である反面、過大近似が大きくなりすぎるという欠点があります。特に多数の時間ステップを計算する必要がある場合には、より精度の高い包含関数が必要となります。次のセクションでは、平均値定理を用いた「平均値包含関数」という、より精度の高い方法を紹介します。

6. 平均値包含関数

6.1. 平均値定理の応用

Sydney Katz：自然包含関数の過大近似の問題に対処するため、より精度の高い包含関数を構築する方法として、微積分学の「平均値定理」を応用したアプローチを紹介します。多くの人は高校や大学の微積分学でこの定理を学びましたが、実際の応用例を見る機会は少なかったかもしれません。

まず、平均値定理を復習しましょう。関数f(x)が区間[a, b]上で連続微分可能であるとき、次のような点cが区間(a, b)内に少なくとも1つ存在します：

f(b) - f(a) = f'(c)(b - a)

この定理は、区間の端点間の平均変化率（割線の傾き）が、区間内のある点における瞬間変化率（接線の傾き）に等しいことを示しています。

視覚的に説明すると、関数のグラフ上で点(a, f(a))と点(b, f(b))を結ぶ直線（割線）があります。平均値定理は、この割線と平行な接線が区間内のどこかに存在すると言っています。つまり、割線の傾きと同じ傾きを持つ接線が区間内に必ず存在します。

このシンプルな定理を応用して、より精度の高い包含関数を構築します。まず、区間[x, x̄]の中点cを考えます：

c = (x + x̄)/2

次に、区間内の任意の点xを選び、区間[x, c]に平均値定理を適用します。ある点x'∈[x, c]に対して：

f(x) - f(c) = f'(x')(x - c)

ここでx'は[x, c]内の点ですが、より大きな区間[x, x̄]にも含まれることに注意してください。

この関係を変形すると：

f(x) = f(c) + f'(x')(x - c)

この式は、区間[x, x̄]内の任意の点xに対して成り立ちます。つまり、関数f(x)の値は、中点cでの関数値f(c)と、区間内のある点x'での導関数f'(x')を用いて表現できるということです。

ここで重要なのは、x'が区間[x, x̄]内のどこかに存在することはわかっているものの、具体的にどの点なのかは不明である点です。しかし、x'∈[x, x̄]であることを利用して、f'(x')の取りうる値の範囲を包含関数f'で表現できます。

これにより、平均値定理を使った包含関数が定式化されます。このアプローチが、次のセクションで詳しく説明する「平均値包含関数」の基礎となります。

このように、単純な微積分学の定理を応用することで、自然包含関数よりも精度の高い包含関数を構築できるのです。平均値定理の優れた点は、関数の局所的な振る舞いを利用して、区間全体での振る舞いを特徴づけられることです。

6.2. 平均値包含関数の導出

Sydney Katz：前節で説明した平均値定理の応用を基に、平均値包含関数の具体的な導出過程を説明します。

平均値定理から導いた式を再度確認しましょう：

f(x) = f(c) + f'(x')(x - c)

ここでcは区間[x, x̄]の中点、x'は区間内のどこかの点です。この式を区間演算に拡張することで、平均値包含関数を導出します。

まず、xが区間[x, x̄]内の任意の点であることを考慮すると、(x - c)は区間[x - c, x̄ - c]のいずれかの値を取ります。また、x'は区間[x, x̄]内の点であるため、f'(x')は区間f'内の値を取ります。ここで[f']は関数f'の包含関数です。

これらの関係を用いて、平均値包含関数[f]_MVを次のように定義します：

[f]_MV([x, x̄]) = f(c) + f'・([x, x̄] - c)

ここで添え字MVは「Mean Value（平均値）」を表します。右辺の最初の項f(c)は区間の中点cにおける関数値で、これは単一の点なので通常の関数評価で計算できます。第二項は、f'の包含関数と区間[x, x̄]とcの差の積です。

この式を分解して考えると：

1. f(c)は中点での関数値（単一の数値）
2. f'はf'の包含関数を区間[x, x̄]に適用した結果（区間）
3. [x, x̄] - cは元の区間と中点の差（区間[x - c, x̄ - c]）
4. これらの積と和を計算して最終的な区間を得る

平均値包含関数の重要な性質は、f(c)が単一の数値として正確に計算されることです。これにより、中点での関数値は過大近似されません。また、関数の導関数を用いることで、関数の局所的な振る舞いを考慮に入れた近似が可能になります。

多次元の場合、平均値包含関数は以下のように一般化されます：

[f]_MV([x]) = f(c) + ∇f・([x] - c)

ここで∇[f]はfの勾配の包含関数を表し、・はドット積を表します。

平均値包含関数の導出において重要なのは、平均値定理を用いることで関数の振る舞いをより正確に捉えられる点です。自然包含関数では同じ変数の複数回の出現が独立に扱われることによる依存効果が問題でしたが、平均値包含関数では関数を一次近似することでこの問題を緩和できます。

また、平均値包含関数は、実際には関数の一次（線形）テイラー展開に基づいているとも解釈できます。f(c)は定数項、f'(x')(x - c)は一次項に対応します。この解釈は後に説明するテイラー包含関数への橋渡しとなります。

次のセクションでは、この平均値包含関数と自然包含関数の精度を比較し、実際にどの程度改善されるかを見ていきます。

6.3. 自然包含関数との比較実験

Sydney Katz：自然包含関数と平均値包含関数の精度の違いを具体的に理解するために、実際の比較実験を行いました。例として、関数f(x) = x - sin(x)を取り上げ、区間[-1, 1]に対する両方の包含関数の結果を比較します。

まずは自然包含関数による計算です：

[f]_N([-1, 1]) = [-1, 1] - sin

ここでsinを計算する必要があります。区間[-1, 1]における正弦関数の値域を考えると、sin(-1) ≈ -0.84、sin(0) = 0、sin(1) ≈ 0.84であり、この区間でsinは単調ではないため、最小値と最大値を考慮するとsin = [-0.84, 0.84]となります。

これを元の式に代入すると： [f]_N([-1, 1]) = [-1, 1] - [-0.84, 0.84] = [-1, 1] - [-0.84, 0.84] = [-1.84, 1.84]

次に平均値包含関数による計算です。区間[-1, 1]の中点はc = 0です：

[f]_MV([-1, 1]) = f(0) + f'・([-1, 1] - 0)

ここでf(0) = 0 - sin(0) = 0、また導関数はf'(x) = 1 - cos(x)です。区間[-1, 1]における余弦関数の値域を考えると、cos(-1) ≈ 0.54、cos(0) = 1、cos(1) ≈ 0.54となり、この区間ではcos(x)の最小値は約0.54、最大値は1です。したがって：

f' = 1 - cos = 1 - [0.54, 1] = [0, 0.46]

これをもとの式に代入すると： [f]_MV([-1, 1]) = 0 + [0, 0.46]・[-1, 1]

区間[0, 0.46]と区間[-1, 1]の積を計算するには、それぞれの端点の積の中から最小値と最大値を選ぶ必要があります： [0, 0.46]・[-1, 1] = [min(0・(-1), 0・1, 0.46・(-1), 0.46・1), max(0・(-1), 0・1, 0.46・(-1), 0.46・1)] = [min(0, 0, -0.46, 0.46), max(0, 0, -0.46, 0.46)] = [-0.46, 0.46]

したがって、[f]_MV([-1, 1]) = 0 + [-0.46, 0.46] = [-0.46, 0.46]となります。

実際の関数f(x) = x - sin(x)の区間[-1, 1]における厳密な値域を数値的に計算するとほぼ[-0.3, 0.3]程度なので、平均値包含関数の結果[-0.46, 0.46]は厳密な値域に近い結果を与えていることがわかります。一方、自然包含関数の結果[-1.84, 1.84]は大きく過大近似しています。

グラフで視覚化すると、この差はさらに明確になります。関数f(x) = x - sin(x)のグラフと、両方の包含関数の結果を横軸に区間[-1, 1]、縦軸に関数値として表示すると、自然包含関数は実際の関数値の範囲を大幅に過大評価しているのに対し、平均値包含関数は関数の実際の変動範囲にはるかに近い結果を与えています。

さらに、この改善は倒立振子のようなより複雑なシステムでも観察できます。自然包含関数を用いた場合、時間ステップが増えるにつれて過大近似が急速に増大し、わずか数ステップで結果が使い物にならなくなってしまいます。一方、平均値包含関数を用いると、より多くの時間ステップにわたって有用な結果が得られます。

この実験結果から、平均値包含関数は自然包含関数と比較して大幅に精度が改善されることが明確になりました。特に、依存効果が問題となるケース（同じ変数が複数回出現する関数など）で顕著な改善が見られます。

6.4. 多次元への一般化

Sydney Katz：これまでは一次元の関数に対する平均値包含関数について説明してきましたが、実際のシステムは通常、複数の状態変数を持つ多次元の場合が一般的です。ここでは、平均値包含関数を多次元のケースに一般化する方法を説明します。

多次元の場合、一変数関数の導関数は多変数関数の勾配（gradient）に置き換えられます。n次元のベクトル値関数f: ℝⁿ → ℝᵐに対して、平均値定理の多次元版は次のように表されます：

f(x) - f(c) = ∇f(ξ)(x - c)

ここで、cは区間ボックス[x]の中点、ξは区間ボックス内のある点（具体的にどの点かは不明）、∇f(ξ)はその点における関数のヤコビアン行列（Jacobian matrix）です。この式は、区間ボックス内の任意の点xに対して成り立ちます。

この関係を変形すると：

f(x) = f(c) + ∇f(ξ)(x - c)

この式を基に、多次元の平均値包含関数は次のように定式化されます：

[f]_MV([x]) = f(c) + ∇f([x] - c)

ここで∇fは関数のヤコビアン行列の包含関数を区間ボックス[x]に適用した結果で、区間行列になります。([x] - c)は元の区間ボックスと中点の差を表す区間ベクトルです。

具体的な例として、2次元の倒立振子システムを考えてみましょう。状態変数はθ（角度）とω（角速度）の2つです。まず、リーチャビリティ関数rを2つのコンポーネント関数r₁（θに対応）とr₂（ωに対応）に分解します。

r₁に対する平均値包含関数は：

[r₁]MV([s₀], [w₀], ..., [w{d-1}]) = r₁(c) + ∇r₁・([s₀] - c₁, [w₀] - c₂, ..., [w_{d-1}] - c_d)

ここでcは([s₀], [w₀], ..., [w_{d-1}])の中点ベクトル、[∇r₁]はr₁の勾配の包含関数です。同様にr₂に対する平均値包含関数も計算できます。

多次元の平均値包含関数の計算は、一次元の場合と比べて技術的に複雑になりますが、基本的な原理は同じです。中点での関数値を正確に計算し、関数の局所的な変化率（勾配）を用いて区間全体での変動を近似します。

Juliaでの実装の観点からは、関数の勾配を計算するために自動微分（automatic differentiation）のツールが使用されます。IntervalArithmetic.jlと組み合わせることで、区間ボックスを通じて勾配を計算できます。これはJuliaの多重ディスパッチ機能のおかげで非常にシームレスに行えます。

実践的な観点からは、多次元平均値包含関数は依然として各状態変数ごとに区間を計算し、それらのデカルト積を取ることで最終的なリーチャブル集合の過大近似を得ます。これは、出力が超矩形（区間ボックス）に制限されることを意味します。しかし、その精度は自然包含関数よりもはるかに優れており、より多くの時間ステップにわたって有用な結果を提供します。

多次元への一般化により、平均値包含関数は実際のシステムのリーチャビリティ解析に実用的に適用できるようになります。次のセクションでは、この平均値包含関数をさらに一般化し、より高次のテイラー展開に基づく「テイラー包含関数」について説明します。

7. テイラー包含関数

7.1. テイラー級数の応用

Sydney Katz：前節で説明した平均値包含関数は、実は一次のテイラー展開に基づいていることがわかります。平均値包含関数の式：

f(x) = f(c) + f'(ξ)(x - c)

は、中点cでの関数値f(c)と一次微分を使った線形近似そのものです。これは、一次のテイラー展開に他なりません。

この洞察から、平均値包含関数をより一般化し、高次のテイラー展開に基づく「テイラー包含関数」を構築することができます。テイラー級数は関数をより高い精度で近似するために使われる強力なツールです。n次のテイラー展開は以下のように表されます：

f(x) = f(c) + f'(c)(x - c) + (f''(c)/2!)(x - c)² + ... + (f^(n)(c)/n!)(x - c)^n + R_n(x)

ここでR_n(x)は剰余項（remainder term）で、テイラー展開の打ち切りによる誤差を表します。

テイラー包含関数の基本的なアイデアは、このテイラー展開の各項を対応する区間演算で置き換え、さらに剰余項に対しても包含関数を見つけることです。n次のテイラー包含関数は次のように定義されます：

[f]_T^n([x]) = f(c) + f'(c)([x] - c) + (f''(c)/2!)([x] - c)² + ... + (f^(n)(c)/n!)([x] - c)^n + R_n

ここでR_nは剰余項R_n(x)の包含関数です。

具体的な例として、二次（n=2）のテイラー包含関数を考えてみましょう：

[f]_T^2([x]) = f(c) + f'(c)([x] - c) + (f''(c)/2)([x] - c)² + R_2

この式では、関数f、その一次導関数f'、および二次導関数f''を中点cで評価し、区間([x] - c)の適切なべき乗と組み合わせます。剰余項R_2は、ラグランジュ形式またはテイラーの定理の一般形を用いて導出できます。

テイラー包含関数の大きな利点は、テイラー級数の次数を上げることで、理論的には任意の精度を達成できる点です。自然包含関数と平均値包含関数は、テイラー包含関数の特殊なケースと見なせます：

• 0次テイラー包含関数（n=0）は、実質的に自然包含関数に相当します
• 1次テイラー包含関数（n=1）は、平均値包含関数に相当します

テイラー包含関数は、関数の局所的な振る舞いをより高次の導関数まで考慮することで、より正確な近似を提供します。特に、関数が高次の非線形性を持つ場合、より高次のテイラー包含関数が有効です。

ただし、次数が上がるにつれて計算コストも増加するため、実際のアプリケーションでは次数とコストのバランスを考慮する必要があります。次のセクションでは、異なる次数のテイラー包含関数の特性と、それらを構築する具体的な方法について詳しく説明します。

7.2. 高次テイラー包含関数

Sydney Katz：テイラー包含関数の枠組みを拡張して、より高次の導関数を活用することで、関数の近似精度をさらに向上させることができます。ここでは、2次以上のテイラー包含関数の構成方法と特性について説明します。

n次のテイラー包含関数は以下のように定式化されます：

[f]_T^n([x]) = T_n(c) + R_n

ここでT_n(c)はテイラー多項式：

T_n(c) = f(c) + f'(c)([x] - c) + (f''(c)/2!)([x] - c)² + ... + (f^(n)(c)/n!)([x] - c)^n

そしてR_nは剰余項の包含関数です。

例えば、2次のテイラー包含関数の場合：

[f]_T^2([x]) = f(c) + f'(c)([x] - c) + (f''(c)/2)([x] - c)² + R_2

剰余項R_2は、通常ラグランジュ形式で表されます：

R_2(x) = (f'''(ξ)/3!)(x - c)³

ここでξは区間[x, x̄]内の未知の点です。これを区間演算に拡張すると：

R_2 = (f'''/6)([x] - c)³

同様に、3次のテイラー包含関数では：

[f]_T^3([x]) = f(c) + f'(c)([x] - c) + (f''(c)/2)([x] - c)² + (f'''(c)/6)([x] - c)³ + R_3

剰余項は：

R_3 = (f^(4)/24)([x] - c)⁴

一般に、より高次のテイラー包含関数は、以下の特性を持ちます：

1. 近似精度：次数が高いほど、区間が狭い場合や関数が滑らかな場合には、より精密な近似が得られます
2. 計算コスト：次数が高いほど、より多くの導関数を計算し、より複雑な区間演算を実行する必要があります
3. 収束性：区間の幅が小さくなるにつれて、テイラー包含関数の結果は真の関数値の範囲に漸近的に近づきます

実際のコード実装では、高次の導関数を効率的に計算するために自動微分が使用されます。Juliaでは、これらの導関数の計算と区間演算をシームレスに組み合わせることができます。例えば、2次のテイラー包含関数のコードは以下のようになります：

function taylor_inclusion_order2(f, interval)
    c = mid(interval)  # 区間の中点
    f_c = f(c)         # 中点での関数値
    f_prime_c = derivative(f, c)  # 一次導関数
    f_double_prime_c = second_derivative(f, c)  # 二次導関数

    # テイラー多項式の計算
    taylor_poly = f_c + f_prime_c * (interval - c) +
                  (f_double_prime_c/2) * (interval - c)^2

    # 剰余項の計算
    f_triple_prime = x -> third_derivative(f, x)
    remainder = (inclusion_function(f_triple_prime, interval)/6) *
                (interval - c)^3

    return taylor_poly + remainder
end

ただし、次数が高ければ常に良い結果が得られるわけではありません。区間が広い場合や、関数が非常に非線形性が強い場合、高次の導関数自体が大きな変動を示し、結果として剰余項の過大近似が大きくなることがあります。

したがって、適切なテイラー包含関数の次数は、問題の性質、求められる精度、計算リソースなどを考慮して選択する必要があります。実際のアプリケーションでは、異なる次数のテイラー包含関数を実験的に比較し、最も効率的な次数を選ぶことが一般的です。

次のセクションでは、異なる次数のテイラー包含関数の実験的な比較結果と、その効果について説明します。

7.3. テイラー次数の効果に関する実験結果

Sydney Katz：異なる次数のテイラー包含関数の精度と効率を比較するため、いくつかの実験を行いました。ここでは、関数f(x) = x - sin(x)を例に、異なる次数のテイラー包含関数の効果を分析します。

まず、区間[-1, 1]に対する0次から3次までのテイラー包含関数の結果を比較しました：

• 0次（自然包含関数）：[-1.84, 1.84]
• 1次（平均値包含関数）：[-0.46, 0.46]
• 2次：[-0.41, 0.41]
• 3次：[-0.30, 0.30]

関数f(x) = x - sin(x)の[-1, 1]における実際の値域は約[-0.3, 0.3]であるため、3次のテイラー包含関数がほぼ正確な結果を与えていることがわかります。この結果から、次数が上がるにつれて精度が向上していることが明らかです。特に、0次から1次への改善が最も顕著であり、2次以降の改善は比較的小さいことが観察されます。

また、区間の幅がテイラー包含関数の精度に与える影響も調査しました。より広い区間[-2, 2]に対する結果は以下の通りです：

• 0次（自然包含関数）：[-3, 3]
• 1次（平均値包含関数）：[-1.7, 1.7]
• 2次：[-1.2, 1.2]
• 3次：[-1.0, 1.0]

区間が広がると、すべての次数で精度が低下しますが、高次のテイラー包含関数ほど精度の低下は小さい傾向があります。これは、高次の導関数が関数の非線形性をより正確に捉えているためです。

一方、関数の性質によっては、次数を上げることの効果が限定的な場合もあります。例えば、非線形性が強い関数や、区間内で導関数が大きく変動する関数では、高次のテイラー包含関数を用いても、剰余項の過大近似が大きくなり、全体の精度改善が小さくなることがあります。

実際のシステム、特に倒立振子のような非線形システムでも同様の実験を行いました。時間の経過とともにどのようにリーチャブル集合の近似が変化するかを観察しました：

1. 自然包含関数（0次）：数ステップ後には過大近似が非常に大きくなり、結果が使い物にならなくなります
2. 平均値包含関数（1次）：より多くのステップで合理的な結果を維持しますが、最終的には過大近似が大きくなります
3. 2次のテイラー包含関数：1次よりもわずかに改善されますが、この特定の問題では劇的な違いは見られませんでした

興味深いことに、倒立振子システムでは、1次から2次への改善は小さく、計算コストの増加を考えると、ほとんどの場合1次（平均値包含関数）が最も効率的な選択であることがわかりました。

また、時間ステップが増加するにつれて、どの次数のテイラー包含関数でも過大近似が累積していく傾向が観察されました。これは、各ステップで生じる非線形性が複合的に増加し、後のステップでより複雑な関数になるためです。例えば、最初のステップではsin(θ)という単純な非線形項だけが含まれていますが、次のステップではsin(θ + Δt・ω)のように、前のステップの結果に再び非線形関数が適用されます。

これらの実験結果から、以下の実用的な知見が得られました：

1. 0次から1次への改善が最も顕著で、多くの場合、平均値包含関数（1次）が計算コストと精度のバランスの点で最適です
2. 特定の問題や関数によっては、高次のテイラー包含関数が有意な改善をもたらす場合があります
3. 区間の幅が狭い場合、より高次のテイラー包含関数がより効果的です
4. 時間ステップが増えるにつれて、どの次数でも過大近似が累積する問題は残ります

最後に、これらの実験結果は、特定の関数やシステムに依存することを強調しておきます。実際のアプリケーションでは、問題に合わせて適切な次数を選択することが重要です。

7.4. ジュリア言語での実装の利点

Sydney Katz：テイラー包含関数の実装において、Julia言語は驚くほど強力かつ柔軟な環境を提供しています。この節では、Julia言語がどのようにして非線形システムのリーチャビリティ解析、特にテイラー包含関数の実装を容易にするかを説明します。

まず、Juliaの最も印象的な特徴の一つが、多重ディスパッチ（multiple dispatch）機能です。これにより、同じ関数名でも引数の型によって異なる実装を呼び出すことができます。区間演算の文脈では、この機能が非常に強力です。例えば、通常の数値用に定義された関数に区間を渡すと、Juliaは自動的に区間に対応した実装を呼び出します。

function f(x)
    return x - sin(x)
end

# 通常の数値に対する評価
result1 = f(0.5)  # 単一の数値を返す

# 区間に対する評価（多重ディスパッチにより自動的に区間演算が適用される）
using IntervalArithmetic
result2 = f(interval(-1, 1))  # 区間を返す

上記のコードでは、同じ関数fを定義していますが、区間を引数として渡すと、Juliaは自動的に対応する区間演算を適用します。これは、基本的な算術演算子や標準関数（sin、cosなど）が区間に対して多重ディスパッチで定義されているためです。

さらに驚くべき点は、Juliaが微分演算と区間演算を組み合わせる能力です。テイラー包含関数の実装では、関数の導関数を計算し、それを区間に適用する必要があります。Juliaでは、自動微分（automatic differentiation）と区間演算を組み合わせることができます：

using ForwardDiff  # 自動微分のためのパッケージ

function taylor_inclusion_order1(f, interval)
    c = mid(interval)
    f_c = f(c)

    # 関数fの導関数を計算し、それを区間に適用
    gradient_f = x -> ForwardDiff.derivative(f, x)
    return f_c + gradient_f(interval) * (interval - c)
end

このコードは、平均値包含関数（1次のテイラー包含関数）を実装しています。ForwardDiff.derivativeを使って関数fの導関数を計算し、その導関数に区間を直接渡しています。多くの言語ではこのような操作が難しいか不可能ですが、Juliaでは自然に書くことができます。

講義中に述べたように、これは本当に驚くべき機能です。「ロールアウト関数の勾配に区間を通す」という複雑な操作を、ほとんど追加のコードなしで実現できるのです。この部分のコードを書いているときは、実際「本当にこれができるのだろうか」と疑問に思いましたが、Juliaでは予想通りに動作しました。

高次のテイラー包含関数の実装も同様に簡潔です：

function taylor_inclusion_order2(f, interval)
    c = mid(interval)
    f_c = f(c)

    # 一次導関数
    f_prime = x -> ForwardDiff.derivative(f, x)
    f_prime_c = f_prime(c)

    # 二次導関数
    f_double_prime = x -> ForwardDiff.derivative(f_prime, x)
    f_double_prime_c = f_double_prime(c)

    # 剰余項のための三次導関数
    f_triple_prime = x -> ForwardDiff.derivative(f_double_prime, x)

    # テイラー多項式の計算
    taylor_poly = f_c + f_prime_c * (interval - c) +
                  (f_double_prime_c/2) * (interval - c)^2

    # 剰余項の計算
    remainder = (f_triple_prime(interval)/6) * (interval - c)^3

    return taylor_poly + remainder
end

このコードも驚くほど読みやすく、数学的定義とほぼ一対一で対応しています。

Juliaの優れたパフォーマンスも重要な利点です。Juliaは動的型付け言語でありながら、コンパイルされたコードと同等の実行速度を実現しています。リーチャビリティ解析のような計算集約型のタスクでは、この高速性が大きなメリットとなります。

さらに、IntervalArithmetic.jlパッケージは、丸め誤差を厳密に考慮した信頼性の高い計算を提供します。これにより、数値計算の不確かさに由来する誤差を気にすることなく、理論的に正しい結果を得ることができます。

総じて、Juliaの多重ディスパッチ、自動微分との統合、高性能、そして充実したパッケージエコシステムは、非線形システムのリーチャビリティ解析のための理想的な環境を提供します。これらの特性により、理論的な概念を実用的なコードに変換するプロセスが大幅に簡略化され、研究者や実務者が複雑なシステムの形式的検証に集中できるようになります。

8. 今後の展望

8.1. テイラーモデルによる表現力の向上

Sydney Katz：これまで説明してきた包含関数アプローチには、一つの重要な制約があります。それは、リーチャブル集合の過大近似が常に超矩形（区間ボックス）の形状に限定されるという点です。実際のリーチャブル集合がより複雑な形状を持つ場合、特に状態変数間に相関がある場合、この制約は大きな過大近似誤差をもたらします。

この問題に対処するために、次回の講義では「テイラーモデル」という、より表現力の高いアプローチを紹介します。テイラーモデルは、超矩形の制約を超えて、より複雑で正確なリーチャブル集合の表現を可能にします。

テイラーモデルの基本的なアイデアは、関数をテイラー多項式と剰余項の和として表現することです。しかし、従来のテイラー包含関数とは異なり、テイラーモデルでは多項式部分をシンボリックに扱い、実際の計算の最後まで区間に変換しません。これにより、状態変数間の相関関係を保持することができます。

数学的には、テイラーモデルは次のように表現されます：

f(x) ≈ p(x) + I

ここでp(x)はテイラー多項式（多変数多項式）で、Iは区間で表される剰余項です。p(x)は変数間の相関関係を保持するため、より正確な近似が可能になります。

テイラーモデルの大きな利点は、次の点にあります：

1. 状態変数間の相関関係の保持：変数間の依存関係を表現できるため、実際のリーチャブル集合の形状により近い近似が可能になります。
2. 依存効果の軽減：多項式部分をシンボリックに処理することで、従来の区間演算で発生する依存効果による過大近似を大幅に軽減できます。
3. より緻密な表現：テイラーモデルは、単なる超矩形ではなく、多項式によって定義される複雑な形状を表現できます。

講義の最後に簡単に示したスライドからもわかるように、テイラーモデルを使用すると、リーチャブル集合の近似精度が劇的に向上します。特に、倒立振子のような非線形システムでは、従来の区間ボックスによる近似では大きな過大近似誤差が生じていましたが、テイラーモデルではリーチャブル集合をはるかに正確に表現できることがわかります。

図では、テイラーモデルによるリーチャブル集合の近似が、サンプル点（実際のリーチャブル集合の推定）をより密接に包含しており、従来の区間ボックスによる近似と比較して過大近似が大幅に減少していることが示されています。この改善は、テイラーモデルが状態変数間の相関関係を捉えることができるためです。

次回の講義では、テイラーモデルの詳細な定式化、その操作方法、および非線形システムのリーチャビリティ解析への応用について詳しく説明します。皆さんがこの手法の可能性に興味を持ち、次回の講義を楽しみにしてくれることを願っています。

8.2. 超矩形の制約を超えた集合表現

Sydney Katz：これまで説明してきた区間演算に基づくアプローチの最大の制約の一つは、リーチャブル集合が常に超矩形（区間ボックス）として表現されるという点です。この制約は、計算効率の面では利点がありますが、表現の正確さという点では大きな限界があります。

実際のリーチャブル集合は、多くの場合、軸に平行ではない楕円形や多面体など、より複雑な形状を持ちます。特に、状態変数間に相関関係がある場合—例えば、ある状態変数の値が大きくなると他の変数も大きくなるという関係がある場合—超矩形による表現は非常に粗い近似になってしまいます。

例えば、2次元の状態空間で斜めに伸びる楕円形のリーチャブル集合を考えてみましょう。この集合を軸に平行な矩形（区間ボックス）で近似すると、実際の集合よりもはるかに大きな領域を含むことになり、大きな過大近似誤差が生じます。

これらの制約を克服するための方法として、以下のようなより表現力の高い集合表現があります：

1. ゾノトープ（Zonotopes）：ゾノトープは、中心点とジェネレータの集合によって定義される凸多面体です。線形システムのリーチャビリティ解析では既に説明しましたが、非線形システムにも拡張できます。ゾノトープは、状態変数間の相関関係を表現でき、比較的効率的に操作できるという利点があります。
2. サポート関数（Support Functions）：サポート関数は、方向ベクトルに対する集合の「最も遠い点」を計算することで集合を表現します。サポート関数は凸集合を正確に表現でき、計算も効率的です。前半で説明したサポートベクトルの概念と密接に関連しています。
3. スターセット（Star Sets）：スターセットは、中心点と一連の方向ベクトルおよび係数の範囲によって定義されます。スターセットは非凸集合も表現できるため、より正確な表現が可能です。
4. テイラーモデル（Taylor Models）：次回の講義で詳しく説明するテイラーモデルは、多項式部分と区間剰余項の組み合わせによって集合を表現します。テイラーモデルは、状態変数間の複雑な相関関係も捉えることができます。

これらの高度な集合表現を採用することで、リーチャブル集合の近似精度を大幅に向上させることができます。特に、テイラーモデルは非線形システムに特に適しており、従来の区間ボックスでは捉えられなかった複雑な形状や相関関係を表現できます。

次回の講義で紹介するテイラーモデルでは、単純な超矩形ではなく、多項式と区間の組み合わせでリーチャブル集合を表現します。これにより、状態変数間の相関関係を保持し、より正確な近似が可能になります。例えば、「角度が大きいときは角速度も大きくなる」といった変数間の関係を表現できるようになります。

超矩形の制約を超えることで、より正確なリーチャビリティ解析が可能になり、過大近似によって「結論が出せない」ケースが減少します。これにより、より多くのシステムに対して安全性保証を提供できるようになります。次回の講義では、これらのより表現力の高い集合表現、特にテイラーモデルの詳細を学びます。

8.3. 非線形性の増加への対処方法

Sydney Katz：これまでの実験結果から明らかになった大きな課題の一つは、時間ステップが増加するにつれて非線形性が複合的に増大し、どの包含関数アプローチでも過大近似が累積していくという問題です。この現象について、なぜ起こるのか、そしてどのように対処できるのかを説明します。

倒立振子の例では、1ステップ目では単純なsin(θ)という非線形項のみを扱っていますが、2ステップ目ではsin(θ + Δt・ω)のように前のステップの結果に再び非線形関数が適用されます。これにより、時間の経過とともにシステムの振る舞いを表現する関数はどんどん複雑になっていきます。例えば、数ステップ後には「sin関数の中にsin関数が入っている」ような複雑な合成関数になり、高次のテイラー包含関数でも適切に近似することが難しくなります。

この非線形性の増加に対処するための方法としては、以下のアプローチが考えられます：

1. パーティショニング（分割）：状態空間を小さな領域に分割し、各領域に対して別々にリーチャビリティ解析を行う方法です。領域が小さいほど、その内部での関数の振る舞いはより線形に近づくため、包含関数の精度が向上します。各領域の結果を合わせることで、全体のリーチャブル集合を得ることができます。このアプローチは次回の講義で詳しく説明します。
2. 時間ステップの分割：大きな時間ステップを複数の小さなステップに分割することで、各ステップでの非線形性の影響を減らす方法です。小さなステップでは関数の変化が小さくなるため、包含関数の精度が向上します。
3. ハイブリッドシステムとしのモデル化：非線形システムを複数の線形システムの組み合わせ（ハイブリッドシステム）として近似する方法です。各領域で線形近似を使用し、領域間の遷移を扱うことで、非線形性の影響を管理します。
4. コントラクタ（Contractors）：リーチャブル集合の過大近似を反復的に「収縮」させる技術です。コントラクタは、システムの制約条件を利用して、リーチャブル集合に含まれない点を除外することで、過大近似を減少させます。
5. 反復的精度向上：最初は粗い近似を行い、次にその結果を利用してより精密な計算を行うという反復的なアプローチです。各反復で過大近似が減少し、より正確な結果に収束していきます。
6. 高度な集合表現の併用：テイラーモデルなどの高度な集合表現と、パーティショニングなどの技術を組み合わせることで、非線形性の影響を効果的に管理できます。

これらの方法は、それぞれ計算コストと精度のトレードオフがあります。例えば、パーティショニングは精度を大幅に向上させる可能性がありますが、分割数に比例して計算コストが増加します。実際のアプリケーションでは、問題の性質や求められる精度、利用可能な計算リソースに応じて、適切な方法を選択または組み合わせる必要があります。

次回の講義では、特にテイラーモデルとパーティショニングに焦点を当て、これらの技術がどのように非線形性の増加問題に対処し、より長い時間ステップにわたる正確なリーチャビリティ解析を可能にするかを詳しく説明します。前回の講義の最後に示したスライドからもわかるように、これらの手法を適用することで、従来のアプローチでは不可能だった精度でのリーチャビリティ解析が可能になります。

Stanford AA228V I Validation of Safety Critical Systems I Reachability for Nonlinear Systems

To follow along with the course, visit the course website: https://aa228v.stanford.edu/ Textbook: https://algorithmsbook.com/validation/ Sydney Katz, Postdoctoral Scholar, Stanford University More about the speaker: https://sydneymkatz.com/ Mykel Kochenderfer, Associate Professor of Aeronautics and Astronautics and, by courtesy, of Computer Science, Stanford University More about the speaker: https://mykel.kochenderfer.com/ To learn more and enroll in the course: https://online.stanford.edu/courses/aa228v-validation-safety-critical-systems

youtu.be