Neural networks are increasingly used as fast stand-ins for optimization solvers. They predict a robot trajectory, a power-grid setpoint or a control action in milliseconds rather than seconds. When those outputs must obey hard physical limits, a growing family of output layers can guarantee feasibility. These layers project the prediction onto the allowed set, or build it so it cannot leave the set. They work only when the allowed set is convex, meaning any straight segment between two allowed points stays allowed. The safe space around obstacles is not convex. It has holes, and the best solution depends on a discrete choice: which way around each obstacle to go. The only learned methods that go beyond convexity map the allowed set onto a ball. A set with a hole cannot be continuously deformed into a ball, so these methods fail in exactly this case.
We propose to move all of the non-convexity into a discrete choice. First, the safe set is covered, offline, by a modest number of overlapping convex regions. This is the same cover that graph-of-convex-sets motion planning already builds. The network then outputs two things: a probability distribution over routes through the graph of overlapping regions, and, for each candidate route, a continuous solution produced by an existing convex hard-constraint layer applied inside that route's regions. Every candidate is feasible by construction. The learning problem is to choose the route well, and the whole layer is trained end to end on the downstream cost. Our central claim is that the route choice is where learned solvers fail on obstacle-filled problems. A post-hoc fix that snaps an unconstrained prediction into the nearest region keeps feasibility but loses badly on cost. Training through the route choice closes most of that gap at millisecond latency.
What exists and where this sits
Three lines of work supply the pieces. Hard-constrained layers for convex sets supply the continuous part. Pinet projects predictions onto convex sets using operator splitting and computes gradients by implicit differentiation at the fixed point. Its authors state that truly non-convex constraints such as arbitrary obstacles remain a challenge. In their multi-vehicle experiment they convexify collision constraints in advance, which fixes one side of each obstacle beforehand. PolyFlow keeps every step of a generative flow inside a polytope using ray shooting, and leaves non-convex sets to convex decomposition. ConstraintNet parameterizes a polytope as a softmax-weighted combination of its vertices. We reuse these layers unchanged inside each region. They are the method, not the competitor.
The graph-of-convex-sets work supplies the representation and the benchmark. Shortest Paths in Graphs of Convex Sets and Motion Planning around Obstacles with Convex Optimization cover free space with convex regions and pose planning as a mixed-integer convex program over routes through the overlap graph. They solve a tight convex relaxation of that program. They also use Bézier curves, curves shaped by a few control points, and rely on the fact that such a curve stays inside the convex hull of its control points: control points inside one convex region keep that curve segment collision-free. These methods run as offline solvers, not differentiable layers, and they take seconds per problem. We use them as the optimality oracle and as the source of the region cover. The proposal is, in effect, an amortized and differentiable version of their route choice.
Two lines of work set the constraints. Homeomorphic Projection and Hom-PGD+ learn an invertible map from a non-convex set to a ball and project there. Their authors state they cannot handle holes or disconnected regions, and this is a topological limit, not an engineering one. DisjunctiveNet handles unions of polyhedra by lifting them to their convex hull and projecting with a linear program. Its projection is exact only at vertices of that hull, the full disjunctive form grows exponentially with the number of rules, and it is limited to linear boundaries. Our design avoids the hull entirely. We select a piece rather than relax the union, so pieces may be curved convex sets such as ellipsoids, and cost grows with the number of candidate routes kept, not with the number of disjunctions. Differentiable quadratic-programming layers (QPLayer, dXPP) are restricted to convex programs because non-convexity makes their backward linear systems singular. Our decomposition keeps every backward pass inside a convex subproblem, so their machinery stays valid on each branch.
Core Claim
Write $x$ for the problem instance, for example start, goal and obstacle layout. Let $\pi$ be a route, meaning a sequence of convex regions in which consecutive regions overlap. Let $p_\theta(\pi \mid x)$ be the network's distribution over routes, and let $y_\theta(x,\pi)$ be the solution a convex hard-constraint layer produces when restricted to that route's regions. For a trajectory, the $k$-th Bézier segment's control points are constrained to the $k$-th region, and segment endpoints are constrained to the overlaps. We train on
$$ \mathcal{L}(\theta) = \mathbb{E}_x \Big[ \sum_{\pi \in \mathcal{K}_\theta(x)} p_\theta(\pi \mid x)\, c\big(y_\theta(x,\pi), x\big) \Big] + \lambda\, \mathbb{E}_x\big[-\log p_\theta(\pi^\star(x) \mid x)\big], $$
where $c$ is the task cost (path length or control effort), $\mathcal{K}_\theta(x)$ is the top-$K$ routes produced by beam search over the region graph, $\pi^\star(x)$ is the route chosen by the graph-of-convex-sets solver when available, and $\lambda$ weights this optional imitation term. At test time we return the lowest-cost candidate in $\mathcal{K}_\theta(x)$, which costs $K$ cheap convex projections. Every candidate lies in the safe set because of the Bézier hull property, so feasibility is exact and does not depend on how well the network learned. We make two testable predictions. First, the dominant error of a feasibility-by-repair pipeline is choosing the wrong way around an obstacle, not continuous suboptimality within a route. Second, a small $K$ recovers most of the solver's quality, because a learned route distribution concentrates on a few plausible routes.
Research Program
The build has three parts. The first is an offline region cover per environment family, generated with the region-inflation procedure used by the graph-of-convex-sets papers, with the overlap graph stored. The second is a route proposer, a graph neural network over the region graph conditioned on start and goal, decoded autoregressively with beam search. The third is a per-route continuous head: a network that outputs raw control points, which Pinet's projection places into the route's polytopes. Ellipsoidal regions use a closed-form scaling, and a generative variant uses PolyFlow for multimodal trajectory sampling.
The analysis has two parts. We will decompose each method's cost gap relative to the solver into a route-mismatch part and a within-route part, which directly tests the first prediction. We will also measure how the gap and the latency scale with $K$ and with region count. We will also study the case where the environment changes at test time. The cover must then be rebuilt, which is the offline bottleneck the graph-of-convex-sets papers acknowledge. We will report cover-construction time honestly and separately from inference.
Baselines
The naive reference point is an unconstrained network regressing trajectories, with and without a soft collision penalty. It is trained on the same instances, with the same backbone and the same hyperparameter budget. We report its collision rate and cost to show how often the problem bites. Any hard-constrained method must beat it on feasibility, and should come close on cost among the instances where it happens to be feasible.
The key ablation isolates end-to-end route choice. We take the same unconstrained predictor and repair its output after the fact. The repair picks the route whose regions are nearest the prediction and projects into those regions with the identical Pinet layer. This baseline has the same feasibility guarantee and the same continuous machinery; only the training signal through the route choice is missing. We also run a variant that trains the route proposer purely by imitation ($\lambda$ only, no cost term) and one with $K=1$. The proposal counts as beating the ablation if it reduces the cost gap to the solver by at least half, with the reduction coming from route mismatch.
For the strongest topological competitor we run Homeomorphic Projection on sets made ball-like by cutting slits from each obstacle to the boundary. This is the obvious way to force its assumption. We give it the same training data and tune the invertible network's size to match our parameter count. On AC-OPF, where the set plausibly has no holes, it serves as a control that should do well. That paper reports a 100% feasibility rate on the 118-node AC-OPF case with roughly 24x speedup, and Hom-PGD+ reports a 3% optimality gap with zero violations on PGLIB 200- and 500-bus cases. On obstacle domains we expect the slits to induce large detours near the cut. DisjunctiveNet is run on 2D mazes, where regions are polytopes and the rule count is small enough for full disjunctive form. It is compared on cost and on wall-clock time as the number of obstacles grows.
The strongest existing method on quality is the graph-of-convex-sets solver itself. On 3D quadrotor navigation it reports trajectories within 1% of the global optimum in 95% of 100 random cluttered environments, 14-DOF dual-arm planning in about 4 to 13 seconds, and a 50x50 maze solved exactly with a single second-order cone program. We do not expect to beat it on cost. Beating it means matching its cost to within a few percent while running two to three orders of magnitude faster, with the same guaranteed feasibility. For PolyFlow's 2D maze, the file reports a 100% safety rate but no cost number. We will rerun it with a hand-chosen convex corridor, which is what it can express, and report cost.
Why not just…?
Why not just project onto the nearest convex region after an unconstrained prediction? This is the real threat, and it is the main ablation above. Our reason to expect it to fall short is structural. When two routes around an obstacle are near-tied, a regressor trained on mixed data averages them and lands inside the obstacle. The nearest region is then essentially arbitrary with respect to cost. If the route-mismatch share of the gap turns out small in our decomposition, the post-hoc repair is sufficient and we will say so. The contribution would then shrink to the region-cover interface.
Why not just run the graph-of-convex-sets solver online? It is the quality reference, but seconds per problem, as reported for high-DOF arms, is too slow for the replanning rates and the use as a layer inside larger learned systems that motivate hard-constrained networks. It is also not differentiable, so it cannot sit inside a larger training loop. The latency comparison at matched cost settles this directly.
Why not just use DisjunctiveNet on the union of regions? Its exactness needs full disjunctive form, which grows exponentially, or needs vertex solutions from a simplex solver. It is also restricted to polyhedra. We test it where it is feasible to run, and we expect it to stop scaling somewhere between 2D mazes and 3D quadrotor scenes.
Why not just cut the holes and use a ball homeomorphism? Cutting is possible but imposes a false wall. The optimal path may need to cross the cut, and the learned map is forced to distort heavily near it. Hom-PGD+'s error bound grows with the square root of the map's approximation error, which makes that distortion costly. The slit baseline measures this.
Proposed Experiments
We will run 2D mazes of increasing obstacle density up to the 50x50 grid, the 100-environment 3D quadrotor suite, and 7-DOF manipulator planning, following the graph-of-convex-sets protocols, with AC-OPF 118-node as a hole-free control. Metrics are feasibility rate, relative cost gap to the solver, route-mismatch rate against $\pi^\star$, and inference latency. We report cover-construction time separately.
The decisive check comes from the gap decomposition on quadrotor scenes. The proposal succeeds if post-hoc nearest-region repair leaves a gap dominated by route mismatch, and our layer with $K \le 8$ removes most of it while staying under ten milliseconds and fully feasible. If route mismatch turns out to be a minor share, the central claim is wrong. A secondary check covers held-out obstacle layouts with rebuilt covers, to test whether the route proposer generalizes across graphs rather than memorizing one.
References
- Pinet: Optimizing hard-constrained neural networks with orthogonal projection layers
- PolyFlow: Safe and Efficient Polytope-Constrained Flow Matching with Constraint Embedding and Projection-free Update
- Sample-Specific Output Constraints for Neural Networks
- Shortest Paths in Graphs of Convex Sets
- Motion planning around obstacles with convex optimization
- Low Complexity Homeomorphic Projection to Ensure Neural-Network Solution Feasibility for Optimization over (Non-)Convex Set
- Hom-PGD$^+$: Fast Reparameterized Optimization over Non-convex Ball-Homeomorphic Set
- DisjunctiveNet: Neural Symbolic Learning via Differentiable Convexified Optimization Layers
- Leveraging augmented-Lagrangian techniques for differentiating over infeasible quadratic programs in machine learning
- A Penalty Approach For Differentiation Through Black-box Quadratic Programming Solvers