Open Source Robotics

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

Graph of Convex Sets

  • 別名: GCS, graphs of convex sets
  • カテゴリ: Planning & manipulation › Trajectory optimisation
  • タグ: motion-planning, convex-optimization, trajectory-optimization, configuration-space, manipulation

自由空間の凸領域をグラフでつなぎ、凸最適化によってその中を通る滑らかで衝突のない経路を見つける動作計画の定式化。

定義

凸集合グラフ（Graph of convex sets、GCS）は、各頂点が凸集合であり、各集合の中で選ぶ点が連続的な決定変数となるグラフである。辺は行き来できる集合同士をつなぎ、辺のコストと制約は両端の点の凸関数である。このようなグラフで最もコストの低い経路を見つけることは、どの集合を通るかという離散的な選択と、各集合のどこを通るかという連続的な選択を組み合わせることになる。Tobia Marcucci、Russ Tedrake らはこの最短経路問題を定式化し、一般には混合整数問題であるものの、多くの場合にタイトまたはほぼタイトになる強い凸緩和をもつことを示した。

動作計画に使う場合は、まずコンフィギュレーション空間の衝突のない部分を凸領域の集まりで覆う。たとえば IRIS アルゴリズムは、シード点から障害物のない大きな多面体を成長させる。各領域が頂点となり、重なり合う領域は辺で結ばれる。各領域の内部では、軌道は滑らかな曲線、典型的には Bézier 曲線で表され、曲線の制御点が領域内にあるので曲線も領域内にとどまる。経路長、所要時間、エネルギーなどのコストや、速度と加速度の制限は凸制約として書かれる。緩和問題を解いて丸めれば、サンプリングベースの探索や後処理なしに、滑らかで衝突のない軌道が得られる。

この手法は、各集合の中が通常のユークリッド幾何であることを前提とする。制限のない連続回転関節や移動ベースの方位のように、コンフィギュレーション空間が周期的に一周するロボットは、そのままではこの前提に合わない。拡張手法では、凸集合を多様体上の測地的に凸（geodesically convex）な集合に置き換える。これは、任意の 2 点が集合内にとどまる唯一の最短経路、すなわち測地線で結ばれる集合である。この変更により、同じグラフの定式化でこうした非ユークリッド空間上の計画ができる。GCS は Drake ツールボックスで利用できる。

重要な理由

サンプリングベースのプランナーは実行可能な経路を見つけるが、通常は平滑化が必要で、経路の良さを測る尺度も与えない。GCS は 1 回の最適化で制約を守る滑らかな軌道を生成し、結果が最適にどれだけ近いかの証明が付くことも多い。これは、棚や作業ステーションのような固定セルで繰り返し作業するロボットアームにとって価値がある。

主な用途

  • 固定されたワークセルにおけるロボットアームの衝突のない軌道計画
  • 連続関節をもつロボットや、一周するコンフィギュレーション空間をもつロボットの計画
  • 地形の凸領域上での足場計画と接触計画
  • 障害物の多い環境を通り抜けるドローンの最短時間軌道
  • 共有作業空間での双腕・多腕の計画

実際の使われ方

固定された棚のビン群からピッキングするアームを導入するチームは、まずオフラインでコンフィギュレーション空間の衝突のない部分の凸領域を生成し、各ビンの手前と内部のコンフィギュレーションに IRIS のシードを置く。これには時間がかかるが、やり直す必要があるのはセルが変わったときだけである。実行時には、各ピッキング要求が、現在のコンフィギュレーションからいずれかのビン内の目標への GCS クエリになる。ソルバーは速度制限を守った滑らかな軌道を返す。求解時間は領域の数とともに増えるので、チームは領域の集合をセルに必要な規模以上にしない。目標がどの領域の外にもある場合はクエリが失敗するので、カバレッジが欠けている所にシードを追加する。モデルになかった物体に対しては、短いホライズンの衝突判定が引き続き備えとなる。

よくある誤解

  • GCS では自由空間が凸である必要がある — 必要なのは自由空間が凸領域の和集合で覆われていることであり、和集合は複雑な形状を近似できる
  • GCS は凸最適化によって常に大域的最適解を返す — 緩和はタイトであることが多いが常にではなく、丸めや混合整数問題としての求解が必要な場合がある
  • GCS は衝突判定を完全に置き換える — 衝突がないことを保証するのは使用した領域に対してだけなので、領域は実際の環境を反映していなければならない

知っておくべき人

  • ロボットアームとドローンの動作計画エンジニア
  • 最適化ベースの計画の研究者
  • 固定セルのピッキング・組立システムのインテグレーター
  • 計画と凸最適化を学ぶロボティクスの学生

関連技術

  • Drake
  • IRIS 領域生成（IRIS Region Generation）
  • Bézier 曲線（Bézier Curves）
  • 凸最適化（Convex Optimization）
  • 混合整数凸計画（Mixed-Integer Convex Programming）

関連用語

  • Configuration Space
  • Motion Planning
  • Trajectory Planning
  • Mixed-Integer Programming
  • Probabilistic Roadmap
  • RRT*

関連プロジェクト

  • LeRobot: HuggingFace ML library for real-world robotics in PyTorch
  • Isaac Lab: NVIDIA robot learning framework: one task API across Newton, PhysX and Isaac Sim
  • NVIDIA Isaac GR00T: NVIDIA open foundation model for humanoid robot reasoning and skills
  • OpenVLA: 7B-parameter Vision-Language-Action model for robotic manipulation
  • Drake: MIT robotics toolbox for model-based dynamics, optimization, and control system design
  • OpenArm: 7DOF humanoid arm for physical AI research in contact-rich environments

動画

  • MIT Robotics - Russ Tedrake - Planning with Graphs of Convex Sets (in the age of foundation models): MIT Robotics

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