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;