Notes Thu. 30 Jan 2003 (scribe -- Andrew Davis, drewdavis00@hotmail.com) Registers problem from the homework: Assume that -You have a bunch of registers (r1, r2, r3,...) -A register can have a contents -There are at least 3 registers -There is a write operator (essentially takes one register and writes its contents onto another register) In the goal state, you want the initial contents to be swapped. Initial State Goal C(r1,a) C(r2,b) C(r2,b) C(r1,b) . . . This problem is very easy to solve for the current generation of planners. But in the old days, certain planners couldn't even solve this problem. This is due to an concept called "serializability." The registers problem is "non-serializable." Suppose there is a planning problem with k goals. If there exists some permutation g of those k goals g1, g2, g3, ... gk such that g1 can be completed first, g2 can be completed 2nd, ... and so on .... and gk can be completed last, then the goals are said to be serializable. If there are k goals, then the number of possible permutations is k!. A set of goals is trivially serializable if a large proportion (>50%) of the possible permutations will work. A set of goals is laboriously serializable if a small proportion (<50%) of the possible permutations will work. A set of goals is non-serializable if a none of the possible permutations will work. A set of goals is independent if all of the possible permutations will work. In the registers problem, if you first try to write the contents of r1 to r2, then the contents of r2 are wiped out, and the goal of copying the contents of r2 to r1 becomes impossible. Similarly, if you first try to write the contents of r2 to r1, then the contents of r1 are wiped out, and the goal of copying the contents of r1 to r2 becomes impossible. The STRIPS planner would make the assumption that any given problem was serializable, and so it would fail on a non-serializable problem such as the registers problem. A few examples: Given a blocks-world initial state with all blocks on the table A B C D --------- If the goal state is A C B D --------- then this is an independent set of goals, because the 2 goals can be accomplished either of the 2 possible orders. ON(A,B) ON(C,D) then then ON(C,D) or ON(A,B) The goal state (starting from the same initial state) A B C --------- is not independent, but is serializable. Given the initial state C A B --------- the goal state ON(A,B) and ON(B,C) as shown below A B C --------- is not serializable. This is known as the "Sussman Anomaly." Note that the given goal state is not complete. If a complete description of the goal state is given, ON(A,B) ON(B,C) ON(C,TABLE) CLEAR(A) HANDEMPTY() then this goal is serializable. The first goal in the permutation would be ON(C,TABLE), and so on... Knowing if a problem is serializable is important, because it affects how expensive it is to find a plan. Finding a plan for an independent problem is very cheap, because all goals can be accomplished in any order or even in parallel. A trivially serializable problem is cheaper to solve than a laboriously serializable problem. The register problem can be made serializable by giving a complete description of the goal state. This would require adding a contents for r3. (As well as in the initial state.) But in general it is more desirable to be able to give a partial description of the goals, wherever possible. That makes the task easier for the person who designs the set of goals. Otherwise they are compelled to consider every possible value. ********* Planning algorithms flow from proofs of correctness of the plans. If we have k different proofs of correctness of the plans, then we have at least k different search algorithms with which to find a plan. We have discussed 3 different proofs: Progression, regression, and causal proof. In any case, you start with an empty plan and keep extending it until the plan that you have satisfies the chosen proof procedure. Progression -- Start with the initial state. An action can be applied to a state only if the preconditions (partial assignments of values to variables) for that action are holding in the given state. If this is the case, then the new state is given by copying the effects of the action into the new state, and all other values remain unchanged from the previous state to the new state. When a state is reached where all the values of the goal state hold, the problem is solved. This is done with a queue of search states. A node is picked from the queue and a check is performed to see if you are done (the goals that you are trying to achieve are given in that state). If not, then the state is expanded (all applicable actions are applied), producing children, and then the children are put back into the queue. For a progressive search--as it is for any sort of search--, the major issue is how the queue is managed (prioritized -- depth-first search, braedth-first search, etc...). This is a question of heuristics, which will be covered more in depth later in the course. Regression -- Start at the goal state. Actions are applied backwards to a state S. This means finding the weakest statement about the state of the world that must hold before the action A is taken. Everything which is present in the effects of action A must hold in the state S (the current goal state) which follows action A. So no action is possible whose effects would contradict the values of any of the variables of state S. Anything which is not present in the effects of action A must have the same value in the state S' (the "regressed" state -- the state preceding action A) as it does in state S which follows action A. Everything which is a precondition for action A must hold in state S' preceding the action. Stop when the current state is consistent with the initial state. Additionally, although this is not really a REQUIREMENT of regression search, any action A applied to a state S regressively should have at least one variable V in its effects which has the same value as that same variable V does in the current goal state S that it is being regressively applied to. (Since state S is only a partial state, not all variables will have assigned values.) This aids the regression search by helping to avoid useless actions, although it will not necessarily prevent all useless actions. One argument in favor of regression search is that it often has a much smaller branching factor than progression. In regression, because the states are partial states, they actually represent a set of states in the progression space, rather than just a single state. This means that the search space is a space of sets of states. So if there are n states in the progression search space, there are 2^n states in the regression search space (the power set). One disadvantage to regression searches is the possibility of generating "dead states" which are physically impossible in the given domain. An example of this would be the state holding(A)/\~clear(B) in a blocksworld with only two blocks. It is even possible that a dead state could be expanded further into even more dead states, which could turn out to dominate the search. In fact, this could turn out to be worse than a progressive search. Trying to test for the validity of every state turns into theorem proving, which is expensive. In addition, such testing would not necessarily be domain-independent. Causal Approach (Plan-Space Planning) -- For every goal in the plan (the final goals as well as every precondition, which are also goals), there must be something in the plan supporting that goal. And no intermediate action (between the original action and the goal) may undo that goal. If all goals hold, then the plan works. (Don't think in terms of states anymore. Think in terms of establishing the truth of each of the goals.) The initial step is a null step which only has effects -- the initial state. The goal step is a null step which only has preconditions -- the goal state. Start with: -a null plan, which consists of only *the initial step S0, and *the goal step Sinf -the ordering S0 < Sinf -the goal step Sinf has all the top-level goals as its preconditions -the initial step S0 has all the initial conditions as its effects The plan is done when all the goals are supported. A goal is supported when there is a causal action which precedes it chronologically in the plan, and which has an effect that can be used to support the goal, but for which no other action comes in between the causal action and the goal that would undo the goal. So if each goal/condition in the plan is supported, then the plan is done. Keep track of all "open conditions" -- conditions which are not yet supported. Select an open condition and find a step to support it. This may be a step which already exists in the plan, or it may be a new action added to the plan for this purpose. When a condition is supported by an action in the plan, it is no longer an open condition, so it is removed from the list of open conditions. Once such an action is selected, a "causal link" is set between the step with the action and the step with the goal, to keep track of the supported condition. This enables us to ensure that no new, subsequent action undoes it. When a causal link has been established, it is important that no new action that would undo the condition comes in between the action which causes it and the action which has it as a precondition. This is often done by simply putting the new action before the action which causes the condition (promotion) or after the action which has the precondition (demotion). The number of open conditions may either be increasing or decreasing as the plan is developed. Early on, as actions are added, the number of open conditions will generally increase. However, as a solution gets near, the number of open conditions will decrease until it reaches zero, and a solution is found. (Assuming, of course, that a solution exists.) Each open condition is associated with a particular step. So at the beginning, the open conditions are in the form C1@Sinf, C2@Sinf, C3@Sinf, ... These correspond to the goals. An "unsafe link" is a causal link and a "threat," for example P (S1--->S2; S3) ^ ^ | | | threat | causal link This is an unsafe link if S3 has effect ~P and it is possible that S1 < S3 < S2. At the beginning -list of open conditions -no unsafe links A partial plan is complete (is a solution) when it has no "flaws": -no open conditions -no unsafe links Remove open conditions by puting in causal links to support them. Remove unsafe links by -promotion: put S3 before S1 -demotion: put S3 after S2 -confrontation Confrontation: if S3 has Q=>~P and P is a precondition for S2, then we can set ~Q as a precondition to S3 (as an extra open condition) This ~Q is called a "preservation condition" A Partial Order plan is called "partial order" because it has a precedence relation between steps. Start with the precedence relation S0 < Sinf. As new steps are added, for any new step Sn we must have S0 < Sn. And for any new step Sn' we must have Sn' < Sinf. So if new steps Sn and Sn' are added, with no order specified between the two, then the plan looks like Sn / \ S0 Sinf \ / Sn' with precedence going from left to right. This indicates that either Sn may come before Sn' or Sn' may come before Sn, but neither of them may come before S0 or after Sinf. This is a partially ordered plan. possible for any one step to come before another. Or after the other. For example, it is necessary that S0 < Sn. And it is necessary that Sn' < Sinf. It is also possible that Sn' < Sn, and it is possible that Sn < Sn'. At this point, there are two possible reasons that it would be necessary to add additional precedences. Suppose that at some point in time, Sn' requires P, and an effect of Sn is P. In that case, a causal link would be set between Sn and Sn'. Which means that Sn < Sn', so a new precedence has been set. This gives P Sn--->Sn' so now, no step which comes between Sn and Sn' may have the effect ~P. On the other hand, suppose that P S0--->Sn' has already been established as a causal link (earlier in the plan), and ~P is an effect of Sn', and P is a precondition of Sn. Then there are three choices S0--Sn'--Sn Sn--S0--Sn' S0--Sn--Sn' The first case is not allowable, because Sn requires P as a precondition, and ~P is an effect of Sn'. The second case is not allowable, because of precedence constraints. No step may precede S0. So, unless there is a resolution through confrontation of Sn' (to cause it to not have effect ~P), the third case is the only choice. So, although there are three branches to make an unsafe link safe, two of them turned out to not to be possible. Planning Terminology -------------------- Step: a step in the partial plan -- which is bound to a specific action Orderings: S1S2): a commitment that the condition P, needed at S2 will be made true by S1 Requires S1 to "cause" P -Either have an effect P -Or have a conditional effect P which is FORCED to happen *By adding a secondary precondition to S1 P Unsafe Link: (S1--->S2; S3) if S3 can come between S1 and S2 and undo P (has an effect that deletes P). Empty Plan: { S:{I,G}; O:{I~P and we set ~Q as a precondition), it is also possible to force some conditional effect to be carried out by making the antecedent true as a precondition. For example, suppose that Sn requires P as a precondition. And suppose that S1 has R=>P as an effect. And suppose that no other step produces P as an effect. Then R can be set as a precondition to S1, which then causes P to be an effect of S1, and a causal link can then be set from S1 to Sn. This R is called a causation condition, and this is the opposite of confrontation (where the ~Q is called a preservation condition). In confrontation (with a preservation condition), the conditional effect is prevented from happening. In a causation condition, the conditional effect is forced to happen. A plan is a 5-tuple of Steps, Orderings, Open Conditions, Causal Links, and Unsafe Links. In the Empty Plan above, the Steps are I and G. The Orderings are I