JP7706667B2 - 連続変数および離散変数を伴う非線形システムのモデル予測制御のための逐次凸化方法 - Google Patents

Description

本開示は、概して混合整数非線形最適化ベースの制御に関し、より詳細には、動作の連続要素および離散要素を伴う非線形ダイナミクスによって記述されるシステムのモデル予測制御のための逐次凸化方法ならびに装置に関する。

モデル予測制御（ＭＰＣ）等の最適化ベースの意思決定、計画、および制御技術は、システムダイナミクス、システム要件、および制約が直接考慮され得る、モデルベースの設計フレームワークを可能にする。このフレームワークは、連続決定変数および離散決定変数の両方を含むハイブリッド動的システムに拡張されており、これは、例えば、モード切換えを伴う動的システムまたは量子化作動を伴うシステム、論理規則、時間論理仕様、または障害物回避制約を伴う問題を含む、広範囲の問題をモデル化するための強力な技術を提供する。しかしながら、結果として生じる最適化問題は、非常に非凸であり、したがって、離散値（例えば、二進値または整数値）しかとらない変数を含むため、実際には解決することが困難である。非線形システムダイナミクス、１つまたは複数の非線形制約関数、および／または非線形目的関数を使用するとき、結果として生じる最適制御問題（ＯＣＰ）は、混合整数非線形計画（ＭＩＮＬＰ）問題として定式化することができるが、これはＮＰハードであり、したがって、解決するのが計算上困難である。

概して、混合整数非線形モデル予測制御（ＭＩＮＭＰＣ）は、非凸ＭＩＮＬＰの解を必要とし、すなわち、最適化問題は、例えば、非線形システムダイナミクス、非線形制約関数、および／または目的関数に起因して、整数制約を緩和した後でも非凸である。ＭＩＮＬＰのための大部分の成功裏な大域的最適化アルゴリズムは、目的関数および制約関数の凸性を必要とし、したがって、ＭＩＮＭＰＣ問題を大域的最適性に解決するためには使用できない。大域的最適化アルゴリズムは、非凸ＭＩＮＬＰに対しては、例えば、因数分解可能問題の緩和を用いて存在するが、それらは通常、計算的に非常に高価であり、したがって、概して、ＭＩＮＭＰＣのリアルタイム実現に対してはまだ実用的ではない。

ハイブリッドシステムのための意思決定、計画、または制御は、リアルタイムＭＩＮＭＰＣアプリケーションを可能にするために、サンプリング時点ごとにＭＩＮＬＰを解くことを目的とする。したがって、いくつかの方法は、厳密なタイミング要件内でＭＩＮＬＰに対する実現可能だが（場合によっては）準最適な解を見つけるための近似またはヒューリスティックな技術に焦点を当てる。いくつかの既存の技術は、凸状ＭＩＮＬＰのための大域的アルゴリズムに基づいており、これは、例えば、外部近似またはハイブリッド分枝限定（ｈＢ＆Ｂ）法を使用して、非凸ＭＩＮＬＰに対する近似解を見つけるために使用することができる。特に非凸ＭＩＮＭＰＣについては、丸め方式と組み合わせた外部凸化（outer convexification）に基づくリアルタイム反復（ＲＴＩ）アルゴリズムの変形が提案されている。しかしながら、不等式制約が離散的な決定変数に直接依存する場合、後者のアプローチは、消失する制約を有する数学的プログラムを解くことを必要とし、それらは特に困難である。

例えば、逐次凸計画（ＳＣＰ）法または逐次二次計画（ＳＱＰ）法を使用する逐次凸化技術は、一般的な非線形計画（ＮＬＰ）問題を解決するための人気のある技術を形成する。特に、逐次凸化技術は、滑らかな非線形ダイナミクス、非線形制約関数および／または不等式制約を伴う非線形モデル予測制御（ＮＭＰＣ）のリアルタイム実現のために成功裏に使用されている。しかしながら、動作の連続要素および動作の離散要素の両方を有するシステム、すなわち、ＭＩＮＭＰＣにおいて連続的ならびに整数および／またはバイナリ決定変数を含むシステムのためには、これらの方法をＮＭＰＣに拡張する必要がある。

最近の先行研究では、連続最適化変数と整数最適化変数の両方に対する信頼領域半径の使用に基づく混合整数逐次二次計画法（ＭＩＳＱＰ）が提案された。この方法は、各反復において混合整数二次計画（ＭＩＱＰ）部分問題の解を必要とし、これは、例えば、現状技術の分枝限定（Ｂ＆Ｂ）最適化法を使用して効率的に解くことができる。しかしながら、標準的なＭＩＳＱＰ法は、整数変数がＭＩＮＬＰに対して滑らかな影響を有するという仮定に依拠しており、すなわち、整数変数を１だけ増分することは、関数値の小さな変化をもたらす。しかしながら、後者の仮定は、概してＭＩＮＭＰＣには当てはまらず、なぜならば、例えば、制約付き最適化問題は、最適な制御軌道に大きな影響を有するバイナリ変数を含み得るからである。

したがって、本発明に記載されるシステムおよび方法の目的である、ＭＩＮＭＰＣ問題に対してより一般的に適用可能である逐次凸化方法が必要とされている。

本発明の実施形態は、１つまたは複数の混合整数凸計画（ＭＩＣＰ）部分問題のシーケンスの解に基づいており、各部分問題の準備は、提案されるＭＩＮＭＰＣコントローラの各サンプリング時点において混合整数非線形最適制御問題の実現可能だが場合によっては準最適な解を計算するために部分的凸化技術に基づいて実行される。各ＭＩＣＰ部分問題の解は、すべての整数および／またはバイナリ決定変数に対する最適解推測への更新、ならびに連続決定変数に対する新たな探索方向を計算するために使用することができる。加えて、整数および／またはバイナリ決定変数に対する更新された値に基づいて、および連続決定変数に対する新たな探索方向に基づいて、連続決定変数に対する現在の解推測は、混合整数逐次凸計画（ＭＩＳＣＰ）最適化アルゴリズムの各反復において更新され得る。

本発明のいくつかの実施形態は、あらゆるＭＩＮＬＰを、異なるが数学的に等価なＭＩＮＬＰとして、分離可能な形式で再定式化することができ、すべての整数および／またはバイナリ決定変数がすべての制約関数および目的関数において直線的に入るという認識に基づいている。後者の再定式化は、例えば、すべての整数および／またはバイナリ最適化変数が制約関数および目的関数において線形に入ることを確実にするために、１つまたは複数の補助連続最適化変数を定義することによって達成することができる。詳細には、したがって、ＭＩＮＭＰＣ定式化の制約関数および目的関数において、分離可能な形式で存在し得る、すべての非線形関数は、連続最適化変数のみに依存する。本発明のいくつかの実施形態は、後者の、すべての整数および／またはバイナリ決定変数に対する、ＭＩＮＭＰＣ定式化における制約関数および目的関数の線形依存性は、平滑性要件を回避するために使用され得、すなわち、整数変数を１だけ増分することは、関数値のわずかな変化をもたらし、これは、ＭＩＮＭＰＣに対する標準的なＭＩＳＱＰアルゴリズムの適用性を制限するという認識に基づく。

提案されるＭＩＳＣＰ最適化アルゴリズムの各反復においてＭＩＣＰ部分問題を準備するために部分的凸化技術が使用される。本発明のいくつかの実施形態は、すべての整数および／またはバイナリ決定変数に対する、ＭＩＮＭＰＣ定式化における制約関数および目的関数の線形依存性に起因して、部分的凸化技術が滑らかな非線形関数にのみ適用される必要があるという認識に基づく。本発明のいくつかの実施形態では、部分的凸化技術は、ＭＩＳＣＰアルゴリズムの現在の反復における連続最適化変数の解推測に基づいて、ＭＩＮＭＰＣ定式化の制約関数および目的関数に存在し得るすべての滑らかな非線形関数の局所線形化に基づく。代替として、本発明の他の実施形態では、部分的凸化技術を使用して、ＭＩＮＭＰＣ問題定式化の１つまたは複数の不等式制約における非線形関数のより一般的な凸近似を計算することができ、混合整数二次制約付き二次計画法（ＭＩＱＣＱＰ）部分問題における凸二次不等式制約、または混合整数二次錐計画法（ＭＩＳＯＣＰ）部分問題における凸二次錐制約をもたらす。

本発明の実施形態は、提案されるＭＩＳＣＰアルゴリズムの各反復におけるＭＩＣＰ部分問題の解は、ＭＩＣＰのための現状技術のソルバの開発において過去数十年にわたってなされてきた進歩のおかげで、相対的に迅速に計算され得るという認識に基づく。例えば、分枝限定法は、混合整数二次計画（ＭＩＱＰ）または混合整数線形計画（ＭＩＬＰ）部分問題を効率的に解決するために使用され得る。ＭＩＱＰおよび／またはＭＩＬＰのための現状技術の分枝限定法は、高度なプライマルヒューリスティックス、分枝戦略、事前解決処理、カット生成技術、ならびに早期終了および実行不可能性検出を伴う凸ソルバを含んで、分枝限定探索木のサイズを効果的に低減し、したがって、各ＭＩＱＰ／ＭＩＬＰに対する大域的に最適な解を計算するために解決される必要がある凸緩和の量を低減し得る。

本発明のいくつかの実施形態は、各ＭＩＳＣＰ反復における連続決定変数の更新を特定の方法で実行して、ＭＩＮＬＰ問題の実現可能だがおそらくは準最適の解を計算する際に、ある程度の進捗を保証するようにすることができるという認識に基づいている。本発明のいくつかの実施形態は、連続および離散決定変数の値の解推測のために最適性および制約充足度の組み合わせを定量化するメリット関数に基づく大域化戦略を使用する。メリット関数の一例は、提案されるＭＩＳＣＰ最適化アルゴリズムの各反復において整数および／またはバイナリ決定変数の各々について故意に自動的に満たされる整数制約を除く、ＭＩＮＭＰＣ問題定式化における等式制約の各々と不等式制約の各々の違反とに適用されるｌ_１ペナルティ関数に基づく。

本発明のいくつかの実施形態では、大域化戦略は、非線形制約および／または目的関数の局所凸近似が充分に正確である、連続決定変数の空間内の小領域を計算する信頼領域方法に基づく。部分的凸化の精度は、ＭＩＳＣＰ最適化アルゴリズムの各反復におけるある解推測から次の解推測へのメリット関数の値の実際の低減対予測される低減の比に基づいて近似的に評価することができる。本発明のいくつかの実施形態は、信頼領域半径に基づき、その値は、アルゴリズムの各反復において増加、減少、または同じに保たれ得る。

本発明のいくつかの実施形態は、ＭＩＳＣＰ最適化アルゴリズムがＭＩＮＭＰＣ問題の実現可能ではあるが場合によっては準最適解に充分に近いときに相対的に小さい信頼領域半径が使用されてもよく、相対的に小さい信頼領域半径に起因してＭＩＣＰ部分問題を解決するための計算コストのかなりの低減をもたらす、という認識に基づく。

本発明のいくつかの実施形態は、前のサンプリング時点におけるＭＩＮＭＰＣ問題の実現可能だが場合によっては準最適な解に基づいて、連続決定変数ならびに整数決定変数および／またはバイナリ決定変数の最適値に対する推測を計算するウォームスタート戦略に基づく。例えば、本発明のいくつかの実施形態では、提案されるＭＩＮＭＰＣコントローラの以前のサンプリング時点におけるＭＩＮＬＰに対する最適またはほぼ最適な解を前提として、ＭＩＳＣＰ最適化アルゴリズムの解推測をウォームスタートするために、１サンプリング期間によるタイムシフト手順を使用することができる。

本発明のいくつかの実施形態は、限定された数の１つまたは複数のＭＩＣＰ部分問題の解に基づき、その後、整数および／もしくはバイナリ決定変数のいくつかまたはすべては固定されたままであり、凸計画（ＣＰ）部分問題のいくつかの１つまたは複数の解をもたらす。ＭＩＣＰ解の数の上限は、ＭＩＳＣＰ最適化アルゴリズムの計算コストをかなり低減することができるように相対的に小さい一方で、ＭＩＳＣＰ最適化アルゴリズムが、ＭＩＮＭＰＣ問題に対する良好に実現可能だが場合によっては準最適な解を計算することを可能にするように充分に大きく選択されることができる。例えば、本発明のいくつかの実施形態では、リアルタイム実行可能ＭＩＮＭＰＣコントローラの各サンプリング時点において、単一のＭＩＣＰ部分問題のみを解決する必要がある。

本発明のいくつかの実施形態は、ＣＰ部分問題の１つまたは複数の解法が、ＭＩＣＰ部分問題の１つまたは複数の解法よりもかなり小さい計算コストで実行され得るという認識に基づく。本発明のいくつかの実施形態は、限定された数のＭＩＣＰ部分問題の１つまたは複数の解の後に、整数および／もしくはバイナリ決定変数のいくつかまたはすべてを固定することは、提案されるＭＩＮＭＰＣコントローラにおけるＭＩＳＣＰ最適化アルゴリズムの循環を防止し得るという認識に基づく。

本発明のいくつかの実施形態において、ＭＩＴＣＰ反復の数は、最適化アルゴリズムの終了条件によって決定され、これは、整数条件を除いて、ＭＩＮＬＰに対する最適性のカルーシュ・クーン・タッカー（ＫＫＴ）必要条件のノルムに基づき得る。

本発明のいくつかの実施形態では、ホモトピー型ペナルティ法を使用して、各ＭＩＣＰ部分問題におけるコスト関数を調整して、ＭＩＳＣＰアルゴリズムを次第に実施して、前のＭＩＳＣＰ反復における整数および／またはバイナリ決定変数の解推測に近いままである、整数および／もしくはバイナリ決定変数のいくつかまたはすべてに対する最適解推測への更新を計算し得る。

本発明のいくつかの実施形態は、整数および／もしくはバイナリ決定変数のいくつかまたはすべてに対するホモトピー型ペナルティ法の使用はＭＩＳＣＰ最適化アルゴリズムにおける循環を防止し得るという認識に基づく。加えて、本発明のいくつかの実施形態は、整数および／もしくはバイナリ決定変数のいくつかまたはすべてに対するホモトピー型ペナルティ法の使用は、ＭＩＳＣＰ最適化アルゴリズムにおいてＭＩＣＰ部分問題を解く計算コストをかなり低減し得るという認識に基づく。

したがって、一実施形態は、非線形ダイナミクスならびに動作の連続要素および離散要素を伴うハイブリッド動的システムを制御するための予測フィードバックコントローラを開示し、予測フィードバックコントローラは、少なくとも１つのプロセッサと、命令を記憶したメモリとを備え、命令は、少なくとも１つのプロセッサによって実行されると、予測フィードバックコントローラに、
●予測コントローラの現在の状態、ハイブリッド動的システムの１つまたは複数のアクチュエータの現在の状態、およびハイブリッド動的システムの出力の現在の状態のうちの１つまたは組合せを含む、ハイブリッド動的システムの現在の状態を示す測定値を含むフィードバック信号を受け入れさせ；
●制御目的に従ってハイブリッド動的システムの現在の状態を変更するための制御コマンドを示す解を用いて、１つまたは複数の制約の対象となる目的関数を最適化する混合整数非線形計画（ＭＩＮＬＰ）問題を定式化させ、制約は、等式制約、不等式制約、または両方を含み、ＭＩＮＬＰ問題の制約および制御目的は、ハイブリッド動的システムの動作の連続要素を表す連続最適化変数の１つまたは複数の非線形関数と、ハイブリッド動的システムの動作の離散要素を表す整数最適化変数の１つまたは複数の線形関数とを含み、ＭＩＮＬＰ問題は、動作の離散要素がＭＩＮＬＰ問題の線形関数にのみ存在することを保証する分離可能なフォーマットに定式化され；さらに、命令は、少なくとも１つのプロセッサによって実行されると、予測フィードバックコントローラに、
●終了条件が満たされるまで、逐次凸化ベースの最適化手順の複数の反復にわたってＭＩＮＬＰ問題を解かせ、反復を実行するために、予測フィードバックコントローラは、現在の解推測を含む解の空間の一部の部分的凸化を実行するように構成され、部分的凸化は、部分的に凸化されたＭＩＮＬＰを生成するためにＭＩＮＬＰの線形関数を近似することなくＭＩＮＬＰの非線形関数の凸近似を生成し；さらに、命令は、少なくとも１つのプロセッサによって実行されると、予測フィードバックコントローラに、部分的に凸化されたＭＩＮＬＰ問題の混合整数凸計画（ＭＩＣＰ）定式化を解くことによって現在の解推測を更新させ；
●ＭＩＮＬＰ問題の解に従って生成された制御コマンドをハイブリッド動的システムに提出させ、それによってハイブリッド動的システムの現在の状態の変化を引き起こさせる。

いくつかの実施形態による、混合整数非線形モデル予測コントローラおよびフィードバックシステムのブロック図を示す。 いくつかの実施形態による、混合整数非線形モデル予測コントローラおよびフィードバックシステムのブロック図を示す。 いくつかの実施形態による、混合整数非線形モデル予測コントローラとフィードバックシステムを制御するための追跡コントローラとの間の階層的統合のブロック図を示す。 いくつかの実施形態による、システムの現在の状態および制御コマンドを前提として、制御信号を計算する予測コントローラを実現するための混合整数非線形モデル予測制御（ＭＩＮＭＰＣ）のための方法のブロック図を示す。 いくつかの実施形態による、最適制御構造化混合整数非線形プログラム（ＭＩＮＬＰ）を解くＭＩＮＭＰＣ方法のブロック図を示す。 いくつかの実施形態による、ＭＩＮＭＰＣ方法の実現例において解決されるＭＩＮＬＰの分離可能なフォーマットへの再定式化を示す。 いくつかの実施形態による、最適制御構造化ＭＩＮＬＰを分離可能なフォーマットで解くＭＩＮＭＰＣ方法のブロック図を示す。 いくつかの実施形態による、反復最適化手順のブロック図を示し、各反復は、部分的凸化ステップと、混合整数凸計画（ＭＩＣＰ）部分問題の解とからなり、ＭＩＮＭＰＣについて実現可能かつ（局所的に）最適な解を計算する。 いくつかの実施形態による、反復最適化手順のブロック図を示し、各反復は、部分的凸化ステップと、信頼領域制約を受けるＭＩＣＰ部分問題の解とからなり、ＭＩＮＭＰＣについて実現可能かつ（局所的に）最適な解を計算する。 本発明のいくつかの実施形態による、実現可能かつ（局所的に）最適なＭＩＮＬＰ解を計算するための逐次凸化ベースの最適化手順の１つまたは複数の反復のブロック図を示す。 いくつかの実施形態による、逐次凸化ベースの最適化手順の１つまたは複数の反復のブロック図を示し、各反復は、ＭＩＮＬＰ解空間の小領域内の局所的な線形－二次近似およびＭＩＱＰ部分問題の解からなる。 本発明のいくつかの実施形態による、実現可能かつ（局所的に）最適なＭＩＮＬＰ解を計算するための逐次凸化ベースの最適化手順のブロック図を示し、整数変数の値は、１回または複数回の反復後に固定される。 いくつかの実施形態による、現在の解推測の局所近傍におけるＭＩＮＬＰ解空間の小領域内の１つまたは複数の非凸不等式制約を近似するために１つまたは複数の凸不等式制約を計算する部分的凸化ステップの概略図を示す。 いくつかの実施形態による、分離可能なフォーマットにおけるＭＩＮＬＰのコスト関数における１つまたは複数の滑らかな非線形関数の凸近似を計算する部分的凸化ステップの概略図を示す。 本発明のいくつかの実施形態による、ＭＩＮＭＰＣコントローラの各時間ステップで解決される、分離可能なフォーマットにおける最適制御構造化ＭＩＮＬＰのコンパクトな定式化のブロック図を示す。 いくつかの実施形態による、ＭＩＮＬＰ解空間の小領域内の局所線形－二次近似と、ＭＩＱＰ部分問題の解とに基づき、ＭＩＮＬＰ解推測を更新するための、逐次凸化ベースの最適化手順のブロック図を示す。 ＭＩＮＬＰ解推測を更新するために、１回または複数回の反復後に整数変数の値を固定し、１回または複数回の後続の反復において凸ＱＰ部分問題を解く、逐次凸化ベースの最適化手順のブロック図を示す。 いくつかの実施形態による、ＭＩＮＭＰＣ問題に対する解を計算するために、各反復が、部分的凸化ステップと、それに続く凸ＱＰまたは非凸ＭＩＱＰ部分問題の解とからなる、逐次凸化ベースの最適化手順のブロック図を示す。 いくつかの実施形態による、逐次凸化ベースの最適化手順においてＭＩＮＬＰ解推測について最適性および制約充足度を定量化するためのメリット関数のブロック図を示す。 いくつかの実施形態による、逐次凸化ベースの最適化手順においてＭＩＮＬＰ解推測を更新するために、１つまたは複数のメリット関数評価および方向導関数に基づいてステップサイズを計算するためのラインサーチ手順のブロック図を示す。 いくつかの実施形態による、ＭＩＮＭＰＣコントローラにおいてＭＩＮＬＰについて実現可能かつ（局所的に）最適な解を計算するための、ラインサーチ手順に基づくＭＩＳＱＰ最適化法の擬似コードを示す。 いくつかの実施形態による、逐次凸化ベースの最適化手順の各反復におけるメリット関数の値に対する実際の低減対予測される低減の比のブロック図を示す。 メリット関数の値に対する実際の低減対予測された低減の比に基づき、かつ信頼領域半径値に基づき、逐次凸化ベースの最適化手順の各反復においてＭＩＮＬＰ解推測を更新する信頼領域手順のブロック図を示す。 いくつかの実施形態による、ＭＩＮＬＰ解空間の小領域内の探索方向を制限するために信頼領域制約を受けるＭＩＱＰ部分問題を構築および解くために部分的凸化ステップに基づくＭＩＳＱＰ最適化アルゴリズムのブロック図を示す。 いくつかの実施形態による、ＭＩＮＭＰＣコントローラにおいてＭＩＮＬＰについて実現可能かつ（局所的に）最適な解を計算するための、信頼領域探索手順に基づく、ＭＩＳＱＰ最適化法の擬似コードを示す。 本発明のいくつかの実施形態による、逐次凸化ベースの最適化手順の収束を加速するために使用することができる、１つまたは複数の追加のペナルティ項をＭＩＮＬＰ目的関数に追加することによる、ホモトピー型ペナルティ法の例を示す。 ＭＩＳＣＰ最適化アルゴリズムの収束を加速してＭＩＮＬＰの実現可能かつ（局所的に）最適な解を見つけるために使用することができる、１つまたは複数の追加のペナルティ項をＭＩＮＬＰ目的関数に追加することによる、ホモトピー型ペナルティ法の一例の概略図を示す。 ＭＩＳＣＰ最適化アルゴリズムの収束を加速してＭＩＮＬＰの実現可能かつ（局所的に）最適な解を見出すために使用することができる、１つまたは複数の追加の線形および／または滑らかな非線形不等式制約を加えることによる、ホモトピー型ペナルティ法の例の概略図を示す。 本発明のいくつかの実施形態による、前の制御時間ステップにおけるＭＩＮＭＰＣ問題に対する（近似）解を前提として、初期ＭＩＮＬＰ解推測を計算するためのウォームスタート初期化手順のブロック図を示す。 いくつかの実施形態による、前の制御時間ステップにおけるＭＩＮＭＰＣ問題に対する（近似）解を前提として、最適な制御構造化ＭＩＮＬＰについての初期解推測を計算するための、タイムシフト動作に基づく、ウォームスタート初期化手順のブロック図を示す。 いくつかの実施形態による、ＭＩＣＰ部分問題の整数実行可能解のための探索領域の入れ子木を表すバイナリ制御変数探索木の例の概略図を示す。 いくつかの実施形態による、探索領域の入れ子木および対応する下限／上限値に基づいて、ＭＩＣＰ部分問題の整数実行可能最適解を探索するための分枝限定混合整数最適化アルゴリズムのブロック図を示す。 いくつかの実施形態の原理を採用する予測コントローラを含む車両の概略図を示す。 いくつかの実施形態による、予測コントローラと車両の他のコントローラとの間の対話の概略図を示す。 いくつかの実施形態の原理を採用する被制御車両のための経路および／または運動計画方法の概略図を示す。 いくつかの実施形態に基づく単一車両または多車両意思決定モジュールの例示的な交通場面を示す。 いくつかの実施形態による、原理を採用する宇宙機混合整数予測制御問題定式化の概略図を示す。 いくつかの実施形態による、原理を採用する宇宙機混合整数予測制御問題定式化の概略図を示す。 いくつかの実施形態による、コントローラによって制御される蒸気圧縮システムの概略図を示す。 いくつかの実施形態による、ＶＣＳ内で使用される信号、センサ、およびコントローラの構成の実施例を図示する。 例示的実施形態による、システムを制御するための方法を図示する。

本開示のいくつかの実施形態は、システムの動作を制御するためのシステムおよび方法、または予測コントローラを使用するシステムを提供する。予測コントローラの例は、動作の連続要素および離散要素を有する被制御システムの非線形モデルに基づいて制御入力を決定する混合整数非線形モデル予測コントローラ（ＭＩＮＭＰＣ）である。

図１Ａは、いくつかの実施形態による、予測コントローラ１１０およびフィードバックシステム１２０のブロック図を示す。図１Ａは、いくつかの実施形態による、状態推定器１３０を介して予測コントローラ１１０（またはコントローラ）に接続された例示的なフィードバックシステム（またはシステム）１２０を示す。いくつかの実現形態では、予測コントローラ１１０は、システム１２０の動的モデル１０２（またはシステムモデル）に従ってプログラムされたＭＩＮＭＰＣコントローラである。システムモデル１０２は、システム１２０の状態および出力１０３の変化を経時的に現在および以前の入力１１１ならびに以前の出力１０３の関数として表す方程式のセットであり得る。システムモデル１０２は、システム１２０の物理的および動作上の制限を表す制約１０４を含むことができる。動作中、コントローラ１１０は、システム１２０の所望の挙動を示すコマンド１０１を受信する。コマンドは、例えば、運動コマンドとすることができる。コマンド１０１の受信に応答して、コントローラ１１０は、動作の連続要素と動作の離散要素との両方を含むシステム１２０に対する入力として働く制御信号１１１を生成する。入力に応答して、システムは、システム１２０の出力１０３を更新する。システム１２０の出力１０３の測定値に基づいて、推定器１３０は、システム１２０の推定状態１２１を更新する。システム１２０のこの推定状態１２１は、状態フィードバックを予測コントローラ１１０に提供する。したがって、予測コントローラは、最初に推定器１３０を介してシステム１２０のフィードバック信号１２１を受け取り、フィードバック信号１２１はシステム１２０の状態の測定値を含む。

本明細書で言及されるシステム１２０は、特定の操作入力信号、例えば制御信号１１１（入力）によって制御される任意の機械または装置であり得る。制御入力信号は、場合によっては、電圧、圧力、力、トルク、操舵角、速度、および温度などの連続要素、ならびにエネルギーレベル、量子化されたバルブ入力、ギアシフト、オン／オフ作動、車線選択、および障害物回避決定変数などの離散要素を含むことができる。システム１２０は、場合によっては、電流、流れ、速度、位置、温度、進行方向および操舵角などの連続要素、ならびにエネルギーレベル、量子化されたバルブ状態、ギア状態、オン／オフ状態、および車線位置などの離散要素を含む、いくつかの制御された出力信号１０３（出力）を返す。出力値は、部分的にシステムの以前の出力値に関連し、部分的に以前および現在の入力値に関連する。以前の入力および以前の出力に対する依存性は、システムの状態において符号化される。システムの動作、例えば、システムの構成要素の運動は、特定の入力値の適用後にシステムによって生成される出力値のシーケンスを含むことができる。

システムモデル１０２は、システム出力が時間とともにどのように変化するかを現在の入力および以前の入力ならびに以前の出力の関数として記述する数学的方程式のセットを含み得る。数学的方程式は、連続変数に依存する１つまたは複数の滑らかな方程式と、連続変数および離散変数の両方に依存する１つまたは複数の混合整数方程式とを含むことができる。数学的方程式における各関数は、線形または滑らかな非線形関数のいずれかであり得る。システム１２０の状態は、例えば、システムのモデルおよび将来の入力とともに、システムの将来の運動を一意に定義することができる、現在の入力および出力ならびに以前の入力および出力の適切なサブセットなど、一般に時変する任意の情報セットである。

システム１２０は、システム１２０の出力、入力、および場合によっては状態も動作させることができる範囲を制限する物理的制限および仕様制約１０４を受け得る。制約は、連続変数に依存する１つまたは複数の滑らかな方程式と、連続変数および離散変数の両方に依存する１つまたは複数の混合整数方程式とを含むことができる。制約関数は、線形または滑らかな非線形関数のいずれかであり得る。本発明のいくつかの実施形態は、制約１０４内の滑らかな非線形関数の各々について一次または高次方向導関数を計算することができるという認識に基づいている。

予測コントローラ１１０は、ハードウェアで、またはプロセッサ、例えばマイクロプロセッサで実行されるソフトウェアプログラムとして実現することができ、固定または可変制御周期サンプリング間隔で、システム１２０の推定状態１２１および所望の運動コマンド１０１を受信し、この情報を使用して、システム１２０を動作させるための入力、例えば制御信号１１１を決定する。予測コントローラ１１０はさらに、混合整数逐次凸計画（ＭＩＳＣＰ）法を使用して、最適制御構造化混合整数非線形計画（ＭＩＮＬＰ）問題を解決し、終了条件が満たされるまで、たとえば解が最適制御構造化ＭＩＮＬＰに対して実現可能および（局所的に）最適になるまで、複数の反復にわたって、１つまたは複数の等式および／または不等式制約を条件として、目的関数の現在の解を最適化する。ＭＩＳＣＰ法の各反復は、現在の解を含む解の空間の一部の部分的凸化を実行し、部分的凸化は、部分的に凸化されたＭＩＮＬＰを生成するためにＭＩＮＬＰの線形関数を近似することなくＭＩＮＬＰの滑らかな非線形関数の凸近似を生成する。次いで、各反復は、制御信号１１１を生成するために、部分的に凸化されたＭＩＮＬＰ問題の混合整数凸計画（ＭＩＣＰ）定式化を解決することによって現在の解を更新することができる。さらに、予測コントローラ１１０は、制御信号１１１に基づいてシステム１２０を制御して、システム１２０の状態を変更する。

推定器１３０は、ハードウェアで、またはコントローラ１１０と同じであるかもしくは異なるプロセッサのいずれかのプロセッサで実行されるソフトウェアプログラムとして実現でき、固定または可変の制御周期サンプリング間隔でシステム１０３の出力を受け取り、新たな出力測定値および以前の出力測定値を用いてシステム１２０の推定状態１２１を判断する。

したがって、ＭＩＳＣＰ最適化法を使用することによって、プロセッサは、ＭＩＣＰ部分問題のシーケンスを解くことによって、最適制御構造化ＭＩＮＬＰの実現可能かつ（局所的に）最適な解を計算し、各ＭＩＣＰ部分問題の定式化は、解空間の一部の部分的凸化に基づく。元のＭＩＮＬＰを解く計算の複雑さと比較してＭＩＣＰ部分問題を解く計算の複雑さが低減されるため、プロセッサは、より少ない時間でシステム１２０の状態を制御するために、実現可能かつ（局所的に）最適な解を正確に決定することが可能になる。したがって、プロセッサは、高速な処理速度を高精度で実現する。

図１Ｂは、いくつかの実施形態による、混合整数非線形予測コントローラ１１０およびフィードバックシステム１２０のブロック図を示す。予測コントローラ１１０は、システム１２０の推定状態１２１および出力１０３がコマンド１０１に従うようにシステム１２０を作動させる。コントローラ１１０は、例えば、システムモデル１０２およびシステム１２０の動作に関する制約１０４を記憶するためのメモリ１５２に接続された単一の中央処理装置（ＣＰＵ）または複数のＣＰＵプロセッサ１５１の形態のコンピュータを含む。ＣＰＵプロセッサ１５１は、シングルコアプロセッサ、マルチコアプロセッサ、コンピューティングクラスタ、または任意の数の他の構成から構成されてもよい。メモリ１５２は、ランダムアクセスメモリ（ＲＡＭ）、読取り専用メモリ（ＲＯＭ）、フラッシュメモリ、または任意の他の好適なメモリシステムを含み得る。

図１Ｃは、本発明のいくつかの実施形態による、上位制御信号１１１を計算する混合整数非線形予測コントローラ１１０と、上位制御信号１１１を追跡し、下位制御信号１１２を計算してフィードバックシステム１２０を直接制御することを目的とする追跡コントローラ１１５との間の階層的統合のブロック図を示す。例えば、予測コントローラ１１０は、動作の連続要素および離散要素を有する被制御システムの非線形動的モデルに基づいて基準運動軌道を計算するＭＩＮＭＰＣコントローラとすることができ、追跡コントローラ１１５は、制御入力１１２を被制御システムのアクチュエータに直接送ることによって基準運動軌道（の一部）を実行することを目的とする。

追跡コントローラ１１５の例は、ＭＩＮＭＰＣコントローラ１１０によって計算される時変基準運動軌道を追跡するための比例積分微分（ＰＩＤ）コントローラに基づくことができる。本発明のいくつかの実施形態では、追跡コントローラ１１５は、相対的に単純化された動的モデルおよび単純化された制約のセットを伴うモデル予測コントローラ（ＭＰＣ）に基づくことができ、したがって、必要とされる計算複雑性が相対的に小さい。例えば、ＭＰＣ追跡コントローラ１１５は、ＭＩＮＭＰＣコントローラ１１０によって解かれるＭＩＮＬＰよりも解くのが計算的にはるかに容易である凸線形計画（ＬＰ）または凸二次計画（ＱＰ）問題の解を必要とする、線形－二次目的関数、線形動的モデル、ならびに線形等式および不等式制約に基づくことができる。

本発明のいくつかの実施形態は、相対的に長い予測ホライズンが混合整数非線形予測コントローラ１１０のために使用され得、相対的に短い予測ホライズンが追跡コントローラ１１５のために使用され得、相対的に速いサンプリングレートが、例えば、１０～１００ミリ秒のサンプリング周期で、追跡コントローラに使用され得、一方、相対的に遅いサンプリングレートが、例えば、０．５～２秒のサンプリング周期で、混合整数非線形予測コントローラ１１０に使用され得るという認識に基づく。

本発明のいくつかの実施形態は、ＭＩＮＬＰを解く計算上の複雑さに起因して、混合整数非線形予測コントローラ１１０のＭＩＮＬＰ定式化においては、相対的に上位の低精度動的モデル１０２および制約１０４を使用することができ、一方、計算的に安価な追跡コントローラ１１５の設計および定式化においては、相対的に下位の高精度動的モデル１０２および制約１０４を使用することができるという認識に基づく。

図２Ａは、いくつかの実施形態に従い、システム１２１の現在の状態および制御コマンド１０１を所与として、制御信号１１１を計算する、予測コントローラ１１０を実現するための混合整数非線形モデル予測制御（ＭＩＮＭＰＣ）のためのシステムおよび方法のブロック図を示す。具体的には、ＭＩＮＭＰＣは、各制御時間ステップにおいて制約付き混合整数非線形計画（ＭＩＮＬＰ）問題２５０を解くことにより、制御解、たとえばシステム１２０の予測時間ホライズンにわたる将来の最適な離散制御入力および連続制御入力のシーケンスを含み得る解ベクトル２５５を計算する。この最適化問題２５０における目的関数、等式制約、ならびに離散的、連続的および混合整数不等式制約のＭＩＮＬＰデータ２４５は、動的モデル、システム制約２４０、システム１２１の現在の状態、制御の目的および制御コマンド１０１に依存する。

本発明のいくつかの実施形態では、この不等式制約付きＭＩＮＬＰ問題２５０の解は、予測時間ホライズンにわたる１つまたは複数の状態値および制御値、ならびに、メモリから読み取ることができる、前の制御時間ステップからの潜在的に他のＭＩＮＬＰ解情報を使用する（２１０）。この概念は、最適化アルゴリズムのウォームスタートまたはホットスタートと呼ばれ、いくつかの実施形態では、ＭＩＮＭＰＣコントローラの必要な計算労力を低減することができる。同様に、対応する解ベクトル２５５を使用して、予測時間ホライズンにわたる１つまたは複数の最適な状態値および制御値のシーケンス、ならびに次の制御時間ステップのための潜在的に他のＭＩＮＬＰ解情報を更新し、メモリに記憶することができる（２３５）。

いくつかの実施形態では、混合整数最適化アルゴリズムは、逐次凸化アルゴリズムの各反復における部分的凸化ステップの結果であるＭＩＣＰ部分問題を解くための探索アルゴリズムに基づき、ＭＩＮＭＰＣコントローラは、現在のおよび／または次の制御時間ステップにおける１つまたは複数の反復における探索アルゴリズムの計算労力を低減するために、追加の混合整数計画解情報２６０を更新および記憶する。一実施形態では、各反復におけるＭＩＣＰ部分問題は、分枝限定最適化法を使用して解決され、ウォームスタート情報は、ある反復から次の反復までノード選択および可変分枝戦略を改善するために、最適な整数実行可能制御解が見出される根ノードから葉ノードまでの解経路の一部である二分探索木内のノードに関連するデータを含むことができる。

図３Ａは、システム１２１の現在の状態１２１および制御コマンド１０１を所与として、各制御時間ステップにおいて制御信号１１１を計算するために最適制御構造化ＭＩＮＬＰ２５０を解くＭＩＮＭＰＣ法のブロック図を示す。本発明のいくつかの実施形態は、線形等式制約２６２と、予測時間ホライズン内の各時間ステップにおける非線形混合整数不等式制約２６４と、予測時間ホライズンの終端時間ステップにおける非線形混合整数不等式制約２６５と、線形離散等式制約２６６と、線形－二次または非線形目的関数２６１とを伴うシステム２６３の非線形動的モデルに基づき、結果として得られる制約付きＭＩＮＬＰ２６０は、各制御時間ステップで解かれる必要がある。ＭＩＮＬＰデータ２４５は、最適制御構造化ＭＩＮＬＰ２６０を定式化するためにＭＩＮＬＰ行列およびベクトル２４６ならびにＭＩＮＬＰ関数２４７を含むことができる。

本発明のいくつかの実施形態では、システムの非線形動的モデル２６３は、１つまたは複数の線形および／または滑らかな非線形微分方程式によって記述される。本発明のいくつかの実施形態では、システムの動的モデル２６３は、例えば区分的に線形および／または区分的に滑らかな非線形方程式を含む、動的方程式における状態依存および／または入力依存跳躍を伴う線形または非線形ハイブリッドシステムを記述する。

図２Ｃは、最適制御構造化ＭＩＮＬＰ２６０の分離可能なフォーマットへの、すなわち、線形的に、場合によっては１つまたは複数の連続変数および／または整数変数を加えることによって、ＭＩＮＬＰに線形に入る連続変数および整数変数の滑らかな非線形関数の分離を伴う、再定式化を示す（２７０）。いくつかの実施形態では、ＭＩＮＭＰＣ予測コントローラ１１０は、システム１２０の現在の状態１２１およびコマンド１０１を前提として、各制御時間ステップにおいて制御信号１１１を計算するために、結果として生じるＭＩＮＬＰを分離可能フォーマットで解く（２８０）。

本発明のいくつかの実施形態では、最適制御構造化ＭＩＮＬＰ２６０は、分離可能フォーマットで自明に再定式化することができ（２７０）なぜならば、例えば、目的における関数２６１、等式制約における関数２６３、および不等式制約における関数２６４～２６５を以下のように定義して、

目的における関数２８１、等式制約における関数２８３、および不等式制約における関数２８４～２８５を、予測時間ホライズンｋ＝０，１，．．．，Ｎ－１内の時間ステップの各々に対する行列Ｄ_ｋ、Ｅ_ｋ、Ｅ_Ｎおよびベクトルｃ_ｋに基づいて、分離可能なフォーマットで定義するからである。

本発明のいくつかの実施形態は、分離可能なフォーマットのＭＩＮＬＰ２８０は元のＭＩＮＬＰ２６０と数学的に等価である、すなわち、分離可能なフォーマットのＭＩＮＬＰ２８０は、元のＭＩＮＬＰ２６０が実行不可能である場合にのみ実行不可能であり、分離可能なフォーマットのＭＩＮＬＰ２８０に対する実現可能で（局所的に）最適な解を使用して、元のＭＩＮＬＰ２６０の実現可能で（局所的に）最適な解を構築することができるという認識に基づく。例えば、本発明のいくつかの実施形態では、分離可能なフォーマットのＭＩＮＬＰ２８０に対する実現可能で（局所的に）最適な解を元のＭＩＮＬＰ２６０の実現可能で（局所的に）最適な解に変換するために、アフィンまたは非線形変換が存在する。

図２Ｄは、システム１２０の現在の状態１２１およびコマンド１０１を前提として、各制御時間ステップで制御信号１１１を計算するために、分離可能なフォーマットで最適制御構造化ＭＩＮＬＰ２８０を解くＭＩＮＭＰＣ法のブロック図を示す。本発明のいくつかの実施形態は、線形等式制約２８２と、予測時間ホライズン内の各時間ステップにおける非線形混合整数不等式制約２８４と、予測時間ホライズンの終端時間ステップにおける非線形混合整数不等式制約２８５と、線形離散等式制約２８６と、線形－二次または非線形目的関数２８１とを伴うシステムの非線形動的モデル２８３に基づき、結果として得られる制約付きＭＩＮＬＰ２８０は、各制御時間ステップで解かれる必要がある。ＭＩＮＬＰデータ２４５は、最適制御構造化ＭＩＮＬＰ２８０を定式化するためにＭＩＮＬＰ行列およびベクトル２４６ならびにＭＩＮＬＰ関数２４７を含むことができる。

例えば、ＭＩＮＬＰ行列およびベクトル２４６は、最適制御構造化ＭＩＮＬＰ２８０の制約関数および目的関数において行列Ｄ_ｋ、Ｅ_ｋ、Ｅ_Ｎおよびベクトルｃ_ｋを含むことができる。

本発明のいくつかの実施形態では、システムの非線形動的モデル２８３は、１つまたは複数の線形および／または滑らかな非線形微分方程式によって記述される。本発明のいくつかの実施形態では、システムの動的モデル２８３は、例えば区分的に線形および／または区分的に滑らかな非線形方程式を含む動的方程式における状態依存および／または入力依存跳躍を伴う線形または非線形ハイブリッドシステムを記述する。

図３Ａは、最適制御構造化ＭＩＮＬＰ２５０を解くための反復最適化手順のブロック図を示し、各反復は、部分的凸化ステップ３１５と、混合整数凸計画（ＭＩＣＰ）部分問題の解３２０とからなり、システム１２０の現在の状態１２１およびコマンド１０１を前提として、各制御時間ステップにおいて制御信号１１１を構築するために使用することができる実現可能かつ（局所的に）最適な解が見つかる（２５５）まで、整数変数３２５および連続変数３３０に対する中間解推測を更新する。

逐次的凸化ベースの最適化手順の各反復は、現在の中間解推測が実現可能および／または（局所的に）最適であるかどうかをチェックすること３５０を含み、その場合、解が見出される（２５５）か、または新たな反復を実行して、部分的凸化ステップ３１５およびＭＩＣＰ部分問題解３２０に基づいて現在の中間ＭＩＮＬＰ解推測３３５を更新し、現在の反復数ｋが更新され得る（３４０）。本発明のいくつかの実施形態では、終了条件３５０は、現在の中間解推測が両方とも実行可能であるかどうか、すなわち解がＭＩＮＬＰにおけるすべての等式および不等式制約を満たすかどうか、それが大域的に最適な解に充分に近いかどうか、および／または反復最適化手順の計算コストが特定の時間制限に達したかどうかをチェックすることを含む。例えば、反復最適化手順が決定論的ランタイムで終了することを確実にするために、最大数の反復を課すことができる。

本発明のいくつかの実施形態は、分離可能なフォーマットのＭＩＮＬＰを解く（２７０）逐次凸化ベースの最適化手順の各反復は、分離可能なフォーマットのＭＩＮＭＰＣ問題の滑らかな非線形部分のみの部分的な凸化ステップ３１５、すなわち、非線形等式制約および非線形不等式制約の各々について、および／または非線形目的関数の各々について、凸化ステップを含むことに基づくことができるという認識に基づく。部分的凸化ステップ３１５は、１つまたは複数の整数変数に依存する線形関数、例えば、最適制御構造化ＭＩＮＬＰ２８０の制約関数および目的関数における行列Ｄ_ｋ、Ｅ_ｋ、Ｅ_Ｎおよびベクトルｃ_ｋに基づく分離可能ＭＩＮＬＰフォーマット２８０における線形制約関数および目的関数を変更しない。具体的には、部分的凸化ステップ３１５は、線形離散等式制約２８６を変更せず、その結果、連続および整数変数（Δy^k,Δz^k）の探索方向を計算する混合整数凸計画（ＭＩＣＰ）部分問題が生ずる（３２０）。

本発明のいくつかの実施形態は、部分的凸化ステップ３１５の特定の実現形態に応じて、ＭＩＣＰ部分問題は、たとえば、混合整数線形計画（ＭＩＬＰ）部分問題、混合整数二次計画（ＭＩＱＰ）部分問題、混合整数二次制約付き二次計画（ＭＩＱＣＱＰ）部分問題または混合整数二次錐計画（ＭＩＳＯＣＰ）部分問題に対応し得るという認識に基づく。

図３Ｂは、最適制御構造化ＭＩＮＬＰ２５０を解くための反復最適化手順のブロック図を示し、各反復は、部分的凸化ステップ３１５と、信頼領域制約を受ける混合整数凸計画（ＭＩＣＰ）部分問題の解３６０とからなり、システム１２０の現在の状態１２１およびコマンド１０１を前提として、各制御時間ステップにおいて制御信号１１１を構築するために使用することができる実現可能かつ（局所的に）最適な解が見つかる（２５５）まで、整数変数および連続変数に対する中間解推測を更新する（３３５）。

同様に、終了条件３５０が満たされるまで、１つまたは複数の追加の反復を実行することができ、たとえば、この条件は、現在の中間解推測が実行可能であるかどうか、それが大域的に最適な解に充分に近いかどうか、および／または逐次凸化ベースの最適化手順の計算コストが特定の時間制限に達したかどうかをチェックすることを含んでもよい。

図４Ｂは、実現可能かつ（局所的に）最適なＭＩＮＬＰ解（y^N*, z^N*）２５５を計算するための逐次凸化ベースの最適化手順の１つまたは複数の反復のブロック図を示し、ここで、各反復における部分的凸化ステップ４０１～４０２は、ＭＩＮＬＰ解空間の小領域内の局所的な線形－二次近似４４１～４４２に基づき、各反復におけるＭＩＣＰ部分問題４１１～４１２は、最適化手順の各反復において探索方向を計算するためのＭＩＱＰ部分問題の解４５１～４５２に対応する。本発明のいくつかの実施形態では、各反復における部分的凸化ステップは、分離可能なフォーマットにおけるＭＩＮＭＰＣ問題の滑らかな非線形部分のみの局所線形化に基づいており、すなわち、非線形等式制約および非線形不等式制約の各々に対する局所線形化ステップおよび／または非線形目的関数の各々に対する局所線形－二次近似ステップを含む。

本発明のいくつかの実施形態は、凸ＱＰ部分問題の解４５３は、逐次凸化ベースの最適化手順の各反復において、非凸ＭＩＱＰ部分問題の解４５１～４５２よりも概して計算的にはるかに安価であるという認識に基づく。本発明のいくつかの実施形態では、すべての整数変数４６０の値を固定するかどうかの判断は、現在の中間解推測が大域的に最適な解に充分に近いかどうか、および／または反復最適化手順の計算コストが特定の時間制限に達したかどうかに基づく。例えば、いくつかの実施形態では、最大数Ｎ_ｍｉｑｐのＭＩＣＰ部分問題解を課して、例えば、ｋ≧Ｎ_ｍｉｑｐ反復４６０の後に整数変数Δｚ^ｋ＝０の値を固定することによって、反復最適化手順の計算労力を大幅に低減することができる。

図５Ａは、現在の中間解推測の局所近傍に対応するＭＩＮＬＰ解空間の小領域内の１つまたは複数の非凸不等式制約を近似するために１つまたは複数の凸不等式制約を計算する部分的凸化ステップの概略図を示す。本発明のいくつかの実施形態は、部分的凸化ステップが、１つまたは複数の整数変数に依存し得る線形関数を不変に維持しながら、分離可能なフォーマットのＭＩＮＬＰ２８０における１つまたは複数の滑らかな非線形不等式制約関数について凸近似を計算するにすぎないという認識に基づく。

本発明のいくつかの実施形態では、逐次凸化ベースの最適化手順の各反復は、非凸実現可能領域５１１のほぼ内側５２６にある探索方向を計算するために、現在の解推測５２０の局所的近傍における１つまたは複数の非凸制約５１０の凸近似５２５を計算するよう部分的凸化ステップを実行する。本発明のいくつかの実施形態は、逐次凸化ベースの最適化手順の各反復が、たとえばバイナリ決定変数ｚ_ｋ∈｛０，１｝（５０５）を含む１つまたは複数の整数変数に起因して非凸であるＭＩＣＰ部分問題３２０に対する解を計算し、それにより、値ｚ_ｋ＝０（５０６）について凸近似５２５を存在させ、一方、非凸実現可能領域５１６のほぼ内側５３６にある探索方向を計算するために、１つまたは複数の非凸制約５１５の、異なる凸近似５３５が、値ｚ_ｋ＝１（５０７）に対応する現在の解推測５３０の局所的近傍に存在し得るという認識に基づく。

例えば、ＭＩＣＰ部分問題３２０に対する解は、ＭＩＮＬＰの滑らかな非線形部分の対応する凸近似５２５または５３５を前提として、バイナリ変数ｚ_ｋ∈｛０，１｝（５０５）をｚ_ｋ＝０（５０６）またはｚ_ｋ＝１（５０７）のいずれかに設定することを含むことができる。本発明のいくつかの実施形態は、バイナリ決定変数ｚ_ｋ∈｛０，１｝（５０５）の値に応じて、すなわち、ｚ_ｋ＝０（５０６）またはｚ_ｋ＝１（５０７）に応じて、逐次凸化ベースの最適化手順の各反復について、現在の解推測５２０または５３０と、非凸実行可能領域５１１または５１６と、対応する凸近似５２５または５３５との間に複素変換５４０が存在し得るという認識に基づく。

本発明のいくつかの実施形態では、逐次凸化ベースの最適化手順の各反復における部分的凸化ステップは、実現可能値の非凸セット５１１または５１６を定義する１つまたは複数の滑らかな非線形不等式制約関数の局所線形化に基づく。具体的には、部分的凸化ステップは、現在の中間解推測５２０の局所近傍に対応するＭＩＮＬＰ解空間の小領域内で、１つまたは複数の滑らかな非線形不等式制約２８４～２８５によって定義される、実現可能値の非凸セット５１１を近似するために、１つまたは複数の線形不等式制約を、すなわち、１つまたは複数の線形関数５２５に関して１つまたは複数の半空間５２６内に留まるよう、計算することができる。同様に、部分的凸化ステップは、現在の中間解推測の局所近傍に対応するＭＩＮＬＰ解空間の小領域内で、１つまたは複数の滑らかな非線形等式制約２８３によって定義される、実現可能値の非凸セットを近似するために、１つまたは複数の線形等式制約を計算することができる。

具体的には、分離可能なフォーマットのＭＩＮＬＰ２８０は、バイナリ変数５０５のゼロ値ｚ_ｋ＝０（５０６）に対応する非凸コスト関数５５０を定義する１つまたは複数の滑らかな非線形目的関数２８１を含むことができ、同様に、同じ１つまたは複数の滑らかな非線形目的関数２８１が、バイナリ変数５０５の１つの値ｚ_ｋ＝１（５０７）に対応する非凸コスト関数５５５を定義することができる。

本発明のいくつかの実施形態では、逐次凸化ベースの最適化手順の各反復は、非凸コスト関数５５０の局所的最小値５６１または大域的最小値５６２にほぼ向かう探索方向を計算するために、現在の解推測５６０の局所的近傍における１つまたは複数の非凸コスト関数５５０の凸近似５６５を計算する部分的凸化ステップを実行する。本発明のいくつかの実施形態は、逐次凸化ベースの最適化手順の各反復が、たとえばバイナリ決定変数ｚ_ｋ∈｛０，１｝５０５を含む１つまたは複数の整数変数に起因して非凸であるＭＩＣＰ部分問題３２０に対する解を計算し、それにより、値ｚ_ｋ＝０（５０６）について凸近似５６５を存在させ、一方、非凸コスト関数５４５の局所的最小値５７１または大域的最小値５７２にほぼ向かう探索方向を計算するために、１つまたは複数の非凸コスト関数５５５の、異なる凸近似５７５が、値ｚ_ｋ＝１（５０７）に対応する現在の解推測５７０の局所的近傍に存在し得るという認識に基づく。

本発明のいくつかの実施形態は、バイナリ決定変数ｚ_ｋ∈｛０，１｝（５０５）の値に応じて、すなわち、ｚ_ｋ＝０（５０６）またはｚ_ｋ＝１（５０７）に応じて、逐次凸化ベースの最適化手順の各反復について、現在の解推測５６０または５７０と、非凸コスト関数５５０または５５５と、対応する凸近似５６５または５７５との間に複素変換５８０が存在し得るという認識に基づく。

本発明のいくつかの実施形態では、逐次凸化ベースの最適化手順の各反復における部分的な凸化ステップは、非凸コスト関数５５０または５５５を定義する１つまたは複数の滑らかな非線形目的関数２８１の局所的な線形または線形－二次近似５６５または５７５に基づく。具体的には、部分的凸化ステップは、現在の中間解推測５６０または５７０の局所近傍に対応するＭＩＮＬＰ解空間の小領域内で非凸コスト関数５４５を近似するために、１つまたは複数の線形または線形－二次目的関数５６５または５７５を計算することができ、結果として生じるＭＩＣＰ部分問題は、ＭＩＣＰ部分問題の解が、非凸コスト関数５４５の局所的または大域的な最小値に向かうＭＩＮＬＰ解空間内の探索方向を定義するように、１つまたは複数の線形または線形二次目的関数５６５または５７５を含む。

図６Ａは、本発明のいくつかの実施形態による、ＭＩＮＭＰＣコントローラの各時間ステップで解決される、分離可能なフォーマットにおける最適制御構造化ＭＩＮＬＰのコンパクトな定式化のブロック図を示す。具体的には、元の最適制御構造化ＭＩＮＬＰは、予測時間ホライズンｋ＝０，１，．．．，Ｎ－１内の時間ステップの各々に対する行列Ｄ_ｋ、Ｅ_ｋ、Ｅ_Ｎおよびベクトルｃ_ｋに基づいて、分離可能なフォーマットで、目的における関数２８１、等式制約における関数２８３、および不等式制約における関数２８４～２８５を含む。

図６Ｂは、本発明のいくつかの実施形態による、ＭＩＮＬＰ解空間の小領域内の局所線形－二次近似およびＭＩＱＰ部分問題の解に基づいてＭＩＮＬＰ解推測を更新する逐次凸化ベースの最適化手順の実現形態のブロック図を示す。

本発明のいくつかの実施形態では、ＭＩＱＰ部分問題６５０は、連続変数ｙ６３６に関して、すなわち、ＭＩＮＬＰの整数変数ｚ６３７に関する線形項に影響を及ぼすことなく、分離可能なフォーマットのＭＩＮＬＰのコンパクトな定式化６３０における滑らかな非線形関数に適用される逐次凸計画（ＳＣＰ）法または逐次二次計画（ＳＱＰ）法に基づいて構築される。

図６Ｄは、図３Ａのブロック図に類似する、最適制御構造化ＭＩＮＬＰ２５０を解くための反復逐次凸化ベースの最適化手順のブロック図を示し、各反復は、部分的凸化ステップ３１５に続いて、整数変数３２５および連続変数３３０に対する中間解推測を更新する凸ＱＰ部分問題６７５またはＭＩＱＰ部分問題６８０の解からなり、実現可能かつ（局所的に）最適な解が見つかるまで（２５５）行い、その解を用いて、システム１２０の現在の状態１２１およびコマンド１０１を前提として、各制御時間ステップにおいて制御信号１１１を構築することができる。

本発明のいくつかの実施形態では、ＭＩＳＣＰ最適化アルゴリズムの各反復は、降下条件７２１が成り立つように充分に大きいパラメータ値ρ＞０を計算する。本発明の実施形態は、パラメータ値ρ＞０を増加させることにより、ＭＩＮＬＰ解推測の最適性と比較して制約充足度を相対的に強く定量化するメリット関数７１１がもたらされるという認識に基づく。代替的に、パラメータ値ρ＞０を減少させることは、ＭＩＮＬＰ解推測に対する制約充足度と比較して最適性を相対的に強く定量化するメリット関数７１１をもたらす。

図７Ｂは、１つまたは複数のメリット関数評価および方向微分計算に基づいてステップサイズを計算して、図３Ａで説明した逐次凸化ベースの最適化手順におけるＭＩＮＬＰ解推測を更新する（７３０）ためのラインサーチ手順のブロック図を示す。

本発明のいくつかの実施形態では、反復バックトラッキング手順を用いて、初期値α^ｋ＝１から開始してステップサイズ値０≦α^ｋ≦１を選択し、このステップサイズ値は、充分な減少条件７３１がＭＩＮＬＰのメリット関数に対して成り立つまで、０≦α^ｋに向かって反復的に減少させることができる。

図８Ａは、逐次凸化ベースの最適化手順の各反復において、ＭＩＮＬＰ解推測（ｙ^ｋ，ｚ^ｋ）およびＭＩＣＰ部分問題解（Δｙ^ｋ，Δｚ^ｋ）を所与として、メリット関数８１０の値に対する実際の低減対予測される低減の比Ｒ_ｋを計算するためのブロック図を示す。ＭＩＮＬＰにおける目的関数および制約関数のコンパクトな定式化７０５を前提として、メリット関数は、各ＭＩＳＣＰ反復におけるＭＩＮＬＰ解推測の最適性および制約充足度を定量化するよう定義されることができ（７１１）、

メリット関数の値を最小化して、分離可能なフォーマットにおけるＭＩＮＬＰの実現可能かつ（局所的に）最適な解を見つけることができる（６３０）。

図８Ｃは、図３Ｂで説明した逐次凸化ベースの最適化手順においてＭＩＮＬＰ解推測を更新する方法を決定するための信頼領域手順のブロック図を示し、部分的凸化ステップ３１５に基づいて、ＭＩＳＣＰ最適化アルゴリズムの各反復においてＭＩＮＬＰ解空間の小領域内の探索方向を制限するために信頼領域制約の対象となるＭＩＣＰ部分問題を構築および解決する（３６０）。

本発明のいくつかの実施形態は、ＭＩＱＰ部分問題８４０が、ＭＩＱＰ部分問題が分離可能フォーマットにおける元のＭＩＮＬＰ６３０の充分に正確な近似を形成するＭＩＮＬＰ解空間の小領域内で探索方向Δ_ｙを制限するための追加の信頼領域制約８４５を伴う、図６ＢのＭＩＱＰ部分問題６５０に対応するという認識に基づく。

本発明のいくつかの実施形態は、概して、ＭＩＣＰ部分問題が、信頼領域半径ｄ_ｋのいっそう小さな値について解くのに、計算的により安価になるという認識に基づく。したがって、本発明のいくつかの実施形態では、信頼領域手順は、実現可能かつ（局所的に）最適なＭＩＮＬＰ解へのＭＩＳＣＰ最適化アルゴリズムの収束を減速させることなく可能であるとき、信頼領域半径を低減することを目的とする。

図９Ａは、本発明のいくつかの実施形態による、逐次凸化ベースの最適化手順の収束を加速するために使用することができるホモトピー型ペナルティ法の例を示す。例えば、本発明のいくつかの実施形態では、ＭＩＮＬＰ６３０の整数変数が１つまたは複数のバイナリ最適化変数ｚ_ｊ∈｛０，１｝９００を含む場合、ＭＩＴＣＰ最適化アルゴリズムの後続の反復においてＭＩＮＬＰ解推測の異なる値の間で循環することを回避するために、１つまたは複数の追加のペナルティ項をＭＩＮＬＰ目的関数６３１に追加することができる。本発明のいくつかの実施形態は、１つまたは複数の追加のペナルティ項をＭＩＮＬＰ目的関数６３１に加えることにより、ＭＩＳＣＰ最適化アルゴリズムの各反復において解くのに計算的により安価であるＭＩＣＰ部分問題６５０をもたらすことができるという認識に基づく。

図９Ｂは、ＭＩＳＣＰ最適化アルゴリズムの収束を加速してＭＩＮＬＰの実現可能かつ（局所的に）最適な解を見つけるために使用することができるホモトピー型ペナルティ法の例の概略図を示す。本発明のいくつかの実施形態では、ホモトピー型ペナルティ法を使用して、各ＭＩＣＰ部分問題３２０におけるコスト関数を調整して、ＭＩＳＣＰ最適化アルゴリズムを次第に実施して、前のＭＩＳＣＰ反復における整数および／またはバイナリ決定変数の解推測に近いままである、整数および／もしくはバイナリ決定変数のいくつかまたはすべてに対するＭＩＮＬＰ解推測への更新を計算することができる。

本発明のいくつかの実施形態は、整数および／もしくはバイナリ決定変数のいくつかまたはすべてに対するホモトピー型ペナルティ法の使用がＭＩＳＣＰ最適化アルゴリズムにおける循環を防止し得るという認識に基づく。加えて、本発明のいくつかの実施形態は、整数および／もしくはバイナリ決定変数のいくつかまたはすべてに対するホモトピー型ペナルティ法の使用は、ＭＩＳＣＰ最適化アルゴリズムにおいてＭＩＣＰ部分問題を解く計算コストをかなり低減し得るという認識に基づく。例えば、本発明のいくつかの実施形態は、ＭＩＳＣＰ最適化アルゴリズムの各反復においてＭＩＣＰ部分問題を解決するために分枝限定法に基づいており、コスト関数に１つまたは複数の線形ペナルティ項を追加することは、かなり小さい分枝限定探索木をもたらし得、したがって、ＭＩＣＰ部分問題を解決する計算コストがかなり低減され得る。

図９Ｃは、ＭＩＳＣＰ最適化アルゴリズムの収束を加速してＭＩＮＬＰの実現可能かつ（局所的に）最適な解を見出すために使用することができる、１つまたは複数の追加の線形および／または滑らかな非線形不等式制約を加えることによる、ホモトピー型ペナルティ法の例の概略図を示す。例えば、本発明のいくつかの実施形態では、ＭＩＮＬＰ６３０の整数変数が１つまたは複数のバイナリ最適化変数ｚ_ｊ∈｛０，１｝９００を含む場合、ＭＩＳＣＰ最適化アルゴリズムの後続の反復においてＭＩＮＬＰ解推測の異なる値間の循環を回避するために、１つまたは複数の追加の線形および／または滑らかな非線形不等式制約をＭＩＮＬＰ制約６３３に追加することができる。本発明のいくつかの実施形態は、１つまたは複数の追加の線形および／または滑らかな非線形不等式制約をＭＩＮＬＰ制約６３３に加えることが、ＭＩＳＣＰ最適化アルゴリズムの各反復において解くのに計算的により安価であるＭＩＣＰ部分問題６５０をもたらすことができるという認識に基づく。

本発明のいくつかの実施形態では、１つまたは複数の整数変数および／または連続変数の値の特定のセットがＭＩＮＬＰ６３０にとって実行不可能であると検出される場合、次いで、ＭＩＳＣＰ最適化アルゴリズムの後続の反復の各々は、ＭＩＮＬＰ６３０のための１つまたは複数の整数変数および／または連続変数の値の同じセットを再訪することを回避するために、１つまたは複数の線形および／または滑らかな非線形不等式制約を含むことができる。

本発明のいくつかの実施形態は、ＭＩＳＣＰ最適化アルゴリズムの各反復においてＭＩＣＰ部分問題を解決するために分枝限定法に基づいており、１つまたは複数の不等式制約を加えることは、かなり小さい分枝限定探索木をもたらし、したがって、ＭＩＣＰ部分問題を解決する計算コストをかなり低減し得る。

図１１Ａは、いくつかの実施形態による、ＭＩＳＣＰ最適化アルゴリズムにおけるＭＩＣＰ部分問題の整数実行可能解のための探索領域の入れ子木を表すバイナリ制御変数探索ツリーの例の概略図を示す。図１１Ａは、二分探索木１１００を混合整数最適化アルゴリズムの特定の反復で示すことにより、いくつかの実施形態でＭＩＮＭＰＣコントローラを実現するために用いられる分枝限定法の概略図を示す。分枝限定法（Ｂ＆Ｂ）の主な概念は、元のＭＩＣＰ部分問題のパーティションを順次作成し、それらのパーティションを解こうとすることであり、各パーティションは、離散制御変数探索空間の特定の領域に対応する。いくつかの実施形態では、分枝限定法は、パーティションまたはノードを選択し、このパーティションをより小さなパーティションまたは探索領域に分枝する離散制御変数を選択し、パーティションまたは探索領域からなる入れ子木をもたらす。

たとえば、パーティションＰ_１１１０１は、２つのより小さなパーティションまたは領域Ｐ_２１１０２およびＰ_３１１０３、つまり共通領域に入れ子にされる第１の領域および第２の領域に分割または分枝することができる離散探索領域を表わす。第１および第２の領域は互いに素であり、つまり、これらの領域の共通部分は空Ｐ_２∩Ｐ_３＝φである（１１０７）が、それらは元のパーティションまたは領域Ｐ_１をともに形成し、つまり、分枝後、和集合Ｐ_２∪Ｐ_３＝Ｐ_１が成り立つ（１１０６）。次に、分枝限定法は、探索空間の第１および第２のパーティションまたは領域の両方について整数緩和凸問題を解き、互いに対して、および最適目的値に対する現在既知の上限値に対して比較することができる２つの解（局所最適解）をもたらす。第１および／もしくは第２のパーティションまたは領域は、それらの性能指標がＭＩＣＰ部分問題の最適目的値に対する現在既知の上限よりも最適でない場合には、剪定されることができる。第１の領域、第２の領域、またはそれら両方の領域がＭＩＣＰ部分問題に対する実行可能な離散解をもたらす場合には、上限値を更新することができる。分枝限定法は、次いで、さらなる分割のために、領域からなる現在の入れ子木内の残りの領域を選択することにより、継続される。

各パーティションを解くことは依然として難しいかもしれないが、混合整数計画の局所緩和を解くことにより、または双対性を用いることにより、最適目的値の局所下限を得ることは、かなり効率的である。ＭＩＣＰ部分問題のための解法が、局所緩和を解きながら、たまたま整数実行可能解を得た場合には、分枝限定法は次いで、それを用いて、ＭＩＮＬＰの実行可能かつ（局所的に）最適な解を見つけるために、ＭＩＳＣＰ最適化アルゴリズムにおいて元のＭＩＣＰ部分問題の混合整数制御解の大域上限値を得ることができる。これは、すでに作成された特定のパーティションを解くことまたは分枝することを回避するのに役立ち、つまり、これらのパーティションまたはノードは剪定されることができる。このような分割の一般的なアルゴリズム的概念は、木の上部に根ノード、たとえばＰ_１１１０１、ならびに木の底部に葉ノード、たとえばＰ_４１１０４およびＰ_５１１０５を含む、二分探索木１１００として表すことができる。加えて、ノードＰ_２ １１０２およびＰ_３ １１０３は、典型的には、ノードＰ_１ １１０１の直接子と呼ばれ、ノードＰ_１ １１０１は、ノードＰ_２ １１０２およびＰ_３ １１０３の親と呼ばれる。同様に、ノードＰ_４ １１０４およびＰ_５ １１０５は、それらの親ノードＰ_２ １１０２の子である。

図１１Ｂは、いくつかの実施形態による、探索領域の入れ子木および対応する下限／上限値に基づいて、ＭＩＣＰ部分問題３２０の整数実行可能最適解を探索するための分枝限定混合整数最適化アルゴリズムのブロック図を示す。図１１Ｂに示される分枝限定混合整数最適化アルゴリズムのブロック図は、いくつかの実施形態では、ＭＩＮＭＰＣコントローラを実現するために使用されることができる。分枝限定法は、行列およびベクトルからなるＭＩＣＰデータ１１６５に基づいて、現在の制御時間ステップにおける混合整数凸計画（ＭＩＣＰ）の分枝探索木情報を初期化する（１１１０）。この初期化は、さらに、現在の制御時間ステップのウォームスタート初期化１１１０を生成するために、以前の反復からの分枝探索木情報およびＭＩＣＰ解情報１１６０を用いることができる。最適化アルゴリズムの主な目標は、ＭＩＣＰ部分問題解の目的値の上限および下限を構築することである。ステップ１１１１で、上限値と下限値との間のギャップが特定の許容値よりも小さい場合には、混合整数最適制御解１１５５が見つかる。

ステップ１１１１で、下限値と上限値との間のギャップが特定の許容値よりも大きく、最適化アルゴリズムが最大実行時間にまだ到達していない限り、分枝限定法はＭＩＣＰ部分問題の混合整数最適制御解１１５５を求めて反復探索を続ける。分枝限定法の各反復は、求解前分枝手法に基づく考えられ得る変数固定で、整数変数探索空間の次の領域またはパーティションに対応する、木の次のノードを選択することによって、始まる（１１１５）。ノードの選択後、求解後分枝手法に基づく、考えられ得る変数固定で、対応する整数緩和凸問題が解かれる（１１２０）。

整数緩和凸問題が実行可能な解を有する場合には、結果の緩和制御解は、整数変数探索空間のその特定の領域またはパーティションの目的値の下限を与える。ステップ１１２１で、目的値が、ＭＩＣＰ部分問題の最適混合整数制御解の目的値の現在既知の上限よりも大きいと判断される場合、選択されたノードは分枝木から剪定または除去される（１１４０）。しかしながら、ステップ１１２１で、目的値が現在既知の上限より低いと判断され、緩和制御解が整数実行可能である場合には（１１２５）、現在既知の上限および対応する混合整数制御解推定値をステップ１１３０で更新する。

整数緩和凸問題が実行可能な解を有し、目的が現在既知の上限より低い（１１２１）が、緩和制御解がまだ整数実行可能でない場合には（１１２５）、目的の大域下限を分枝木の残りの葉ノードの目的値の最小値に更新することができ（１１３５）、選択されたノードは木から剪定される（１１４０）。加えて、現在のノードから出発して、元のＭＩＣＰ部分問題の離散探索空間の小領域またはパーティションに対応する、結果として得られる予備ＭＩＣＰ部分問題を作成して、分枝木におけるそのノードの子として追加するために（１１５０）、小数値を伴う離散変数が、特定の分枝戦略に従って、分枝のために選択される（１１４５）。

分枝限定法の重要なステップは、どのようにしてパーティションを形成するか、つまり、どのノードを選択し（１１１５）、どの離散変数を分枝のために選択するか（１１４５）である。いくつかの実施形態は、整数緩和凸問題解において小数値を伴うバイナリ制御変数の１つを分枝することに基づく。たとえば、特定のバイナリ制御変数u_i,k ∈ {0,1}が整数緩和凸問題解の一部として小数値を有する場合、いくつかの実施形態は、それぞれ、等式制約u_i,k = 0を一方の部分問題に、等式制約u_i,k= 1を他方の部分問題に加えることにより、ＭＩＣＰ部分問題の２つのパーティションを作成する。いくつかの実施形態は、以前の分枝判断からの情報に基づいて将来の分枝挙動を予測することを目的とする、変数選択の信頼性分枝戦略に基づく（１１４５）。

いくつかの実施形態は、後入れ先出し（ＬＩＦＯ）バッファを用いて実現することができる深さ優先ノード選択戦略を用いる分枝限定法に基づく。解くべき次のノードが現在のノードの子の１つとして選択され、ノードが剪定されるまで、つまり、ノードが実行不可能となるか、最適となるか、または現在既知の上限値に支配されるまで、このプロセスが繰り返され、その後、バックトラッキング手順が続く。代わりに、いくつかの実施形態は、現在最も低い局所下限を有するノードを選択する最良優先戦略を用いる分枝限定法に基づく。いくつかの実施形態は、深さ優先ノード選択策と最良優先ノード選択策との組み合わせを採用し、整数実現可能制御解が見つかるまで深さ優先ノード選択戦略が用いられ、その後、分枝限定に基づく最適化アルゴリズムの後続の反復において、最良優先ノード選択戦略が用いられる。後者の実現例は、分枝限定手順の開始の早い段階で整数実行可能制御解を見つけて（深さ優先）早期剪定を可能にし、その後、より良い実行可能解を求める、より貪欲な探索が続く（最良優先）ことを目的とすることにより、動機づけられている。

分枝限定法は、１つまたは複数のいずれかの以下の条件が満たされるまで反復を続ける。

プロセッサの最大実行時間に達する。

分枝探索木のすべてのノードが剪定されて、凸緩和を解くためまたは分枝するために新たなノードを選択できない。

ＭＩＣＰ部分問題解の目的の大域上下限値間の最適性ギャップが許容値よりも小さい。

図１２Ａは、いくつかの実施形態の原理を採用する予測コントローラ１２０２を含む車両１２０１の概略図を示す。本明細書で用いられるように、車両１２０１は、乗用車、バス、またはローバーなどの任意のタイプの車輪付き車両とすることができる。また、車両１２０１は、自律車両または半自律車両とすることもできる。たとえば、いくつかの実施形態は、車両１２０１の運動を制御する。運動の例には、車両１２０１のステアリングシステム１２０３によって制御される車両の横方向運動が含まれる。一実施形態において、ステアリングシステム１２０３は、コントローラ１２０２によって制御される。追加的に、または代替的に、ステアリングシステム１２０３は、車両１２０１の運転者によって制御されることができる。

車両は、エンジン１２０６も含むことができ、エンジン１２０６は、コントローラ１２０２または車両１２０１の他のコンポーネントによって制御することができる。車両は、周囲の環境を検知するための１つ以上のセンサ１２０４も含むことができる。センサ１２０４の例には、距離レンジファインダー、レーダー、ライダー、およびカメラが含まれる。車両１２０１は、それの現在の運動量および内部状態を検知するための１つ以上のセンサ１２０５を含むこともできる。センサ１２０５の例には、全地球測位システム（ＧＰＳ）、加速度計、慣性測定ユニット、ジャイロスコープ、シャフト回転センサ、トルクセンサ、偏向センサ、圧力センサ、および流量センサが含まれる。センサは、コントローラ１２０２に情報を与える。車両は、有線または無線通信チャネルを介してコントローラ１２０２の通信機能を可能にするトランシーバ１２０７を装備することができる。

図１２Ｂは、いくつかの実施形態による、コントローラ１２０２、たとえば混合整数非線形モデル予測コントローラ（ＭＩＮＭＰＣ）と車両１２０１の他のコントローラ１２２０との間の対話の概略図を示す。たとえば、いくつかの実施形態では、車両１２０１のコントローラ１２２０は、それぞれ、車両１２２０の回転および加速を制御するステアリングコントローラ１２２５およびブレーキ／スロットルコントローラ１２３０である。そのような場合、予測コントローラ１２０２は、車両１２０１の状態を制御するよう、コントローラ１２２５および１２３０に制御入力を出力する。コントローラ１２２０は、予測コントローラ１２０２の制御入力をさらに処理する車線維持支援コントローラ１２３５などのハイレベルコントローラも含むことができる。両方の場合とも、コントローラ１２２０は、車両１２０１の運動を制御するために、車両１２０１のステアリングホイールおよび／またはブレーキなどの、車両１２０１の少なくとも１つのアクチュエータを制御するために、予測コントローラ１２０２の出力を用いる。さらに、予測コントローラ１２０２は、混合整数最適制御解に基づいて車両１２０１への入力を決定し、車両１２０１への入力は、車両１２０１の加速度、車両１２０１のエンジントルク、ブレーキトルク、および操舵角のうちの１つまたは組合せ、ならびに離散制御判断、システムダイナミクスにおける切換え、ギアシフト、および障害物回避制約のうちの１つまたは組合せをモデル化するための離散最適化変数を含む。

図１２Ｃは、いくつかの実施形態の原理を採用する制御車両のための経路および／または運動計画法の概略図を示す。図１２Ｃは、本開示の実施形態を用いることにより、動的に実行可能であり最適であることが多い軌道１２５５を計算することができる、自律または半自律制御車両１２５０の概略図を示す。生成された軌道は、車両を特定の道路境界１２５２内に維持することを目的とし、他の制御および／または非制御車両を回避することを目的とし、すなわち、これらの車両は、この特定の制御車両１２５０に対する障害物１２５１である。いくつかの実施形態では、障害物１２５１の各々は、各障害の１つ以上の追加の離散変数を含む、制約付き混合整数非線形計画問題の時間または空間定式化において１つ以上の不等式制約によって表すことができる。たとえば、混合整数非線形モデル予測コントローラを実現するように構成された実施形態に基づいて、自律または半自律制御車両１２５０は、たとえば、車両１２５０の運動を制御するために、速度、加速度または操舵入力といった連続的判断を実時間で追加的に行いながら、左側もしくは右側の別の車両を追い越すか、または代わりに、道路１２５２の現在の車線内の別の車両の後ろに留まるなど、離散的判断を実時間で行うことができる。

図１２Ｄは、いくつかの実施形態に基づく単一車両または複数車両意思決定モジュールの例示的な交通場面を示す。図１２Ｄは、自車両１２７１と呼ばれる、制御下の１つまたは複数の車両を伴うシナリオを描写し、交通は、１２７２に類似して示される他の車両からなり、車線は、例えば、Ｌ６として、１２７３と印され、停止線は、例えば、Ｓ１として、１２７４と印され、交差点は、たとえば、Ｉ３として、１２７５と印される。最終目的地１２６２を有する位置１２６１の車両について、経路付けモジュールは、矢印１２６３によって示される道路のシーケンスと、矢印１２６４によって示される方向変更のシーケンスとを提供する。しかしながら、道路シーケンス１２６３および方向変更シーケンス１２６４は、それ自体では車両の軌道または経路を指定しないことに留意されたい。車両がどの車線で走行すべきか、車両が車線を変更すべきか現在の車線に留まるべきか、車両が減速を開始して停止線で停止すべきか、車両が交差点を横切ることを許可されているかなど、なすべきいくつかの離散的な判断がある。さらに、車両がその初期地点からその目的地までの移動において達成すべき位置および向きの時限シーケンスなど、なすべきいくつかの連続的な判断がある。これらの判断は、車両が対応する位置に到達する瞬間におけるそのときの交通に大きく依存し、これは、交通運動の不確実性および車両がその位置に到達することになる瞬間の不確実性に起因して、概して、経路付けモジュールには未知である。本開示のいくつかの実施形態では、運動計画を、１つまたは複数の被制御自車両１２７１について、場合によっては、車両間（Ｖ２Ｖ）および／またはスマートインフラストラクチャシステムと車両との間（Ｖ２Ｘ）の協調を可能にする通信を用いて、１つまたは複数の接続された混合整数非線形計画問題を解決することによって、計算することができる。

図１３Ａおよび図１３Ｂは、本開示のいくつかの実施形態の原理を用いる宇宙機混合整数非線形モデル予測制御問題の定式化の概略図である。図１３Ａおよび図１３Ｂは、スラスタ１３５０および運動量交換装置１３５１などの複数のアクチュエータを備えた宇宙機１３０２を示す。運動量交換装置のタイプの例には、リアクションホイール（ＲＷ）およびジャイロスコープが含まれる。宇宙機１３０２は、アクチュエータに送信されるコマンドに応じて、宇宙機１３０２の位置、速度、姿勢または向きなどの量が動作により変化する、宇宙空間で飛行するように設計された車両、船舶、または機械である。命令されると、アクチュエータは、宇宙機１３０２にその速度を増加または減少させる力を与え、それにより宇宙機１３０２にその位置を変換させ、および、命令されると、アクチュエータは、さらに、宇宙機１３０２にトルクを与え、宇宙機１３０２を回転させ、それにより、その姿勢または向きを変える。本明細書で用いられるように、宇宙機１３０２の動作は、そのような量を変化させる宇宙機１３０２の動きを決定するアクチュエータの動作によって決定される。

宇宙機１３０２は、地球１３６１、月、および／または他の天体惑星、星、小惑星、彗星などの１つ以上の重力体の周り、間、または近くで、開放または閉鎖軌道経路１３６０に沿って宇宙空間を飛行する。通常、軌道経路に沿った望ましい位置または目標位置１３６５が与えられる。参照フレーム１３７０が所望の位置に取り付けられ、フレームの原点、すなわちその参照フレーム内のすべてゼロの座標は、常に所望の位置の座標である。

宇宙機１３０２は、さまざまな外乱力１３１４を受ける。これらの外乱力には、宇宙機１３０２の軌道経路を判断する際に考慮されなかった力が含まれ得る。これらの外乱力は、宇宙機１３０２に作用して、軌道上の所望の位置から宇宙機１３０２を遠ざける。これらの力には、重力の引力、放射圧、大気抵抗、非球形中心体、および推進剤の漏れが含まれるが、これらに限定されない。したがって、宇宙機１３０２は目標位置から離れた距離１３６７にある可能性がある。

外乱力のため、宇宙機１３０２をその軌道に沿った所望の位置に維持することが常に可能であるとは限らない。したがって、代わりに、宇宙機１３０２は、所望の位置の周りにおいて、指定された寸法１３６４を伴う窓１３６６内にとどまることが望まれる。そのために、宇宙機１３０２は、所望の目標ウィンドウ内に含まれる任意の経路１３８０に沿って移動するように制御される。この例では、ウィンドウ１３６６は長方形の形状を有するが、ウィンドウの形状は、実施形態ごとに異なり得る。

宇宙機１３０２は、多くの場合、所望の向きを維持することを必要ともされる。たとえば、宇宙機に固定された参照フレーム１３７４は、遠方の星１３７２に対して固定された慣性参照フレーム１３７１、または常に地球の方向を指す態様で向き付けられた参照フレーム１３７３などの、所望の参照フレームと位置合わせする必要がある。しかしながら、宇宙機１３０２の形状に応じて、異なる外乱力１３１４が宇宙機１３０２に不均一に作用し、それによって、外乱トルクが生成され、宇宙機１３０２をその所望の向きから外れるように回転させる可能性がある。外乱トルクを補償するために、リアクションホイールなどの運動量交換装置１３５１を用いて外乱トルクを吸収し、それにより宇宙機がその所望の方向を維持できるようにする。

運動量交換装置が飽和し、それによって外乱トルクを補償する能力を失わないように、それらの保存された運動量は、たとえばリアクションホイールのスピン速度を下げることによって、無負荷状態にされなければならない。運動量交換装置を無負荷状態にすると、宇宙機１３０２に望ましくないトルクが加わる。このような望ましくないトルクもスラスタによって補償される。

本発明のいくつかの実施形態では、１つまたは複数の非線形方程式を使用して被制御システムのダイナミクスおよび／または制約を記述し、ＭＩＮＭＰＣコントローラは、混合整数最適制御解に基づいて宇宙機１３０２への入力を決定し、宇宙機１３０２への入力は、スラスタおよび運動量交換装置の１つまたは組み合わせを作動させ、離散最適化変数を用いて、離散制御判断、システムダイナミクスにおける切換え、スラスタコマンドの整数値、および障害物回避制約のうちの１つまたは組合せをモデル化する。

いくつかの実施形態において、宇宙機１３０２はハイブリッドシステムとしてモデル化することができ、アクチュエータに送信されるコマンドは、混合整数非線形モデル予測コントローラ（ＭＩＮＭＰＣ）などの予測コントローラを用いて計算される。たとえば、いくつかの実施形態では、スラスタ１３５０に送信されるコマンドは、離散的な値のセットしかとることができず、したがって、混合整数制御ホライズン内の各段階についてバイナリまたは整数制御入力変数のセットとなる。

本発明のいくつかの実施形態において、予測コントローラは、宇宙機１３０２が、軌道に沿った所望の位置に近い、特定の寸法の特定のゾーン１３８５の外側に留まるように設計される。後者のゾーンは、時間において固定することも、時間的に変化させることもでき、多くの場合、除外ゾーン１３８５と呼ばれ、このゾーンに対して、混合整数制御ホライズン内の段階ごとにバイナリまたは整数の制御入力変数の追加セットを用いて、対応する論理不等式制約をモデル化できる。この例では、除外ゾーン１３８５は長方形であり、所望のウィンドウ１３６６の角に位置決めされているが、所望の目標ウィンドウ内の除外ゾーンの形状および位置は、異なる実施形態で異なり得る。

図１４Ａは、いくつかの実施形態による、コントローラ１４６０によって制御される蒸気圧縮システム１４００の概略図を示す。コントローラ１４６０は、混合整数非線形モデル予測制御（ＭＩＮＭＰＣ）を実現するコントローラなどの予測コントローラを含む。蒸気圧縮システム（ＶＣＳ）１４００の構成要素は、屋内空間またはゾーン１４５０に位置する室内機熱交換器１４２０、周囲環境に位置する室外機熱交換器１４３０、圧縮機１４１０および膨張弁１４４０を含むことができる。熱負荷１４１５は屋内空間またはゾーン１４５０に作用する。

さらに、ＶＣＳ１４００は、圧縮機を出る高圧冷媒を室外機熱交換器または室内機熱交換器のいずれかに向け、室内機熱交換器または室外機熱交換器のいずれかから戻る低圧冷媒を圧縮機の入口に向けるために用いられる逆流弁１４５５を含むことができる。高圧冷媒が室外機熱交換器に向けられる場合、室外機熱交換器は凝縮器として機能し、室内機は蒸発器として機能し、システムはゾーンから周囲環境に熱を排除し、それは動作上は「冷却モード」と呼ばれる。逆に、高圧冷媒が室内機熱交換器に向けられる場合、室内機熱交換器は凝縮器として機能し、室外機熱交換器は蒸発器として機能し、周囲環境から熱を抽出し、この熱をゾーン内に圧送し、それは動作上は「加熱モード」と呼ばれる。

図１４Ｂは、いくつかの実施形態による、ＶＣＳ１４００で用いられる信号、センサ、およびコントローラの構成の例を示す。コントローラ１４６０は、周囲の気温などの測定可能な外乱を含む、システムの動作に関するさまざまな温度、圧力、流量、その他の情報を測定するように構成されたセンサ１４７０からの情報を読み取る。コントローラ１４６０には、所望のゾーン温度などの、プロセスの測定信号の所望の値を表す設定点１４６６を設けることができる。設定点情報は、サーモスタット、ワイヤレスリモートコントロール、または内部メモリもしくは記憶媒体から取得できる。次に、コントローラは、いくつかの測定された出力がそれらの設定点に駆動されるように、制御入力を計算する。これらの制御入力は、室内機ファン速度１４８０、室外機ファン速度１４８１、圧縮機回転速度１４８２、膨張弁位置１４８３、および逆流弁位置１４８４を含むことができる。このようにして、コントローラは、システムに作用する熱負荷などの外乱１４６８の存在下で設定点値が達成されるように、蒸気圧縮システムの動作を制御する。

いくつかの実施形態では、ＶＣＳ１４００はハイブリッド非線形システムとしてモデル化することができ、アクチュエータに送信されるコマンドは、混合整数非線形モデル予測コントローラ（ＭＩＮＭＰＣ）などの予測コントローラを用いて計算される。たとえば、いくつかの実施形態では、弁および／またはファンに送信されるコマンドは、離散的な値のセットしかとることができず、したがって、混合整数制御ホライズン内の各段階についてバイナリまたは整数制御入力変数のセットとなる。

いくつかの実施形態では、予測コントローラは、混合整数最適制御解に基づいて蒸気圧縮システムへの入力を決定し、蒸気圧縮システムへの入力は、室内機ファン速度、室外機ファン速度、圧縮機回転速度、膨張弁位置、および逆流弁位置の１つまたは組み合わせを含み、離散最適化変数を用いて、離散制御判断、システムダイナミクスにおける切換え、ならびに弁および／またはファンに送信されるコマンドのための整数値の１つまたは組み合わせをモデル化する。

いくつかの実施形態では、ＶＣＳ１４００の動的挙動は、システムの現在の状態および現在の制御入力値に応じて、急速に変化するか、または特定の瞬間で切り替わることさえあり得る。スイッチングダイナミクスを有する結果的なハイブリッドＶＣＳ１４００は、混合整数制御ホライズン内の各段階ごとにバイナリまたは整数制御入力変数の追加セットを用いてモデル化できる。

図１５は、例示的な実施形態による、システムを制御するための方法１５００を示す。ステップ１５０１において、本方法は、システムの状態の測定値を含むフィードバック信号を受け入れることを含む。ステップ１５０３において、本方法は、混合整数非線形計画（ＭＩＮＬＰ）問題の実現可能かつ（局所的に）最適な解を探索する混合整数逐次凸計画（ＭＩＳＣＰ）最適化アルゴリズムを使用して、混合整数非線形最適制御問題を解くことを含む。ステップ１５０５において、制御信号に基づいてシステムを制御して、システムの状態を変更する。

本開示の上述の実施形態は、多数の方法のいずれかで実現することができる。たとえば、実施形態は、ハードウェア、ソフトウェア、またはそれらの組み合わせを用いて実現されてもよい。ソフトウェアで実現される場合、ソフトウェアコードは、単一のコンピュータで提供されるか、複数のコンピュータに分散されるかに関係なく、任意の好適なプロセッサまたはプロセッサの集まりにおいて実行されることができる。そのようなプロセッサは、集積回路コンポーネント内に１つ以上のプロセッサを備えた集積回路として実現されてもよい。ただし、プロセッサは、任意の好適な形式の回路系を用いて実現されてもよい。

また、本明細書で概説される様々な方法またはプロセスは、様々なオペレーティングシステムまたはプラットフォームのいずれか１つを用いる１つ以上のプロセッサで実行可能なソフトウェアとしてコード化されてもよい。加えて、そのようなソフトウェアは、多数の好適なプログラミング言語および／またはプログラミングもしくはスクリプトツールのいずれかを用いて記述されてもよく、フレームワークまたは仮想マシンで実行される実行可能マシン言語コードまたは中間コードとしてコンパイルされてもよい。通常、プログラムモジュールの機能は、さまざまな実施形態において所望のように組み合わせられるかまたは分散されてもよい。

また、本開示の実施形態は、例が提供されている方法として具体化することができる。方法の一部として実行される行為は、任意の好適な方法で順序付けされてもよい。したがって、例示的な実施形態において連続的な行為として示されているいくつかの行為を同時に実行することを含むことができる、例示とは異なる順序で行為が実行される実施形態を構築することができる。

本開示を好ましい実施形態の例によって説明してきたが、本開示の範囲内で様々な他の適応および変更を行うことができることを理解されたい。したがって、特許請求の範囲の目的は、本開示の真の精神および範囲内にあるそのようなすべての変形および修正を網羅することである。

Claims (15)

1. 非線形ダイナミクスならびに動作の連続要素および離散要素を有するハイブリッド動的システムを制御するための予測フィードバックコントローラであって、少なくとも１つのプロセッサと、命令が記憶されたメモリとを備え、前記命令は、前記少なくとも１つのプロセッサによって実行されると、前記予測フィードバックコントローラに、
   前記予測コントローラの現在の状態、前記ハイブリッド動的システムの１つまたは複数のアクチュエータの現在の状態、および前記ハイブリッド動的システムの出力の現在の状態のうちの１つまたは組合せを含む、前記ハイブリッド動的システムの現在の状態を示す測定値を含むフィードバック信号を受け入れさせ、
   １つまたは複数の制約の対象となる制御目的を、前記制御目的に従って前記ハイブリッド動的システムの前記現在の状態を変更するための制御コマンドを示す解を用いて最適化する混合整数非線形計画（ＭＩＮＬＰ）問題を定式化させ、前記制約は、等式制約、不等式制約、または両方を含み、前記ＭＩＮＬＰ問題の前記制約および前記制御目的は、前記ハイブリッド動的システムの前記動作の前記連続要素を表す連続最適化変数の１つまたは複数の非線形関数と、前記ハイブリッド動的システムの前記動作の前記離散要素を表す整数最適化変数の１つまたは複数の線形関数とを含み、さらに、前記命令は、前記少なくとも１つのプロセッサによって実行されると、前記予測フィードバックコントローラに、
   終了条件が満たされるまで、逐次凸化ベースの最適化手順の複数の反復にわたって前記ＭＩＮＬＰ問題を解かせ、反復を実行するために、前記予測フィードバックコントローラは、現在の解推測を含む前記解の空間の一部の部分的凸化を実行するように構成され、さらに、前記命令は、前記少なくとも１つのプロセッサによって実行されると、前記予測フィードバックコントローラに、
   前記ＭＩＮＬＰ問題の前記解に従って生成された前記制御コマンドを前記ハイブリッド動的システムに提出させ、それによって前記ハイブリッド動的システムの前記現在の状態の変化を引き起こさせ、
   前記予測フィードバックコントローラは、混合整数非線形モデル予測制御（ＭＩＮＭＰＣ）を使用して実現され、前記ＭＩＮＭＰＣは、前記システムの現在の状態および制御コマンドに基づいて制御信号を計算し、前記ＭＩＮＭＰＣは、各制御時間ステップにおいて制約付き混合整数非線形最適化問題を解くことによって、前記ハイブリッド動的システムの予測時間ホライズンにわたる将来の最適な離散および連続制御入力のシーケンスを含む制御解を計算し、
   前記ＭＩＮＭＰＣは、前記ハイブリッド動的システムの動的システムモデルに従って計画され、
   前記ＭＩＮＬＰ問題は、前記動作の前記離散要素が前記ＭＩＮＬＰ問題の前記線形関数にのみ存在することを保証する分離可能なフォーマットに定式化され、
   前記部分的凸化は、部分的に凸化されたＭＩＮＬＰを生成するために前記ＭＩＮＬＰの前記線形関数を近似することなく前記ＭＩＮＬＰの前記非線形関数の凸近似を生成し、さらに、前記命令は、前記少なくとも１つのプロセッサによって実行されると、前記予測フィードバックコントローラに、前記部分的に凸化されたＭＩＮＬＰ問題の混合整数凸計画（ＭＩＣＰ）定式化を解くことによって前記現在の解推測を更新させることにおいて特徴付けられる、予測フィードバックコントローラ。
2. 前記プロセッサは、
   追加の整数最適化変数および追加の連続最適化変数の１つまたは組合せを元のフォーマットに追加することによって、前記ＭＩＮＬＰ問題を前記元のフォーマットから前記分離可能なフォーマットに変換し、それによって、前記動作の前記離散要素が分離可能なフォーマットで前記ＭＩＮＬＰの前記線形関数にのみ存在することを保証するよう構成される、請求項１に記載の予測フィードバックコントローラ。
3. 前記部分的凸化を実行するために、前記プロセッサは、
   前記ＭＩＮＬＰ問題の目的関数または前記制約における関数が前記整数最適化変数または前記連続最適化変数の関数であるかどうかを識別し、
   前記関数が前記連続最適化変数の滑らかな非線形関数である場合、前記ＭＩＮＬＰ問題の前記解空間内の前記現在の解推測の局所近傍において前記滑らかな非線形関数の凸近似を計算し、
   前記関数が前記整数最適化変数の線形関数である場合、前記整数変数を保存することによって前記凸近似を回避し、前記ＭＩＮＬＰの前記解空間の非凸部分内にあるよう構成される、請求項１に記載の予測フィードバックコントローラ。
4. 前記凸近似は、記号微分、数値微分またはアルゴリズム微分を使用して、前記滑らかな非線形関数の１つまたは複数の一次および／または高次方向導関数を評価することによって、前記ＭＩＮＬＰ問題の前記解空間内の前記現在の解推測の局所近傍における前記滑らかな非線形関数の局所制約線形化または線形－二次目的近似によって計算される、請求項３に記載の予測フィードバックコントローラ。
5. 前記反復の前記現在の解推測を更新するために、前記予測フィードバックコントローラは、
   前記部分的に凸化されたＭＩＮＬＰの前記ＭＩＣＰ問題を解いて、前記連続最適化変数についての探索方向および前記整数最適化変数についての探索方向を計算し、
   前記整数最適化変数の現在値を、前記整数最適化変数の各々に対する制約が整数値であることを満たすステップで、前記整数最適化変数の前記探索方向に向かって更新し、
   前記連続最適化変数の現在値を、ラインサーチ法を用いて選択されるステップサイズ値０≦αｋ≦１で、前記連続最適化変数の前記探索方向に向かって更新するよう構成される、請求項１に記載の予測フィードバックコントローラ。
6. 前記ステップサイズ値は、０と１との間にあり、前記ＭＩＮＬＰ問題の前記解の最適性と実現可能性との均衡をとるメリット関数に基づいて前記反復のために選択され、前記メリット関数の値は、前記逐次凸化ベースの最適化手順の少なくとも２つの反復の間で減少する、請求項５に記載の予測フィードバックコントローラ。
7. 前記ステップサイズ値は、１の初期ステップサイズ値から始まる反復ラインサーチ手順に基づいて選択され、前記予測フィードバックコントローラは、前記ステップサイズ値を選択するために前記反復ラインサーチ手順の１つまたは複数の反復を実行し、各反復は、
   前記ＭＩＮＬＰ問題の前記解の最適性と実現可能性との均衡をとるメリット関数について減少条件が満たされるかどうかをテストし、
   充分な減少条件が満たされる場合、前記反復ラインサーチ手順を終了し、前記ステップサイズ値を使用して、前記連続最適化変数の現在値を前記連続最適化変数の前記探索方向に向かって更新し、そうでない場合には、
   前記ステップサイズ値を減少させ、前記反復ラインサーチ手順を継続するよう構成されるか、または、
   前記メリット関数は、目的関数と、前記ＭＩＮＬＰ問題における前記等式制約の各々に対する違反および前記不等式制約の各々に対する違反に適用される１つまたは複数のペナルティ関数との組み合わせである、請求項６に記載の予測フィードバックコントローラ。
8. 前記部分的に凸化されたＭＩＮＬＰの前記ＭＩＣＰ問題は、１つまたは複数の信頼領域不等式制約を含み、前記連続最適化変数の前記探索方向が信頼領域半径値を下回ることを保証する、請求項５に記載の予測フィードバックコントローラ。
9. 前記反復の前記現在の解推測を更新するために、前記プロセッサは、
   前記部分的に凸化されたＭＩＮＬＰ問題の前記ＭＩＣＰ解の最適性と実現可能性との均衡をとるメリット関数の値について実際の低減対予測される低減の比を計算し、
   前記メリット関数の値についての前記実際の低減対予測される低減の比が閾値を上回る場合、前記整数および連続最適化変数の現在の値を前記整数および連続最適化変数の前記探索方向に向かって更新するよう構成される、請求項８に記載の予測フィードバックコントローラ。
10. 前記部分的に凸化されたＭＩＮＬＰの前記ＭＩＣＰ問題の前記解に基づいて前記信頼領域半径値を更新するために、前記プロセッサは、
    前記メリット関数の値の前記実際の低減対予測される低減の比または前記連続最適化変数の前記探索方向が閾値を下回る場合、前記信頼領域半径値を減少させ、前記連続最適化変数の前記探索方向が次の反復のうちの１つまたは複数において低減されることを保証し、そうでない場合には、
    前記信頼領域半径値を増加させ、前記連続最適化変数の前記探索方向が次の反復の１つまたは複数において増加されることを保証する、請求項９に記載の予測フィードバックコントローラ。
11. 分枝限定（Ｂ＆Ｂ）最適化法を用いて、前記部分的に凸化されたＭＩＮＬＰの前記ＭＩＣＰ問題の大域的に最適な解を計算するか、または、
    ホモトピー型ペナルティ法を用いて、前記逐次凸化ベースの最適化手順の少なくとも２回の反復の間で、正の重み値に基づいて、前記整数最適化変数の１つまたは複数の値の変化にペナルティを課す、請求項１に記載の予測フィードバックコントローラ。
12. 前記整数最適化変数の前記現在値は、前記逐次凸化ベースの最適化手順の１つまたは複数の反復後に固定され、前記逐次凸化ベースの最適化手順の１つまたは複数の反復において前記現在の解推測を更新するために、前記予測フィードバックコントローラは、
    前記整数最適化変数の前記固定された現在値を所与として、前記部分的に凸化されたＭＩＮＬＰの凸計画（ＣＰ）問題を解いて、前記連続最適化変数の探索方向を計算し、
    前記連続最適化変数の現在値を、前記ステップサイズ値で、前記連続最適化変数の前記探索方向に向かって更新するよう構成される、請求項５に記載の予測フィードバックコントローラ。
13. 前記ホモトピー型ペナルティ法を用いて、前記逐次凸化ベースの最適化手順の前記少なくとも２回の反復の間で、前記正の重み値に基づいて、前記整数最適化変数の１つまたは複数の前記値の前記変化にペナルティを課し、
    前記ホモトピー型ペナルティ法は、前記逐次凸化ベースの最適化手順の、前記ＭＩＮＬＰ問題の実現可能および／または最適解への収束を加速するために、前記部分的に凸化されたＭＩＮＬＰの前記ＭＩＣＰ問題の目的関数において１つまたは複数のペナルティ項を追加するか、または、
    前記ホモトピー型ペナルティ法は、前記逐次凸化ベースの最適化手順の、前記ＭＩＮＬＰ問題の実現可能および／または最適解への収束を加速するために、前記部分的に凸化されたＭＩＮＬＰの前記ＭＩＣＰ問題の前記不等式制約に、複数の線形および／または滑らかな非線形不等式制約の１つまたは組合せを加える、請求項１１に記載の予測フィードバックコントローラ。
14. ある制御時間ステップにおける前記制約付き混合整数非線形最適化問題の解を、前記逐次凸化ベースの最適化手順のための初期解推測として使用して、次の制御時間ステップにおいて前記制約付き混合整数非線形最適化問題の解を計算する、請求項１に記載の予測フィードバックコントローラ。
15. 請求項１に記載の予測フィードバックコントローラを備えるハイブリッド動的システムであって、
    前記ハイブリッド動的システムは、前記制御コマンドを表す操作入力信号によって制御される装置を含み、前記入力信号は、前記ハイブリッド動的システムの前記動作の前記連続要素の値および前記ハイブリッド動的システムの前記動作の前記離散要素の値を指定し、前記連続要素は、電圧、圧力、力、トルク、操舵角、速度および温度のうちの１つまたは組合せを含み、前記離散要素は、エネルギーレベル、量子化されたバルブ入力、ギアシフト、オン／オフ作動、車線選択、および障害物回避決定変数のうちの１つまたは組み合わせを含むか、または、
    前記予測フィードバックコントローラによって生成される前記制御コマンドは、前記ハイブリッド動的システムの目標状態を指定し、前記ハイブリッド動的システムは、前記ハイブリッド動的システムの前記現在の状態と前記ハイブリッド動的システムの前記目標状態との間の誤差を低減するために、前記ハイブリッド動的システムの前記アクチュエータへの１つまたは複数の制御入力を生成するように構成される追跡コントローラを備えるか、または、
    前記システムは車両であり、前記予測フィードバックコントローラは、前記ＭＩＮＬＰ解に基づいて前記車両への入力を決定し、前記車両への前記入力は、前記車両の加速度、前記車両のエンジントルク、ブレーキトルク、および操舵角の１つまたは組み合わせを含み、離散最適化変数を用いて、離散制御判断、システムダイナミクスにおける切換え、ギアシフト、および障害物回避制約の１つまたは組み合わせをモデル化するか、または、
    前記システムは宇宙機であり、前記予測フィードバックコントローラは、前記ＭＩＮＬＰ解に基づいて前記宇宙機への入力を決定し、前記宇宙機への前記入力は、スラスタおよび運動量交換装置の１つまたは組み合わせを作動させ、前記離散最適化変数を用いて、離散制御判断、前記システムダイナミクスにおける切換え、スラスタコマンドのための整数値、および障害物回避制約の１つまたは組み合わせをモデル化するか、または、
    前記システムは蒸気圧縮システムであり、前記予測フィードバックコントローラは、前記ＭＩＮＬＰ解に基づいて前記蒸気圧縮システムへの入力を決定し、前記蒸気圧縮システムへの前記入力は、室内機ファン速度、室外機ファン速度、圧縮機回転速度、膨張弁位置、および逆流弁位置の１つまたは組み合わせを含み、前記離散最適化変数を用いて、離散制御判断、システムダイナミクスにおける切換え、ならびに前記弁および／または前記ファンに送信されるコマンドのための整数値の１つまたは組み合わせをモデル化する、ハイブリッド動的システム。