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）集合取代凸集合：在這種集合中，任兩點都由一條留在集合內的唯一最短路徑（也就是測地線）相連。做了這個改變之後，同樣的圖表述就能在這類非歐幾里得空間上進行規劃。GCS 已收錄在 Drake 工具箱中。

為何重要

以取樣為基礎的規劃器能找到可行路徑，但通常需要平滑化，而且無法衡量路徑有多好。GCS 在單次最佳化中產生平滑且遵守約束的軌跡，並常附帶一個說明結果離最佳有多近的證明；這對在貨架與工作站等固定單元中反覆作業的機器手臂很有價值。

主要應用

  • 固定工作單元中機器手臂的無碰撞軌跡規劃
  • 為具有連續關節或會繞回之組態空間的機器人進行規劃
  • 在地形的凸區域上進行落腳點與接觸規劃
  • 無人機穿越雜亂環境的最短時間軌跡
  • 共用工作範圍中的雙臂與多臂規劃

實際應用

一個團隊部署一支機器手臂，從一組固定的貨架料盒中揀選物品。他們先離線產生組態空間中無碰撞部分的凸區域，在每個料盒前方與內部的組態處為 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 以瀏覽我們的開源機器人專案。