From the free course Motion Planning with Graphs of Convex Sets on Lykke
The Gap Between Discrete and Continuous Planning
Key concepts: Combinatorial Optimization · Trajectory Optimization · Local Minima · Completeness
An analysis of the traditional divide between combinatorial graph search and continuous trajectory optimization.
The Gap Between Discrete and Continuous Planning
In the field of robotic motion planning, a fundamental schism has long existed between two disparate algorithmic philosophies: Discrete Combinatorial Search and Continuous Trajectory Optimization. For decades, practitioners have been forced to choose between the global connectivity guarantees of graph-based methods and the local, dynamically feasible precision of optimization-based methods. This "gap" is not merely a matter of implementation preference; it is a mathematical divide rooted in the topology of configuration spaces ($C$-space) and the computational complexity of navigating non-convex environments.
The challenge arises because the "free space" ($\mathcal{C}_{free}$) in which a robot moves is almost never convex. Obstacles create "holes" or "voids" in the manifold of valid configurations, forcing any planner to make discrete, topological decisions: Do I go left of the pillar or right? Once that discrete decision is made, the problem becomes one of continuous refinement: How do I steer the actuators to follow that path smoothly? Historically, we have solved these two problems sequentially or in isolation, leading to solutions that are either jerky and impractical or smooth but trapped in sub-optimal local minima.
The Discrete Regime: Combinatorial Search and Completeness
Discrete planning treats the world as a collection of nodes and edges. Whether through a predefined grid, a visibility graph, or sampling-based methods like Rapidly-exploring Random Trees (RRT) and Probabilistic Roadmaps (PRM), the goal is to find a sequence of symbolic states that connect a start configuration $q_{start}$ to a goal $q_{goal}$.
Definition: Resolution Completeness A discrete planner is said to be resolution complete if, given a solution exists, the algorithm is guaranteed to find it within a finite amount of time, provided the discretization (grid size or sample count) is sufficiently fine.
The primary advantage of the discrete approach is its ability to handle complex topologies. Because algorithms like Dijkstra’s or A* explore the graph systematically, they do not get "stuck" in the sense that an optimizer does. If a path exists through a narrow corridor, a discrete search will eventually find it. However, this comes at a significant cost:
| Feature | Discrete Search (e.g., A*, RRT*) |
|---|---|
| State Space | Discretized or sampled; loses the "infinitesimal" precision of the real world. |
| Dynamics | Difficult to incorporate; often requires "kinodynamic" sampling which scales poorly. |
| Optimality | Only optimal relative to the graph; paths are often "jagged" and require post-processing. |
| Complexity | Exponential in the dimension of the state space (The Curse of Dimensionality). |
The "gap" here is one of quality. A discrete planner might tell you to turn 90 degrees instantly—a physical impossibility for a high-speed drone or a heavy robotic arm. To fix this, we typically "smooth" the path afterward, but this post-processing often pushes the trajectory back into obstacles or violates the very optimality the search was intended to provide.
The Continuous Regime: Trajectory Optimization and Local Minima
On the other side of the divide lies Trajectory Optimization. Here, we represent the robot's path as a continuous function of time, $x(t)$, and attempt to minimize a cost functional $J = \int_{0}^{T} L(x, u) dt$ subject to the robot's nonlinear dynamics $\dot{x} = f(x, u)$ and obstacle constraints $g(x) \leq 0$.
This is typically solved using local methods like Sequential Quadratic Programming (SQP) or Differential Dynamic Programming (DDP). These methods use the gradient of the cost and the Jacobian of the constraints to "push" the trajectory toward a lower-cost, feasible solution.
The Problem of Non-Convexity
The Achilles' heel of continuous optimization is the Local Minimum. Because obstacles are represented as "keep-out" zones, the feasible set of trajectories is non-convex. If an optimizer is initialized on the "wrong" side of an obstacle, the gradient will point it toward the obstacle's surface, where it will get stuck, unable to "jump" to the other side where the global optimum might reside.
The Local Minimum Trap: Imagine a robot trying to reach a goal behind a wall. A local optimizer initialized to go straight will hit the wall and stop, as any small movement left or right might initially increase the distance to the goal or the control effort, creating a "valley" in the cost landscape from which the optimizer cannot escape.
The Mathematical Conflict: NP-Hardness vs. Convexity
Why is this gap so hard to bridge? It comes down to the complexity classes of the underlying math. Finding the shortest path in a non-convex environment is known to be NP-Hard as the number of dimensions increases. Conversely, Convex Optimization is "easy" (solvable in polynomial time) and provides global guarantees.
The gap exists because we are trying to solve an NP-Hard problem (discrete topological choice) using tools designed for convex problems (continuous refinement). Traditional attempts to merge them usually fall into one of two camps:
- Mixed-Integer Programming (MIP): Formulating the obstacle avoidance as "either/or" constraints. While exact, MIP solvers often struggle with the nonlinear dynamics of robots, leading to massive computation times for even simple tasks.
- Sampling-based Motion Planning (SBMP): Using discrete samples to "seed" local optimizers. This is the current industry standard (e.g., in the MoveIt! framework), but it lacks the mathematical elegance and robustness of a unified framework.
Bridging the Gap: Graphs of Convex Sets (GCS)
The breakthrough discussed by Russ Tedrake involves a new mathematical framework called Graphs of Convex Sets (GCS). GCS aims to unify the discrete and continuous by rethinking what a "node" in a graph represents. In a traditional graph, a node is a single point. In GCS, a node is a convex set (e.g., a polytope or an ellipsoid) in the configuration space.
The GCS Formulation
In GCS, we decompose the free space $\mathcal{C}_{free}$ into a collection of overlapping convex regions $\mathcal{X}_i$. We then define a graph where:
- Nodes are the convex sets $\mathcal{X}_i$.
- Edges represent the ability to transition from one set to another (usually where sets overlap).
- Continuous Variables $x_i$ are constrained to lie within their respective sets $\mathcal{X}_i$.
The "magic" of GCS is that the problem of finding the shortest path through this graph, while simultaneously optimizing the continuous trajectory within each set, can be formulated as a Convex Optimization problem—specifically, a relaxation of a Mixed-Integer Program that is remarkably tight.
Convex Decomposition: Tiling the Free Space
To use GCS, one must first solve the "Convex Decomposition" problem: how do we turn a complex, non-convex environment into a set of convex polytopes? One leading method is the IRIS (Iterative Regional Inflation by Semidefinite programming) algorithm.
How IRIS Works:
- Seed Point: Start with a point in $\mathcal{C}_{free}$.
- Find Nearest Obstacle: Locate the closest point on any obstacle.
- Hyperplane Separation: Draw a plane (a "tangent") between the seed and the obstacle.
- Inscribe Ellipsoid: Maximize the volume of an ellipsoid that does not cross any of these planes.
- Iterate: Use the new ellipsoid to find more obstacles and refine the planes until a large convex "bubble" of free space is formed.
By repeating this process, we can "tile" the entire environment with a finite number of overlapping convex sets. This transforms the infinite complexity of the environment into a finite, combinatorial structure that still preserves the continuous nature of the space.
| Method | Representation | Obstacle Handling | Global Optimality |
|---|---|---|---|
| Grid Search | Discrete Pixels/Voxels | Binary Occupancy | Yes (Resolution) |
| Trajectory Opt | Continuous Splines | Penalty Functions | No (Local Minima) |
| GCS | Graphs of Convex Sets | Set Constraints | Yes (Global) |
The Power of Perspective Functions
The technical core of bridging the gap in GCS involves the use of perspective functions. When we decide whether to "use" an edge in a graph, we usually use a binary variable $z \in {0, 1}$. In standard optimization, this makes the problem non-convex.
However, if we have a convex cost function $f(x)$, we can define its perspective as $g(x, z) = z f(x/z)$. This transformation allows us to "relax" the binary choice. Instead of $z$ being exactly 0 or 1, we let $z$ be anywhere in the interval $[0, 1]$. Because of the properties of perspective functions, the resulting optimization problem remains convex.
This means we can solve for the "flow" of a trajectory through the graph. If the relaxation is tight (which it often is in GCS), the optimizer will naturally push the $z$ values toward 0 or 1, effectively "searching" all possible paths through the obstacles simultaneously and picking the best one—all without ever getting stuck in a local minimum.
Worked Example: Navigating a 2D Maze
Consider a simple 2D robot that needs to move from $(0,0)$ to $(10,10)$ in a room with a large central obstacle.
- Decomposition: Using IRIS, we generate four convex polytopes (rectangles) that cover the free space around the central obstacle. Let's call them $S_{North}, S_{South}, S_{East}, S_{West}$.
- Graph Construction: We create edges between sets that overlap. For example, $S_{West}$ overlaps with $S_{North}$ and $S_{South}$.
- Cost Definition: We define our cost as the squared Euclidean distance: $\sum |x_{i+1} - x_i|^2$.
- Optimization: We solve the GCS problem. The optimizer doesn't just "try" the North path. It looks at the entire graph of sets. It evaluates the minimum possible cost of traversing ${S_{West} \to S_{North} \to S_{East}}$ versus ${S_{West} \to S_{South} \to S_{East}}$.
- Result: Because the formulation is convex, the solver returns the mathematically guaranteed shortest path that respects the boundaries of the rectangles.
In a traditional optimizer, if you started the robot slightly closer to the South, it would be forced to take the South path. In GCS, even if you start near the South, if the North path is 1% shorter, the solver will find it.
Common Pitfalls and Limitations
While GCS and similar convex-bridging methods are powerful, they are not magic bullets. Senior engineers should be aware of several critical nuances:
- Decomposition Quality: The efficiency of the search depends heavily on the convex decomposition. If the sets are too small or too numerous, the resulting graph becomes massive, slowing down the solver. If they are too large, they might not capture the nuances of the environment.
- High-Dimensional Dynamics: While GCS handles kinematics beautifully, incorporating full nonlinear dynamics (like the aerodynamics of a flapping wing) still requires approximations. Often, we use "flat" outputs or mixed-integer formulations that can become computationally expensive.
- The Relaxation Gap: Although the GCS relaxation is "tight," it is not always perfect. In some edge cases, the solver might return a "fractional" solution where the robot seems to exist in two paths at once. Rounding these solutions back to a valid path requires careful algorithmic handling.
Summary of the Integrated Approach
The "Gap" between discrete and continuous planning is being closed by moving away from the "Search then Optimize" pipeline toward a "Search via Optimization" framework. By encoding the discrete topology of the world into the constraints of a convex program, we gain the best of both worlds: the reliability of a map and the elegance of a smooth curve.
As robotics moves toward more safety-critical applications—such as autonomous surgery or high-speed urban drone delivery—the ability to provide global guarantees on trajectory optimality and feasibility becomes not just a theoretical luxury, but a fundamental requirement.
Source Materials
Study Motion Planning with Graphs of Convex Sets on Lykke
This course page is free to open: signed out, you can read its first two sections, and signing in, on any plan, opens the rest. The free Lykke Chrome extension syncs your own Canvas courses, so ChatGPT, Claude and Muse can answer from your classes and deadlines. It only reads Canvas.
Add the free extensionSign in to open every sectionAll sections of Motion Planning with Graphs of Convex Sets · Browse more course pages