PlanGeneration&Causal-LinkPlanning1

,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Plan Generation &Causal-Link Planning 1,Jos, Luis Ambite,1,Review,Frame problem:,How to specify what does not change,Qualification problem,Hard to specify all preconditions,Ramification problem,Hard to specify all effects,2,Review,Situation Calculus,Successor state axioms:,Broken(x, do(s,a),a = drop(x) fragile(x, s),ba=explode(b) nextTo(b, x, s) ,broken(x,s) a = repair(x),Preconditions axioms:,Poss(pickup(r,x), s) robot(r) z holding(z, x, s) ,nextTo(r, x, s),Strips representation,Means-ends analysis,Networks of Actions (Noah),3,Domain-Independent Planning,Inputs:,Domain Action Theory,Problem Instance,Description of (initial) state of the world,Specification of desired goal behavior,Output: sequence of actions that executed in initial state satisfy goal,4,“Classical Planning” Assumptions,Atomic Time,Instantaneous actions,Deterministic Effects,Omniscience,Sole agent of change,Goals of attainment,5,Example Problem Instance:“Sussman Anomaly”,Initial State: (on-table A) (on C A) (on-table B),(clear B) (clear C),Goal: (on A B) (on B C),A,B,C,A,B,C,Initial State:,Goal:,6,Example Problem Instance:“Sussman Anomaly”,Initial State: (and (on-table A) (on C A),(on-table B) (clear B) (clear C),Goal: (and (on A B) (on B C),A,B,C,A,B,C,Initial State:,Goal:,7,Action Representation:Propositional STRIPS,Move-C-from-A-to-Table:,preconditions: (on C A) (clear C),effects:,add (on-table C),delete (on C A),add (clear A),Solution to frame problem: explicit effects are the only changes to the state.,8,Action Representation:Propositional STRIPS,Move-C-from-A-to-Table:,preconditions: (and (on C A) (clear C),effects:,(and (on-table C),(not (on C A),(clear A),Solution to frame problem: explicit effects are the only changes to the state.,9,Plan Generation:Search space of world states,Planning as a (graph) search problem,Nodes: world states,Arcs: actions,Solution: path from the initial state to one state that satisfies the goal,Initial state is fully specified,There are many goal states,10,Search Space: Blocks World,11,Progression:Forward search (I,-,G),ProgWS,(state, goals, actions, path),If state satisfies goals, then return path,else a =,choose,(actions), s.t.,preconditions(a) satisfied in state,if no such a, then return failure,else return,ProgWS,(apply(a, state), goals, actions,concatenate(path, a),First call: ProgWS(IS, G, Actions, (),12,Progression Example: Sussman Anomaly,I: (on-table A) (on C A) (on-table B) (clear B) (clear C),G: (on A B) (on B C),P(I, G, BlocksWorldActions, (),P(S1, G, BWA, (move-C-from-A-to-table),P(S2, G, BWA, (move-C-from-A-to-table,move-B-from-table-to-C),P(S3, G, BWA, (move-C-from-A-to-table,move-B-from-table-to-C,move-A-from-table-to-B),G,S3 = Success!,Non-Deterministic,Choice!,13,Regression:Backward Search (I, Success!,Non-Deterministic,Choice!,15,Regression Example: Sussman Anomaly,I: (on-table A) (on C A) (on-table B) (clear B) (clear C),G: (on A B) (on B C),P(I, G, BlocksWorldActions, (),P(S1, G, BWA, (move-C-from-A-to-table),P(S2, G, BWA, (move-C-from-A-to-table,move-B-from-table-to-C),P(S3, G, BWA, (move-C-from-A-to-table,move-B-from-table-to-C,move-A-from-table-to-B),G,S3 = Success!,Non-Deterministic,Choice!,16,Progression vs. Regression,Both algorithms are:,Sound: the result plan is valid,Complete: if valid plan exists, they find one,Non-deterministic choice = search!,Brute force: DFS, BFS, Iterative Deepening, .,Heuristic: A*, IDA*, ,Complexity: O(b,n,) worst-case,b = branching factor, n = |“choose”|,Regression: often smaller b, focused by goals,Progression: full state to compute heuristics,17,Total-Order vs Partial-Order Plans,18,Plan Generation: Search space of plans,Partial-Order Planning (POP),Nodes are partial plans,Arcs/Transitions are plan refinements,Solution is a node (not a path).,Principle of “Least commitment”,e.g. do not commit to an order of actions until it is required,19,Partial Plan Representation,Plan = (A, O, L), where,A: set of actions in the plan,O:,temporal orderings,between actions (a b),L:,causal links,linking actions via a literal,Causal Link:,Action Ac (consumer) has precondition Q that is established in the plan by Ap (producer).,move-a-from-b-to-table move-c-from-d-to-b,Ap,Ac,Q,(clear b),20,Threats to causal links,Step A,t,threatens,link (A,p, Q, A,c,) if:,1. A,t,has (not Q) as an effect, and,2. A,t,could come between A,p,and A,c, i.e.,O, (,A,p, A,t, A,c,) is consistent,Whats an example of an action that threatens the link example from the last slide?,21,Initial Plan,For uniformity, represent initial state and goal with two special actions:,A,0,:,no preconditions,initial state as,effects,must be the,first,step in the plan.,A,:,no effects,goals as,preconditions,must be the,last,step in the plan.,22,POP algorithm,POP(A, O, L), agenda, actions),If agenda = () then return (A, O, L),Pick,(Q, a,need,) from agenda,a,add,=,choose,(actions) s.t. Q,effects(,a,add,),If no such action a,add,exists,fail,.,L := L,(a,add, Q, a,need,) ; O := O,(a,add, a,need,),agenda := agenda - (Q, a,need,),If a,add,is new, then A := A,a,add,and,P preconditions(,a,add,), add,(P,a,add,) to agenda,For every action a,t,that threatens any causal link (a,p, Q, a,c,) in L,choose,to add a,t, a,p,or a,c, a,t,to O.,If neither choice is consistent,fail,.,POP(A, O, L), agenda, actions),Termination,Action Selection,Update goals,Protect causal links,Demotion:,a,t,a,p,Promotion:,a,c, Promotion,28,Work on open precondition (clear A),(on A B),(on B C),A2: move A from Table to B,(clear A),(clear B),(on-table A),(on A B),-(on-table A),-(clear B),A3: move C from A to Table,(clear C),(on C A),-(on C A),(on-table C),(clear A),A0,(on C A),(on-table A),(on-table B),(clear C),(clear B),A1: move B from Table to C,(on B C),-(on-table B),-(clear C),(clear B),(clear C),(on-table B),Ainf,and protect links,29,Final plan,(on A B),(on B C),A2: move A from Table to B,(clear A),(clear B),(on-table A),(on A B),-(on-table A),-(clear B),A3: move C from A to Table,(clear C),(on C A),-(on C A),(on-table C),(clear A),A0,(on C A),(on-table A),(on-table B),(clear C),(clear B),A1: move B from Table to C,(on B C),-(on-table B),-(clear C),(clear B),(clear C),(on-table B),Ainf,30,Plartial-Order Planning vs State-Space Planning,Complexity: O(b,n,) worst-case,Non-deterministic choices (n):,ProgWS, RegWS: n = |actions|,POP: n = |preconditions| + |link protection|,Generally an action has several preconditions,Branching factor (b),POP has smaller b:,No backtrack due to goal ordering,Least commitment: no premature step ordering,Does POP make the least possible amount of commitment?,31,