TL;DR
This paper introduces a powerful method for solving conformant planning—finding plans that work despite initial uncertainty—by translating them into standard classical planning problems. By identifying a structural property called conformant width, the authors demonstrate that most common benchmarks can be solved in polynomial time using off-the-shelf classical planners, leading to the award-winning $T_0$ system.
What Problem Does This Paper Address?
In classical planning, you know exactly where you start. In conformant planning, you are essentially "blind." You have an uncertain initial state (e.g., "the key is in one of these three drawers") and your actions might have uncertain effects, yet you have no sensors to check your progress. You must find a single sequence of actions that guarantees the goal is reached regardless of which initial possibility was true.
Traditionally, this is solved by searching through "belief space"—the set of all possible states you could be in. However, belief space is exponentially larger than the actual state space, making these problems notoriously difficult to solve and even harder to develop effective heuristics for.
Methods
The authors propose a "translation-based" approach. Instead of searching in belief space, they compile the uncertainty directly into the problem description, turning it into a classical (deterministic) planning problem.
- The $K_{T,M}$ Translation: They introduce new literals of the form $KL/t$, which read as: "Literal $L$ is known to be true, given that the initial assumption $t$ was true."
- Tags and Merges: "Tags" ($t$) represent small sets of initial uncertainties. "Merge" actions are added to the planner to perform "reasoning by cases." For example, if the planner knows "I am at the goal if I started at A" AND "I am at the goal if I started at B," a merge action allows it to conclude "I am definitely at the goal."
- Conformant Width: This is the paper's most significant theoretical contribution. It is a structural parameter that measures how much the initial uncertainties "interact." If a problem has a width of $i$, it can be solved completely using tags of size $i$.
- The $T_0$ Planner: A system that automatically calculates the width, performs the translation, and hands the resulting deterministic problem to a high-performance classical planner (specifically, the FF planner).
Datasets
The authors evaluated their approach on a wide array of benchmarks from the International Planning Competition (IPC) and academic literature, including:
- Standard Benchmarks: Bomb-in-the-toilet, Logistics, Ring, and Safe.
- Grid/Navigation: Square-Center and Cube-Center (finding the middle of a grid from an unknown start).
- Complex Logic: Blocks-world, Sortnet (sorting networks), and Adder (binary addition).
- New Challenges: Look-and-Grab and 1-dispose (robotics-style tasks with high object uncertainty).
Key Insights and Ideas
- Local vs. Global Context: Instead of trying to track the entire global belief state, the translation tracks conditional truths. This "knowledge-level" representation is often much more compact.
- The "Width-1" Phenomenon: Surprisingly, the authors found that almost all standard conformant planning benchmarks have a width of 1. This means the uncertainty is "decoupled" enough that you only need to track one initial assumption at a time to find a valid plan.
- Leveraging Classical Success: By converting the problem to classical planning, the authors "piggyback" on decades of research into fast heuristic search. The heuristics designed for classical planning (like those in FF) turn out to be incredibly effective once the uncertainty is compiled away.
Key Results
- Competition Success: The $T_0$ planner, based on this theory, was the best-performing entry in the Conformant Track of the 2006 International Planning Competition.
- Superior Scaling: On many domains, $T_0$ solved problems orders of magnitude faster than dedicated belief-space planners like POND or MBP. For example, in the "Corners-Square-116" task, $T_0$ found a plan in ~581 seconds, while other state-of-the-art planners timed out after 2 hours.
- Efficiency: For problems with bounded width, the translation is polynomial in size, proving that many "hard" conformant problems are actually much more manageable than previously thought.
Limitations and Future Work
- High-Width Problems: While most benchmarks are width-1, some problems (like the "Adder" or "Sortnet" domains) have high width. In these cases, the translation becomes exponential, and the approach struggles.
- Non-Determinism: The core theory focuses on deterministic actions with uncertain initial states. While the authors provide a workaround for non-deterministic actions, it isn't as natively "clean" as the initial state translation.
- Contingent Planning: The authors suggest that this "compilation" approach could be extended to contingent planning, where the agent does have sensors. (Note: The authors followed up on this in later work, such as the cited Albore et al., 2009).
Summary updated