💻 computer science

Graph-Loc: Robust Graph-Based LiDAR Pose Tracking with Compact Structural Map Priors under Low Observability and Occlusion

Graph-Loc is a robust graph-based LiDAR localization framework that achieves accurate and stable pose tracking under low observability and occlusion by utilizing compact structural map priors represented as lightweight point-line graphs and employing unbalanced optimal transport with anisotropy-aware updates.

Original authors: Wentao Zhao, Yihe Niu, Zikun Chen, Rui Li, Yanbo Wang, Tianchen Deng, Jingchuan Wang

Published 2026-07-10

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Wentao Zhao, Yihe Niu, Zikun Chen, Rui Li, Yanbo Wang, Tianchen Deng, Jingchuan Wang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to navigate a robot through a giant, endless maze of identical white hallways. The robot has a laser scanner (LiDAR) that sees the walls, but the view is often blocked by people walking by, or the robot only sees a tiny slice of the maze at a time. The big problem? The robot needs a map to know where it is, but it can't carry a heavy, high-definition 3D photo album of the whole building because its memory is too small.

For a long time, the solution was to chop the map into millions of tiny, jagged pieces to make it fit, hoping the robot could match them up. But this paper, Graph-Loc, says: "Wait, chopping the map makes it messy and huge. Let's try something smarter."

The Big Idea: A Sketch Instead of a Photo

Instead of carrying a heavy, dense point-cloud map (which is like carrying a 100MB photo album), Graph-Loc uses a compact structural map. Think of this as a lightweight, hand-drawn sketch of the building's skeleton. It only keeps the essential lines and corners—the "point-line graph"—which takes up almost no space (often less than 1 MB, sometimes even just a few kilobytes!).

The paper argues that you don't need to break these long lines into tiny fragments to make them matchable. In fact, breaking them up (a method used by other systems like ERPoT) inflates the map size and makes things slower. Graph-Loc keeps the lines long and clean, trusting its brain to figure out the connections.

How It Solves the "Who's Who" Problem

When the robot scans a hallway, it sees a bunch of lines. In a boring, repetitive corridor, every line looks like every other line. If the robot just picks the closest line it sees (a "nearest-neighbor" approach), it might grab the wrong one and get lost.

Graph-Loc uses a clever trick called Unbalanced Optimal Transport.

The Analogy: Imagine you are matching two groups of people at a party. A normal method tries to pair everyone up one-by-one immediately. If someone is missing or if there's a fake person (a dynamic obstacle like a pedestrian), the whole pairing gets messed up.
Graph-Loc's Method: It looks at the whole group at once. It asks, "If I move this whole group of lines, does the pattern of connections between them make sense?" It uses a mathematical "soft" matching system that allows some lines to remain unmatched if they are blocked by a person or if the view is cut off. It doesn't force a match where there isn't one. This is the "unbalanced" part—it relaxes the rule that everyone must be paired up, which makes it super robust when parts of the map are hidden or when people are walking in front of the robot.

The "Wait and See" Strategy

Sometimes, the robot is in a situation where it can't tell which way is forward or backward (like being in a long, straight tunnel with no turns). The paper calls this "low observability." If the robot tries to guess its position here, it might drift off course.

Graph-Loc has a degeneracy-aware delayed optimization strategy.

The Analogy: Imagine you are walking in a foggy tunnel. You can feel the walls on your left and right, so you know you aren't hitting them. But you can't tell if you are walking forward or backward because the tunnel looks the same in both directions.
The Fix: Instead of guessing and potentially making a mistake, Graph-Loc says, "I'll freeze the forward/backward guess for a second." It keeps moving based on its last known speed (constant-velocity prediction) but waits. It collects evidence as it moves. Once the robot sees a turn or a unique feature (like a door or a corner), it says, "Aha! Now I know!" and releases all the stored guesses at once to correct its position. This prevents small errors from piling up into a big disaster.

What the Experiments Showed

The authors tested this on real-world data and simulations to see how well it holds up.

Real-World Tests: They used public datasets like KITTI (driving on city streets) and ERPoT (parking garages). They also tested it on MulRan, a dataset where the robot drove the same route over a month, dealing with changing lanes and traffic.
- The Result: Graph-Loc tracked the robot's position with high accuracy (often under 10 cm error on average) while using a map that was 10 to 15 times smaller than the dense maps used by other methods. Even when the map was just a simple outline from a floor plan, it worked better than systems that tried to split those outlines into tiny pieces.
Dynamic Obstacles: They tested it in places with lots of people walking around (like the DOALS dataset).
- The Result: Because Graph-Loc doesn't force matches on lines that are blocked by people, it stayed stable. Other methods often got confused by the moving people and drifted. Graph-Loc kept its cool, even when pedestrians blocked up to 20% of the view in simulations.
Simulations: In a controlled simulation (CMU-EXPLORATION) where they could control exactly how many people were blocking the view, Graph-Loc maintained stable tracking even in "heavy occlusion" scenarios where other systems failed completely.

What It's NOT (And What It Rules Out)

The paper is very clear about what this method is not doing:

It does not require the map to be updated online. It works with a fixed map that was made beforehand (offline).
It does not rely on splitting long map lines into short segments to make them easier to match. The authors explicitly argue that splitting lines makes the map bigger and more complex without solving the core problem of ambiguity.
It does not need high-level semantic labels (like knowing "that is a door" or "that is a car"). It just looks at the geometry (lines and points).

How Sure Are They?

The authors are quite confident in their results because they backed them up with numbers.

They measured the error in centimeters across multiple real-world datasets.
They ran controlled simulations where they systematically increased the number of people blocking the view to prove the system holds up under stress.
They compared their method directly against top competitors (like ALOAM, FLOAM, and ERPoT) and showed that Graph-Loc achieved lower error rates while using significantly less memory.

In short, Graph-Loc suggests that you don't need a massive, detailed 3D map to navigate a robot. A tiny, smart sketch of the building's skeleton, combined with a brain that knows how to wait for the right moment to make a guess, is enough to keep a robot on track even when the world is messy, crowded, and changing.

Technical Summary: Graph-Loc

Problem Statement

Long-term autonomous operation using LiDAR requires robust pose tracking against onboard map priors. A fundamental conflict exists in practical deployments: the onboard map must be compact for scalable storage and fast retrieval, yet sufficiently discriminative to support robust data association in environments characterized by repetitive structures, partial visibility, and frequent occlusion.

Dense point-cloud maps preserve rich geometry but become computationally expensive to store and query as coverage grows. Conversely, compact structural maps (e.g., polygon outlines, CAD layouts) offer efficient storage but often suffer from fragile data association when the environment is geometrically degenerate (e.g., long straight corridors) or heavily occluded. Existing methods relying on compact priors often resort to splitting long contours into shorter segments to increase matchability, which inflates map size and offline processing complexity. Furthermore, standard nearest-neighbor association strategies become brittle in repetitive layouts, leading to incorrect correspondences and drift.

Methodology

The authors propose Graph-Loc, a graph-based localization framework that tracks platform pose against compact structural priors represented as a lightweight point-line graph. The system operates without requiring high-level semantic annotations or online map updating.

1. Structural Graph Representation

Prior Map: The onboard map is represented as a fixed graph $\mathcal{M} = (\mathcal{V}_M, \mathcal{E}_M)$ , where nodes encode geometric features (points and lines) and edges capture local neighborhood context. This representation supports heterogeneous sources, including polygon outlines vectorized from occupancy/grid maps and CAD/floor-plan layouts.
Observation Graph: For each incoming LiDAR scan, the system extracts sparse structural features to form an observation graph $\mathcal{S}_t$ $S_{t}$ . This involves a dual-stream extraction process:
- Short Sparse Features: LOAM-style edge and planar features extracted from range discontinuities.
- Long Structural Lines: Sector-based extraction of long line features to provide stable, repeatable cues.
- Fusion & Filtering: The two streams are fused to suppress dynamic interference (e.g., pedestrians) and handle occlusion patterns (e.g., inferring soft junctions or conservatively updating endpoints).
Pose-Conditioned Retrieval: Using a constant-velocity motion prediction, the system performs LiDAR ray simulation on the prior map to retrieve a visible subgraph $\mathcal{M}_t$ . This restricts matching to plausible candidates, reducing ambiguity in repetitive layouts.

2. Unbalanced Optimal Transport (UOT) for Association

Instead of greedy nearest-neighbor matching, Graph-Loc formulates scan-to-map association as an unbalanced optimal transport problem over graph nodes. The objective function minimizes:
$\gamma^* = \arg \min_{\gamma \ge 0} \langle \gamma, C(P) \rangle + \beta \Omega_{rel}(\gamma) + \rho D_{UOT}(\gamma) + \varepsilon H(\gamma)$

Geometric Matching ( $\langle \gamma, C(P) \rangle$ ): Scores pairwise compatibility between point and line features (including cross-type point-to-line associations).
Context Coupling ( $\Omega_{rel}$ ): A second-order regularizer that enforces consistency in local neighborhood relations (e.g., distance between points, angle between lines), reducing ambiguity in repetitive structures.
Mass Relaxation ( $D_{UOT}$ ): A KL-penalized unbalanced formulation that relaxes strict mass conservation. This allows the system to tolerate missing, spurious, or fragmented features caused by occlusion without forcing them into incorrect one-to-one correspondences.
Solver: The problem is solved efficiently online using a Sinkhorn-style iterative scaling algorithm with entropic smoothing.

3. Degeneracy-Aware Delayed Optimization

To address ill-conditioned pose updates in low-observability segments (e.g., long straight corridors where lateral constraints are strong but longitudinal constraints are weak), the system employs a degeneracy-aware delayed optimization strategy:

Detection: The system analyzes the information matrix (normal equations) to identify weakly constrained motion directions via eigen-decomposition.
Masked Update: In degenerate states, updates along weak directions are suppressed (masked), and only well-constrained corrections are applied immediately.
Delayed Release: Constraints from degenerate frames are buffered. Once observability recovers (non-degenerate state), the buffered evidence is aggregated with current constraints to release a full, stable correction.

Key Contributions

Compact Structural Framework: A localization framework that represents heterogeneous priors and observations as point-line structural graphs, enabling pose tracking with sparse but geometrically meaningful priors without contour splitting.
Context-Aware Unbalanced OT: A formulation of feature association as unbalanced optimal transport with graph-context regularization. This reduces local ambiguity and prevents occluded or dynamic observations from being forced into incorrect correspondences.
Degeneracy-Aware Delayed Optimization: A strategy that separates well-constrained corrections from unreliable ones in low-observability segments, stabilizing tracking in geometrically degenerate environments.
Comprehensive Evaluation: Extensive validation on public benchmarks (KITTI, ERPoT, MulRan), controlled simulations (CMU-EXPLORATION), and real-world deployments (DOALS, indoor/outdoor robots), demonstrating competitive accuracy with KB-level priors under occlusion and scene changes.

Experimental Results

The paper evaluates Graph-Loc across four distinct settings:

Public Benchmarks (KITTI, ERPoT, MulRan): Graph-Loc achieves lower Average Trajectory Error (ATE) than state-of-the-art methods (including ALOAM, FLOAM, KISS-MCL, HDL LOC, and ERPoT) while using significantly smaller map priors (e.g., ~0.25 MB vs. ~56 MB for point clouds). Notably, on the MulRan DCC dataset (long-term repeated routes), Graph-Loc maintained stable tracking with a 0.72 MB prior, whereas baselines failed or required much larger maps.
Dynamic Occlusion (DOALS & CMU-EXPLORATION): In sequences with real pedestrian motion and controlled high-density occlusion, Graph-Loc demonstrated superior robustness. It maintained stable trajectories where baselines diverged, particularly in structurally degenerate layouts. The unbalanced OT formulation effectively handled transient returns and missing data.
Real-World Deployments:
- Indoor: Tested on a corridor-like route with sustained close-range pedestrian occlusion. Graph-Loc outperformed point-cloud and polygon baselines using a CAD prior.
- Outdoor: Tested in a parking lot with gradual scene changes (parked vehicles, obstacles). Graph-Loc achieved the lowest ATE with a compact polygon prior, demonstrating stability despite prior-observation mismatches.
Ablation Studies: Removing the unbalanced OT module caused the most significant performance degradation, confirming its role as the core robustness mechanism. The delayed optimization was critical for stability in degenerate segments, and dynamic filtering improved robustness in dynamic scenes.
Runtime: The GPU implementation achieves a mean latency of ~~24.5 ms, outperforming the ERPoT baseline (~~100 ms) due to the efficiency of the Sinkhorn solver on GPUs.

Significance

The paper claims that Graph-Loc addresses the critical trade-off between map compactness and localization robustness. By shifting from local, greedy association to global, context-aware matching via unbalanced optimal transport, the system achieves reliable tracking without the need to inflate map size through contour splitting. The degeneracy-aware delayed optimization further ensures stability in geometrically weak environments where traditional filters often drift.

The work demonstrates that compact structural priors (KB-level) derived from heterogeneous sources (occupancy maps, CAD, floor plans) are sufficient for long-term autonomous operation, provided the association mechanism is robust to occlusion and degeneracy. This makes the system suitable for "drop-in" integration into navigation stacks with strict onboard memory and retrieval constraints, particularly in structured environments like buildings, corridors, and industrial sites.