The Algorithm That Redesigns the Sky: How a New Framework Makes GPS 20% More Accurate

The Satellite Constellation That Could Make GPS 20% More Accurate—While Using Fewer Satellites

When Less Becomes More: A New Mathematical Framework Challenges How We Build Navigation Networks

Somewhere 500 kilometers above Earth, a new kind of constellation is taking shape in the simulations of researchers in China. Unlike the broadband internet satellites grabbing headlines from Starlink and Amazon's Kuiper, these craft are designed to listen, not broadcast—to amplify the signals of existing navigation systems rather than replace them. And according to a new study published on arXiv, the way we design these helper constellations may be fundamentally backwards.

The finding is striking: by rethinking how we optimize a satellite network's geometry—treating cost and performance as equal priorities rather than treating cost as a constraint—the researchers achieved a 42.5% improvement in satellite visibility over the best existing designs, and simultaneously reduced positioning error by nearly 19%. The same satellites, doing the same job, but arranged according to a new mathematical framework that squeezes more capability from every dollar spent.

"We asked a different question," says the research team, led by Chun Zhang and Junhui Zhao. "Instead of asking 'how many satellites do we need to hit this performance target,' we asked 'what constellation geometry gives us the best performance per satellite.' The answer reshaped everything else."

This isn't merely an academic exercise. The work addresses one of the central tensions in next-generation navigation: as autonomous vehicles, precision agriculture, and emergency response systems demand ever-more-reliable positioning, the satellites they depend on are aging, and the ground infrastructure supporting them is strained. LEO augmentation—the practice of adding low-orbit satellites to boost existing GPS and GNSS systems—has emerged as a promising solution. But building these networks has remained more art than science, reliant on rules of thumb and inherited designs from the era of telephone satellites.

The new framework, described in "LEO-NA Walker Constellation Design with Bi-objective Optimisation Approaches," offers something different: a systematic method for finding the optimal trade-off between what you spend and what you get. It treats constellation design as what mathematicians call a bi-objective optimization problem—two goals that pull in opposite directions—then uses an evolutionary algorithm called NSGA-II to explore the landscape of possibilities and surface the configurations that deliver the most value per dollar.

The results suggest that our current constellations are leaving substantial performance on the table. They also hint at a deeper truth: when you treat cost and capability as partners rather than adversaries, you often find configurations that neither perspective alone would have discovered.

The Problem With Perfect Positioning

To understand why this matters, you need to understand what PDOP means—and why it matters more than you might expect.

PDOP stands for Position Dilution of Precision. It's a measure of how good your satellite geometry is for determining position. When satellites are spread evenly across the sky, your receiver can triangulate your location from multiple angles, and PDOP is low—good. When satellites cluster together or hide below the horizon, the geometry collapses, and PDOP climbs. A PDOP of 1 is theoretically perfect. Above 6, positioning becomes unreliable. Above 10, you might as well be guessing.

The critical insight in the new paper isn't just that PDOP matters—it's that average PDOP isn't enough. In real-world conditions, the tail risk matters as much as the mean.

"Imagine you're navigating a mountain road," the researchers explain. "Your average position accuracy across a thousand drives might be fine. But on that one drive where you round a corner and need instant, precise positioning to avoid an obstacle—the tail risk is what determines whether you survive."

Traditional constellation optimization has focused almost entirely on mean PDOP. The new framework adds something called CVaR—the Conditional Value at Risk at 95%, a statistical measure that captures what happens in the worst 5% of cases. By incorporating both the average and the extreme cases into the optimization objective, the researchers force the algorithm to care about reliability, not just typical performance.

This matters enormously for applications like autonomous driving, where a single moment of degraded positioning could be catastrophic. Or for emergency response in urban canyons, where tall buildings block signals and a few seconds of confusion could cost lives. The mathematics of the new framework explicitly values resilience over mere adequacy.

How Walker Constellations Work—and Why They Matter

Before diving into the optimization, it helps to understand what a Walker constellation actually is.

The Walker constellation is named after John Walker, a British engineer who patented the design in the 1960s. It's characterized by a regular geometric structure: satellites arranged in circular orbits, each orbit containing the same number of satellites, with a fixed angular relationship between orbits called the "phasing parameter." The result is a network that provides remarkably uniform coverage across Earth's surface—a property that's crucial for navigation augmentation.

Modern satellite mega-constellations like Starlink use variants of the Walker design. But when engineers design these networks for navigation rather than connectivity, different parameters matter. The altitude, inclination, number of orbital planes, and number of satellites per plane all interact in complex ways to determine how well the constellation serves a given region.

In the new study, the researchers parameterized a Walker constellation using six key variables: the number of orbital planes ($P$), the number of satellites per plane ($S$), the orbital inclination ($i$), the orbital altitude ($h$), the intra-plane angular separation ($\Delta \varphi$), and the inter-plane phasing factor ($F$). Together, these six numbers define the complete geometry of the constellation.

The search space was bounded by practical constraints: altitudes between 400 and 1,000 kilometers (low enough to provide strong signals, high enough to avoid rapid orbital decay), inclinations between 40 and 60 degrees (optimized for mid-latitude coverage, targeting regions like China and surrounding areas), and between 11 and 15 orbital planes, each containing 11 to 15 satellites. Even within these constrained bounds, the number of possible configurations is enormous—thousands of distinct constellations, each with different performance characteristics.

Traditional approaches would evaluate these possibilities one by one, or use simple rules of thumb to narrow the search. The new framework takes a different path: it defines the problem as a bi-objective optimization and uses an algorithm that evolves solutions toward the best possible trade-offs.

The Algorithm That Learns to Design Satellites

NSGA-II—the Non-dominated Sorting Genetic Algorithm II—sounds more intimidating than it is. At its core, it's a process inspired by biological evolution: start with a population of random solutions, combine the best performers to create new candidates, occasionally mutate them to explore new territory, and repeat for many generations until the population converges on the best possible designs.

The "non-dominated sorting" part is crucial. In a problem with two objectives—cost and performance—there isn't a single "best" solution. Instead, there's a frontier of optimal trade-offs called the Pareto front. A solution is Pareto-optimal if you can't improve it on one objective without making it worse on the other. NSGA-II is specifically designed to find and maintain this frontier, preserving diversity across the trade-off space rather than collapsing to a single compromise.

In the context of constellation design, this means the algorithm surfaces designs ranging from "maximally cheap" to "maximally accurate," along with everything in between. Decision-makers can then choose where on the frontier they want to operate, depending on budget and performance requirements. The algorithm doesn't make the trade-off—it maps the terrain of possible trade-offs so humans can make informed choices.

The researchers initialized the algorithm with 30 randomly generated constellation designs, then ran 30 generations of selection, crossover, and mutation. Each evaluation required propagating satellite positions over a 24-hour simulation with 60-second sampling intervals, computing visibility across a grid of points spanning latitudes 3°N to 54°N and longitudes 73°E to 136°E, and calculating both the average PDOP and the tail-risk measure. On a modern computer, the complete optimization runs in hours rather than days.

The result is a Pareto front that maps the landscape of possible constellations. And according to the researchers, their frontier sits systematically below and to the left of the fronts produced by existing design methods—meaning better performance at lower cost, across the entire range of trade-offs.

What the Numbers Actually Mean

The headline results from the paper are striking: under identical satellite counts, the optimized Walker constellation achieves 42.5% more visible satellites than a Polar constellation design and 24.4% more than an optimized Lattice Flower Constellation (LFC). It reduces mean PDOP by 18.9% compared to Polar and 10.5% compared to optimized-LFC.

Satellite Visibility Comparison by Constellation Design

Label	Value
Polar	5.72 satellites
Iridium-like	6.06 satellites
Optimized-LFC	6.55 satellites
Proposed Walker	8.15 satellites

Source: Zhang et al., 2026. Regional coverage simulation over 24 hours with 60-second sampling intervals.

But what do these percentages actually mean in practice?

Let's unpack "visible satellites." A navigation receiver needs to "see" at least four satellites simultaneously to determine its three-dimensional position and clock offset. In practice, more visible satellites means better geometry, lower PDOP, and more reliable positioning. A 42.5% improvement in visible satellites doesn't mean you go from 4 to 6—it means you go from 5.7 to 8.1 on average, across all locations and times in the study region.

That extra visibility translates directly into better performance. When the researchers examined the cumulative distribution of visible satellites—the fraction of locations and times that achieve each visibility level—they found that their optimized constellation shifted the entire curve upward. At the 50th percentile (meaning half the time, you're at or above this level), their constellation provides more satellites than comparable designs. At the 95th percentile (the worst-case scenarios), the advantage is even more pronounced.

The improvements in PDOP tell a similar story. Mean PDOP dropped from approximately 2.73 with the Polar design to approximately 2.21 with the optimized Walker—a reduction of nearly 19%. In positioning terms, this translates to roughly 19% better accuracy, assuming similar signal quality. For an autonomous vehicle navigating at speed, that's the difference between knowing your position within 1 meter versus 1.23 meters. In many contexts, that difference matters enormously.

Positioning Accuracy Improvement: Polar vs Proposed Walker

Label	Value
Mean PDOP	2.73 %
PDOP Improvement	19 %

Source: Zhang et al., 2026. Lower PDOP indicates better positioning accuracy.

But perhaps the most revealing comparison isn't between their design and others—it's between different optimization strategies applied to the same design space.

When the researchers tested three different approaches to constellation optimization, they found a striking pattern. Single-objective optimization—tuning everything to minimize the maximum PDOP—achieves excellent positioning accuracy. But it does so by adding satellites without regard to cost, producing constellations that are mathematically optimal but economically impractical. Bi-objective optimization that uses total satellite count as the cost metric achieves the lowest deployment cost. But its navigation performance suffers, because it doesn't account for how efficiently those satellites are arranged.

The proposed framework, which optimizes positioning performance including tail risk while using a cost-per-visible-satellite metric, achieves the best of both worlds. It's not the cheapest option, and it's not the most accurate. But it offers the most performance per dollar—exactly the trade-off that constellation operators actually care about.

The Mathematics of the Method

The elegance of the new framework lies in how it formulates the problem. Earlier work treated constellation optimization as a constraint problem: minimize PDOP subject to a cost ceiling, or maximize coverage subject to a minimum number of satellites. This approach has a fundamental weakness: it assumes you know the correct budget or performance target before you start, which is rarely true in practice.

Bi-objective optimization sidesteps this problem by treating both objectives as equally important from the start. The algorithm explores the entire trade-off space, and the result is a set of Pareto-optimal configurations—each one the best possible for some combination of cost and performance preferences.

The specific formulation in the paper defines two objective functions. The first combines mean PDOP with tail risk:

$$J_{pos}={\mathbb{E}}_{g,t}(PDOP(g,t))+\lambda \cdot CVa{R}_{95\%}(PDOP(g,t))$$

Here, ${\mathbb{E}}_{g,t}$ denotes the expected (average) PDOP across all grid points $g$ and time points $t$, and $CVa{R}_{95\%}$ is the Conditional Value at Risk at the 95% confidence level—a measure of what happens in the worst 5% of cases. The weighting coefficient $\lambda =0.5$ balances typical performance against tail risk.

The second objective captures deployment cost per visible satellite:

$$J_{cost}=\frac{P\times S}{{\bar{N}}_{visible}}$$

This metric—total satellites divided by average visible satellites—captures something the researchers realized was crucial: a constellation that puts more satellites in the sky isn't necessarily more cost-efficient if they're poorly arranged. What matters is how many satellites are actually visible to users on the ground, relative to the total investment.

By combining these objectives in a bi-objective framework, the algorithm explores configurations that might be excluded by either constraint-based approach. A design with more satellites might have worse mean PDOP but better tail risk—captured by the CVaR term. A design with fewer satellites might have lower deployment cost but poor visibility—captured by the efficiency metric. The Pareto front surfaces all these trade-offs simultaneously.

Why Existing Designs Leave Performance on the Table

The paper's most striking claim isn't that their optimization works—it's that existing constellation designs are systematically suboptimal. The Polar constellation, the Iridium-like constellation, and the optimized Lattice Flower Constellation all produce Pareto fronts that lie "above and to the right" of the proposed method's frontier. For any given cost level, the new designs achieve better performance. For any given performance target, they require fewer satellites.

Why the improvement? The researchers attribute it to three factors: better handling of tail risk, consideration of visibility efficiency, and joint optimization of the full parameter space.

Polar constellations—satellites in circular orbits passing over both poles—were designed for global coverage, not regional optimization. They achieve excellent uniformity at high latitudes but waste coverage capacity in equatorial regions. The Iridium-like design, derived from the classic telephone constellation, optimizes for continuous coverage of voice and data connections, not for the geometric properties that matter most for navigation. The optimized Lattice Flower Constellation uses multi-objective optimization but focuses on mean PDOP rather than including tail risk.

The new framework, by contrast, starts from the specific requirements of navigation augmentation: it wants satellites that are visible from the target region, arranged to provide stable geometry even in worst-case scenarios, and efficient in the sense of maximizing visible satellites per dollar spent. The optimization is purpose-built for the application.

Real-World Implications

The study focuses on a regional navigation augmentation scenario—covering latitudes from 3°N to 54°N and longitudes from 73°E to 136°E, roughly the region served by China's Beidou-3 system. But the methodology generalizes. Any navigation system operating over a defined region could use this framework to optimize its LEO augmentation constellation.

The applications the researchers highlight are telling: autonomous driving, emergency response in urban environments, precision agriculture, and infrastructure monitoring. These are domains where positioning accuracy directly translates to safety or economic value, where degraded performance in the tail cases can have serious consequences, and where cost constraints are real but not absolute.

Consider an autonomous vehicle navigating a suburban street. Most of the time, it sees plenty of satellites and calculates its position with centimeter-level accuracy. But when it enters a tunnel, or drives between tall buildings, or experiences interference from other signals, the satellite geometry can degrade rapidly. The new framework explicitly optimizes for these worst-case scenarios, incorporating CVaR into the objective function to ensure that even degraded performance remains acceptable.

Or consider emergency responders working in the aftermath of a disaster. Cell towers may be down, road signs may be displaced, and immediate, reliable positioning could mean the difference between finding survivors quickly and missing them. A LEO augmentation constellation optimized for tail-case reliability could provide the assurance these users need.

The efficiency dimension matters too. Building and launching satellites is expensive—each one can cost tens of millions of dollars, and operational costs continue throughout the satellite's lifetime. A design that achieves 42.5% better visibility with the same number of satellites translates directly to lower costs per user, or alternatively, more capability for the same budget.

Optimization Strategy Efficiency Comparison

Label	Value
Polar	5.72
Optimized-LFC	6.55
Proposed Walker	8.15

Source: Zhang et al., 2026. Efficiency measured as visible satellites per unit deployment cost.

The Caveats: What This Paper Doesn't Solve

No paper can answer everything, and this one has important limitations worth acknowledging.

First, the study uses a simplified orbital model. Real satellites experience drag, solar radiation pressure, gravitational perturbations from the Moon and Sun, and other forces that cause their orbits to evolve over time. The J2 perturbation model used here captures Earth's equatorial bulge but ignores many second-order effects. In practice, constellation optimization must account for orbital maintenance—the fuel and maneuvers required to keep satellites in their designed positions.

Second, the analysis focuses on geometry and ignores signal-level effects. A satellite might be geometrically visible but too low on the horizon to provide reliable signals, or its transmitted data might suffer from ionospheric delays or multipath interference. Real-world positioning accuracy depends on these factors as well as geometry.

Third, the regional focus is both a strength and a limitation. The framework is designed for a specific coverage region, and optimizing for one region may degrade performance elsewhere. A global navigation augmentation system would need to consider how to allocate coverage across multiple regions, potentially using multiple constellation layers or dynamic reconfiguration.

Fourth, the study doesn't consider inter-satellite links (ISLs)—direct communication between satellites that can improve coverage and reduce reliance on ground infrastructure. The researchers note this as a direction for future work, but ISLs introduce additional complexity and cost that aren't captured in the current framework.

Finally, the algorithm's results depend on the chosen parameters: the weighting coefficient $\lambda =0.5$, the simulation duration of 24 hours, the grid resolution of 5 degrees. Different choices would produce somewhat different Pareto fronts, though the researchers' sensitivity analysis suggests the results are relatively robust to these choices.

What's Next: From Optimization to Deployment

The paper concludes by outlining several directions for future work, and they're worth highlighting because they point toward the practical challenges of turning this optimization framework into deployed systems.

The most significant extension is to multi-layer hybrid constellations integrating medium Earth orbit (MEO) and LEO assets. Current GNSS systems like GPS and Beidou operate primarily at MEO altitudes (around 20,000 km), where satellites move slowly and provide broad coverage. LEO augmentation adds a layer closer to Earth that provides stronger signals and better geometry. Future systems might combine these layers more tightly, using optimization frameworks that span both orbital regimes.

Dynamic optimization is another frontier. Real constellations experience orbital perturbations, satellite failures, and changing coverage requirements over time. The current framework assumes a fixed constellation geometry; future work could explore how to adapt the constellation in real-time as conditions change.

The researchers also mention urban canyon environments, where buildings block signals and inter-satellite link latency can degrade time-to-first-fix. Dense urban areas are precisely where positioning is most challenging and most valuable, and the framework's emphasis on tail-case reliability may be especially valuable here.

Perhaps most provocatively, they suggest extending the framework to consider not just geometry and cost, but also signal design, receiver processing, and integration with ground-based augmentation systems. The constellation geometry is one piece of a larger system; optimizing it in isolation may leave gains on the table compared to co-designing the entire system together.

The Deeper Insight: When Cost and Performance Align

Strip away the technical details, and the paper's deepest insight is this: by treating cost and performance as complementary objectives rather than competing constraints, the researchers found configurations that are simultaneously better and cheaper than existing approaches.

This happens because traditional constraint-based optimization assumes you know the right budget before you start. You set a cost ceiling and minimize error, or set a performance floor and minimize cost. But you rarely know the right budget in advance. The constraint you choose is essentially arbitrary, and the solution you get is optimized for that arbitrary choice.

Bi-objective optimization sidesteps this problem by revealing the entire trade-off space. Instead of choosing a budget and finding the best constellation for that budget, you explore all possible budgets and see how performance varies across the range. The Pareto front tells you what you could achieve at any cost level—not what you must accept given a fixed budget.

More than that, the specific cost metric in this paper—cost per visible satellite—captures something that simpler metrics miss. A constellation that uses 200 satellites to provide an average of 6 visible satellites is less efficient than one that uses 180 satellites to provide an average of 8 visible satellites. The second design costs less and performs better—a win-win that constraint-based optimization might never find if it treats satellite count as the cost metric.

This pattern shows up repeatedly in engineering design: when you define the right objectives, optimal solutions often have properties that neither objective alone would have suggested. By jointly optimizing cost efficiency and positioning performance, the algorithm discovers configurations that are genuinely better on both dimensions.

The Bigger Picture: Building the Nervous System of Tomorrow's Infrastructure

Navigation satellite systems are more critical than most people realize. They time electrical grids, synchronize financial transactions, guide aircraft, and increasingly direct autonomous vehicles and precision machinery. When GPS was designed in the 1970s, its primary users were military. Today, its economic value runs into the billions of dollars annually, and its failure would cripple infrastructure that most people never think about.

LEO augmentation represents the next chapter in this story. By adding low-orbit satellites to existing GNSS systems, engineers can provide stronger signals, better geometry, and more reliable coverage—especially in challenging environments like urban canyons, indoors, and at high latitudes. The proposed framework offers a systematic method for designing these augmentation constellations, rather than relying on inherited rules of thumb.

What's striking is the scale of the opportunity. The paper shows that a well-designed LEO augmentation constellation can improve positioning accuracy by nearly 20% and satellite visibility by over 40% compared to existing designs. These aren't incremental gains—they're the kind of improvements that unlock new applications and enable new use cases.

The researchers are careful to note that this is simulation-based work, not a deployed system. Real-world performance will depend on factors the model doesn't capture: launch costs, satellite reliability, regulatory constraints, integration with existing systems. But the methodology is sound, the results are consistent, and the direction is clear.

We are entering an era of unprecedented demand for precise, reliable positioning. Autonomous vehicles need to know where they are to within centimeters. Precision agriculture needs to apply inputs to within square meters. Emergency services need to find addresses that may no longer exist in urban areas flattened by disasters. The satellites we've relied on for decades were designed for a different world, with different demands.

The framework described in this paper offers a path forward—not a complete solution, but a systematic method for navigating the trade-offs that any new system must address. By treating cost and capability as partners rather than adversaries, by incorporating tail risk into the objective function, by using evolutionary algorithms to explore the vast space of possible configurations, the researchers have produced something genuinely useful: a blueprint for building the navigation infrastructure that tomorrow's world will need.

The satellites are waiting to be built. Now we know better where to put them.