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 以浏览我们的开源机器人项目。