連続システムをマルコフ決定過程に変換するための方法
【課題】最適な制御シーケンスをＭＤＦ及び連続状態空間システムについて見つけることができるように、所与の連続状態空間動的システムを離散状態空間を有するマルコフ決定過程（ＭＤＦ）に変換する。
【解決手段】連続動的システムが、離散状態を有するマルコフ決定過程に変換される。連続システムの所定の数の連続状態が選択される。各連続状態は、ＭＤＰの１つの離散状態に対応する。ドローネ三角形分割が連続状態に適用されて、一組の三角形が作成される。各三角形の頂点は連続状態を表す。各離散状態について、次の離散状態ｙ＝ｆ（ｘ，ａ）が求められる。ｘは、その離散状態に対応する連続状態を表し、ａは制御動作であり、ｆは、連続状態の非線形遷移関数である。次の離散状態ｙを含む特定の三角形が識別され、次の離散状態ｙは、その特定の三角形の頂点によって表された連続状態ｘに対応する離散状態に遷移する確率として表される。
【解決手段】連続動的システムが、離散状態を有するマルコフ決定過程に変換される。連続システムの所定の数の連続状態が選択される。各連続状態は、ＭＤＰの１つの離散状態に対応する。ドローネ三角形分割が連続状態に適用されて、一組の三角形が作成される。各三角形の頂点は連続状態を表す。各離散状態について、次の離散状態ｙ＝ｆ（ｘ，ａ）が求められる。ｘは、その離散状態に対応する連続状態を表し、ａは制御動作であり、ｆは、連続状態の非線形遷移関数である。次の離散状態ｙを含む特定の三角形が識別され、次の離散状態ｙは、その特定の三角形の頂点によって表された連続状態ｘに対応する離散状態に遷移する確率として表される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動的システムの最適な逐次制御に関し、より詳細には、連続状態空間を有する非線形動的システムを、離散状態空間を有するマルコフ決定過程（ＭＤＰ）に変換することに関する。
【背景技術】
【０００２】
動的システムの動作は、通例、制御動作の影響を受けたシステムの状態の時間依存性及び展開を指定する一組の方程式によって記述される。どの所与の時刻においても、動的システムは、実数のベクトルによって与えられる状態を有する。この実数のベクトルは、適切な状態空間において表すことができる。動的システムの状態における小さな変化は、これらの実数における小さな変化に対応する。連続動的システムは、通例、一組の微分方程式に従って動作する。
【０００３】
本発明は、一組の離散制御動作によって制御される任意の遷移関数を有する連続状態空間における任意の非線形動的システムの自動制御及び自動スケジューリングに関係する。
【０００４】
例示的な動的システムには、ロボット、車両、熱換気空調（ＨＶＡＣ）システム、発電機、及び家庭用機器が含まれる。通常、これらのシステムは、モータによって動作される。モータは、例えばオン及びオフといった比較的少数の離散的な設定を有する。或いは、可能な設定の数は適度に制限することができ、例えば、サーモスタットを整数の温度にのみ設定することができる。
【０００５】
このようなシステムの状態は、通常、その動的システムの連続状態空間Ｘの実数値ベクトルｘである。集合Ａの制御動作ａは離散的である。制御システムのダイナミクスは、以下の一組の方程式によって記述することができる。
ｘｋ＋１＝ｆ（ｘｋ，ａｋ）
ここで、ｘｋは時刻ｔｋにおけるシステムの状態であり、ａｋは時刻ｔｋにおいて適用される制御動作であり、ｆは任意の非線形遷移関数であり、システムは、選択された間隔Δｔについてｔｋ＝ｋΔｔとなるような離散時間で展開する。動作シーケンスａ０，ａ１，ａ２，…は、性能の指標が最適化されるように選択しなければならない。例えば、ＨＶＡＣシステムは、最小のエネルギー消費で、環境を所望の温度に徐々に持って行くことによって最適化することができる。
【０００６】
１つの性能指標は、Ｋ個のステップにわたる累積コストＪである。
【０００７】
【数１】
【０００８】
ここで、ｇは、選択された動作コストであり、ｈは最終状態ｘＫに関連付けられた終端コストである。
【０００９】
任意の関数ｆ、ｇ、及びｈのこの最適化問題を解くための方法は存在せず、特別な場合の解決法のみが知られている。例えば、線形二次レギュレータ（ＬＱＲ）では、ａは実数であり、ｆは線形であり、ｇ及びｈは、状態ｘ及び制御ａにおいて二次である。しかしながら、一般的な場合に、関数ｆは線形ではなく、コスト関数ｇ及びｈは、その状態及び制御において二次ではない。このような場合、最適な制御は数値的方法によって見つけることができる。
【００１０】
時間的な動的システムの展開を記述する別の方法は、マルコフ決定過程（ＭＤＰ）として展開を表すことである。ＭＤＰは、４つの要素（Ｓ，Ａ，Ｒ，Ｐ）によって記述される。ここで、Ｓは、状態ｓの有限集合であり、Ａは動作ａの有限集合であり、Ｒは、Ｒ（ｓ，ａ）が、動作ａが状態ｓで行われた場合の報酬（個々にはコスト）を表すような報酬関数であり、Ｐはマルコフ遷移モデル（Markovian transition model）である。このマルコフ遷移モデルでは、Ｐ（ｓ’｜ｓ，ａ）は、動作ａが状態ｓで行われた場合に状態ｓ’で終了する確率を表する。
【００１１】
上記の場合と同様に、目標は、累積報酬Ｒ（ｓ，ａ）の点から定義される性能指標を最適化する動作シーケンスａ０，ａ１，ａ２，…を見つけることである。このような最適な動作シーケンスを見つけるための方法は、任意の遷移モデルＰ（ｓ’｜ｓ，ａ）について存在する。
【発明の概要】
【発明が解決しようとする課題】
【００１２】
しかしながら、ＭＤＰと、連続状態空間動的システムを記述する一組の微分方程式との間の主な差異は、ＭＤＰの状態空間が離散的であるということである。すなわち、システムは、どの所与の時刻においても、限られた数の離散状態にのみ存在することができるということである。したがって、最適な制御シーケンスをＭＤＰ及び連続状態空間システムについて見つけることができるように、所与の連続状態空間動的システムを、離散状態空間を有するマルコフ決定過程（ＭＤＰ）に変換することが望まれている。
【課題を解決するための手段】
【００１３】
連続動的システムが、離散状態を有するマルコフ決定過程（ＭＤＰ）に変換される。連続システムの所定の数の連続状態が選択される。各連続状態は、ＭＤＰの１つの離散状態に対応する。
【００１４】
ドローネ三角形分割が連続状態に適用されて、一組の三角形が作成される。各三角形の頂点は連続状態を表す。
【００１５】
各離散状態について、次の離散状態ｙ＝ｆ（ｘ，ａ）が求められる。ｘは、その離散状態に対応する連続状態を表し、ａは制御動作であり、ｆは、連続状態の非線形遷移関数である。
【００１６】
次の離散状態ｙを含む特定の三角形が識別され、次の離散状態ｙは、その特定の三角形の頂点によって表された連続状態ｘに対応する離散状態に遷移する確率として表される。
【図面の簡単な説明】
【００１７】
【図１】本発明の実施形態による、動的システムをマルコフ決定過程に変換するための方法のブロック図である。
【図２】本発明の実施形態による、連続状態を離散状態に変換するためのステップのブロック図である。
【図３】本発明の実施形態による、選択された連続状態を表す三角形をトラバースするためのブロック図である。
【図４】本発明の実施形態による、三角形分割された連続状態の概略図である。
【発明を実施するための形態】
【００１８】
図１に示すように、本発明の実施形態は、連続状態の集合Ｘ＝｛ｘｉ｝１０１を有する非線形動的システムを、離散状態の集合Ｓ＝｛ｓ（１），ｓ（２），…，ｓ（Ｎ）｝１０９を有するマルコフ決定過程（ＭＤＰ）に変換するための方法を提供する。離散状態の集合Ｓは、オリジナルのシステムの状態空間ＸからＮ個のサンプルを（ランダム又は系統的な順序に従って）取り出すことによって取得することができる。１つのサンプリング方法は、Ｘ全体にわたる一様ランダム分布からサンプルを取り出すことである。もう１つの方法は、Ｘ全体にわたる規則的なグリッドを使用することである。
【００１９】
制御動作ａｋに起因して離散時間で現在の離散状態ｓｋから次の状態ｓｋ＋１へ遷移する確率は
【００２０】
【数２】
【００２１】
である。この方法は、状態ｓｋ＋１、ｓｋがＳに存在するように、あらゆる３重項（ｓｋ＋１，ｓｋ，ａｋ）の遷移確率ｐを構成する。次に、構成されたＭＤＰに対して、ポリシー反復又はポリシー値を使用して、あらゆる状態ｓｋについて、状態ｓを最適な制御ａにマッピングする最適なポリシーａ＝π（ｓｋ）を見つけることができる。
【００２２】
この構成方法は、条件付き確率関数及び凸結合の特性における類似点に基づいている。条件付き確率関数は、確率変数が或る指定された値に等しい確率を指定する。ＭＤＰの場合、遷移関数が、現在の状態及び制御動作を条件としたこのような確率関数となる。
【００２３】
この確率関数が指定される確率変数は、次の状態ｓｋ＋１である。遷移関数の要素は、
【００２４】
【数３】
【００２５】
である。
【００２６】
条件付き確率関数の公理的性質から、
【００２７】
【数４】
【００２８】
となる。
【００２９】
他方、Ｎ個のベクトルｙｉの凸結合は、
【００３０】
【数５】
【００３１】
である。
【００３２】
したがって、条件付き確率関数及び凸結合は同じ制約を有する。すなわち、この関数の確率及びこの結合の係数は、すべて非負であり、合計すると１になる。条件付き確率関数の確率は、有効な凸結合の係数として使用することができ、その逆も同様である。したがって、ＭＤＰの遷移関数は、適切に定義された凸結合の係数の集合として構成することができる。
【００３３】
システム変換方法
図１〜図３に示すように、動的システムは、連続状態ｘ（ｉ）の集合Ｘ１０１を有する。各状態は、ｄ次元ベクトルによって表すことができる。図４に示すように、例示的なＨＶＡＣシステムの状態ｘは、連続的に変化する温度４０１及び湿度４０２を含む。
【００３４】
本方法は、各状態ｘ（ｉ）が集合ＳのＮ個の離散状態ｓ（ｉ）の１つに対応するように、集合ＸからＮ個の連続状態ｘ（ｉ）１１１を選択する（１１０）。この選択によって、連続状態空間を一様かつランダムにサンプリングすることができる。選択された状態は、ｄ×Ｎ行列Ｂ１１２に格納される。この行列Ｂ１１２において、各列は、選択された状態の１つである。
【００３５】
ドローネ三角形分割ＤＴ（Ｘ）をこの集合に適用する（１２０）。この三角形分割によって、Ｍ個の三角形ｍが作成される。これらの三角形は、行列Ｄ１２１に格納される。この行列Ｄ１２１において、各列は１つの三角形に対応し、３つの行はこれらの三角形の頂点に対応する。
【００３６】
シンプレックス
本明細書及び特許請求の範囲では一般に、各三角形は、より一般的な項であるシンプレックスに置き換えることができる。シンプレックスは、任意の次元ｄの状態空間Ｘにおいて三角形を一般化したものである。例えば、次元数ｄ＝２である場合、シンプレックス（又は三角形）における頂点の数はｄ＋１＝３であり、ｄ＝３の場合、シンプレックスは、ｄ＋１＝４個の頂点を有する四面体である。
【００３７】
状態ｓは、図２に示すように一度に１つの状態が変換される（２００）。各状態ｓ（ｉ）２０３について、対応する状態ｘ（ｉ）１１１及び制御ａ（ｌ）２０２がリトリーブされ（２１０）、次の状態ｙ＝ｆ（ｘ（ｉ），ａ（ｌ））２０４を求める（２１０）のに使用される。ここで、ｆは、連続状態空間システムの展開を記述する任意の非線形関数である。図２は、或る動作ａについて、ｉ＝０及びｙ＝ｆ（ｘ（０），ａ）である場合を示す。
【００３８】
一般に、次の状態ｙ２０４は、選択された状態ｘ（ｉ）のいずれとも一致しない。次の状態ｙ２０４を含むＤＴ（Ｘ）の特定の三角形ｍ４１０は、図３について以下で説明するようにすべてのＭ個の三角形をトラバースすることによって突き止められる（３００）。
【００３９】
現在の三角形ｍについて、この三角形ｍの最後の頂点ｖｍ，ｄ＋１がリトリーブされ、ベクトルｑに格納される（３１０）。ｄ×ｄ差分行列Ｅ３２１が構成される（３２０）。行列Ｅにおいて、列ｊは、ｊ＝１、ｄについて差分ｖｍ，ｊ−ｑを含む。一組の連立一次方程式を解くことによって、Ｅｃ＝（ｙ−ｑ）となるようなｄ次元ベクトルｃが求められる。
【００４０】
ベクトルｃの最後の要素ｃｄ＋１３４１が、
【００４１】
【数６】
【００４２】
として求められる（３４０）。
【００４３】
ｊ＝１…ｄ＋１のあらゆる要素ｃｊについて、ｃｊが負であるか否か、すなわちｃｊ＜０であるか否かが確認される。真である場合、三角形ｍは状態ｙを含まず、ｍがインクリメントされ、次の三角形について繰り返される。
【００４４】
そうではなく、すべてのｃｊが正である場合、三角形ｍは状態ｙを含む。ｄ＋１次元ベクトルｃは、ステップ２２０における
【００４５】
【数７】
【００４６】
となるような有効な凸結合を定義する係数を含む。したがって、ベクトルｃは、そのエントリのすべてが非負であり、合計すると１になるので、有効な確率遷移関数を定義する。
【００４７】
すべての可能なＮ個の次の状態について完全な遷移確率分布を構成するために、以下のステップが、ｌ＝１…Ｎの各離散状態ｓ（ｌ）について実行される。
【００４８】
状態ｓ（ｌ）が三角形ｍの頂点の１つに対応する場合、すなわち、或るｊについてｘ（ｌ）＝ｖｍ，ｊである場合（２３０）、ＭＤＰの対応する遷移確率ｐｌ４１１は、
【００４９】
【数８】
【００５０】
であり、そうでない場合、ｐｌ＝０である（２３２）。
【００５１】
概念的には、離散状態ｓ（ｉ）の小さな集合のみを伴う確率的表現と等価な関数ｆによって表される動的システムは、動的システムの連続状態Ｘに組み込まれる。
【００５２】
システムがこれらの状態の１つで始動する場合、次の状態ｙは、一般に、これらの状態の別の１つと一致しない。三角形の頂点を定義するｄ＋１個の状態は、次の状態ｙを完全に取り囲む。すなわち、システムは、状態ｙでなく、さまざまな確率を有する対応する三角形の頂点に遷移している。
【００５３】
これらの確率は、（状態ｙを含む三角形の）頂点に関する状態ｙの凸分解に等しい。これらの確率は、取り囲む三角形の頂点に関する状態ｙの重心座標とみなすこともできる。これは、凸結合とＭＤＰの確率関数との間の類似点によって可能にされる。
【００５４】
処理時間を減らすために、行列Ｅの逆行列Ｅ−１を、ドローネ三角形分割のあらゆる三角形について格納することができ、次いで、各反復で一組の一次方程式を解くのではなく、ステップ３３０においてこの逆行列を使用して、
ｃ＝Ｅ−１（ｙ−ｑ）
を求めることができる。
【００５５】
ドローネ三角形分割の三角形のトラバースも改善することができる。次の状態ｙを取り囲む三角形が現在の状態の三角形の近くにあると予想することが妥当である。現在の状態と各三角形の重心との間の距離が予め求められている場合、ドローネ三角形分割の三角形は、距離の昇順でトラバースすることができる。
【００５６】
本発明を、好ましい実施形態の例として説明してきたが、本発明の精神及び範囲内で他のさまざまな適合及び変更を行えることが理解されるべきである。したがって、本発明の真の精神及び範囲内に入るすべての変形及び変更を包含することが、添付の特許請求の範囲の目的である。
【技術分野】
【０００１】
本発明は、動的システムの最適な逐次制御に関し、より詳細には、連続状態空間を有する非線形動的システムを、離散状態空間を有するマルコフ決定過程（ＭＤＰ）に変換することに関する。
【背景技術】
【０００２】
動的システムの動作は、通例、制御動作の影響を受けたシステムの状態の時間依存性及び展開を指定する一組の方程式によって記述される。どの所与の時刻においても、動的システムは、実数のベクトルによって与えられる状態を有する。この実数のベクトルは、適切な状態空間において表すことができる。動的システムの状態における小さな変化は、これらの実数における小さな変化に対応する。連続動的システムは、通例、一組の微分方程式に従って動作する。
【０００３】
本発明は、一組の離散制御動作によって制御される任意の遷移関数を有する連続状態空間における任意の非線形動的システムの自動制御及び自動スケジューリングに関係する。
【０００４】
例示的な動的システムには、ロボット、車両、熱換気空調（ＨＶＡＣ）システム、発電機、及び家庭用機器が含まれる。通常、これらのシステムは、モータによって動作される。モータは、例えばオン及びオフといった比較的少数の離散的な設定を有する。或いは、可能な設定の数は適度に制限することができ、例えば、サーモスタットを整数の温度にのみ設定することができる。
【０００５】
このようなシステムの状態は、通常、その動的システムの連続状態空間Ｘの実数値ベクトルｘである。集合Ａの制御動作ａは離散的である。制御システムのダイナミクスは、以下の一組の方程式によって記述することができる。
ｘｋ＋１＝ｆ（ｘｋ，ａｋ）
ここで、ｘｋは時刻ｔｋにおけるシステムの状態であり、ａｋは時刻ｔｋにおいて適用される制御動作であり、ｆは任意の非線形遷移関数であり、システムは、選択された間隔Δｔについてｔｋ＝ｋΔｔとなるような離散時間で展開する。動作シーケンスａ０，ａ１，ａ２，…は、性能の指標が最適化されるように選択しなければならない。例えば、ＨＶＡＣシステムは、最小のエネルギー消費で、環境を所望の温度に徐々に持って行くことによって最適化することができる。
【０００６】
１つの性能指標は、Ｋ個のステップにわたる累積コストＪである。
【０００７】
【数１】
【０００８】
ここで、ｇは、選択された動作コストであり、ｈは最終状態ｘＫに関連付けられた終端コストである。
【０００９】
任意の関数ｆ、ｇ、及びｈのこの最適化問題を解くための方法は存在せず、特別な場合の解決法のみが知られている。例えば、線形二次レギュレータ（ＬＱＲ）では、ａは実数であり、ｆは線形であり、ｇ及びｈは、状態ｘ及び制御ａにおいて二次である。しかしながら、一般的な場合に、関数ｆは線形ではなく、コスト関数ｇ及びｈは、その状態及び制御において二次ではない。このような場合、最適な制御は数値的方法によって見つけることができる。
【００１０】
時間的な動的システムの展開を記述する別の方法は、マルコフ決定過程（ＭＤＰ）として展開を表すことである。ＭＤＰは、４つの要素（Ｓ，Ａ，Ｒ，Ｐ）によって記述される。ここで、Ｓは、状態ｓの有限集合であり、Ａは動作ａの有限集合であり、Ｒは、Ｒ（ｓ，ａ）が、動作ａが状態ｓで行われた場合の報酬（個々にはコスト）を表すような報酬関数であり、Ｐはマルコフ遷移モデル（Markovian transition model）である。このマルコフ遷移モデルでは、Ｐ（ｓ’｜ｓ，ａ）は、動作ａが状態ｓで行われた場合に状態ｓ’で終了する確率を表する。
【００１１】
上記の場合と同様に、目標は、累積報酬Ｒ（ｓ，ａ）の点から定義される性能指標を最適化する動作シーケンスａ０，ａ１，ａ２，…を見つけることである。このような最適な動作シーケンスを見つけるための方法は、任意の遷移モデルＰ（ｓ’｜ｓ，ａ）について存在する。
【発明の概要】
【発明が解決しようとする課題】
【００１２】
しかしながら、ＭＤＰと、連続状態空間動的システムを記述する一組の微分方程式との間の主な差異は、ＭＤＰの状態空間が離散的であるということである。すなわち、システムは、どの所与の時刻においても、限られた数の離散状態にのみ存在することができるということである。したがって、最適な制御シーケンスをＭＤＰ及び連続状態空間システムについて見つけることができるように、所与の連続状態空間動的システムを、離散状態空間を有するマルコフ決定過程（ＭＤＰ）に変換することが望まれている。
【課題を解決するための手段】
【００１３】
連続動的システムが、離散状態を有するマルコフ決定過程（ＭＤＰ）に変換される。連続システムの所定の数の連続状態が選択される。各連続状態は、ＭＤＰの１つの離散状態に対応する。
【００１４】
ドローネ三角形分割が連続状態に適用されて、一組の三角形が作成される。各三角形の頂点は連続状態を表す。
【００１５】
各離散状態について、次の離散状態ｙ＝ｆ（ｘ，ａ）が求められる。ｘは、その離散状態に対応する連続状態を表し、ａは制御動作であり、ｆは、連続状態の非線形遷移関数である。
【００１６】
次の離散状態ｙを含む特定の三角形が識別され、次の離散状態ｙは、その特定の三角形の頂点によって表された連続状態ｘに対応する離散状態に遷移する確率として表される。
【図面の簡単な説明】
【００１７】
【図１】本発明の実施形態による、動的システムをマルコフ決定過程に変換するための方法のブロック図である。
【図２】本発明の実施形態による、連続状態を離散状態に変換するためのステップのブロック図である。
【図３】本発明の実施形態による、選択された連続状態を表す三角形をトラバースするためのブロック図である。
【図４】本発明の実施形態による、三角形分割された連続状態の概略図である。
【発明を実施するための形態】
【００１８】
図１に示すように、本発明の実施形態は、連続状態の集合Ｘ＝｛ｘｉ｝１０１を有する非線形動的システムを、離散状態の集合Ｓ＝｛ｓ（１），ｓ（２），…，ｓ（Ｎ）｝１０９を有するマルコフ決定過程（ＭＤＰ）に変換するための方法を提供する。離散状態の集合Ｓは、オリジナルのシステムの状態空間ＸからＮ個のサンプルを（ランダム又は系統的な順序に従って）取り出すことによって取得することができる。１つのサンプリング方法は、Ｘ全体にわたる一様ランダム分布からサンプルを取り出すことである。もう１つの方法は、Ｘ全体にわたる規則的なグリッドを使用することである。
【００１９】
制御動作ａｋに起因して離散時間で現在の離散状態ｓｋから次の状態ｓｋ＋１へ遷移する確率は
【００２０】
【数２】
【００２１】
である。この方法は、状態ｓｋ＋１、ｓｋがＳに存在するように、あらゆる３重項（ｓｋ＋１，ｓｋ，ａｋ）の遷移確率ｐを構成する。次に、構成されたＭＤＰに対して、ポリシー反復又はポリシー値を使用して、あらゆる状態ｓｋについて、状態ｓを最適な制御ａにマッピングする最適なポリシーａ＝π（ｓｋ）を見つけることができる。
【００２２】
この構成方法は、条件付き確率関数及び凸結合の特性における類似点に基づいている。条件付き確率関数は、確率変数が或る指定された値に等しい確率を指定する。ＭＤＰの場合、遷移関数が、現在の状態及び制御動作を条件としたこのような確率関数となる。
【００２３】
この確率関数が指定される確率変数は、次の状態ｓｋ＋１である。遷移関数の要素は、
【００２４】
【数３】
【００２５】
である。
【００２６】
条件付き確率関数の公理的性質から、
【００２７】
【数４】
【００２８】
となる。
【００２９】
他方、Ｎ個のベクトルｙｉの凸結合は、
【００３０】
【数５】
【００３１】
である。
【００３２】
したがって、条件付き確率関数及び凸結合は同じ制約を有する。すなわち、この関数の確率及びこの結合の係数は、すべて非負であり、合計すると１になる。条件付き確率関数の確率は、有効な凸結合の係数として使用することができ、その逆も同様である。したがって、ＭＤＰの遷移関数は、適切に定義された凸結合の係数の集合として構成することができる。
【００３３】
システム変換方法
図１〜図３に示すように、動的システムは、連続状態ｘ（ｉ）の集合Ｘ１０１を有する。各状態は、ｄ次元ベクトルによって表すことができる。図４に示すように、例示的なＨＶＡＣシステムの状態ｘは、連続的に変化する温度４０１及び湿度４０２を含む。
【００３４】
本方法は、各状態ｘ（ｉ）が集合ＳのＮ個の離散状態ｓ（ｉ）の１つに対応するように、集合ＸからＮ個の連続状態ｘ（ｉ）１１１を選択する（１１０）。この選択によって、連続状態空間を一様かつランダムにサンプリングすることができる。選択された状態は、ｄ×Ｎ行列Ｂ１１２に格納される。この行列Ｂ１１２において、各列は、選択された状態の１つである。
【００３５】
ドローネ三角形分割ＤＴ（Ｘ）をこの集合に適用する（１２０）。この三角形分割によって、Ｍ個の三角形ｍが作成される。これらの三角形は、行列Ｄ１２１に格納される。この行列Ｄ１２１において、各列は１つの三角形に対応し、３つの行はこれらの三角形の頂点に対応する。
【００３６】
シンプレックス
本明細書及び特許請求の範囲では一般に、各三角形は、より一般的な項であるシンプレックスに置き換えることができる。シンプレックスは、任意の次元ｄの状態空間Ｘにおいて三角形を一般化したものである。例えば、次元数ｄ＝２である場合、シンプレックス（又は三角形）における頂点の数はｄ＋１＝３であり、ｄ＝３の場合、シンプレックスは、ｄ＋１＝４個の頂点を有する四面体である。
【００３７】
状態ｓは、図２に示すように一度に１つの状態が変換される（２００）。各状態ｓ（ｉ）２０３について、対応する状態ｘ（ｉ）１１１及び制御ａ（ｌ）２０２がリトリーブされ（２１０）、次の状態ｙ＝ｆ（ｘ（ｉ），ａ（ｌ））２０４を求める（２１０）のに使用される。ここで、ｆは、連続状態空間システムの展開を記述する任意の非線形関数である。図２は、或る動作ａについて、ｉ＝０及びｙ＝ｆ（ｘ（０），ａ）である場合を示す。
【００３８】
一般に、次の状態ｙ２０４は、選択された状態ｘ（ｉ）のいずれとも一致しない。次の状態ｙ２０４を含むＤＴ（Ｘ）の特定の三角形ｍ４１０は、図３について以下で説明するようにすべてのＭ個の三角形をトラバースすることによって突き止められる（３００）。
【００３９】
現在の三角形ｍについて、この三角形ｍの最後の頂点ｖｍ，ｄ＋１がリトリーブされ、ベクトルｑに格納される（３１０）。ｄ×ｄ差分行列Ｅ３２１が構成される（３２０）。行列Ｅにおいて、列ｊは、ｊ＝１、ｄについて差分ｖｍ，ｊ−ｑを含む。一組の連立一次方程式を解くことによって、Ｅｃ＝（ｙ−ｑ）となるようなｄ次元ベクトルｃが求められる。
【００４０】
ベクトルｃの最後の要素ｃｄ＋１３４１が、
【００４１】
【数６】
【００４２】
として求められる（３４０）。
【００４３】
ｊ＝１…ｄ＋１のあらゆる要素ｃｊについて、ｃｊが負であるか否か、すなわちｃｊ＜０であるか否かが確認される。真である場合、三角形ｍは状態ｙを含まず、ｍがインクリメントされ、次の三角形について繰り返される。
【００４４】
そうではなく、すべてのｃｊが正である場合、三角形ｍは状態ｙを含む。ｄ＋１次元ベクトルｃは、ステップ２２０における
【００４５】
【数７】
【００４６】
となるような有効な凸結合を定義する係数を含む。したがって、ベクトルｃは、そのエントリのすべてが非負であり、合計すると１になるので、有効な確率遷移関数を定義する。
【００４７】
すべての可能なＮ個の次の状態について完全な遷移確率分布を構成するために、以下のステップが、ｌ＝１…Ｎの各離散状態ｓ（ｌ）について実行される。
【００４８】
状態ｓ（ｌ）が三角形ｍの頂点の１つに対応する場合、すなわち、或るｊについてｘ（ｌ）＝ｖｍ，ｊである場合（２３０）、ＭＤＰの対応する遷移確率ｐｌ４１１は、
【００４９】
【数８】
【００５０】
であり、そうでない場合、ｐｌ＝０である（２３２）。
【００５１】
概念的には、離散状態ｓ（ｉ）の小さな集合のみを伴う確率的表現と等価な関数ｆによって表される動的システムは、動的システムの連続状態Ｘに組み込まれる。
【００５２】
システムがこれらの状態の１つで始動する場合、次の状態ｙは、一般に、これらの状態の別の１つと一致しない。三角形の頂点を定義するｄ＋１個の状態は、次の状態ｙを完全に取り囲む。すなわち、システムは、状態ｙでなく、さまざまな確率を有する対応する三角形の頂点に遷移している。
【００５３】
これらの確率は、（状態ｙを含む三角形の）頂点に関する状態ｙの凸分解に等しい。これらの確率は、取り囲む三角形の頂点に関する状態ｙの重心座標とみなすこともできる。これは、凸結合とＭＤＰの確率関数との間の類似点によって可能にされる。
【００５４】
処理時間を減らすために、行列Ｅの逆行列Ｅ−１を、ドローネ三角形分割のあらゆる三角形について格納することができ、次いで、各反復で一組の一次方程式を解くのではなく、ステップ３３０においてこの逆行列を使用して、
ｃ＝Ｅ−１（ｙ−ｑ）
を求めることができる。
【００５５】
ドローネ三角形分割の三角形のトラバースも改善することができる。次の状態ｙを取り囲む三角形が現在の状態の三角形の近くにあると予想することが妥当である。現在の状態と各三角形の重心との間の距離が予め求められている場合、ドローネ三角形分割の三角形は、距離の昇順でトラバースすることができる。
【００５６】
本発明を、好ましい実施形態の例として説明してきたが、本発明の精神及び範囲内で他のさまざまな適合及び変更を行えることが理解されるべきである。したがって、本発明の真の精神及び範囲内に入るすべての変形及び変更を包含することが、添付の特許請求の範囲の目的である。
【特許請求の範囲】
【請求項１】
連続システムをマルコフ決定過程（ＭＤＰ）に変換するための方法であって、前記連続システムは動的であり、前記ＭＤＰは離散状態を有し、該方法は、
前記連続システムの所定の数の連続状態を選択するステップであって、各連続状態は前記ＭＤＰの１つの離散状態に対応する、選択するステップと、
ドローネ三角形分割を前記連続状態に適用するステップであって、一組の三角形を作成し、各三角形の頂点は前記連続状態を表す、適用するステップと、
を含み、
各離散状態について、
次の離散状態ｙ＝ｆ（ｘ，ａ）を求めるステップであって、ｘはその離散状態に対応する前記連続状態を表し、ａは制御動作であり、ｆは前記連続状態の非線形遷移関数である、求めるステップと、
前記次の離散状態ｙを含む特定の三角形を識別するステップと、
前記次の離散状態ｙを、前記特定の三角形の前記頂点によって表された前記連続状態ｘに対応する前記離散状態に遷移する確率として表すステップと、
をさらに含み、
前記ステップは、プロセッサにおいて実行される、
方法。
【請求項２】
前記ＭＤＰの前記離散状態は、前記連続システムの状態空間Ｘの一様ランダムサンプリングによって選択される、請求項１に記載の方法。
【請求項３】
前記ＭＤＰの前記離散状態は、前記連続システムの状態空間Ｘに規則的なグリッドをインポーズすることによって選択される、請求項１に記載の方法。
【請求項４】
前記特定の三角形を識別するステップは、前記差分行列Ｅの列ｊが、ｊ＝１…ｄについて、三角形ｍのｊ番目の頂点ｖｍ，ｊと該三角形ｍのｄ＋１番目の頂点ｑ＝ｖｍ，ｄ＋１との間の差分ｖｍ，ｊ−ｖｍ，ｄ＋１を含むようなｄ×ｄ差分行列Ｅを形成し、ベクトルｃについて方程式Ｅｃ＝（ｙ−ｑ）の線形システムを解くことによって実行され、前記三角形ｍは、すべてｃｊ＞０、ｊ＝１，ｄであり、かつ
【数１】
である場合にｙを含むものとして識別される、請求項１に記載の方法。
【請求項５】
前記線形方程式をｃ＝Ｅ−１（ｙ−ｑ）として解くことができるように、前記行列Ｅの逆行列Ｅ−１が事前に計算されて格納される、請求項４に記載の方法。
【請求項６】
前記ドローネ三角形分割の前記三角形は、前記頂点の重心から前記状態ｙまでの距離の昇順でトラバースされる、請求項４に記載の方法。
【請求項７】
前記三角形はシンプレックスに一般化される、請求項１に記載の方法。
【請求項１】
連続システムをマルコフ決定過程（ＭＤＰ）に変換するための方法であって、前記連続システムは動的であり、前記ＭＤＰは離散状態を有し、該方法は、
前記連続システムの所定の数の連続状態を選択するステップであって、各連続状態は前記ＭＤＰの１つの離散状態に対応する、選択するステップと、
ドローネ三角形分割を前記連続状態に適用するステップであって、一組の三角形を作成し、各三角形の頂点は前記連続状態を表す、適用するステップと、
を含み、
各離散状態について、
次の離散状態ｙ＝ｆ（ｘ，ａ）を求めるステップであって、ｘはその離散状態に対応する前記連続状態を表し、ａは制御動作であり、ｆは前記連続状態の非線形遷移関数である、求めるステップと、
前記次の離散状態ｙを含む特定の三角形を識別するステップと、
前記次の離散状態ｙを、前記特定の三角形の前記頂点によって表された前記連続状態ｘに対応する前記離散状態に遷移する確率として表すステップと、
をさらに含み、
前記ステップは、プロセッサにおいて実行される、
方法。
【請求項２】
前記ＭＤＰの前記離散状態は、前記連続システムの状態空間Ｘの一様ランダムサンプリングによって選択される、請求項１に記載の方法。
【請求項３】
前記ＭＤＰの前記離散状態は、前記連続システムの状態空間Ｘに規則的なグリッドをインポーズすることによって選択される、請求項１に記載の方法。
【請求項４】
前記特定の三角形を識別するステップは、前記差分行列Ｅの列ｊが、ｊ＝１…ｄについて、三角形ｍのｊ番目の頂点ｖｍ，ｊと該三角形ｍのｄ＋１番目の頂点ｑ＝ｖｍ，ｄ＋１との間の差分ｖｍ，ｊ−ｖｍ，ｄ＋１を含むようなｄ×ｄ差分行列Ｅを形成し、ベクトルｃについて方程式Ｅｃ＝（ｙ−ｑ）の線形システムを解くことによって実行され、前記三角形ｍは、すべてｃｊ＞０、ｊ＝１，ｄであり、かつ
【数１】
である場合にｙを含むものとして識別される、請求項１に記載の方法。
【請求項５】
前記線形方程式をｃ＝Ｅ−１（ｙ−ｑ）として解くことができるように、前記行列Ｅの逆行列Ｅ−１が事前に計算されて格納される、請求項４に記載の方法。
【請求項６】
前記ドローネ三角形分割の前記三角形は、前記頂点の重心から前記状態ｙまでの距離の昇順でトラバースされる、請求項４に記載の方法。
【請求項７】
前記三角形はシンプレックスに一般化される、請求項１に記載の方法。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【公開番号】特開２０１１−１３８４８９（Ｐ２０１１−１３８４８９Ａ）
【公開日】平成２３年７月１４日（２０１１．７．１４）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１０−２５７９４９（Ｐ２０１０−２５７９４９）
【出願日】平成２２年１１月１８日（２０１０．１１．１８）
【出願人】（５９７０６７５７４）ミツビシ・エレクトリック・リサーチ・ラボラトリーズ・インコーポレイテッド (484)
【住所又は居所原語表記】２０１ ＢＲＯＡＤＷＡＹ， ＣＡＭＢＲＩＤＧＥ， ＭＡＳＳＡＣＨＵＳＥＴＴＳ ０２１３９， Ｕ．Ｓ．Ａ．
【Ｆターム（参考）】
【公開日】平成２３年７月１４日（２０１１．７．１４）
【国際特許分類】
【出願番号】特願２０１０−２５７９４９（Ｐ２０１０−２５７９４９）
【出願日】平成２２年１１月１８日（２０１０．１１．１８）
【出願人】（５９７０６７５７４）ミツビシ・エレクトリック・リサーチ・ラボラトリーズ・インコーポレイテッド (484)
【住所又は居所原語表記】２０１ ＢＲＯＡＤＷＡＹ， ＣＡＭＢＲＩＤＧＥ， ＭＡＳＳＡＣＨＵＳＥＴＴＳ ０２１３９， Ｕ．Ｓ．Ａ．
【Ｆターム（参考）】
[ Back to top ]