Warm Start

• 別名: warm starting
• カテゴリ: Planning & manipulation › Trajectory optimisation
• タグ: optimization, model-predictive-control, trajectory-optimization, numerical-methods, real-time

反復ソルバーをゼロからではなく、前回の解や関連する解などの良い推定で初期化し、求解時間を短縮するとともに、有用な局所最適解へ導くこと。

定義

ウォームスタート（warm start）は、反復的な最適化ソルバーや数値ソルバーを、デフォルトの、あるいは任意の初期点からではなく、関連する問題から得た情報で初期化することである。前者はコールドスタート（cold start）と呼ばれる。その情報は、主変数（軌道のような決定変数そのもの）、双対変数またはラグランジュ乗数、不等式制約の有効制約集合、あるいは準ニュートン法の Hessian のような近似でありうる。非線形のロボティクスの問題には通常多くの局所最適解があるため、初期点はソルバーの収束の速さだけでなく、どの解が見つかるかにも影響する。

最も一般的な用途はモデル予測制御である。各制御周期で、制御装置は前回とほぼ完全に重なるホライズン上で最適化を解くため、前回の解を 1 時間ステップ前にずらし、最後のステップを延長したものは、すでに新しい最適解に近い。このようにウォームスタートすると、1 周期あたりの求解が数回の反復で済むことが多い。Diehl らのリアルタイム反復法はこれをさらに推し進め、1 周期あたり逐次二次計画法の反復を 1 回だけ行う。MPPI やクロスエントロピー法のようなサンプリングベースの制御装置は、前回の平均制御系列を再利用することでウォームスタートする。

ウォームスタートがどれだけ役立つかはソルバーによる。qpOASES のような有効制約法や、ADMM ソルバー OSQP のような一次法は、近い主・双対の推定や正しい有効制約集合があればすぐに終了できるため、大きな恩恵を受ける。内点法はウォームスタートが難しい。反復点が実行可能領域の厳密に内側にあり、制約境界から離れている必要があるが、前回の解は通常その境界上にあるからである。オフラインの軌道最適化では、ウォームスタートは、より単純なモデル、より粗い離散化、問題の緩和版、保存された解のライブラリ、あるいは良い初期推定を予測するよう学習したニューラルネットワークから得られる。物理エンジンも同様に、前のステップの力積で反復的な接触ソルバーをウォームスタートする。機械学習では、この用語は以前に学習したモデルから学習を初期化することにも使われる。

重要な理由

最適化ベースのリアルタイム制御装置は数十から数千ヘルツで動作し、その周期を満たせるのは、たいてい各求解が答えの近くから始まるからである。オフラインの計画では、良いウォームスタートが、ソルバーが妥当な動きに収束するか、失敗するか悪い局所最小解を見つけるかの分かれ目になることが多い。

主な用途

• 脚式ロボット、ドローン、マニピュレータでのリアルタイムモデル予測制御
• コンタクトインプリシット軌道最適化と非線形軌道最適化
• 全身制御における一連の関連する二次計画問題
• 物理エンジンの反復的な接触ソルバー
• 高速な動作計画のための学習による初期推定

実際の使われ方

ある脚式ロボットが 100 Hz で非線形 MPC を実行している。各求解のあと、制御装置は最適な状態軌道と入力軌道、そして乗数を保存する。次の周期では、これらを 1 ステップずらし、最後のステップを複製してホライズンの末尾を埋め、最初の状態を新たに計測した状態に置き換え、その結果を初期推定としてソルバーに渡す。こうすると、典型的な求解は 20 回ではなく 2、3 回の反復で済む。エンジニアはウォームスタートがうまくいかない場合にも対処する。大きく押されたあとや歩容を切り替えたあとは、ずらした推定が新しい最適解から遠いため、制御装置はその歩容用に保存した公称軌道にフォールバックし、その周期ではより多くの反復を許す。

よくある誤解

• ウォームスタートは高速化のためだけのものである — 非凸問題では、どの局所最適解が見つかるかも決めるため、悪いウォームスタートはソルバーを悪い解に閉じ込めることがある
• どのソルバーも同じように恩恵を受ける — 有効制約法と一次法が最も恩恵を受け、内点法は恩恵が小さく、特別な扱いが必要になることがある
• ウォームスタートには前回の決定変数だけあればよい — 双対変数や有効制約集合もあわせて与えることが、高速な収束にとって同じくらい重要なことが多い
• 前回の解は常に良い推定である — 大きな外乱、モードの切り替え、目標の変更のあとでは新しい最適解から遠く離れていることがあり、フォールバックが必要になる

知っておくべき人

• モデル予測制御のエンジニア
• 軌道最適化の開発者
• 脚式移動とドローン制御のエンジニア
• ロボティクスにおける数値最適化の実務者

関連技術

• OSQP
• qpOASES
• IPOPT
• acados
• CasADi
• リアルタイム反復法（Real-Time Iteration Scheme）

関連用語

• Model Predictive Control
• Direct Collocation
• Differential dynamic programming
• Trajectory Planning
• Model Predictive Path Integral
• Complementarity Constraint

関連プロジェクト

• GENESIS: World's fastest physics engine: 43M FPS for embodied AI learning
• Cartographer: Google's real-time 2D and 3D SLAM system for multi-platform robotics
• FAST-LIVO2: Fast, direct LiDAR-inertial-visual odometry from HKU-MARS, published in IEEE T-RO
• Drake: MIT robotics toolbox for model-based dynamics, optimization, and control system design
• Dora AI: Dataflow middleware for AI robotics applications, built in Rust
• GTSAM: Factor-graph optimization library powering many modern SLAM backends