Graphs of Convex Sets

Splitting free space into convex chunks connected into a graph, then using convex optimization to find a globally good, smooth trajectory.

Proposed by Tobia Marcucci and colleagues in MIT Russ Tedrake's group: the underlying ‘shortest paths in graphs of convex sets’ theory was published in SIAM Journal on Optimization (2024), with the motion-planning application in Science Robotics (2023). Configuration space's collision-free region is first decomposed into a set of convex regions, each a node in a graph, with edges between regions that overlap; a Bézier curve then represents each trajectory segment within a region, and the problem decides both which regions to pass through and the shape of each curve. This is fundamentally a mixed-integer optimization, but its convex relaxation is tight enough that solving one convex program and rounding is usually enough to get a globally optimal or near-optimal trajectory, with an accompanying optimality bound. Compared to sampling-based planners like RRT or PRM, the resulting trajectory is smoother and higher quality; the cost is needing a convex decomposition up front. Drake already includes an implementation.

ExampleUsing Drake's GcsTrajectoryOptimization: given several collision-free convex regions for an arm moving among shelves, the solver outputs a smooth trajectory that passes through these regions, respects velocity limits, and takes as little time as possible.

Also called

GCS, Graph of Convex Sets, GCS Motion Planning

Related

Motion Planning · Rapidly-exploring Random Tree · Probabilistic Roadmap · Convex Optimization · Trajectory Optimization · Drake

Sources

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