PaperlayerView exact revision on arXiv

Source-linked AI summary

Compiling Uncertainty Away in Conformant Planning Problems with Bounded Width

Hector Palacios, Hector Geffner

arXiv:1401.3468v1cs.AI

TL;DR

Conformant planning requires reliable plans despite uncertainty, while belief-space representations and heuristics make scaling difficult. The paper compiles deterministic problems into classical ones using conditional knowledge literals, establishes soundness and completeness conditions, and reports strong planner performance. Its main scope boundary is that the core formulation assumes deterministic actions and uncertainty only in the initial state.

  • Problem

    Conformant planning must achieve goals under incomplete initial knowledge, but belief-space representations and heuristics are difficult to scale.

  • Method

    The paper compiles deterministic conformant problems into classical planning problems using literals KL/t that encode conditional knowledge about initial assumptions.

  • Results

    The translation is sound generally, with completeness under suitable conditions, and its planner shows good performance against existing conformant planners, forming the basis of T0.

  • Takeaways & Limitations

    Classical planning technology can be used to solve a broad class of conformant problems through knowledge-level translation.

  • Takeaways & Limitations

    The core formulation assumes deterministic actions and places all uncertainty in the initial situation.

Abstract

from arXiv · show

Conformant planning is the problem of finding a sequence of actions for achieving a goal in the presence of uncertainty in the initial state or action effects. The problem has been approached as a path-finding problem in belief space where good belief representations and heuristics are critical for scaling up. In this work, a different formulation is introduced for conformant problems with deterministic actions where they are automatically converted into classical ones and solved by an off-the-shelf classical planner. The translation maps literals L and sets of assumptions t about the initial situation, into new literals KL/t that represent that L must be true if t is initially true. We lay out a general translation scheme that is sound and establish the conditions under which the translation is also complete. We show that the complexity of the complete translation is exponential in a parameter of the problem called the conformant width, which for most benchmarks is bounded. The planner based on this translation exhibits good performance in comparison with existing planners, and is the basis for T0, the best performing planner in the Conformant Track of the 2006 International Planning Competition.

1. Introduction

Conformant planning must achieve goals despite uncertainty, but belief-space representations and heuristics make scaling difficult. This work instead compiles deterministic conformant problems into classical planning problems, with soundness, completeness conditions, bounded-width complexity, and strong empirical performance.

  • Motivation: Conformant planning seeks plans that achieve goals despite incomplete initial knowledge and potentially non-deterministic effects.It is computationally harder than classical planning, and plan verification remains hard even with polynomial plan-length restrictions.
  • Motivation: Belief-space planners must represent possible states compactly and obtain effective heuristics over beliefs.Logical representations using SAT or OBDD technology improve scaling, but belief-space heuristics have been less successful than classical-planning heuristics.
  • Approach: The paper compiles deterministic conformant problems into classical planning problems solved by an off-the-shelf classical planner.Its translation introduces literals KL/t expressing that L must hold when initial assumptions t hold.
  • Approach: The translation is sound generally, while completeness depends on suitable conditions involving tags and merges.The complete translation has complexity exponential in conformant width, which is bounded for many benchmark domains and therefore yields polynomial complexity there.
  • Results: The resulting planner shows good performance against existing conformant planners and forms the basis of T0.T0 is reported as the best-performing planner in the 2006 International Planning Competition’s Conformant Track.
  • Scope: The formulation is restricted to deterministic conformant problems whose uncertainty lies entirely in the initial situation.The paper also discusses extending the approach to non-deterministic domains and reports empirical results there.

2. The Conformant Problem P

A conformant problem specifies fluents, an uncertain initial situation, deterministic actions with conditional effects, and goals. A plan is conformant only if it is executable and achieves the goals from every possible initial state.

  • Problem Definition: A conformant problem is represented as P = ⟨F, I, O, G⟩, with fluents F, initial clauses I, actions O, and goal literals G.Actions have fluent-literal preconditions and conditional effects of the form C →L.
  • Problem Definition: All actions are deterministic, so uncertainty is confined to the initial situation.Without initial uncertainty, the problem is equivalent to classical planning.
  • Semantics: A possible initial state is any truth assignment satisfying the clauses in I.The formulation assumes both I and the planning problem are consistent.
  • Semantics: A conformant plan is an action sequence that is a classical plan for every possible initial state.It must be executable from each possible state and produce a state satisfying all goal literals.
  • Motivation: Conformant planning is computationally harder than classical planning because plan verification remains hard under polynomial plan-length restrictions.This motivates alternative representations and solution methods.
  • Belief-State View: The belief-state formulation turns conformant planning into path finding over sets of states deemed possible.Actions map one belief state to another, with the initial belief as source and goal beliefs as targets.

3. A Basic Translation K0

The basic translation K0 replaces fluent knowledge with classical literals and encodes action effects through support and cancellation rules. It is sound and produces valid conformant plans, but its restricted representation makes it incomplete.

  • Translation: K0 replaces each literal L with KL and K¬L, representing knowledge that L is true or false.Its initial state contains KL exactly when L is a unit clause in the original initial situation, and its goals require KL for each original goal literal.
  • Translation: Each original conditional effect becomes a support rule and a cancellation rule in the classical problem.Support derives KL when KC is known; cancellation removes K¬L when C is not known false.
  • Properties: K0 is sound: every classical plan solving K0(P) is a conformant plan for P.This means knowledge established in the translated problem is sufficient for certainty in the original problem.
  • Properties: K0 is incomplete because some conformant plans do not make the corresponding KL literals true.The translation captures only the restricted, non-disjunctive knowledge represented by the 0-approximation semantics.
  • Properties: A classical plan for K0(P) is equivalent to a conformant plan under the 0-approximation semantics.Both approaches discard disjunctive information and restrict plans that rely on uncertain knowledge.
  • Implications: The translation addresses both belief representation and belief-heuristic problems by turning beliefs into classical states solvable with classical heuristics.It therefore provides valid conformant plans using a classical planner without explicit belief-space search.

4. General Translation Scheme KT,M

The general translation KT,M augments K0 with tags encoding initial assumptions and merges supporting reasoning by cases. Under consistent tags and valid merges it is sound, and suitable choices can make it complete.

  • General Scheme: KT,M extends K0 with a set of tags T and a set of merges M.Tags condition knowledge literals on initial assumptions, while merges combine conditional knowledge into unconditional knowledge.
  • Tags: A tag t is a conjunction of initially uncertain literals, and KL/t means that L is true if t was initially true.¬KL/t differs from K¬L/t: the former denies the conditional, while the latter asserts the conditional for ¬L.
  • Merges: A merge is a non-empty collection of tags representing a disjunction, and its merge action performs reasoning by cases.A valid merge is one where at least one included tag must hold initially.
  • Merges: Merges are formally associated with particular literals through pairs (m, L), grouped into sets ML.This lets the translation specify where merges should be used for computational convenience.
  • Properties: The translation is complete when every conformant plan can be represented by a translated classical plan after removing merge actions.The basic translation is recovered when M is empty and T contains only the empty tag.
  • Properties: KT,M is sound when every merge is valid and every tag is consistent.Soundness means that removing merge actions from any translated classical plan yields a conformant plan.
  • Example: In the illustrated two-location problem, merging conditional knowledge about at(l3) produces the unconditional goal Kat(l3).The corresponding translated plan succeeds, whereas removing the first drop causes cancellation to invalidate the conditional knowledge needed by the second pickup.

5. A Complete Translation: KS0

KS0 is an exhaustive translation that represents all possible initial states as tags and uses merges for each precondition and goal literal, yielding a complete classical-planning encoding. Its completeness is theoretically guaranteed, but the exhaustive representation can be costly for practical problems.

  • Translation definition: KS0 uses every possible initial state as a tag and includes one merge containing all such tags for each precondition and goal literal.This construction is valid and complete because tags correspond directly to possible initial states.
  • Completeness: For every conformant plan π, KS0 provides a classical plan π′ whose merge actions can be removed to recover π.The correspondence establishes completeness of the exhaustive translation.
  • Practical significance: KS0 can be difficult even with few possible initial states, as illustrated by the Square-Center-n task.The task requires reaching the center of a grid with certainty despite an unknown initial location.
  • Empirical comparison: Table 1 compares the KS0 translation solved by FF with POND and Conformant FF using solving times and reported plan lengths.The table also records the number of possible initial states and whether Conformant FF handles the goal syntax.

6. Complete Translations that May be Compact Too

Compact complete translations are obtained by exploiting covering conditions and the conformant width of a problem. Their size is exponential in width but polynomial in the rest of the problem, and most existing benchmarks have width 1.

  • Prerequisites: Complete polynomial translations require assumptions such as prime-implicate initial-state formulas, which make logical entailment checks tractable.Without such assumptions, checking whether a goal follows from the initial situation can itself be intractable.
  • Covering translations: Covering translations are complete: every conformant plan has a corresponding classical plan after merge actions are removed.The covering condition can both certify completeness and guide construction of complete translations.
  • Covering translations: A single valid merge can make a translation polynomial while preserving completeness, as in the disjunctive x1 ∨· · · ∨xm example.The exhaustive KS0 translation is exponential in m, whereas the covering translation uses one merge over the m tags.
  • Kmodels: Kmodels is sound and complete and can be exponentially more compact than KS0 when relevant clauses involve fewer variables than the full initial-state uncertainty.Its worst-case size remains exponential, motivating width-based polynomial translations.
  • Conformant width: Conformant width bounds the time and space needed to generate covering translations, with complexity exponential in width rather than necessarily in all unknown fluents.Width is bounded by the number of unknown fluents but can be substantially smaller.
  • Benchmark widths: Almost all existing conformant benchmarks have width 1, so their translations use tags no larger than single literals.Domains such as Blocks, Sortnet, and Adder instead have maximal widths because their fluents interact through action conditions.
  • Polynomial translation Ki: For fixed i, Ki is sound and polynomial, and it is complete for problems whose conformant width is at most i.The translation remains exponential in i but polynomial in the numbers of fluents, actions, and clauses.

7. Tags and Initial States

The paper shows how tags in covering translations correspond to critical initial states, allowing polynomial-size bases to represent exponentially many possible initial states when conformant problem width is bounded.

  • Basis construction: A basis is a subset of possible initial states such that every plan conforming with it conforms with all possible initial states.Thus, conformant-plan computation need not consider the entire initial-state set.
  • Illustration: In the illustrative problem, n single-true valuations form a basis for 2^n − 1 possible initial states.Plans conforming with the n selected states are exactly those conforming with the complete set of possible initial states.
  • Monotonicity: Monotonicity ensures that a plan conforming with the representative critical states also conforms with the full collection of possible initial states.The argument compares relevant literals across states and uses this relation to transfer conformity from a basis to the complete initial-state set.
  • Tags and initial states: The translation’s tags correspond to representative initial states selected for relevant precondition and goal literals.Each tag in a merge covering a literal represents a state that falsifies relevant literals outside the tag’s closure.
  • Bounded width: A conformant problem with bounded width admits a polynomial-size basis, despite potentially exponentially many possible initial states.The resulting complete translations can therefore be polynomial for bounded-width problems.
  • Conditions: The basis construction assumes a logically consistent initial situation and tags consistent with that initial situation.The theorem establishing the basis is stated for covering translations with the initial situation in prime implicate form.

8. The Planner T0

T0 combines polynomial and complete translation instances with a classical planner, using simplifications and additional deductive rules to reduce translation overhead.

  • Translation pipeline: T0 feeds outputs from two instances of the translation scheme into the classical planner FF v2.3.8.One instance is polynomial but not necessarily complete; the other is complete but not necessarily polynomial.
  • Translation pipeline: The incomplete translation K1 is complete for problems of width at most 1 and may also solve some problems with larger widths.T0 uses K1 first in its default mode, then falls back to the complete Kmodels translation if needed.
  • Translation pipeline: For the complete translation, T0 uses Kmodels and substitutes a simpler K1 merge when K1 produces a single merge covering a literal.This substitution is described as an optimization that preserves completeness.
  • Translation pipeline: T0 computes other Kmodels merges from models of clauses consistent with the initial situation using the SAT solver relsat v2.20.The default sequence invokes FF on K1’s output before attempting the complete translation.
  • Simplifications: The translations simplify the representation by omitting irrelevant conditioned literals and support or cancellation rules.They also group support and cancellation rules when the initial situation and tag determine relevant literals completely.
  • Deductive rules: T0 adds two sound deductive rule types for action consequences and static disjunctions.These rules respectively capture certain action implications and derive one disjunct when all alternatives are ruled out.
  • Implementation: The reported T0 version converts the initial situation to prime implicate form with Tison’s algorithm, taking at most 48 seconds on solved benchmarks.The translators are written in OCaml and the PDDL parser in C++.

9. Experimental Results

Experiments evaluate translation size, runtime, scalability, and plan quality across benchmark families, comparing T0 with conformant and classical-planning alternatives. T0 generally scales well and often dominates, but performance depends on domain structure, encoding choices, and translation selection.

  • Experimental setup: The experiments cover established benchmarks, IPC5 problems, grid domains, and instances from Palacios and Geffner.T0 times include prime-implicate computation, translation, and FF search, with a 2-hour or 2.1GB cutoff.
  • Translation costs: Translation size grows substantially in conditional effects, and translation can take several seconds on selected instances.Table 3 reports actions, atoms, effects, translation time, and PDDL size.
  • Benchmark performance: T0 scales well in most domains, with exceptions including Square-Center, Cube-Center, and Sortnet where other planners scale better.On width-1 benchmarks, T0 performs particularly well on Ring and Safe, while Conformant-FF also performs well on Bomb and Logistics.
  • Benchmark performance: T0 dominates across the reported domains except Adder, where POND alone solves an instance, and Sortnet, where MBP and KACMBP perform very well.T0 fails on Adder because FF gets lost in search; an alternative DNF goal encoding solves Adder-01 in some cases.
  • Search comparison: Translation-based search evaluates thousands of nodes per second with FF, versus a few hundred for Conformant-FF, but node counts vary by domain.In Dispose-8-3, T0 solves the instance after evaluating more than half a million nodes, whereas Conformant-FF times out after fewer than three thousand.
  • Plan quality and scaling: T0 usually produces shorter plans, including 125 actions for Dispose-04-03 versus 314 for CpA(H) and 320 for CpA(C).CpA planners are slightly faster on Blocks, while T0 scales better with grid size in Dispose but worse with object count.
  • IPC6 analysis: Fixing IPC6’s Dispose translation bug increases solved instances from 20 to 60 of 90 and yields shorter plans, including 470 versus 2881 and 3693 actions on Dispose-06-8.The bug used Kmodels instead of K1, although K1 is complete for Dispose’s width-1 domain.

10. Non-Deterministic Actions

The paper extends its translation-based conformant planner toward non-deterministic actions by encoding outcomes as initial uncertainty and iteratively controlling action reuse. Experiments show meaningful performance, though classical-planner search and translation size remain practical constraints.

  • Scope and extension: The translation schemes are originally limited to deterministic actions, with non-deterministic extensions requiring suitable transformations.The authors present these transformations as illustrative rather than a full treatment of non-deterministic domains.
  • Outcome encoding: Non-deterministic effects are encoded by deterministic rules conditioned on hidden outcome variables introduced as initially uncertain.An action with outcomes S1,...,Sm becomes rules a:C,hi→Si, with oneof(h1,...,hm) added initially.
  • Correctness condition: The encoding is equivalent to the original problem when each non-deterministic action is executed at most once, but repeated execution can cause divergence.The paper illustrates divergence with repeated grid moves, where the transformed problem permits fewer possible locations than the original.
  • Iterative planning: An iterative planner constructs P1, P2, and subsequent problems that permit progressively more executions of non-deterministic actions, stopping when a solution is found.The at-most-once restriction is enforced with enabled(a), while successive action copies encode additional executions.
  • Implementation: T0’s refinement adds reset actions so non-deterministic actions may be repeated after outcome-dependent knowledge literals are erased.This refinement exploited the explicit tags in the KT,M translation; the experiments used it on non-deterministic domains.
  • Experimental results: T0 outperformed MBP on the tested non-deterministic domains but underperformed KACMBP in particular on NonDet-Ring and Non-Det-Ring-1Key.When T0 failed, the reported cause was FF becoming lost in search rather than a translation failure.

11. Related Work

The related-work discussion positions the paper between belief-space planners, approximate belief representations, and knowledge-level approaches. Its distinctive contribution is to use translation both to represent beliefs and to compute conformant plans with a classical planner.

  • Belief-space planning: Belief-space planners rely on compact SAT or OBDD representations and heuristic functions, but both representation and heuristic quality are central scaling concerns.These techniques may be intractable in the worst case while performing well on average.
  • Approximate belief updates: Petrick and Bacchus use formula-based belief states with approximations that do not add new disjunctions, limiting the problems their approach can handle.The passage identifies this restriction as a consequence of the belief-update approximation.
  • 0-approximation semantics: The K0 translation corresponds to conformant plans under 0-approximation semantics, while Ki translations extend it with tags for higher-width problems.The 0-approximation and basic K0 approaches are described as too weak for existing benchmarks.
  • Distinctive contribution: Unlike approaches that primarily represent or update beliefs, the translation approach also converts the problem into a classical planning problem that a classical planner can solve.This separates the approach from methods built on top of 0-approximation semantics that do not provide the same classical-planning computation route.

12. Summary

The paper introduces a translation from conformant to classical planning, develops T0 from it, and reports good performance against existing conformant planners. It also identifies bounded width as common among conformant benchmarks and extends the ideas toward contingent planning.

  • Contribution: The paper converts conformant problems P into classical problems KT,M(P), which are then solved by a classical planner.This is the paper’s central reformulation of conformant planning.
  • Width and planner: Most conformant benchmarks have width 1, and the authors develop the conformant planner T0 based on these translations.The summary presents bounded benchmark width as a central empirical observation supporting the approach.
  • Evaluation: T0 exhibits good performance in comparison with existing conformant planners.The paper reports this outcome without claiming uniform dominance across all domains.
  • Broader scope: The authors report that these ideas have also been explored in the more general setting of contingent planning.This extends the relevance of the translation ideas beyond purely conformant settings.

Appendix A. Proofs

The appendix establishes soundness, completeness, and polynomial-size basis results for translations, while relating classical plans to conformant plans under stated conditions.

  • Soundness of K0: A classical plan for K0(P) is a conformant plan for P under the 0-approximation semantics.The correspondence follows from matching applicability and achievement conditions between K0(P) and the 0-approximation.
  • Soundness of KT,M: The general translation KT,M(P) is sound when all merges are valid and all tags are consistent.Consistency means that tag literals hold in some possible initial state, while valid merges cover the relevant possibilities.
  • Completeness: A conformant plan for P corresponds to a classical plan for KS0(P) after merge actions are removed.More generally, covering translations KT,M(P) are complete: every conformant plan has a corresponding classical plan with merge actions omitted.
  • Completeness: Theorem A.10 and Lemma A.11 connect possible initial states, relevant literals, tags, and translated literals KL/t in covering translations.These results support completeness by showing when achievement in a possible initial state yields achievement of the corresponding conditioned literal.
  • Width and complexity: The width w(P) can be determined in time exponential in w(P), and bounded-width problems admit a polynomial-size basis.The basis is formed from states associated with precondition or goal literals and tags in merges covering those literals.
  • Width and complexity: For fixed i, Ki(P) is sound and polynomial, and it is covering and complete when w(P) ≤ i.Thus, bounded conformant width supplies the condition under which a fixed-width translation captures conformant plans completely.

Appendix B. Consistency

Appendix B defines consistency through logically consistent initial situations and mutex complements, then proves that valid translations preserve consistency under these assumptions.

  • Consistency conditions: A problem is consistent when its initial situation is logically consistent and every complementary pair L and ¬L is mutex.This condition ensures reachable states remain complete and consistent truth assignments.
  • Scope condition: Two introduced domains, 1-Dispose and Look-and-Grab, are exceptions to the benchmarks' otherwise observed consistency.For these domains, translation consistency must be checked explicitly, or obtained plans must be checked to avoid conflicting effects KL/t and ¬KL/t.
  • Mutex sets: Mutex sets are sound: no pair in a mutex set can occur together in any reachable state.The proof proceeds inductively from possible initial states through action progression.
  • Mutex sets: When the initial situation is in prime implicate form, computing the largest mutex set and testing consistency are polynomial-time operations.The largest mutex set is obtained by iteratively removing pairs that violate the mutex conditions until reaching a fixed point.
  • Consistency preservation: For a valid translation KT,M(P) of a consistent problem P, the constructed set RT is a mutex set in the translation.RT relates conditioned literals whose underlying literals are mutex and whose tags are jointly satisfiable with the initial situation.
  • Consistency preservation: A valid translation KT,M(P) is consistent if P is consistent.The result includes K0(P) as a special case with an empty merge set and only the empty tag.
Loading 1401.3468v1…