Abstract
Conformant planning involves finding a sequence of actions to achieve a goal despite uncertainty in the initial state or action effects, without the aid of sensors. Traditionally, this is framed as a path-finding problem in belief space, which often suffers from exponential state explosion. This paper introduces a novel formulation for conformant problems with deterministic actions by automatically converting them into classical planning problems solvable by off-the-shelf planners. The translation maps literals $L$ and sets of initial assumptions $t$ into new literals $KL/t$, representing the knowledge that $L$ must be true if $t$ was initially true. We establish a general sound translation scheme and identify the conditions for completeness. The complexity of this translation is shown to be exponential in a parameter called "conformant width," which remains bounded for most standard benchmarks. Our resulting planner, $T_0$, demonstrated state-of-the-art performance, winning the Conformant Track of the 2006 International Planning Competition.
Introduction
In classical planning, an agent possesses perfect knowledge of its initial state and the outcomes of its actions. In contrast, conformant planning requires an agent to operate "blindly." With an uncertain initial state—such as a key located in one of several possible drawers—and no sensors to verify progress, the agent must find a single, robust sequence of actions that guarantees the goal is reached regardless of the actual initial configuration.
Historically, researchers approached this by searching through "belief space," the set of all possible states an agent could be in. However, because the number of belief states is $2^n$ relative to $n$ physical states, this approach is computationally taxing and makes the development of effective heuristics difficult. This work proposes a shift in perspective: instead of searching in belief space, we can compile the uncertainty directly into the problem description, transforming it into a deterministic classical planning problem.
The $K_{T,M}$ Translation
The core of this approach is a translation-based method that tracks conditional truths rather than global belief states. The authors introduce the $K_{T,M}$ translation, which utilizes three primary components:
- Conditional Literals ($KL/t$): These represent the knowledge that a literal $L$ is true, given that a specific initial assumption (or "tag") $t$ was true.
- Tags and Merges: "Tags" represent small sets of initial uncertainties. To handle the combination of these uncertainties, the translation introduces "Merge" actions. These actions allow for reasoning by cases: if the planner determines that the goal is reached if assumption $A$ was true, and also reached if assumption $B$ was true, a merge action allows the planner to conclude that the goal is reached definitively.
- Classical Integration: By converting the problem into a classical format, the system can leverage decades of research into high-performance classical planners. The $T_0$ system specifically utilizes the FF (Fast-Forward) planner to solve the resulting deterministic problems.
The Theory of Conformant Width
The paper’s most significant theoretical contribution is the definition of conformant width. This structural parameter measures the degree to which initial uncertainties interact. If a problem has a width of $i$, it can be solved completely using tags of size $i$.
Empirical analysis reveals a "Width-1" phenomenon: the vast majority of standard conformant planning benchmarks have a width of 1. This implies that the uncertainty in these problems is sufficiently decoupled that an agent only needs to track one initial assumption at a time to find a valid plan. For problems with bounded width, the translation is polynomial in size, proving that many seemingly difficult conformant problems are more tractable than previously assumed.
Empirical Evaluation
The $T_0$ planner was evaluated against a wide array of benchmarks from the International Planning Competition (IPC) and academic literature, including:
- Navigation and Grids: Square-Center and Cube-Center tasks.
- Logic and Robotics: Blocks-world, Sortnet (sorting networks), and 1-dispose (robotics tasks with high object uncertainty).
- Standard Benchmarks: Logistics, Ring, and Bomb-in-the-toilet.
Key Results
- Performance: $T_0$ was the top-performing entry in the Conformant Track of IPC 2006.
- Scaling: On complex tasks like "Corners-Square-116," $T_0$ found solutions in approximately 581 seconds, while competing belief-space planners like POND or MBP failed to find a solution within a two-hour timeout.
- Heuristic Efficiency: The study demonstrated that heuristics designed for classical planning are remarkably effective for conformant planning once the uncertainty is compiled into the literal representation.
Limitations and Future Directions
While the translation-based approach is highly effective for low-width problems, it faces challenges in high-width domains like "Adder" or "Sortnet," where the translation size can become exponential. Additionally, while the theory focuses on deterministic actions, the authors provide a framework for non-deterministic effects that warrants further refinement.
Future work suggests that this compilation strategy could be extended to contingent planning, where agents have access to sensors. By treating observations as a way to prune the set of active tags, the same underlying logic of conditional knowledge could revolutionize how we solve problems involving both uncertainty and sensing.
Summary updated