Unordered Landmark Visual Navigation

1. Introduction: Breaking Free from Sequential Video Constraints

Visual image-goal navigation serves as a foundational capability in embodied AI, allowing autonomous agents to reach target destinations using visual imagery. Historically, visual navigation frameworks have relied heavily on temporally ordered video streams, odometric priors, or auxiliary multimodal sensors such as depth cameras and LiDAR to construct spatial maps and track state transitions. While these assumptions simplify spatial tracking, they severely limit operational deployment—particularly when training or operating robots using crowd-sourced, unstructured, or pre-recorded photo collections where temporal sequence data is unavailable.

To resolve these constraints, Ren et al. introduced Unordered Landmark Visual Navigation (ULVN) (ECCV 2026 Oral & Spotlight). The paper presents a unified RGB-only framework that achieves robust closed-loop visual navigation directly from an unordered “bag of images.” Operating entirely without odometry, depth sensors, or sequential video assumptions, ULVN integrates topological graph mapping, belief propagation state estimation, and path search to systematically bound compounding mapping and tracking errors.

---

2. The Failure Modes of Unordered Visual Navigation

When sequential heuristics and multimodal sensors are stripped away from image-goal navigation, existing embodied AI pipelines encounter catastrophic degradation. Ren et al. identified three principal technical hurdles that emerge in unordered, RGB-only navigation:

• Perceptual Aliasing & False Correspondences: Without temporal continuity or active depth sensors, appearance-based retrieval struggles to distinguish visually identical or repetitive environments (such as uniform office hallways or identical doors). Raw visual similarity frequently leads to false-positive correspondences, creating spurious topological edges that corrupt the underlying spatial representation.
• Cumulative Mapping and Drift Errors: Removing sequential updates and odometric metrics eliminates the constraints needed to bound scale and viewpoint variations. As a result, small edge verification errors aggregate during graph assembly, leading to severe topological deformation, broken graph connectivity, and rapid localization drift during execution.
• Myopic Planning and Trajectory Oscillation: Purely reactive end-to-end models lacking structured memory fail to maintain dynamic long-horizon goal awareness. When operating without temporal tracking to smooth trajectory predictions, reactive policies exhibit severe action instability, repeated looping behavior, and trajectory oscillations near decision junctions.

---

3. System Architecture: The Three Pillars of ULVN

ULVN addresses these challenges through a unified system architecture that co-designs mapping, localization, and planning to constrain error accumulation across the entire navigation lifecycle.

+-----------------------------------------------------------------------------------+
|                                 ULVN ARCHITECTURE                                 |
+-----------------------------------------------------------------------------------+
|  1. RAVEL: Topological Graph Construction                                         |
|     Unordered Images -> VPR Retrieval (MegaLoc) -> Data-Calibrated Matching       |
|     -> Maximum Spanning Forest (MSF) -> Strong-Loop Reinsertion                   |
+-----------------------------------------------------------------------------------+
                                         |
                                         v
+-----------------------------------------------------------------------------------+
|  2. BPL: Belief Propagation Localization                                          |
|     2D Transition Matrix (Multi-Hop K=3) + Observation Likelihood                  |
|     -> Entropy-Adaptive Fusion (wp = 1 - Hn, wo = Hn) -> MAP State Estimation     |
+-----------------------------------------------------------------------------------+
                                         |
                                         v
+-----------------------------------------------------------------------------------+
|  3. BASS: Belief-Aware Subgoal Search                                             |
|     Widest Path Search (Max-Min Confidence Dijkstra) -> Local Planner Execution   |
|     -> Dynamic Replanning on Deviation Threshold (D_thres = 3)                    |
+-----------------------------------------------------------------------------------+

3.1 Topological Graph Construction (RAVEL)

The RAVEL (Robust Augmentation and VErification of Landmarks) module transforms an unstructured set of images $L = \{I_i\}_{i=1}^N$ into a weighted, directed visual graph $\mathbf{G} = (V, E, \mathbf{W})$. To bypass exhaustive pairwise matching across large collections, RAVEL pairs global retrieval with data-calibrated local feature verification:

1. Global Retrieval and Indexing: $L_2$-normalized global descriptors $\mathbf{z}_i = f(I_i)$ are extracted using an image encoder. While general-purpose backbones (e.g., ResNet, DINOv2) or temporal distance proxies (e.g., ViNT) exhibit weak, non-linear correlations with geometric overlap ($r$), Visual Place Recognition (VPR) representations trained explicitly for place matching (such as MegaLoc) demonstrate a tight linear correlation with true geometric inlier counts. Descriptors are indexed using FAISS to enable rapid candidate retrieval.
2. Data-Driven Calibration: RAVEL automatically calibrates local verification parameters via a one-shot step. It selects an initial query image $q_0$ and identifies its farthest valid retrieved candidate neighbor: $q_f = \arg\max_{j \in \mathcal{N}_{\text{FAISS}}(q_0)} \|\mathbf{z}_{q_0} - \mathbf{z}_j\|_2$ explicitly filtering out invalid index entries. For each anchor $q \in \{q_0, q_f\}$, RAVEL performs local feature matching across candidate pairs to gather inlier counts $c_{qj}$ and descriptor distances $d_{qj}$. Applying $k$-means clustering ($k=2$) to pooled inlier counts separates pairs into a high-confidence cluster $S_h$ and a lower-confidence cluster $S_l$. The dynamic inlier threshold $\tau$ and global distance threshold $d_{\text{VPR}}$ are derived as: $\tau = \frac{1}{2}\left(\min(S_h) + \max(S_l)\right), \quad d_{\text{VPR}} = \max_{(q,j) \in S_h} \|\mathbf{z}_q - \mathbf{z}_j\|_2$ If the cluster $S_h$ is invalid, RAVEL defaults to conservative fallback parameters: $\tau_{\text{default}} = 15$ inliers and $d_{\text{VPR,default}} = 1.7$.
3. Local Geometric Verification: For candidate pairs where descriptor distance $s_{ij} \le d_{\text{VPR}}$, a deep local matcher (LightGlue) computes feature inliers $c_{ij}$. Edges are formed in the adjacency matrix with weight $W_{ij} = c_{ij}$ whenever $c_{ij} > \tau$.
4. Maximum Spanning Forest (MSF) Skeleton: Raw candidate graphs built from unordered collections contain weak, redundant edges that cause probability diffusion during localization. RAVEL computes a Maximum Spanning Forest $F = (V, E_{\text{MSF}})$ using Kruskal’s algorithm, maximizing $\sum_{(i,j) \in E_{\text{MSF}}} W_{ij}$ to preserve the strongest geometric transitions as the core backbone. Ablation experiments reveal that omitting the MSF causes Recall to drop sharply from 76.56% to 42.20% due to local edge fragmentation, proving that global structural optimization is essential for graph coherence.
5. Strong-Loop Reinsertion: Extracting an MSF destroys cyclic structures required for topological loop closure and dynamic re-routing. RAVEL applies $k$-means clustering ($k=10$) to all edge weights in $\mathbf{G}$, establishing a dynamic threshold $\tau_{\text{add}}$ set to the minimum weight of the top two centroid clusters (bounded by default as $\tau_{\text{add}} = 1.5\tau$). Edges satisfying $W_{ij} > \tau_{\text{add}}$ are reinserted into $\mathbf{G}_{\text{pruned}}$, balancing structural rigidity with topological redundancy.

3.2 Graph-Based Belief Propagation Localization (BPL)

The BPL filter extends classical Bayesian 1D sequential localization filters to operate on general 2D branching graphs containing loops and junctions without odometric sensors.

• Topological Prediction: Using the binary adjacency matrix $\mathbf{A}$ of $\mathbf{G}_{\text{pruned}}$, BPL constructs a cumulative multi-hop reachability matrix $\mathbf{C} = \sum_{m=0}^K \mathbf{A}^m$ (with propagation depth $K=3$ and $\mathbf{A}^0 = \mathbf{I}$). Row-normalizing $\mathbf{C}$ yields a stochastic transition matrix $\mathbf{T}$. Prior belief is propagated across 2D spatial pathways as $\bar{\mathbf{b}}_t = \mathbf{b}_{t-1} \mathbf{T}$.
• Entropy-Adaptive Fusion: Given live visual observation likelihood $L(v_i | I_t) = \exp(-\lambda \|\mathbf{z}_t - \mathbf{z}_i\|_2^2)$ (where $\lambda = 5$ in theoretical formulations and scaled to $\lambda = 10$ during implementation), BPL quantifies tracking uncertainty using the normalized Shannon entropy $H_n$ of the prior belief state: $H_n(\mathbf{b}_{t-1}) = -\frac{1}{\log |V|} \sum_{v_i \in V} \mathbf{b}_{t-1}(v_i) \log \mathbf{b}_{t-1}(v_i)$ Fusion weights are dynamically assigned as prediction weight $w_p = 1 - H_n(\mathbf{b}_{t-1})$ and observation weight $w_o = H_n(\mathbf{b}_{t-1})$, guaranteeing $w_p + w_o = 1$. When the prior belief state $\mathbf{b}_{t-1}$ is clear and confident (low entropy $H_n$), $w_p$ dominates, causing the filter to rely primarily on topological prediction $\bar{\mathbf{b}}_t$. Conversely, when prior tracking becomes diffuse or uncertain (high entropy $H_n$), $w_o$ increases, forcing the filter to weight incoming visual evidence $L(v_i | I_t)$ more heavily to re-anchor state estimation. Posterior belief is computed via a normalized weighted geometric mean: $\mathbf{b}_t(v_i) \propto \bar{\mathbf{b}}_t(v_i)^{w_p} \cdot L(v_i | I_t)^{w_o}$ The agent estimates its global location via Maximum A Posteriori (MAP) node selection $\hat{v}_t = \arg\max_{v_i} \mathbf{b}_t(v_i)$. Disabling this entropy-adaptive fusion mechanism degrades localization accuracy from 95.49% to 90.57%.

3.3 Belief-Aware Subgoal Search (BASS)

Given start node $v_s = \arg\max_{v_i} \mathbf{b}_0(v_i)$ and target goal node $v_g = \arg\max_{v_i} (\mathbf{z}_g^\top \mathbf{z}_i)$, BASS executes closed-loop navigation through visual subgoals.

• Topological Planning: The path confidence $\text{conf}(P)$ of a route $P$ on $\mathbf{G}$ is defined by its weakest visual link: $\text{conf}(P) = \min_{(v_i, v_j) \in P} W_{ij}$. BASS computes the optimal route $P^*$ using Dijkstra’s algorithm applied to a max-min confidence objective: $P^* = \arg\max_P \left( \min_{(v_i, v_j) \in P} W_{ij} \right)$ This selects the “widest path” possessing maximum visual overlap between consecutive nodes.
• Closed-Loop Execution and Dynamic Replanning: Subgoals along $P^*$ are passed sequentially to an un-retrained local visual policy (such as ViNT or NoMaD) to command robot movements. BPL continuously updates $\mathbf{b}_t$. If the estimated MAP node $\hat{v}_t$ leaves $P^*$, or if the topological graph distance from $\hat{v}_t$ to the active subgoal exceeds $D_{\text{thres}} = 3$, BASS automatically triggers dynamic replanning from $\hat{v}_t$ to $v_g$. Navigation is officially completed when posterior belief converges on the goal node with a probability exceeding 0.5 ($\mathbf{b}_t(v_g) > 0.5$).

---

4. Experimental Results and Empirical Benchmarks

Ren et al. evaluated ULVN across simulated environments (GRScenes in NVIDIA Isaac Sim, CARLA) and physical deployments on mobile hardware.

Ground-Truth Connectivity Pipeline

To establish ground-truth connectivity for topological mapping benchmarks, the authors developed an automated in-simulation pipeline within GRScenes. The pipeline exports 3D scene occupancy and converts it into a 2D traversability grid based on the physical dimensions of the robot. Applying Euclidean Signed Distance Field (ESDF) skeletonization and non-maximum suppression extracts a clean topological skeleton of the traversable space. Uniformly sampling nodes along this skeletal structure provides an objective spatial ground truth against which precision, recall, and edge connectivity are measured.

Topological Mapping Comparison

Table 1 compares RAVEL’s graph construction performance across 10 scenes in GRScenes against baseline representations, while Table 2 details structural ablation metrics.

Table 1: Graph Construction Baselines on GRScenes	Precision ($P$)	Recall ($R$)	F1-score ($F_1$)	Accuracy ($Acc.$)
VGGT	0.1599	0.1659	0.1629	0.9931
PlaceNav (Top 2)	0.5262	0.7113	0.6043	0.9948
PlaceNav (Top 5)	0.2699	0.7655	0.3731	0.9853
ViNT (Top 2)	0.5201	0.6775	0.5815	0.9946
ViNT (Top 5)	0.2660	0.8246	0.3806	0.9816
RAVEL (ULVN)	0.7104	0.7656	0.7365	0.9970

Table 2: RAVEL Structural Ablation Study	Precision ($P$)	Recall ($R$)	F1-score ($F_1$)	Accuracy ($Acc.$)
Top-$k$ ANN	0.1245	0.9121	0.2156	0.9584
RAVEL w/o (MSF, AVP $\tau$)	0.3676	0.7177	0.4496	0.9898
RAVEL w/o MSF	0.6910	0.4220	0.5157	0.9956
RAVEL (Full Pipeline)	0.7104	0.7656	0.7365	0.9970

Resilience to Environmental Perturbations

To evaluate mapping stability under sensor noise, the authors introduced a +noise benchmark incorporating random brightness scaling ($[0.75, 1.25]$), color jitter ($\pm 5\%$), low-light Gaussian noise ($\sigma \in [3, 10]$), and directional motion blur (kernel sizes $3$–$11$). As detailed in Table 3, appearance-based retrieval methods experience severe degradation under visual perturbations, whereas RAVEL maintains structural integrity with minimal loss in accuracy.

Table 3: Mapping Robustness Under Visual Perturbations	Precision	Recall	F1-score	Accuracy
RAVEL + noise	0.6703 (-5.64%)	0.7072 (-7.63%)	0.6882 (-6.56%)	0.9963 (-0.07%)
CosPlace Top 2 + noise	0.4592 (-12.73%)	0.6615 (-7.00%)	0.5420 (-10.29%)	0.9936 (-0.12%)
CosPlace Top 5 + noise	0.2192 (-18.78%)	0.7739 (+1.10%)	0.3416 (-8.44%)	0.9826 (-0.27%)
ViNT Top 2 + noise	0.4197 (-19.30%)	0.6064 (-10.49%)	0.4961 (-15.70%)	0.9913 (-0.33%)
ViNT Top 5 + noise	0.2065 (-22.36%)	0.7976 (-3.27%)	0.3281 (-18.43%)	0.9769 (-0.48%)

Localization Accuracy and Perceptual Degradation

Across continuous trajectories in GRScenes, BPL achieved 95.49% overall MAP localization accuracy (932/976 successful nodes). On the “Difficult Path” benchmark (routes characterized by sharp turns and low start-to-goal visual overlap), BPL retained 93.99% accuracy, outperforming MegaLoc (89.03%), ViNT (70.50%), and JIST (82.25%).

When evaluated across four physical robot datasets (RECON, SCAND, GoStanford, SACSoN) under viewpoint rotation, Gaussian noise, Poisson noise, and random cropping, BPL maintained an average localization accuracy of 0.930 ± 0.040. Table 4 details BPL’s state estimation performance across multi-hop propagation settings ($K$).

Table 4: BPL Hop-Depth and Fusion Ablation	$K=1$	$K=2$	$K=3$ (Default)	$K=4$	$K=5$	Without Adaptive Fusion
Localization Accuracy (%)	95.49	94.47	93.65	92.42	92.73	90.57

Closed-Loop Navigation and Policy Dynamics

ULVN was combined with un-retrained visual action policies (ViNT, NoMaD) and evaluated against end-to-end and reactive baselines on GRScenes (Table 5).

Table 5: Closed-Loop Navigation Benchmarks	Success Rate (SR)	Avg. Collisions	Avg. SPL
Uni-Navid (End-to-End)	32.0%	1.96	0.2391
UniGoal	61.6%	0.88	0.3176
ULVN + ViNT-A (No temporal loss)	31.0%	1.13	0.8120
ULVN + NoMaD-A (No temporal loss)	54.3%	0.94	0.7458
ULVN + ViNT w. $d_{\text{temp}}$ (Temporal localization)	59.6%	0.88	0.7752
ULVN + ViNT (Full Framework)	68.1%	0.76	0.8398
ULVN + NoMaD (Full Framework)	71.9%	0.42	0.7978

Analyzing local planner training dynamics reveals a critical distinction between training signals and execution filters. Removing temporal distance loss during training (-A variants) severely degrades local action policies (dropping ViNT success from 68.1% to 31.0%), proving that temporal distance serves as a vital auxiliary training loss. However, replacing BPL state estimation with temporal distance during execution (ULVN + ViNT w. dtemp) causes Success Rate to drop from 68.1% to 59.6%. This demonstrates that while pairwise temporal proxies aid local action execution, global tracking requires true topological belief filtering.

Real-World Deployment

To evaluate sim-to-real transfer, ULVN was deployed on a Diablo wheeled robot equipped with an Azure Kinect RGB camera and an NVIDIA Jetson Orin compute module. During physical trials, mechanical disturbances and wheel slip caused the robot to drift off its planned path. BPL detected tracking divergence as belief shifted toward off-path nodes. Upon exceeding the deviation threshold ($D_{\text{thres}} = 3$), BASS initiated dynamic replanning, re-routing the robot to its target destination without odometry or manual intervention.

---

5. Key Takeaways & Future Directions

1. Elimination of Temporal and Multimodal Dependencies: ULVN demonstrates that structured visual navigation does not require ordered video streams, depth sensors, or odometry. Robust topological maps can be assembled from unstructured image collections using data-calibrated geometric verification.
2. Global Coherence via Spanning Forests and Loop Reinsertion: Combining Maximum Spanning Forest skeletonization with dynamic threshold loop reinsertion eliminates false edges while preserving cyclic paths necessary for dynamic re-routing. Omitting MSF filtering causes recall to collapse from 76.56% to 42.20%.
3. Entropy-Adaptive State Tracking on 2D Graphs: Extending 1D temporal tracking to multi-hop 2D graph propagation enables global state estimation across complex topologies. Dynamic entropy weighting balances prediction and observation, preventing tracking divergence under visual ambiguity.
4. Lightweight Topological Memory Over Pure Reactivity: Incorporating structured graph memory and widest-path search overcomes the trajectory oscillations and local minima inherent in purely reactive end-to-end models, achieving a 71.9% navigation success rate on complex benchmarks.

Read the full paper on arXiv · PDF