Abstract
Conformant planning involves finding a single sequence of actions that achieves a goal despite uncertainty in the initial state. This paper presents a novel translation scheme that compiles conformant planning problems into classical ones. By representing "knowledge" as logical literals, the method allows off-the-shelf classical planners to solve complex uncertain environments. While the translation is sound but incomplete, empirical results demonstrate that it significantly outperforms specialized conformant planners in scalability and efficiency across various benchmarks.
Introduction: The Challenge of Conformant Planning
In classical planning, the initial state is fully known, and actions have deterministic outcomes. Conformant planning elevates the difficulty by introducing initial state uncertainty—for instance, a robot might not know which room contains a target object. The objective is to find a "conformant" plan: a single action sequence that succeeds regardless of which initial state possibility is true.
Computationally, conformant planning is $\Sigma^P_2$-complete, making it significantly harder than the NP-complete classical planning. Traditional solvers often struggle with the combinatorial explosion of "belief space"—the set of all possible states. This paper explores whether we can bypass this complexity by translating uncertainty into a language classical planners already understand.
Methodology: The $K(P)$ Translation
The authors propose a translation scheme, $K(P)$, which transforms a conformant problem $P$ into a classical problem $K(P)$. The fundamental shift is moving from state variables (fluents) to "epistemic" literals. For any fluent $L$, a new literal $KL$ is introduced, signifying "it is known that $L$ is true."
Core Translation and Reasoning by Cases
The translation consists of a core mapping ($K_0$) for basic actions and a more sophisticated "Split-Protect-and-Merge" strategy to handle disjunctions (OR statements).
- Split: Introduces atoms $L/X_i$, representing conditional beliefs (e.g., "if $X_i$ was true initially, then $L$ is true now").
- Merge: A synthetic action that allows the planner to derive $KL$ once it has verified the condition for every possible case $X_i$ in a disjunction.
- Protect: A flagging system ensures that conditional proofs remain valid until they are merged.
As shown in the table above, while the translation increases the number of actions and atoms, the process remains computationally efficient, typically taking only a few seconds even for large problems.
Experimental Evaluation
The authors evaluated their tool, cf2cs, using the FF v2.3 classical planner against standard benchmarks (e.g., Bomb, Cube, Square) and custom grid-based problems (Retrieve, Dispose).
Key Results
The compilation approach demonstrated remarkable scaling. In the Cube-75-Ctr problem, specialized conformant planners like CFF timed out, whereas cf2cs(ff) found a solution in approximately 8 minutes.
The results in Table 1 highlight that for many domains, the combined time of translation and classical solving is orders of magnitude faster than direct conformant solving. For instance, on Sqr-120-Ctr, cf2cs(ff) solved the problem in under a minute, while CFF failed to produce a result within the time limit.
Discussion and Key Insights
- Knowledge as a Fluent: By treating "knowing" as a standard variable, the system leverages years of optimization in classical heuristic search.
- Soundness vs. Completeness: The translation is sound (plans are guaranteed to work) but incomplete (it may miss some valid plans). This trade-off is the price of efficiency.
- Modular Inference: The framework is extensible; additional rules for more complex logical inferences can be added without modifying the underlying solver.
Limitations and Future Work
The current system is limited to deterministic actions and cannot handle nested disjunctions or reasoning that requires simultaneous consideration of multiple independent disjunctions. Future work aims to extend the translation to non-deterministic effects and more expressive forms of logical reasoning.
Summary updated