Technical Summary: PSG-Nav: Probabilistic Scene Graph Navigation via Multiverse Decision Making

Problem Definition

Open-vocabulary navigation in complex, unknown environments requires embodied agents to navigate using free-form text goals (e.g., "find a blue sofa"). A critical challenge in this domain is perception uncertainty, stemming from the semantic ambiguity of physical objects and errors in perception models. Existing approaches often rely on deterministic representations, where noisy perceptual outputs are treated as absolute facts and mapped to single fixed labels (e.g., labeling an object strictly as "bed" or "sofa"). This approach discards the full semantic distribution, leading to:

1. Illogical Layouts: Inaccurate maps where objects are placed in semantically inconsistent contexts (e.g., a bed in a living room).
2. Overconfident Decisions: Agents make irreversible decisions based on noisy data, causing false positives where the agent terminates an episode prematurely near an incorrect goal.
3. Domain Shift Failures: Frequent misidentifications due to the gap between real-world pre-training and simulated environments.

The paper argues that managing this uncertainty is critical for task success, as treating noisy outputs as facts leads to information loss and unreliable paths.

Methodology

The authors propose PSG-Nav, a unified framework designed to navigate robustly under semantic ambiguity. The system consists of three core components:

1. 3D Probabilistic Scene Graph (3D-PSG)

Unlike traditional scene graphs that assign hard labels, the 3D-PSG maintains a full categorical distribution for every object node.

• Hierarchical Structure: The graph is organized into three tiers: Object nodes, Group nodes (clusters of spatially proximal objects), and Room nodes.
• Probabilistic Representation: Each object node $o_i$ maintains a belief distribution $P(o_i = c_k)$ updated via a "vote" accumulation strategy (counting detection votes over time) rather than unstable Bayesian updates with Dirichlet priors.
• Hierarchical Factorization: To avoid the combinatorial explosion of a global joint distribution, uncertainty is factorized hierarchically. Group nodes compute joint probabilities of their constituent objects, and Room nodes aggregate group distributions.
• Logical Pruning: During construction, the system enumerates potential semantic combinations and uses a Large Language Model (LLM) as a logical filter to prune configurations with semantic conflicts (e.g., a toilet in a living room), ensuring global semantic coherence.

2. Multiverse Decision Framework

To operationalize the probabilistic graph for planning, the framework samples a set of discrete, deterministic "worlds" from the 3D-PSG's joint distribution.

• World Sampling: The system generates $K$ distinct world instantiations ($G^{(1)} \dots G^{(K)}$), each representing a logically consistent interpretation of the environment.
• Intrinsic Uncertainty-Aware Exploration: The agent evaluates candidate landmarks (derived from Generalized Voronoi Graphs and frontiers) based on two metrics:
  • Spatial Information Gain ($I_{spa}$): The expected coverage of unknown space.
  • Semantic Disambiguation Potential ($I_{sem}$): The expected reduction in semantic entropy (Shannon entropy) of nearby objects.
• Stochastic Pairwise Comparison: Instead of ranking landmarks on a single noisy map, the agent performs $M$ rounds of evaluation. In each round, a world is sampled, and the LLM acts as a preference oracle to compare pairs of landmarks based on their likelihood of leading to the goal within that specific world.
• Decision Aggregation: The final preference score is derived by marginalizing pairwise wins across the entire multiverse, ensuring the selected path is robust to perceptual noise.

3. Evidential Experience Calibrator (EEC)

To mitigate false positives caused by epistemic uncertainty, the EEC acts as a Retrieval-Augmented Generation (RAG) based verification module.

• Probabilistic Context Memory: The system maintains two memory banks: a Positive Bank ($B^+$) of successful goal detections and a Negative Bank ($B^-$) of historical false positives. Entries include visual embeddings and structural context (room and group semantic distributions).
• Confidence Calibration: When a candidate object is detected, the EEC retrieves similar contexts from both banks. It computes a calibration margin based on the similarity to successful vs. failure cases.
• Dynamic Adjustment: The raw detection score is adjusted by this margin. The agent only terminates the episode if the calibrated score exceeds a validation threshold, effectively suppressing detections that resemble known error modes.

Key Contributions

1. 3D Probabilistic Scene Graph: A hierarchical representation that preserves full semantic distributions across object, group, and room levels, preventing the irreversible information loss associated with deterministic labeling.
2. Multiverse Decision Making: A novel planning strategy that samples multiple plausible world settings to evaluate navigation landmarks, allowing the agent to marginalize out perceptual noise and make stable decisions.
3. Evidential Experience Calibrator: An online, lifelong learning module that cross-validates detections against a memory of past successes and failures to dynamically calibrate confidence and prevent premature termination.
4. State-of-the-Art Performance: The framework establishes new benchmarks on standard datasets while demonstrating practical deployability on physical robots.

Experimental Results

The authors evaluated PSG-Nav on three widely used benchmarks: MP3D, HM3D, and HSSD.

• Success Rates (SR):
  • HM3D: 66.1% (PSG-Nav) vs. 65.4% (ASCENT, the previous SOTA).
  • MP3D: 44.8% (PSG-Nav) vs. 44.5% (ASCENT).
  • HSSD: 67.9% (PSG-Nav).
• Zero-Shot Performance: The variant without the EEC (strict zero-shot) still achieved 63.5% SR on HM3D, outperforming methods like BeliefMapNav (61.4%) and ApexNav (59.6%).
• Ablation Studies:
  • Removing the 3D-PSG (reverting to deterministic labels) caused a significant drop in performance (e.g., -9.4% SR on HSSD).
  • Removing the Group-level hierarchy rendered the joint probability of global configurations negligible, making world sampling intractable.
  • The EEC was shown to intercept 76.9% of false-positive stops in a specific failure-mode subset, recovering 30.3% of previously failed episodes.
• Real-World Deployment: The system was successfully deployed on a physical robot (Agilex SCOUT MINI) in indoor environments, where it correctly rejected a visually similar sofa as a chair target and continued exploration to find the true goal.

Significance and Claims

The paper claims that PSG-Nav addresses the "deterministic collapse" in open-vocabulary navigation by explicitly modeling environments as probabilistic structures. By preserving full semantic distributions and utilizing historical experience for calibration, the framework enables more reliable decision-making in complex environments.

The authors position their work as a step toward trustworthy and capable autonomous agents that can handle the inherent uncertainty of the physical world. They note that while their approach significantly improves robustness, it currently relies on 2D occupancy maps, limiting its ability to handle vertical navigation (stairs, multi-floor topologies) explicitly. Future work is proposed to extend the framework to volumetric planning and hierarchical floor-level scene graphs.