Compilation of Email Discussion on the topic of Planning as Satifiability. CSCE976 Spring'2002 ================================================== Date: Tue, 12 Feb 2002 09:04:34 -0600 From: Amy Davis Subject: Tibor's Minutes Addition: We discussed the encodings in class -- especially the first two encodings -- direct from graphplan and linear. I would like a summary of how each of these encodings works, because we spent a fair amount of class time on them. Here's what I remember: Graphplan has different levels -- with actions taking place between states. Each level is a particular time slot. In encoding GraphPlan into SAT, we take the plan built by GraphPlan and first encode the start and finish facts. Then we assume that at each level, an action implies it's pre-requisites, and one of the possible actions is taken. These translate into sentances that then become part of the problem statement. In a linear encoding, it is assumed that only one action takes place at a time, and that each action implies both is pre-requisits and its effects (at different time stamps). Then frams axiom is used to carry truth values through the different time stamps (as a no-op). We're handing in the state-based Wednesday. O __ || / \_ CH2 -O- C - CH2 - CH2 - CH3 \ __ / Stop and smell the Roses! ================================================== Date: Tue, 12 Feb 2002 14:30:48 -0600 From: Robert Glaubius Comments on the minutes from Feb. 2 and 4 discussions - In the listing of the material's contrabutions, it is important to note that stochastic search is demonstrated, but not necessarily proven to solve larger planning problems. Due to the space of problems in question, it is likely that there exist an infinite number of planning problems in which systematic search will outperform stochastic search most of the time. Reasearch into phase transition behavior in planning problems would likely uncover this "anomalous" behavior, I expect. - Not sure I understand the comment "FOL without negation is NP-Complete" from the final paragraph of the minutes. FOL itself is a logic, and therefore time complexity is not applicable. Induction is difficult in FOL, and induction in FOL without refutation is incomplete (assuming that then your set of induction rules is then limited to resolution), Finally, FOL without negation reduces the expressive power of FOL. ================================================================= Date: Tue, 12 Feb 2002 18:22:03 -0600 (CST) From: "Berthe Y. Choueiry" Rob> Due to the space of problems in question, it is likely that there Rob> exist an infinite number of planning problems in which systematic Rob> search will outperform stochastic search most of the time. and vice versa... Rob> Not sure I understand the comment "FOL without negation is Rob> NP-Complete" What is meant is "entailment in FOL-without-negation is NP-Complete." This is a comment I introduced, my error. The reference to LO15 reduces the ambiguity as one could have checked it out... > Induction is difficult in FOL, and induction in FOL without > refutation is incomplete (assuming induction is typically not even sound... I guess you mean deduction:-) > Finally, FOL without negation reduces the expressive power of FOL. Correct, and this was one of the simplifications adopted by STRIPS. Comments? -Berthe Y. Choueiry choueiry@cse.unl.edu ======================================================== Date: Tue, 12 Feb 2002 15:41:13 -0600 (CST) From: Lin Xu To: cse976-ml@cse.unl.edu Comments on the minutes from Feb. 2 and 4 discussions - In paper "Pushing the envelope:planning, prepositional logic, and stochastic search". I want mention that the encodings they used in their experiments were created by hand, based on their understanding of the semantics of the various benchmark domains. This is not very serious since which also means different people can do this in different way. It also will limit the real application - It will be nice to find the relation between type of problem and method could solve them. In the paper, we only know most time walksat is better, but it not always good. Does it have some kind of relation for example, for some type problem walsat is better, but another it will appearly not. .'* :`...' `.,' ' `. ' .**. ; ; ': ` ``:`****,' .' : ..::. ``**":.'' `. .: `: ; `,' : For everyone you love and love you! `: ` : ; : : : ; : : : .: : : :..,' ``::. Lin Xu `....:..' ..:;'' .: . ...:::: ,'''''``::::::: `:::: `::. `:: ================================================================= Date: Tue, 12 Feb 2002 18:41:16 -0600 (CST) From: "Berthe Y. Choueiry" > - It will be nice to find the relation between type of problem and > method could solve them. In the paper, we only know most time > walksat is better, but it not always good. Does it have some kind of > relation for example, for some type problem walsat is better, but > another it will appearly not. Remember that such a criterion is unlikely to exist because of NP-completeness (at least...). One can imagine perhaps some empirical evaluations... on random problems (?!). But, what is a `good' random problem? I am not convinced that any random problem is representative of reality. In short I have no answer to the second issue Xu Lin raises. Anyone comments? Thanks, -Berthe Y. Choueiry choueiry@cse.unl.edu ================================================================= Date: Wed, 13 Feb 2002 00:28:56 -0600 From: Robert Glaubius > I am not convinced that any random problem is representative of > reality. I wonder -- isn't it possible that every random problem is representative of some set of real-world problems and it's just that nobody has noticed it yet : ) ================================================================= Date: Wed, 13 Feb 2002 12:55:40 -0600 (CST) From: "Berthe Y. Choueiry" > I wonder -- isn't it possible that every random problem is > representative of some set of real-world problems and it's just that > nobody has noticed it yet : ) In the discussion about random problem, I confess I have taken a strong stand , trying to make a point. In the IJCAI-97 Workshop on Empirical AI (among other meetings), the usefulness/ meaningness (?) of random problems have been discussed. I particularly like the argument of David Poole arguing the (real) world is *not* random otherwise we would *not* have been able to survive as a specie. I'll print out his one page summary and provide it in class. The (short) proceedings are available from: http://dream.dai.ed.ac.uk/group/tw/empirical/1997/proceedings.ps The short (and very interesting) report by Toby about the workshop are available from: http://dream.dai.ed.ac.uk/group/tw/empirical/1997/aimag.ps Enjoy :-) -Berthe Y. Choueiry Assistant Professor Tel: +1(402)472-5444 Department of Computer Science & Eng. Fax: +1(402)472-7767 115 Ferguson Hall Email: choueiry@cse.unl.edu University of Nebraska at Lincoln URL: www.cse.unl.edu/~choueiry/ Lincoln, NE 68588-0115 ================================================================= Date: Wed, 13 Feb 2002 00:13:26 -0600 From: Daniel Buettner In the section on Graphplan, it says: -> Once a plan of length n is found, the algorithm can go back -> and optimize it, by looking for subplans that can be -> executed in parallel. This isn't quite true, as Graphplan naturally puts actions in parallel while searching for a solution. Once a solution is found, it doesn't need to go back in order to make subplans parallel. But, since we hadn't covered Graphplan yet, it's not too surprising that we weren't clear on the details. There are a few references in the notes to the "assessment anomaly" -- this should read the "Sussman anomaly". I think that it is also important to point out that the stochastic solver was able to solve every member of the (admittedly self-selected) set of sample problems when using "direct" encodings. The other planners could at best solve two thirds of the tested problems. -- ~ ~ ~ "Daniel Buettner" line 4 of 4 --100%-- ================================================================= Date: Wed, 13 Feb 2002 08:40:27 -0600 From: Tibor Moldovan hmm, i thought all the refferences to the "assesment anomaly" were corrected to sussman anolmaly. i emailed dan a separate file, and it is possible that i've emaild an earlier version. i will verify that. tibor ================================================================= Date: Tue, 12 Feb 2002 22:41:59 -0600 From: Shabbir Ali Syed Comments to the discussion : The goal acheived here is that there is a possibility shown to use stochastic algorithms to solve state based encodings of logistic problems that cannot be solved by any other domain independent planner. However it is not clear how it is advantageous to optimize the gross statistical properties of an axiomatization when choosing between declarative statements. Also one observation is: encoding resulting from compiling away states, leaving "ation based "encoding are similar to causal encodings and the worst case size of the action based encoding is better than of the state based encoding. Also, I dont consider this approach to be domain independent because, the no. of actions that actually account for a change in the truth value of the fluents was small, in the domains considered. Graduate Student CSCE UN-L =================================================================