TL;DR
This paper introduces SDR, a novel online planning algorithm for problems with partial information and sensing actions. SDR tackles the challenge of scaling to complex domains by using a "sample, determinize, replan" approach, significantly improving performance over existing methods on benchmark problems.
What Problem Does This Paper Address?
Planning in real-world scenarios often involves uncertainty. Agents might not know the complete state of their environment but can gather information through sensing actions. This problem, known as Planning Under Partial Observability with Sensing Actions (PPOS), is notoriously difficult because it requires generating conditional plans (plan trees) that account for all possible contingencies. These plans can grow exponentially, making offline generation infeasible for complex problems. Online planning, where the agent plans step-by-step, is a more practical approach. However, efficiently generating these plans in the face of uncertainty remains a significant challenge. Existing replanning techniques often rely on translating PPOS problems into deterministic classical planning problems, but this translation can lead to very large, non-deterministic problems, especially when sensing actions are involved.
Methods
SDR (Sample, Determinize, Replan) addresses these challenges with a novel approach:
- Sampling the Belief State: Instead of planning for all possible initial states (which can be exponentially many), SDR samples a small subset of these states. This significantly reduces the size of the classical planning problem generated.
- Determinization via Sampling: SDR uses the sampled belief state to determinize the planning problem. It assumes that observations will align with what would be observed if the sampled initial state were the true one. This optimistic assumption allows for the use of standard classical planners.
- Replanning: The agent executes the generated plan. If an observation contradicts the assumption about the initial state, or if the plan leads to an unsafe situation, the agent replans.
- Lazy Belief State Maintenance: To efficiently track the agent's knowledge, SDR uses a "lazy" regression-based method. Instead of maintaining an explicit, potentially large, representation of the belief state, it regresses queries (like preconditions or goals) through the history of actions and observations. This allows for efficient checking of conditions without the overhead of full belief state updates.
Datasets
The paper evaluates SDR on several benchmark domains:
- Wumpus: A grid-based navigation problem where the agent must avoid monsters and pits, using sensing actions (stench for Wumpus, breeze for pits) to infer their locations.
- Doors: A grid-based navigation problem with locked doors that must be tried to determine if they are unlocked.
- Color-balls: An agent must find colored balls and transfer them to bins of the correct color.
- Unix: A task involving finding a file in a hierarchical directory structure.
- Localize: A grid-based navigation problem where the agent's position is unknown and must be deduced by sensing nearby walls.
- Disease Identification: A toy example illustrating the identification and treatment of a disease using tests.
- RockSample: A POMDP domain inspired by Mars rovers, where an agent samples minerals from rocks using sensors.
- MasterMind: A game where the agent must guess a sequence of colored pegs.
The authors also introduce new benchmark domains, including variations of Wumpus with dead-ends and restarts, to highlight the limitations of current planners and test new approaches.
Key Insights and Ideas
- Sampling is Key to Scalability: The core insight is that sampling a subset of possible initial states is a highly effective way to reduce the complexity of the planning problem, enabling scalability to larger and more complex domains.
- Optimism with Replanning: SDR's optimistic assumption about observations, combined with its replanning mechanism, allows it to make progress even when initial assumptions are incorrect. The replanning step corrects for these optimistic biases.
- Lazy Belief Maintenance is Efficient: The lazy regression-based approach to belief state maintenance avoids the computational burden of explicitly representing and updating the belief state, making it more efficient for online planning.
- Benchmark Limitations: The paper highlights that many existing benchmark domains are too simple, lacking features like dead-ends or complex conditional effects, which are crucial for truly challenging PPOS problems.
Key Results
- Improved Scalability: SDR significantly outperforms the state-of-the-art CLG planner on existing benchmark problems, especially as the problem size increases.
- Faster Execution: SDR variants are generally faster than CLG, with observation bias (SDR-OBS) often leading to faster execution by encouraging early sensing.
- Comparable Plan Quality: While CLG sometimes produces shorter plans (due to considering all contingencies), SDR's plans are often comparable, and in some cases better, especially on larger instances.
- New Domains Highlight Weaknesses: SDR struggles with newly introduced domains featuring dead-ends, where its optimistic assumption of a single initial state can lead to failure. CLG, however, handles these domains better.
Limitations and Future Work
- Unsoundness with Sampling: The theoretical guarantees of the idealized SDR planner do not hold for the sampled version. Plans generated might be unsound (i.e., not executable in all possible states), though the agent's safety is maintained by checking for unsafe actions.
- Suboptimal Plans in Certain Domains: In domains with restarts (like the Wumpus variation), SDR's plans can be suboptimal because it doesn't explicitly weigh the cost of sensing against the cost of restarting.
- Challenges with Dead-ends and Conditional Effects: SDR struggles with domains containing dead-ends and complex conditional effects, where its optimistic assumptions can lead to failure.
- Future Work: The authors suggest exploring optimizations like using "tags" (sets of states) instead of individual states for translation, further improving efficiency. They also highlight the need for new benchmark domains that better expose the limitations of current planners and drive future research. Investigating how to better handle dead-ends and more complex conditional effects is also a promising direction.
Summary updated