Open Source Robotics

高品質なオープンソースロボティクスプロジェクト、ツール、ソフトウェアの厳選コレクション。

Mixed-Integer Programming

  • 別名: MIP, MILP, MIQP, MICP
  • カテゴリ: Planning & manipulation › Trajectory optimisation
  • タグ: optimization, integer-programming, motion-planning, task-allocation, hybrid-systems

一部の変数が整数値（多くの場合 0 か 1）をとらなければならない最適化で、1 つの問題の中で離散的な選択と連続的な量を組み合わせられる。

定義

混合整数計画（Mixed-integer programming、MIP）は、連続変数と、整数に制限された変数とが混在する最適化であり、整数変数は 0 か 1 の値をとる 2 値変数であることが最も多い。2 値変数は離散的な決定を表す。経路がどの領域を通るか、次にどの足を着地させるか、ある接触が有効かどうか、どのロボットがどのタスクを受け持つかといったものである。連続変数は、位置、速度、力などの残りを担う。一般的なクラスは残りの問題の形で名付けられており、混合整数線形計画（MILP）、混合整数二次計画（MIQP）、より一般には混合整数凸計画（MICP）がある。

これらの問題は一般には NP 困難だが、最新のソルバーは多くの実用的なインスタンスをうまく扱える。用いるのは分枝限定法である。整数の要件を外した連続緩和を解き、小数になった変数を 1 つ選び、それを切り下げるか切り上げるかを強制する 2 つの部分問題に分け、緩和解がすでにそれまでに見つかった最良の整数解より悪い分枝を枝刈りする。その過程で切除平面が緩和を引き締める。Gurobi や CPLEX のような商用ソルバー、SCIP、HiGHS、CBC のようなオープンソースのソルバーがこれらの手法を実装している。

問題をどう書くかは、どのソルバーを使うかと同じくらい重要である。論理条件はよくビッグ M 制約（big-M constraints）で符号化される。これは 2 値変数と大きな定数で制約をオンまたはオフにするもので、定数が大きすぎると緩和が弱まり、数値的な問題を引き起こす。緩和がタイトな定式化ははるかに速く解ける。凸集合グラフのような構造化された手法が、緩和が真の問題に近くなるように設計されている理由の 1 つはここにある。

重要な理由

ロボットの計画問題の多くは、障害物の左右どちらを通るか、接触の順序の選択、タスクの割り当てのように、部分的に離散的である。混合整数計画は、手作りのヒューリスティックやサンプリングに頼る代わりに、これらの選択を 1 つの最適化の中で厳密に扱い、答えが最適からどれだけ離れているかの上下界を与えることも多い。

主な用途

  • 脚ロボットの足場と接触順序の計画
  • ドローンとロボットアームの凸領域を通る軌道計画
  • ロボットフリートのタスク割り当てとスケジューリング
  • 離散モードをもつハイブリッドモデル予測制御
  • 離散的な行動の選択を伴うタスクと動作の統合計画

実際の使われ方

飛び石を渡るヒューマノイドの足場を計画するチームは、各石の歩ける表面を凸多角形で表す。この先の各ステップについて、足がどの多角形に着地するかを選ぶ 2 値変数と、選ばれた多角形に対してだけ有効になる制約を加え、さらに足の位置を表す連続変数と、歩幅と旋回の制限を加える。コストは目標への前進に報酬を与え、不自然な歩みにペナルティを課す。混合整数ソルバーは、通常は再計画用に設定した制限時間内に、ステップの系列を、見つかった最良解と最良の上下界との間のギャップとともに返す。求解時間が長すぎる場合は、一度に計画するステップ数を減らすか、ビッグ M の値を引き締めるか、前回の計画からウォームスタートする。

よくある誤解

  • 混合整数計画はロボティクスには常に遅すぎる — 小規模でうまく定式化された問題は、オンラインの再計画に十分な速さで解ける
  • 連続緩和を丸めれば最適な整数解が得られる — 緩和がタイトでない限り、丸めた結果は実行不可能だったり最適から大きく外れたりしうる
  • ビッグ M 制約の M は大きな値なら何でもよい — 大きすぎる値は緩和を弱め、数値的な困難を引き起こす
  • 制限時間で止まったソルバーは失敗している — 通常はそれまでの最良解と、その良さを示す最適性ギャップを返す

知っておくべき人

  • 動作計画と足場計画のエンジニア
  • フリートのスケジューリングとタスク割り当ての開発者
  • 最適化ベースの制御の研究者
  • 最適化を学ぶロボティクスの学生

関連技術

  • 分枝限定法（Branch and Bound）
  • Gurobi
  • SCIP
  • HiGHS
  • 線形計画（Linear Programming）
  • 凸最適化（Convex Optimization）

関連用語

  • Graph of Convex Sets
  • Task and Motion Planning
  • Model Predictive Control
  • Motion Planning
  • Trajectory Planning
  • Multi-Agent Path Finding

関連プロジェクト

  • Drake: MIT robotics toolbox for model-based dynamics, optimization, and control system design
  • GTSAM: Factor-graph optimization library powering many modern SLAM backends
  • OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
  • MoveIt 2: Motion planning framework for ROS 2 robot arms, with kinematics and collision checking
  • PyRoki: Modular Python toolkit for kinematic optimization across CPU, GPU, and TPU via JAX
  • PyPose: PyTorch library for differentiable robotics with deep learning and Lie group optimization

動画

  • Mixed Integer Linear Programming (MILP) Tutorial: APMonitor.com

ウィキペディア

  • 整数計画問題

このウェブサイトにはJavaScriptが必要です。オープンソースロボティクスプロジェクトを閲覧するにはJavaScriptを有効にしてください。