Robust Task-Aware State Estimation from Pre-trained Perception

Agents that perform state estimation using pretrained perception models, e.g., Vision-Language Models (VLMs), face the fundamental challenge that predictions are uncertain. Still, most approaches determinize these predictions into a single best-guess state and make decisions as if it were ground truth. This is brittle because when the guess is wrong, the agent's decisions may be unsafe or infeasible. At the other extreme, maintaining a full distribution over symbolic states is often intractable. We propose a middle path, drawing on the underlying probabilities the perception model already produces (e.g., a VLM's output-layer token distributions) to construct a θ-confidence Minimal Belief Set (MBSθ), a minimal subset of states whose cumulative probability meets a user-defined threshold. The minimality of an MBSθ ensures that the agent considers only the most likely states, enhancing robustness in downstream decision-making while maintaining computational tractability. Using a novel three-layered belief system, we efficiently approximate individual state probabilities from per-feature predictions and task-level constraints, on which we base our MBSθ construction, while maintaining only a lean factored representation of the belief. Our algorithm, PRaVaSS, takes advantage of the unique structure of this belief system to construct an MBSθ with correctness guarantees and polynomial complexity. Using a VLM as the backbone of our state estimator, we validate our method's theoretical properties, scalability with problem size, and improvement of downstream decision-making when used in a task planning pipeline.