💻 computer science

Effective Task Planning with Missing Objects using Learning-Informed Object Search

This paper introduces a novel task planning framework that integrates learning-informed object search (LIOS) actions into high-level planning, enabling mobile robots to effectively generate sound and complete plans for retrieving objects with unknown locations by interleaving search and execution while remaining compatible with existing full-knowledge solvers.

Original authors: Raihan Islam Arnob, Max Merlin, Abhishek Paudel, Benned Hedegaard, George Konidaris, Gregory J. Stein

Published 2026-02-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Raihan Islam Arnob, Max Merlin, Abhishek Paudel, Benned Hedegaard, George Konidaris, Gregory J. Stein

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a robot tasked with making a delicious breakfast and a cup of coffee for your human owner. You know what you need (eggs, toast, coffee beans, water), and you know where the kitchen is. But here's the catch: you have no idea where the actual items are. The eggs might be in the fridge, the toaster might be on the counter, or the coffee beans could be hidden in a pantry you haven't checked yet.

This is the problem this paper solves.

The Old Way: The "Blind" Planner vs. The "Guessing" Robot

The Old School Planner (The Rigid Architect):
Imagine a super-smart architect who can draw the perfect blueprint for your day. But this architect has a rule: "I can only plan if I know exactly where every single brick is." If you tell them, "I need a hammer, but I don't know where it is," they freeze. They can't draw a plan because the map is incomplete. In the robot world, this is like using standard planning software (PDDL) which assumes the robot sees everything perfectly.

The Old Searcher (The Random Digger):
On the other hand, some robots just start digging. They might check the fridge, then the sofa, then the bed, just in case the coffee beans are there. They use a "Greedy" strategy: "Go to the closest thing I haven't checked yet." This works, but it's inefficient. You might spend 20 minutes looking for the toaster in the bedroom when it was right next to you in the kitchen the whole time.

The New Solution: The "Smart Scout" (LIOS)

The authors of this paper created a hybrid system called Learning-Informed Object Search (LIOS). Think of it as giving your robot a Smart Scout and a Crystal Ball.

1. The Crystal Ball (Learning)

The robot has been trained on thousands of virtual houses (simulated environments). It has learned patterns, like:

"Toasters are usually on kitchen counters."
"Cellphones are often on nightstands or desks."
"Water bottles are usually in the fridge."

This isn't magic; it's a machine learning model that says, "Based on what I've seen before, there is a 90% chance the water bottle is in the fridge, and only a 5% chance it's under the bed."

2. The Smart Scout (The "Find" Action)

Instead of treating "searching" as a messy, unpredictable process, the robot packages it into a neat, single action called "Find."

Imagine you are playing a board game. Usually, you can't move a piece unless you know exactly where the path is. But this new rule says: "You can play a 'Find Card.' When you play it, a magical scout goes out, looks in the most likely places based on the Crystal Ball, grabs the item, and brings it back to you. You don't need to know the exact path; you just know the card will work."

This allows the main planner (the Architect) to stay in control. It can say, "Okay, I need to make coffee. I will play the 'Find Coffee Beans' card, then the 'Find Water' card, then 'Make Coffee'." The planner treats the search as a guaranteed, predictable step, even though the robot is actually searching in the real, messy world.

3. The Cost Calculator (The "Price Tag")

This is the secret sauce. The robot doesn't just guess; it calculates the expected cost.

Scenario A: The fridge is 5 steps away, and there's a 90% chance the water is there. The "price" of searching the fridge is low.
Scenario B: The bedroom is 50 steps away, and there's a 1% chance the water is there. The "price" is huge.

The robot uses these "price tags" to decide what to look for first. If it needs a phone and a water bottle, and the phone is likely on the desk (close by) while the water is likely in the fridge (far away), the robot will grab the phone first to save time and energy.

How It Works in Real Life

The researchers tested this on a real robot (Boston Dynamics' Spot) and in a massive video game simulation of houses.

The Test: The robot had to deliver a water bottle to the kitchen and a phone to the bedroom.
The Competitor (Greedy): The robot checked the closest room first (the bedroom), found nothing, then went to the kitchen, found nothing, then went back to the bedroom, and so on. It checked all 9 containers and took 311 seconds.
The New Way (LIOS): The robot looked at its "Crystal Ball," realized the water bottle was likely in the kitchen (where it started), and the phone was likely on the desk. It went straight to the kitchen, grabbed the water, then went to the desk for the phone. It only checked 2 containers and finished in 174 seconds.

The Big Picture

This paper is about teaching robots to be smart detectives rather than confused wanderers.

They learn from experience (where things usually are).
They package the messy act of searching into a clean, predictable step so the main brain can make a plan.
They calculate the "price" of searching different places to decide the most efficient order of operations.

By combining machine learning (to guess where things are) with classic planning (to organize the steps), these robots can now handle the messy, unknown reality of our homes without getting stuck or wasting time. They don't just know how to do a task; they know where to look to make the task possible.

1. Problem Statement

Mobile robots operating in real-world environments (e.g., homes) face a critical challenge: task planning under partial observability.

The Gap: Traditional task planners (e.g., PDDL-based solvers like FASTDOWNWARD) assume full knowledge of the environment and deterministic action effects. They fail when task-critical objects are missing or their locations are unknown.
The Challenge: While recent learning-based methods can effectively search for objects, they operate as standalone modules. They cannot be easily integrated into high-level symbolic planners because:
1. Search is inherently non-deterministic (stochastic).
2. Planners need to decide what object to search for, when to search, and in what order to minimize total task cost.
3. Existing frameworks (like LOMDP) often use greedy, front-loaded search strategies that delay task execution until all objects are found, which is inefficient.

2. Methodology

The authors propose a framework that bridges the gap between learning-based object search and deterministic symbolic planning by introducing Learning-Informed Object Search (LIOS) actions.

A. High-Level Abstraction: The `find` Action

To maintain compatibility with efficient PDDL solvers, the authors encapsulate the stochasticity of searching into a deterministic high-level action called find.

Definition: find(object, start, target) is treated as a monolithic skill with deterministic postconditions: the robot ends up holding the object at the target location.
Mechanism: While the high-level planner sees this as a single step, the execution involves a closed-loop policy that searches containers, replans as the environment is revealed, and retrieves the object.
Optimism: The planner assumes "optimistically" that found objects will satisfy future preconditions. If an object's state (e.g., clean vs. dirty) is incorrect, the system replans upon discovery.

B. Learning-Informed Object Search (LIOS) Policy

To instantiate the find action, the authors developed a model-based policy that combines learned predictions with planning:

Probability Estimation: A neural network (trained on Sentence-BERT embeddings of room/container/object names) predicts the probability ( $P_{FOUND}$ ) of finding a specific object in an unsearched container.
Expected Cost Calculation: Using a Bellman equation (Eq. 1), the system computes the expected cost ( $Q_{\pi_o}$ ) of a search policy. This cost accounts for:
- Movement costs between containers.
- Search costs.
- The probability of finding the object vs. the cost of continuing to search other containers.
- The final cost of moving the object to the target.
Policy Synthesis: The system solves for the policy $\pi_o$ that minimizes this expected cost, effectively determining the optimal sequence of containers to search.

C. Integration with Task Planning

The LIOS policy generates an expected cost for the find action.
The high-level PDDL planner uses these costs to generate a global plan that interleaves search and execution.
Replanning: As the robot executes the plan and discovers new objects (revealing the map), it updates the set of known objects and containers, triggering replanning to refine the remaining task.

3. Key Contributions

Deterministic Abstraction for Stochastic Search: The introduction of the find action allows standard, highly-optimized deterministic planners (like FASTDOWNWARD) to handle missing objects by treating search as a deterministic action with a learned expected cost.
Model-Based Learning-Informed Search (LIOS): A novel policy that integrates learned object-location probabilities with model-based planning to compute accurate expected search costs, rather than relying on simple heuristics.
Holistic Decision Making: The framework simultaneously solves three sub-problems:
- How to find an object (via LIOS policy).
- What object to search for (via cost comparison in the global plan).
- When to search (interleaving search with task execution).
Real-World Validation: Successful deployment on a Boston Dynamics Spot robot in a real home environment, demonstrating the transition from simulation (PROCTHOR) to reality.

4. Experimental Results

The approach was evaluated in the PROCTHOR simulation environment (500+ procedurally generated homes) and on a Spot robot in a real home.

Object Search Performance

LIOS vs. Greedy: In 200 trials of single-object retrieval, the LIOS policy reduced search costs by 59.9% compared to a simple Greedy baseline (searching nearest containers first). LIOS successfully prioritized high-probability locations (e.g., searching the kitchen for a toaster) over random or nearest-neighbor approaches.

Task Planning Performance

Five complex scenarios were tested (e.g., "Deliver 3 Objects," "Breakfast Prep," "Coffee Prep").

ModelLIOS (Full Approach): Outperformed all baselines (OptGreedy, PesGreedy, OptLIOS, PesLIOS) in terms of average task cost and success rate.
Key Finding: The use of the expected cost (Eq. 1) was critical. Strategies that used LIOS for search but naive cost estimates (OptLIOS/PesLIOS) performed worse than ModelLIOS. This proves that accurate cost estimation is necessary for the high-level planner to decide the optimal order of operations (e.g., retrieving the easiest object first).
Real-World Results: In the Spot robot experiments, ModelLIOS completed tasks in 174 seconds with only 2 container searches, whereas baselines took 264s–311s and searched 6–9 containers. This highlights the efficiency of long-horizon reasoning based on expected costs.

5. Significance and Impact

Bridging the Gap: This work successfully integrates modern machine learning (for perception/prediction) with classical symbolic planning (for reasoning/optimization), overcoming the "modularity" problem where learning and planning are usually separate.
Scalability: By abstracting stochastic search into deterministic actions with expected costs, the method scales to large, complex household environments where full POMDP planning would be computationally intractable.
Practicality: The system enables robots to operate effectively in "the wild" where object locations are unknown, moving beyond the theoretical assumption of fully known maps.
Limitations & Future Work: The current approach assumes a single-object search window (no concurrent search) and treats object states optimistically. Future work aims to predict object states (e.g., dirty vs. clean) and support opportunistic search during navigation.

In conclusion, the paper presents a robust framework that allows mobile robots to reason about uncertainty, efficiently search for missing items, and execute complex multi-step tasks in dynamic, unknown environments.