gnss_gpu is a CUDA-backed GNSS positioning repo built around experiment-first development. The repository contains reusable core code under python/gnss_gpu/, but a large part of the current value is the evaluation stack around UrbanNav, PPC-Dataset, and real-PLATEAU subsets.
This repo is no longer in a "pick one perfect architecture first" phase. The current workflow is:
- build comparable variants under the same contract
- evaluate them on fixed splits and external checks
- freeze only the parts that survive
- keep rejected or supplemental ideas in
experiments/, not in the core API
| Main result (UrbanNav external) | Particle scaling (100 to 1M) |
|---|---|
 |
 |
| BVH runtime (57.8x speedup) | PPC holdout (design discipline) |
|---|---|
 |
 |
- PF beats RTKLIB demo5: RMS 6.81m (10K particles) vs 13.08m (48% improvement) on Odaiba
- GNSS corrections: gnssplusplus-library (Sagnac, tropo, iono, TGD, ISB)
- Cross-geography: PF wins on 5 sequences in 2 cities (Tokyo + Hong Kong)
- Scaling: phase transition at N≈1,000, tail improvement up to 1M particles
- Systems:
PF3D-BVH-10K— 57.8x runtime reduction
| Method | P50 | P95 | RMS 2D | >100 m |
|---|---|---|---|---|
| RTKLIB demo5 | 2.67 m | 32.41 m | 13.08 m | — |
| PF 10K particles | 4.32 m | 12.69 m | 6.81 m | 0.000% |
| PF 1M particles | 3.64 m | 13.15 m | 6.72 m | 0.000% |
PF 10K already beats RTKLIB demo5 by 48% in RMS and 61% in P95, with zero catastrophic failures. Scaling to 1M gives marginal additional improvement (6.81→6.72m). RTKLIB wins P50 by 36% (iterative WLS produces sharper point estimates). PF uses gnssplusplus-library for pseudorange corrections (Sagnac, troposphere, ionosphere, TGD, ISB).
PF (red) vs RTKLIB demo5 (green dashed) vs Ground truth (blue) on real Tokyo streets.
| Odaiba (moderate urban) | Shinjuku (deep urban canyon) |
|---|---|
| Download mp4 | Download mp4 |
View on GitHub Pages for inline playback.
For a longer LOS/NLOS sweep with OpenStreetMap basemap, coarse 3D PLATEAU buildings, and satellites projected onto a virtual sky ceiling, open the interactive deck.gl map or download mp4. A still preview is at los_nlos_deckgl_still.png.
PF crosses the RTKLIB demo5 baseline at N≈500 particles on Odaiba. Mean RMS saturates near N=5,000 (~7m on Odaiba, ~15m on Shinjuku), with >100m failure rate at 0% for all N≥500. GPU-scale particle inference enables a tail-robustness regime unreachable at conventional particle counts. 1M particles at 9 ms/epoch — well within 1 Hz GNSS budget.
PF family outperforms baselines across 5 sequences in 2 cities (Tokyo + Hong Kong).
Tokyo (trimble + G,E,J, gnssplusplus corrections)
| Sequence | PF RMS | Baseline RMS | Baseline | PF improvement |
|---|---|---|---|---|
| Odaiba | 6.72 m | 13.08 m | RTKLIB demo5 | 49% |
| Shinjuku | 8.51 m | 18.12 m | gnssplusplus SPP | 53% |
Hong Kong (ublox, gnssplusplus corrections, multi-GNSS nav)
| Sequence | Sats | PF RMS | SPP RMS | >100m (PF) | Note |
|---|---|---|---|---|---|
| HK-20190428 | 8 | 24.6 m | 23.7 m | 0.0% | GPS+BeiDou |
| HK TST | 20 | 317.6 m | 318.3 m | 78.5% | deep urban, NLOS dominant |
| HK Whampoa | 30 | 503.4 m | 508.7 m | 94.7% | deepest urban canyon |
HK-20190428 achieves sub-25m with multi-GNSS nav (GPS+BeiDou). TST and Whampoa have 20-30 satellites but SPP itself fails (>300m) due to dominant NLOS — pseudorange errors of hundreds of meters make single-epoch and temporal filtering approaches equally ineffective. This is a fundamental SPP limitation, not a PF limitation. These environments require RTK, carrier-phase, or 3D-map-aided NLOS exclusion to achieve usable accuracy.
BVH systems result (PPC-Dataset PLATEAU subset, separate dataset)
BVH (Bounding Volume Hierarchy) accelerates the 3D ray-tracing likelihood computation used in the PF3D variant. For each particle-satellite pair, the system traces a ray through PLATEAU 3D building models to determine LOS/NLOS visibility. Without BVH, this requires checking every triangle in the mesh (O(N×K×T) where T=triangles). BVH organizes triangles into a spatial hierarchy, reducing this to O(N×K×log(T)) through hierarchical culling. Accuracy is preserved because BVH is an exact acceleration structure (no approximation).
| Method | Runtime | Speedup |
|---|---|---|
PF3D-10K |
1028.29 ms/epoch | baseline |
PF3D-BVH-10K |
17.78 ms/epoch | 57.8x faster |
In the PF3D variant, each particle independently evaluates whether each satellite signal is LOS or NLOS by ray-tracing from the particle's position to the satellite through 3D building geometry. The per-particle likelihood is a two-component mixture:
p(pseudorange | particle, satellite) =
(1 - p_nlos) × N(residual; 0, σ_los²) [LOS component]
+ p_nlos × N(residual; bias, σ_nlos²) [NLOS component]
where p_nlos is set by the ray-trace result (high if blocked, clear_nlos_prob=0.01 if clear), σ_los is the LOS noise (~3m), σ_nlos is the NLOS noise (~30m), and bias is the NLOS positive bias (~15m). This means different particles can disagree on which satellites are blocked, naturally handling the multi-modal posterior in urban canyons. The standard PF variant (without 3D models) uses a simpler Gaussian likelihood with clear_nlos_prob to provide robustness without explicit ray-tracing.
Controlled simulation with parametric canyon (parallel buildings, ray-traced NLOS). PF advantage increases with NLOS severity.
| Canyon height | NLOS % | WLS RMS | PF RMS | PF+Map RMS | PF gain |
|---|---|---|---|---|---|
| 20 m | 33% | 40.68 m | 12.41 m | 11.45 m | 72% |
| 60 m | 83% | 51.83 m | 11.73 m | 10.09 m | 81% |
| 80 m | 91% | 51.72 m | 7.88 m | 6.47 m | 87% |
PF+Map prior (Oh et al. 2004 IROS inspired): particles inside building footprints receive near-zero weight, constraining the posterior to the street. Adds 14-18% improvement in deep canyons on top of standard PF.
- PF with proper pseudorange corrections beats RTKLIB demo5 by 49% in RMS on UrbanNav Tokyo.
- PF eliminates catastrophic failures (>100m rate = 0%) through temporal filtering.
- Particle count scaling reveals a phase transition at N≈1,000 with continued tail improvement to 1M.
- BVH makes real-PLATEAU PF3D runtime practical without changing accuracy.
- Urban canyon simulation confirms PF advantage increases with NLOS severity (87% gain at 91% NLOS).
- Map prior (Oh et al. 2004) adds 14-18% improvement by constraining particles to road network.
- 24 cited references, gnssplusplus-library as submodule for GNSS corrections.
- It does not claim a world-first GNSS particle filter.
- It does not claim PF beats iterative WLS in per-epoch median accuracy (P50).
- It does not claim the same configuration works across all urban environments without tuning.
- GitHub Pages artifact snapshot:
docs/index.html - Experiment log:
internal_docs/experiments.md - Decision log:
internal_docs/decisions.md - Minimal retained interface:
internal_docs/interfaces.md - Working plan / handoff log:
internal_docs/plan.md - Paper-oriented asset outputs:
experiments/results/paper_assets/
pip install .Or build manually:
mkdir -p build
cd build
cmake .. -DCMAKE_CUDA_ARCHITECTURES=native
make -j"$(nproc)"If you build extensions manually, copy the generated .so files into python/gnss_gpu/ before running Python-side experiments.
PYTHONPATH=python python3 -m pytest tests/ -qFreeze checkpoint status:
440 passed, 7 skipped, 17 warnings
The remaining warnings are existing pytest.mark.slow, datetime.utcnow(), and plotting warnings rather than new failures.
python3 experiments/build_githubio_summary.pyThis rebuilds:
docs/assets/results_snapshot.jsondocs/assets/data/*.csvdocs/assets/figures/*.pngdocs/assets/media/los_nlos_deckgl.htmldocs/assets/media/los_nlos_deckgl.gifdocs/assets/media/los_nlos_deckgl.mp4docs/assets/media/los_nlos_deckgl_still.pngdocs/assets/media/los_nlos_deckgl.webmdocs/assets/media/site_poster.pngdocs/assets/media/site_teaser.gifdocs/assets/media/site_teaser.mp4docs/assets/media/site_teaser.webmdocs/assets/media/site_urbannav_runs.pngdocs/assets/media/site_window_wins.pngdocs/assets/media/site_hk_control.pngdocs/assets/media/site_urbannav_timeline.pngdocs/assets/media/site_error_bands.png
npm install
npx playwright install chromium
npm run site:smokeThis checks the built snapshot page on desktop and mobile Chromium, asserts that the main sections render, and fails on non-ignored browser runtime errors.
python3 experiments/build_paper_assets.pyThis rebuilds:
experiments/results/paper_assets/paper_main_table.csvexperiments/results/paper_assets/paper_main_table.mdexperiments/results/paper_assets/paper_ppc_holdout.pngexperiments/results/paper_assets/paper_urbannav_external.pngexperiments/results/paper_assets/paper_bvh_runtime.pngexperiments/results/paper_assets/paper_captions.mdexperiments/results/paper_assets/paper_particle_scaling.png
UrbanNav external evaluation (PF+RobustClear-10K with self-corrections):
PYTHONPATH=python python3 experiments/exp_urbannav_fixed_eval.py \
--data-root /tmp/UrbanNav-Tokyo \
--runs Odaiba,Shinjuku \
--systems G,E,J \
--urban-rover trimble \
--n-particles 10000 \
--methods EKF,PF-10K,PF+RobustClear-10K,WLS,WLS+QualityVeto \
--quality-veto-residual-p95-max 100 \
--quality-veto-residual-max 250 \
--quality-veto-bias-delta-max 100 \
--quality-veto-extra-sat-min 2 \
--clear-nlos-prob 0.01 \
--isolate-methods \
--results-prefix urbannav_fixed_eval_external_gej_trimble_qualityvetoMain output files:
experiments/results/urbannav_fixed_eval_external_gej_trimble_qualityveto_summary.csvexperiments/results/urbannav_fixed_eval_external_gej_trimble_qualityveto_runs.csv
python/gnss_gpu/: reusable library code, bindings, dataset adapters, and core hookssrc/: CUDA/C++ kernels and pybind-facing native implementationsexperiments/: experiment-only runners, sweeps, diagnostics, and artifact buildersdocs/: experiment log, decisions, interface notes, paper draft, and GitHub Pages sourcetests/: unit and regression tests
- Keep stable, reusable code in
python/gnss_gpu/orsrc/. - Keep variant-heavy logic in
experiments/until it survives fixed evaluation. - Do not promote a method because it wins a pilot split.
- Prefer same-input, same-metric comparisons over new abstractions.
- Record adoption and rejection reasons in
internal_docs/decisions.md.
experiments/results/paper_assets/paper_main_table.mdexperiments/results/paper_assets/paper_urbannav_external.pngexperiments/results/paper_assets/paper_bvh_runtime.pngexperiments/results/paper_assets/paper_particle_scaling.pngexperiments/results/urbannav_window_eval_external_gej_trimble_qualityveto_w500_s250_summary.csvexperiments/results/pf_strategy_lab_holdout6_r200_s200_summary.csvexperiments/results/urbannav_fixed_eval_hk20190428_gc_adaptive_summary.csv
Apache-2.0