Bridging Learned Visual Perception and Symbolic Belief-Space Planning

# Bridging Learned Visual Perception and Symbolic Belief-Space Planning via Probabilistic Grounding
Source: [https://arxiv.org/html/2609.16884](https://arxiv.org/html/2609.16884)
\\jmlrpages

Guy AzranEmail:[guy\.azran@campus\.technion\.ac\.il](mailto:[email protected])Affiliation:Taub Faculty of Computer Science, Technion \- Israel Institute of Technology and Faculty of Mathematics, Technion \- Israel Institute of Technology and Taub Faculty of Computer Science, Technion \- Israel Institute of TechnologySarah KerenEmail:[sarahk@cs\.technion\.ac\.il](mailto:[email protected])Affiliation:

###### Abstract

In partially observable settings, agents must act without full knowledge of the world state and rely on uncertain state\-estimation pipelines\. Obtaining grounded and verifiable symbolic plans under such uncertainty remains a key challenge\. Recent work has integrated[vlm](https://arxiv.org/html/2609.16884#id2)to bridge perception and symbolic reasoning, following two main paradigms\. The first,[vlm](https://arxiv.org/html/2609.16884#id2)\-as\-planner, maps images directly to action sequences, and the second,[vlm](https://arxiv.org/html/2609.16884#id2)\-as\-grounder, grounds observations into symbolic predicates used as the initial state by off\-the\-shelf planners\. Both approaches ignore uncertainty in the planning process, compromising robustness\. We introduce a third paradigm,[vlm](https://arxiv.org/html/2609.16884#id2)\-as\-probabilistic\-grounder, a novel approach that captures the uncertainty of[vlm](https://arxiv.org/html/2609.16884#id2)predicate groundings as a probability distribution over symbolic states\. This enables planning in belief space and producing robust plans under uncertainty\. Experiments in simulated household robot settings show improved robustness and task success over deterministic grounding, underscoring how our approach leverages foundation models for reliable planning under uncertainty\.

††year:2026††proceedings:: Preprint††workshop:Accepted at NeuS 2026###### keywords

planning under uncertainty, vision\-language models, robust decision\-making

## 1Introduction

\\subfigure\[“Book to shelf”\]![Refer to caption](https://arxiv.org/html/2609.16884v1/images/radio.jpg)\\subfigure\[“Bowl to sink”\]![Refer to caption](https://arxiv.org/html/2609.16884v1/images/kitchen.png)

Figure 1:Observations for two tasks in the ViPlan household benchmark\([Merler et al\., 2025](https://arxiv.org/html/2609.16884#bib.bib21)\)\.Robotic applications remain challenging due to the inherent uncertainty in perception and action outcomes\. Many traditional frameworks adopt the[cwa](https://arxiv.org/html/2609.16884#id1)\([Reiter, 1981](https://arxiv.org/html/2609.16884#bib.bib29)\), treating facts not known to be true as false, and rely on handcrafted, task\-specific solutions\([Wertheim et al\., 2024](https://arxiv.org/html/2609.16884#bib.bib33);[Moreno et al\., 2024](https://arxiv.org/html/2609.16884#bib.bib22);[Rana et al\., 2023](https://arxiv.org/html/2609.16884#bib.bib28);[Garrett et al\., 2020](https://arxiv.org/html/2609.16884#bib.bib8)\)\. Recently,[vlm](https://arxiv.org/html/2609.16884#id2)have been incorporated to infer task\-relevant information from visual observations, enabling more generalizable and flexible planning systems\([Zhang et al\., 2024](https://arxiv.org/html/2609.16884#bib.bib36);[Hu et al\., 2023](https://arxiv.org/html/2609.16884#bib.bib13)\)\.[Merler et al\. \(2025\)](https://arxiv.org/html/2609.16884#bib.bib21)distinguish between two paradigms for[vlm](https://arxiv.org/html/2609.16884#id2)\-planning integration:[vlm](https://arxiv.org/html/2609.16884#id2)\-as\-planner, where the[vlm](https://arxiv.org/html/2609.16884#id2)directly generates plans from visual inputs, and[vlm](https://arxiv.org/html/2609.16884#id2)\-as\-grounder, where the[vlm](https://arxiv.org/html/2609.16884#id2)provides symbolic predicates that an off\-the\-shelf planner uses to compute plans\. These approaches disregard the inherent uncertainty in visual grounding and treat[vlm](https://arxiv.org/html/2609.16884#id2)predictions as deterministic\. This is ineffective in domains such as household robotics, where perception is noisy and ambiguous, and producing deterministic plans may fail when ambiguity and missing information lead to incorrect predicate assignments\.

\\cref

fig:example shows two tasks that demonstrate planning uncertainty due to misleading[vlm](https://arxiv.org/html/2609.16884#id2)predictions and partial observability\. In\\creffig:example:radio, the robot must place a book on the target shelf, which is outside the frame\. A radio appears behind the robot’s gripper, but the[vlm](https://arxiv.org/html/2609.16884#id2)believes it is holding the book\. The robot plans to navigate to the shelf, where it will realize its mistake, triggering a replan\. In\\creffig:example:kitchen, the robot must bring a hidden bowl to the sink\. The[vlm](https://arxiv.org/html/2609.16884#id2)has no indication that the bowl is in a cabinet, so it will repeatedly plan to navigate to the bowl that it cannot see and never complete the task\. The robot can overcome these challenges by maintaining a belief over possible world states \(e\.g\., book in hand and not in hand, or bowl in cabinet or not in cabinet\) and planning to solve the task accordingly\. This will enable the robot to solve the task with less replanning\.

In line with this, we present[sc](https://arxiv.org/html/2609.16884#id11)\([sc](https://arxiv.org/html/2609.16884#id11)\), which leverages a[vlm](https://arxiv.org/html/2609.16884#id2)to guide a robust decision\-making process rather than blindly trusting its output\. We use the[vlm](https://arxiv.org/html/2609.16884#id2)to produce predicate probabilities to maintain an explicit belief over high\-level states and frame the problem as[cpp](https://arxiv.org/html/2609.16884#id6)\([cpp](https://arxiv.org/html/2609.16884#id6)\)\([Domshlak and Hoffmann, 2006](https://arxiv.org/html/2609.16884#bib.bib5)\)\. This produces more robust plans while retaining the interpretability improvements of symbolic grounding\. The contributions of our work are as follows:

1. 1\.We introduce[vlm](https://arxiv.org/html/2609.16884#id2)\-as\-probabilistic\-grounder, a new[vlm](https://arxiv.org/html/2609.16884#id2)\-planning paradigm leveraging fluent\-level probability instead of brittle deterministic grounding or direct action generation\.
2. 2\.We formalize the[rvp](https://arxiv.org/html/2609.16884#id10)\([rvp](https://arxiv.org/html/2609.16884#id10)\) problem, providing a principled definition of planning under partial observability and perceptual uncertainty in visual robotic domains\.
3. 3\.We propose[sc](https://arxiv.org/html/2609.16884#id11), a robust visual task planner that maintains a symbolic belief derived from[vlm](https://arxiv.org/html/2609.16884#id2)\-based probabilities and compiles it into a[cp](https://arxiv.org/html/2609.16884#id5)\([cp](https://arxiv.org/html/2609.16884#id5)\) problem\.
4. 4\.We develop a theoretically grounded planning\-execution loop with guarantees on correctness and safety, including conditions under which the[vlm](https://arxiv.org/html/2609.16884#id2)is sufficiently accurate and useful\.

We evaluate our approach on the ViPlan\-HH benchmark\([Merler et al\., 2025](https://arxiv.org/html/2609.16884#bib.bib21)\), which contains multiple robot planning tasks in various home scenes\. Our experiments demonstrate how[sc](https://arxiv.org/html/2609.16884#id11)’s robust plans enable robots to solve complex tasks under uncertainty where other approaches fail\.

![Refer to caption](https://arxiv.org/html/2609.16884v1/theirs-rearrange.png)

Figure 2:[vlm](https://arxiv.org/html/2609.16884#id2)\-as\-grounder \(top\) and[vlm](https://arxiv.org/html/2609.16884#id2)\-as\-planner \(bottom\)
![Refer to caption](https://arxiv.org/html/2609.16884v1/ours-rearrange.png)

Figure 3:[sc](https://arxiv.org/html/2609.16884#id11)\([sc](https://arxiv.org/html/2609.16884#id11)\) pipeline

## 2Background and Related Work

Our approach is based on harnessing the power of pre\-trained[vlm](https://arxiv.org/html/2609.16884#id2)to answer semantic queries about visual input\([Li et al\., 2022b](https://arxiv.org/html/2609.16884#bib.bib18);[Radford et al\., 2021](https://arxiv.org/html/2609.16884#bib.bib27);[Li et al\., 2019](https://arxiv.org/html/2609.16884#bib.bib17)\)\. LetOObe a set of possible image observations, and let𝒱\\mathcal\{V\}be a set of textual tokens called the vocabulary\. A[vlm](https://arxiv.org/html/2609.16884#id2)is a functionϕ:O×𝒱∗→\[0,1\]𝒱\\phi:O\\times\\mathcal\{V\}^\{\*\}\\to\[0,1\]^\{\\mathcal\{V\}\}that takes as input an image observationo∈Oo\\in Oand a sequence of textual tokens \(a prompt\)x=⟨v1,…,vn⟩∈𝒱∗x=\\left\\langle v\_\{1\},\\ldots,v\_\{n\}\\right\\rangle\\in\\mathcal\{V\}^\{\*\}\. Its output is a prediction for the next token in the sequence\. By iteratively inserting the predicted token into the prompt, the[vlm](https://arxiv.org/html/2609.16884#id2)generates textual outputs conditioned on visual inputs\.

Recent work in[vla](https://arxiv.org/html/2609.16884#id3)\([vla](https://arxiv.org/html/2609.16884#id3)\) robotics uses visual and language inputs either to produce low\-level robot actions directly or to support task\-level planning\. End\-to\-end[vla](https://arxiv.org/html/2609.16884#id3)policies map observations and natural language instructions to robot controls\([Kim et al\., 2024](https://arxiv.org/html/2609.16884#bib.bib15);[Duan et al\., 2024](https://arxiv.org/html/2609.16884#bib.bib6);[Jiang et al\., 2023](https://arxiv.org/html/2609.16884#bib.bib14)\), while planning\-loop approaches use[vlm](https://arxiv.org/html/2609.16884#id2)as high\-level planners or symbolic grounders\([Rana et al\., 2023](https://arxiv.org/html/2609.16884#bib.bib28);[Zhang et al\., 2024](https://arxiv.org/html/2609.16884#bib.bib36);[Hu et al\., 2023](https://arxiv.org/html/2609.16884#bib.bib13)\)\. In this work, we focus on the latter\.

[Merler et al\. \(2025\)](https://arxiv.org/html/2609.16884#bib.bib21)distinguish two paradigms for integrating a[vlm](https://arxiv.org/html/2609.16884#id2)into a planning loop\. In[vlm](https://arxiv.org/html/2609.16884#id2)\-as\-planner, depicted in\\creffig:methods:theirs \(bottom\), the model maps an image observation and task description directly to an action sequence\([Yang et al\., 2025](https://arxiv.org/html/2609.16884#bib.bib34);[Duan et al\., 2024](https://arxiv.org/html/2609.16884#bib.bib6);[Hu et al\., 2023](https://arxiv.org/html/2609.16884#bib.bib13)\)\. In[vlm](https://arxiv.org/html/2609.16884#id2)\-as\-grounder, depicted in\\creffig:methods:theirs \(top\), the model assigns Boolean values to grounded task fluents, and a symbolic planner plans from the resulting state estimate\([Azran et al\., 2025](https://arxiv.org/html/2609.16884#bib.bib1);[Liang et al\., 2024](https://arxiv.org/html/2609.16884#bib.bib19);[Chen et al\., 2024](https://arxiv.org/html/2609.16884#bib.bib3);[Ding et al\., 2024](https://arxiv.org/html/2609.16884#bib.bib4);[Zhang et al\., 2024](https://arxiv.org/html/2609.16884#bib.bib36)\)\. Both paradigms typically commit to a single[vlm](https://arxiv.org/html/2609.16884#id2)output rather than propagating uncertainty over multiple plausible symbolic states\. Our approach instead extracts per\-fluent probabilities, constructs a belief over symbolic states, selects states whose cumulative probability is at leastθ\\theta, and computes a conformant plan that is valid for every selected state\.

These task\-level approaches typically use a deterministic symbolic action model\([Ghallab et al\., 2004](https://arxiv.org/html/2609.16884#bib.bib10)\)\. Grounder\-based systems pass one grounded state to a classical planner, while planner\-based systems generate an action sequence expressed in the same symbolic model\. Such models are commonly represented using the[strips](https://arxiv.org/html/2609.16884#id4)formalism\([Fikes and Nilsson, 1971](https://arxiv.org/html/2609.16884#bib.bib7)\)\.[strips](https://arxiv.org/html/2609.16884#id4)defines a planning problem as a tuple⟨F,I,A,G⟩\\left\\langle F,I,A,G\\right\\rangle, whereFFis a set of fluents representing the state of the world,IIis the initial state,AAis a set of actions \(operators\) that have preconditions that determine when they are applicable and can change the state via their effects, andG⊆FG\\subseteq Fis the goal condition\. While it is common to use classical planning algorithms and replanning upon unexpected outcomes\([Yoon et al\., 2007](https://arxiv.org/html/2609.16884#bib.bib35)\), this is highly ineffective in settings in which replanning is costly or even impossible\. For example, a robot may need to communicate with an external computation source to plan, taking a long time due to bad connectivity or even failing when there is no connectivity\.

On the other end of the spectrum,*[cp](https://arxiv.org/html/2609.16884#id5)*\([Palacios and Geffner, 2009](https://arxiv.org/html/2609.16884#bib.bib26);[Smith and Weld, 1998](https://arxiv.org/html/2609.16884#bib.bib31)\)addresses planning under partial observability by generating plans that are guaranteed to achieve the goal from any possible initial state\. In[cp](https://arxiv.org/html/2609.16884#id5), the agent must find a plan that will achieve the goal from a set of possible states called the*belief set*, denotedbIb^\{I\}\.*[cpp](https://arxiv.org/html/2609.16884#id6)*\([Domshlak and Hoffmann, 2006](https://arxiv.org/html/2609.16884#bib.bib5)\)extends this framework by replacing the belief set with a probability distribution over possible statesβ:2F→\[0,1\]\\beta:2^\{F\}\\rightarrow\[0,1\], called a*belief state*, or*belief*\. The objective of[cpp](https://arxiv.org/html/2609.16884#id6)is to find a plan that achieves the goal with some threshold probabilityθ\\theta\. Our work builds upon[cpp](https://arxiv.org/html/2609.16884#id6)by utilizing[vlm](https://arxiv.org/html/2609.16884#id2)to define and update the belief based on visual observations, allowing for more informed planning under uncertainty in visually rich environments\. We find robust plans using insights from[Taig and Brafman \(2013\)](https://arxiv.org/html/2609.16884#bib.bib32)and using off\-the\-shelf conformant planners\([Maliah et al\., 2022](https://arxiv.org/html/2609.16884#bib.bib20);[Shani and Brafman, 2011](https://arxiv.org/html/2609.16884#bib.bib30);[Palacios and Geffner, 2009](https://arxiv.org/html/2609.16884#bib.bib26)\)\.

## 3Problem Formulation

We aim to construct perception–action pipelines that ground symbolic reasoning from raw visual input\. These pipelines should produce satisficing task\-level plans that remain effective despite sensor noise, occlusion, and partial observability\. We therefore formulate*[rvp](https://arxiv.org/html/2609.16884#id10)*for agents operating in complex, partially observable environments\. Hereafter, we focus on an embodied robotic agent, and therefore refer to it as a robot\. In[rvp](https://arxiv.org/html/2609.16884#id10), a robot must perceive the world through onboard sensors \(e\.g\., cameras, depth, proprioception\), infer symbolic state information from raw visual input, and select high\-level actions to execute\. These are represented as*skills*, i\.e\., action implementations for the robot realized by low\-level motion controllers\.

We formalize the problem as a tuple⟨F,A,G,W,O,M,ξ⟩\\left\\langle F,A,G,W,O,M,\\xi\\right\\rangle, which augments the symbolic task model with a continuous configuration space, an observation model, and stochastic skill execution\. Each component captures a layer in the perception\-action hierarchy of a robotic agent:

- •FF,AA, andGGdefine thesymbolic task space, following[strips](https://arxiv.org/html/2609.16884#id4)\([Fikes and Nilsson, 1971](https://arxiv.org/html/2609.16884#bib.bib7)\)\.
- •WWrepresents therobotic workspace, comprising the set of all feasible continuous configurations of both the robot and the manipulable objects in the scene\. A workspace configurationw∈Ww\\in Wencodes the robot’s joint positions, object poses, and environmental states\.
- •OOdenotes theobservation spaceavailable to the robot, such as RGB\-D or multi\-view camera images\.
- •M:W→Δ​OM:W\\to\\Delta Ois theobservation model\. Given a workspace configurationww, the robot receives an observationo∼M⁡\(w\)o\\sim M\(w\)that reflects sensor noise, occlusion, and limited field of view\.
- •ξ:A×W→Δ​W\\xi:A\\times W\\to\\Delta Wis the skill executor, which translates symbolic actions to low\-level control policies that are executable in the workspace\. Invokingξ⁡\(a,w\)\\xi\(a,w\)returns the stochastic result of applying a motion primitive or controller \(e\.g\., for grasping or navigation\) that attempts to realize the symbolic effects ofa∈Aa\\in Aon current workspace configurationw∈Ww\\in W\.

Note that the high\-level STRIPS model is a deterministic view of the world, which defines how we expect actions to affect the workspace\. However, the actual transition is handled by the non\-deterministic skill executorξ\\xi\.

Our objective is to harness the capabilities of[vlm](https://arxiv.org/html/2609.16884#id2)and equip robotic agents with robust planning capabilities in visually complex and uncertain environments\. Assuming that for evaluation, we have access to ground\-truth mappingσ:W→2F\\sigma:W\\to 2^\{F\}from workspace configurations to high\-level[strips](https://arxiv.org/html/2609.16884#id4)states, and to the initial workspace configurationw0w\_\{0\}, we aim to generate policies that maximize the probability of reaching a goal\-satisfying workspace configuration under partial observability\.

## 4[sc](https://arxiv.org/html/2609.16884#id11)\([sc](https://arxiv.org/html/2609.16884#id11)\)

Our approach,*[sc](https://arxiv.org/html/2609.16884#id11)\([sc](https://arxiv.org/html/2609.16884#id11)\)*, integrates[vlm](https://arxiv.org/html/2609.16884#id2)\-based symbolic state estimation, probabilistic planning, and execution strategies for robust decision\-making under perceptual uncertainty in[rvp](https://arxiv.org/html/2609.16884#id10)\.

The[sc](https://arxiv.org/html/2609.16884#id11)pipeline is depicted in\\creffig:methods:ours\. Component \(A\) translates an image observation into a symbolic belief by using a[vlm](https://arxiv.org/html/2609.16884#id2)to obtain a probability distribution over task\-relevant facts, maintained via logarithmic opinion\-pooling updates\. Component \(B\) takes the belief and produces a robust plan, selecting a subset of possible states whose cumulative probability surpasses a user\-specified threshold and invoking a conformant planner that satisfies all states in the subset\. Component \(C\) handles execution, selecting actions and triggering replanning\.

### 4\.1[vlm](https://arxiv.org/html/2609.16884#id2)\-Based Symbolic State Estimation

In the first stage of the pipeline, we infer a high\-level representation of the state from an input image observation, as depicted in component \(A\) of\\creffig:methods:ours\.

The common approach to using[vlm](https://arxiv.org/html/2609.16884#id2)for symbolic state estimation involves prompting the model with visual observations \(e\.g\., images from the robot’s cameras\) and querying it for the truth values of task\-relevant predicates in a deterministic fashion\([Azran et al\., 2025](https://arxiv.org/html/2609.16884#bib.bib1);[Merler et al\., 2025](https://arxiv.org/html/2609.16884#bib.bib21);[Zhang et al\., 2024](https://arxiv.org/html/2609.16884#bib.bib36)\)\. We also prompt the model for true\-false labels of specific fluentsff, but extract the internal probability that the[vlm](https://arxiv.org/html/2609.16884#id2)assigns to the next\-token predictionϕ⁡\(o,x\)\\phi\(o,x\)over the vocabulary, and normalize the true\-false distribution to define a belief over the truth value offf\.

Intuitively, we would expect the[vlm](https://arxiv.org/html/2609.16884#id2)to assign “uncertain” probabilities to true and false \(e\.g\., both around 0\.5\) in cases where the fluent is unobservable\. However,[vlm](https://arxiv.org/html/2609.16884#id2)are typically trained on data where the relevant information is already in the image\. Therefore, questions about objects not present in the image are considered out\-of\-distribution, and thus, we cannot expect them to be calibrated for this\. To account for unobservable or uncertain fluents, we allow a third response labelnullfor cases where there is not enough evidence to confidently assign true or false\.

We define*probabilistic symbolic grounding*as the extraction of a probability for eachf∈Ff\\in F\. Denote byxfx\_\{f\}the prompt used to query fluentff, e\.g\., “Is the cabinet currently open?” for fluent`open\(cabinet\)`\.[Azran et al\. \(2025\)](https://arxiv.org/html/2609.16884#bib.bib1)showed how to generate these prompts autonomously given a symbolic representation of the domain, e\.g\., using[pddl](https://arxiv.org/html/2609.16884#id9)\([pddl](https://arxiv.org/html/2609.16884#id9)\)\.

To obtain a probabilitypo,fp\_\{o,f\}for each fluentf∈Ff\\in Ffor that specific observationooand[vlm](https://arxiv.org/html/2609.16884#id2)ϕ\\phi, we calculate the probability of fluentff\. First, we extract the[vlm](https://arxiv.org/html/2609.16884#id2)output probabilities for the tokens “true”, “false”, and “null”\. If the “null” token is most likely, we set the probability for that fluent topo,f=0\.5p\_\{o,f\}=0\.5\. Otherwise, we normalize the true\-false probabilitiespo,f=po,ft​r​u​epo,ft​r​u​e\+po,ff​a​l​s​ep\_\{o,f\}=\\frac\{p^\{true\}\_\{o,f\}\}\{p^\{true\}\_\{o,f\}\+p^\{false\}\_\{o,f\}\}\. See\\crefap:probground for full details on the probabilistic grounding computation\.

We define a*factored belief*βF=\(βf\)f∈F∈\[0,1\]F\\beta\_\{F\}=\(\\beta\_\{f\}\)\_\{f\\in F\}\\in\[0,1\]^\{F\}as a belief maintained over individual fluents\. Using this representation, we perform per\-fluent logarithmic opinion\-pooling updates\([Neyman and Roughgarden, 2023](https://arxiv.org/html/2609.16884#bib.bib23);[Genest and Zidek, 1986](https://arxiv.org/html/2609.16884#bib.bib9)\)\. We calculateβf←expit⁡\(logit⁡\(βf\)\+logit⁡\(po,f\)\)\\beta\_\{f\}\\leftarrow\\mathrm\{expit\}\(\\mathrm\{logit\}\(\\beta\_\{f\}\)\+\\mathrm\{logit\}\(p\_\{o,f\}\)\)\. Note that ifpo,f=0\.5p\_\{o,f\}=0\.5, thenlogit⁡\(po,f\)=0\\mathrm\{logit\}\(p\_\{o,f\}\)=0, and thus the belief about fluentffremains unchanged, as expected for an uninformative observation\.

To obtain a belief over the full symbolic state, we assume conditional independence between fluents, subject to constraints𝒞\\mathcal\{C\}, e\.g\., mutual exclusion and co\-dependence defined by the task domain\. This factorization is an approximation\. The constraints encode known dependencies, while unmodeled correlations may enlarge the[mlss](https://arxiv.org/html/2609.16884#id8)\([mlss](https://arxiv.org/html/2609.16884#id8)\) and make planning conservative\. States that violate𝒞\\mathcal\{C\}are assigned zero probability, and the rest are normalized accordingly\.

Denotes⁡\(f\)=𝟙f∈ss\(f\)=\\mathbbm\{1\}\_\{f\\in s\}\. The belief is calculated as follows:

β~​\(s\)=∏f∈Fβfs⁡\(f\)​\(1−βf\)1−s⁡\(f\)\\tilde\{\\beta\}\(s\)=\\prod\_\{f\\in F\}\\beta\_\{f\}^\{s\(f\)\}\(1\-\\beta\_\{f\}\)^\{1\-s\(f\)\}\(1\)
β⁡\(s\)=\{β~​\(s\)Zif​s​satisfies​𝒞0otherwise\\beta\(s\)=\\begin\{cases\}\\frac\{\\tilde\{\\beta\}\(s\)\}\{Z\}&\\text\{if \}s\\text\{ satisfies \}\\mathcal\{C\}\\\\ 0&\\text\{otherwise\}\\end\{cases\}\(2\)
whereZ≤1Z\\leq 1is a normalization constant\. We callβ~\\tilde\{\\beta\}the*unconstrained belief*, as it does not take into account the constraints in𝒞\\mathcal\{C\}\. Note that forbbto be well\-defined, we must assume there exists at least one statessthat satisfies𝒞\\mathcal\{C\}with a non\-zeroβ~​\(s\)\\tilde\{\\beta\}\(s\)\.

To extract the constraint set𝒞\\mathcal\{C\}, we use the Fast Downward planning system’s finite domain representation\([Helmert, 2006](https://arxiv.org/html/2609.16884#bib.bib12)\)\. This reveals several constraints, e\.g\., mutually exclusive fluent groups, exposed in a dedicated invariant discovery stage\. We can use the graphs generated by this invariant finder to calculateZZin polynomial time\. However, ignoring this term, we can view our belief as a lower bound on the actual belief\. This will be enough to obtain a state space that guarantees a desired threshold probability of success in the underlying[cpp](https://arxiv.org/html/2609.16884#id6)problem \(see next section\)\.

### 4\.2Conformant Probabilistic Planning with[vlm](https://arxiv.org/html/2609.16884#id2)\-based Belief

Next in the pipeline is component \(B\) in\\creffig:methods:ours, which generates a robust plan that satisfies the goal with high probability according to our maintained belief\.

The[cp](https://arxiv.org/html/2609.16884#id5)paradigm addresses planning under initial state uncertainty\.[rvp](https://arxiv.org/html/2609.16884#id10)raises two sources of uncertainty, namely perceptual uncertainty when translating from observations to symbolic states, and partial observability in a single observation that may not fully reveal the true symbolic state\. When the agent receives an observation, we want to define a[cp](https://arxiv.org/html/2609.16884#id5)problem that reflects the current belief\.

Let⟨F,β,A,G,θ⟩\\left\\langle F,\\beta,A,G,\\theta\\right\\ranglebe a[cpp](https://arxiv.org/html/2609.16884#id6)problem\.[Taig and Brafman \(2013\)](https://arxiv.org/html/2609.16884#bib.bib32)prove that solving this problem is equivalent to solving a[cp](https://arxiv.org/html/2609.16884#id5)problem⟨F,bI,A,G⟩\\left\\langle F,b^\{I\},A,G\\right\\ranglesuch that the probability that the initial state is inbIb^\{I\}is greater thanθ\\theta, i\.e\.,∑s∈bIβ⁡\(s\)≥θ\\sum\_\{s\\in b^\{I\}\}\\beta\(s\)\\geq\\theta\. However, their approach used a planner to find abIb^\{I\}with the cheapest solution\. We want the robot to act on the best interpretation of the visual scene, and so we propose finding the most likely subset of states that satisfy the probability threshold\.

###### Definition 1\.

LetβF\\beta\_\{F\}be a factored belief,θ∈\[0,1\]\\theta\\in\[0,1\]be a probability threshold, and𝒞\\mathcal\{C\}be a set of constraints overFF\. The[mlss](https://arxiv.org/html/2609.16884#id8)\([mlss](https://arxiv.org/html/2609.16884#id8)\), denoted byM​L​S​S​\(βF,θ,𝒞\)MLSS\(\\beta\_\{F\},\\theta,\\mathcal\{C\}\), is a subset of statesbI⊆2Fb^\{I\}\\subseteq 2^\{F\}of minimal cardinality such that∑s∈bIβ⁡\(s\)≥θ\\sum\_\{s\\in b^\{I\}\}\\beta\(s\)\\geq\\theta\.

\\cref

alg:mlss describes our approach to finding an[mlss](https://arxiv.org/html/2609.16884#id8)by performing a search over boolean fluent value flips\. In lines[1](https://arxiv.org/html/2609.16884#algx1.l1)\-[4](https://arxiv.org/html/2609.16884#algx1.l4), we initialize the search with the most likely states0s\_\{0\}and set up a max\-heap containing only this state\. In line[7](https://arxiv.org/html/2609.16884#algx1.l7), we extract the most likely state from the heap, based on its unconstrained beliefβ~\\tilde\{\\beta\}, i\.e\., the belief before applying constraints and normalizing \(computed via\\crefeq:calc\-unconst\-belief\)\. The extracted state is added to the output belief set if it satisfies the constraints \(line[9](https://arxiv.org/html/2609.16884#algx1.l9)\)\. The loop starting at line[12](https://arxiv.org/html/2609.16884#algx1.l12)explores neighboring states by flipping each fluent in turn, adding unvisited neighbors to the heap \(line[16](https://arxiv.org/html/2609.16884#algx1.l16)\)\. The termination condition \(line[6](https://arxiv.org/html/2609.16884#algx1.l6)\) checks whether the cumulative probability of the selected states meets or exceedsθ\\theta\. The key insight behind this algorithm is that although states are extracted from the heap according to the unconstrained beliefβ~\\tilde\{\\beta\}, they are guaranteed to be in non\-increasing order of the beliefβ\\beta\.

Algorithm 1[mlss](https://arxiv.org/html/2609.16884#id8)0:

βF:F→\[0,1\]\\beta\_\{F\}:F\\rightarrow\[0,1\],

θ∈\[0,1\]\\theta\\in\[0,1\],

𝒞\\mathcal\{C\}– set of constraints\.

0:

M​L​S​S​\(βF,θ,𝒞\)MLSS\(\\beta\_\{F\},\\theta,\\mathcal\{C\}\)
1:

s0←𝟙\[βf\>0\.5\]∀f∈Fs\_\{0\}\\leftarrow\\mathbbm\{1\}\[\\beta\_\{f\}\>0\.5\]\\quad\\forall f\\in F
2:

Q←Q\\leftarrowEmpty max\-heap

3:

QQ\.Insert\(

s0s\_\{0\},

β~​\(s0\)\\tilde\{\\beta\}\(s\_\{0\}\)\) \{

β~\\tilde\{\\beta\}from\\crefeq:calc\-unconst\-belief\}

4:

Visited←\{s0\}\\text\{Visited\}\\leftarrow\\\{s\_\{0\}\\\},

b←∅b\\leftarrow\\emptyset
6:while

p<θp<\\thetaand

Q≠∅Q\\neq\\emptysetdo

7:

s←s\\leftarrowQQ\.ExtractMax\(\)

8:if

s⊧𝒞s\\models\\mathcal\{C\}then

9:

b←b∪\{s\}b\\leftarrow b\\cup\\\{s\\\}
10:

p←p\+β⁡\(s\)p\\leftarrow p\+\\beta\(s\)\{

β\\betafrom\\crefeq:calc\-belief\}

11:endif

13:

s′←s^\{\\prime\}\\leftarrowFlip\(

ss,

ff\)

14:if

s′∉Visiteds^\{\\prime\}\\notin\\text\{Visited\}then

15:

Visited←Visited∪\{s′\}\\text\{Visited\}\\leftarrow\\text\{Visited\}\\cup\\\{s^\{\\prime\}\\\}
16:

QQ\.Insert\(

s′s^\{\\prime\},

β~​\(s′\)\\tilde\{\\beta\}\(s^\{\\prime\}\)\)

17:endif

18:endfor

19:endwhile

Algorithm 2[sc](https://arxiv.org/html/2609.16884#id11)Execution Loop0:

⟨F,A,G,W,O,M,ξ⟩\\left\\langle F,A,G,W,O,M,\\xi\\right\\rangleis an[rvp](https://arxiv.org/html/2609.16884#id10)problem,

θ∈\[0,1\]\\theta\\in\[0,1\],

βI:2F→\[0,1\]\\beta^\{I\}:2^\{F\}\\to\[0,1\], and

o∈Oo\\in O
1:

𝒞←\\mathcal\{C\}\\leftarrowExtractConstraints\(

F,AF,A\)

2:

βF←\\beta\_\{F\}\\leftarrowVLM\-belief\(

o,ϕ,βI,𝒞o,\\phi,\\beta^\{I\},\\mathcal\{C\}\)

3:while

β⁡\(G\)<θ\\beta\(G\)<\\thetado

4:

bI←b^\{I\}\\leftarrowMLSS\(

βF,θ,𝒞\\beta\_\{F\},\\theta,\\mathcal\{C\}\)

5:

Π←\\Pi\\leftarrow[cp](https://arxiv.org/html/2609.16884#id5)\(

F,bI,A,G,θF,b^\{I\},A,G,\\theta\)

7:ifUnsafe\(

a,bIa,b^\{I\}\)then

8:break\{Replan\}

9:endif

11:

o←o\\leftarrowSensorReading\(\)

12:

βF←\\beta\_\{F\}\\leftarrowVLM\-belief\(

o,ϕ,βF,𝒞o,\\phi,\\beta\_\{F\},\\mathcal\{C\}\)

13:ifImprobable\(

Πremaining,βF\\Pi\_\{\\text\{remaining\}\},\\beta\_\{F\}\)then

14:break\{Replan\}

15:endif

16:endfor

17:endwhile

###### Theorem 2\.

In\\crefalg:mlss, when a constraint\-satisfying statessis extracted from the heapQQ, then for alls′∉bs^\{\\prime\}\\notin bit holds thatβ⁡\(s\)≥β⁡\(s′\)\\beta\(s\)\\geq\\beta\(s^\{\\prime\}\), whereβ\\betais the belief computed by\\crefeq:calc\-belief\.

The proof asserts that states are extracted from the heap in non\-increasing order of their unconstrained beliefβ~\\tilde\{\\beta\}across the entire state space2F2^\{F\}\. Find the full proof in\\crefap:proof\-mlss\.

In the worst case, the number of explored states is exponential in\|F\|\|F\|\. Even if we bound the minimal subset size tokk, there might still be many constraint\-violating states that must be explored before findingkkvalid states\. In the absence of constraints, we can provide a tighter bound on the runtime, hoping that in practice we encounter a manageable number of constraint\-violating states\.

###### Proposition 3\.

If𝒞=∅\\mathcal\{C\}=\\emptyset,\\crefalg:mlss runs inO⁡\(\|F\|​k​log⁡\|F\|​k\)O\(\|F\|k\\log\|F\|k\)time withO⁡\(\|F\|2​k\)O\(\|F\|^\{2\}k\)bits, wherekkis the number of states in the[mlss](https://arxiv.org/html/2609.16884#id8)\.

With this, we can efficiently generate the[cpp](https://arxiv.org/html/2609.16884#id6)problem that arises from the[vlm](https://arxiv.org/html/2609.16884#id2)\-based belief state estimation\. By characterizing the accuracy of a[vlm](https://arxiv.org/html/2609.16884#id2)by its cumulative error over all fluents, we can guarantee that if the[vlm](https://arxiv.org/html/2609.16884#id2)’s per\-fluent predictions are*sufficiently*accurate, the true state will be included in the[mlss](https://arxiv.org/html/2609.16884#id8)\. This enables the user to define bounds on sufficiency and accuracy\. As a first step, we prove a sufficient condition on the factored belief that guarantees that the true state is included in the[mlss](https://arxiv.org/html/2609.16884#id8)\.

###### Definition 4\(Cumulative factored belief error\)\.

Lets∈2Fs\\in 2^\{F\}be some high\-level state of the world, and letβF=\(βf\)f∈F\\beta\_\{F\}=\(\\beta\_\{f\}\)\_\{f\\in F\}be a factored belief\. The*cumulative factored belief error*isδ⁡\(βF,s\)=∑f∈F\|βf−s⁡\(f\)\|\\delta\(\\beta\_\{F\},s\)=\\sum\_\{f\\in F\}\|\\beta\_\{f\}\-s\(f\)\|\.

###### Theorem 5\.

Letθ∈\(0,1\]\\theta\\in\(0,1\], let𝒞\\mathcal\{C\}be a set of constraints overFF, and lets∈2Fs\\in 2^\{F\}satisfy𝒞\\mathcal\{C\}\. For everyβF∈\[0,1\]F\\beta\_\{F\}\\in\[0,1\]^\{F\}, ifδ⁡\(βF,s\)<θ\\delta\(\\beta\_\{F\},s\)<\\theta, thens∈M​L​S​S​\(βF,θ,𝒞\)s\\in MLSS\(\\beta\_\{F\},\\theta,\\mathcal\{C\}\)\.

The proof uses the Weierstrass product inequality to lower\-bound the probability of a constraint\-satisfying state\. The full proof is provided in\\crefap:proof:calib\. If the true current states∗s^\{\*\}is in the[mlss](https://arxiv.org/html/2609.16884#id8), any conformant plan found for the[mlss](https://arxiv.org/html/2609.16884#id8)is valid froms∗s^\{\*\}under the symbolic model\. We next give sufficient conditions under which repeated observations of a fixed state can reduce the cumulative factored belief error in a finite number of steps\.

###### Definition 6\(Weakly calibrated[vlm](https://arxiv.org/html/2609.16884#id2)\)\.

For fluent probabilitypfp\_\{f\}and true state fluent assignments∗​\(f\)s^\{\*\}\(f\), definepcorrectp\_\{\\text\{correct\}\}as the probability of the true assignment, i\.e\.,pfp\_\{f\}ifs∗​\(f\)=1s^\{\*\}\(f\)=1and1−pf1\-p\_\{f\}otherwise, with complementpincorrect=1−pcorrectp\_\{\\text\{incorrect\}\}=1\-p\_\{\\text\{correct\}\}\. A[vlm](https://arxiv.org/html/2609.16884#id2)is*weakly calibrated*if there existsγ\>0\\gamma\>0such that for every observationo∈Oo\\in Oand fluentf∈Ff\\in F, the probabilitypfp\_\{f\}derived for fluentffis at leastγ\\gammacloser to the correct prediction than the incorrect one, i\.e\.,pcorrect−pincorrect≥γp\_\{\\text\{correct\}\}\-p\_\{\\text\{incorrect\}\}\\geq\\gamma\.

###### Definition 7\(Minimum visibility rate\)\.

The*minimum visibility rate*ρ\\rhois the frequency with which the rarest fluent is observed, where the rarest fluent is a maximizer inarg​maxf∈F​Pr​\(po,fnull\>max⁡\{po,ftrue,po,ffalse\}\)\\argmax\_\{f\\in F\}\\Pr\(p\_\{o,f\}^\{null\}\>\\max\\\{p\_\{o,f\}^\{true\},p\_\{o,f\}^\{false\}\\\}\)

###### Corollary 8\.

Letρ\>0\\rho\>0be the minimum visibility rate\. If the[vlm](https://arxiv.org/html/2609.16884#id2)is weakly calibrated with error marginγ\\gamma, then there exists a finite number of stepsTTafter which a conformant plan for the[mlss](https://arxiv.org/html/2609.16884#id8)according toβF\\beta\_\{F\}is satisficing from the true current state\.

In the proof, we find a lower bound on the current log odds in the belief that grows over time, and push it aboveθ\\theta\. Thus, the[vlm](https://arxiv.org/html/2609.16884#id2)need not be perfect\. It only needs to be persistently better than a random guess on visible fluents to eventually generate a satisficing plan for the real\-world state\. The full proof is in\\crefap:proof:fin\-step\.

These assumptions describe when repeated visible predictions provide consistent evidence for each fluent\. They are weaker than assuming error\-free deterministic grounding\. Both assumptions can be empirically evaluated for a given[vlm](https://arxiv.org/html/2609.16884#id2)and task domain\. The parametersγ\\gammaandρ\\rhocan then be used to calculate the number of steps required by\\crefthm:fin\-step\.

Of course, when using a conformant planner, there is an inherent tradeoff between robustness and completeness\. The[cpp](https://arxiv.org/html/2609.16884#id6)component of[sc](https://arxiv.org/html/2609.16884#id11)allows the user to iteratively adjust this by calibrating the success probability thresholdθ\\thetaif a plan is not found\.

### 4\.3Executing Conformant Probabilistic Plans

We aim to support robotic settings, wherein executing a plan may lead to unexpected outcomes due to perceptual uncertainty, partial observability, and action failure\. As such, part of the robustness of our policy relies on the ability of the executor to detect failure and inconsistency\. A replan may be triggered when new observations indicate that the current belief is inconsistent with the belief set used for planning, or the action execution failed\. In the classical case, initiating replanning is straightforward: when an action cannot be executed, or its observed outcome does not match the expected state, the agent replans from the new observed state\([Yoon et al\., 2007](https://arxiv.org/html/2609.16884#bib.bib35)\)\. In the conformant case, there are a few more considerations\.

To handle replanning, we introduce a novel conformant plan executor, handled in component \(C\) of\\creffig:methods:ours\. We need to determine when the current plan no longer aligns with the belief derived from new observations\. Our execution component introduces a belief\-consistency\-based monitoring criterion, a probabilistic monitoring scheme tailored for[vlm](https://arxiv.org/html/2609.16884#id2)uncertainty\.[vlm](https://arxiv.org/html/2609.16884#id2)can drastically change their predictions from one observation to another, so the standard “expected state vs observed state” criterion can lead to constant replanning\. As such, we propose three replanning triggers based on this misalignment, namely improbable plan, unsafe action, and plan exhaustion\. We focus on belief drift via the improbable plan trigger, which requires the[vlm](https://arxiv.org/html/2609.16884#id2)to output predictions that are persistently inconsistent with the belief and with great confidence\. The unsafe action trigger protects against “hallucinated certainty”, where a[vlm](https://arxiv.org/html/2609.16884#id2)might initially be confident but wavers as the robot approaches\. Finally, the plan exhaustion trigger ensures that if the plan is not successful after execution, we replan to correct for any misinterpretations of the environment\. To our knowledge, this is the first execution framework that explicitly reasons about[vlm](https://arxiv.org/html/2609.16884#id2)\-induced belief drift rather than single\-step perceptual inconsistency\. The full execution loop is outlined in\\crefalg:replan\.

An improbable plan is one whose probability of success is below a thresholdθ\\thetagiven the current belief\. As a proxy for this value, we calculate the probability of the current belief setbIb^\{I\}, after executing all actions taken thus far\. If this value drops belowθ\\theta, it is possible that the plan’s success probability is also belowθ\\theta, and so we replan\.

The resulting policy from\\crefalg:replan, which we denote asπc​p​p\\pi\_\{cpp\}, provides a conditional robustness guarantee based on the accuracy of our perceptual belief, according to\\crefthm:calib\. This execution strategy also provides a safety guarantee compared to[vlm](https://arxiv.org/html/2609.16884#id2)\-as\-grounder approaches, as shown in\\crefap:safety\.

The computational requirements of\\crefalg:replan are divided into three components\. The[vlm](https://arxiv.org/html/2609.16884#id2)is queried once per fluent, so this stage is linear in\|F\|\|F\|\(number of[vlm](https://arxiv.org/html/2609.16884#id2)calls\), and in practice dominates wall\-clock time because[vlm](https://arxiv.org/html/2609.16884#id2)calls are expensive\. These independent queries can be batched or restricted to task\-relevant fluents\. The[mlss](https://arxiv.org/html/2609.16884#id8)algorithm has a worst\-case exponential time complexity in the number of fluents, but as shown in\\crefthm:efficient, this is manageable when the number of constraint\-violating states is limited\. Finally,[cp](https://arxiv.org/html/2609.16884#id5)itself is worst\-case exponentially hard, meaning[sc](https://arxiv.org/html/2609.16884#id11)inherits the conformant planners’ theoretical complexity\.

## 5Use Case for Robust Visual Planning with a Simulated Household Robot

Domain\.We evaluate[sc](https://arxiv.org/html/2609.16884#id11)on ViPlan\-HH\([Merler et al\., 2025](https://arxiv.org/html/2609.16884#bib.bib21)\), a household robotics benchmark built on iGibson\([Li et al\., 2022a](https://arxiv.org/html/2609.16884#bib.bib16)\)\. We enhance the benchmark by removing any privileged information about hidden objects, making this a true partially observable domain111All code is available at[https://github\.com/CLAIR\-LAB\-TECHNION/ViPlanPO/](https://github.com/CLAIR-LAB-TECHNION/ViPlanPO/)\. The robot is a mobile manipulator with an RGB camera and one arm\. Tasks include sorting books on shelves, cleaning out drawers, locking doors, packing and unpacking groceries, and other household rearrangement tasks\. Tasks are categorized into three difficulty levels \(simple, medium, hard\) based on the task horizon, meaning that harder tasks require more actions to complete, but are not necessarily more complex\. See\\crefap:domain for details on the domain and tasks\. The domain is specified in[pddl](https://arxiv.org/html/2609.16884#id9)with movable and fixed objects, relations such asontopandinside, and high\-level actions such asnavigate\-to,grasp, andplace\-on\. Motion actions use probabilistic executors and may fail because of kinematics, collisions, or similar constraints\. Observations are egocentric RGB images, so the robot sees only part of the home and must reason about hidden objects while replanning from new views\. Sample[pddl](https://arxiv.org/html/2609.16884#id9)files appear in\\crefap:pddl\.

Setup\.We compare three planning\-loop paradigms from\\creffig:methods:theirs,fig:methods:ours, namely[vlm](https://arxiv.org/html/2609.16884#id2)\-as\-planner \(VLM\-P\),[vlm](https://arxiv.org/html/2609.16884#id2)\-as\-grounder \(VLM\-G\), and[sc](https://arxiv.org/html/2609.16884#id11)\. All methods receive the current image and[pddl](https://arxiv.org/html/2609.16884#id9)\-derived context\. We use GPT\-4\.1\([OpenAI, 2023](https://arxiv.org/html/2609.16884#bib.bib24)\)through the OpenAI API for all methods\. The planner baseline returns text actions, while[vlm](https://arxiv.org/html/2609.16884#id2)\-as\-grounder and[sc](https://arxiv.org/html/2609.16884#id11)use next\-token probabilities from fluent queries\. Implementation details, baselines, and prompts are in\\crefap:use\-case,ap:baselines,ap:prompts\.

Table 1:ViPlan\-HH results\.[vlm](https://arxiv.org/html/2609.16884#id2)\-P is[vlm](https://arxiv.org/html/2609.16884#id2)\-as\-planner,[vlm](https://arxiv.org/html/2609.16884#id2)\-G is[vlm](https://arxiv.org/html/2609.16884#id2)\-as\-grounder, and[sc](https://arxiv.org/html/2609.16884#id11)is our method\. Success and valid\-first\-plan rates are percentages\. Lower action and planner\-call counts are better\.Quantitative Results\.\\Creftab:results reports task execution success, valid\-first\-plan rates, and mean action counts and planner calls per trial\.[sc](https://arxiv.org/html/2609.16884#id11)achieves the highest success rate in every split\. Relative to VLM\-G, success improves by 116\.8% on simple tasks and 166\.8% on medium tasks\. On hard tasks, VLM\-G solves no instances while[sc](https://arxiv.org/html/2609.16884#id11)solves 66\.7%\. Relative to VLM\-P, success improves by 333\.5%, 704\.2%, and 100\.3% on simple, medium, and hard tasks, respectively\. Compared to both baselines,[sc](https://arxiv.org/html/2609.16884#id11)fully solves some task families for which neither baseline solves any instance\. These performance gains also come with reduced planning overhead\.[sc](https://arxiv.org/html/2609.16884#id11)uses between 1\.9 and 10\.0 times fewer planner calls than the baselines, and executes between 1\.2 and 6\.8 fewer actions on average\. The 66\.7% valid\-first\-plan rate on simple tasks indicates that considering multiple initial\-state hypotheses is often sufficient to generate a valid plan without replanning\. This advantage for[sc](https://arxiv.org/html/2609.16884#id11), however, is only visible in the simplest tasks\.

Qualitative Behavior\.The same mechanism explains the observed failures\. In*cleaning out drawers*, the VLM\-P baseline assumes the hidden bowl is reachable and plans a direct grasp, which fails when the bowl is inside a closed cabinet\.[sc](https://arxiv.org/html/2609.16884#id11)assigns probability to the hidden\-object state and opens the cabinet first, so the plan succeeds whether or not the bowl is hidden\. In*sorting books*, the image can make objects near the gripper appear held, and a deterministic grounder may conclude that the robot already holds the hardback\.[sc](https://arxiv.org/html/2609.16884#id11)keeps both holding hypotheses and selects a plan that is feasible under either one, avoiding the brittle dependence on a single perceptual judgment\.

## 6Conclusion

To enable robotic agents to operate effectively in real\-world, partially observable environments characterized by limited and uncertain perceptual information, we propose a framework for robust planning under perceptual uncertainty\. The approach employs[vlm](https://arxiv.org/html/2609.16884#id2)\([vlm](https://arxiv.org/html/2609.16884#id2)\) to derive a probabilistic, factored representation of the current state, which is used to update the agent’s belief\. This belief representation supports the synthesis of robust task plans using off\-the\-shelf planners\. As a natural extension of this work, we will incorporate active sensing into the planning process, enabling agents to reason explicitly about the informational value of sensing actions\. In addition, we plan to embed the proposed methodology within embodied robotic systems and evaluate its effectiveness across a suite of complex task\-and\-motion planning \(TAMP\) domains\.

###### acknowledgments\-disclosure\-of\-funding\.

Beyond the experiments, we used generative AI tools in the following ways:

- •Gemini’s\([Google, 2026](https://arxiv.org/html/2609.16884#bib.bib11)\)deep research feature was used to verify novelty after the literature review\.
- •ChatGPT\([OpenAI, 2026](https://arxiv.org/html/2609.16884#bib.bib25)\)was used to rephrase text and detect basic syntax and grammar errors\.
- •Codex\([Chen et al\., 2021](https://arxiv.org/html/2609.16884#bib.bib2)\)was used for initial implementations of some components in the experimental code\.

## References

- Azran et al\. \(2025\)Guy Azran, Yuval Goshen, Kai Yuan, and Sarah Keren\.S3E: Semantic Symbolic State Estimation With Vision\-Language Foundation Models\.In*AAAI 2025 Workshop LM4Plan*, February 2025\.
- Chen et al\. \(2021\)Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert\-Voss, William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N\. Carr, Jan Leike, Josh Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, Ilya Sutskever, and Wojciech Zaremba\.Evaluating Large Language Models Trained on Code, July 2021\.
- Chen et al\. \(2024\)Siwei Chen, Anxing Xiao, and David Hsu\.LLM\-State: Open World State Representation for Long\-horizon Task Planning with Large Language Model, April 2024\.
- Ding et al\. \(2024\)Yan Ding, Xiaohan Zhang, Saeid Amiri, Nieqing Cao, Hao Yang, Chad Esselink, and Shiqi Zhang\.Robot Task Planning and Situation Handling in Open Worlds, September 2024\.
- Domshlak and Hoffmann \(2006\)Carmel Domshlak and Jörg Hoffmann\.Fast probabilistic planning through weighted model counting\.In*Proceedings of the Sixteenth International Conference on International Conference on Automated Planning and Scheduling*, ICAPS’06, pages 243–252, Cumbria, UK, June 2006\. AAAI Press\.ISBN 978\-1\-57735\-270\-9\.
- Duan et al\. \(2024\)Jiafei Duan, Wentao Yuan, Wilbert Pumacay, Yi Ru Wang, Kiana Ehsani, Dieter Fox, and Ranjay Krishna\.Manipulate\-Anything: Automating Real\-World Robots using Vision\-Language Models\.In*8th Annual Conference on Robot Learning*, September 2024\.
- Fikes and Nilsson \(1971\)Richard E\. Fikes and Nils J\. Nilsson\.Strips: A new approach to the application of theorem proving to problem solving\.*Artificial Intelligence*, 2\(3\):189–208, December 1971\.ISSN 0004\-3702\.[10\.1016/0004\-3702\(71\)90010\-5](https://doi.org/10.1016/0004-3702(71)90010-5)\.
- Garrett et al\. \(2020\)Caelan Reed Garrett, Tomás Lozano\-Pérez, and Leslie Pack Kaelbling\.PDDLStream: Integrating Symbolic Planners and Blackbox Samplers via Optimistic Adaptive Planning, March 2020\.
- Genest and Zidek \(1986\)Christian Genest and James V\. Zidek\.Combining Probability Distributions: A Critique and an Annotated Bibliography\.*Statistical Science*, 1\(1\):114–135, 1986\.ISSN 0883\-4237\.
- Ghallab et al\. \(2004\)Malik Ghallab, Dana S\. Nau, and Paolo Traverso\.*Automated Planning: Theory and Practice*\.Elsevier/Morgan Kaufmann, Amsterdam Boston, 2004\.ISBN 978\-1\-55860\-856\-6\.
- Google \(2026\)Google\.Gemini, 2026\.
- Helmert \(2006\)M\. Helmert\.The Fast Downward Planning System\.*Journal of Artificial Intelligence Research*, 26:191–246, July 2006\.ISSN 1076\-9757\.[10\.1613/jair\.1705](https://doi.org/10.1613/jair.1705)\.
- Hu et al\. \(2023\)Yingdong Hu, Fanqi Lin, Tong Zhang, Li Yi, and Yang Gao\.Look Before You Leap: Unveiling the Power of GPT\-4V in Robotic Vision\-Language Planning, December 2023\.
- Jiang et al\. \(2023\)Yunfan Jiang, Agrim Gupta, Zichen Zhang, Guanzhi Wang, Yongqiang Dou, Yanjun Chen, Li Fei\-Fei, Anima Anandkumar, Yuke Zhu, and Linxi Fan\.VIMA: General Robot Manipulation with Multimodal Prompts\.In*International Conference on Learning Representations \(ICLR\)*\. arXiv, 2023\.[10\.48550/ARXIV\.2210\.03094](https://doi.org/10.48550/ARXIV.2210.03094)\.
- Kim et al\. \(2024\)Moo Jin Kim, Karl Pertsch, Siddharth Karamcheti, Ted Xiao, Ashwin Balakrishna, Suraj Nair, Rafael Rafailov, Ethan Foster, Grace Lam, Pannag Sanketi, Quan Vuong, Thomas Kollar, Benjamin Burchfiel, Russ Tedrake, Dorsa Sadigh, Sergey Levine, Percy Liang, and Chelsea Finn\.OpenVLA: An Open\-Source Vision\-Language\-Action Model, September 2024\.
- Li et al\. \(2022a\)Chengshu Li, Fei Xia, Roberto Martín\-Martín, Michael Lingelbach, Sanjana Srivastava, Bokui Shen, Kent Elliott Vainio, Cem Gokmen, Gokul Dharan, Tanish Jain, Andrey Kurenkov, Karen Liu, Hyowon Gweon, Jiajun Wu, Li Fei\-Fei, and Silvio Savarese\.iGibson 2\.0: Object\-centric simulation for robot learning of everyday household tasks\.In Aleksandra Faust, David Hsu, and Gerhard Neumann, editors,*Proceedings of the 5th Conference on Robot Learning*, volume 164 of*Proceedings of Machine Learning Research*, pages 455–465\. PMLR, November 2022a\.
- Li et al\. \(2019\)Liunian Harold Li, Mark Yatskar, Da Yin, Cho\-Jui Hsieh, and Kai\-Wei Chang\.VisualBERT: A Simple and Performant Baseline for Vision and Language, August 2019\.
- Li et al\. \(2022b\)Liunian Harold Li, Pengchuan Zhang, Haotian Zhang, Jianwei Yang, Chunyuan Li, Yiwu Zhong, Lijuan Wang, Lu Yuan, Lei Zhang, Jenq\-Neng Hwang, Kai\-Wei Chang, and Jianfeng Gao\.Grounded Language\-Image Pre\-training\.In*2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition \(CVPR\)*, pages 10955–10965, June 2022b\.[10\.1109/CVPR52688\.2022\.01069](https://doi.org/10.1109/CVPR52688.2022.01069)\.
- Liang et al\. \(2024\)Yichao Liang, Nishanth Kumar, Hao Tang, Adrian Weller, Joshua B\. Tenenbaum, Tom Silver, Joao F\. Henriques, and Kevin Ellis\.VisualPredicator: Learning Abstract World Models with Neuro\-Symbolic Predicates for Robot Planning\.In*The Thirteenth International Conference on Learning Representations*, October 2024\.
- Maliah et al\. \(2022\)Shlomi Maliah, Radimir Komarnitski, and Guy Shani\.Computing Contingent Plan Graphs using Online Planning\.*ACM Trans\. Auton\. Adapt\. Syst\.*, 16\(1\):1:1–1:30, January 2022\.ISSN 1556\-4665\.[10\.1145/3488903](https://doi.org/10.1145/3488903)\.
- Merler et al\. \(2025\)Matteo Merler, Nicola Dainese, Minttu Alakuijala, Giovanni Bonetta, Pietro Ferrazzi, Yu Tian, Bernardo Magnini, and Pekka Marttinen\.ViPlan: A Benchmark for Visual Planning with Symbolic Predicates and Vision\-Language Models, May 2025\.
- Moreno et al\. \(2024\)Magí Dalmau Moreno, Néstor García, Vicenç Gómez, and Héctor Geffner\.Combined Task and Motion Planning via Sketch Decompositions\.*Proceedings of the International Conference on Automated Planning and Scheduling*, 34:123–132, May 2024\.ISSN 2334\-0843\.[10\.1609/icaps\.v34i1\.31468](https://doi.org/10.1609/icaps.v34i1.31468)\.
- Neyman and Roughgarden \(2023\)Eric Neyman and Tim Roughgarden\.No\-Regret Learning with Unbounded Losses: The Case of Logarithmic Pooling, October 2023\.
- OpenAI \(2023\)OpenAI\.GPT\-4V\(ision\) system card\.https://openai\.com/index/gpt\-4v\-system\-card/, 2023\.
- OpenAI \(2026\)OpenAI\.ChatGPT, 2026\.
- Palacios and Geffner \(2009\)H\. Palacios and H\. Geffner\.Compiling Uncertainty Away in Conformant Planning Problems with Bounded Width\.*Journal of Artificial Intelligence Research*, 35:623–675, August 2009\.ISSN 1076\-9757\.[10\.1613/jair\.2708](https://doi.org/10.1613/jair.2708)\.
- Radford et al\. \(2021\)Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever\.Learning Transferable Visual Models From Natural Language Supervision\.In*Proceedings of the 38th International Conference on Machine Learning*, pages 8748–8763\. PMLR, July 2021\.
- Rana et al\. \(2023\)Krishan Rana, Jesse Haviland, Sourav Garg, Jad Abou\-Chakra, Ian Reid, and Niko Suenderhauf\.SayPlan: Grounding Large Language Models using 3D Scene Graphs for Scalable Robot Task Planning\.In*7th Annual Conference on Robot Learning*, August 2023\.
- Reiter \(1981\)Raymond Reiter\.ON CLOSED WORLD DATA BASES\.In Bonnie Lynn Webber and Nils J\. Nilsson, editors,*Readings in Artificial Intelligence*, pages 119–140\. Morgan Kaufmann, January 1981\.ISBN 978\-0\-934613\-03\-3\.[10\.1016/B978\-0\-934613\-03\-3\.50014\-3](https://doi.org/10.1016/B978-0-934613-03-3.50014-3)\.
- Shani and Brafman \(2011\)Guy Shani and Ronen I\. Brafman\.Replanning in domains with partial information and sensing actions\.In*Proceedings of the Twenty\-Second International Joint Conference on Artificial Intelligence \- Volume Volume Three*, IJCAI’11, pages 2021–2026, Barcelona, Catalonia, Spain, July 2011\. AAAI Press\.ISBN 978\-1\-57735\-515\-1\.
- Smith and Weld \(1998\)David E\. Smith and Daniel S\. Weld\.Conformant Graphplan\.In*AAAI/IAAI*, July 1998\.
- Taig and Brafman \(2013\)Ran Taig and Ronen I\. Brafman\.Compiling Conformant Probabilistic Planning Problems into Classical Planning\.*Proceedings of the International Conference on Automated Planning and Scheduling*, 23:197–205, June 2013\.ISSN 2334\-0843\.[10\.1609/icaps\.v23i1\.13540](https://doi.org/10.1609/icaps.v23i1.13540)\.
- Wertheim et al\. \(2024\)Or Wertheim, Dan R\. Suissa, and Ronen I\. Brafman\.Plug’n Play Task\-Level Autonomy for Robotics Using POMDPs and Probabilistic Programs\.*IEEE Robotics and Automation Letters*, 9\(1\):587–594, January 2024\.ISSN 2377\-3766\.[10\.1109/LRA\.2023\.3334682](https://doi.org/10.1109/LRA.2023.3334682)\.
- Yang et al\. \(2025\)Zhutian Yang, Caelan Garrett, Dieter Fox, Tomás Lozano\-Pérez, and Leslie Pack Kaelbling\.Guiding Long\-Horizon Task and Motion Planning with Vision Language Models\.In*2025 IEEE International Conference on Robotics and Automation \(ICRA\)*, pages 16847–16853, May 2025\.[10\.1109/ICRA55743\.2025\.11128705](https://doi.org/10.1109/ICRA55743.2025.11128705)\.
- Yoon et al\. \(2007\)Sungwook Yoon, Alan Fern, and Robert Givan\.FF\-Replan: A baseline for probabilistic planning\.In*Proceedings of the Seventeenth International Conference on International Conference on Automated Planning and Scheduling*, ICAPS’07, pages 352–359, Providence, Rhode Island, USA, September 2007\. AAAI Press\.ISBN 978\-1\-57735\-344\-7\.
- Zhang et al\. \(2024\)Xiaohan Zhang, Zainab Altaweel, Yohei Hayamizu, Yan Ding, Saeid Amiri, Hao Yang, Andy Kaminski, Chad Esselink, and Shiqi Zhang\.DKPROMPT: Domain Knowledge Prompting Vision\-Language Models for Open\-World Planning, June 2024\.

\\crefalias

sectionappendix\\crefaliassubsectionappendix

## Appendix AProbabilistic Grounding Calculation

The exact computation of the probabilistic grounding of fluentffgiven observationoois:

1. 1\.Extract the[vlm](https://arxiv.org/html/2609.16884#id2)output probabilities for the tokens “true”, “false”, and “null”\. Denotepo,ft​r​u​e=ϕ⁡\(o,xf\)​\[t​r​u​e\]p^\{true\}\_\{o,f\}=\\phi\(o,x\_\{f\}\)\[true\],po,ff​a​l​s​e=ϕ⁡\(o,xf\)​\[f​a​l​s​e\]p^\{false\}\_\{o,f\}=\\phi\(o,x\_\{f\}\)\[false\],po,fn​u​l​l=ϕ⁡\(o,xf\)​\[n​u​l​l\]p^\{null\}\_\{o,f\}=\\phi\(o,x\_\{f\}\)\[null\]\.
2. 2\.Ifpo,fn​u​l​l\>po,ft​r​u​ep^\{null\}\_\{o,f\}\>p^\{true\}\_\{o,f\}andpo,fn​u​l​l\>po,ff​a​l​s​ep^\{null\}\_\{o,f\}\>p^\{false\}\_\{o,f\}, setpo,f=0\.5p\_\{o,f\}=0\.5\.
3. 3\.Otherwise, normalize the true\-false probabilities:po,f=po,ft​r​u​epo,ft​r​u​e\+po,ff​a​l​s​ep\_\{o,f\}=\\frac\{p^\{true\}\_\{o,f\}\}\{p^\{true\}\_\{o,f\}\+p^\{false\}\_\{o,f\}\}\.

## Appendix BProof of\\crefthm:mlss

###### Definition 9\(Bit diffset\)\.

Lets,s′∈2Fs,s^\{\\prime\}\\in 2^\{F\}\. The*bit diffset*D⁡\(s,s′\)D\(s,s^\{\\prime\}\)is defined as the set of fluents that differ betweenssands′s^\{\\prime\}, i\.e\.,

D⁡\(s,s′\)=\{f∈F\|s⁡\(f\)≠s′​\(f\)\}D\(s,s^\{\\prime\}\)=\\\{f\\in F\|s\(f\)\\neq s^\{\\prime\}\(f\)\\\}

###### Definition 10\(Bit\-flip operator\)\.

Lets∈2Fs\\in 2^\{F\}andf∈Ff\\in F\. The*bit\-flip operator*Flip​\(s,f\)\\text\{Flip\}\(s,f\)returns a new states′∈2Fs^\{\\prime\}\\in 2^\{F\}such that:

∀f′∈Fs′​\(f′\)=\{1−s⁡\(f\)if​f′=fs⁡\(f′\)otherwise\\forall f^\{\\prime\}\\in F\\quad s^\{\\prime\}\(f^\{\\prime\}\)=\\begin\{cases\}1\-s\(f\)&\\text\{if \}f^\{\\prime\}=f\\\\ s\(f^\{\\prime\}\)&\\text\{otherwise\}\\end\{cases\}

###### Definition 11\(Canonical path\)\.

Lets,s′∈2Fs,s^\{\\prime\}\\in 2^\{F\}\. LetD⁡\(s,s′\)=\{f1,…,fn\}D\(s,s^\{\\prime\}\)=\\\{f\_\{1\},\.\.\.,f\_\{n\}\\\}where the fluents are numbered according to a fixed total ordering overFF\. The*canonical path*fromsstos′s^\{\\prime\}is the path of statess=s0→s1→…→sn=s′s=s\_\{0\}\\rightarrow s\_\{1\}\\rightarrow\.\.\.\\rightarrow s\_\{n\}=s^\{\\prime\}achieved by flipping the bits of states0s\_\{0\}one by one in the order of the fluents\. That is, fori∈\{1,…,n\}i\\in\\\{1,\.\.\.,n\\\}, definesi=Flip​\(si−1,fi\)s\_\{i\}=\\text\{Flip\}\(s\_\{i\-1\},f\_\{i\}\), froms0=ss\_\{0\}=sleading tosn=s′s\_\{n\}=s^\{\\prime\}\.

###### Lemma 12\.

In\\crefalg:mlss, letSextS^\{\\text\{ext\}\}denote the set of states that have been extracted from the heapQQthus far\. Then at the moment of max\-extraction fromQQ, it holds thatQ∪Sext=VisitedQ\\cup S^\{\\text\{ext\}\}=\\text\{Visited\}\.

###### Proof\.

Note that every insertion to the heap is accompanied by an insertion of the same state to the visited set\. All states that have ever been added to the heap are either still in the heap or have been extracted from it\. Since no state is ever removed from the visited set, the lemma holds\. ∎

###### Lemma 13\.

In\\crefalg:mlss, the probabilities of the states on the canonical path froms0s\_\{0\}to any statessare monotonically non\-increasing in the states’ unconstrained belief values, i\.e\.:

β~​\(s0\)≥…≥β~​\(sn\)=β~​\(s\)\\tilde\{\\beta\}\(s\_\{0\}\)\\geq\.\.\.\\geq\\tilde\{\\beta\}\(s\_\{n\}\)=\\tilde\{\\beta\}\(s\)

###### Proof\.

Assume by contradiction that there exists0<j≤n0<j\\leq nsuch that0≤β~​\(sj−1\)<β~​\(sj\)0\\leq\\tilde\{\\beta\}\(s\_\{j\-1\}\)<\\tilde\{\\beta\}\(s\_\{j\}\)\. Then all of the components that comprise the product inβ~​\(sj\)\\tilde\{\\beta\}\(s\_\{j\}\)are non\-zero\. Thus, we can safely divide by

∏f∈F∖\{fj\}βF​\(f\)sj−1​\(f\)​\(1−βF​\(f\)\)1−sj−1​\(f\)\\prod\_\{f\\in F\\setminus\\\{f\_\{j\}\\\}\}\\beta\_\{F\}\(f\)^\{s\_\{j\-1\}\(f\)\}\(1\-\\beta\_\{F\}\(f\)\)^\{1\-s\_\{j\-1\}\(f\)\}From here, we have:

β~​\(sj−1\)<β~​\(sj\)\\displaystyle\\tilde\{\\beta\}\(s\_\{j\-1\}\)<\\tilde\{\\beta\}\(s\_\{j\}\)⇔1\\displaystyle\\overset\{1\}\{\\iff\}∏f∈FβF​\(f\)sj−1​\(f\)​\(1−βF​\(f\)\)1−sj−1​\(f\)<∏f∈FβF​\(f\)sj​\(f\)​\(1−βF​\(f\)\)1−sj​\(f\)\\displaystyle\\prod\_\{f\\in F\}\\beta\_\{F\}\(f\)^\{s\_\{j\-1\}\(f\)\}\(1\-\\beta\_\{F\}\(f\)\)^\{1\-s\_\{j\-1\}\(f\)\}<\\prod\_\{f\\in F\}\\beta\_\{F\}\(f\)^\{s\_\{j\}\(f\)\}\(1\-\\beta\_\{F\}\(f\)\)^\{1\-s\_\{j\}\(f\)\}⇔2\\displaystyle\\overset\{2\}\{\\iff\}βF​\(fj\)sj−1​\(fj\)​\(1−βF​\(fj\)\)1−sj−1​\(fj\)<βF​\(fj\)sj​\(fj\)​\(1−βF​\(fj\)\)1−sj​\(fj\)\\displaystyle\\beta\_\{F\}\(f\_\{j\}\)^\{s\_\{j\-1\}\(f\_\{j\}\)\}\(1\-\\beta\_\{F\}\(f\_\{j\}\)\)^\{1\-s\_\{j\-1\}\(f\_\{j\}\)\}<\\beta\_\{F\}\(f\_\{j\}\)^\{s\_\{j\}\(f\_\{j\}\)\}\(1\-\\beta\_\{F\}\(f\_\{j\}\)\)^\{1\-s\_\{j\}\(f\_\{j\}\)\}⇔3\\displaystyle\\overset\{3\}\{\\iff\}βF​\(fj\)sj−1​\(fj\)​\(1−βF​\(fj\)\)1−sj−1​\(fj\)<βF​\(fj\)1−sj−1​\(fj\)​\(1−βF​\(fj\)\)sj−1​\(fj\)\\displaystyle\\beta\_\{F\}\(f\_\{j\}\)^\{s\_\{j\-1\}\(f\_\{j\}\)\}\(1\-\\beta\_\{F\}\(f\_\{j\}\)\)^\{1\-s\_\{j\-1\}\(f\_\{j\}\)\}<\\beta\_\{F\}\(f\_\{j\}\)^\{1\-s\_\{j\-1\}\(f\_\{j\}\)\}\(1\-\\beta\_\{F\}\(f\_\{j\}\)\)^\{s\_\{j\-1\}\(f\_\{j\}\)\}Transition 1 follows the definition ofβ~\\tilde\{\\beta\}in\\crefeq:calc\-unconst\-belief\. Transition 2 is a division by all components in the product except for the one corresponding tofjf\_\{j\}, which are non\-zero, which are equal sincesj−1​\(f\)=sj​\(f\)s\_\{j\-1\}\(f\)=s\_\{j\}\(f\)for allf≠fjf\\neq f\_\{j\}by the definition of the canonical path in\\crefdef:canon\-path\. Transition 3 follows from the definition of the bit\-flip operation in\\crefdef:bit\-flip, which states thatsj​\(fj\)=1−sj−1​\(fj\)s\_\{j\}\(f\_\{j\}\)=1\-s\_\{j\-1\}\(f\_\{j\}\)\.

Ifsj−1​\(fj\)=1s\_\{j\-1\}\(f\_\{j\}\)=1, then the above simplifies to

βF​\(fj\)1​\(1−βF​\(fj\)\)0<βF​\(fj\)0​\(1−βF​\(fj\)\)1\\displaystyle\\beta\_\{F\}\(f\_\{j\}\)^\{1\}\(1\-\\beta\_\{F\}\(f\_\{j\}\)\)^\{0\}<\\beta\_\{F\}\(f\_\{j\}\)^\{0\}\(1\-\\beta\_\{F\}\(f\_\{j\}\)\)^\{1\}⇒βF​\(fj\)<0\.5\\displaystyle\\Rightarrow\\beta\_\{F\}\(f\_\{j\}\)<0\.5Ifsj−1​\(fj\)=0s\_\{j\-1\}\(f\_\{j\}\)=0, then the above simplifies to

βF​\(fj\)0​\(1−βF​\(fj\)\)1<βF​\(fj\)1​\(1−βF​\(fj\)\)0\\displaystyle\\beta\_\{F\}\(f\_\{j\}\)^\{0\}\(1\-\\beta\_\{F\}\(f\_\{j\}\)\)^\{1\}<\\beta\_\{F\}\(f\_\{j\}\)^\{1\}\(1\-\\beta\_\{F\}\(f\_\{j\}\)\)^\{0\}⇒βF​\(fj\)\>0\.5\\displaystyle\\Rightarrow\\beta\_\{F\}\(f\_\{j\}\)\>0\.5Sincesj−1​\(fj\)=s0​\(fj\)s\_\{j\-1\}\(f\_\{j\}\)=s\_\{0\}\(f\_\{j\}\), then both cases contradict the definition ofs0s\_\{0\}, which for all fluents is defined ass0\(f\)=𝟙\[βF\(f\)\>0\.5\]s\_\{0\}\(f\)=\\mathbbm\{1\}\[\\beta\_\{F\}\(f\)\>0\.5\]\. ∎

###### Lemma 14\.

In\\crefalg:mlss, when a states∈2Fs\\in 2^\{F\}is extracted from the max\-heapQQ, then for alls′∈2Fs^\{\\prime\}\\in 2^\{F\}not yet extracted fromQQ, it holds thatβ~​\(s\)≥β~​\(s′\)\\tilde\{\\beta\}\(s\)\\geq\\tilde\{\\beta\}\(s^\{\\prime\}\)\.

###### Proof\.

LetSkext=\{s0,…,sk−1\}S^\{\\text\{ext\}\}\_\{k\}=\\\{s\_\{0\},\.\.\.,s\_\{k\-1\}\\\}be the set of the firstkkstates extracted fromQQ, numbered by the order in which they were extracted\. We must show that for allkkand for all statess∈Skexts\\in S^\{\\text\{ext\}\}\_\{k\}, and for alls′∉Skexts^\{\\prime\}\\notin S^\{\\text\{ext\}\}\_\{k\}, it holds thatβ⁡\(s\)≥β⁡\(s′\)\\beta\(s\)\\geq\\beta\(s^\{\\prime\}\)\. We do this by induction onkk\.

##### Basis:

Whenk=1k=1, this is the first iteration where the only value in the heap iss0s\_\{0\}\. By definition, for anys≠s0s\\neq s\_\{0\}, it holds thatβ~​\(s0\)≥β~​\(s\)\\tilde\{\\beta\}\(s\_\{0\}\)\\geq\\tilde\{\\beta\}\(s\)

##### Assumption:

Assume that for somekkit holds that for alls∈Skexts\\in S^\{\\text\{ext\}\}\_\{k\}ands′∉Skexts^\{\\prime\}\\notin S^\{\\text\{ext\}\}\_\{k\}we haveβ~​\(s\)≥β~​\(s′\)\\tilde\{\\beta\}\(s\)\\geq\\tilde\{\\beta\}\(s^\{\\prime\}\)\.

##### Induction Step:

LetSk\+1ext=\{s0,…,sk\}S^\{\\text\{ext\}\}\_\{k\+1\}=\\\{s\_\{0\},\.\.\.,s\_\{k\}\\\}\. By the induction assumption,Skext=Sk\+1ext∖\{sk\}S^\{\\text\{ext\}\}\_\{k\}=S^\{\\text\{ext\}\}\_\{k\+1\}\\setminus\\\{s\_\{k\}\\\}contains the topkkmost probable states, i\.e\., for alls∈Skexts\\in S^\{\\text\{ext\}\}\_\{k\}and for alls′∉Skexts^\{\\prime\}\\notin S^\{\\text\{ext\}\}\_\{k\}, it holds thatβ~​\(s\)≥β~​\(s′\)\\tilde\{\\beta\}\(s\)\\geq\\tilde\{\\beta\}\(s^\{\\prime\}\)\. It is left to show that for alls∉Sk\+1exts\\notin S^\{\\text\{ext\}\}\_\{k\+1\}, it holds thatβ~​\(sk\)≥β~​\(s\)\\tilde\{\\beta\}\(s\_\{k\}\)\\geq\\tilde\{\\beta\}\(s\)\.

Assume by contradiction that there exists a states∉Sk\+1exts\\notin S^\{\\text\{ext\}\}\_\{k\+1\}such thatβ~​\(s\)\>β~​\(sk\)\\tilde\{\\beta\}\(s\)\>\\tilde\{\\beta\}\(s\_\{k\}\)\. Thens∉Qs\\notin Qbecause otherwise it would have been extracted beforesks\_\{k\}\. By\\crefle:res\-vis,sshas not yet been visited\.

On the canonical path froms0s\_\{0\}tosn=ss\_\{n\}=s, sinces0s\_\{0\}has been visited andsn=ss\_\{n\}=shas not yet been visited, there exists0<j≤n0<j\\leq nsuch thatsjs\_\{j\}has not yet been visited andsj−1s\_\{j\-1\}has\.

- •Sincesj−1s\_\{j\-1\}is in the visited set, then by\\crefle:res\-vis, it is either in the heap or has been extracted from the heap\. It cannot have been extracted from the heap because then it would have been expanded, andsjs\_\{j\}would have been visited\. Therefore,sj−1s\_\{j\-1\}is in the heap\.
- •Sincesks\_\{k\}was extracted butsj−1s\_\{j\-1\}was not, it follows thatβ~​\(sk\)≥β~​\(sj−1\)\\tilde\{\\beta\}\(s\_\{k\}\)\\geq\\tilde\{\\beta\}\(s\_\{j\-1\}\)\.
- •By\\crefle:path\-mono,β~​\(sj−1\)≥β~​\(sn\)=β~​\(s\)\\tilde\{\\beta\}\(s\_\{j\-1\}\)\\geq\\tilde\{\\beta\}\(s\_\{n\}\)=\\tilde\{\\beta\}\(s\)\.

Putting it all together, we get:

β~​\(sk\)≥β~​\(sj−1\)≥β~​\(s\)\>β~​\(sk\)\\tilde\{\\beta\}\(s\_\{k\}\)\\geq\\tilde\{\\beta\}\(s\_\{j\-1\}\)\\geq\\tilde\{\\beta\}\(s\)\>\\tilde\{\\beta\}\(s\_\{k\}\)which is a contradiction\. Thus, for alls∉Sk\+1exts\\notin S^\{\\text\{ext\}\}\_\{k\+1\}, it holds thatβ~​\(sk\)≥β~​\(s\)\\tilde\{\\beta\}\(s\_\{k\}\)\\geq\\tilde\{\\beta\}\(s\)\. ∎

MLSS Theorem:In\\crefalg:mlss, when a constraint\-satisfying statessis extracted from the heapQQ, then for alls′∉bs^\{\\prime\}\\notin bit holds thatβ⁡\(s\)≥β⁡\(s′\)\\beta\(s\)\\geq\\beta\(s^\{\\prime\}\), whereβ\\betais the belief computed by\\crefeq:calc\-belief\.

###### Proof\.

Letssbe a constraint\-satisfying state extracted from the heap at some iteration\. We must show that for alls′∉bs^\{\\prime\}\\notin b, it holds thatβ⁡\(s\)≥β⁡\(s′\)\\beta\(s\)\\geq\\beta\(s^\{\\prime\}\)\.

Ifs′s^\{\\prime\}violates the constraints, then triviallyβ⁡\(s′\)=0≤β⁡\(s\)\\beta\(s^\{\\prime\}\)=0\\leq\\beta\(s\)\. Otherwise, note thatbbis comprised of all constraint\-satisfying states that were extracted from the heap beforess\. Therefore,s′s^\{\\prime\}has not yet been extracted from the heap\. By\\crefle:order, we have:

β~​\(s\)≥β~​\(s′\)⇔β~​\(s\)Z≥β~​\(s′\)Z⇔β⁡\(s\)≥β⁡\(s′\)\\tilde\{\\beta\}\(s\)\\geq\\tilde\{\\beta\}\(s^\{\\prime\}\)\\iff\\frac\{\\tilde\{\\beta\}\(s\)\}\{Z\}\\geq\\frac\{\\tilde\{\\beta\}\(s^\{\\prime\}\)\}\{Z\}\\iff\\beta\(s\)\\geq\\beta\(s^\{\\prime\}\)Thus, the theorem holds for alls′∉bs^\{\\prime\}\\notin b\. ∎

## Appendix CProof of\\crefthm:efficient

### C\.1Time Complexity\.

###### Claim 1\.

The time complexity of\\crefalg:mlss isO⁡\(\|F\|​k​log⁡\(\|F\|​k\)\)O\(\|F\|k\\log\(\|F\|k\)\)

###### Proof\.

Pre\-iteration cost\.In lines[1](https://arxiv.org/html/2609.16884#algx1.l1)\-[5](https://arxiv.org/html/2609.16884#algx1.l5)of the algorithm, we linearly computes0s\_\{0\}and its probability, and initialize collections with at most one item\. This requiresO⁡\(\|F\|\)O\(\|F\|\)operations\.

Inner\-iteration cost\.The internalforloop in line[12](https://arxiv.org/html/2609.16884#algx1.l12)consists of a bit\-flip, a “visited” check, an insertion to the visited set, and an insertion to the heap\. Using random access, the bit flip isO⁡\(1\)O\(1\)\. Checking membership in the visited set isO⁡\(1\)O\(1\)\. Inserting into the visited isO⁡\(log⁡\(M\)\)O\(\\log\(M\)\)whereMMis the size of the set\. The heap insertion isO⁡\(log⁡\(N\)\)O\(\\log\(N\)\)whereNNis the size of the heap\. Assuming none of the states are visited \(worst case\), then we requireO⁡\(\|F\|​\(log⁡\(N\)\+log⁡\(M\)\)\)O\(\|F\|\(\\log\(N\)\+\\log\(M\)\)\)for all iterations\. We must also acknowledge the time to compute the probability at each iteration\. If naively implemented, this would takeO⁡\(\|F\|\)O\(\|F\|\), meaning throughout the iteration, this would takeO⁡\(\|F\|2\)O\(\|F\|^\{2\}\)\. However, by updating the probability incrementally according to only the changed bit \(divide by unflipped value and multiply by flipped value\), this operation takesO⁡\(1\)O\(1\)\.

Outer\-iteration cost\.Thewhileloop in line[6](https://arxiv.org/html/2609.16884#algx1.l6)consists of a max extraction from the heap, an insertion of this value tobb, and the internalforloop\. Sincebbis at most sizekk, the insertion can be implemented inO⁡\(log⁡\(k\)\)O\(\\log\(k\)\)\. The max extraction from the heap requiresO⁡\(log⁡\(M\)\)O\(\\log\(M\)\)whereMMis the size of the heap\. Thewhileconditions are checkable inO⁡\(1\)O\(1\)\. The innerforloop isO⁡\(\|F\|​\(log⁡\(N\)\+log⁡\(M\)\)\)O\(\|F\|\(\\log\(N\)\+\\log\(M\)\)\)\. Considering that at most\|F\|\|F\|values are inserted into the visited set and heap at every iteration, thenM=N=\|F\|​kM=N=\|F\|kat most\. Overall, each iteration in thewhileloop requires:

O⁡\(log⁡\(k\)\)\+O⁡\(log⁡\(M\)\)\+O⁡\(\|F\|​\(log⁡\(N\)\+log⁡\(M\)\)\)\\displaystyle O\(\\log\(k\)\)\+O\(\\log\(M\)\)\+O\(\|F\|\(\\log\(N\)\+\\log\(M\)\)\)=\\displaystyle=O⁡\(log⁡\(k\)\)\+O⁡\(\|F\|​\(log⁡\(\|F\|​k\)\+log⁡\(\|F\|​k\)\)\)\\displaystyle O\(\\log\(k\)\)\+O\(\|F\|\(\\log\(\|F\|k\)\+\\log\(\|F\|k\)\)\)=\\displaystyle=O⁡\(\|F\|​log⁡\(\|F\|​k\)\)\\displaystyle O\(\|F\|\\log\(\|F\|k\)\)There are at mostkkiterations, so the overall time complexity of the while loop isO⁡\(\|F\|​k​log⁡\(\|F\|​k\)\)O\(\|F\|k\\log\(\|F\|k\)\)\.

Since the pre\-iteration costs are negligible compared to the iteration cost, the final time upper\-bound complexity stands atT⁡\(F,k\)=O⁡\(\|F\|​k​log⁡\(\|F\|​k\)\)T\(F,k\)=O\(\|F\|k\\log\(\|F\|k\)\)\. ∎

### C\.2Space Complexity

###### Claim 2\.

The space complexity of\\crefalg:mlss isO⁡\(\|F\|2​k\)O\(\|F\|^\{2\}k\)bits\.

###### Proof\.

As seen in the proof of time complexity, we store the following values at any one time:

- •The visited set, containingO⁡\(\|F\|​k\)O\(\|F\|k\)states\.
- •The heap, containingO⁡\(\|F\|​k\)O\(\|F\|k\)states\.

Each state can be represented using a bitmask of\|F\|\|F\|bits\. ThereforeS⁡\(F,k\)=O⁡\(\|F\|2​k\)S\(F,k\)=O\(\|F\|^\{2\}k\)bits\. ∎

## Appendix DProof of Finite Step Convergence

In this section, we prove\\crefthm:fin\-step via\\crefthm:calib\.

### D\.1Proof of\\crefthm:calib

Theorem Statement\.Letθ∈\(0,1\]\\theta\\in\(0,1\], let𝒞\\mathcal\{C\}be a set of constraints overFF, and lets∈2Fs\\in 2^\{F\}satisfy𝒞\\mathcal\{C\}\. For everyβF∈\[0,1\]F\\beta\_\{F\}\\in\[0,1\]^\{F\}, ifδ⁡\(βF,s\)<θ\\delta\(\\beta\_\{F\},s\)<\\theta, thens∈M​L​S​S​\(βF,θ,𝒞\)s\\in MLSS\(\\beta\_\{F\},\\theta,\\mathcal\{C\}\)\.

###### Proof\.

Lets∈2Fs\\in 2^\{F\}satisfy𝒞\\mathcal\{C\}and letβF∈\[0,1\]F\\beta\_\{F\}\\in\[0,1\]^\{F\}\. For simplicity, we denoteδ=δ⁡\(βF,s\)\\delta=\\delta\(\\beta\_\{F\},s\)\.

Letεf=\|βf−s⁡\(f\)\|\\varepsilon\_\{f\}=\|\\beta\_\{f\}\-s\(f\)\|be a single fluent belief error, and letW⁡\(s\)=∏f∈Fβfs⁡\(f\)​\(1−βf\)1−s⁡\(f\)W\(s\)=\\prod\_\{f\\in F\}\\beta\_\{f\}^\{s\(f\)\}\(1\-\\beta\_\{f\}\)^\{1\-s\(f\)\}be the unnormalized probability weight of statess\.

Ifs⁡\(f\)=1s\(f\)=1then

εf=\|βf−s⁡\(f\)\|=1−βf\\displaystyle\\varepsilon\_\{f\}=\|\\beta\_\{f\}\-s\(f\)\|=1\-\\beta\_\{f\}⇒βf=1−εf\\displaystyle\\Rightarrow\\beta\_\{f\}=1\-\\varepsilon\_\{f\}and ifs⁡\(f\)=0s\(f\)=0then

εf=\|βf−s⁡\(f\)\|=βf\\displaystyle\\varepsilon\_\{f\}=\|\\beta\_\{f\}\-s\(f\)\|=\\beta\_\{f\}⇒1−βf=1−εf\\displaystyle\\Rightarrow 1\-\\beta\_\{f\}=1\-\\varepsilon\_\{f\}Then by the Weierstrass product inequality, the unnormalized weight assigned tossis:

W⁡\(s\)=∏f∈F\(1−εf\)≥1−∑f∈Fεf=1−δW\(s\)=\\prod\_\{f\\in F\}\(1\-\\varepsilon\_\{f\}\)\\geq 1\-\\sum\_\{f\\in F\}\\varepsilon\_\{f\}=1\-\\delta
β\\betais normalized by a normalizing factor0<Z≤10<Z\\leq 1\. Thus:

β⁡\(s\)=W⁡\(s\)Z≥W⁡\(s\)≥1−δ\\beta\(s\)=\\frac\{W\(s\)\}\{Z\}\\geq W\(s\)\\geq 1\-\\delta
Assume by contradiction thats∉M​L​S​S​\(βF,θ,𝒞\)s\\notin MLSS\(\\beta\_\{F\},\\theta,\\mathcal\{C\}\)\. Then

β⁡\(s\)≤∑s′∉M​L​S​S​\(βF,θ,𝒞\)β⁡\(s′\)≤1−θ\.\\beta\(s\)\\leq\\sum\_\{s^\{\\prime\}\\notin MLSS\(\\beta\_\{F\},\\theta,\\mathcal\{C\}\)\}\\beta\(s^\{\\prime\}\)\\leq 1\-\\theta\.
From the previous inequality:

1−θ≥β⁡\(s\)≥1−δ\\displaystyle 1\-\\theta\\geq\\beta\(s\)\\geq 1\-\\delta⇒\\displaystyle\\Rightarrowδ≥θ\\displaystyle\\delta\\geq\\theta
This contradicts the theorem’s assumption thatδ<θ\\delta<\\theta, and thusssmust be in the[mlss](https://arxiv.org/html/2609.16884#id8)\.

∎

### D\.2Proof of\\crefthm:fin\-step

Theorem Statement:Letρ\>0\\rho\>0be the minimum visibility rate\. If the[vlm](https://arxiv.org/html/2609.16884#id2)is weakly calibrated with error marginγ\\gamma, then there existsTTsuch that a conformant plan for the[mlss](https://arxiv.org/html/2609.16884#id8)is satisficing from the true current state\.

###### Proof\.

Letlf,tl\_\{f,t\}be the log odds of the correct assignment offfat timettof the evidence provided by the[vlm](https://arxiv.org/html/2609.16884#id2)\. Since the[vlm](https://arxiv.org/html/2609.16884#id2)is weakly calibrated, then:

pcorrect,t−\(1−pcorrect,t\)≥pcorrect,t−pincorrect,t≥γ\\displaystyle p\_\{\\text\{correct\},t\}\-\(1\-p\_\{\\text\{correct\}\},t\)\\geq p\_\{\\text\{correct\},t\}\-p\_\{\\text\{incorrect\},t\}\\geq\\gamma⇒\\displaystyle\\Rightarrowpcorrect,t≥γ2\+0\.5\\displaystyle p\_\{\\text\{correct\},t\}\\geq\\frac\{\\gamma\}\{2\}\+0\.5
This implies that1−pcorrect,t≤0\.5−γ21\-p\_\{\\text\{correct\},t\}\\leq 0\.5\-\\frac\{\\gamma\}\{2\}\. Thus:

pcorrect,t1−pcorrect,t≥0\.5\+γ20\.5−γ2\\displaystyle\\frac\{p\_\{\\text\{correct\},t\}\}\{1\-p\_\{\\text\{correct\},t\}\}\\geq\\frac\{0\.5\+\\frac\{\\gamma\}\{2\}\}\{0\.5\-\\frac\{\\gamma\}\{2\}\}⇒\\displaystyle\\Rightarrowlog⁡\(pcorrect,t1−pcorrect,t\)≥log⁡\(0\.5\+γ20\.5−γ2\)\\displaystyle\\log\\left\(\\frac\{p\_\{\\text\{correct\},t\}\}\{1\-p\_\{\\text\{correct\},t\}\}\\right\)\\geq\\log\\left\(\\frac\{0\.5\+\\frac\{\\gamma\}\{2\}\}\{0\.5\-\\frac\{\\gamma\}\{2\}\}\\right\)⇒\\displaystyle\\Rightarrowlf,t≥log⁡\(0\.5\+γ20\.5−γ2\)\>0\\displaystyle l\_\{f,t\}\\geq\\log\\left\(\\frac\{0\.5\+\\frac\{\\gamma\}\{2\}\}\{0\.5\-\\frac\{\\gamma\}\{2\}\}\\right\)\>0
ThenLLis bounded by a strictly positive constant\. DenoteC=log⁡\(0\.5\+γ20\.5−γ2\)C=\\log\\left\(\\frac\{0\.5\+\\frac\{\\gamma\}\{2\}\}\{0\.5\-\\frac\{\\gamma\}\{2\}\}\\right\)\.

LetLf,tL\_\{f,t\}be the log odds of the correct assignment offfat timettaccording to factored beliefβF,t\\beta\_\{F,t\}\. The logarithmic pooling update rule isLf,t=Lf,t−1\+lf,tL\_\{f,t\}=L\_\{f,t\-1\}\+l\_\{f,t\}\. Assume W\.L\.O\.G\. that the initial beliefβF,0\\beta\_\{F,0\}is uniform \(because in any case, it is constant\)\. Since we only update fluents that are visible, the log odds value at timeTTis:

Lf,T\\displaystyle L\_\{f,T\}=log⁡\(βf,01−βf,0\)\+∑t=1T𝟙f​\(t\)⋅lf,t\\displaystyle=\\log\\left\(\\frac\{\\beta\_\{f,0\}\}\{1\-\\beta\_\{f,0\}\}\\right\)\+\\sum\_\{t=1\}^\{T\}\\mathbb\{1\}\_\{f\}\(t\)\\cdot l\_\{f,t\}=∑t=1T𝟙f​\(t\)⋅lf,t\\displaystyle=\\sum\_\{t=1\}^\{T\}\\mathbb\{1\}\_\{f\}\(t\)\\cdot l\_\{f,t\}where𝟙f​\(t\)\\mathbb\{1\}\_\{f\}\(t\)is an indicator function for fluentffbeing visible at timesteptt\. By the definition ofρ\\rho, all fluents appear at leastρ​T\\rho Ttimes withinTTtimesteps\. Thus:

Lf,T≥ρ​T⋅CL\_\{f,T\}\\geq\\rho T\\cdot C
Letδt\\delta\_\{t\}be the cumulative factored belief error at timett, and letεf=\|βf−s∗​\(f\)\|=1−pcorrect\\varepsilon\_\{f\}=\|\\beta\_\{f\}\-s^\{\*\}\(f\)\|=1\-p\_\{\\text\{correct\}\}wheres∗s^\{\*\}is the true current state\. Then:

Lf,t\\displaystyle L\_\{f,t\}=log⁡\(pcorrect1−pcorrect\)\\displaystyle=\\log\\left\(\\frac\{p\_\{\\text\{correct\}\}\}\{1\-p\_\{\\text\{correct\}\}\}\\right\)Lf,t\\displaystyle L\_\{f,t\}=log⁡\(1−εf,tεf,t\)\\displaystyle=\\log\\left\(\\frac\{1\-\\varepsilon\_\{f,t\}\}\{\\varepsilon\_\{f,t\}\}\\right\)eLf,t\\displaystyle e^\{L\_\{f,t\}\}=1−εf,tεf,t\\displaystyle=\\frac\{1\-\\varepsilon\_\{f,t\}\}\{\\varepsilon\_\{f,t\}\}εf,t\\displaystyle\\varepsilon\_\{f,t\}=11\+eLf,t≤e−Lf,t≤e−ρT⋅C\\displaystyle=\\frac\{1\}\{1\+e^\{L\_\{f,t\}\}\}\\leq e^\{\-L\_\{f,t\}\}\\leq e^\{\-\\rho T\\cdot C\}
We want the cumulative factored belief error to be less thanθ\\theta\. Note that:

δt=∑f∈Fεf,t≤∑f∈Fe−ρT⋅C=\|F\|⋅e−ρT⋅C\\displaystyle\\delta\_\{t\}=\\sum\_\{f\\in F\}\\varepsilon\_\{f,t\}\\leq\\sum\_\{f\\in F\}e^\{\-\\rho T\\cdot C\}=\|F\|\\cdot e^\{\-\\rho T\\cdot C\}Then it is enough to findTTsuch that

\|F\|⋅e−ρT⋅C<θ\\displaystyle\|F\|\\cdot e^\{\-\\rho T\\cdot C\}<\\theta⇔\\displaystyle\\Leftrightarrow−ρT⋅C<log\(θ\|F\|\)\\displaystyle\-\\rho T\\cdot C<\\log\\left\(\\frac\{\\theta\}\{\|F\|\}\\right\)⇔\\displaystyle\\LeftrightarrowT\>log⁡\(\|F\|\)−log⁡\(θ\)ρ⋅C\\displaystyle T\>\\frac\{\\log\(\|F\|\)\-\\log\(\\theta\)\}\{\\rho\\cdot C\}
Since all values\|F\|,θ,C,\|F\|,\\theta,C,andρ\\rhoare all constant, there exists a finiteTTsuch that this inequality always holds\. Therefore, after theTTth belief update,s∗s^\{\*\}is in the[mlss](https://arxiv.org/html/2609.16884#id8), and so a conformant plan for all states in the[mlss](https://arxiv.org/html/2609.16884#id8)is also a satisficing plan froms∗s^\{\*\}\. ∎

## Appendix EProof of\\crefthm:safety

An unsafe action is one for which the planner did not verify the preconditions\. As inspired by[Shani and Brafman \(2011\)](https://arxiv.org/html/2609.16884#bib.bib30), we define an action as safe if its preconditions hold for all states in the[mlss](https://arxiv.org/html/2609.16884#id8)\. With the replanning strategy in\\crefalg:replan, we can provide a safety guarantee compared to a[vlm](https://arxiv.org/html/2609.16884#id2)\-as\-grounder policy\([Merler et al\., 2025](https://arxiv.org/html/2609.16884#bib.bib21)\), denotedπd​e​t\\pi\_\{det\}, that always plans from the most probable state\.

###### Theorem 15\.

Letunsafe​\(π\)\\text\{unsafe\}\(\\pi\)denote the event that policyπ\\piexecutes an unsafe action\. Then,

Pr⁡\(unsafe​\(πd​e​t\)\)≥Pr⁡\(unsafe​\(πc​p​p\)\)\+\(θ−β⁡\(sm​a​x\)\)s\.t\.sm​a​x∈arg​maxs⁡β​\(s\)\\Pr\(\\text\{unsafe\}\(\\pi\_\{det\}\)\)\\geq\\Pr\(\\text\{unsafe\}\(\\pi\_\{cpp\}\)\)\+\(\\theta\-\\beta\(s\_\{max\}\)\)\\ \\ s\.t\.\\ \\ s\_\{max\}\\in\\argmax\_\{s\}\\beta\(s\)

###### Proof\.

For beliefβ\\beta,πd​e​t\\pi\_\{det\}generates a plan that is verified to be valid for the most likely state, denotedsm​a​xs\_\{max\}\. Thus,

Pr⁡\(unsafe​\(πd​e​t\)\)=1−β⁡\(sm​a​x\)\\Pr\(\\text\{unsafe\}\(\\pi\_\{det\}\)\)=1\-\\beta\(s\_\{max\}\)
Policyπc​p​p\\pi\_\{cpp\}generates a plan that is verified for all states in the[mlss](https://arxiv.org/html/2609.16884#id8), denotedβθ\\beta\_\{\\theta\}\. By the definition ofβθ\\beta\_\{\\theta\}:

∑s∈βθβ⁡\(s\)≥θ\\displaystyle\\sum\_\{s\\in\\beta\_\{\\theta\}\}\\beta\(s\)\\geq\\theta⇒\\displaystyle\\RightarrowPr⁡\(unsafe​\(πc​p​p\)\)=1−∑s∈βθβ⁡\(s\)≤1−θ\\displaystyle\\Pr\(\\text\{unsafe\}\(\\pi\_\{cpp\}\)\)=1\-\\sum\_\{s\\in\\beta\_\{\\theta\}\}\\beta\(s\)\\leq 1\-\\theta
From here:

Pr⁡\(unsafe​\(πd​e​t\)\)\\displaystyle\\Pr\(\\text\{unsafe\}\(\\pi\_\{det\}\)\)=\\displaystyle=1−β⁡\(sm​a​x\)\\displaystyle 1\-\\beta\(s\_\{max\}\)=\\displaystyle=\(1−θ\)\+\(θ−β⁡\(sm​a​x\)\)\\displaystyle\(1\-\\theta\)\+\(\\theta\-\\beta\(s\_\{max\}\)\)≥\\displaystyle\\geqPr⁡\(unsafe​\(πc​p​p\)\)\+\(θ−β⁡\(sm​a​x\)\)\\displaystyle\\Pr\(\\text\{unsafe\}\(\\pi\_\{cpp\}\)\)\+\(\\theta\-\\beta\(s\_\{max\}\)\)=\\displaystyle=Pr⁡\(unsafe​\(πc​p​p\)\)\+\(θ−maxs∈S⁡β⁡\(s\)\)\\displaystyle\\Pr\(\\text\{unsafe\}\(\\pi\_\{cpp\}\)\)\+\(\\theta\-\\max\_\{s\\in S\}\\beta\(s\)\)∎

\\cref

thm:safety states that our[cpp](https://arxiv.org/html/2609.16884#id6)replanning policy is at least as safe as the VLM\-as\-grounder policy as long as the planning threshold is greater than the probability of the most likely state\. We see that the safety advantage of our method grows exponentially with the entropy of the[vlm](https://arxiv.org/html/2609.16884#id2)\-induced belief\. Althoughθ−β⁡\(sm​a​x\)\\theta\-\\beta\(s\_\{max\}\)can be negative ifβ⁡\(sm​a​x\)\>θ\\beta\(s\_\{max\}\)\>\\theta, in practice\\crefalg:mlss will select only this maximizer, making the resulting plan equivalent to that of the VLM\-as\-grounder policy\.

## Appendix FViPlan\-HH Domain and Evaluated Tasks

ViPlan\-HH\([Merler et al\., 2025](https://arxiv.org/html/2609.16884#bib.bib21)\)is a simulated household robotics domain built on iGibson\([Li et al\., 2022a](https://arxiv.org/html/2609.16884#bib.bib16)\)\. The agent is a mobile manipulator with an egocentric RGB camera and a single gripper\. Each problem specifies a household scene, a set of typed objects, and a goal condition\. The robot must navigate to relevant objects, manipulate movable items, and interact with containers such as drawers, cabinets, shelves, doors, and boxes\.

##### Symbolic domain\.

The high\-level model is represented in[pddl](https://arxiv.org/html/2609.16884#id9)\. Objects are typed as general objects, movable objects, containers, sliceable objects, and slicers\. The main predicates describe reachability, grasp state, container state, object placement, containment, adjacency, and slicing, using predicates such asreachable,holding,open,ontop,inside,nextto, andsliced\. The action set containsnavigate\-to,grasp,place\-on,place\-next\-to,place\-inside,open\-container,close\-container, andslice\. Sample domain and problem files are shown in\\crefap:pddl\.

The[pddl](https://arxiv.org/html/2609.16884#id9)state is a high\-level abstraction of the simulator state\. Navigation makes a target object reachable and normally makes other objects unreachable, reflecting the robot’s local viewpoint and manipulation range\. Opening a reachable container makes its contents reachable, while closing a container hides them again\. Placement actions require holding the moved object and reaching the target support or container\. This abstraction captures the task\-relevant structure while delegating low\-level geometric execution to the simulator interface\.

##### Observations and partial observability\.

At each step the agent observes an RGB image from the robot’s current viewpoint\. Objects outside the field of view, inside closed containers, or occluded by scene geometry are not directly observable\. The original ViPlan\-HH implementation supplements some non\-visible predicates with privileged simulator state\. We remove this privileged information in our experiments\. As a result, hidden objects and unobserved relations must be handled through belief rather than by direct access to ground truth, making the setting a true partially observable visual planning problem\.

##### Evaluated task families\.

The quantitative experiments use the ViPlan\-HH difficulty splits, but only the task families for which the conformant\-planning backend could be evaluated reliably\. The evaluated task families are listed in\\creftab:domain\-tasks\. Task identifiers match the benchmark task names used by the code\.

Table 2:ViPlan\-HH task families used in the quantitative evaluation\.The remaining ViPlan\-HH task families were not included in the quantitative table because they exposed implementation\-level nontermination in the Unified Planning CPOR backend used for conformant planning\([Maliah et al\., 2022](https://arxiv.org/html/2609.16884#bib.bib20)\)\. In these cases, the generated planning calls did not reliably return either a plan or a failure\. The issue was in the planner stack rather than in the visual\-planning policy\. In particular, CPOR is invoked through the Python experiment harness but executes solver code in a separate \.NET runtime, so Python\-level timeouts did not consistently terminate the underlying solver process\. This made the affected tasks unsuitable for automated, reproducible evaluation with the conformant\-planning component\.

We therefore report results on the largest subset of ViPlan\-HH task families that could be run reliably under the same evaluation protocol for all compared methods\. This filtering was based on backend evaluability, not on task outcome\. The retained subset still spans all three official difficulty levels and includes tasks with hidden objects, container manipulation, object rearrangement, and long\-horizon household goals\. Excluding planner\-backend hangs avoids conflating third\-party solver nontermination with the visual planning questions studied in this paper\.

## Appendix GViPlan\-HH PDDL Files

### G\.1Domain File

\(define\(domainigibson\)

\(:requirements:strips:typing:negative\-preconditions:conditional\-effects:equality\)

\(:types

containermovable\-object

sliceableslicer\-movable

\)

\(:predicates

;;Agentpredicates

\(reachable?o\-object\)

\(holding?m\-movable\)

;;Objectattributes

\(open?c\-container\)

;;Objectrelations

\(ontop?o1\-object?o2\-object\);;noassumptionsonthetypesofobjectsthatcanbeontoporbelowothers

\(inside?o\-object?c\-container\);;onlycontainerscancontainobjects

\(nextto?o1\-object?o2\-object\);;noassumptionsonthetypesofobjectsthatcanbenexttoeachother

;;Specificobjectattributes

\(sliced?s\-sliceable\);;\(e\.g\.slicedtomato\)

\)

\(:actiongrasp

:parameters\(?m\-movable\)

:precondition\(and

\(forall

\(?x\-movable\)

\(not\(holding?x\)\)\);;Agentmustnotbeholdinganything

;;\(forall

;;\(?x\-movable\)

;;\(not\(ontop?x?m\)\)\);;Can’tgraspanobjectthathassomethingontopofit

\)

:effect\(and

\(when

\(reachable?m\)

\(and

\(holding?m\)

\(forall

\(?y\-object\)

\(and

\(not\(ontop?m?y\)\);;Ifgraspedobjectisontopofsomething,itisnolongerontopofit

\(not\(nextto?m?y\)\)\)\);;Samefornextto

\)

\)

\(forall

\(?c\-container\)

\(when

\(and

\(reachable?m\)

\(inside?m?c\)

\)

\(not\(inside?m?c\)\)\)\);;Ifmwasinacontainer,it’snotanymore

\)

\)

\(:actionplace\-on

:parameters\(?m\-movable?o2\-object\)

:precondition\(and

\(reachable?o2\)

\)

:effect\(and

\(when

\(holding?m\)

\(and

\(ontop?m?o2\)

\(not\(holding?m\)\)

\)

\)

\)

\)

\(:actionplace\-next\-to

:parameters\(?m\-movable?o2\-object\)

:precondition\(and

\(reachable?o2\)

\)

:effect

\(when

\(holding?m\)

\(and

\(nextto?m?o2\)

\(not\(holding?m\)\)

\)

\)

\)

\(:actionplace\-inside

:parameters\(?m\-movable?c\-container\)

:precondition\(and

\(reachable?c\)

\(open?c\)

\)

:effect

\(when

\(holding?m\)

\(and

\(inside?m?c\)

\(not\(holding?m\)\)

\)

\)

\)

\(:actionopen\-container

:parameters\(?c\-container\)

:precondition\(and

\(forall

\(?x\-movable\)

\(not\(holding?x\)\)\);;Agentmustnotbeholdinganything

\)

:effect\(and

\(when

\(reachable?c\)

\(open?c\)

\)

\(forall

\(?o\-object\)

\(when

\(and

\(reachable?c\)

\(inside?o?c\)

\)

\(reachable?o\)\)\);;Allobjectsinsidethecontainerarereachable

\)

\)

\(:actionclose\-container

:parameters\(?c\-container\)

;:precondition\(\)

:effect\(and

\(when

\(reachable?c\)

\(not\(open?c\)\)

\)

\(forall

\(?o\-object\)

\(when

\(inside?o?c\)

\(not\(reachable?o\)\)

\);;Allobjectsinsidethecontainerareunreachable

\)

\)

\)

\(:actionnavigate\-to

:parameters\(?o\-object\)

:precondition\(and

;;don’tnavigate\-tothingshiddeninaclosedcontainer

\(forall

\(?c\-container\)

\(or

\(not\(inside?o?c\)\)

\(open?c\)

\)

\)

\)

:effect\(and

\(reachable?o\);;maketargetobjectreachable

\(forall

\(?x\-object\)

\(when

\(not\(=?x?o\)\);;condition

\(not\(reachable?x\)\)\)\);;effect

;;Also,ifthereexistsacontainerwhichis?oandthatit’sopen,

;;settheobjectsinsideasreachable

\(forall

\(?c\-container?x\-object\)

\(when

\(and

\(=?c?o\)

\(open?c\)

\(inside?x?c\)

\)

\(reachable?x\)\)\)

\)

\)

\(:actionslice

:parameters\(?o\-sliceable?s\-slicer\)

:precondition\(and

\(holding?s\)

\(reachable?o\)

\(not\(sliced?o\)\)

\)

:effect\(and

\(sliced?o\)

\)

\)

\)

### G\.2Example “Sorting Books” Problem File

\(define\(problemsorting\_books\_0\)

\(:domainigibson\)

\(:objects

hardback\_1\-movable

table\_1\-object

shelf\_1\-object

\)

\(:init

\(ontophardback\_1table\_1\)

\)

\(:goal

\(and

\(ontophardback\_1shelf\_1\)

\)

\)

\)

### G\.3Example “Cleaning Out Drawers” Problem File

\(define\(problemcleaning\_out\_drawers\_0\)

\(:domainigibson\)

\(:objects

bowl\_1\-movable

cabinet\_1\-container

sink\_1\-object

\)

\(:init

\(insidebowl\_1cabinet\_1\)

\(not\(opencabinet\_1\)\)

\)

\(:goal

\(and

\(ontopbowl\_1sink\_1\)

\)

\)

\)

## Appendix HUse Case: Full Details

### H\.1Baselines

We compare three approaches for integrating[vlm](https://arxiv.org/html/2609.16884#id2)into a planning loop, depicted in\\creffig:methods:theirs,fig:methods:ours\. These are[vlm](https://arxiv.org/html/2609.16884#id2)\-as\-planner,[vlm](https://arxiv.org/html/2609.16884#id2)\-as\-grounder, and[sc](https://arxiv.org/html/2609.16884#id11)\(ours\)\. The full implementation details are provided in\\crefap:baselines\.

### H\.2Deeper Analysis

#### H\.2\.1Scenario 1: Hidden Object

In the*cleaning out drawers*task, the robot must place a bowl into the sink, but the bowl is initially out of view and located inside a closed cabinet \(see\\creffig:example:kitchen\)\. The VLM\-P baseline consistently mispredicts the initial state, assuming the bowl is directly reachable\. As a result, it generates the following plan:`navigate\-to\(bowl\_1\)`,`grasp\(bowl\_1\)`,`navigate\-to\(sink\_1\)`,`place\-on\(bowl\_1, sink\_1\)`\. This plan inevitably fails when the bowl is inside a cabinet, since grasping it requires opening the cabinet first\.

In contrast,[sc](https://arxiv.org/html/2609.16884#id11)assigns non\-zero probability to the bowl being hidden, producing the plan:`navigate\-to\(cabinet\_1\)`,`open\-container\(cabinet\_1\)`,`navigate\-to\(bowl\_1\)`,`grasp\(bowl\_1\)`,`navigate\-to\(sink\_1\)`,`place\-on\(bowl\_1, sink\_1\)`\. This plan is valid whether the bowl is actually inside the cabinet or not\. By choosing a robust plan that includes opening the cabinet,[sc](https://arxiv.org/html/2609.16884#id11)avoids premature commitment and expands the set of possible successful initial states, reducing the need for replanning\.

#### H\.2\.2Scenario 2: Misleading Observation

In the*sorting books*task, the robot must place a hardback book onto a shelf\. The initial camera image can be misleading: objects near the gripper may appear as if they are being held \(\\creffig:example:radio\)\. Under these conditions, the[vlm](https://arxiv.org/html/2609.16884#id2)\-as\-grounder baseline often incorrectly interprets the scene and concludes that the robot is already holding the hardback\. This misinterpretation causes the robot to generate the following plan:`navigate\-to\(shelf\_1\)`,`place\-on\(hardback\_1, shelf\_1\)`\. Because the robot is not actually holding thehardback\_1, this plan fails\.

[sc](https://arxiv.org/html/2609.16884#id11), however, maintains uncertainty over theholdingpredicate and generates a plan that is feasible under both hypotheses \(holding vs\. not holding\):`place\-on\(hardback\_1, shelf\_1\)`,`navigate\-to\(hardback\_1\)`,`grasp\(hardback\_1\)`,`place\-on\(hardback\_1, shelf\_1\)`\. This plan ensures task success in either case, avoiding the brittle dependence on a single incorrect perceptual judgment\.

## Appendix IExperimental Baselines

##### [vlm](https://arxiv.org/html/2609.16884#id2)\-as\-planner\.

This baseline, denoted VLM\-P, implements the ViLa planning architecture\([Hu et al\., 2023](https://arxiv.org/html/2609.16884#bib.bib13)\)\. The[vlm](https://arxiv.org/html/2609.16884#id2)outputs a task plan in a specific format directly\. The first action in that plan is taken as the agent’s next action\. A list of all previously selected actions is added to the[vlm](https://arxiv.org/html/2609.16884#id2)’s context to provide the system with some memory of past interactions with the environment\.

##### [vlm](https://arxiv.org/html/2609.16884#id2)\-as\-grounder\.

This is implemented as in[Merler et al\. \(2025\)](https://arxiv.org/html/2609.16884#bib.bib21)as a variation of[s3e](https://arxiv.org/html/2609.16884#id7)\([s3e](https://arxiv.org/html/2609.16884#id7)\)\([Azran et al\., 2025](https://arxiv.org/html/2609.16884#bib.bib1)\)\. The[vlm](https://arxiv.org/html/2609.16884#id2)outputs a grounded[pddl](https://arxiv.org/html/2609.16884#id9)state, obtained by asking a series of yes\-no questions corresponding to grounded fluents\. The grounded state is passed to the Fast Downward planner\([Helmert, 2006](https://arxiv.org/html/2609.16884#bib.bib12)\)to produce a task plan that is passed to the executor\. The executor uses the VLM to monitor execution by checking preconditions and effects of the new observations\. When these become inconsistent with the current action, replanning is triggered\.

Importantly, the implementation in[Merler et al\. \(2025\)](https://arxiv.org/html/2609.16884#bib.bib21)bypasses partial observability by supplementing the grounded state with privileged information from the simulation in the form of ground\-truth assignments for predicates containing objects that are not visible\. To increase the fidelity and reliability of our approach, we do not assume access to this information\.

##### [sc](https://arxiv.org/html/2609.16884#id11)\(Ours\)\.

As described above, and depicted in\\creffig:methods:ours, in our approach, we extract probabilities from the[vlm](https://arxiv.org/html/2609.16884#id2)for each grounded predicate via the logits from the final layer of the network\. We use these probabilities to update a per\-predicate belief using logarithmic opinion pooling belief update\([Neyman and Roughgarden, 2023](https://arxiv.org/html/2609.16884#bib.bib23)\)\. Using\\crefalg:mlss, a subset of states whose probability is at least some threshold probability is selected for planning\. The state selection process uses constraints from the Fast Downward invariant finder\([Helmert, 2006](https://arxiv.org/html/2609.16884#bib.bib12)\)to filter out impossible states\. We then find a conformant plan for the selected subset of states, if one exists, using the CPOR planner\([Maliah et al\., 2022](https://arxiv.org/html/2609.16884#bib.bib20)\)with a Fast Downward internal planner\. If no plan is found, we perform a binary search to find the largest threshold probability for which a plan exists\. If a plan is found, it is executed, updating the belief at every step\.

## Appendix J[vlm](https://arxiv.org/html/2609.16884#id2)Prompts

We provide the exact prompts used for all baselines in our experiments\. The[vlm](https://arxiv.org/html/2609.16884#id2)\-as\-planner pipeline is prompted to generate a plan, while[sc](https://arxiv.org/html/2609.16884#id11)and the[vlm](https://arxiv.org/html/2609.16884#id2)\-as\-grounder pipeline are prompted to answer questions about the state of the environment\. The prompts are divided into a system prompt, which describes the task and the environment, and a user prompt, which contains the specific question or goal for the current episode\.

For[vlm](https://arxiv.org/html/2609.16884#id2)\-as\-planner, the system and user prompts are as follows:

<system\>

Youareanexpertplanningassistant\.Youwillbegivenanimagewhichrepresentsthecurrentstateoftheenvironmentyouarein,anaturallanguagedescriptionofthegoalthatneedstobeachievedandasetofactionsthatcanbeperformedintheenvironment\.

Yourtaskistogenerateaplanthatachievesthegoal,intheformofasequenceofactionsthatneedtobeexecutedtoreachthegoal\.

TheformatofyouroutputshouldbeaJSONobjectwiththefollowingstructure:

“‘json

\{

”plan”:\[

\{

”action”:action\_name,

”parameters”:\[’parameter1’,’parameter2’,…\]

\},

…otheractions…

\]

\}

“‘

Youwillalsoreceivefeedbackofthepreviouslytakenactions,withanoteshowingiftheyfailedornot\.Ifanactionfailed,thinkaboutwhythatcouldbeandthenoutputanewplanaccordingly\.

</system\>

<user\>

\#\#Descriptionoftheenvironment

Theenvironmentisavirtualhouseholdsimulator,withobjectsandfurniturewhichcanbeinteractedwith\.Keepinmindthatsomeobjectsmightnotbevisibleorimmediatelyreachable,inwhichcaseyouneedtonavigatetothemfirst\.Ifafternavigatingtoanobjectitisstillnotreachable,youmightneedtoopenacontainer\.

Visibleobjectsrelatedtothetaskarehighlightedwithboundingboxesandlabeled\.Objectsthatarenotinboundingboxesarenotrelevanttothetask,ignorethemwhenyouanswer\.

\#\#Availableactions

\-Action:grasp

\-Parameters:

1\.amovableobject

\-Preconditions:

\-Theobjectiswithinreach\.

\-Theagentisnotholdinganything\.

\-Effects:

\-Theagentpicksupthatobject\.

\-Itisnolongerontopofornexttoanyotherobject\.

\-Ifitwasinsideacontainer,itleavesthecontainer\.

\-Action:place\-on

\-Parameters:

1\.themovableobjectbeingheld

2\.anotherobjecttoserveassupport

\-Preconditions:

\-Theagentisholdingthefirstobject\.

\-Thesupportobjectiswithinreach\.

\-Effects:

\-Theheldobjectisplacedontopofthesupportobject\.

\-Theagent’shandsbecomefree\.

\-Action:place\-next\-to

\-Parameters:

1\.themovableobjectbeingheld

2\.anotherobjecttostandbeside

\-Preconditions:

\-Theagentisholdingthefirstobject\.

\-Theotherobjectiswithinreach\.

\-Effects:

\-Theheldobjectispositionednexttotheotherobject\.

\-Theagent’shandsbecomefree\.

\-Action:place\-inside

\-Parameters:

1\.themovableobjectbeingheld

2\.anopencontainer

\-Preconditions:

\-Theagentisholdingtheobject\.

\-Thecontainerisopenandwithinreach\.

\-Effects:

\-Theobjectisplacedinsidethecontainer\.

\-Theagent’shandsbecomefree\.

\-Action:open\-container

\-Parameters:

1\.aclosedcontainer

\-Preconditions:

\-Thecontaineriswithinreach\.

\-Theagentisnotholdinganything\.

\-Effects:

\-Thecontainerbecomesopen\.

\-Allobjectsinsideitbecomereachable\.

\-Action:close\-container

\-Parameters:

1\.anopencontainer

\-Preconditions:

\-Thecontaineriswithinreach\.

\-Effects:

\-Thecontainerbecomesclosed\.

\-Allobjectsinsideitbecomeunreachable\.

\-Action:navigate\-to

\-Parameters:

1\.anytargetobject

\-Preconditions:

\-Thetargetobjectiscurrentlyoutofreachandnothiddeninaclosedcontainer\.

\-Effects:

\-Thetargetobjectbecomesreachable\.

\-Allotherobjectsbecomeoutofreach\.

\-Ifthetargetisanopencontainer,everythinginsideitalsobecomesreachable\.

\#\#Goal

\{goal\_string\}

\#\#Previouslytakenactions

\{previous\_actions\}

</user\>

The goal string is a natural language description of the goal that needs to be achieved, taken from a template with placeholders for the relevant objects\. For example,`reachable\(red\-book\)`is a goal condition, then the goal string would contain the string “the red\-book needs to be reachable by the agent”\.

The previously taken actions are given as a list of action names and their parameters, e\.g\.,`grasp\(red\-book\)`,`place\-on\(red\-book, table\)`, etc\.

For[sc](https://arxiv.org/html/2609.16884#id11)and[vlm](https://arxiv.org/html/2609.16884#id2)\-as\-grounder, the system and user prompts are as follows:

<system\>

Youaretaskedwithreplyingtoaquestionaboutthegivenimage\.Youwillonlyrefertoobjectsthataremarkedinredboundingboxandignoretheotherobjects\.Youwillbegivenasinglequestion,andwillneedtoansweritONLYwith”yes”toanswerpositively,”no”toanswernegatively,or”unknown”ifthereisnotenoughinformationtotell\.Donotwriteanythingelsebesidesyouranswer\.

Theenvironmentisavirtualhouseholdsimulator\.Keepinmindthatsomeobjectsmightnotbevisibleorimmediatelyreachable,theymightbeout\-of\-sightinsomecontainer\.

Thereisaroboticarm,whichistheagent,thatcanholdobjects\.Visibleobjectsrelatedtothetaskarehighlightedwithredboundingboxesandlabeled\.Objectsthatarenotinboundingboxesarenotrelevanttothetask,ignorethemwhenyouanswer\.

</system\>

<user\>

\{fluent\_question\}

</user\>

The fluent question is a natural language question about the status of a fluent, taken from a template with placeholders for the relevant objects\. For example,`open\(cabinet\)`is a fluent, then the fluent question would contain the string “Is the cabinet currently open?”\.

## Appendix KAcronyms

CWAClosed World AssumptionVLMVision\-Language ModelVLAVision\-Language\-ActionSTRIPSStanford Research Institute Problem SolverCPconformant planningCPPconformant probabilistic planningS3ESemantic Symbolic State EstimationMLSSMost Likely Subset of StatesPDDLPlanning Domain Definition LanguageRVPRobust Visual PlanningRoVLaPRobust Vision\-Language Planning