Introduction to AI - Week 9 Planning * The world is described in (a fragment of) logic * Search in the universe of states Operators are represented by three lists: + [Preconditions:] specify the applicability of the operator + [delete list:] specifies what does not hold any longer + [add list:] specifies what newly holds _________________________________________________________________________________________________________ The Planning System Strips Fikes and Nilsson 1971: STanford Research Institute Problem Solver * initial state Init (given by predicate logical formulae) * goal state goal (given by predicate logical formulae) * set of rules (given by name, preconditions, delete list, & add list ) Remark: For first-order logic it is not trivial to see whether goal state is reached, however trivial for the fragment normally taken _________________________________________________________________________________________________________ Example: Blocks World [planning6.jpg] Ontable(A) Ontable(B) On(D,A) On(C,D) Clear(C) Clear(B) Handempty [planning7.jpg] Ontable(B) Ontable(C) On(D,B) On(A,D) Clear(A) Clear(C) Handempty InitGoal The operators are as on the next slide. _________________________________________________________________________________________________________ Operators of the Blocks World -------- ------------- ------------- PICKUP(x) preconditions Clear(x) Ontable(x) Handempty endtr delete list Clear(x) Ontable(x) Handempty add list Holds(x) PUTDOWN(x) preconditions Holds(x) delete list Holds(x) add list Clear(x) Ontable(x) Handempty -------- ------------- ------------- STACK(x,y) preconditions Holds(x) Clear(y) delete list Holds(x) Clear(y) add list Clear(x) On(x,y) Handempty UNSTACK(x,y) preconditions Clear(x) On(x,y) Handempty delete list Clear(x) On(x,y) Handempty add list Holds(x) Clear(y) -------- ------------- ------------- _________________________________________________________________________________________________________ Example Plan Execution Ontable(A) Ontable(B) On(D,A) On(C,D) Clear(C) Clear(B) Handempty UNSTACK(C,D)---> Ontable(A) Ontable(B) On(D,A) [DEL: On(C,D) :DEL] [DEL: Clear(C) :DEL] Clear(B) [DEL: Handempty :DEL] Holds(C) Clear(D) PUTDOWN(C)---> Ontable(A) Ontable(B) On(D,A) Clear(B) [DEL: Holds(C) :DEL] Clear(D) Clear(C) Ontable(C) Handempty UNSTACK(D,A)---> Ontable(A) Ontable(B) [DEL: On(D,A) :DEL] Clear(B) [DEL: Clear(D) :DEL] Clear(C) Ontable(C) [DEL: Handempty :DEL] Holds(D) Clear(A) STACK(D,B)---> Ontable(A) Ontable(B) [DEL: Clear(B) :DEL] Clear(C) Ontable(C) [DEL: Holds(D) :DEL] Clear(A) Clear(D) On(D,B) Handempty PICKUP(A)---> [DEL: Ontable(A) :DEL] Ontable(B) Clear(C) Ontable(C) [DEL: Clear(A) :DEL] Clear(D) On(D,B) [DEL: Handempty :DEL] Holds(A) STACK(A,D)---> Ontable(B) Clear(C) Ontable(C) [DEL: Clear(D) :DEL] On(D,B) [DEL: Holds(A) :DEL] Clear(A) On(A,D) Handempty Plan: (UNSTACK(C,D),PUTDOWN(C),UNSTACK(D,A),STACK(D,B),PICKUP(A),STACK(A,D)) _________________________________________________________________________________________________________ How to Search in Strips ? * Simple planning algorithm: breadth first search, i.e. apply all applicable operators with all possible instantiations one after the other and generate all possible states. But: intractable * Heuristic procedure of Strips: means ends analysis (as in GPS): Search in the search space from the goal, apply operators backward * Advantages: Goal often relatively easy compared to initial state * Examples: In order to come up with Holds(A) two possibilities: PICKUP(A) or UNSTACK(A,x) _________________________________________________________________________________________________________ Algorithm MEA (means-end-analysis) Input: a set Goal, an initial state Init, a set of rules RULES Output: a plan P in form of a list of operators with instantiations Auxiliary Variable: Actual for actual state begin 0. P:=NIL;Actual:=Init 1. while goals in Goal open in Actual do 1.1. select goal Goal[1] that is open in Actual ;;; arbitrary choice -> backtrack point 1.2. select instance I of operator with Goal[1], in add list ;;; arbitrary choice -> backtrack point 1.3 P:= append(P,MEA(preconditions(I),Actual),list(I)) 1.4 Actual := P(Init) end_do 2. return(P) end _________________________________________________________________________________________________________ Example Ontable(A) Ontable(B) On(D,A) On(C,D) Clear(C) Clear(B) Handempty Actual = Init Ontable(B) Ontable(C) On(D,B) On(A,D) Clear(A) Clear(C) Handempty Goal Open are: Ontable(C), On(D,B), On(A,D), and Clear(A) Goal_1 := Ontable(C) How to achieve this goal? Only by PUTDOWN(C), hence plan: P=(MEA(preconditions(PUTDOWN(C))),PUTDOWN(C)) Hence we need a plan for the preconditions of PUTDOWN(C), i.e. Holds(C) _________________________________________________________________________________________________________ Example (Cont'd) How to achieve Holds(C)? Two possibilities by PICKUP(C) or UNSTACK(C,x) First: bad choice, since precondition is Ontable(C) (was initial goal) Second: with x|-> D, hence plan: P=(UNSTACK(C,D),PUTDOWN(C)) Now apply P to Init: Actual:= P(Init), i.e., Result after one loop ( Actual): [planning5.jpg] Ontable(A) Ontable(B) Ontable(C) On(D,A) Clear(B) Clear(C) Clear(D) Handempty Still open: On(D,B), On(A,D), and Clear(A) _________________________________________________________________________________________________________ Example (Cont'd) For getting On(D,B) only possible operator STACK(D,B) In order to get precondition UNSTACK(D,A) Hence plan after second loop: P=(UNSTACK(C,D),PUTDOWN(C),UNSTACK(D,A),STACK(D,B)) Result after two loops ( Actual): [planning4.jpg] Ontable(A) Ontable(B) On(D,B) Clear(A) Clear(C) Clear(D) Handempty Still open: On(A,D) _________________________________________________________________________________________________________ Example (Cont'd) Operator STACK(A,D) For preconditions of this use PICKUP(A) Hence plan after third loop: P = ( UNSTACK(C,D),PUTDOWN(C),UNSTACK(D,A), STACK(D,B),PICKUP(A),STACK(A,D)) No goal open ( Goal = Actual): [planning2.jpg] Ontable(B) Ontable(C) On(D,B) On(A,D) Clear(A) Clear(C) Handempty _________________________________________________________________________________________________________ Limitations of Strips Some general limitations of the representation, in particular: * Expressive power of description language for the operators: + Operator changes exactly, what is specified in its add list and delete list. * Problems with the strategy: Sussman anomaly [planning1.jpg] _________________________________________________________________________________________________________ Sussman Anomaly (Cont'd) Select first goal On(A,B) else selection optimal The following plan fulfils this goal Ontable(A) Ontable(B) On(C,A) Clear(B) Clear(C) Handempty UNSTACK(C,A)---> Ontable(A) Ontable(B) Clear(B) [DEL: On(C,A) :DEL] [DEL: Clear(C) :DEL] [DEL: Handempty :DEL] Holds(C) Clear(A) PUTDOWN(C)---> Ontable(A) Ontable(B) Clear(A) Clear(B) [DEL: Holds(C) :DEL] Ontable(C) Clear(C) Handempty PICKUP(A)---> Ontable(B) Ontable(C) Clear(B) Clear(C) [DEL: Ontable(A) :DEL] [DEL: Clear(A) :DEL] [DEL: Handempty :DEL] Holds(A) STACK(A,B)---> Ontable(B) Ontable(C) Clear(C) [DEL: Clear(B) :DEL] [DEL: Holds(A) :DEL] On(A,B) Clear(A) Handempty _________________________________________________________________________________________________________ Sussman Anomaly (Cont'd) Now select the second goal On(B,C). Has plan: Ontable(B) Ontable(C) Clear(C) On(A,B) Clear(A) Handempty UNSTACK(A,B)---> Ontable(B) Ontable(C) Clear(C) [DEL: Clear(A) :DEL] [DEL: On(A,B) :DEL] [DEL: Handempty :DEL] Holds(A) Clear(B) PUTDOWN(A)---> Ontable(B) Ontable(C) Clear(B) Clear(C) [DEL: Holds(A) :DEL] Ontable(A) Clear(A) Handempty PICKUP(B)---> Ontable(A) Ontable(C) Clear(A) Clear(C) [DEL: Ontable(B) :DEL] [DEL: Clear(B) :DEL] [DEL: Handempty :DEL] Holds(B) STACK(B,C)---> Ontable(A) Ontable(C) Clear(A) [DEL: Clear(C) :DEL] [DEL: Holds(B) :DEL] On(B,C) Clear(B) Handempty PICKUP(A)---> Ontable(C) Clear(B) On(B,C) [DEL: Ontable(A) :DEL] [DEL: Clear(A) :DEL] [DEL: Handempty :DEL] Holds(A) STACK(A,B)---> Ontable(C) On(B,C) [DEL: Holds(A) :DEL] [DEL: Clear(B) :DEL] On(A,B) Clear(A) Handempty First part undoes the plan for the goal On(A,B) _________________________________________________________________________________________________________ Sussman Anomaly (Cont'd) Second trial: select the goal On(B,C) first. Now first, B is set on top of C, this must be undone again. Hence, the decomposition into partial goals, necessarily results in superfluous steps, i.e. bad plans. (disadvantage in particular, when execution of plans is expensive) That plans are found at all, is due to the fact that in the blocks world for each operator there is an inverse operator _________________________________________________________________________________________________________ Heuristics in the Blocksworld * Heuristic for selecting a goal: Give order to goals such that: 1. Prefer goals involving Ontable over all others 2. When all Ontable predicates fulfilled, build towers: Build up towers from the bottom up, i.e., when block A should be above block B, then On(A,x) has lower priority than On(B,x) 3. Handempty has always lowest priority * Heuristic for selecting an operator: 1. Never try an operator like UNSTACK(A,A) 2. Whenever goal Holds(x) & Ontable(x) given, choose PICKUP(x) 3. Whenever goal Holds(x) and On(x,y) is given, choose UNSTACK(x,y) 4. Whenever goal Ontable(x), no choice 5. Whenever goal On(x,y), no choice 6. Whenever there is a further choice, take the first of the possible operator instances _________________________________________________________________________________________________________ Assumptions of Planning in Strips * Linear planning, i.e., plan as sequence of operators * Separation of planning in planning and execution phase * Search in a particular model * Assumption on complete knowledge of the initial state and the operators * Search Strategy select one subgoal after the other. Narrow focus on a single subgoal at a time. * Extended to deal with different subgoals simultaneously, non-linear planning. _________________________________________________________________________________________________________ Graphplan Features: * Fast graph-based partial-order planner * Finds shortest possible plan (if exists) * Does not search in the state space, but makes use of compact structure, called Planning Graph * Makes use of strong sufficient constraints _________________________________________________________________________________________________________ Planning Graphs A planning graph is similar to a valid plan, but without the requirement that the actions at a given time step not interfere (i.e., corresponds roughly to conflicts not resolved). * Directed, levelled graph: that is, the nodes can be partitioned into disjoint sets L[1],L[2],... ,L[n] such that the edges only connect nodes in adjacent levels. * Two kinds of nodes: alternate between proposition nodes (labelled by, e.g., On(A,B)) and action nodes (labelled by, e.g., UNSTACK(A,B)): 1st level: propositions true at time 1 (initial state) 2nd level: possible actions at time 1 3rd level: propositions possibly true at time 2 4th level: possible actions at time 2 5th level: propositions possibly true at time 3 (and so forth) _________________________________________________________________________________________________________ Planning Graphs (Cont'd) Three kinds of edges: * precondition-edges connect actions in action-level i to their preconditions in proposition level i. * add-edges connect action nodes in action-level i to their add-effects in proposition level i+1. * delete-edges connect action nodes in action-level i to their delete-effects in proposition level i+1. _________________________________________________________________________________________________________ Example - Rocket Domain One rocket R, two pieces of cargo A and B, start location L, destination P. Delete edges as dashed lines. Explicit no-op actions (with dot). Not all nodes at 2nd and 3rd action levels displayed. [graphplan.jpg] _________________________________________________________________________________________________________ Valid Plans A plan is called valid: * Actions at time 1, at time 2, at time 3 etc * Several actions may occur at the same time so long as they do not interfere with each other, i.e., if one does not delete a precondition or an add-effect of the other. (In a linear plan these independent parallel actions could be arranged in any order with exactly the same outcome. * A valid plan may perform an action at time t=1 if all its preconditions are true in the initial state. * A valid plan may perform an action at time t>1 if the plan makes all its preconditions true at time t. * Because of no-op actions we may define a proposition to be true at time t>1 iff it is an add-effect of some action taken at time t-1. * A valid plan must make all goals true at the final time step. _________________________________________________________________________________________________________ Mutual Exclusion * Two actions at a given action level are mutual exclusive if no valid plan could possibly contain both. * Two propositions at a given proposition level are mutual exclusive if no valid plan could possibly make both true. Identify mutual exclusion relationships to reduce the search for a subgraph of a Planning Graph that may correspond to a valid plan. * Graphplan notices and records mutual exclusion relationships by propagating them through the Planning Graph using a few simple rules. * The rules do not guarantee to find all mutual exclusion relationships (just typically a large number of them). _________________________________________________________________________________________________________ Example Rocket domain: * Initial state: At(Rocket1,London), Fuel(Rocket1) * The actions MOVE(Rocket1,London,Paris) and LOAD(Alex,Rocket1,London) are exclusive at time 1 because the first deletes the proposition At(Rocket1,London) which is a precondition of the second * The propositions At(Rocket1,London) and At(Rocket1,Paris) are exclusive at time 2 because all ways of generating the first (only no-op does) are exclusive of all ways of generating the second (only MOVE does). _________________________________________________________________________________________________________ Exclusion Relations * The Competing needs relation and the exclusivity between propositions are not just logical properties of the operators, they also depend on the interplay between operators and the initial state. * Example: Initially one object is not at two different places. The operators guarantee that this relation remains invariant during the plan construction. [If, however, it were not true initially, it wouldn't necessarily hold later on.] _________________________________________________________________________________________________________ Description of the Algorithm Planning_Graph := Initial_state, i := 1, No_Plan_found := TRUE, Plan_exists := TRUE WHILE No_Plan_found and Plan_exists DO 1. i := i+1 2. Take the Planning_Graph from stage i-1, extend it one time step, that is, add the next action level and the following proposition level. 3. Search for a valid plan of length i in Planning_Graph. If plan found No_Plan_found := FALSE, store plan in Plan. If detected that no plan can exist Plan_exists := FALSE END WHILE IF No_Plan_found=FALSE RETURN Plan ENDIF IF Plan_exists=FALSE RETURN "No Plan Exists" ENDIF _________________________________________________________________________________________________________ Properties * Graphplan's algorithm is sound and complete: only legal plans are generated. If there is a legal plan then Graphplan finds one. * In each loop i of the algorithm the algorithm either discovers a plan or proves that no plan having i or fewer steps exists. Extending planning graphs works as follows: * For each operator and each way of instantiating its preconditions to propositions in the previous level, insert an action node if no two of its preconditions are labelled as mutually exclusive. * Insert all the no-op actions & insert the precondition edges. * Check the action nodes for exclusivity and create an "actions-that-I-am-exclusive-of" list for each action. * Generate proposition level by inserting add-effects. _________________________________________________________________________________________________________ Searching for a Plan Given a Planning Graph, search for a valid plan using a backward-chaining strategy. * Level-by-level approach (to make best use of the mutual exclusion constraints). * Given a set of goals at time t, it attempts to find a set of actions (no-ops included) at time t-1 having these goals as add effects. * The preconditions of these actions form a set of subgoals at time t-1 (if these goals can be achieved in t-1, then the original goals can be achieved in t steps). * If the goal set at time t-1 turns out not to be solvable, try to find a different set of actions (backtracking), continuing until it either succeeds or proves that the original set of goals is not solvable at time t. _________________________________________________________________________________________________________ Memoisation * When a set of (sub)goals at some time t is determined to be not solvable, then before backtracking Graphplan memoises this fact (goal set and the time t) in a hash table. * Before searching for plans of a set of subproblems look up hash table whether it is proved to be unsolvable. Two aspects: * Speed up * Termination check _________________________________________________________________________________________________________ Minimal Action sets - Goal Orderings * Let G be a set of goals at time t. A non-exclusive set of actions A at time t-1 is a minimal set of actions achieving G if: 1. every goal in G is an add-effect of some action in A, and 2. no action can be removed from A so that the add effects of the actions remaining still contain G. * It suffices to look at minimal action sets. * Graphplan's strategy is breadth-first like, hence fairly insensitive to goal orderings, in particular when considering only minimal action sets. _________________________________________________________________________________________________________ Termination on Unsolvable Problems * If a proposition appears in some proposition level then (because of no-ops) it also appears in all future proposition levels. * Only a finite set of propositions can be created by Strips-style operators. Hence there is a minimal n such that propositions P[n] are equal to P[n+i] for all i>= 0. The graph is levelled off. * Let St[i] the collection of all sets memoised as unsolvable at level i at stage t: 1. Any plan considered must make one of the goal sets in St[i] true at time i, and 2. none of the goal sets in St[i] is achievable in i steps. * If a graph has levelled off at some level n and a stage t has passed in which abs(St-1[n])=abs(St[n]) then "No Plan Exists." * Graphplan outputs "No Plan Exists" if and only if the problem is unsolvable. _________________________________________________________________________________________________________ Summary of Graphplan * No search in the state space * If a plan exists, finds shortest plan. * If no plan exists, stops with "No Plan Exists" * Experimental Results: In tests significantly more efficient than traditional planners. Literature [books-shelf1.jpg] * Avrim L. Blum and Merrick L. Furst. Fast Planning Through Planning Graph Analysis. Artificial Intelligence, 90:281-300, 1997. _________________________________________________________________________________________________________ _________________________________________________________________________________________________________ © Manfred Kerber, 2004, Introduction to AI 24.4.2005 The URL of this page is http://www.cs.bham.ac.uk/~mmk/Teaching/AI/Teaching/AI/l9.html. URL of module [1]http://www.cs.bham.ac.uk/~mmk/Teaching/AI/ References 1. http://www.cs.bham.ac.uk/~mmk/Teaching/AI/