(57)【特許請求の範囲】
【請求項１】
システムの状態変数及び制御変数に対する等式制約及び不等式制約を含む制約を条件として前記システムを制御する予測コントローラであって、
前記システムの出力の測定値を用いて前記システムの現在の状態を推定する推定器と、
各制御ステップにおいて、必要な最適性条件の行列方程式を解いて制御解を生成し、前記制御解を用いて前記システムを制御し、前記システムの状態を変更するコントローラであって、前記行列方程式は、前記システムの前記等式制約の制約ヤコビ行列を有するブロック構造化行列を含み、前記コントローラは、第１レベルの反復と、前記第１レベルの反復のうちの或る反復内で実行される第２レベルの反復とを含む２つのレベルの反復を用いて前記制御解を反復して求める、コントローラと、
を備え、
第１の終了条件が満たされるまで実行される前記第１レベルの反復は、
制御ホライズン内の各時点のアクティブ不等式制約を選択し、
アクティブ不等式制約セットの変更のための低ランク更新を用いて前記制約ヤコビ行列を更新して、前記等式制約及び前記アクティブ不等式制約を含め、
前記制約ヤコビ行列の前記低ランク更新に応答して、低ランク因数分解更新を用いて前処理行列を更新し、
第２の終了条件が満たされるまで実行される前記第２レベルの反復は、前記更新された前処理行列を用いて、前記更新された制約ヤコビ行列を有する前記行列方程式を解いて、前記制御解を生成する、予測コントローラ。
【請求項２】
不等式制約の制約関数が、或る時点において前記不等式制約の制約境界に等しいとき、前記不等式制約は、前記時点においてアクティブであり、前記第１レベルの反復は、前記システムの前記現在の状態及び制御入力の現在のシーケンスに基づいて前記アクティブ不等式制約セットを選択する、請求項１に記載の予測コントローラ。
【請求項３】
前記アクティブ不等式制約セットの各変更は、前記制約ヤコビ行列のランク１更新に応答して、前記前処理行列のランク１因数分解更新をもたらす、１つの制約のみが追加又は除去されることに対応する、請求項１に記載の予測コントローラ。
【請求項４】
前記前処理行列は、前記行列方程式に用いられる計算精度と比較して低下した計算精度を用いて更新されるか又はその値が求められる、請求項１に記載の予測コントローラ。
【請求項５】
前記第１の終了条件は、前記制御解の実行可能性と、前記制御解の最適性とを含み、
前記コントローラは、前記制御解の最適性及び実行可能性を検査し、前記第１の終了条件が満たされているときは、前記第１レベルの反復を抜け、そうでないときは、
前記制御解は最適でなく、前記コントローラは、前記制御解の最適性を妨げる負の双対変数を有する前記アクティブ不等式制約を削除し、前記第１レベルの反復を繰り返し、そうでないときは、
前記制御解は実行可能でなく、前記コントローラは、前記制御入力の現在のシーケンスを、前記制御解の実行可能な部分を用いて更新し、前記アクティブ不等式制約セットにおいてブロッキング不等式制約を追加し、前記第１レベルの反復を繰り返す、請求項２に記載の予測コントローラ。
【請求項６】
前記コントローラは、前記ブロッキング不等式制約の追加に応答して、前記ブロッキング不等式制約の係数の第１の関数を有する行を前記制約ヤコビ行列において追加し、前記ブロッキング不等式制約の前記係数の第２の関数を用いて前記前処理行列を更新する、請求項５に記載の予測コントローラ。
【請求項７】
前記コントローラは、前記アクティブ不等式制約の削除に応答して、前記削除されたアクティブ不等式制約に対応する行を前記制約ヤコビ行列において削除し、前記第２の関数の逆関数を用いて前記前処理行列を更新する、請求項６に記載の予測コントローラ。
【請求項８】
前記前処理行列はブロック三重対角構造を有し、各ブロックは正定であり、前記コントローラは、前記ブロック三重対角構造を維持しながら前記前処理行列の因数分解を更新する、請求項１に記載の予測コントローラ。
【請求項９】
前記コントローラは、ブロック三重対角コレスキー因数分解の低ランク更新を用いて前記前処理行列の前記因数分解を更新する、請求項８に記載の予測コントローラ。
【請求項１０】
現在の制御ステップについて、前記コントローラは、以前の制御ステップ中に求められたヤコビ行列の値と因数分解された前処理行列の値とを用いて、前記ヤコビ行列と前記前処理行列の前記因数分解とを初期化する、請求項１に記載の予測コントローラ。
【請求項１１】
前記前処理行列は拡張ラグランジアンブロック対角行列であり、前記第２レベルの反復は、最小残差法を用いて前記行列方程式を解く、請求項１に記載の予測コントローラ。
【請求項１２】
前記前処理行列はシューア補行列ブロック対角行列であり、前記第２レベルの反復は、最小残差法を用いて前記行列方程式を解く、請求項１に記載の予測コントローラ。
【請求項１３】
前記コントローラは、前記行列方程式の行列のヘッシアンを正則化して、前記行列の前記ヘッシアンの正定値近似を生成し、前記コントローラは、前記行列の前記ヘッシアンの前記正定値近似に基づいて前記シューア補行列ブロック対角行列の要素を求める、請求項１２に記載の予測コントローラ。
【請求項１４】
前記前処理行列は制約プレコンディショナであり、前記第２レベルの反復は、射影共役勾配法を用いて前記行列方程式を解く、請求項１に記載の予測コントローラ。
【請求項１５】
前記コントローラは、前記行列方程式の行列のヘッシアンを正則化して、前記行列の前記ヘッシアンの正定値近似を生成し、前記コントローラは、前記行列の前記ヘッシアンの前記正定値近似に基づいて前記制約プレコンディショナの要素を求める、請求項１４に記載の予測コントローラ。
【請求項１６】
前記システムは車両であり、前記コントローラは、前記制御解に基づいて前記車両への入力を求め、前記車両への前記入力は、前記車両の加速度、前記車両のモーターのトルク、及びステアリング角度の１つ又は組み合わせを含む、請求項１に記載の予測コントローラ。
【請求項１７】
請求項１に記載の予測コントローラを備える車両。
【請求項１８】
システムの状態変数及び制御変数に対する等式制約及び不等式制約を含む制約を条件として前記システムを制御する方法であって、前記方法は、前記方法を実施する記憶された命令と結合されたプロセッサを用い、前記命令は、前記プロセッサによって実行されると、前記方法のステップを実行し、前記ステップは、
前記システムの出力の測定値を用いて前記システムの現在の状態を推定することと、
各制御ステップにおいて、必要な最適性条件の行列方程式を解いて制御解を生成することと、
前記制御解を用いて前記システムを制御し、前記システムの状態を変更することと、
を含み、
前記行列方程式は、前記システムの前記等式制約の制約ヤコビ行列を有するブロック構造化行列を含み、コントローラは、第１レベルの反復と、前記第１レベルの反復のうちの或る反復内で実行される第２レベルの反復とを含む２つのレベルの反復を用いて前記制御解を反復して求め、
第１の終了条件が満たされるまで実行される前記第１レベルの反復は、
制御ホライズン内の各時点のアクティブ不等式制約を選択し、
アクティブ不等式制約セットの変更のための低ランク更新を用いて前記制約ヤコビ行列を更新して、前記等式制約及び前記アクティブ不等式制約を含め、
前記制約ヤコビ行列の前記低ランク更新に応答して、低ランク因数分解更新を用いて前処理行列を更新し、
第２の終了条件が満たされるまで実行される前記第２レベルの反復は、前記前処理行列の前記因数分解更新を用いて、前記更新された制約ヤコビ行列を有する前記行列方程式を解いて、前記制御解を生成する、方法。
【請求項１９】
前記前処理行列はブロック三重対角構造を有し、各ブロックは正定であり、前記方法は、前記ブロック三重対角構造を維持しながら前記前処理行列の前記因数分解を更新する、請求項１８に記載の方法。
【請求項２０】
前記コントローラは、ブロック三重対角コレスキー因数分解の低ランク更新を用いて前記前処理行列の前記因数分解を更新する、請求項１９に記載の方法。
【請求項２１】
前記システムは車両であり、前記コントローラは、前記制御解に基づいて前記車両への入力を求め、前記車両への前記入力は、前記車両の加速度、前記車両のモーターのトルク、及びステアリング角度の１つ又は組み合わせを含む、請求項１８に記載の方法。
【請求項２２】
方法を実行するプロセッサによって実行可能なプログラムが具現化される非一時的コンピュータ可読記憶媒体であって、前記方法は、
システムの出力の測定値を用いて前記システムの現在の状態を推定することと、
各制御ステップにおいて、必要な最適性条件の行列方程式を解いて制御解を生成することと、
前記制御解を用いて前記システムを制御し、前記システムの状態を変更することと、
を含み、
前記行列方程式は、前記システムの等式制約の制約ヤコビ行列を有するブロック構造化行列を含み、コントローラは、第１レベルの反復と、前記第１レベルの反復のうちの或る反復内で実行される第２レベルの反復とを含む２つのレベルの反復を用いて前記制御解を反復して求め、
第１の終了条件が満たされるまで実行される前記第１レベルの反復は、
制御ホライズン内の各時点のアクティブ不等式制約を選択し、
アクティブ不等式制約セットの変更のための低ランク更新を用いて前記制約ヤコビ行列を更新して、前記等式制約及び前記アクティブ不等式制約を含め、
前記制約ヤコビ行列の前記低ランク更新に応答して、低ランク因数分解更新を用いて前処理行列を更新し、
第２の終了条件が満たされるまで実行される前記第２レベルの反復は、前記前処理行列の更新された因数分解を用いて、前記更新された制約ヤコビ行列を有する前記行列方程式を解いて、前記制御解を生成する、非一時的コンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、予測制御に関し、より詳細には、不等式制約の存在下における動的システムの前処理付き（preconditioned）予測制御のための方法及び装置に関する。
【背景技術】
【０００２】
モデル予測制御（ＭＰＣ：model predictive control）等の予測コントローラは、複雑な動的システムを制御する多くのアプリケーションにおいて用いられる。そのようなシステムの例としては、生産ライン、車両、衛星、エンジン、ロボット、発電機及び他の数値制御機械がある。
【０００３】
動的最適化ベースの予測制御及び推定は、コントローラ及び推定器の設計プロセスを大幅に加速させることができる。加えて、動的最適化は、制御目標又は推定目標だけでなく、システムダイナミクスと、システムの状態及び制御に関係した制約又は制限とを直接考慮することを可能にする。予測制御又は推定のリアルタイムアプリケーションの場合、厳密なタイミング制約の下で、多くの場合に計算リソースが限られた組み込みハードウェア上で最適制御問題を解く必要がある。
【０００４】
リアルタイム最適制御への適用に成功しているほとんどの組み込み型最適化方法は、直接的な線形代数ルーチンに依拠している。これについては、例えば、特許文献１を参照されたい。しかしながら、最適化問題のブロック構造化スパース性（block-structured sparsity）を２次最適化方法に明示的に考慮したとき、それらの直接的な解法手順の計算複雑度はＯ（Ｎｍ３）である。これは、計算コストが、ホライズン長Ｎに線形に比例して増減し、システムの状態及び制御の数、すなわちｍの３乗に比例して増減することを意味する。後者の３乗の複雑度は、最適な制御及び推定の幾つかのリアルタイムアプリケーションには望ましくない。これに対して、システムの離散時間ダイナミクスに基づいて最適化問題から状態変数を除去した後、１次最適化方法を代わりに用いることによって、計算複雑度はＯ（Ｎ２ｍ２）になる。計算コストは、システムの状態及び制御の数、すなわちｍの２乗に比例して増減するが、ホライズン長Ｎの２乗にも比例して増減する。後者の２乗の複雑度は、最適な制御及び推定の幾つかのリアルタイムアプリケーションには望ましくない。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】米国特許出願公開第２００４／０１０７０１２号
【発明の概要】
【発明が解決しようとする課題】
【０００６】
幾つかの実施の形態は、動的最適化問題を解く反復法が、２次最適化に現れる鞍点線形システムを解くときに、より良好な漸近的計算複雑度をもたらすことができるという認識に基づいている。加えて、反復ソルバーは、例えば、高速組み込み型アプリケーションの加算演算及び乗算演算の比率がより高いことに起因して、高速組み込み型アプリケーションにＦＰＧＡを用いた線形システム解法のハードウェア高速化に適している。反復法の使用は、計算時間と解の数値精度との間のトレードオフを行うことも可能にする。しかしながら、反復ソルバーは、前処理がない場合に収束が不十分になる傾向があり、プレコンディショナの生成を効率的にする必要がある。したがって、動的システムのリアルタイム最適制御に適した反復前処理付きソルバーが必要とされている。
【０００７】
そのために、幾つかの実施の形態の目的は、前処理付き反復法を用いて不等式制約付き動的最適化問題を解くことによってシステムを制御するシステム及び方法を提供することである。幾つかの実施の形態の目的は、動的システムにおける区間の数に線形に比例するとともに状態変数及び制御変数の数の２乗に比例して増減する計算コストを有する反復前処理付きソルバーを提供することである。したがって、制御問題の次元に基づく計算複雑度及びメモリ所要量の増減は、Ｎを制御ホライズン長として、ｍを状態及び制御の数とすると、Ｏ（Ｎｍ２）である。１つの実施の形態の別の目的は、最適化問題を解くための反復回数及び対応する計算時間について決定論的挙動を有するソルバーを提供することである。
【０００８】
幾つかの実施の形態の別の目的は、リアルタイム最適制御を行うために組み込みハードウェア上で実施するのに適したソルバーを提供することである。１つの実施の形態の別の目的は、不要なライブラリー依存性を有しない自己完結型ソルバーコードを必要とする組み込み型制御アプリケーションに適したソルバーを提供することである。１つの実施の形態の別の目的は、計算リソースが限られた組み込み型制御ハードウェア上で許容可能なリアルタイム数値性能を有するソルバーを提供することである。
【課題を解決するための手段】
【０００９】
幾つかの実施の形態は、最適性の必要な条件を構成する最適制御問題のカルーシュ・クーン・タッカー（ＫＫＴ：Karush-Kuhn-Tucker）方程式を直接解く２次最適化に基づいている。より具体的には、２次最適化では、変化する行列Ｋ及び右辺ベクトルｂを有する行列方程式Ｋｚ＝ｂを繰り返し解くことが必要である。これには、反復ソルバーを用いることができる。制御の時間ステップごとに、予測コントローラは、不等式制約付き最適化問題の最適解から、制御動作を生成してシステムを制御する。最適制御問題を解くときの行列Ｋにおける特定のブロックスパース性（block sparsity）構造に起因して、最適な計算複雑度を得るには、反復線形ソルバーの目的に合った構造を利用したプレコンディショナが必要とされる。これは、組み込み型制御ハードウェアの限られた計算リソースを用いるリアルタイム制御アプリケーションに特に有用である。
【００１０】
幾つかの実施の形態は、線形システムの係数行列Ｋを近似する前処理行列（preconditioning matrix）Ｐを用いると、反復ソルバーの収束を改善することができるという理解に基づいている。より具体的には、前処理付き行列Ｐ−１Ｋの固有値は、反復ソルバーの収束を改善するために、元の行列Ｋの固有値よりも密集することになる。幾つかの実施の形態は、プレコンディショナを用いない場合には、最適制御のほとんどの実際的なアプリケーションに反復ソルバーを用いることができないという理解に基づいている。そのため、幾つかの実施の形態は、スパース行列Ｋにおけるブロック構造と同様の特定のブロックスパース性構造を有する行列Ｐを形成することができるという理解に基づいている。ブロック構造化行列Ｐは、形成、更新及び因数分解するコストが密行列よりもはるかに少ない。そのため、ブロック構造化前処理行列Ｐは、最適制御アルゴリズム内で反復ソルバーを用いるのに有利である。
【００１１】
具体的には、幾つかの実施の形態は、システムを制御する計算複雑度が、システムの状態及び制御入力に対する不等式制約に起因しているという理解に基づいている。等式制約と対照的に、最適化アルゴリズムは、不等式制約のうちのいずれが最適制御解においてアクティブであるのかを特定する必要があり、これは、一般に組み合わせ問題である。幾つかの実施の形態は、リアルタイム最適制御アプリケーションの場合に、以前のサンプリング時点における最適制御問題の解に基づいて調整された初期化を用いることによって、解く際に最適なアクティブ制約セットを効率的に特定することができるという理解に基づいている。
【００１２】
幾つかの実施の形態は、計算需要が、前処理行列Ｐを構築することだけにあるのではなく、ほとんどが、最適なアクティブセットの現在の推測（guess）に対して制約を追加又は削除する２次最適化内で行列Ｐを更新することにあるという認識に基づいている。そのような行列更新が利用するリソースは、前処理行列の初期計算及び因数分解よりも少ない。これらの理解を有することによって、幾つかの実施の形態では、最適なアクティブセットの現在の推測を更新するときに、したがって、行列Ｋ及び前処理行列Ｐを更新するときに、動的最適化問題の反復解法の複雑度を低減するようにこの解法を変更する。
【００１３】
幾つかの実施の形態は、不等式制約が、被制御システムの状態又は制御が制御ホライズンの特定の点における不等式制約の境界に近づいているときにのみアクティブであり、それ以外は非アクティブであるという認識に基づいている。制御の時間ステップが異なり、及び／又は、最適化の反復が異なれば、アクティブ不等式制約又は非アクティブ不等式制約も異なる可能性がある。幾つかの実施の形態は、非アクティブ不等式制約を無視することができ、アクティブ不等式制約を、等式制約のみを条件とする動的最適化問題を構成する等式制約に置き換えることができるという認識に基づいている。この等式制約付き最適化問題を代わりに解くことによって、アクティブ制約セットの現在の推測が最適であるときに、元の最適制御解を復元することができる。現在のアクティブセットが最適でない場合には、等式制約付き解は、最適なアクティブセットを反復して見つけ、したがって、元の不等式制約付き最適化問題の正確な解を見つけるために、現在の推測に対して追加及び／又は削除すべき制約を特定する探索方向を提供する。
【００１４】
アクティブ不等式制約を等式制約に置き換えることによって、ＫＫＴ方程式が鞍点線形システムに対応する等式制約付き最適化問題が得られる。この行列方程式の行列Ｋは、本明細書ではＫＫＴ行列と呼ばれるブロック構造化ＫＫＴ行列である。このＫＫＴ行列は、ブロック対角ヘッセ行列及びブロック構造化ヤコビ行列を含む。幾つかの実施の形態は、現在のアクティブセットに対する変更がヤコビ行列の低ランク更新をもたらすという理解に基づいている。より具体的には、アクティブセットにおいて１つの制約のみを追加又は削除すると、行列Ｋ内のヤコビ行列及び対応する前処理行列Ｐのランク１更新を計算することができる。因数分解されたプレコンディショナのそのような低ランク更新に必要とされる計算リソースは、新たな行列因数分解の計算に必要とされるものよりも少ない。最適制御問題におけるブロックスパース性構造化行列の特定の場合に、これらの低ランク因数分解更新技法は最適な計算複雑度をもたらす。
【００１５】
通常、プレコンディショナを用いてＫＫＴシステムを解くには、行列方程式を反復して解くごとに新たなプレコンディショナが必要とされる。これは、プレコンディショナが、行列方程式におけるＫＫＴ行列の関数であり、ＫＫＴ行列の変更とともに、新たなプレコンディショナが用いられるべきであるからである。
【００１６】
幾つかの実施の形態は、ＫＫＴ最適性方程式が、アクティブセット手法を用いて解かれるとき、ＫＫＴ行列の制約ヤコビ行列のみが、反復して解くごとに変更されるという理解に基づいている。その上、制約ヤコビ行列のそのような更新はランク１を有する。
【００１７】
幾つかの実施の形態は、プレコンディショナがＫＫＴ行列全体の関数であるにもかかわらず、制約ヤコビ行列のみが低ランク更新を用いて更新されたとき、制約ヤコビ行列のこの低ランク更新が、プレコンディショナ全体の低ランク更新をもたらすという理解に基づいている。そのようにして、行列方程式を反復して解くごとにプレコンディショナを再計算する複雑度が、以前に求められたプレコンディショナの低ランク更新に低減される。
【００１８】
幾つかの実施の形態は、制約ヤコビ行列が多段ブロックスパース性構造を有するので、ＫＫＴシステムを解くためのプレコンディショナがブロック三重対角スパース性構造を有することができるという理解に基づいている。プレコンディショナは、制約ヤコビ行列の関数である。制約ヤコビ行列が更新されるたびに、幾つかの実施の形態は、ブロック三重対角スパース性構造を維持しながらプレコンディショナを更新する。
【００１９】
幾つかの実施の形態は、制約ヤコビ行列が、アクティブ不等式制約セットの変更に起因して頻繁に更新されるという認識に基づいている。それらの更新は、１つの制約のみがアクティブセットに対して追加又は削除されるときはランク１更新である。制約ヤコビ行列のランク１更新は、プレコンディショナのランク１更新を与える。プレコンディショナのそのような低ランク更新は、行列方程式を解くのに必要とされるプレコンディショナの行列因数分解に起因して、依然として計算コストが高い可能性がある。
【００２０】
しかしながら、そのブロック三重対角スパース性構造に起因して、プレコンディショナの行列因数分解は、ブロック三重対角コレスキー（Cholesky）因数分解を用いて計算効率が良い方法で計算することができる。低ランク更新をそのような効率的な行列因数分解と組み合わせることによって、ブロック三重対角スパース性構造を維持することができる計算的に最適な因数分解更新が得られる。
【００２１】
幾つかの実施の形態は、プレコンディショナの逆行列を効率的に適用するために、前処理行列のブロック三重対角コレスキー因数分解を反復して用いて、アクティブセットベース最適化アルゴリズムの各反復内で行列方程式を解く。この実施の形態では、前処理行列はブロック三重対角構造を有し、各ブロックは、ブロック構造化コレスキー因数分解を用いることができるように正定である。
【００２２】
この実施の形態は、アクティブ不等式制約セットの変更に応答してヤコビ行列及び前処理行列を更新する。そのような方法では、ヤコビ行列及び前処理行列の更新は低ランク因数分解更新である。しかしながら、この更新手順中、１つの実施の形態は、それらの行列のブロックスパース性構造を維持する。加えて、プレコンディショナの逆行列を適用する後退代入は、そのブロック構造化コレスキー因数に基づいて複雑度Ｏ（Ｎｍ２）の計算コストを要する。そのようにして、リアルタイム最適制御のためのアクティブセットベース最適化アルゴリズム内のこの反復前処理付きソルバーの全体的な計算複雑度はＯ（Ｎｍ２）である。これによって、この実施の形態におけるソルバーの計算コストは、制御区間の数Ｎに線形に比例して増減し、また、システムにおける状態変数及び制御変数の数ｍの２乗に比例して増減することになる。
【００２３】
幾つかの実施の形態は、ソルバーの反復性が、前処理行列におけるヤコビ行列及び／又はプレコンディショナのブロック三重対角コレスキー因数分解を、閉ループ制御方式において以前の時間ステップ中に求められたそれらの行列の値に基づいてウォームスタートさせることを可能にするという認識に基づいている。それらの実施の形態は、それらの行列及び因数分解を初期化するのに必要とされる計算リソースを更に削減することができる。加えて、幾つかの実施の形態は、アクティブセットベース最適化アルゴリズムの早期の終了が、被制御システムの全ての制約及び制限を満たす準最適制御解を与えるという理解に基づいている。これは、制約の全てを考慮しながら最適又は準最適な制御入力をシステムに適用することができるリアルタイム制御アプリケーションの決定論的な計算遅延をもたらす。
【００２４】
したがって、１つの実施の形態は、システムの状態変数及び制御変数に対する等式制約及び不等式制約を含む制約を条件としてシステムを制御する予測コントローラを開示する。予測コントローラは、
システムの出力の測定値を用いてシステムの現在の状態を推定する推定器と、
各制御ステップにおいて、必要な最適性条件の行列方程式を解いて制御解を生成し、この制御解を用いてシステムを制御し、システムの状態を変更するコントローラであって、行列方程式は、システムの等式制約の制約ヤコビ行列を有するブロック構造化行列を含み、コントローラは、第１レベルの反復と、この第１レベルの反復のうちの或る反復内で実行される第２レベルの反復とを含む２つのレベルの反復を用いて制御解を反復して求める、コントローラと、
を備え、
第１の終了条件が満たされるまで実行される第１レベルの反復は、
制御ホライズン内の各時点のアクティブ不等式制約を選択し、
アクティブ不等式制約セットの単一の変更のための低ランク更新を用いて制約ヤコビ行列を更新して、等式制約及びアクティブ不等式制約を含め、
制約ヤコビ行列の低ランク更新に応答して、低ランク因数分解更新を用いて前処理行列を更新し、
第２の終了条件が満たされるまで実行される第２レベルの反復は、更新された前処理行列を用いて、更新された制約ヤコビ行列を有する行列方程式を解いて、制御解を生成する。
【００２５】
別の実施の形態は、システムの状態変数及び制御変数に対する等式制約及び不等式制約を含む制約を条件としてシステムを制御する方法であって、この方法は、この方法を実施する記憶された命令と結合されたプロセッサを用い、命令は、プロセッサによって実行されると、方法のステップを実行し、ステップは、
システムの出力の測定値を用いてシステムの現在の状態を推定することと、
各制御ステップにおいて、必要な最適性条件の行列方程式を解いて制御解を生成することと、
制御解を用いてシステムを制御し、システムの状態を変更することと、
を含み、
行列方程式は、システムの等式制約の制約ヤコビ行列を有するブロック構造化行列を含み、コントローラは、第１レベルの反復と、この第１レベルの反復のうちの或る反復内で実行される第２レベルの反復とを含む２つのレベルの反復を用いて制御解を反復して求め、
第１の終了条件が満たされるまで実行される第１レベルの反復は、
制御ホライズン内の各時点のアクティブ不等式制約を選択し、
アクティブ不等式制約セットの単一の変更のための低ランク更新を用いて制約ヤコビ行列を更新して、等式制約及びアクティブ不等式制約を含め、
制約ヤコビ行列の低ランク更新に応答して、低ランク因数分解更新を用いて前処理行列を更新し、
第２の終了条件が満たされるまで実行される第２レベルの反復は、前処理行列の更新された因数分解を用いて、更新された制約ヤコビ行列を有する行列方程式を解いて、制御解を生成する、方法を開示する。
【００２６】
更に別の実施の形態は、方法を実行するプロセッサによって実行可能なプログラムが具現化される非一時的コンピュータ可読記憶媒体であって、方法は、
システムの出力の測定値を用いてシステムの現在の状態を推定することと、
各制御ステップにおいて、必要な最適性条件の行列方程式を解いて制御解を生成することと、
制御解を用いてシステムを制御し、システムの状態を変更することと、
を含み、
行列方程式は、システムの等式制約の制約ヤコビ行列を有するブロック構造化行列を含み、コントローラは、第１レベルの反復と、第１レベルの反復のうちの或る反復内で実行される第２レベルの反復とを含む２つのレベルの反復を用いて制御解を反復して求め、
第１の終了条件が満たされるまで実行される第１レベルの反復は、
制御ホライズン内の各時点のアクティブ不等式制約を選択し、
アクティブ不等式制約セットの単一の変更のための低ランク更新を用いて制約ヤコビ行列を更新して、等式制約及びアクティブ不等式制約を含め、
制約ヤコビ行列の低ランク更新に応答して、低ランク因数分解更新を用いて前処理行列を更新し、
第２の終了条件が満たされるまで実行される第２レベルの反復は、前処理行列の更新された因数分解を用いて、更新された制約ヤコビ行列を有する行列方程式を解いて、制御解を生成する、非一時的コンピュータ可読記憶媒体を開示する。
【図面の簡単な説明】
【００２７】
【図１】幾つかの実施形態によるコントローラ及びフィードバックシステムのブロック図である。
【図２】本発明の幾つかの実施形態による、ＣＰＵプロセッサ及びメモリを用いて実施されるコントローラ、並びに、フィードバックシステムのブロック図である。
【図３Ａ】幾つかの実施形態による、コントローラを実現するモデル予測制御（ＭＰＣ）方法のブロック図である。
【図３Ｂ】幾つかの実施形態による、最適制御構造化２次計画問題（ＱＰ：Quadratic Program）を解くＭＰＣ方法のブロック図である。
【図３Ｃ】幾つかの実施形態による２層コントローラの概略図である。
【図４Ａ】幾つかの実施形態によるＭＰＣコントローラを実現するアクティブセット最適化のブロック図である。
【図４Ｂ】１つの実施形態によるＭＰＣコントローラを実現するアクティブセット最適化の擬似コードである。
【図５Ａ】幾つかの実施形態によるアクティブセットベースＭＰＣコントローラの初期化手順のブロック図である。
【図５Ｂ】幾つかの実施形態によるアクティブセットベースＭＰＣコントローラのスラック変数を用いた初期化手順のブロック図である。
【図６Ａ】幾つかの実施形態によるアクティブセットベースＭＰＣコントローラ内の前処理付き反復ソルバーのブロック図である。
【図６Ｂ】幾つかの実施形態によるアクティブセットベースＭＰＣコントローラ内のプレコンディショナのランク１更新のブロック図である。
【図７Ａ】幾つかの実施形態による、ＭＰＣコントローラにおける各アクティブセット変更後に解かれるＫＫＴ最適性条件の線形システムのブロック図である。
【図７Ｂ】幾つかの実施形態による、ＭＰＣコントローラにおける各アクティブセット変更後に解かれるＫＫＴ線形システムにおけるブロック構造化係数行列の概略図である。
【図８】幾つかの実施形態による、アクティブセット最適化の各反復において線形ＫＫＴシステムを解くのに用いられる前処理付き反復ソルバーのブロック図である。
【図９Ａ】幾つかの実施形態による、コレスキー因数分解を用いた、反復ソルバー内における正定値前処理行列の適用を示すブロック図である。
【図９Ｂ】幾つかの実施形態による、ブロック三重対角コレスキー因数分解を用いた、正定値前処理行列の適用を示すブロック図である。
【図１０Ａ】幾つかの実施形態による、拡張ラグランジアンタイプブロック三重対角前処理行列を反復法と組み合わせて用いて各線形ＫＫＴシステムを解く、ＭＰＣのアクティブセット最適化のブロック図である。
【図１０Ｂ】幾つかの実施形態による、アクティブセットベースＭＰＣコントローラ内で用いられる拡張ラグランジアンタイプブロック三重対角前処理行列の概略図である。
【図１１Ａ】幾つかの実施形態による、シューア（Schur）補行列タイプブロック三重対角前処理行列を反復法と組み合わせて用いて各線形ＫＫＴシステムを解く、ＭＰＣのアクティブセット最適化のブロック図である。
【図１１Ｂ】幾つかの実施形態による、アクティブセットベースＭＰＣコントローラ内で用いられるシューア補行列タイプブロック三重対角前処理行列の概略図である。
【図１２Ａ】幾つかの実施形態による、制約プレコンディショナを射影前処理付き共役勾配法と組み合わせて用いて各線形ＫＫＴシステムを解く、ＭＰＣのアクティブセット最適化のブロック図である。
【図１２Ｂ】幾つかの実施形態による、ＭＰＣの射影前処理付き共役勾配法内で制約プレコンディショナを適用する概略図である。
【図１３】幾つかの実施形態の原理を用いるコントローラを備える車両の概略図である。
【図１４】幾つかの実施形態の原理を用いるコントローラと幾つかの実施形態による車両１３０１のコントローラとの間の相互作用の概略図である。
【発明を実施するための形態】
【００２８】
本発明の幾つかの実施形態は、システムの動作を制御するシステム及び方法、又は、予測コントローラを用いるシステムを提供する。予測コントローラの一例は、被制御システムのモデルに基づいて制御入力を求めるモデル予測制御（ＭＰＣ）である。
【００２９】
図１は、状態推定器１３０を介して予測コントローラ１１０に接続された一例示のシステム１２０を示している。幾つかの実施態様では、この予測コントローラは、システムの動的モデル１０２に従ってプログラミングされたＭＰＣコントローラである。このモデルは、システム１２０の状態及び出力１０３の経時的な変化を、現在及び以前の入力１１１並びに以前の出力１０３の関数として表す一組の方程式とすることができる。このモデルは、システムの物理的な制限及び動作上の制限を表す制約１０４を含むことができる。動作中、コントローラは、システムの所望の挙動を示すコマンド１０１を受信する。このコマンドは、例えば、動作コマンドとすることができる。コマンド１０１の受信に応答して、コントローラは、システムの入力として機能する制御信号１１１を生成する。この入力に応答して、システムは、当該システムの出力１０３を更新する。システムの出力１０３の測定値に基づいて、推定器は、システムの推定状態１２１を更新する。システムのこの推定状態１２１は、状態フィードバックをコントローラ１１０に与える。
【００３０】
システム１２０は、本明細書において、幾つかの特定の操作入力信号１１１（入力）によって制御されるとともに、幾つかの制御された出力信号１０３（出力）を返す任意の機械又はデバイスとすることができる。上記入力は、電圧、圧力、力、トルク等の物理量に関連していることがあり、上記出力は、以前の状態から現在の状態へのシステムの状態の遷移を示す電流、流量、速度、位置等の物理量に関連していることがある。出力値は、一部はシステムの以前の出力値に関係し、一部は以前の入力値及び現在の入力値に関係している。以前の入力及び以前の出力に対する依存関係は、システムの状態内に符号化される。システムの動作、例えば、システムの構成要素の動きは、幾つかの特定の入力値の印加に従ってシステムによって生成される出力値のシーケンスを含むことができる。
【００３１】
システムのモデル１０２は、システム出力が経時的にどのように変化するのかを、現在及び以前の入力と、以前の出力との関数として記述する一組の数学方程式を含むことができる。システムの状態は、システムのモデル及び今後の入力とともに、システムの今後の動きを一意に規定することができる、一般的には時間変化する任意の情報セット、例えば、現在及び以前の入力及び出力の適切なサブセットである。
【００３２】
システムは、出力、入力、及び場合によってはシステムの状態が作用することができる範囲を制限する物理制限及び仕様制約１０４を条件とすることができる。
【００３３】
コントローラ１１０は、ハードウェアで実施することもできるし、プロセッサ、例えば、マイクロプロセッサにおいて実行されるソフトウェアプログラムとして実施することもでき、一定又は可変の制御周期サンプリング間隔で、システムの推定状態１２１及び所望の動作コマンド１０１を受信し、この情報を用いて、システムを動作させるための入力、例えば、制御信号１１１を決定する。
【００３４】
推定器１３０は、ハードウェアで実施することもできるし、プロセッサ、すなわち、コントローラ１１０と同じ又は異なるプロセッサにおいて実行されるソフトウェアプログラムとして実施することもでき、一定又は可変の制御周期サンプリング間隔で、システムの出力１０３を受信し、この新たな出力測定値及び以前の出力測定値を用いて、システム１２０の推定状態１２１を求める。
【００３５】
図２は、システムの推定状態１２１及び出力１０３がコマンド１０１に従うようにシステムを作動させる、本発明の幾つかの実施形態によるコントローラ１１０のブロック図を示している。コントローラ１１０は、例えば、モデル１０２とシステムの動作に対する制約１０４とを記憶するメモリ２０２に接続された単一の中央処理装置（ＣＰＵ）プロセッサ又は複数のＣＰＵプロセッサ２０１の形態のコンピュータを含む。
【００３６】
図３Ａは、幾つかの実施形態による、システムの現在の状態１２１及び制御コマンド１０１が与えられると制御信号１１１を計算するコントローラ１１０を実現するモデル予測制御（ＭＰＣ）のためのシステム及び方法のブロック図を示している。具体的には、ＭＰＣは、各制御時間ステップにおいて不等式制約付き最適化問題を解く（３５０）ことによって、システムの予測時間ホライズン（time horizon：計画対象期間）にわたって今後の最適制御入力のシーケンスを含む制御解、例えば、解ベクトル３５５を計算する（３６０）。この最適化問題３５０における目的関数、等式制約及び不等式制約のデータ３４５は、動的モデル、システム制約３４０、システムの現在の状態１２１及び制御コマンド１０１に依存する。
【００３７】
幾つかの実施形態では、この不等式制約付き最適化問題の求解３５０は、以前の制御時間ステップ３１０から予測時間ホライズンにわたる状態値及び制御値を用いる。これらの値は、メモリから読み出すことができる。この概念は、最適化アルゴリズムのウォームスタート又はホットスタートと呼ばれ、幾つかの実施形態では、ＭＰＣコントローラの必要とされる計算量をかなり削減することができる。同様にして、対応する解ベクトル３５５を用いて、次の制御時間ステップの最適な状態値及び制御値のシーケンスを更新及び記憶することができる（３６０）。
【００３８】
図３Ｂは、システムの現在の状態１２１及びコマンド１０１が与えられると、各制御時間ステップにおいて信号１１１を計算するために最適制御構造化最適化問題を解く（３５０）ＭＰＣコントローラのブロック図を示している。幾つかの実施形態は、線形等式制約３５２及び線形不等式制約３５４を有する線形動的モデル３５３と、線形２次目的関数３５１とに基づいており、そのため、制約付き２次計画問題（ＱＰ）３５０は、各制御時間ステップにおいて解く必要がある。具体的には、ＱＰデータ３４５は、その場合、ヘッセ行列及び制約ヤコビ行列３４６と、対応する勾配ベクトル及び制約評価ベクトル３４７とを含む。
【００３９】
幾つかの実施形態では、例えば、システムの線形時間不変（ＬＴＩ：linear time-invariant）動的モデル及び時間不変制約に基づいて、ＱＰベクトル３４７のみが制御時間ステップごとに変化することができ、ＱＰ行列３４６はその代わりに一定である。この線形時間不変の場合には、幾つかの実施形態は、各制御時間ステップにおいてＭＰＣ方法の必要とされる計算量を削減するために、一定のＱＰ行列に関係した行列因数分解の再利用に基づいて、最適化アルゴリズムのホットスタートを用いることができる。他の実施形態において、システムの動的モデル及び／又は制約及び制限の時変記述が与えられると、ＱＰベクトル３４７及びＱＰ行列３４６の双方が制御時間ステップごとに変化することができる。
【００４０】
幾つかの実施形態は、２次最適化アルゴリズムが、変化する行列Ｋ及び右辺ベクトルｂを有する行列方程式Ｋｚ＝ｂを繰り返し解くことを必要とするという認識に基づいている。しかしながら、反復ソルバーは、前処理がない場合に収束が不十分になる傾向がある。そのために、反復ごとの計算コストＯ（Ｎｍ２）を有するＰ−１Ｋｚ＝Ｐ−１ｂを解く効率的な前処理行列Ｐの設計がある。
【００４１】
一般に、前処理行列Ｐを計算することは、多くの計算量を要するタスクである可能性がある。しかしながら、幾つかの実施形態は、幾つかの状況下では、前処理行列Ｐを複数の行列更新と置き換えることができるという理解に基づいている。その上、行列の或るスパース構造を用いると、それらの複数の更新は、Ｏ（Ｎｍ２）の所望の計算コストをもたらす低ランクのものである。
【００４２】
具体的には、システム制御は、システムの状態及び制御入力に対して等式制約及び不等式制約を条件とする一方、計算複雑度は、ほとんどが不等式制約に起因していることが理解されている。時点が異なれば、異なる不等式制約がアクティブ（潜在的に違反している）又は非アクティブである可能性がある。非アクティブ不等式制約は無視することができる一方、アクティブ不等式制約は、等式制約のみを条件とする最適化問題を形成する等式制約と置き換えることができる。
【００４３】
アクティブ不等式制約を等式制約と置き換えることによって、アクティブセットの変更ごとに、行列Ｋ及び前処理行列Ｐが更新される。したがって、計算需要は、プレコンディショナＰを構築することだけにあるのではなく、ほとんどが現在のアクティブセットに対する制約の追加又は削除に応じて行列Ｐを更新することにある。加えて、アクティブ不等式制約を等式制約に置き換えることによって、ブロック対角ヘッセ行列及びブロックスパースヤコビ行列を含むＫＫＴ行列Ｋが得られる。形成、更新、及び因数分解する計算が密行列よりも少ない特定のブロックスパース性構造を有する行列Ｐも形成することができる。
【００４４】
そのようにして、現在のアクティブセットに対する変更は、ブロックスパースヤコビ行列の低ランク更新をもたらすことが理解されている。この状況において、元の行列と更新された行列との間の差のランクが行列の次元に対して相対的に小さいとき、行列の更新は低ランクであると考えられる。特殊な場合として、現在のアクティブセットに対して１つの制約のみを追加又は削除することによって、ブロックスパースヤコビ行列のランク１更新が行われることが理解されている。正確に２つの制約が、現在のアクティブセットに対して追加又は削除される場合、これによって、ブロックスパースヤコビ行列のランク２更新が行われる。プレコンディショナは、ＫＫＴ行列Ｋ全体の関数であるにもかかわらず、制約ヤコビ行列の低ランク更新は、プレコンディショナ全体の低ランク更新をもたらす。
【００４５】
そのために、幾つかの実施形態は、前処理行列Ｐのスパース性構造、例えば、ブロック三重対角構造を維持しながら、前処理付き反復ソルバーを用いたアクティブセット最適化を用いる。
【００４６】
図３Ｃは、幾つかの実施形態による２層コントローラ３７０の概略図を示している。２層コントローラ３７０は、Ｏ（Ｎｍ２）の計算コストを有する予測コントローラ１１０の原理を実施するプロセッサを備える。２層コントローラ３７０は、各制御ステップにおいて、必要な最適性条件の行列方程式を解いて制御解３８０を生成し、この制御解を用いてシステムを制御してシステムの状態を変更するように構成されている。この行列方程式は、システムの等式制約の制約ヤコビ行列を有するブロック構造化行列を含む。プロセッサは、第１レベルの反復３７５と、第１レベルの反復のうちの或る反復内で実行される第２レベルの反復３７７とを含む２つのレベルの反復を用いて制御解を反復的に求める。
【００４７】
第１レベルの反復３７５は、第１の終了条件が満たされるまで、例えば、或る収束基準及び／又は或る反復回数に達するまで実行される。第１レベルの反復の目的は、制約ヤコビ行列及び前処理行列を更新することである。例えば、第１レベルの反復は、制御ホライズン内の各時点のアクティブ不等式制約を選択し（３８５）、アクティブ不等式制約セットにおける単一の変更についてランク１更新を用いて制約ヤコビ行列を更新して等式制約及びアクティブ不等式制約を含め（３８６）、制約ヤコビ行列のランク１更新に応答して、ランク１因数分解更新を用いて前処理行列を更新する（３８７）。アクティブ不等式制約セットに対する変更が複数ある場合、制約ヤコビ行列の低ランク更新３８６は、前処理行列の低ランク因数分解更新３８７を与える。
【００４８】
第２レベルの反復は、前処理行列の更新された因数分解を用いて、更新された制約ヤコビ行列を有する行列方程式を解き、制御解３８０を生成する（３７７）。この解は、解基準の最適性及び／又は反復回数等の第２の終了条件が満たされるまで反復して見つけられる。最適である制御解３８０が見つかった場合、この解が、システムを制御するのに用いられる。そうでない場合、第１レベルの反復及び第２レベルの反復が繰り返される。
【００４９】
図４Ａは、幾つかの実施形態による、ＭＰＣコントローラ１１０の各制御時間ステップにおいて最適制御解３５５を計算するアクティブセットベース最適化方法のブロック図を示し、図４Ｂは、その擬似コードを示している。幾つかの実施形態は、主実行可能（primal feasible）アクティブセット法（active set method：有効制約法）に基づいている。この方法では、主実行可能初期開始点４０１が、最適制御解３５５の推測と、この最適制御解におけるアクティブ不等式制約セットの推測とを形成するのに用いられる。幾つかの実施形態は、以前の制御時間ステップ３１０からの状態値及び制御値を用いるとともに、ＱＰ行列及びベクトル３４５を用いて主実行可能初期開始点を計算する（４０１）。この解推測及びアクティブ不等式制約セットは、アクティブセットストラテジーが、予測時間ホライズンにわたる状態値及び制御値のシーケンスからなる制御解推測がアクティブセット法の反復ごとに主実行可能であり続けていることを保証している間、反復して更新される。
【００５０】
アクティブセット法の各反復において、この方法は、アクティブ不等式制約の現在の推測に対応する等式制約付きＱＰを解く（４０５）。等式制約付きＱＰの求解に必要とされる計算量は、不等式制約付きＱＰ３５０の元の求解よりも少ない。その結果得られた新たな制御解推測が、最適であるとともに実行可能である場合には（４０６）、元の不等式制約付きＱＰ３５０の最適解３５５が見つけられる。これに該当しないが、アクティブ不等式制約セットに対応するラグランジュ乗数のうちの１つが負である場合には（４０７）、対応する不等式制約（複数の場合もある）をアクティブセットの現在の推測から削除することができる（４１０）。最後に、新たな解推測が最適及び実行可能でないが、アクティブ不等式制約に対応する全てのラグランジュ乗数が正である場合には、新たな主実行可能解推測を計算するために、ブロッキング（blocking）不等式制約を特定することができる（４１５）。このブロッキング不等式制約（複数の場合もある）は、その後、アクティブ不等式制約セットの現在の推測に追加することができ（４２０）、最適制御解推測をそれに応じて更新することができる（４２２）。
【００５１】
幾つかの実施形態では、アクティブセット法の反復は、終了条件が満たされるまで、例えば、最適かつ実行可能な制御解が見つかる（３５５）まで又は最大反復回数に達する（４０２）まで継続する。各アクティブセット反復４０５において等式制約付きＱＰの解として得られる探索方向（Δｙ，Δλ）は、αの値にかかわらず、アクティブセットに含まれる等式制約及び不等式制約に関して主実行可能である候補ベクトルｙ＋αΔｙのファミリーを与えることに留意されたい。したがって、幾つかの実施形態は、ブロッキング不等式制約が等式制約として正確に満たされ（４２１）、他の全ての不等式制約も満たされるように、最大のブロッキング制約を、ステップ長α＞０が最も大きい不等式制約として特定する。
【００５２】
アクティブ不等式制約に対応するラグランジュ乗数のうちの少なくとも１つが負である場合に（４０７）、幾つかの実施形態は、最も大きな負のラグランジュ乗数に対応する不等式制約を現在のアクティブセットから削除する（４１０）。一方、幾つかの実施形態は、代わりに、負のラグランジュ乗数に対応する異なる制約をアクティブセットから削除することを決定することもできるし、幾つかの実施形態は、複数の制約をアクティブセットから同時に削除することを決定することもできる（４１０）。同様に、幾つかの実施形態は、１つの反復において複数の不等式制約をアクティブセットに同時に追加することができる（４２０）。そして、幾つかの実施形態は、アクティブセットに対する制約（複数の場合もある）の削除の決定（４１０）又は追加の決定（４２０）の順序を逆にする。すなわち、そのような実施形態は、アクティブ不等式制約に対応する負のラグランジュ乗数を確認する（４０７）前に、ブロック不等式制約の特定（４１５）を最初に試みる。
【００５３】
図５Ａは、アクティブセットベースＭＰＣコントローラの主実行可能初期開始点を計算する（４０１）手順のブロック図を示している。幾つかの実施形態は、以前の制御時間ステップの予測ホライズンにわたる状態値及び制御値をメモリから読み出し（３１０）、これらの値を直接用いて初期開始点を計算する（４０１）。幾つかの他の実施形態では、次の制御時間ステップにおける最適制御解のより良好な推測を形成するために、以前の状態値及び制御値がメモリから読み出され、制御入力の時点が１ステップだけシフトされる（５０１）。このシフトされた制御解推測が与えられると、現在の状態推定値１２１及び離散時間システムダイナミクスに基づいて、対応する状態値を得ることができる（５０５）。結果として得られた状態値及び制御値の組み合わせは、その後、アクティブセット最適化アルゴリズムの主実行可能開始点４０１を形成する。
【００５４】
幾つかの実施形態では、状態依存不等式制約の存在が、図５Ａからの初期化手順が主実行可能初期開始点を与えることを妨げる可能性がある。代わりに、幾つかの実施形態は、状態依存不等式制約がソフト制約に置き換えられる新たなＱＰを定式化するためにスラック変数再定式化に基づいている。幾つかの実施形態は、再定式化されたＱＰが等価となるような、すなわち、元の最適化問題が実行可能である場合に、新たなＱＰの最適制御解も元の不等式制約付きＱＰの一意の最適制御解となるようなこれらのスラック変数のＬ１ペナルティー化に基づいている。他の実施形態は、Ｌ２ペナルティー化、すなわち、これらのスラック変数の最小二乗コストに基づくことができる。図３Ｂにおける最適化問題３５０の最適制御スパース性構造を維持するために、時間区間ごとに独立に不等式制約を再定式化する少なくとも１つのスラック変数を導入する必要がある。このスラック変数（複数の場合もある）は、システムへの付加的な人工制御入力（複数の場合もある）とすることができる。
【００５５】
図５Ｂは、幾つかの実施形態による、状態依存不等式制約をソフト制約に再定式化して主実行可能性を確保するスラック変数を含む、アクティブセットベースＭＰＣコントローラの主実行可能初期開始点を計算する（４０１）手順のブロック図を示している。幾つかの実施形態は、したがって、システムの現在の状態１２１が与えられると、以前の値をメモリから読み出し（３１０）、制御入力を１つの時間ステップだけシフトし（５０１）、システムダイナミクスをシミュレーションして状態値を計算する（５０５）ことによって、開始点を計算する（４０１）。その結果の状態及び制御入力が与えられると、全てのソフト不等式制約が満たされるようにスラック変数の値を計算することができる（５１０）。幾つかの実施形態では、各時間区間のスラック変数は、その特定の時間区間において全てのソフト制約を満たすために、最も小さな（正）値に設定することができる。幾つかの他の実施形態では、状態値及び制御値の初期推測に基づいて、予測ホライズンの各時間区間内のＱＰの全ての（ソフト）不等式制約を満たす更新された一組の状態値及び制御値を計算するフェーズＩ手順ステップが用いられる。
【００５６】
図６Ａは、本発明の幾つかの実施形態による、ＭＰＣコントローラの１つの時間ステップ中にアクティブセット反復のそれぞれにおいて等式制約付きＱＰの解を計算する前処理付き反復ソルバーに基づくアクティブセット最適化アルゴリズムのブロック図を示している。アクティブ不等式制約セットの現在の推測が与えられると、新たな探索方向（Δｙ，Δλ）を計算するために、等式制約付きＱＰを解く（４０５）必要がある。最適性に必要な条件、すなわち、等式制約付きＱＰのカルーシュ・クーン・タッカー（ＫＫＴ）条件は、各反復において解く（６０１）必要がある鞍点線形システムに対応する。本発明の実施形態では、この鞍点線形ＫＫＴシステムは、前処理付き反復ソルバーを用いると効率良く解かれる（６０５）。結果として得られた新たな制御解推測は、最適制御解が見つけられる（３５５）ような実行可能かつ最適なものである（４０６）か、又は、現在のアクティブ不等式制約ワーキングセットの更新が必要とされる（６１０）。
【００５７】
図４Ａ及び図４Ｂに示すように、アクティブセットの各更新は、負のラグランジュ乗数値がある（４０７）のか又はブロッキング不等式制約がある（４１５）のかに応じて、制約が現在のアクティブセットに対して追加（４２０）又は除去（４１０）されることに対応する。幾つかの実施形態は、現在のアクティブ不等式制約ワーキングセットのこれらの更新６１０が、アクティブセット法６０１の各反復において解く必要がある線形ＫＫＴシステムにおける係数行列の低ランク更新をもたらすという理解に基づいている。前処理付き反復ソルバーを用いて各鞍点線形ＫＫＴシステムの解を計算する（６０５）とき、現在のワーキングセットのこれらの更新６１０は、前処理行列の対応する更新６１５を与える。
【００５８】
図６Ｂは、各アクティブセットの変更が、１つ又は複数の不等式制約が現在のアクティブセットに対して追加（４２０）又は除去（４１０）されることに正確に対応する前処理付き反復ソルバーに基づくアクティブセット最適化アルゴリズムのブロック図を示している。現在のアクティブセットのこの更新６１１は、追加又は除去された（６１６）制約に直接に依存する前処理行列の低ランク更新をもたらす。幾つかの実施形態では、反復ソルバー内でプレコンディショナの逆行列を効率的に適用するために、行列因数分解の低ランク更新が計算される。より具体的には、１つの制約のみが、現在のアクティブセットの更新６１１において追加又は除去される場合、これは、前処理行列及びその因数分解のランク１更新６１６を与える。
【００５９】
密ｎ×ｎ行列の場合、行列因数分解は、一般にＯ（ｎ３）の計算複雑度を有する一方、事前計算された行列因数分解のランク１更新は、Ｏ（ｎ２）の計算複雑度にしか対応しない。低ランク因数分解更新の場合も、ランクがｎ×ｎ行列の次元ｎと比較して小さい限り、計算複雑度はＯ（ｎ２）である。低ランク因数分解更新は、直接又はランク１因数分解更新のシーケンスの形で実行することができる。したがって、一般に、行列因数分解の低ランク更新は、アクティブセットの各更新後の新たな行列因数分解の計算よりも低次の計算複雑度である。
【００６０】
図７Ａは、現在のアクティブ不等式制約セットが与えられると、元の不等式制約付きＱＰ３５０を局所的に近似する等式制約付きＱＰ（ＥＱＰ：equality constrained QP）定式化７００の詳細な記載を有するブロック図を示している。ＥＱＰにおける目的関数７０１は、元の線形２次目的関数３５１と等価であることに留意されたい。同様に、ＥＱＰにおける線形等式制約７０２及び７０３も、元のＱＰ定式化における対応する制約３５２及び３５３と等価である。主な相違は、ＱＰ定式化における元の不等式制約３５４が、最適制御解におけるアクティブセットの現在の推測に基づいてアクティブ不等式制約セット７０４に置き換えられていることである。前述したように、ＥＱＰ問題７００の求解は、最適性の必要なＫＫＴ条件７０５を記述している鞍点線形システムの解を必要とする。
【００６１】
幾つかの実施形態は、解く必要がある線形システム７０７が特定の鞍点ＫＫＴ構造７０６を有するという理解に基づいている。より具体的には、（１，１）ブロックにおける行列Ｈは、ＫＫＴ行列７０８内のブロック対角ヘッセ行列に対応する。幾つかの実施形態は、ヘッセブロック行列のそれぞれが、個々に正定（半正定）である（７０８）という特性に依拠している。加えて、ＫＫＴ行列７０６内の（２，１）ブロックにおける行列Ａ及び１，２）ブロックにおけるその転置行列Ａ−Ｔは、鞍点線形ＫＫＴシステムにおけるブロック構造化制約ヤコビ行列を定義する。幾つかの実施形態は、制約ヤコビがフルランクの行列である、すなわち、行列Ａ内の行のそれぞれが線形独立である必要があるという特性に依拠している。図４において説明したような主実行可能アクティブセット法に基づく本発明の実施形態は、ヤコビ行列がアクティブセット法の各反復においてフルランクであるようにアクティブ不等式制約セットを自動的に維持する。他の実施形態では、フルランクの対応するヤコビ行列を与えるために、アクティブセットの最大の線形独立サブセットを計算する必要がある。
【００６２】
図７Ｂは、幾つかの実施形態による各アクティブセット変更後に解く必要がある鞍点線形システムにおけるＫＫＴ行列７０６のスパース性構造の概略図を示している。幾つかの実施形態では、ブロック対角ヘッセ行列は、ヘッセブロック行列のそれぞれが対角であるとき、対角ヘッセ行列７０８に簡約化され、これによって、通常、対応する鞍点線形ＫＫＴシステムを解くのに必要とされる計算量を削減することができる。加えて、このＫＫＴ行列内の制約ヤコビ行列７０９及びその転置行列７１１は、本発明の実施形態による、各鞍点線形ＫＫＴシステムの効率的な解法において利用される通常の最適制御ブロックスパース性構造を示している。
【００６３】
図８は、アクティブセットベースＭＰＣ方法の各反復において、行列方程式、すなわち、鞍点線形システムＫｚ＝ｂを解く前処理付き反復法の一例を示している。正確な係数行列Ｋ８０１は、図７Ｂに示すような最適制御構造化ブロックスパース性を有するＫＫＴ行列７０６として定義される。主な計算量は、解ｚ★が見つかる（８３５）まで、線形システムＫｚ＝ｂの解の近似を反復して（８４５）更新する（８４０）ために、係数行列Ｋを適用する（８０５）ことと、プレコンディショナの逆行列Ｐ−１を適用する（８２５）こととからなる。
【００６４】
ソルバーの各反復は、図７に示すような最適制御構造化ブロックスパース性を利用することによって効率的に実行することができる、正確な係数行列Ｋを用いた少なくとも１つの行列ベクトル乗算（８０５）を必要とする。図７Ｂにおけるヘッセ行列７０８及びヤコビ行列７０９のこのブロックスパース性構造が与えられると、その結果、これらの行列ベクトル乗算の計算複雑度はＯ（Ｎｍ２）となる。ここで、Ｎは制御ホライズン長であり、ｍは状態変数及び制御変数の数である。幾つかの実施形態は、対応する計算コストを更に削減する対角ヘッセ行列に依拠している。例えば、或る特定の時間区間における状態変数又は制御変数のうちの幾つかについてアクティブである単純な境界の場合に、係数行列Ｋを適用する（８０５）実際的な計算コストを削減するために、ブロック行列内のアクティブ不等式制約のヤコビ行列のスパース性を更に利用することができる。
【００６５】
各鞍点線形システムを解く全体的な計算コストは、反復回数に比例する。停止基準８３０は、現在の近似ｚが所与の許容範囲（tolerance）を満たすか否か又は反復ステップの最大数ｋ＝ｋｍａｘに達したか否かを調べる。この停止基準が満たされる場合には、解ｚ★が見つかり（８３５）、そうでない場合には、近似ｚは更新され（８４０）、反復は継続する（８４５）。この反復法の幾つかの例は、前処理付き一般化最小残差（ＰＧＭＲＥＳ：preconditioned generalized minimal residual）法、前処理付き最小残差（ＰＭＩＮＲＥＳ：preconditioned minimal residual）法及び射影前処理付き共役勾配（ＰＰＣＧ：projected preconditioned conjugate gradient）法である。
【００６６】
幾つかの実施形態では、鞍点線形システムの解を求める反復手順を開始するのに、初期近似解ｚ０８１０が用いられる。この近似解推測は、アクティブセット法の反復ごとのアクティブセット変更を所与とする（６０１）以前の鞍点線形システムの解６０５に基づくことができる。或いは、幾つかの実施形態は、妥当な解推測が代わりにゼロ値からなるように、鞍点線形システム７０６における主変数及び双対変数の変化を計算する。
【００６７】
幾つかの実施形態は、正確な係数行列Ｋ８０１又は近似係数行列８１５のいずれかを用いて、前処理行列の少なくとも一部を求めるか又は更新する（８２０）。プレコンディショナを最初に生成し、その後、例えば、主要な反復サイクルのあらゆるステップにおいて適用することができる（８２５）。幾つかの実施形態では、プレコンディショナは、主要な反復サイクルの外部で生成される（８２０）前処理関数に関係付けられている。この前処理関数は、プレコンディショナの逆行列Ｐ−１とベクトルとの積を返すためにその特定のベクトルに適用することができる（８２５）。例えば、この反復法の幾つかの実施形態では、前処理関数は、Ｐ−１（ｂ−Ｋｚ）を計算するために残差ｂ−Ｋｚに作用する。プレコンディショナの適用によって、反復ごとの計算コストを大幅に増加させることなく、反復法の収束が高速化され、したがって、ＭＰＣコントローラの全体的な性能が改善される。
【００６８】
本発明の幾つかの実施形態では、ブロック構造化プレコンディショナが、その行列因数分解を効率的に求め、更新し（８２０）、適用する（８２５）ことができるように用いられる。したがって、ブロック構造化行列因数分解は、複雑度Ｏ（Ｎｍ３）の計算コストを要する。ここで、Ｎは制御ホライズン長であり、ｍは状態変数及び制御変数の数である。しかしながら、幾つかの実施形態では、アクティブセット法の反復ごとにプレコンディショナの行列因数分解を代わりに更新する（６１５）ことによって、各鞍点線形システムの解を得るために必要とされるこの行列因数分解の計算は回避される。１つの制約のみが各反復においてアクティブセットに対して追加又は削除される場合、そのような更新は、前処理行列のブロック構造化スパース性を維持する複雑度Ｏ（Ｎｍ２）のランク１因数分解更新に対応する。同様に、このブロックスパース行列因数分解を所与としてプレコンディショナの逆行列Ｐ−１をベクトルに適用することは、複雑度Ｏ（Ｎｍ２）の計算コストを要する。
【００６９】
近似係数行列の近似逆行列が、プレコンディショナの行列形式に用いられる場合、すなわち、Ｐ−１≒Ｋ−１である場合、前処理付き反復法における反復回数は、根本的に削減される。所与の時間ステップにおけるプレコンディショナ８２０が正確な係数行列８０１の逆行列と一致する正確な場合、すなわち、Ｐ−１＝Ｋ−１である場合、前処理付き反復法における反復回数は１に削減される。しかしながら、この正確な場合は、計算コストが高くなる可能性があり、したがって、幾つかの実施形態は、前処理セットアップ又は更新８２０及び適用８２５を目的とした場合、近似係数行列８１５が、それらの正確なものと比較して、因数分解がより容易かつより高速である可能性がある一方、引き続き高品質の前処理が得られるという認識に基づいている。同様に、プレコンディショナの決定、更新８２０又は適用は、完全な精度を必要とせず、コンピュータベースのコントローラ１１０上で削減された数の算術ビットを用いて行うことができる。別の実施形態は、既に計算された近似係数行列から低精度の算術でプレコンディショナの因数分解を求めることができ、及び／又は、適用することができる。
【００７０】
図９Ａは、１つの実施形態によって用いられるプレコンディショナ行列のコレスキー行列因数分解（又は分解）９００に基づいてプレコンディショナを適用する方法のブロック図を示している。プレコンディショナセットアップ９０５は、行列因数分解Ｐ＝ＬＬＴを求める。ここで、前処理行列Ｐは正定値行列であり、行列Ｌは下三角行列である。この分解Ｐ＝ＬＬＴは、Ｐがｎ×ｎ行列である場合にｎ３／３個の浮動小数点演算（ＦＬＯＰＳ）のコスト、すなわち、Ｏ（ｎ３）の計算複雑度で新たな行列因数分解に基づいて計算することができる。代わりに、低ランク更新が前処理行列に与えられると（６１６）、この行列のコレスキー因数分解のランク１更新（複数の場合もある）を、代わりにＯ（ｎ２）の計算複雑度で実行することができる。プレコンディショナ関数の適用９１０は、以下のステップを含む。最初に、行列方程式
【数１】
0006808093.tif 000002
が、行列Ｌが下三角行列であることを用いて、前進代入によって解かれる（９１５）。次に、行列方程式
【数２】
0006808093.tif 000003
が、行列ＬＴが上三角行列であることを用いて、後退代入によって解かれる（９２０）。コレスキー因数Ｌ及びＬＴを用いた前進代入及び後退代入のいずれも、Ｏ（ｎ２）の計算複雑度で実行することができる。最後に、プレコンディショナを適用した結果は、Ｐ−１ｂ＝（ＬＬＴ）−１ｂ＝ｚとして求められる（９２５）。
【００７１】
図９Ｂは、１つの実施形態によって用いられるプレコンディショナ行列のブロック三重対角コレスキー因数分解（又は分解）９３５に基づいてブロック構造化正定値プレコンディショナを適用する（９３０）方法のブロック図を示している。プレコンディショナセットアップ９３５は、行列因数分解Ｐ＝ＬＬＴを求める。ここで、前処理行列Ｐは、正定値行列であるとともにブロック三重対角行列であり、行列Ｌは、下三角行列であるとともに下ブロック二重対角行列である。この分解は、Ｏ（Ｎｍ３）の計算複雑度で新たなブロック三重対角行列因数分解に基づいて計算することができる。ここで、Ｎはブロックの数であり、ｍは各ブロック行列の次元を表す。代わりに、低ランク更新が前処理行列に与えられると（６１６）、この行列のブロック三重対角コレスキー因数分解のランク１更新（複数の場合もある）を、代わりにＯ（Ｎｍ２）の計算複雑度で実行することができる。プレコンディショナ関数の適用９４０は、以下のステップを含む。最初に、行列方程式
【数３】
0006808093.tif 000004
が、行列Ｌが下三角行列であるとともに下ブロック二重対角行列であることを用いて、ブロック二重対角前進代入によって解かれる（９４５）。次に、行列方程式
【数４】
0006808093.tif 000005
が、行列ＬＴが上三角行列であるとともに上ブロック二重対角行列であることを用いて、ブロック二重対角後退代入によって解かれる（９５０）。コレスキー因数Ｌ及びＬＴを用いたブロック二重対角前進代入及びブロック二重対角後退代入のいずれも、Ｏ（Ｎｍ２）の計算複雑度で実行することができる。最後に、プレコンディショナを適用した結果は、Ｐ−１ｂ＝（ＬＬＴ）−１ｂ＝ｚとして求められる（９２５）。
【００７２】
ｎ×ｎ行列のコレスキー因数分解Ｐ＝ＬＬＴは、ランク１変更
【数５】
0006808093.tif 000006
の後に、Ｏ（ｎ２）の計算で復元することができる。これは、α＞０である場合には更新と呼ばれ、α＜０である場合にはダウンデート（downdate）と呼ばれる。ブロック三重対角コレスキー因数分解の場合、行列がランク１変更
【数６】
0006808093.tif 000007
の後もブロック三重対角のままである限り、コレスキー因数の特定のブロックスパース性構造を維持することができる。前述したように、計算複雑度は、ブロック三重対角コレスキー因数分解についてはＯ（Ｎｍ３）であり、ブロック三重対角行列のランク１変更に基づくランク１更新についてはＯ（Ｎｍ２）である。対称行列Ｐにおける行及び列の対の挿入又は抹消も、特定のタイプのランク１変更に対応し、コレスキー因数分解はＯ（Ｎｍ２）の同じ計算複雑度で更新することができることに留意されたい。幾つかの実施形態は、ブロック三重対角コレスキー因数分解の後方（backward）又は逆の変形形態に基づいている。この変形形態は、アクティブセット変更のほとんどが制御予測ホライズンにおいて早期の時間区間中に行われることを仮定すると、ＭＰＣコントローラの場合にランク１因数分解更新を実行するときに特定の利点を有する。
【００７３】
図１０Ａは、幾つかの実施形態による、ＭＰＣコントローラ１１０を実現するためのアクティブセット最適化のブロック図を示している。この最適化では、１０１０による拡張ラグランジアンタイプブロック三重対角前処理行列が、前処理付き一般化最小残差（ＰＧＭＲＥＳ）法又は前処理付き最小残差（ＰＭＩＮＲＥＳ）法のいずれかと組み合わせて用いられる（１００５）。前処理行列１０１１の特定の最適制御タイプブロック三重対角スパース性構造が与えられると、ブロック三重対角コレスキー因数分解を用いて、図９Ｂにおいて説明したようにこのプレコンディショナを効率的に適用することができる。幾つかの実施形態は、プレコンディショナＰａも正定値行列であり、一意のコレスキー因数分解が存在するように、正定値重み行列Γ＞０に基づいている。
【００７４】
図１０Ｂは、幾つかの実施形態による、ブロック三重対角スパース性構造１０２２を有するブロック行列Ｈ＋ＡＴΓＡ１０２０と、逆重み行列Γ−１１０２１とを含むブロック構造化対称前処理行列Ｐａ１０１１の概略図を示している。本発明の幾つかの実施形態は、対角重み行列Γ＝γＩの単純な選択に基づいている。ここで、Ｉは単位行列を表し、γ＞０は正の値である。幾つかの緩やかな条件下では、プレコンディショナＰａがγ＞０の任意の値について正定値行列であり、一意のコレスキー因数分解が存在することを示すことができる。加えて、前処理付き行列Ｐａ−１Ｋの固有値は、γ＞０の値が増加するにつれて、±１の周辺により密集するようになり、それによって、一般に、前処理付き反復法は、γの値を増加させることによって、より高速に収束することになる。したがって、γの十分に大きな値について、ＰＭＩＮＲＥＳ法は、２つの反復内（ほぼ２つの反復）で収束することができる。一方、γを過度に大きく選ぶと、前処理行列Ｐａの不良条件がもたらされる場合があり、そのため、このパラメーターは、例えば、コンピュータベースのコントローラ１１０内の利用可能な算術ビットの数に応じて、慎重に設計されるべきである。
【００７５】
不等式制約が追加又は削除されるアクティブセットの更新６１１が与えられると、ブロック三重対角スパース性構造を維持しながら前処理行列のコレスキー因数分解のランク１更新が計算される。より具体的には、拡張ラグランジアンタイププレコンディショナ１０１１の場合、制約を追加又は削除することによって、対称重み行列Γ＝γＩの対応する行及び列が追加又は削除される。なぜならば、その次元は、等式制約及びアクティブ不等式制約の総数に対応するからである。加えて、アクティブセットに対する制約の追加又は削除は、ＫＫＴ行列７０６の制約ヤコビ行列Ａにおける行の追加又は削除に対応し、これは、行列Ｈ＋ＡＴΓＡのブロック三重対角コレスキー因数分解のランク１更新又はダウンデートをもたらす。
【００７６】
Γ＝γＩである特定の実施形態について、逆行列
【数７】
0006808093.tif 000008
は既知であり、そのため、ブロック行列Ｈ＋ＡＴΓＡ１０２２のブロック三重対角コレスキー因数分解のみを計算及び更新する必要がある。この因数分解を計算又は更新する計算コストは、それぞれＯ（Ｎｍ３）又はＯ（Ｎｍ２）である。ここで、Ｎは制御ホライズン長であり、ｍは状態及び制御の数である。
【００７７】
図１１Ａは、１つの実施形態による、ＭＰＣコントローラ１１０を実現するためのアクティブセット最適化アルゴリズムのブロック図を示している。このアルゴリズムでは、１１１０によるシューア補行列タイプブロック三重対角前処理行列が、ＰＧＭＲＥＳ法又はＰＭＩＮＲＥＳ法のいずれかと組み合わせて用いられる（１００５）。前処理行列１１１１の特定の最適制御タイプブロック三重対角スパース性構造が与えられると、ブロック三重対角コレスキー因数分解を用いて、図９Ｂにおいて説明したようにこのプレコンディショナを効率的に適用することができる。幾つかの実施形態は、正定値ヘッセ近似
【数８】
0006808093.tif 000009
になるように、ヘッセ正則化手順１１２０に基づいており、そのため、プレコンディショナＰｓも正定値行列であり、一意のコレスキー因数分解が存在する。
【００７８】
図１１Ｂは、幾つかの実施形態による、ブロック対角ヘッセ近似
【数９】
0006808093.tif 000010
１１２５と、ブロック三重対角スパース性構造１１２７を有するブロック行列
【数１０】
0006808093.tif 000011
１１２６とからなるブロック構造化対称前処理行列Ｐｓ１１１１の概略図を示している。本発明の幾つかの実施形態では、ヘッセ近似は正定値行列であり、したがって、行列
【数１１】
0006808093.tif 000012
も正定値行列であり、そのため、シューア補行列タイププレコンディショナの一意のコレスキー因数分解が存在する。加えて、前処理付き行列Ｐｓ−１Ｋの固有値は、ヘッセ近似が正確なブロック対角ヘッセ行列に近づくにつれて、すなわち、
【数１２】
0006808093.tif 000013
になるにつれて、より密集するようになり、それによって、一般に、前処理付き反復法は、より高速に収束することになる。十分に近い近似
【数１３】
0006808093.tif 000014
である場合、ＰＭＩＮＲＥＳ法は、３つの反復内（ほぼ３つの反復）で収束することができる。一方、半正定値に近い
【数１４】
0006808093.tif 000015
を選ぶと、前処理行列Ｐｓの不良条件がもたらされる場合があり、そのため、ヘッセ正則化手順におけるこれらのパラメーターは、例えば、コンピュータベースのコントローラ１１０内の利用可能な算術ビットの数に応じて、慎重に設計されるべきである。
【００７９】
幾つかの実施形態では、ＭＰＣ問題定式化のヘッセ行列は対角行列１１２５であり、そのため、例えば、対角要素が個々に或る正の値ε＞０よりも大きくなるように対角要素のそれぞれを近似することによって、ヘッセ正則化
【数１５】
0006808093.tif 000016
を効率的に行うことができる。一般に、ヘッセ近似
【数１６】
0006808093.tif 000017
は、ε＞０の値が小さいほど接近し、そのため、反復ソルバーはより高速に収束するが、εは、前処理行列Ｐｓの不良条件を回避するために十分に大きなものを選ぶべきである。ＭＰＣ問題定式化のためのヘッセ行列が、密ヘッセブロックを有する一般的なブロック対角行列である他の実施形態では、ヘッセ正則化は、例えば、ヒューリスティックに実行することもできるし、ブロック行列の因数分解に基づいて実行することもできる。或いは、リカッチベースの再帰を実行して、ヘッセ行列正定値をシステムダイナミクス及び／又はアクティブ不等式制約の距離空間内にすることができる。しかしながら、そのような技法は、一般に、Ｏ（Ｎｍ３）の計算複雑度を要し、この複雑度は、ブロック三重対角コレスキー因数分解自体の複雑度と同じ複雑度である。
【００８０】
不等式制約が追加又は削除されるアクティブセットの更新６１１が与えられると、ブロック三重対角スパース性構造を維持しながら前処理行列のコレスキー因数分解のランク１更新が計算される。より具体的には、シューア補行列タイププレコンディショナ１１１１の場合、制約の追加又は削除は、ヘッセ行列にもその近似
【数１７】
0006808093.tif 000018
にも影響を及ぼさない。一方、アクティブセットに対する制約の追加又は削除は、ＫＫＴ行列７０６の制約ヤコビ行列Ａにおける行の追加又は削除に対応し、その結果、ブロック三重対角スパース性構造１１２７を有するブロック行列
【数１８】
0006808093.tif 000019
１１２６において行及び列の対が追加又は削除される。その場合、この挿入又は抹消は、行列
【数１９】
0006808093.tif 000020
のブロック三重対角コレスキー因数分解のランク１更新又はダウンデートをもたらす。行列
【数２０】
0006808093.tif 000021
のこの更新は、対角ヘッセ行列
【数２１】
0006808093.tif 000022
については容易に計算することができるが、一般的なブロック対角ヘッセ行列についても、この更新は、例えば、正定値ヘッセ近似
【数２２】
0006808093.tif 000023
におけるブロック行列のコレスキー因数分解に基づいて有効に計算することができることに留意されたい。
【００８１】
図１２Ａは、１つの実施形態のアクティブセット最適化のブロック図を示している。この実施形態では、ＭＰＣコントローラ１１０を実現するために、例えば、図７Ｂに示すようなＫＫＴ行列１２１１の構造と同じブロックスパース性構造を有する制約プレコンディショナが、射影前処理付き共役勾配（ＰＰＣＧ）法１２０５と組み合わせて用いられる（１２１０）。制約プレコンディショナを有効に適用するために、行列
【数２３】
0006808093.tif 000024
のブロック三重対角コレスキー因数分解１２１２を、各アクティブセット変更に従って計算及び更新することができる（１２１５）。シューア補行列タイプブロック対角プレコンディショナに基づく実施形態と同様に、幾つかの実施形態は、ヘッセ正則化手順１２２０を制約前処理行列と組み合わせて用い、そのため、ヘッセ近似
【数２４】
0006808093.tif 000025
のコレスキー因数分解を用いて、反復ＰＰＣＧ法内でこのプレコンディショナを有効に適用することができる。
【００８２】
正確なヘッセ行列が可逆的であり、制約プレコンディショナが近似
【数２５】
0006808093.tif 000026
に基づいている場合、その結果のＰＰＣＧの実施は、実行される反復が理論上わずか１回であるような直接的な線形システム解に対応する。しかしながら、実際には、コンピュータベースのコントローラ１１０上で用いられる算術ビットの数が限られていること、制約プレコンディショナの不正確な適用、及び／又は実際的なＭＰＣ定式化の問題データの不良条件によって、複数の共役勾配反復が依然として必要であることが多い。
【００８３】
図１２Ｂは、零空間の基底の明示的な計算を伴わずに、制約ヤコビ行列における等式制約及びアクティブ不等式制約の零空間上へのベクトルの射影を行う（１２２５）ために、１つの実施形態に従って制約プレコンディショナを適用する概略図を示している。別の反復ソルバーを用いて射影を鞍点線形システム１２２６の解として計算することができることに留意されたい。可逆的ヘッセ近似
【数２６】
0006808093.tif 000027
の場合には、幾つかの実施形態は、逆演算子
【数２７】
0006808093.tif 000028
及び
【数２８】
0006808093.tif 000029
を適用することによって、制約プレコンディショナを直接適用する（１２２７）。対角ヘッセ近似行列の場合には、逆演算子
【数２９】
0006808093.tif 000030
を自明に計算することができる。ブロック対角ヘッセ行列のより一般的な場合には、幾つかの実施形態は、ヘッセブロック行列のコレスキー因数分解に基づく。シューア補行列タイププレコンディショナと同様に、アクティブセット最適化アルゴリズムの各反復においてランク１因数分解更新１２１５を用いることができるブロック三重対角スパース性構造を有する行列
【数３０】
0006808093.tif 000031
１１２６のブロック三重対角コレスキー因数分解を計算することによって、逆演算子
【数３１】
0006808093.tif 000032
を有効に適用することができる（１１２７）。
【００８４】
ブロック三重対角コレスキー因数分解を実行するための複雑度Ｏ（Ｎｍ３）を有する相対的に高いコストは、ホットスタート手順を実行することによって、ＭＰＣコントローラのオンライン計算において回避することができることに留意されたい。幾つかの実施形態では、線形時間不変ＭＰＣ定式化に基づいて、コレスキー因数分解が、その後、制御時間ステップごとに再利用され、これは、アクティブセット法のホットスタートと呼ばれることが多い。このために、次の制御時間ステップ中に、以前の制御時間ステップにおける制御解からアクティブセット最適化アルゴリズムの初期実行可能開始点へのアクティブセット変更に基づいて因数分解を更新する必要がある。
【００８５】
図１３は、本発明の幾つかの実施形態の原理を用いる予測コントローラ１３０２を備える車両１３０１の概略図を示している。本明細書において用いられるような車両１３０１は、客車、バス、又はローバー等の任意のタイプの装輪車両とすることができる。また、車両１３０１は、自律的又は半自律的な車両とすることもできる。例えば、幾つかの実施形態は、車両１３０１の動きを制御する。動きの例として、車両１３０１のステアリングシステム１３０３によって制御される車両の横方向の動きがある。１つの実施形態では、ステアリングシステム１３０３は、コントローラ１３０２によって制御される。加えて又は代替的に、ステアリングシステム１３０３は、車両１３０１の運転手によって制御することができる。
【００８６】
車両は、コントローラ１３０２又は車両１３０１の他の構成要素によって制御することができるエンジン１３０６も備えることができる。車両は、周囲環境を検知する１つ以上のセンサ１３０４も備えることができる。センサ１３０４の例として、距離レンジファインダー、レーダー、ライダー、及びカメラがある。車両１３０１は、当該車両の現在の動きの量及び内部ステータスを検知する１つ以上のセンサ１３０５も備えることができる。センサ１３０５の例として、全地球測位システム（ＧＰＳ）、加速度計、慣性測定ユニット、ジャイロスコープ、シャフト回転センサ、トルクセンサ、たわみセンサ、圧力センサ、及び流量センサがある。これらのセンサは、情報をコントローラ１３０２に与える。車両は、有線通信チャネル又は無線通信チャネルを通じてコントローラ１３０２の通信機能を可能にする送受信機１３０６を装備することができる。
【００８７】
図１４は、幾つかの実施形態による予測コントローラ１３０２と車両１３０１のコントローラ１４００との間の相互作用の概略図を示している。例えば、幾つかの実施形態では、車両１３０１のコントローラ１４００は、車両１４００の回転及び加速を制御するステアリングコントローラ１４１０及びブレーキ／スロットルコントローラ１４２０である。そのような場合には、予測コントローラ１３０２は、制御入力をコントローラ１４１０及び１４２０に出力して車両の状態を制御する。コントローラ１４００は、予測コントローラ１３０２の制御入力を更に処理する高レベルコントローラ、例えば、車線維持支援コントローラ１４３０も備えることができる。いずれの場合も、コントローラ１４００は、車両の動きを制御するために、予測コントローラ１３０２の出力を用いて、車両のハンドル及び／又はブレーキ等の車両の少なくとも１つのアクチュエーターを制御する。
【００８８】
本発明の上記の実施形態は数多くの方法のいずれかにおいて実現することができる。例えば、それらの実施形態は、ハードウェア、ソフトウェア又はその組み合わせを用いて実現することができる。ソフトウェアにおいて実現されるとき、そのソフトウェアコードは、単一のコンピュータ内に設けられるにしても、複数のコンピュータ間に分散されるにしても、任意の適切なプロセッサ、又はプロセッサの集合体において実行することができる。そのようなプロセッサは集積回路として実現することができ、集積回路コンポーネント内に１つ以上のプロセッサが含まれる。しかしながら、プロセッサは、任意の適切な構成の回路を用いて実現することができる。
【００８９】
また、本明細書において概説される種々の方法又はプロセスは、種々のオペレーティングシステム又はプラットフォームのいずれか１つを利用する１つ以上のプロセッサ上で実行可能であるソフトウェアとしてコード化することができる。さらに、そのようなソフトウェアは、幾つかの適切なプログラミング言語及び／又はプログラミングツール若しくはスクリプト記述ツールのいずれかを用いて書くことができ、フレームワーク又は仮想機械上で実行される実行可能機械語コード又は中間コードとしてコンパイルすることもできる。通常、プログラムモジュールの機能は、種々の実施形態において望ましいように、組み合わせることもできるし、分散させることもできる。
【００９０】
また、本発明の実施形態は方法として具現することができ、その一例が提供されてきた。その方法の一部として実行される動作は、任意の適切な方法において順序化することができる。したがって、例示的な実施形態において順次の動作として示される場合であっても、例示されるのとは異なる順序において動作が実行される実施形態を構成することもでき、異なる順序は、幾つかの動作を同時に実行することを含むことができる。
【図１】
0006808093.tif 000033
【図２】
0006808093.tif 000034
【図３Ａ】
0006808093.tif 000035
【図３Ｂ】
0006808093.tif 000036
【図３Ｃ】
0006808093.tif 000037
【図４Ａ】
0006808093.tif 000038
【図４Ｂ】
0006808093.tif 000039
【図５Ａ】
0006808093.tif 000040
【図５Ｂ】
0006808093.tif 000041
【図６Ａ】
0006808093.tif 000042
【図６Ｂ】
0006808093.tif 000043
【図７Ａ】
0006808093.tif 000044
【図７Ｂ】
0006808093.tif 000045
【図８】
0006808093.tif 000046
【図９Ａ】
0006808093.tif 000047
【図９Ｂ】
0006808093.tif 000048
【図１０Ａ】
0006808093.tif 000049
【図１０Ｂ】
0006808093.tif 000050
【図１１Ａ】
0006808093.tif 000051
【図１１Ｂ】
0006808093.tif 000052
【図１２Ａ】
0006808093.tif 000053
【図１２Ｂ】
0006808093.tif 000054
【図１３】
0006808093.tif 000055
【図１４】
0006808093.tif 000056