Note taker: Terry Zimmerman (zim@asu.edu)
Date: 7 Feb 2000
Subject: DISJUNCTIVE REFINEMENT PLANNING
In exchange with No-one!
----------------------------------------------------------------------------------
Started from the slide: "Disjunctive Refinement Planning"
Ended with the slide: "Refining Disjunctive plans (4)"
----------------------------------------------------------------------------------
Disjunctive planning (DP) poses special problems:
A key question is "If you have a disjunctive plan, how do you refine it?"
One approach is to generalize the notion of FSS refinement to apply to disjunctive plans.
Then the FSS based proof could be applied to determine if a valid plan exists. (Recall
that there are 3 types of proofs for plan correctness.)
Since plan refinement must be quick, in general you want to use "cheap" inferences such
as modus ponens. Unfortunately modus ponens is often not real effective with
disjunction. Resolution works, but it is expensive.
Graphplan provides one system for refining disjunctive plans.
(Note that currently we don't have an effective plan-space refinement approach for
disjunctive planning.)
Alternately we could setup a proof-of-correctness procedure for disjunctive structures.
The effect of DP is to push the search effort into the solution extraction phase. This
makes this phase more expensive than that for conjunctive planning. Two possible
approaches to soln extraction are 1) direct combinatorial search 2) compile the search
problem into CSP or SAT or ILP. (These are the "workhorses" for combinatorial problems)
At this point Rao conducted a brief review of CSP and SAT based closely on the first 4
slides under CSP AND SAT REVIEW. A key concept that was discussed is the idea of
"k-consistency": An n-variable CSP problem is said to be k-consistent iff every
consistent assignment for (k-1) of the n variables can be extended to include any k-th
variable. So, for example, a 2-consistent problem means any single variable and its
assignment can be extended to the 2nd variable. Note that it is NOT the case that
k-consistency => k-1 consistency.
We can enforce consistency in a problem by ADDING constraints. This typically involves
preprocessing: worst case O(2**n) for any CSP for n variables. Ideally we expect the
search cost vs. preprocessing costs to look something like:
| . *
| . * <---preprocessing cost
| . *
| . *
| . *
| .*
| *| .
| * | . <---search cost
|__*_______|_____________
~k=2 K
For general CSP's 2-consistency if typically the optimum. For temporal CSP's you
generally need 3-consistency. (2-consistency can be enforced by enforcing
"arc-consistency" / 3-consistency can be enforced by enforcing "path-consistency")
Binary CSPs are those for which every constraint is between 2 variables. (Not the same as
boolean CSP where every var is either T or F). The real world tends to be full of binary
CSPs. We can use a "constraint graph" to enforce arc-consistency on a binary CSP with
effort of O(n**2). The process is basically an iterative procedure to remove domain
values from variables based on the dictates of the given constraints.
Path consistency is assessed in a similar manner except you reason based on 3 vars.
The lecture wrapped up with a discussion of the 4 slides relating to Refining Disjunctive
Plans -each illustrating a possible approach:
1) Indirect unioned approach -gives maximum "progressiveness" (pruning power) but it's
INFEASIBLE due to exponential refinement cost
2) Direct naive approach
Most naive: put in all possible actions at all levels (used in SATPLAN)
Less naive: union the states associated with all actions at each level
Solution extraction cost goes higher than for 1.
3) Enforce partial 1-consistency (at O(n) cost)
Here unsupported conditions are precluded from the proposition levels
Solution extraction cost goes higher than for 1.
4) Enforce (partial) 2-consistency
Consider pairs of props to see if all are consistent. (Graphplan does this
with mutexing) Basically constraints such as At(R E) => ~At(R M) get added.
Refinements can now be seen as "canned" inference procedures that try to increase the
local consistency of a CSP problem.
Given a disjunctive structure of partial plans (such as a planning graph) you must now
decide how to check for (i.e. extract) a solution. This is the topic for the next
class.