Graph of Convex Sets

• Also called: GCS, graphs of convex sets
• Category: Planning & manipulation › Trajectory optimisation
• Tags: motion-planning, convex-optimization, trajectory-optimization, configuration-space, manipulation

A motion planning formulation that links convex regions of free space in a graph and finds a smooth, collision-free path through them by convex optimization.

Definition

A graph of convex sets (GCS) is a graph in which every vertex is a convex set and the point chosen inside each set is a continuous decision variable. Edges connect sets that can be passed between, and edge costs and constraints are convex functions of the points at either end. Finding the cheapest route through such a graph combines a discrete choice, which sets to pass through, with a continuous one, where in each set to go. Tobia Marcucci, Russ Tedrake and colleagues formulated this shortest-path problem and showed that, although it is a mixed-integer problem in general, it has a strong convex relaxation that is often tight or nearly tight.

For motion planning, the collision-free part of configuration space is first covered by a collection of convex regions, for example with the IRIS algorithm, which grows large obstacle-free polytopes from seed points. Each region becomes a vertex, overlapping regions are joined by edges, and inside each region the trajectory is represented as a smooth curve, typically a Bézier curve, that stays within the region because the curve's control points do. Costs such as path length, duration or energy, and limits on velocity and acceleration, are written as convex constraints. Solving the relaxation and rounding it gives a smooth, collision-free trajectory without sampling-based search or post-processing.

The approach assumes ordinary Euclidean geometry within each set. Robots whose configuration spaces wrap around, such as continuous revolute joints without limits or a mobile base's heading, do not fit that assumption directly. Extensions replace convex sets with geodesically convex sets on a manifold: sets in which any two points are joined by a unique shortest path, or geodesic, that stays inside the set. With that change the same graph formulation can plan on such non-Euclidean spaces. GCS is available in the Drake toolbox.

Why it matters

Sampling-based planners find feasible paths but usually need smoothing and give no measure of how good the path is. GCS produces smooth, constraint-respecting trajectories in a single optimization, often with a certificate of how close to optimal the result is, which is valuable for arms working repeatedly in fixed cells such as shelves and workstations.

Key applications

• Collision-free trajectory planning for manipulators in fixed workcells
• Planning for robots with continuous joints or wrapping configuration spaces
• Footstep and contact planning over convex regions of terrain
• Minimum-time trajectories for drones through cluttered environments
• Bimanual and multi-arm planning in shared workspaces

In practice

A team deploying an arm to pick from a fixed set of shelf bins first generates convex regions of collision-free configuration space offline, seeding IRIS at configurations in front of and inside each bin. This takes time but only needs to be redone when the cell changes. At run time, each pick request becomes a GCS query from the current configuration to a goal in one bin. The solver returns a smooth trajectory with velocity limits respected, and solve time grows with the number of regions, so the team keeps the region set no larger than the cell needs. If a goal lies outside every region, the query fails, so the team adds seeds where coverage is missing. A short-horizon collision check still guards against objects that were not in the model.

Common misconceptions

• GCS requires free space to be convex — it requires free space to be covered by a union of convex regions, which can approximate complex shapes
• GCS always returns the global optimum by convex optimization — the relaxation is often tight but not always; rounding or a mixed-integer solve may be needed
• GCS replaces collision checking entirely — it guarantees collision-freedom only with respect to the regions used, so the regions must reflect the real environment

Who should know this

• Motion planning engineers for manipulators and drones
• Researchers in optimization-based planning
• Integrators of fixed-cell picking and assembly systems
• Robotics students studying planning and convex optimization

Related technologies

• Drake
• IRIS Region Generation
• Bézier Curves
• Convex Optimization
• Mixed-Integer Convex Programming

Related terms

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

Related projects

• 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

Videos

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