Handling Operator Schemas Can be done in three ways: 1) We can write all ground operator instances a priori 2) We can write all ground operator instances after seeing the problem (such as puton(X,Y,Z) where X,Y,Z is substituted with ALL combinations of the blocks A,B,C in the blocks world example above). Note that this is different from forward state space search. Suppose to we have one action Puton(x,y,z) and three blocks we can write the (3!) actions and use them instead of the single action 3) We can do planning with incompletely instantiated operators! Even here, we can do one of two things -- let the library contain only the uninstantiated actions (such as Puton(x,y,z)). But, when you need to introduce an action into the plan to establish some condition, make sure that the action is completely established. [e.g. You need to establish On(B,C) at step S, and you decide to use the action Puton(...)--so you realize that you need Puton(B,y,C). Rather than introduce that action you introduce each instantiation of Puton(B,y,C)--where y is substituted with one of the possible objects (blocks) in the problem. If your problem was dealing with a total of four blocks, A,B,C,D, then you can substitute A or D for y-- for each of those choices, you make a separate partial plan] [In a way this approach is similar to what we do with operator templates in forward and backward state space planning] -- THe second way is to let the plan contain a partially instantiated action. To understand the motivation behind this, note that in the example above, the only thing that we know for sure about puton() action is that its first argument has to be B and the last one C, so that On(B,C) will be an effect given by it. the middle argument, y, is not constrained by our current establishment decision. Trying to give it a value at this point is PREMATURE in a way similar to PREMATURE ordering of actions By allowing partially instantiated actions into the plan, we can extend the least-commitment to variable bindings also. Extending flexibility to objects Known as least commitment to objects Uses partially instantiated operations One worry is that we may terminate without completely binding all objects. In such a case, the agent does not know what the plan is (since the specification of some of the objects is incomplete). THis worry is unfounded since By the time all final conditions are satisfied, all variables will be bound [This is because every variable of an operator schema will occur in at least one of its preconditions, and the preconditions of the operators are finally (transitively) satisfied form the initial state--and initial state is completely specified (i.e., has no variables).] How does a plan change? The plan will now have bindings in addition to steps, orderings and links Bindings are constraints of the form x = y, x = A and x!=y x!=A where x, y are variables 1) Establishment portion changes - existential conditions TO establish a condition On(x,y) at step S, we need to find a step S' (from library or currently in the plan) such that S' has some effect (say On(u,v)) such that On(u,v) can UNIFY with On(x,y). Once this is done, we add the binding x=u, y=v to the set of bindings of the plan. (of course, we will still add the ordering and link constraints as before). 2) When is a link violated? Suppose we have a link and a step S'' which can come between S' and S and has a delete list literal On(x,y) [since S'' can be partially instantiated]. Now, IF x and y become equal to A and B respectively, then S'' will become a real threat. As of now it is only a potential threat. -- We now face the question-- SHOULD WE worry about this threat? We have two reasonable options --One: the conservative "wait and see one"-- Here we wait until the potential threat becomes a real threat, and handle only real threats [This will work since eventually, all variables have to get bound anyway.] The threat resolution will be the same as before--involving promotion and demotion The good point about this strategy is that eventually, x and y may actually get bound to C and D respectively, in which case, the potential threat between S'' and the link never occurs. So, we don't have to waste time doing conflict resolution (and increasing the branching inthe search). --Second: the EAGER "let's get the potential threat" one Here, we try to handle the potential threat right away. If we do so, we need to generalize the threat resolution. In addition to promotion and demotion, we need to consider the scenario where we force S'' to be a non-threat. We can force S'' to be a non threat in our example by "SEPARATING THE VARIABLES" --i.e., adding either the constraint x != A or the constraint y != B (and generating one partial plan for each possibility) In this kind of situation, the partial plan's consistency needs to be checked not just with respect to orderings but also with respect to bindings (EG: if there is a constraint x = y, y = z , and x != z, then the constraints are inconsistent ) *** EMPIRICAL RESULTS SHOW THAT THE CONSERVATIVE "WAIT AND SEE" APPROACH IS MUCH MORE EFFICIENT THAN THE EAGER APPROACH. THIS MAKES SENSE AS IN GENERAL, EAGER APPROACH MAY BE WASTING ITS TIME RESOLVING THREATS AND INCREASING BRANCHING FACTORS, WHEN IF IT JUST WAITED A BIT, THOSE THREATS MAY HAVE GONE AWAY. [OF COURSE, THIS IS A HEURISTIC CONCLUSION--WE CAN COOK UP A SCENARIO WHERE WAITING UNTIL A POTENTIAL THREAT BECOMES REAL THREAT MIGHT ACTUALLY BE VERY QUITE CATASTROPHIC --SORT OF LIKE THE PROVERB 'A STITCH IN TIME SAVES NINE' ] ============================================================================ Example: Least Commitment to Objects (Partially Instantiated Operations) Initial state: |A| |B| |C| |D| -------------- For goal state, want cl(B) and cl(C). t(0) --------------> t(infinity) cl(B) cl(C) First, pick cl(C) to satisfy (no action required) cl(C) ------------> t(0) --------------> t(infinity) Next, pick cl(B) to satisfy (use puton(A,B,X), where X is an uninstantiated variable). cl(B) ---------------> cl(C) -----------------------------------------> t(0) ------------> puton(A,B,X) ------------------> t(infinity) Finally, X will get instantiated when we work on the precondtion On(A,X) of the step Puton(A,B,X). ============================================================================ Example of partial plan search tree with backtracking. Given the start state |A| |B| |C| ---------------------- and the desired final state |A| |B| |C| ---------------------- The search tree will be as follows: t(0) ---> t(infinity) on(B,C) on(A,B) | | First, pick on(A,B) for establishment | V Yields two separate branches (first branch is shown immediately below, second branch is shown later). First branch: on(A,B) -----------> t(0) -------------> t(infinity) Pick on(B,C) at tinfty to work on next on(B,C) -----------> on(A,B) -------------------------------------> t(0) -----------> puton(B,X,C) -------------> t(infinity) Now, achieve cl(B) at puton(B,x,C) cl(B) on(B,C) ---------> -------> on(A,B) ------------------------------------------------------------> t(0) ------------> puton(A,B,Y) -----------> puton(B,X,C) ---------> t(infinity) But there is a conflict, since puton(A,B,Y) deletes the required condition of on(A,B). The conflict can't be resolved by promotion or demotion since puton(A,B,Y) is plunk in the middle of t0 and tinfty, which are the first and last steps of the plan. so this branch is a dead end. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Then the second branch is explored: on(A,B) ------------> t(0) --------------> puton(A,X,B) --------------> t(infinity) on(A,B) --------> on(B,C) ---------------------------------> t(0) -------> puton(B,Y,C) ----------> puton(A,X,B) ----------> t(infinity) on(A,B) --------> on(B,T) on(B,C) -----> ---------------------------------> t(0) -------> puton(B,T,C) ----------> puton(A,X,B) ----------> t(infinity) on(A,T) ---------------------> cl(C) on(B,C) --------------------> ---------------------> cl(A) cl(B) on(A,B) --> --> --> t(0) ----> puton(A,B,T) ----> puton(B,T,C) ----> puton(A,X,B) ----> t(infinity) on(A,T) ---------------------> cl(C) on(B,C) --------------------> ---------------------> cl(A) cl(B) on(A,B) --> --> --> t(0) ----> puton(A,B,T) ----> puton(B,T,C) ----> puton(A,T,B) ----> t(infinity) This last step shows all variables bound and all conditions met. More Extensions to the language: (Conditional Effects etc.) - Extending Operator Language - So far, all preconditions were non-negated, simple atoms, conjoined. - We want to extend to express more complicated situtations. - Spliting number of operators - results in too many of them - don't know which to pick => must do backtracking - Generalizing - write fewer number of actions - do planning more efficiently (example) puton(x,y,z) effect: if z<>table then ~clear(z) paint(object,color) effect: if color(object,white) then color(object,color) -NOTE: otherwise we must write paint operator for each color! (example) Move briefcase to office from home. Everything in briefcase should also be at office. move(B,L1,L2) precond: at(B,L1) effect: at(B,L2) {at(x,L2)| (Ax) in(x,B)} [everything in briefcase also moved] - Disjunctive preconditions => split operators - Quantified effects - More clear for Forward State Space. More complex for Least commitment planner. (example) Painting t0 ---> paint(A,green) ---> t(inf) color(A,white) color(A,green) ______________ ^ |-------- Secondary precondition (make it a precondition) Causation precondition (make either T of F) t0 ---> whiten(A) ---> paint(A,green) ---> t(inf) | | ---------------- color(A,white) (example) Briefcase transport (want to leave book at home, but take briefcase to office) t0 ---> move(H,O) ---> t(inf) * move(H,O) deletes at(Book,H) | | | promotion, demotion won't work | --------------| | at(BC,O) | -------------------------- at(Book,H) Since a conditional conflict, make it into a non-conflict move-B(x,y) if in(Book,BC) <----- negate this then done. [Called Confrontation] then ~at(Book,x) at(Book,y) t0 ---> move-B(H,O) ---> t(inf) (~in(Book,BC)) Create a takeout operator takeout(Book,BC) ~in(B,BC) t0 ---> takeout(Book,BC) ---> move-B(H,O) ---> t(inf)