A household robot told to "put a chilled apple on the table" usually cannot see the apple. It sits in a fridge, a drawer, or a cabinet, and the robot must pay real time and motion to walk over and open each one. Once it finds an apple, it faces a quieter question: should it use this one, or keep looking for an apple that is closer to the table and easier to grasp? Current embodied agents answer both questions with hand-written rules. We propose answering them with the Pandora's Box problem from search theory. In that problem, each option hides a random reward behind an inspection cost, and a simple per-option score, the reservation value, tells you which option to open next and when to stop.
The twist that makes this worth doing is that robot search breaks the textbook assumptions in two specific ways. The cost of opening a container depends on where the robot is standing, so costs change after every move. The reward of a found object is not a fixed number but the remaining cost of finishing the task from that object, which depends on the rest of the plan. We will build a search module that recomputes reservation values from the robot's current position and scores each found object by the planner's estimate of the work still needed. We will drop it into an existing embodied planner in place of its exploration heuristic, and we will measure, against an exact solver on small instances and against strong heuristics on ALFRED, when this search rule helps and when it reduces to something simpler.
Core Claim
The claim is narrow and testable. In long-horizon household tasks, the exploration subproblem of finding a usable instance of an object among closed containers is a Pandora's Box problem with two changes: inspection costs that depend on the robot's state, and box values defined as negative cost-to-go under the downstream plan. A rolling reservation-value policy that recomputes indices after each move and stops once the best object already found beats every unopened container's index should do three things. It should come close to the optimal expected cost on small instances. It should beat both the heuristic exploration used by the Egocentric Planning Agent and the classic "probability divided by cost" search order. And the gain should be concentrated in episodes where several candidate instances differ in downstream cost. That last prediction is the part of the claim that is falsifiable. If the gains vanish there, the Pandora's Box framing is adding nothing over older search heuristics, and we will say so.
Where This Sits
The motivating gap comes from the robotics side. Egocentric Planning for Scalable Embodied Task Achievement (EPA) pairs neural perception with a symbolic planner. When a needed object is missing, it runs Iterative Exploration Replanning, a heuristic that visits "anchor objects" such as fridges and cabinets. EPA reaches 36.07% success on the ALFRED unseen test set. Its authors attribute much of the remaining failure to perception and exploration, and they note that their method assumes actions can be undone. ALFRED supplies the setting: household instruction-following episodes averaging about 50 steps, with objects hidden in receptacles and some state changes that cannot be reversed. SayCan picks skills greedily by multiplying a language-model relevance score by a learned success probability. It treats checking whether a skill will work as free and ignores what the chosen action rules out later. Both systems motivate the proposal, and neither supplies a principled rule for costly search.
The method comes from search theory. Recent Developments in Pandora's Box Problem surveys Weitzman's index policy: open boxes in descending order of reservation value and stop when the best realized value beats every remaining index. The survey also states that costs which are not simply additive, such as travel costs, and dynamic environments remain open problems. That is exactly the regime we enter. It also warns that correlation across boxes makes exact policies intractable, which constrains our design. Pandora's AI Model Routing Box is the closest existing application. It uses reservation prices to decide which language model to evaluate before routing a query, and it shows that fixed-threshold heuristics are suboptimal. It works entirely in software, with fixed costs, Gaussian value signals, and independent options. We keep its core idea of reservation-price search and change all three assumptions. BOLT decides on-robot when to trigger expensive perception, using a fixed Lagrangian threshold. Its decisions are one step at a time, so it never asks how an inspection now changes the cost of the next one.
Research Program
We will build a search module with three parts and plug it into EPA's pipeline where Iterative Exploration Replanning currently sits.
Priors over hidden contents. For each receptacle type and object type, we estimate from ALFRED training scenes the probability that the receptacle contains an instance. When it does, we also estimate a distribution over the instance's properties that matter downstream: its pose class, whether it needs an extra step such as cleaning, and its location within the room. Optionally, a vision-language model can adjust these counts from the current image. We will measure whether this adjustment helps rather than assume it does.
Box values from the downstream plan. The value of finding instance $j$ is
$$v_j = R - C_{\text{plan}}(j),$$
where $R$ is the task reward and $C_{\text{plan}}(j)$ is the symbolic planner's estimated number of remaining steps to finish the task using instance $j$, including navigation, extra preparation steps, and a penalty for expected grasp failure. This definition is what links search to the long-horizon structure of the task. A nearby dirty mug and a distant clean mug are different prizes.
Rolling reservation values. Suppose the robot is at state $s$ and considers opening receptacle $i$. Its reservation value $\sigma_i(s)$ solves
$$\mathbb{E}\big[(v_i - \sigma_i(s))^+\big] = c_i(s),$$
where $v_i$ is the random value of the best instance inside $i$ (or minus infinity if it is empty), $(x)^+ = \max(x, 0)$, and $c_i(s)$ is the navigation-plus-opening cost of reaching $i$ from $s$. The expectation is taken over the priors above.
The policy runs in a loop. It opens the receptacle with the highest $\sigma_i(s)$, updates the robot's state, and recomputes every $\sigma_i$. It stops and commits to the best instance found once that instance's value exceeds all remaining indices. With fixed costs and independent boxes this is exactly Weitzman's optimal rule. With costs that depend on state it becomes a heuristic, and quantifying the gap is a research goal in its own right.
Exact oracle and correlation. For instances with up to about eight receptacles, we solve the full search problem, including the dependence of travel cost on the route, by exact dynamic programming over (visited set, position, best value found). This gives the optimal expected cost as a ground truth. We also test sensitivity to correlation. In single-instance episodes, finding the object in one box empties the others. Such episodes break the independence assumption, and we will report them separately. On the analysis side, we will try to bound the rolling policy's loss relative to the oracle by how far travel costs are from additive, for example by the ratio of pairwise receptacle distances to distances from the robot. We present this as a target, not a promised theorem.
Baselines
The naive reference point is nearest-first search: open the closest unopened receptacle and commit to the first instance found. This shows how much any principled ordering or stopping rule is worth.
The strongest existing system is EPA with its original Iterative Exploration Replanning, run from the released pipeline. It is the strongest competitor because it is the winning ALFRED agent. Its reported figure is 36.07% success on the unseen test set (EPA). For a fair comparison, we keep EPA's perception, language parsing, and planner fixed and replace only the exploration module, so every difference traces to search. Beating EPA means a statistically significant gain in unseen-split success, or equal success with significantly fewer steps per successful episode. We also report results on the validation-unseen split, where we can run many seeds.
The strongest simple heuristic is probability-over-cost ordering: open receptacles in decreasing order of $p_i / c_i(s)$, recomputed after each move, and commit to the first instance found. Classical search theory makes this ordering near-optimal when there is one target and values do not vary, so it is the real threat. It gets the same priors, the same cost model, and the same tuning budget as our method.
Static-cost Weitzman computes reservation values once, from the robot's starting position. It corresponds to the fixed-cost setting of Pandora's AI Model Routing Box and isolates the value of recomputing costs as the robot moves.
Binary-value Pandora sets $v_j$ to a constant for any found instance, which removes the downstream plan. It isolates the key ingredient: scoring found objects by cost-to-go.
LLM-ranked search asks a language model to order the receptacles. It tests whether common-sense ranking alone is enough.
On the small synthetic instances, the exact oracle serves as an upper bound for all of the above.
Why not just…?
Why not just open receptacles in order of probability over cost? For a single target with uniform value, this is essentially what Weitzman's rule reduces to. We expect it to tie our method on those episodes, so it is a serious threat. The separation should appear only when several instances exist and differ in downstream cost. In that case the ratio rule has no stopping criterion beyond "first found," while the reservation rule can pass up a poor instance. The binary-value ablation and the split of episodes by number of instances settle this directly. If the ratio rule matches us on multi-instance episodes as well, the proposal's contribution shrinks to reporting a negative result.
Why not just let an LLM decide where to look? SayCan shows that language models without grounding produce physically infeasible plans, and grounding them roughly doubled task performance. A language model's ranking also carries no notion of travel cost and gives no stopping rule. We still run it as a baseline, and we use its ranking as an optional input to our priors, so a good language-model prior helps our method rather than competing with it.
Why not just train an end-to-end policy to explore? ClevrSkills reports near-0% zero-shot success for vision-language-action models on multi-step tasks, and only 3.3% to 5.8% after fine-tuning on its hardest level. ALFRED reports 0.4% unseen success for its sequence-to-sequence baseline. A learned policy could in principle discover good search behavior. With the data that exists, however, the evidence points toward a modular system, and our module is small enough to slot into one.
Why not just solve the whole thing as a partially observable planning problem? On small instances, that is exactly our exact oracle, and we use it as the reference. It grows exponentially with the number of receptacles, which is why an index policy that is cheap to compute matters. The oracle gap measures what we give up by using the index policy instead.
Proposed Experiments
Controlled suite. We first build a suite of 2,000 search instances from ALFRED's AI2-THOR scenes. Each instance has 4 to 8 closed receptacles, object placements sampled from the learned priors, and 1 to 3 candidate instances with varied poses and preparation needs. On this suite we report the ratio of each policy's expected cost to the oracle's, broken down by how far travel costs are from additive.
ALFRED. We then run the full EPA-based agent on ALFRED's validation-unseen and test-unseen splits. We report task success, steps per successful episode, and the number of receptacles opened. Results are also split into three strata: target visible, single hidden instance, and multiple hidden instances.
Decisive checks. Three results would decide the outcome. First, rolling reservation values should stay within a few percent of the oracle on the controlled suite, while static-cost Weitzman degrades as travel costs become less additive. Second, on multi-instance ALFRED episodes, our method should beat probability-over-cost ordering, and the binary-value ablation should lose most of that gain. That would show the cost-to-go value, not the ordering, is doing the work. Third, the full agent should improve on EPA's reported unseen success, or reach it with fewer steps.
If the second check fails, the conclusion is that robot object search is still well served by classical single-target search heuristics. That would be a useful negative result for anyone tempted to import prophet-style machinery into embodied planning.
References
- Egocentric Planning for Scalable Embodied Task Achievement
- ALFRED: A Benchmark for Interpreting Grounded Instructions for Everyday Tasks
- Do As I Can, Not As I Say: Grounding Language in Robotic Affordances
- Recent Developments in Pandora's Box Problem: Variants and Applications
- Pandora's AI Model Routing Box: Efficient Allocation with Costly Value Estimation
- BOLT: Decision‑Aligned Distillation and Budget-Aware Routing for Constrained Multimodal QA on Robots
- ClevrSkills: Compositional Language And Visual Reasoning in Robotics