Notes for Thursday, Feb. 27, 2003 Memory Usage is Important -- Anecdote A problem with conversion - the size of the encoding can be larger. In 1998, Blackbox entered the planning competition. Everything until then said that Blackbox beat other planners. At the time, Blackbox was being tested on AT&T's 8 GB RAM machines. At that time the planning competition had a machine with a much smaller amount of RAM. Blackbox died because of lack of memory during competition and failed to win. You need to indicate the memory and CPU you're using in future projects. For project II, write a domain -- think of something that doesn't look much like block world and logistics. Last class - we were talking about converting a planning graph to CSP. Solving CSP encoding of planning graph takes less time, and it also takes less space. Why does CSP take less space? Memos take a significant amount of extra space for the graphplan algorithm. The amount of space for the planning graph is nothing compared to the space you use when doing the search. The more search you do, the more space you need -- the more space you search, the more memos you will learn. A lot of memos will be created that have nothing to do with the search for the solution. With graphplan, the more search you do, the more memos you learn. -> You fail fewer times with more directionality. When you talk about space, the maximum space used is all that matters. If you're one byte over your machine's memory capacity, you're dead. Information on CSP It's important to note that very specific things are less likely to fail. A thing to do in CSP solvers -- larger nogoods get thrown away, smaller nogoods are kept. Many people are interested in solving CSP problems, so there are many good heuristics. As of 2000, compiling into CSP was faster than compiling into SAT. But, currently, compiling into SAT is faster. SAT solver called CHAFF that's actually much faster than CSP. DCSP Sometimes it's better to think of a planning graph as a dynamic CSP (DCSP). This is a useful abstraction to have in mind. In normal CSP, all the variables, domains and constraints are given to you. All you're supposed to do is find assignments to variables such that none of the constraints are violated. How DCSP Works Given a bunch of variables, their domains and constraints, you're still supposed to find the assignments to variables such that none of the constraints are violated. But there's one trick. For specific values that variables take, you activate a bunch of new variables that you didn't even know existed (called activation constraints). For example: You have 1 million variables. 100 are activated initially. All you're supposed to do is give values to those 100 variables. Forget about inactive variables for now. When a variable takes on a value other variables are activated. There's a cascading effect. When you give values to variables more of them become active. Normal CSP is dynamic CSP where all the variables are active up front. Sometimes it's better to think of the planning graph as DCSP, then compile to CSP. Why is DCSP useful? Some variables cannot be solved together. The real problem is that as soon as you bring in an action to support a goal, all of the actions' preconditions become subgoals. Subgoals are variables that are "sleeping", becoming "active" during the solving process. The cascading -- all the goals need actions to support them. Anytime you put in an action, other goals become active. The open preconditions can then be thought of as "new variables" in the problem. Normally in planning, you don't know up front how many goals are going to come. Whereas, in the simplest version of DCSP, we assume the initial set of variables that are active are the goals. We also know the activation constraints, allowing us to think of each variable as it comes while solving. Configure Problems This kind of DCSP has been thought of in the CSP community before in problems called configuration problems. Think of configuring your computer. If you want to have a SCSI disk, you cannot have an IDE CD-ROM. So, as soon as you choose one think you must choose other things. Dynamic CSP can be compiled down to static ("normal") CSP Here's how you do it: The only thing added to DCSP from CSP is activation constraints. So, for every variable in the dynamic CSP, you add an extra value called a null value (#). If a variable takes a null value, then that variable is inactive. If you want a variable to be active, you say that it cannot take a null value. Removing Irrelevant Variables If you have the entire planning graph, and the last level of the graph has 10000 propositions and you only have 4 top level goals. You only need to worry about those 4 top level goals. Why should we write constraints about the other 9996 propositions? The irrelevant search space won't be looked at anyway! One way to do this is mark goals as "in". Anything connected variables marked "in" become "in". So, there's an "in" propagation. This is not search, this is just a simple propagation. Only consider those that are "in". This cuts down on the number of constraints and variables that you need to write. For example, a mutex constraint between an "in" variable and an "out" variable wouldn't need to be written. Converting Planning Graph Propositions Each planning graph proposition is assigned a mapping for the level that it's in when it's converted to CSP. So, a proposition called P in level 2 of the planning graph will be called something like P-2. When you convert back, you'll know the ordering of the plan because of the mapping done with the planning graph. A similar mapping is done with actions. Looking at Constraints as Procedures (Implicit Constraints) A constraint in CSP lets us take an assignment and ask "am I happy with this" (i.e. does this conflict with our constraints)? For example, we have the assignments: x1=1 x2=3 x4=5 And the constraint: ~(x1=1 ^ x4=5) If you give this assignment, the constraint will say "no" (this conflicts). We could either write constraints, or we could write this as a procedure. You could give the assignments, and the procedure could output "yes" or "no". Sometimes writing the constraint in the declarative form takes up too much space. For example, how do we say X1 < X2 (where X1 and X2 have domains from 1..1000)? You'd have to say: ~(X1=1 ^ X2=2), ~(X1=1 ^ X2 = 3), ~(X1=1 ^ X2=4)... This will take a lot of space. Look at this as a procedure that returns "yes" or "no". Given an assignment for X1 and X2, the procedure will tell you what whether the constraint is satisfied using X1 < X2. This is an implicit constraint. Mutex constraints can be thought of in a similar way. Many mutex constraints involve a given pair of variables. In the normal encoding, we might have ~(P1 = A1 ^ P2 = A3), ~(P1 = A2 ^ P2 = A4). This can be compacted into Mutex(P1, P2). (Note - implicit constraints are also known as closed-form constraints) This can significantly improve the amount of space taken for a particular problem. Advantage - Thinking of constraints this way helps us to understand the notion of forward checking and DDB. They are a special case of resolution. SAT encoding does not have this advantage. Recall, forward checking is the process where whenever a variable X is assigned, we look at each unassigned variable Y that is connected to X by a constraint and delete from Y's domain any value that is inconsistent with the value chosen for X. Also, DDB is dependency-directed backtracking, where when a failure is detected we determine which propositions cause the failure. SAT Encoding SAT is always written in a declarative fashion. SAT is just CSP with only boolean variables. How do you convert CSP to SAT? Just make each assignment into a boolean variable. When you want to say X1 < X2, you say that X1=1 is one variable X1=2 is one variable, etc. How does EBL get done in CSP contrasted with what is done with graphplan? From the slide from week 6: variables/domain: x, y, u, v: {A, B, C, D, E} w: {D, E} l : {A, B} no goods (constraints): x=A => w != E y=B => u != D y=B => w != D u=C => l != A v=D => l != B (remember: ~x=A ^ w!=E converts from (x=A => w!=E). Constraints have no direction. This is a logical implication. It doesn't matter whether x=A happens before w=E or w=E happens before x=A. The constraint tells us to prevent both from being true at the same time.) The following is just one variable ordering search tree to illustrate DDB & EBL in CSP. N1: {x=A} | v N2: {x=A^y=B} | v N3: {x=A^y=B^v=D} | v N4: {x=A^y=B^v=D^u=C}----- | \ v \ N5: {x=A^y=B^v=D^u=C^w=E} \ v N6: {x=A^y=B^v=D^u=C^w=D} Once a constraint is violated you cannot fix it without backtracking. When we have w=E and x=A at N5, we have violated a constraint (namely x=A => w != E) and that node is dead. What's the explanation for the failure? One thing we can say is that the entire node is the explanation. Another idea is to find the constraint that is violated and to call that the explanation (in this case x=A => w != E). When the node is dead and you get an explanation, it is what you undo. But suppose there were multiple reasons that the node died there. Suppose there is one more constraint which says x=A ^ y=B ^ v=D => w!=E. Now we have multiple explanations for the failed node N5. Which explanation do we choose? We can choose the smaller explanation. This will likely provide us with specific information. But it might be better to choose the older explanation -- we want to backtrack as far up the tree as we can. It's good to blame something higher up the tree so we can change everything from then on (so we won't run into the same constraint when searching on the tree). We would like to pick the smallest explanation and the oldest explanation because it would have us backtrack further up the tree. Where do we backtrack to? We want to go back to where the explanation first occurred. In this case, it is just one node back to N4. We have save the explanation for the failure in N5 with N4. We then choose w=D, going to N6. We have violate another constraint (y=B => w != D). We backtrack one node again and saved N6's failure explanation. There are no other assignments we can make. Now we have proven that N4 is dead because its children are dead. When we regressed up to N4, we recorded the explanations of the children's death. N4's failure reason is the conjunction of the regressed failure explanations of its children. So, N4 died because y=B ^ x=A. We now move up the tree until the explanation for failure changes - up until it is not the case that y=B ^ x=A, the node N1. Intelligent backtracking has been performed in this search. The search avoided searching on failed nodes. The search has also learned a derived constraint - y=B ^ x=A. If we ever find a derived explanation y=B ^ x=A we don't have to go all the way down. We can immediately kill that node because it's a nogood. It's no good to have too many no goods Depth first search takes linear space to solve CSP. But, with nogoods, it takes exponential space. Also, each nogood has to be verified with each state. So the more nogoods you have, the more time it takes to check all of the nogoods against the current state. We want to remember only some of the nogoods even if it means we might repeat some of the failures. What nogoods to remember? (Pruning) There are a lot of ways to reduce the number of nogoods you remember. First, forget remembering large nogoods. They are less likely to be useful the second time around and there are more large nogoods than small nogoods. Size-based pruning The smaller the nogood is the more powerful it is. Limit the size of nogoods stored to k or less (k<