Fwd: Notes for Thu. Jan 30

[Subbarao Kambhampati <rao@asu.edu>]

Outstanding job, Drew! I was able to reconstruct the plan almost 
minute-by-minute with your notes...
And the notes were almost free of errors (about the only ultra-minor point 
is that at one point you say that "the main issue in progressive search is 
how to maintain search queue"--it is the main issue not just in 
progression, but every possible kind of search).

Great job. Worth the wait.

Rao

ps1: I have verified these--so you don't have to...

ps: to others--this is sort of a early high-water mark--see if we can do 
better..

> Date: Wed, 05 Feb 2003 22:38:57 -0700
> From: Drew Davis <Andrew.M.Davis@asu.edu>
> Subject: Notes for Thu. Jan 30
> X-Originating-IP: [65.57.33.251]
> To: Mike.Rush@asu.edu
> Cc: rao@asu.edu
> X-OriginalArrivalTime: 06 Feb 2003 05:38:57.0498 (UTC)
>  FILETIME=[0B222BA0:01C2CDA2]
>
>
> Mike --
>
> Here are my notes for Thursday, Jan 30, 2003 for you to verify.  I still 
> haven't received the notes from you for Jan 28 for me to verify.  So if 
> you sent them already, I didn't get them.
>
> See you in class,
>
> -- Andrew Davis
> drewdavis00@hotmail.com
>
> **********************************************************************
> 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, 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.
>
> From this point, the question can be asked whether it is necessary or 
> 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: S1<S2  S1 must precede S2
>
> Open Conditions: preconditions of the steps (including goal step)
>
>
>                P
> Causal Link (S1--->S2): 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<G}, OC:{g1@G;g2@G...}, CL:{}; US:{}}
>
>
>
>
> Another aspect of conditional effects, in addition to being able to force 
> some conditional effect not to be carried out (by making the antecedent 
> false as a precondition, as was done above when we had Q=>~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<G.  The Open Conditions are g1@G and g2@G (assuming that 
> g1 and g2 are the only goals).  At the beginning, there are no Causal 
> Links or Unsafe Links.
>
>
> A "flaw" is
>   -an open condition, or
>   -an unsafe link
>
> A solution plan is a partial plan with no remaining flaws -- that is, when
>   -every open condition is satisfied by some action
>   -no unsafe link exists (i.e. the plan is consistent)
>
>
>
> POP Algorithm
> -------------
>
> 1)  Let P be an initial plan
> 2)  Flaw selection -- choose a flaw from the partial plan
> 3)  Flaw resolution
>       -if f is an open condition,
>          choose an action that achieves f
>       -if f is an unsafe link
>          choose promotion or demotion
>       -update P
>       -return NULL if no resolution exists
> 4)  If there is no flaw left, return P
>       else go to 2
>
>
>
> When selecting a flaw for resolution, it doesn't matter which flaw is 
> picked, because the order of flaw resolution does not matter.  (In terms 
> of whether a solution is found, that is.  It could affect how quickly a 
> solution is found.)
>
> When resolving an open condition, one choice is to select a step that is 
> already present in the plan that could potentially come before the open 
> condition, and that has an effect which satisfies the open condition.  If 
> there is more than one such step, then a separate plan (search branch) is 
> created for each such step, with that step acting as a causal link for the 
> condition.  Since it is possible that none of these steps may actually 
> work, it is also necessary (the second choice) to import into the plan all 
> possible actions in the domain that are not currently in the plan, and 
> which could satisfy the open condition.  The only necessary ordering for 
> these actions is that they must come after S0 and before Sinf and before 
> the step with the condition being satisfied.  Of course, when a new action 
> is brought in to the plan, its preconditions must be added to the open 
> conditions list.
>
> When resolving an unsafe link, the choices are promotion or demotion or 
> confrontation.  If there are no conditional effects, then the only choices 
> are promotion and demotion.
>
> All of the children produced by the flaw resolution go into the queue.  If 
> no resolutions exist for the flaw, then the plan's children do not go into 
> the queue.  So if a flaw cannot be resolved, then no further time is 
> wasted on plans which cannot work.
> **********************************************************************
>
>
> _________________________________________________________________
> Add photos to your messages with MSN 8. Get 2 months FREE*.
> http://join.msn.com/?page=features/featuredemail