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

Open-vocabulary navigation requires embodied agents to manage significant perception uncertainty stemming from semantic ambiguity and model errors. However, most existing works settle for local optimal deterministic approaches, depriving complex navigation decision-making over multiple composite possibilities that are critical for globally better solutions. In this paper, we propose Probabilistic Scene Graph Navigation (PSG-Nav), which constructs a 3D Probabilistic Scene Graph that uses full semantic categorical distributions to account for perception uncertainty. To efficiently use the local distributions to compose and reason about the optimal navigation landmarks, we propose Multiverse Decision to sample multiple most likely world settings from the joint distribution, and evaluate navigation landmarks based on the compatibility between landmarks and multiverses. To mitigate false positives due to epistemic uncertainty in open-vocabulary navigation, we introduce the Evidential Experience Calibrator, which enables online lifelong adaptation by cross-validating detections against memories of past successes and failures. Extensive experiments on widely-used benchmarks MP3D, HM3D, and HSSD demonstrate that PSG-Nav establishes new state-of-the-art results, achieving Success Rates of 66.1%, 44.8%, and 67.9%, respectively. Code is available at: https://psg-nav.github.io

Robots that navigate in homes and offices often need to find objects based on open-ended instructions, such as “find the sofa” or “go to the chair.” However, their visual systems can be uncertain: for example, a sofa may look like a bed, and a detector may confidently give the wrong label. This paper introduces a navigation method that keeps track of multiple possible interpretations of what the robot sees instead of immediately choosing a single label. The robot then reasons over these possible interpretations to choose where to explore next, and it also uses past successes and mistakes to avoid stopping at objects that only look like the target. Experiments in several indoor navigation benchmarks and real-world robot tests show that this approach helps robots find target objects more reliably under visual ambiguity.