凸集图规划

把无碰撞空间拆成凸块连成图，用凸优化求出全局较优的平滑轨迹。

由 MIT Russ Tedrake 组的 Tobia Marcucci 等人提出：「凸集图上的最短路」理论发表于 SIAM Journal on Optimization（2024），运动规划应用发表于 Science Robotics（2023）。先把构型空间里的无碰撞区域分解成若干凸区域，每块是图的一个节点，相互重叠的块之间连边；再在每块内用贝塞尔曲线表示一段轨迹，同时决定走哪些块和曲线的形状。这本是混合整数优化，但它的凸松弛很紧，解一次凸优化再做简单取整，通常就能得到全局最优或接近最优的轨迹，并附带最优性界。相比 RRT、PRM 等采样式规划，轨迹更平滑、质量更高；代价是要预先做凸分解。Drake 中已有实现。

例子用 Drake 的 GcsTrajectoryOptimization：给出机械臂在货架间的若干无碰撞凸区域，求解器输出一条穿过这些区域、满足速度限制、用时尽量短的平滑轨迹。

也叫

凸集图、Graph of Convex Sets、GCS 运动规划

相关

运动规划、快速扩展随机树、概率路线图、凸优化、轨迹优化、Drake

来源

Marcucci et al., Motion Planning around Obstacles with Convex Optimization (arXiv 2205.04422)
Marcucci et al., Shortest Paths in Graphs of Convex Sets (arXiv 2101.11565, SIAM J. Optim. 2024)
Drake: GcsTrajectoryOptimization