Complexity, Decidability and Undecidability Results
for Domain-Independednt Planning
&
Serializability

Papers:
  "Complexity, Decidability and Undecidability Results for Domain-Independent
   Planning", K. Erol, D. Nau, V. Subrahmanian.
  "A Candidate Set based analysis of Subgoal Interactions in conjunctive
   goal planning", S. Kambhampati.
  Optionally "Characterizing Subgoal Interactions for Planning", A. Barrett,
   D. Weld.

Notes by Jay Noh


Complexity (in approximate order of difficulty)
  - P, NP
  - NP-complete
  - PSPACE-complete
  - EXPtime, NEXPtime
  - EXPSpace, NEXPSpace

Basic Definitions
  - Planning Operator a is a 4-tuple (Name(a), Pre(a), Add(a), Del(a))
    where Name(a) is the name, Pre(a) is the precondition list, Add(a)
    and Del(a) are the add list and delete list of a.
  - Planning Domain is a pair P=(S0,O) where S0 is the initial state,
    and O is a finite set of planning operators.
  - Language of P is the first order language generated by the constant,
    function, predicate, and variable symbols appearing in P, along with
    an infinite number of additional variable symbols.
  - Goal is a conjuction of atoms that are existentially closed (they
    are quantified).
  - Planning Problem Instance is a triple P=(S0, O, G) where (S0, G) is
    a planning domain and G is a goal.
  - "a" is theta-executable if executing a results in state S' when
    starting from state S.

Two decision problems:
  - Plan Existence
    Given a planning problem instance (S,O,G), is there a plan in P that
    achieves G?
  - Plan Length
    Given a planning problem instance (S,O,G) and integer k encoded in
    binary, is there a plan in P of length k that achieves G?
    Note: This problem itself is not interesting since it is a decision
    problem. The more interesting problem is the optimization problem
    that finds the shortest path.

Boundedness
  - Level Mapping for a language L is a mapping l:AT(L)-->N where AT(L)
    is the set of ground atoms in L and N is the set of natural numbers.
  - Predicate Level Mapping for L is a mapping #:Pred(L)-->N where
    Pred(L) is the set of predicate symbols in L.
  - P is Atomically Acyclic if and only if there exists a level mapping
    l such that for any ground instance a of operators in P, it is the
    case that l(A) > l(B) for all A in Add(a), B in Pre(a).
  - P is Predicate Acyclic if and only if there exists a predicate level
    mapping # such that for all operators a in P, it is the case that
    #(p) > #(q) for all predicates p occurring in Add(a) and all predicates
    q occurring in Pre(a).
  - Some goal will have an upper bound on the levels of ground instances
    of the goal. Then, the goal will be Bounded. This puts a bound on the
    length of the plan, and thus cause planning for such goals in such
    domains to be decidable.

Decidability Results
  - If function symbols are allowed, plan existence is undecidable in
    general.
  - When no delete lists or negative preconditions exists, plan existence
    is decidable.
  - If no function symbols (has only finitely many ground terms), then
    plan existence is decidable.

Complexity Results
 Plan Existence
  - If no restrictions, then EXPSpace-complete.
  - If no delete lists, then NEXPtime.
  - If no delete lists and no (-) preconditions, then EXPtime.
  - If each operator has at most one precondition, then PSPACE.
 Plan Length
  - If no delete lists and no (-) preconditions, then NEXPtime
  - If each operator has at most one precondition, then PSPACE.
  - If fixed set of operators and can be described with STRIPS operators,
    then PSPACE, and there exists such domains where planning is
    PSAPCE-complete.
 Other Obsevations
  - Conditional operators don't affect the results. (conditonal operators
    are useful only when we have incomplete ifo about the initial state).
  - Complexity in the datalog case is a level harder than the propositional
    case.
  - Regardless of (-) preconditions, Plan Length has same complexity.
    How to handle enabling-condition interactions is the reason.
  - Delete lists are more "powerful" than (-) preconditions.
    If delete lists are allowed, (-) precondition doesn't affect complxity.

Definitions in refinement planning
  - IPC (interval preservation constant)
    A 3-tuple (t,p,t') such that condition p be preserved between t and t'
    in every ground linearization of the plan.
  - PTC (point truth constraints)
    A 2-tuple (p,t) such that condition p be true before step t.
  - CC (contiguity constraints)
    t1 * t2 such that no step intervene between t1 and t2 in any ground
    linearization of the plan.
  - Prefix Plan
    If all the plan except t(inf) are all contiguos.
  - Suffix Plan
    If all the plan except t(0) are contiguos.
  - Protected Plan
    Has IPC to protect the subgoal as well as every precondition of every
    step of P.

Subgoal interaction
  - Mergeability
    A plan P1 for achieving a goal g1 from an initial state I is mergeable with
    respect to a plan P2 for achieving goal g2 if there is a plan P' that
    achieves both g1 & g2 (from the same initial state), and <<P1>> ^ <<P2>>
    >= <<P'>>.
    The plans are said to be simple mergeable if the minimal candidates of P'
    are not longer than the sum of the lengths of the minimal candidates of
    P1 and P2.

  - Serial Extension
    A plan P for achieving g1 from a given initial state I is serially
    extensible with
    extensible with respect to a second goal g2 if there is a plan P' that
    achieves g1 & g2 from I, and <<P>> >= <<P'>>.

  - Mergeability implies Serial extensibility, however, the reverse is false.

Subgoal Independence

  - Serializability
    Two subgoals g1 & g2 are serializable with respect to an initial state I
    if there exists a permutation "pi" on the the subgoals, such that every
    protected prefix plan P1 for the first subgoal "pi"[1] can be serially
    extended with respect to the second subgoal "pi"[2].

  - Subgoal Independence
    Two subgoals are independent if optimal plans for both subgoals can be
    obtained by merging separately produced optimal prefix plans for the two
    subgoals in any order.

Korf's Subgoal Heirarchy

  - Any arbitrary goal can be classified as:
    - Serializable
      - Trivial
        Each subgoal can be solved sequentially in any order.
        - Independent
          The subgoals can be solved in ANY order.
      - Laborous
        There exists just 1/n orders where the subgoals cannot be solved.
    - Non-serializable

  - Trivial serializability of a domain D in a planner implies that D is
    tractable. However, even though we have tractable domains, we cannot
    find planners that are tractable.

Open problem

  - How does the notion of serializability apply to Graphplan?
    (although serializability is domain independent, it is planner dependent)

-- 
Jay Noh
jnoh@asu.edu