(57)【特許請求の範囲】
【請求項１】
ルートに沿った運行中の車両の動きの運転曲線を、少なくとも、運行の連続空間における該車両の速度と該車両の位置との関数として求める方法であって、
前記連続空間から選択されたアンカー状態の集合に関してマルコフ決定過程(ＭＤＰ)を求めるステップであって、前記車両を或る状態に動かす制御が、前記連続空間におけるアンカー状態と前記状態との間の距離の関数として求められる確率で前記ＭＤＰを前記アンカー状態に遷移させるようにするものと、
制約を受ける前記ＭＤＰを解いて、前記車両の動きのコストを表すコスト関数を最適化するＭＤＰポリシーを求めるステップと、
前記ＭＤＰポリシーに基づいて前記運転曲線を求めるステップと、
を含み、
前記コスト関数は、前記運行中の前記車両のエネルギー消費及び総運行時間の双方を表し、前記運転曲線が前記車両のエネルギー消費と総運行時間との組み合わせを最適化するようにし、
前記ＭＤＰを求めることは、
前記連続空間における１組の段階を形成する１組の距離周期において前記車両の走行距離を分割することと、
前記遷移のステップを距離周期として求めることであって、各制御が、システムを前の段階の前の状態から次の段階における次の状態に遷移させるようにするものと、
前記連続空間における各アンカー状態のロケーションが前記１組の段階からの或る段階にあるように前記アンカー状態の集合を選択することと、
を含み、
前記各ステップはプロセッサにおいて実行される、ルートに沿った運行中の車両の動きの運転曲線を、少なくとも、運行の連続空間における該車両の速度と該車両の位置との関数として求める方法。
【請求項２】
ルートに沿った運行中の車両の動きの運転曲線を、少なくとも、運行の連続空間における該車両の速度と該車両の位置との関数として求める方法であって、
前記連続空間から選択されたアンカー状態の集合に関してマルコフ決定過程(ＭＤＰ)を求めるステップであって、前記車両を或る状態に動かす制御が、前記連続空間におけるアンカー状態と前記状態との間の距離の関数として求められる確率で前記ＭＤＰを前記アンカー状態に遷移させるようにするものと、
制約を受ける前記ＭＤＰを解いて、前記車両の動きのコストを表すコスト関数を最適化するＭＤＰポリシーを求めるステップと、
前記ＭＤＰポリシーに基づいて前記運転曲線を求めるステップと、
を含み、
前記コスト関数は、前記運行中の前記車両のエネルギー消費及び総運行時間の双方を表し、前記運転曲線が前記車両のエネルギー消費と総運行時間との組み合わせを最適化するようにし、
前記制約は、法的制約、前記ルートの制約及び前記車両の制約のうちの１つ又はそれらの組み合わせを含み、
前記各ステップはプロセッサにおいて実行される、ルートに沿った運行中の車両の動きの運転曲線を、少なくとも、運行の連続空間における該車両の速度と該車両の位置との関数として求める方法。
【請求項３】
ルートに沿った運行中の車両の動きの運転曲線を、少なくとも、運行の連続空間における該車両の速度と該車両の位置との関数として求める方法であって、
前記連続空間から選択されたアンカー状態の集合に関してマルコフ決定過程(ＭＤＰ)を求めるステップであって、前記車両を或る状態に動かす制御が、前記連続空間におけるアンカー状態と前記状態との間の距離の関数として求められる確率で前記ＭＤＰを前記アンカー状態に遷移させるようにするものと、
制約を受ける前記ＭＤＰを解いて、前記車両の動きのコストを表すコスト関数を最適化するＭＤＰポリシーを求めるステップと、
前記ＭＤＰポリシーに基づいて前記運転曲線を求めるステップと、
を含み、
前記コスト関数は、前記運行中の前記車両のエネルギー消費及び総運行時間の双方を表し、前記運転曲線が前記車両のエネルギー消費と総運行時間との組み合わせを最適化するようにし、
前記ＭＤＰポリシーに基づいて前記運転曲線を求めることは、最近傍アンカー点法、最高投票点法及び最高予測利益法からなる群から選択される方法を用い、
前記各ステップはプロセッサにおいて実行される、ルートに沿った運行中の車両の動きの運転曲線を、少なくとも、運行の連続空間における該車両の速度と該車両の位置との関数として求める方法。
【請求項４】
ルートに沿って運行中の車両の動きを制御するシステムであって、
マルコフ決定過程(ＭＤＰ)曲線生成装置であって、前記車両の前記動きの連続空間から選択されたアンカー状態の集合に関してＭＤＰを求めるとともに、前記ＭＤＰを解いて、前記車両の前記動きのコストを表すコスト関数を最適化するＭＤＰポリシーを求めるものと、
前記ＭＤＰポリシーに基づいて運転曲線を生成する運転曲線生成装置と、
前記運転曲線に従って制御信号を生成する制御コンピューターと、
前記制御信号に基づいて前記車両に電力を供給する電源デバイスと、
を備え、
前記車両の前記動きの前記運転曲線をリアルタイムで求めるように構成される、ルートに沿って運行中の車両の動きを制御するシステム。
【請求項５】
ルートに沿って運行中の車両の動きを制御するシステムであって、
マルコフ決定過程(ＭＤＰ)曲線生成装置であって、前記車両の前記動きの連続空間から選択されたアンカー状態の集合に関してＭＤＰを求めるとともに、前記ＭＤＰを解いて、前記車両の前記動きのコストを表すコスト関数を最適化するＭＤＰポリシーを求めるものと、
前記ＭＤＰポリシーに基づいて運転曲線を生成する運転曲線生成装置と、
前記運転曲線に従って制御信号を生成する制御コンピューターと、
前記制御信号に基づいて前記車両に電力を供給する電源デバイスと、
を備え、
前記ＭＤＰ曲線生成装置が、
前記コスト関数は、前記運行中の前記車両のエネルギー消費及び総運行時間の双方を表し、前記運転曲線が前記車両のエネルギー消費と総運行時間との組み合わせを最適化するようにし、
前記ＭＤＰを求めるために、
前記車両を或る状態に動かす制御として、前記連続空間におけるアンカー状態と前記状態との間の距離の関数として求められる確率で前記ＭＤＰを前記アンカー状態に遷移させ、
前記連続空間における１組の段階を形成する１組の距離周期において前記車両の走行距離を分割し、
前記遷移を距離周期として求め、各制御が、システムを前の段階の前の状態から次の段階における次の状態に遷移させるようにし、
前記連続空間における各アンカー状態のロケーションが前記１組の段階からの或る段階にあるように前記アンカー状態の集合を選択する、
ルートに沿って運行中の車両の動きを制御するシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、車両の動きを最適化することに関し、より詳細には車両の最適運転曲線を求めることに関する。
【背景技術】
【０００２】
電車、空港における誘導輸送システム、又はハイブリッド自動車のエネルギー効率のよい動作等の多くの輸送問題は、ルートに沿った移動車両の速度プロファイルの最適化に帰着することができる。速度プロファイルは運転曲線と呼ばれる。ルートに沿った距離がｚによって表される場合、位置ｚにおける所望の速度ｖ(ｚ)は運転曲線を示す。運転曲線は、ルートの法的制約及び機械的制約、例えば速度制限、安全域等に従わなければならず、車両の機構によって物理的に実現可能でなくてはならない。
【０００３】
例えば、自動列車制御(ＡＴＣ)は、列車等の車両を制御する既知の方法である。ＡＴＣを用いると、列車の速度がルートの特定の区間にわたって指定の許容最大速度を超えたとき、ブレーキシステムが作動して、列車は減速される。運転曲線の決定は、速度制限に対する制約等の様々な制約に適応することが有利である。例えば、高速列車の速度は、所定の最大速度の段階的低減、すなわち８０ｋｍ／ｈ、６５ｋｍ／ｈ、４５ｋｍ／ｈ及び２５ｋｍ／ｈに従って調整することができる。列車が或る特定の区間にわたって所与の制限速度で走行することが必要とされる場合、許容最大速度は、その区間の目標制限速度に近づくように徐々に段階的に低減される。
【０００４】
しかしながら、最適運転曲線は、ルートの法的制約を単に順守することよりも多くの利点を提供するべきである。例えば、状況によっては、最適運転曲線は、例えばｚ＝０に位置する出発地と、例えばｚ＝Ｚに位置する目的地との間の運転時間を最小にするべきである。さらに、最適運転曲線は、ルートに沿って車両が消費する必要最小エネルギーを最小にするべきである。
【０００５】
通常、これらの２つの要件は互いに相反する。すなわち、運転時間が短くなると、より多くのエネルギーが必要となり、逆もまた同様である。このため、車両の最適運転曲線を求める方法及びシステムを提供する必要がある。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
この発明の様々な実施の形態の目的は、出発地から目的地までの運行中の車両の運転曲線を求めるシステム及び方法を提供することである。この発明のいくつかの実施の形態の更なる目的は、運行中の車両のエネルギー消費を最適化する運転曲線を求めることである。この発明のいくつかの実施の形態の更なる目的は、車両のエネルギー消費及び運行時間の双方を最適化する運転曲線を求めることである。この発明のいくつかの実施の形態の更なる目的は、所定の運行時間の車両のエネルギー消費を最適化する運転曲線を求めることである。
【０００７】
この発明のいくつかの実施の形態の更なる目的は、運転曲線の計算の計算複雑度を低減することである。この発明のいくつかの実施の形態の更なる目的は、最適運転曲線をリアルタイムで求めることである。この発明のいくつかの実施の形態の更なる目的は、運行中の車両の動きを制御する運転曲線を表す制御シーケンスを求めることである。
【課題を解決するための手段】
【０００８】
この発明のいくつかの実施の形態は、車両の運行の連続空間をマルコフ決定過程(ＭＤＰ)の形態で離散空間において変換することができ、それによって、離散空間におけるＭＤＰの解を用いて連続空間における運転曲線を求めることができるという認識に基づいている。特に、いくつかの実施の形態では、ＭＤＰは、ＭＤＰ及びベクトルの凸結合によって用いられる確率関数の数学特性が類似しているという別の認識に基づいて構築される。そのような認識は、実施の形態によってＭＤＰを求めるのに用いられる。特に、実施の形態は、車両を連続空間における或る状態に動かす制御動作が、ＭＤＰの離散状態と連続空間における状態との間の距離の関数として求められる確率でＭＤＰをＭＤＰの離散状態に遷移させるという原理を用いる。
【０００９】
ＭＤＰの解は、コスト関数を最適化するＭＤＰポリシーを求める。様々な実施の形態において、コスト関数に対する解は、法的制約、ルートの制約、及び車両の制約のうちの１つ又はそれらの組み合わせを含む制約を受ける。また、コスト関数は、運行中の車両の動きのコストを表す。ＭＤＰポリシーに基づいて求められた運転曲線はそのコストを最適化する。
【００１０】
したがって、様々な実施の形態が、コスト関数を変動させて実施の形態の特定の目的を達成する。例えば、１つの実施の形態では、コスト関数は運行中の車両のエネルギー消費を表し、運転曲線はエネルギー消費を最適化する。それに加えて又は代替的に、様々な実施の形態において、コスト関数はエネルギー消費及び運行時間の双方を表すか、又は所定の運行時間のエネルギー消費を表す。
【００１１】
さらに、本明細書における出願人は、ＭＤＰの使用によって運転曲線計算の複雑度が低減するが、車両の運行中にリアルタイムで用いられるのに常に十分高速であるとは限らないことを概ね認識している。これは、ＭＤＰによってはＭＤＰの状態への自己遷移を有し、結果としてＭＤＰを解く反復手法が必要となることに起因する。しかしながら、出願人らは、ＭＤＰを埋め込むように連続空間を特殊サンプリングすることによって、自己遷移問題を取り除き、計算複雑度を低減することができることを更に認識している。
【００１２】
例えば、１つの実施の形態は、等距離ＭＤＰ状態サンプリングを用い、ここでＭＤＰの状態は、連続空間における複数の垂直ライン上に位置し、複数の状態が同じ距離座標を有するようになっている。そのような状態は段階を形成し、状態遷移は、連続した段階間でのみ生じ、例えば後方動的計画法によってリアルタイムに解くことが可能になる。
【００１３】
別の実施の形態は３次元サンプリングを用い、ここで所定の運行時間のＭＤＰは、タイムスライスに編成された、複数の時間ステップの三角形分割のレプリカを含む。各遷移は１つのタイムスライスから次のタイムスライスへのものであり、これによって自己遷移問題が取り除かれる。
【００１４】
したがって、この発明の１つの実施の形態は、車両の動きの運転曲線を、連続空間における車両の速度と車両の位置との関数として求める方法を開示する。本方法は、連続空間から選択されたアンカー状態の集合に関してＭＤＰを求めることであって、車両を或る状態に動かす制御が、連続空間におけるアンカー状態と上記状態との間の距離の関数として求められる確率でＭＤＰをアンカー状態に遷移させるようにすることと、制約を受けるＭＤＰを解いて、車両の動きのコストを表すコスト関数を最適化するＭＤＰポリシーを求めることと、ＭＤＰポリシーに基づいて運転曲線を求めることと、を含む。
【００１５】
別の実施の形態は、システムの状態変数によって定義される連続空間において、システムを初期状態から最終状態に遷移させる制御の最適シーケンスを求める方法を開示する。最適シーケンスは少なくとも１つの状態変数にわたって単調増加し、システムは、前の状態と制御の離散集合との動的関数によって定義される状態を有する動的システムであり、遷移ごとに、制御が制御の離散集合から選択され、制御ごとに、動的関数が遷移ステップにわたってシステムを前の状態から次の状態へ遷移させるようにする。本方法は、連続空間から選択されたアンカー状態の集合に関してマルコフ決定過程(ＭＤＰ)を求めることであって、制御の離散集合からの各制御が、連続空間における或る状態のロケーションに対する連続空間における次のアンカー状態のロケーションに基づいて求められた確率で、前記ＭＤＰを或るアンカー状態から次のアンカー状態に遷移させるようにし、アンカー状態と対応する制御との動的関数がシステムを遷移させることと、ＭＤＰを解いて、アンカー状態ごとの最適制御を定義するＭＤＰの最適ポリシーを求めることと、最適ポリシーに基づいて連続空間における制御の最適シーケンスを求めることと、を含む。
【００１６】
また別の実施の形態は、車両の動きを制御するシステムを開示する。本システムは、車両の動きの連続空間から選択されたアンカー状態の集合に関してＭＤＰを求めるとともに、ＭＤＰを解いて、車両の動きのコストを表すコスト関数を最適化するＭＤＰポリシーを求める、マルコフ決定過程(ＭＤＰ)曲線生成装置と、ＭＤＰポリシーに基づいて運転曲線を生成する運転曲線生成装置と、運転曲線に従って制御信号を生成する制御コンピューターと、制御信号に基づいて車両に電力を供給する電源デバイスと、を備える。本システムは、車両の動きの運転曲線をリアルタイムで求めるように構成することができる。
【図面の簡単な説明】
【００１７】
【図１Ａ】この発明のいくつかの実施の形態による、車両の運転曲線を求めるシステムのブロック図である。
【図１Ｂ】図１Ａのシステムによって求められる運転曲線の例である。
【図２】この発明のいくつかの実施の形態による、車両の動きの連続空間にマルコフ決定過程(ＭＤＰ)を埋め込む概略図である。
【図３】この発明のいくつかの実施の形態による、ＭＤＰを用いて運転曲線を求める方法のブロック図である。
【図４】この発明の実施の形態による、連続状態から離散状態に変換するプロセスのブロック図である。
【図５】この発明の実施の形態による、選択された連続状態を表す三角形をトラバースするプロセスのブロック図である。
【図６】この発明の実施の形態による、連続状態を三角形分割するプロセスの概略図である。
【図７Ａ】自己遷移を有しないＭＤＰの概略図である。
【図７Ｂ】この発明の実施の形態による等距離(ＥＤ)ＭＤＰ法の概略図である。
【図８Ａ】終了時点が固定の車両の運行の運転曲線を求める方法の概略図である。
【図８Ｂ】終了時点が固定の車両の運行の運転曲線を求める方法の概略図である。
【図８Ｃ】終了時点が固定の車両の運行の運転曲線を求める方法の概略図である。
【発明を実施するための形態】
【００１８】
システム概観
図１Ａは、この発明のいくつかの実施の形態による車両１１０の運転曲線を求めるシステムを示している。本開示において、「車両」という用語は包括的に用いられ、限定ではないが、電車、空港における誘導輸送システム、又はハイブリッド自動車等の任意の輸送手段を含む。この非限定的な例において、車両１１０は電車であり、電力が変換され、ブレーカーを介して給電線又は地上コイル(ＧＣ)に供給される。
【００１９】
車両１１０の制御システム１０１は、マルコフ決定過程(ＭＤＰ)曲線生成装置１、運転曲線生成装置３、電源デバイス５及び制御コンピューター７のうちの１つ又はそれらの組み合わせを含むことができる。制御システムは、車両の動きの運転曲線を、ルートに沿った車両の運行の連続空間における車両の速度と車両の位置との関数として求める。
【００２０】
様々な実施の形態において、運転曲線は、運行中に車両に適用される制御シーケンスによって表される。制御システムの実装は、車両の回路内で実行することができ、遠隔管制センター１２０において実行することができ、及び／又は車両と管制センターとの間で分散させることができる。車両と管制センターとの間の通信は、無線送受信機１１〜１３を用いて達成することができる。プロセッサを用いて、制御システムの様々なコンポーネント及びモジュールを実装することができる。
【００２１】
ＭＤＰ曲線生成装置は、連続空間から選択されたアンカー状態の集合に関してＭＤＰを求め、このＭＤＰを解いて、車両動きのコストを表すコスト関数を最適化するＭＤＰポリシー１１１を求める。例えば、様々な実施の形態において、コスト関数は、運行中の車両のエネルギー消費、運行時間、エネルギー消費及び運行時間の双方、又は所定の運行時間のエネルギー消費のうちの１つ又はそれらの組み合わせを表す。
【００２２】
図１Ｂに示すように、運転曲線生成装置３は、出発地１４２から目的地１４４までＭＤＰポリシーに基づいて運転曲線１１３を生成する。いくつかの実施の形態では、運転曲線は車両の動きを規定する制御シーケンスによって表される。
【００２３】
１つの実施の形態では、シーケンス内の各制御は、加速制御１５２と、減速制御１５４と、一定速度運転制御１５６と、惰行制御１５８とを含む離散制御集合から選択される。また、様々な実施の形態において、ＭＤＰ及び／又は運転曲線１１３に対する解は、法的制約、ルートの制約及び車両の制約のうちの１つ又はそれらの組み合わせを含む制約を受ける。制約及びコスト関数は、管制センターによって提供することができる(１２５)。制約の例には、速度制限制約(speed limit constraint)１３０及び速度規制制約(speed restriction constraint)１３５が含まれる。
【００２４】
電源デバイス５は、列車を駆動する地上コイルＧＣに電力１１５を供給する。制御コンピューター７は、運転曲線１１３に従って電源デバイス５を制御する制御信号１１７を生成する。
【００２５】
問題の定式化
この発明のいくつかの実施の形態は、運転曲線最適化を最適制御問題として定義することができ、それによって、最適運転曲線の問題が、運行時間基準及び運行エネルギー基準を例えば同時に最適化するように低減されるという認識に基づく。
【００２６】
車両の動特性は通常、以下の式に従って、時点ｔにおけるルートに沿った車両の相対位置ｚ(ｔ)と車両の速度ｖ(ｔ)とを指定する１組の微分方程式によって表すことができる。
【００２７】
【数１】
0005905094.tif 000002
【００２８】
ここで、関数ａ(ｚ，ｖ，ｕ)は、速度ｖで移動している間、位置ｚの車両に動作ｕが加えられたときの車両の加速を示す。関数ａは、車両の質量及び速度で表されるような車両の慣性、ロケーションｚにおけるルートの傾き(勾配)、及び速度ｖにおける空気抵抗を組み込む。
【００２９】
車両の状態がベクトルｘ＝［ｚ，ｖ］Ｔである場合、車両の動特性は、ベクトル値方程式
【００３０】
【数２】
0005905094.tif 000003
【００３１】
によって表すことができる。動的関数ｆは、車両の動きの様々な制約を組み込む。例えば、車両の速度は速度制限を超えるべきでない。
【００３２】
車両によって消費される瞬時電力は、関数ｐ(ｚ，ｖ，ｕ)によって表される。この関数は、位置、速度及び適用される制御に依拠するが、その他の点では時間非依存である。回生ブレーキが用いられるとき、関数ｐ(ｚ，ｖ，ｕ)は負になることもでき、車両によって生成されエネルギー源に返されるエネルギーを表す。例えば、電車の場合、エネルギー源は線路の上方のカテナリー電力ケーブルである。所与の制御軌道ｕ(ｔ)，０≦ｔ≦Ｔの結果として以下の総エネルギー消費が生じる。
【００３３】
【数３】
0005905094.tif 000004
【００３４】
ここで、Ｔは運行の終了時点であり、すなわち、車両が意図される目的地に到達する時点である。
【００３５】
実施の形態は、運行の終了時点Ｔが固定であるか否かに依拠して運転曲線最適化問題の様々な定式化を用いる。
【００３６】
定式化ＶＴＴ(可変終了時点)
終了時点Ｔは固定でなく、実施の形態の目的は、重みμ，０≦μ≦１についてエネルギー及び時間の加重和Ｊ＝μＥ＋(１−μ)Ｔを最小にすることである。重みは経済的考慮事項、例えば車両の全乗客に対する、エネルギー単位の相対コスト対時間単位の相対コストに従って選択することができる。
【００３７】
定式化ＦＴＴ(固定終了時点)
終了時点Ｔは固定であり、事前に指定され、実施の形態の目的はエネルギーＪ＝Ｅを最小にすることである。この定式化は、出発地と目的地との間の運行が最大でＴの時間単位までかかり得るときに有用とすることができる。
【００３８】
双方の場合に、実施の形態は関数ｕ(ｔ)，０≦ｔ≦Ｔを求める。この関数は、車両の動特性
【００３９】
【数４】
0005905094.tif 000005
【００４０】
並びに制約及び条件ｚ(０)＝０、ｚ(Ｔ)＝Ｚ、ｖ(０)＝ｖ(Ｔ)＝ｖ(Ｚ)＝０及び０≦ｖ(ｚ)≦ｖｍａｘ(ｚ)を条件として車両の動きのコストＪを最小にする。ここで、Ｚは出発地と目的地との間の距離であり、ｖｍａｘ(ｚ)はロケーションｚ(ｔ)の速度制限である。
【００４１】
双方の定式化ＶＴＴ及びＦＴＴが最適制御問題を表し、最適関数ｕ(ｔ)は、ハミルトン−ヤコビ−ベルマン(ＨＪＢ)方程式として知られる以下の式１を解くことによって求めることができる。状態ｘにおいて制御ｕが適用されるときに生じる瞬時コストをｃ(ｘ，ｕ)として定義し、最終目的地までの最適累積到達コスト(optimal cumulative cost−to−go)をＶ(ｘ，ｔ)として定義した場合、ＨＪＢ方程式は、以下の式に従って状態空間においてＶの時間微分を瞬時コストｃ及びＶの勾配に関係付ける。
【００４２】
【数５】
0005905094.tif 000006
【００４３】
ここで、勾配∇Ｖ(ｘ，ｔ)は状態変数に関するＶ(ｘ，ｔ)の全ての空間微分のベクトルであり、この場合ｚ及びｖである。定式化ＶＴＴの場合、直接コスト関数ｃ(ｘ，ｕ)は
【００４４】
【数６】
0005905094.tif 000007
【００４５】
として定義され、定式化ＦＴＴの場合、
【００４６】
【数７】
0005905094.tif 000008
【００４７】
として定義される。
【００４８】
ＨＪＢ方程式は、解析的に解くことがほとんど不可能な偏微分方程式(ＰＤＥ)である。特に運転曲線最適化の場合、解析解は利用可能でないようであり、代わりに数値法を適用しなくてはならない。ＰＤＥを解く従来の方法は、有限差分又は有限要素によって数値離散化を実行し、続いて多次元問題又はコロケーションについてガラーキン法、レイリー−リッツ法等の解決手順を実行することである。一般に、ＨＪＢ方程式に対する直接解を実施し検証することは困難であり、結果として計算が長引く。
【００４９】
したがって、実施の形態は、以下に説明するように、マルコフ決定過程に基づいて代替的な解法を用いる。
【００５０】
運転曲線計算についてのマルコフ決定過程
図２は、車両の動きの連続空間においてＭＤＰを埋め込む概略図を示している。様々な実施の形態は、車両１１０の動きの連続空間２００から選択されたアンカー状態の集合２１０に関してＭＤＰを求める。通常、連続空間は車両の速度Ｖと車両の位置Ｚとの関数として定義される。連続空間の他の定義が可能である。制御２２０、例えば加速又は減速は、連続空間において車両を状態ｙ２２５に移す。しかしながら、実施の形態は、制御２２０がＭＤＰをアンカー状態、例えばアンカー状態ｐ２２１０’にも遷移させるという認識を用いている。その遷移の確率は、連続空間におけるアンカー状態２１０’と状態２２５との間の距離２３０の関数として求められる。
【００５１】
したがって、実施の形態は、連続状態空間問題をマルコフ決定過程(ＭＤＰ)の形態で表し、ＭＤＰを、例えば動的計画法、値反復、又はポリシー反復によって解く。ＭＤＰの遷移空間はタプル(Ｓ，Ａ，Ｐ，Ｒ)によって示される。離散空間は、任意の時点ｔｋにおいてＭＤＰがＮ個の状態ｓ(ｉ)∈Ｓ，１≦ｉ≦Ｎのうちの１つｓｋ∈Ｓを占有するような、これらの状態の離散集合Ｓと、任意の所与の時点において適用することができるＬ個の動作ｕ(ｌ)∈Ｕ，１≦ｌ≦Ｌの集合Ｕとを含む。開始状態ｓ０は既知であり固定である。遷移確率関数Ｐは、ＭＤＰが時点ｔｋにおいて状態ｓｋ＝ｓ(ｉ)にあり、かつその時点において制御(動作)ｕｋ＝ｕ(ｌ)が適用された場合に、時点ｔｋ＋１において状態ｓｋ＋１＝ｓ(ｊ)にある確率
【００５２】
【数８】
0005905094.tif 000009
【００５３】
を表す。同様に、報酬関数Ｒは、時点ｔｋにおいて動作ｕｋ＝ｕ(ｌ)を状態ｓｋ＝ｓ(ｉ)に適用する報酬(又はコスト)
【００５４】
【数９】
0005905094.tif 000010
【００５５】
を表す。ＭＤＰは規則的な時間間隔(例えば、ｔｋ＝ｋΔｔ)で生じることができるか、又は属する固定の持続時間を有しないことができる離散決定期間において展開する。ＭＤＰの解は以下の式に従って性能尺度を最適化する。
【００５６】
【数１０】
0005905094.tif 000011
【００５７】
図３は、ＭＤＰを用いて運転曲線を求める方法のブロック図を示している。ＭＤＰは離散状態空間を有し、離散決定期間(discrete decision epoch)において展開するので、実施の形態は連続空間２００の一連の離散化３１０を用い、これによって問題をＭＤＰ法に従わせる。第１の離散化３２０は車両に適用することができる利用可能な制御の集合に関する。所与の瞬間において、いくつかの実施の形態は、以下の４つ、すなわち、加速(ｕ１)、減速(ｕ２)、一定速度運転(ｕ３)及び車両自体の推進力に起因する運動である惰行(ｕ４)のうちの１つに対する制御を制限する。そのような制限は、輸送システムに一般的なようであり、結果として制御の最適シーケンスの表現がコンパクトになる。一方、代替的な制御離散化が可能であり、この発明の範囲内にある。
【００５８】
第２の離散化３３０は、車掌の連続状態及び連続時間動特性を離散化し、ＭＤＰの離散状態空間を作成する。様々な実施の形態が、問題の定式化、例えばＶＴＴ又はＦＴＴ、及びＭＤＰの解法に依拠して異なる離散化方法３３０を用いる。これらの方法の例が以下に説明される。
【００５９】
ＭＤＰの解３５０によって、コスト関数３５５を最適化するＭＤＰポリシー１１１が決まる。様々な実施の形態において、法的制約、ルートの制約、車両の制約のうちの１つ又はそれらの組み合わせを含む制約を条件として解が求められる。また、コスト関数は、運行中の車両の動きのコストを表し、ＭＤＰポリシーに基づいて求められる運転曲線はコストを最適化する。したがって、様々な実施の形態は、コスト関数を変動させて実施の形態の特定の目的を達成する。例えば、１つの実施の形態において、コスト関数は運行中の車両のエネルギー消費を表し、運転曲線はエネルギー消費を最適化する。さらに又は代替的に、様々な実施の形態において、コスト関数はエネルギー消費及び運行時間の双方を表すか、又は所定の運行時間のエネルギー消費を表す。
【００６０】
ＭＤＰポリシーは離散空間における最適制御ポリシーを表す。したがって、実施の形態は、最適ポリシーに基づいて連続空間における運転曲線１１３を求め(３６０)、例えば埋め込まれたＭＤＰの離散状態と反対に、移動車両の連続状態ｘからのマッピングである制御法則ｕ＝ρ(ｘ)を求める。
【００６１】
いくつかのマッピング方法が実施の形態によって用いられる。例えば、最近傍アンカー点３７２法は、例えばユークリッド距離の観点で、埋込み連続空間におけるｘに最も近いアンカー状態ｘ(ｉ)を求め、対応するＭＤＰ状態ｓ(ｉ)：ｕ＝π＊(ｓ(ｉ))の最適制御を用いる。
【００６２】
代替的に、最高投票点法(largest vote method)３７４が、連続状態ｘを含むシンプレックスｍを求め、そのシンプレックスの３つの頂点ｖｍ，ｊ，ｊ＝１，３に関して状態ｘの重心座標ｃを求める。ｕｊ＝π＊(ｓ(ｊ))である場合、ここでｓ(ｊ)は頂点ｖｍ，ｊに対応する状態であり、重心座標ｃｊは制御ｕｊに対する個々の投票として用いられ、最適制御シーケンスは、３つ全ての頂点にわたって最高累積投票点を有する動作を含む。
【００６３】
また、最高予測利益法(highest expected merit method)３７６は、重心座標を用いて、状態ｘにおいて得られる個々の制御ｕの利益
【００６４】
【数１１】
0005905094.tif 000012
【００６５】
を
【００６６】
【数１２】
0005905094.tif 000013
【００６７】
として推定し、制御法則
【００６８】
【数１３】
0005905094.tif 000014
【００６９】
を用いる。重心座標ｃをＭＤＰがその離散状態のうちの１つにある個々の確率として解釈することができることを所与とすると、関数
【００７０】
【数１４】
0005905094.tif 000015
【００７１】
は、連続状態ｘにおいて制御動作ｕをとる予測利益である。
【００７２】
ＭＤＰポリシーに基づいて運転曲線を求める他の変形形態も可能であり、この発明の範囲内にある。
【００７３】
連続状態離散化
ＶＴＴの場合の等時点ＭＤＰ
ＶＴＴ離散化方法の場合の等時点ＭＤＰにおいて、時間は長さΔｔの一定の時間間隔において離散化され、それによって決定及び状態遷移は時点ｔｋ＝ｋΔｔにおいて発生する。ここでｋは整数である。したがって、図２の制御２２０は固定の時間期間にわたってシステムを遷移させる。車両の動きの方程式は、１つの時間間隔にわたって順方向の時間で積分し、その時間間隔の終了時点において、初期状態ｘｋ＝ｘ(ｔｋ)から、以下のように後続状態の１組の差分方程式を得ることができる。
【００７４】
【数１５】
0005905094.tif 000016
【００７５】
制御動作ｕｋ２２０は、時間ステップ全体にわたって一定のままであるが、連続状態ｘ(ｔ)，ｔｋ≦ｔ≦ｔｋ＋１は、ｘｋからｘｋ＋１まで平滑な軌道を辿る。上記で説明したように、状態変数のうちの一方又は双方がこの積分中に限界に到達する場合、これらの変数は限界範囲内に留まるべきである。
【００７６】
積分方法は、厳密計算法(exact)又は数値計算法(numerical)のいずれかとすることができる。例えば、順方向オイラー積分法が用いられる場合、いくつかの実施の形態によって、以下の１組の近似動的方程式が用いられる。
【００７７】
【数１６】
0005905094.tif 000017
【００７８】
ここで、αｋは車両の加速であり、βｋは減速であり、ともに選択された動作ｕｋに従い、γｋはルートの傾き、空気抵抗及び車輪摩擦に起因する加速／減速である。積分の時間ステップも異なることができ、例えば時間間隔Δｔよりも小さくすることができ、この場合、Δｔに等しい総持続時間で複数の積分ステップが行われる。
【００７９】
同様に、１つの期間中に被る直接コストＣ(ｘｋ，ｕｋ)は、その期間にわたる瞬時コストｃ(ｘ，ｕ)の積分である。そのコストのエネルギー部分は、以下の式となる。
【００８０】
【数１７】
0005905094.tif 000018
【００８１】
一般的な場合、エネルギーは２つの成分、すなわち駆動力成分ｇ(ｘｋ，ｕｋ)及び回生成分ｈ(ｘｋ，ｕｋ)を有し、ｅ(ｘｋ，ｕｋ)＝ｇ(ｘｋ，ｕｋ)−ｈ(ｘｋ，ｕｋ)である。駆動力成分はｇ(ｘｋ，ｕｋ)＝ｍαｋｖｋΔｔ／ξｋとして定義され、ｍは車両の質量であり、ξｋ＜１はモーターによる電気エネルギーから機械エネルギーへの変換効率である。散逸ブレーキが用いられるとき、車両の運動エネルギーは熱に変換され、回生成分はゼロ：ｈ(ｘｋ，ａｋ)になる。回生制動(braking)が用いられるとき、モーターは発電機として機能する。
【００８２】
生成されるエネルギーは、カテナリー電力ケーブルを介して電力網に返されるか、又はバッテリーに格納される。回生成分は
【００８３】
【数１８】
0005905094.tif 000019
【００８４】
として定義され、ここで、ｘｋ＜１は、発電機として用いられるモーターが機械エネルギーを電気エネルギーに変換する効率である。ほとんどの場合に、同じ状態ｘｋについて、ｘｋ＜ξｋである。
【００８５】
ＶＴＴの定式化において、直接コストは時間成分も有し、これは(１−μ)Δｔに等しく、以下のようになっている。
【００８６】
【数１９】
0005905094.tif 000020
【００８７】
車両動特性とＭＤＰとの間の類似性は、双方が小数の離散動作の影響下で離散時間において展開し、双方が状態及び動作にわたって定義される性能判断基準を最適化しようとすることである。
【００８８】
２つの主要な差異は、用いられる状態のタイプ(連続ｘ∈Ｒ２対離散ｓ∈Ｓ)、及び状態展開がどのように表されるか(関数Ｆ(ｘ，ａ)対確率遷移関数Ｐｉｊｌ)である。このとき、変換方法の目的は、全ての３つ組(ｓ(ｉ)，ｓ(ｊ)，ｕ(ｌ))について、Ｒ２に埋め込まれた状態集合Ｓ及び遷移関数Ｐｉｊｌを構築することである。ＭＤＰが構築された後、ポリシー反復及び／又は値反復法等の様々な方法を用いることによって、全てのｓ(ｉ)∈Ｓについて状態を最適な制御にマッピングする最適ポリシーｕ＝π(ｓ(ｉ))を求めることができる。
【００８９】
いくつかの実施の形態は、確率関数及び凸結合の数学的特性における類似性を用いる。確率関数(確率密度関数と区別するために確率質量関数と呼ばれることもある)は、確率変数が或る特定の値に等しい確率を特定する。ＭＤＰの場合、遷移関数はそのような(条件付き)確率質量関数であり、開始状態ｓｋ＝ｓ(ｉ)及び適用される制御ｕｋ＝ｕ(ｌ)を条件とする。確率関数が特定される確率変数は、後続の状態ｓｋ＋１である。状態集合ＳのサイズがＮである場合、ｓ(１)、ｓ(２)、…、ｓ(Ｎ)を、全ての状態を列挙したものとする。このとき、遷移関数の要素は以下のように定義することができる。
【００９０】
【数２０】
0005905094.tif 000021
【００９１】
確率質量関数の公理的特性から、以下であることは常に真である。
【００９２】
【数２１】
0005905094.tif 000022
【００９３】
他方で、Ｎ個のベクトルｙｊ，ｊ＝１，Ｎの凸結合は以下のように定義される。
【００９４】
【数２２】
0005905094.tif 000023
【００９５】
２つの定義を比較することによって、本出願人らは、確率質量関数と凸結合を定義する係数の集合とが正確に同じ制約に従うこと、及び有効な確率関数を有効な凸結合の係数として用いることができ、逆もまた同様であることを認識した。実施の形態はこの認識を用いて、ＭＤＰの全ての遷移関数を、適切に定義された凸結合の係数の集合として構築する。
【００９６】
ＭＤＰを求める
図４〜図６は、車両１１０等の動的システムの連続空間からＭＤＰを求める例を示している。様々な実施の形態において、制御シーケンスはシステムの状態変数によって定義された連続空間において、動的システムを初期状態から最終状態に遷移させる。最適シーケンスは、少なくとも１つの状態変数、例えば運行距離にわたって単調増加する。動的システムの状態は、前の状態と制御の離散集合との動的関数によって定義される。遷移ごとに、制御の離散集合から制御が選択され、それによって、制御ごとに、動的関数が遷移ステップにわたってシステムを前の状態から次の状態に遷移させる。
【００９７】
動的システムは、連続状態ｘ(ｉ)４０１の集合Ｘを有する。各状態はｄ次元ベクトルによって表すことができる。方法は集合ＸからＮ個の連続状態ｘ(ｉ)４１１を選択し(４１０)、各状態ｘ(ｉ)が集合Ｓ内のＮ個の離散状態ｓ(ｉ)に対応し、ＭＤＰ状態４０９を形成するようにする。この選択は、連続状態空間を均一に及びランダムにサンプリングすることができる。選択された状態はｄ×Ｎの行列Ｂ４１２に記憶され、各列は選択された状態のうちの１つである。
【００９８】
１つの実施の形態において、ドロネー三角形分割ＤＴ(Ｘ)が集合に適用される(４２０)。三角形分割によってＭ個の三角形ｍが生成される。三角形は、行列Ｄ４２１に記憶され、ここで各列は三角形に対応し、３つの行は三角形の頂点に対応する。
【００９９】
シンプレックス
通常、各三角形は、より一般的な用語シンプレックスに置き換えることができる。シンプレックスは、任意の次元ｄの状態空間Ｘ内の三角形の一般化である。例えば、次元数ｄ＝２の場合、シンプレックス(又は三角形)内の頂点の数はｄ＋１＝３であり、ｄ＝３の場合、シンプレックスはｄ＋１＝４個の頂点を有する四面体である。
【０１００】
図５に示すように、状態ｓは一度に１つの状態ずつ変換される(５００)。状態ｓ(ｉ)５０３ごとに、対応する状態ｘ(ｉ)４０１及び制御ａ(ｌ)４０２が取り出され(５１０)、これらを用いて次の状態ｙ＝ｆ(ｘ(ｉ)，ａ(ｌ))５０４が求められる(５１０)。ここで、ｆは連続状態空間システムの展開を表す任意の非線形関数である。図５は、或る動作ａについてｉ＝０及びｙ＝ｆ(ｘ(０)，ａ)である場合の事例を示している。
【０１０１】
図６について示すように、次の状態ｙ２２５は選択された状態ｘ(ｉ)のいずれとも一致しない。次の状態ｙ２２５を含むＤＴ(Ｘ)における特定の三角形ｍ２４０は、Ｍ個全ての三角形をトラバースすることによって位置特定される(６００)。
【０１０２】
現在の三角形ｍについて、三角形ｍの最後の頂点ｖｍ，ｄ＋１が取り出され、ベクトルｑに記憶される(６１０)。ｄ×ｄの差分行列Ｅ６２１が構築される(６２０)。行列Ｅにおいて、列ｊはｊ＝１，ｄについて差分ｖｍ，ｊ−ｑを含む。１組の連立一次方程式を解くことによって、Ｅｃ＝(ｙ−ｑ)となるようなｄ次元ベクトルｃが求められる。
【０１０３】
ベクトルｃの最終要素ｃｄ＋１６４１が
【０１０４】
【数２３】
0005905094.tif 000024
【０１０５】
として求められる(６４０)。全ての要素ｃｊ，ｊ＝１，ｄ＋１について、ｃｊが負であるか否か、すなわちｃｊ＜０であるか否かが試験される。真である場合、三角形ｍは状態ｙを含まず、ｍをインクリメントし、次の三角形について繰り返す。
【０１０６】
そうではなく、全てのｃｊが正である場合、三角形ｍは状態ｙを含む。ステップ５２０において、ｄ＋１次元ベクトルｃは、
【０１０７】
【数２４】
0005905094.tif 000025
【０１０８】
となるような有効な凸結合を定義する係数を含む。したがって、ベクトルｃは、その全てのエントリが非負であり、合算すると１になるので、有効な確率遷移関数を定義する。
【０１０９】
全ての可能なＮ個の次の状態について完全な遷移確率分布を構築するために、離散状態ｓ(ｌ)，ｌ＝１，Ｎごとに以下のステップが実行される。
【０１１０】
状態ｓ(ｌ)が三角形ｍの頂点のうちの１つに対応する場合、すなわち、或るｊについてｘ(ｌ)＝ｖｍ，ｊ５３０である場合、ＭＤＰの対応する遷移確率ｐｌ２３０は
【０１１１】
【数２５】
0005905094.tif 000026
【０１１２】
となり(５３１)、そうでない場合、ｐｌ＝０となる(５３２)。
【０１１３】
概念上、関数ｆによって表される動的システムは、動的システムの連続状態Ｘに埋め込まれる離散状態ｓ(ｉ)の小さな集合のみを伴う確率表現に等しい。
【０１１４】
システムがこれらの状態のうちの１つにおいて開始する場合、次の状態ｙは一般に、これらの状態のうちの別の状態と一致しない。三角形の頂点を定義するｄ＋１個の状態は、次の状態ｙを完全に取り囲む。すなわち、システムは状態ｙに遷移したのではなく、様々な確率を有する対応する三角形の頂点に遷移した。
【０１１５】
確率は、状態ｙを含む三角形の頂点に関する状態ｙの凸分解に等しい。これらの確率は、取り囲む三角形の頂点に関する状態ｙの重心座標とみなすことができる。これは、ＭＤＰに関する凸結合と確率質量関数との類似性によって可能にされる。
【０１１６】
処理時間を減らすために、行列Ｅの逆行列Ｅ−１を、ドロネー三角形分割における全ての三角形について記憶することができ、次に、ステップ３３０においてこれを用いて、各反復において１組の線形方程式を解くのではなく、
【０１１７】
【数２６】
0005905094.tif 000027
【０１１８】
を求める。
【０１１９】
いくつかの実施の形態では、ドロネー三角形分割の三角形のトラバースは、次の状態ｙを取り囲む三角形が現在の状態の三角形の近くにあるという認識に基づいて改善される。現在の状態と各三角形の重心との間の距離が所定である場合、ドロネー三角形分割の三角形は、距離の昇順でトラバースすることができる。
【０１２０】
等時点ＭＤＰを解く
いくつかの実施の形態は、値反復手順を用いてＭＤＰを解く。この手順は、値関数Ｖ(ｓ)が収束するまでＭＤＰの状態空間全体にわたる複数回のパスにおいて以下の割り当てを実行することを含む。
【０１２１】
【数２７】
0005905094.tif 000028
【０１２２】
単一のそのような割り当ては、ベルマンバックアップとして知られ、状態ｓごとに最大で３つの可能な後続状態ｓ’しか存在しないので、計算的に単純である。これらの値反復ステップ中、目的地の駅に対応する最終状態の値は一定に保持され、或る適切な値、例えばゼロに等しい。値関数が収束した後、値関数は式２を等式として満たす。その後、ＭＤＰの最適ポリシーをπ＊(ｓ)＝ａｒｇｍａｘｕＱ(ｓ，ｕ)として求めることができ、ここで以下の補助関数を利用する。
【０１２３】
【数２８】
0005905094.tif 000029
【０１２４】
ＶＴＴの場合の等距離ＭＤＰ
等時点(ＥＴ)ＭＤＰ法は、値反復手順を用いる必要性に起因して比較的低速である。この必要性は、ＭＤＰの遷移グラフにおけるサイクルから生じる。例えば、１つの三角形の頂点ｘ(ｉ)からの遷移の結果、同じ三角形となる場合、結果として得られるＭＤＰはこの頂点に対応する状態ｓ(ｉ)の自己遷移を有する。このため、その状態の対応するベルマン方程式は、式の両辺にＶ(ｓ(ｉ))を含み、結果として固定点への反復が得られる。
【０１２５】
したがって、全ての状態ｓのベルマン方程式が、右辺において、状態ｓよりも順序が下位の後続状態のみを含むように状態が線形に順序付けされるＭＤＰを構築する必要がある。そのようなＭＤＰは、最下位の要素から開始し、最高位の要素へと後方に進んで、状態ごとに単一のベルマンバックアップのみを用いて解くことができる。明らかに、自己遷移を有するＭＤＰはそのような順序付けを有していない。しかしながら、上記で説明した等時点制御動作ではなく、等距離の制御動作に基づいて構築されたＭＤＰはそのような線形順序付けを有する。
【０１２６】
図７Ａは、等距離(ＥＤ)ＭＤＰ法に基づいて求められた自己遷移を有しないＭＤＰ７００を示している。図７Ｂは、ＭＤＰ７００を求める方法の例を示している。移動車両の連続空間(ｚ，ｖ)におけるルートｚは、複数の垂直線７１０ｚ＝ｚｊによって分割され、これらのラインのそれぞれは、同じ座標ｚを有するＭＤＰの複数のアンカー状態７１５を含む。ＭＤＰの制御規則も変更され、すなわち、各遷移７２０は、或るラインインデックスｊ及び速度ｖの場合に座標［ｚｊ，ｖ］を有する状態７３０において開始し、距離座標が次のライン、すなわちｚ＝ｚｊ＋１において終了状態ｙ７４０に達するまで制御動作ｕが実行される。遷移の持続時間７２５は、開始状態及び制御動作に従って変動する。
【０１２７】
ＥＤ法に起因して、終了状態ｙの重心座標への分解の結果、３つの座標の場合、最大で２つの非ゼロ値、すなわちｐ２及びｐ３が得られる。なぜなら、終了状態ｙは、常に状態空間のドロネー三角形分割における三角形の辺のうちの１つの上にあるためである。同等に、重心座標がＭＤＰの遷移確率として解釈されるとき、遷移は常にラインｚｊ上の状態において開始し、ラインｚｊ＋１上の１つ又は２つの状態において終了し、これはＭＤＰが自己遷移を有しないことを意味する。
【０１２８】
いくつかの実施の形態は、走行距離の連続空間を、連続空間において１組の段階を形成する１組の距離周期に分割する(７５０)。アンカー状態の集合は、連続空間内のアンカー状態のロケーションが、１組の段階からの一段階にあるように、すなわち、ラインｚｊ上にある状態が段階ｊを形成するように選択される(７７０)。結果として得られるＭＤＰは一連の段階に分解され、車両は各決定ステップにおいて段階間を移動する。すなわち、遷移のステップは、各制御によってシステムが前の段階の前の状態から次の段階の次の状態に遷移するように、距離の関数として求められる(７６０)。次に、最後の段階から開始して、時間において後方に進んで、段階ごとにベルマンバックアップを実行することによって、値関数は、値反復手順によって必要とされる複数パスではなく、状態空間の単一のパスのみで求められる。
【０１２９】
段階ｊにおける状態と段階ｊ＋１における状態との間の全ての遷移は車両経路に沿って同じ距離(ｚｊ＋１−ｚｊに等しい)をカバーするので、結果として得られるＭＤＰはＥＤ−ＭＤＰである。ＥＤ−ＭＤＰは一般的なＭＤＰ手法の特殊な事例であり、全ての重心座標は、それらのうちの最大で２つがゼロよりも大きくなるように縮退する。計算の観点から、これらの正の座標を求めることも、段階ｊ＋１にある状態のみが考慮されるので、一般的な事例よりもはるかに単純である。１つの実施の形態は、速度を昇順にソートし、速度に対し二分探索を用いて、正の遷移確率を有する２つの状態を得る。加えて、この実施の形態の１つの変形形態は、ステップΔｖを用いて速度座標に沿って所与の段階における状態を等しく離間し、遷移座標の計算は、終了状態ｙの速度ｖと離散化ステップΔｖとの比ｖ／Δｖの切上げ又は切下げに縮約される。
【０１３０】
ＦＴＴの場合の等時点ＭＤＰ
図８Ａ〜図８Ｃは、この発明のいくつかの実施の形態による、終了時点Ｔが固定された車両の運行の運転曲線を求める方法のいくつかの原理及び例を示している。これらの実施の形態は、ｔｋ＝ｋΔｔ及びＴ＝ｔＫ＝ＫΔｔとなるように時間座標ｔｋを用いてＭＤＰの状態空間８００を拡張する。この場合、終了時点Ｔは時間ステップΔｔ８１０の整数倍である。ＭＤＰの各状態８２０は、３つ組［ｚ，ｖ，ｔ］によって示され、遷移８３０は連続時間ステップ間で生じる。ＭＤＰの状態空間はタイムスライス８４０に編成することができ、ここで各スライスはＥＴ−ＭＤＰの場合、三角形分割のレプリカであり、例えば連続空間２００である。各遷移は、１つのスライスにおける開始状態と、次のスライスにおける終了状態との間で生じる。
【０１３１】
ＭＤＰポリシーは、全ての拡張状態(ｓ，ｔ)について値関数Ｖ(ｓ，ｔ)を計算することによって求められ、状態は時間を含む。一般に、同じ状態ｓであるが異なる時点ｔ１及びｔ２の場合の値関数は同じでない。この場合、拡張状態のベルマンバックアップは以下の通りである。
【０１３２】
【数２９】
0005905094.tif 000030
【０１３３】
後続状態ｓ’は常にスライスｋ＋１(時点ｔｋ＋１の場合)にあるので、ＭＤＰに自己遷移は存在しない。そのような３次元サンプリングでは、所定の運行時間のＭＤＰが、タイムスライスに編成された複数の時間ステップの三角形分割の別個のレプリカを含み、各遷移が１つのタイムスライスから次のタイムスライスにかけて実行され、自己遷移問題を取り除く。
【０１３４】
値関数は、上記の式を用いて、最後のスライス(Ｋ)から開始して、開始スライス及び開始状態まで時間において後方に進む動的計画法によって求めることができる。この方法は反復的ではないが、拡張状態空間にわたる単一のパスのみが必要である。このＭＤＰはＶＴＴの場合のＥＴ−ＭＤＰ又はＥＤ−ＭＤＰの状態よりもＫ倍多くの状態を有し、その計算時間はＫ倍長い。
【０１３５】
図８Ｃは、システムの状態変数によって定義される連続空間における初期状態から最終状態へシステムを遷移させるマルコフ決定過程を求める方法のブロック図を示している。状態変数は、車両の速度と、車両の位置と、３次元連続空間を形成する走行距離にわたって車両が走行する走行時間とを含む。
【０１３６】
ステップ８５０において、本方法は、走行時間を、連続空間における１組のタイムスライスを形成する１組の時間周期に分割し、各制御がシステムを前のタイムスライスにおける前の状態から次のタイムスライスにおける次の状態に遷移させるようにする。ステップ８６０において、本方法は連続空間をサンプリングして、各アンカー状態がタイムスライス内に位置するようにアンカー状態の集合を求め、ここで各タイムスライスは少なくとも１つのアンカー状態を有し、各制御がＭＤＰを前のタイムスライスにおける前のアンカー状態から次のタイムスライスにおける次のアンカー状態に遷移させるようになっている。
【０１３７】
次に、次のタイムスライスにおける状態を取り囲むシンプレックス２４０が求められる(８７０)。ここで、確率の頂点は次のタイムスライスにおけるアンカー状態の集合の部分集合によって形成される。ＭＤＰをアンカー状態から部分集合内の各アンカー状態に遷移させる確率は、シンプレックス内の状態のロケーションの重心座標として求められ(８８０)、ＭＤＰをアンカー状態から部分集合を形成しない次のアンカー状態に遷移させる確率はゼロを割り当てられる(８９０)。
【０１３８】
実施の形態は、多数の方法のうちの任意のもので実施することができる。例えば、実施の形態は、ハードウェア、ソフトウェア、又はそれらの組み合わせを用いて実施することができる。ソフトウェアで実施されるとき、ソフトウェアコードは、単一のコンピューターにおいて提供されようと、複数のコンピューター間で分散されようと、任意の適切なプロセッサ又はプロセッサの集合体において実行することができる。そのようなプロセッサは、１つ又は複数のプロセッサが集積回路コンポーネント内にある集積回路として実装することができる。ただし、プロセッサは任意の適切なフォーマットで回路を用いて実装することができる。
【０１３９】
また、本明細書で概説された様々な方法又はプロセスを、様々なオペレーティングシステム又はプラットフォームのうちの任意のものを用いる１つ又は複数のプロセッサ上で実行可能なソフトウェアとしてコーディングすることができる。さらに、そのようなソフトウェアは、複数の適切なプログラミング言語及び／又はプログラミングツール若しくはスクリプト記述ツールのうちの任意のものを用いて書くことができ、実行可能な機械言語コード又はフレームワーク若しくは仮想マシン上で実行される中間コードとしてコンパイルすることもできる。
【０１４０】
「プログラム」又は「ソフトウェア」という用語は、本明細書において、一般的な意味で用いられ、上記で検討したようなこの発明の様々な態様を実施するようにコンピューター又は他のプロセッサをプログラミングするのに用いることができる任意のタイプのコンピューターコード又は１組のコンピューター実行可能命令を指す。
【０１４１】
コンピューター実行可能命令は、１つ又は複数のコンピューター又は他のデバイスによって実行されるプログラムモジュール等の多くの形態をとることができる。通常、プログラムモジュールは、特定のタスクを実行するか又は特定の抽象データタイプを実装するルーチン、プログラム、オブジェクト、コンポーネント、データ構造を含む。通常、プログラムモジュールの機能は、様々な実施の形態において所望に応じて組み合わせることも分散させることもできる。
【０１４２】
また、この発明の実施の形態は、方法として具現化することができ、その例が提供された。本方法の一部として実行される動作は、任意の適切な形で順序付けすることができる。したがって、示したものと異なる順序で動作が実行される実施の形態を構築することができ、それにはいくつかの動作が例証的な実施の形態において連続した動作として示される場合であっても、それらを同時に実行することを含むこともできる。
【図１Ａ】
0005905094.tif 000031
【図１Ｂ】
0005905094.tif 000032
【図２】
0005905094.tif 000033
【図３】
0005905094.tif 000034
【図４】
0005905094.tif 000035
【図５】
0005905094.tif 000036
【図６】
0005905094.tif 000037
【図７Ａ】
0005905094.tif 000038
【図７Ｂ】
0005905094.tif 000039
【図８Ａ】
0005905094.tif 000040
【図８Ｂ】
0005905094.tif 000041
【図８Ｃ】
0005905094.tif 000042