From tson@sagarmatha.eas.asu.edu Wed Feb 16 17:51:04 2000
Date: Wed, 16 Feb 2000 11:27:09 -0700 (MST)
From: tson
To: binhminh@sagarmatha.eas.asu.edu
--------------------------------------------------------------------------------
----
Note on Feb 14 Class. Note taker: Son Cao Tran
Topics: + Disjunctive Planning
Papers involved:
1. Rao's paper: "Planning as Refinement". AI Magazine.
2. Rao's tutorial paper at IJCAI-99.
--------------------------------------------------------------------------------
----
First, Rao was talking about his 2 1/2 rush days to get the NASA proposal done.
Mathematically, the chance for his proposal being accepted is 1/2000 - since
there were 2000 proposals submitted:-)
He mentioned that one of the goals of the proposal is his goal for the course:
by the end of this course we will know how to do planning in temporal domains where
actions have durations and propositions (variables) can have continuous values.
Starting from Wednesday, we will talk about scheduling. Papers for this topic
include Smidth's paper and the AAAI-tutorial on knowledge based scheduling --
which he will give us the copy by tomorow (Tue.) We will see that ILP, CSP,
SAT techniques are also useful for scheduling.
Topics of the day:
* Solution extraction in disjunctive plans:
+ after refinement, a k-length disjunctive plan contains too many potential
k-length plans ==> need for solution extraction
+ two approaches: direct or compiled solution extraction
* Direct methods: graph plan backward search; graph plan local search
+ graph plan backward search
+ other direct extraction strategies
* Compilation
+ CSP
+ SAT
+ ILP
It is obvious that each SAT-problem can be viewed as a CSP-problem; and
each CSP-problem can be viewed as ILP-problem.
(Binhminh: Rao, you did seem to say that in the class. But I think
that ILP is like special kind of CSP, where there is structure in the
value-set (domain), and the constraints are of three special types :
"<",">", "=". It's quite straight forward to convert CSP to SAT and
vice-versa, but there is no obvious way to convert directly from CSP to
ILP, and vice-versal. We can go around by CSP->SAT->binary ILP and
ILP->SAT->CSP, but I can't imagine of the direct way, because in
general, the domain of CSP variable is a collection of discreet
values, and we are normally deal with them as individual values with
no relation)
why then we talk about three different compilation methods?
+ ILP and CSP have different search improvement techniques. Thus, knowing
both methods could be useful; especially in developing the solution
extraction procedure for Graph Plan (GP)
+ ILP is useful to handel continuous values.
(Binhminh: ILP/LP look at problem more "globally", and CSP look at the
problem more "locally". Actually, if we don't use LP relaxation as the
tool for setting bound, get heuristic values on which var and which
value to branch on, then ILP will be solved by branching, which is
somewhat similar to CSP. Thus, will be more concern about the problem
"locally". However, LP relaxation has been dominant method, and the
ways Simplex used to solve the problem by matries (over all variables)
operations, ILP/LP turn to be more "global" in the way they solve
the problem).
* Compilation:
There are two steps in plan encoding. The first step is to identify
"what are the constraints"; and the next step is "write down these
constraints" - or encoding.
In every encoding, the constraints set up lines of the proof for the
correctness of the plan.
We are only interested in "bounded length" plan. The
reason is that planning is outside NP-complete, i.e., it is harder than NP-hard. There
are planning domains where the minimal plan has the length exponential to the size
of the domains - one example is the "Tower of Hanoi" planning domain.
* We discussed two types of encoding: State-based Encoding and Causal Encoding
- State based encoding: further divided into two types:
+ progression; and
+ regression.
In either type, frame axioms have to be written, though in different styles.
In progression encoding, "classical frame axioms" have to be written.
For regression encoding, we have to write "explanatory frame axioms".
We discussed the question: "Why progression?" and "Why regression?"
+ it is proved that the number of clauses in regression encoding is smaller
than that of progression encoding.
+ it is empirically proved that regression encoding is faster
than progression encoding.
(Binhminh: As Rao said in the class, the comparison is kind of bias
here. Because regression encoding allow parallelism, there are many
domain (e.g logistics) in which the length of the encoding required to
get the solution in regression encoding is smaller than the
progression encoding of the same problem. Therefore, we are kind of
comparing orange and apple in those domain, where the starting point
of the regression encoding is much better with a lot smaller
encoding. Rao said that no one has check the comparion for serial
domain, where the length will be the same for both encodings)
Important to note: the three factors influencing performance in CSP are (i)
number of variables; (ii) number of constraints; and (iii) size of constraints
If we compare the two encodings (progression, and regression), we can
see that the numbers of variable are the same in for two types of
encoding, but the number of constraint of the regression encoding is
smaller, but the size of constraint is bigger than the progression encoding.
Notice that besides (i)-(iii) we have to take into consideration (iv) the
"degree of local consistency" when in comparing two CSP problems. This is the most
important factor in determining the easiness in solving the
problem. However, it is normally too difficult to determine the
degree of local consistency. Therefore most of the comparisons are
done without considering (iv).
The notion of "degree of local consistency" is similar to that of "closeness of
intergral hull" in ILP.
- Causal encoding: steps for causal encoding and its alternatives can be found
in the slides. As it turns out, the number of clauses of causal encoding is
bigger than that of state-based encoding;