Sparse Navigation Graphs for Asymmetric Costs via Bounded Asymmetry

Robots that share maps over weak wireless links must send small maps. The usual way to shrink a map graph is a spanner: a subgraph that keeps few edges but guarantees every shortest path grows by at most a fixed factor. Spanners work well when travel costs are symmetric. Real terrain is not symmetric. Going uphill costs more energy than going down, moving against a current costs more than moving with it, and some doors open only one way. For general one-way graphs the theory is discouraging: sparse spanners with small stretch cannot exist, and the worst case needs a quadratic number of edges. We argue that this worst case comes from a specific failure of the distance axioms. In those bad graphs the cost of going back can be unbounded. Physical navigation graphs almost never look like that, because the uphill cost is usually within a small factor κ of the downhill cost.

We propose to treat bounded asymmetry as an axiom in its own right. A "κ-quasimetric" is a distance that satisfies the triangle inequality and is never more than κ times more expensive in one direction than in the other. We then build compressed navigation graphs whose one-way stretch is provably controlled by κ. The goal is to keep the sparsity of undirected spanners where asymmetry is mild, and to pay for density only on the truly one-way edges. We test this inside the hierarchical scene-graph compression pipeline used for multi-robot navigation.

Core Claim

Let $G$ be a directed graph with edge costs $w(a,b)$. Call an edge κ-reversible if the reverse edge exists and $w(b,a) \le \kappa\, w(a,b)$, and call it one-way otherwise. Our claim is that the directed-spanner barrier is driven entirely by one-way edges and by unbounded κ. On graphs where all but $s$ edges are κ-reversible, a subgraph $H$ exists and can be built quickly with

$$d_H(u,v) \le t \cdot d_G(u,v) \quad \text{and} \quad |E_H| = O\!\left(f(\kappa)\, n^{1+1/k} + s\right),$$

where $d$ denotes one-way shortest-path distance, $t = 2k-1$ is the target stretch, $n$ is the number of nodes, and $f$ is a function of the asymmetry bound alone. Two endpoints are already easy to reach. First, the max-symmetrized cost $\max(w(a,b), w(b,a))$ is a metric, and an undirected spanner on it gives one-way stretch $t\kappa$ with no $\kappa$ penalty in size; this follows by sandwiching the one-way distance between the original and the max-symmetrized distance. Second, keeping every edge gives stretch 1 at quadratic size. The open question, and the research contribution, is whether a construction can keep stretch $t$, independent of κ, while paying only a modest $f(\kappa)$ in size. The natural candidate is the directed greedy spanner, which scans pairs by increasing cost and adds an edge only when the current subgraph violates stretch $t$. We conjecture that it achieves $f(\kappa) = O(\kappa)$. The intuition is that bounded asymmetry turns every short directed cycle into a cycle of bounded roundtrip length, which restores the girth argument that makes undirected greedy spanners sparse.

Relation to Prior Work

The roundtrip line of work motivates the axiomatic view and supplies tools. Pachocki et al. showed that the roundtrip distance $d(u,v)+d(v,u)$ is a metric on strongly connected graphs. They used this to build roundtrip spanners with $O(n^{1+1/k})$ edges and $O(k\log n)$ stretch in near-linear time. Chechik et al. reached stretch 8 with $\tilde O(n^{3/2})$ edges using paired in-balls and out-balls. Dalirrooyfard and Vassilevska Williams improved this to $5+\epsilon$. All three bound roundtrip stretch. A robot travels one way, and a roundtrip guarantee says nothing useful about $d_H(u,v)$ when $d(v,u)$ is large. Our work adds the missing quantity, κ, that converts roundtrip guarantees into one-way guarantees, and it asks whether the conversion can be done without the factor κ loss.

The general directed-spanner results constrain the design. The flow-LP methods of Dinitz and Krauthgamer and Berman et al. only achieve polynomial approximation ratios such as $\tilde O(n^{2/3})$ for arbitrary directed instances. Transitive-closure spanners preserve reachability rather than costs. These results tell us not to aim at arbitrary digraphs. We restrict the input class by an axiom instead.

The axiomatic-distance literature supplies the lens. Acharyya, Banerjee and Boley and Chen, Chen and Rao show that naive symmetrization of an asymmetric divergence generally fails the triangle inequality, and that the right transformation must be chosen carefully. Our setting is the reverse situation. Path costs are already quasimetric, so max-symmetrization is a valid metric. The cost of using it is a loss of κ in stretch, not a loss of the triangle inequality. The question becomes how much of that loss can be avoided.

The application regime comes from D-Lite. Its bottom-up and top-down greedy spanners (BUD-Lite, TOD-Lite) compress hierarchical 3D scene graphs while preserving paths between navigation terminals. They assume symmetric, static costs. We keep the hierarchy and the terminal-pair formulation and replace the symmetric spanner step.

Research Program

The theoretical part has three goals. The first is to prove or refute the $O(\kappa\, n^{1+1/k})$ size bound for the directed greedy $t$-spanner on κ-reversible graphs, starting from the girth argument and the roundtrip cycle bounds above. The second is to give a lower-bound family showing how $f(\kappa)$ must grow. Directed matchings are the Ω(n²) example when κ is infinite, and interpolating them for finite κ should expose the true dependence. The third is to extend the result to terminal-pair spanners, since navigation only needs guarantees between a terminal set $T$, and to mixed graphs with $s$ one-way edges.

The algorithmic part has three components. We will build a hybrid constructor that partitions edges into κ-reversible and one-way edges. It runs greedy on the reversible part and keeps only the one-way edges that some terminal path actually needs. We will plug this constructor into BUD-Lite and TOD-Lite in place of their symmetric step. We will also measure how far the empirical κ distribution of realistic cost models is from the worst case.

Baselines

The naive reference point is to transmit the full directed scene graph. It gives stretch 1 and no compression, and it anchors both axes of every plot.

The strongest existing system is D-Lite (Chang et al.), run on max-symmetrized costs so that its symmetric spanner is valid. Its reported figures are compression to "1.6% of the original size" with navigation time "increased by at most 8%" on uHumans2. Those numbers are for symmetric costs. We found no reported result on Lacuna for D-Lite or any spanner under asymmetric navigation costs. We will therefore rerun D-Lite ourselves on the same graphs, with the same terminal sets and the same edge budgets. Beating it means lower worst-case and mean one-way terminal stretch at equal transmitted size, or smaller size at equal stretch.

The strongest theoretical competitor is the roundtrip spanner of Dalirrooyfard and Vassilevska Williams, with $5+\epsilon$ roundtrip stretch and $\tilde O(n^{1.5})$ edges, alongside the stretch-8 construction of Chechik et al.. We will implement both, give them the same edge budget, and report their one-way stretch.

The key ablation is the plain directed greedy spanner with no reversible/one-way split. It isolates whether the hybrid treatment of one-way edges matters. A second ablation isolates the role of the κ axiom: we run the same constructor on cost fields with κ swept from 1 to unbounded.

Why not just…?

Why not just max-symmetrize and run D-Lite? This is a real threat. It is provably correct, and its stretch $t\kappa$ may be acceptable when κ is near 1. Our experiments sweep κ and report where its one-way stretch exceeds the hybrid's at equal size. If there is no such crossover for realistic κ (roughly 1.5–5 for slopes), we will report that the axiomatic insight reduces to max-symmetrization and that the theoretical question is mainly of combinatorial interest.

Why not just run the plain directed greedy spanner? It may already be as sparse as our hybrid on κ-reversible graphs. Our conjecture is that it is, and if so the contribution is the proof and the size guarantee, not a new algorithm. The ablation shows whether greedy alone wastes edges near one-way doors, where it has no guarantee at all.

Why not just use roundtrip spanners, which already restore the metric axioms? They control $d(u,v)+d(v,u)$, so the one-way bound they give is $\alpha(1+\kappa)\,d(u,v)$. That is worse than max-symmetrization, and they offer nothing for one-way edges. The equal-budget comparison measures this directly.

Proposed Experiments

We use the uHumans2 office and apartment scene graphs from D-Lite. These environments are essentially flat and symmetric, so we will inject asymmetry: synthetic slope fields with controlled κ, current or wind fields, and a varying fraction of one-way doors. We will state this limitation plainly. We report compressed size as a fraction of the original, worst-case and mean one-way stretch over terminal pairs, navigation time in the simulator, and construction time.

The first decisive check is the κ sweep. We plot one-way stretch at a fixed 2% size budget for max-symmetrized D-Lite, roundtrip spanners, directed greedy, and the hybrid. The proposal succeeds if the hybrid stays near target $t$ while max-symmetrized D-Lite degrades roughly linearly in κ.

The second check sweeps the fraction of one-way doors. The hybrid's size should grow additively in $s$, not multiplicatively.

The third check is a lower-bound experiment on interpolated directed-matching graphs. It tests whether measured greedy size tracks the conjectured $O(\kappa\, n^{1+1/k})$, which would support or refute the theory before a proof is attempted.