Minimal Particle Set Tracking with Neurosymbolic State Estimation for Robust Planning and Execution

Symbolic planners are only as reliable as the state estimates they consume, and agents increasingly obtain those estimates by querying pretrained vision-language models. Committing to the single most likely state is brittle, and existing robust alternatives infer a compact set of likely states from each observation in isolation, discarding the knowledge that acting creates. We introduce Minimal Particle Set Tracking (MPST), which maintains a weighted set of symbolic states, called particles, throughout execution by pushing them through the agent’s action model, reweighting them with calibrated perception, and keeping only the smallest set that captures a target probability mass. Our key observation is that a particle set is a constraint set, so state validity follows from reachability, correlations are preserved in the support, and a previously intractable normalizer becomes a linear sum. We prove an anytime guarantee relative to the assumed action and observation models: the probability of ever losing the true state is bounded by the expected mass discarded by pruning, a ledger the algorithm computes as it runs. Because the maintained set is minimal, valid, and weight-ordered, it feeds a conformant replanning executive directly. Experiments with two vision-language-model backbones on four visually grounded domains show that MPST matches exact filtering’s coverage at the smallest or tied-smallest support of any tested set-valued recursive filter. In closed-loop execution on the two partially observable domains it reaches task success where single-observation estimation cannot act at all, matching exact filtering’s success rate on ALF with an eighth of the belief states and a third fewer planner calls.