Many planning problems in robotics share one structure: route a system from one safe region to many targets, or from many start states back to one safe region, while paying as little control effort as possible. Once the continuous dynamics are discretized into a graph of state cells and feasible transitions, this becomes a directed Steiner tree problem. That problem asks for the cheapest set of one-way edges that connects a root to $k$ terminals. In general directed graphs it is notoriously hard. The standard linear-programming relaxation can be off by a polynomial factor, and polynomial-time algorithms only achieve $O(k^\epsilon)$ ratios. Controllers with drift (a cart-pole that cannot instantly reverse its momentum, a quadrotor that is falling) produce exactly the one-way transition graphs where this hardness lives. Today's nonlinear planners therefore either chain safe sets heuristically or sample, and they come with no account of how far from optimal they are.
This note proposes to test whether that pessimism is warranted. The worst-case constructions behind directed Steiner hardness need wild combinatorial structure: huge fan-out, and edges that encode set containment. Graphs built from Lipschitz dynamics in a fixed, low state dimension have none of that. Their edges connect nearby cells, out-degree is bounded, and their geometry admits small separators. Our hypothesis is that, on such graphs, the hardness weakens to a level governed by state dimension. If so, a separator-based rounding algorithm in the style of the planar-graph results gives polynomial-time, near-certified multi-goal plans for nonlinear systems. If not, we will have identified which dynamics actually realize the hard instances.
Core Claim
Let $G_\varepsilon$ be the directed transition graph obtained by discretizing a system $x_{t+1}=f(x_t,u_t)$ with Lipschitz $f$ on a $d$-dimensional state space at resolution $\varepsilon$. An edge cost is the control effort of the corresponding transition. We conjecture two things. First, the integrality gap of the flow linear program for rooted directed Steiner tree on $G_\varepsilon$ is bounded by $\mathrm{polylog}(k)\cdot g(d)$, with no dependence on the number of cells $n$, for some function $g$. Second, the polynomial gap reappears only when $d$ grows like $\log n$, which is roughly the dimension at which arbitrary layered set-system gadgets can be embedded.
The upper bound is novel at this intersection. The file reports no paper that analyzes directed Steiner relaxations on reachability graphs of dynamical systems. The algorithmic consequence is a polynomial-time rounding procedure whose guarantee and empirical performance depend on how many shortest directed paths are needed to separate $G_\varepsilon$.
Grounding in Prior Work
Two results in directed network design motivate the conjecture by locating the hardness precisely. Polynomial Integrality Gap of Flow LP for Directed Steiner Tree proves an $\Omega(n^{0.0418})$ gap using a five-level layered graph. In that graph, intermediate vertices are subsets of a ground set and edges are containments, so fractional flow can spread thinly over exponentially many disjoint paths. ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network shows a $k^{1/4-o(1)}$ hardness for the multi-pair version under the Exponential Time Hypothesis. Both rely on graphs whose local structure is unconstrained. We ask whether bounded-dimension dynamics forbid that structure.
Note that layering alone does not help. Time-expanded reachability graphs are layered acyclic graphs, just like the Li–Laekhanukit gadget. So any argument must rely on locality and dimension, not acyclicity.
Two further results supply the method. From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs shows that planarity drops the gap to $O(\log^2 k)$. It does this by recursively splitting the graph along three shortest paths, using Thorup's separator theorem, and embedding the result into a tree of logarithmic height. Reachability graphs of even "planar" robots are not planar: a point mass in the plane has a 4-dimensional state. We therefore reuse their recursion but replace the three-path separator with a separator made of $s(d)$ shortest directed paths. The ratio is then expected to grow with $s(d)$, not with $n$.
O(log2 k / log log k)-approximation algorithm for directed Steiner tree achieves the tight ratio for general graphs, but only in $n^{O(\log^5 k)}$ time using the Sherali–Adams hierarchy, a sequence of progressively tighter linear programs. We use it only as a theoretical reference point, because it is far too slow for control.
On the control side, ABC-LMPC is the closest application. It grows a goal-conditioned safe set backward from the goal by finding new start states that can reach it, and it optimizes trajectories with the cross-entropy method, a sampler that repeatedly refits a distribution to its best samples. The authors identify chaining safe sets under irreversible dynamics as the unresolved combinatorial step. We recast exactly that step as a rooted Steiner in-arborescence on the reversed transition graph: the goal safe set is the root and the $k$ start regions are the terminals. safe-control-gym supplies the systems and constraint machinery. Its tasks are single-trajectory tracking or stabilization, so multi-terminal routing is new there.
Local safety filters such as ISSA from Model-free Safe Control for Zero-Violation Reinforcement Learning are complementary rather than competing. They project a single action into the safe set and do not plan across goals. We use one as the low-level tracker underneath the plan.
Research Program
Graph construction. We build $G_\varepsilon$ for Cart-Pole and the 2D quadrotor from safe-control-gym, and for the point mass and inverted pendulum from the ABC-LMPC environments. The procedure grids or samples states inside the constraint set and shoots short control primitives through the simulator. An edge is kept if its endpoint falls in a cell, and its cost is the integrated squared input. Constraint-violating transitions are discarded, so every edge in a solution is safe by construction up to the discretization error, which we bound using the Lipschitz constant.
Measuring the gap. We solve the flow linear program and the exact integer program for rooted directed Steiner tree, sweeping $\varepsilon$ (and hence $n$), the number of terminals $k$, and the state dimension. For dimension, we use a chain of coupled pendula or point masses so that $d$ can be raised without changing the physics family. Under the conjecture, the measured gap stays flat in $n$ at fixed $d$. A fitted exponent in $n$ comparable to $0.04$ would contradict it.
Theory, in two directions. For the upper bound, we try to prove that $G_\varepsilon$ admits balanced separators made of $s(d)$ shortest directed paths. The recursion of Chekuri et al. then yields a gap of $O(s(d)\log^2 k)$. For the lower bound, we try to realize the Li–Laekhanukit set-containment gadget as a piecewise-affine system and determine the minimal dimension at which this is possible. A matching pair of results would characterize the phenomenon. A gadget embedded at constant $d$ would refute the conjecture outright, and we would report that.
Algorithm. We implement the separator-recursion rounding with heuristically computed multi-path separators and use it as the global planner in an ABC-LMPC-style loop. The planner selects which safe-set chains to build, and a learned-model controller executes them.
Baselines
The naive reference is the union of independent cheapest paths from each start region to the goal. It is the do-nothing answer to "what does sharing buy?", and it is a trivial $k$-approximation. We run it on exactly the same $G_\varepsilon$ with the same edge costs. If it is within a few percent of the exact optimum on our benchmarks, cost-sharing is irrelevant there and the combinatorial framing is unnecessary for these tasks. Our method must beat it by a margin that grows with $k$.
The strongest existing method for this exact task is ABC-LMPC's sequential start-state expansion. It is the only method in the file that chains safe sets backward under nonlinear stochastic dynamics. Its reported result on the point mass is expanding the start domain from coordinate −25 to −70 while staying safe. It is also reported as comparable to SAVED. No reported cost figures for multi-terminal tasks were found on Lacuna, because the task is new.
To keep the comparison fair, ABC-LMPC and our planner share the same learned dynamics ensemble, the same simulator query budget, and the same wall-clock limit. Both are tuned over a matched grid of hyperparameters. Beating it means a lower total control effort to connect all $k$ start regions at equal success rate and zero constraint violations, or a higher success rate at equal effort.
The exact integer program, solved offline, serves as ground truth for measuring ratios, not as a deployable competitor. Flow-LP solutions with plain randomized rounding form an intermediate baseline.
The key ablation isolates the separator. We run the same recursion with random balanced vertex separators instead of shortest-path separators. If the ratio does not degrade, the planar-style geometry is not what makes the method work.
Why not just…?
Why not just solve the integer program exactly? This is a real threat. At benchmark resolutions, a mixed-integer solver may finish in seconds, which would make approximation guarantees practically moot. We measure solve time against $n$ and $k$ and report the crossover point where exact solving exceeds a replanning budget. If no crossover occurs at resolutions that matter for control, we say so plainly. The contribution then narrows to the gap characterization, which still tells practitioners when the linear relaxation can be trusted for fast bounds and warm starts.
Why not just take the union of shortest paths, or a greedy merge? If drift graphs rarely let different demands share edges, this baseline is already near-optimal, and nothing deep is happening. The experiment that settles it is the ratio of the path-union cost to the exact optimum as $k$ grows. We expect sharing to matter most where many start regions funnel through a common basin, such as the pendulum swing-up. We report the outcome either way.
Why not just use local nonlinear MPC or cross-entropy sampling per goal? Gradient-based solvers via CasADi, as used in safe-control-gym, optimize one trajectory from one initialization. They neither share structure across terminals nor bound suboptimality. ABC-LMPC's authors themselves cite the computational cost of the cross-entropy method as a limitation. We include per-goal cross-entropy planning, at a matched query budget, as an extra comparison in the multi-goal runs.
Proposed Experiments
The decisive checks are three.
The first is the gap-scaling plot, measured gap against $n$ at fixed $d$ for each system, together with the gap against $d$ on the coupled-chain family. Flatness in $n$ supports the conjecture. Polynomial growth refutes it.
The second is the path-union-to-optimum ratio as a function of $k$, which establishes whether the problem has real combinatorial content on physical systems.
The third is the closed-loop multi-goal comparison against ABC-LMPC. It is run on the point-mass, pendulum, Cart-Pole and 2D-quadrotor tasks under safe-control-gym's injected disturbances. Metrics are total control effort, success rate over all $k$ terminals, constraint-violation count, and planning time, all at matched simulator budgets.
If the first check fails at low dimension, the gadget-embedding construction becomes the main result. It would give the first evidence that directed-Steiner hardness is physically realizable in control.
References
- Polynomial Integrality Gap of Flow LP for Directed Steiner Tree
- ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network
- From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs
- O(log2 k / log log k)-approximation algorithm for directed Steiner tree: a tight quasi-polynomial-time algorithm
- ABC-LMPC: Safe Sample-Based Learning MPC for Stochastic Nonlinear Dynamical Systems with Adjustable Boundary Conditions
- Safe-Control-Gym: A Unified Benchmark Suite for Safe Learning-Based Control and Reinforcement Learning in Robotics
- Model-free Safe Control for Zero-Violation Reinforcement Learning