Unit 15. Advanced Planning Nov 22, 2011 Video 15.1. Introduction four things that we left out before time -- actions that persist over a length of time resources active perception hierarchical -- steps within steps Video 15.2. Scheduling scheduling tasks from Start to Finish, each with a duration arrows indicate precidence, previous needs to finish before the next times in the boxes are how long the task takes Video 15.3. Schedule Question see image: 15class_ScheduleESLS.jpg ES -- earliest possible start time LS -- Latest possible start time for which it's possible to complete the task network in the shortest total amount of time can use a set of recursive formulas solved by dynamic programming ES(s) = 0 Earliest StartTime of Start is defined to be 0 ES(taskB) = max_A->B(ES(A)) + Duration(A) Earliest StartTime of D is the max Start time of A + Duration of A The StartTime of the maximum of all (A) predecessors to (B) ie The latest start of A's with arrows leading into B plus the Duration of A so in the image the ES of the top middle "30" box is the 0 + the duration of the previous "30" == 30 LS(f) = ES(F) Latest StartTime of the Finish state is the same as the Earliest StartTime of the Finish (HUH -- takes into account that the Earliest Start of the Finish is the Maximum of all the paths leading in, so back-tracking Latest Starts uses that value, see Quiz) LS(A) = min_B<-A(LS(B) - Duration(A) The Latest StartTime of any state is the minimum Latest StartTime of all the B that come after A minus the Duration of A These formulas together form a unique schedule which is the fastest possible. Quiz: fill in the ES in upper right and the LS in upper left see image: 15class_ScheduleESLS_QuizA.jpg things on the line with no slack are on the Critical Path see image: 15class_ScheduleESLS_QuizB.jpg sometimes all this crap is in Operations Research instead of AI... Video 15.4. Resources Question see image: 15class_ClassicalPlan_Resources.jpg how about getting resources for the schedule, like nuts and bolts. Could be handled by Classical Planning, see image: goal is to get it inspected (successfully?) Inspect(nnnnn,bbbbb) Have Action(Fasten(n,b) whose effect is Fastened, with Nut and Bolt no longer available and Initial state nnnn bbbbb -- 4 nuts and 5 bolts with this can goal be achieved? N (need another nut to pass the mustard) given a depth first tree search, how many paths does the planner need to consider? 4! * 5! Because you find a solution on the first pass down N1,B1 but backtrack though all the other possibilities before completing... so end up trying all combinations of parts... because each part is a distinct entity rather than a class Video 15.5. Extending Planning see image: 15class_ClassicalPlan_Resources_Add.jpg add Resources to plan new cluses CONSUME -- use a nut and bolt USE -- use an inspector keeping track of resources this way gets rid of the combinational explosion Video 15.6. Hierarchical Planning close the Abstraction Gap -- ex: lifetime in seconds * muscles * number_muscle_ops/sec 10^9 * 10^3 * 10^1 = 10^13 operations to plan but we can handle maybe 10^4 when planning so we'd rather deal with more Abstract Plans at a higher level use a Hierarchical Task Network (HTN) or Refinement Planning rather than a Plan being a sequence of individual steps we can talk about higher order steps where these steps coorespond to multiple lower level steps Video 15.7. Refinement Planning see image: 15class_PlanRefinement.jpg in addition to regular actions there are Abstract Actions for Abstract Actions there can be Refinements that specify specific plans ex: Refinement(Navigate([a,b], [x,y]) Precond: a=x AND b=y // already there... Steps: [] ) // don't do nuthin Refinement(Navigate([a,b], [x,y]) Precond: Connected([a,b] [a-1,b]) // a is to right of b Steps: [Left, Navigate...) ) // turn left and go The idea is I can figure out a complex plan that involves navigating without having to have a detailed plan for each step. How to know if it's successful: A HTN achieves the goal if, for every part, (every abstract action) at least one of the refinements achieves the goal Only need one because the planners get to choose which... it's an AND/OR search where we can make the best possible choices and if any work then the goal can be achieved. Video 15.8. Reachable States in addition to an AND/OR search we can sometimes solve an HTN without going to the detailed plan level see image: 15class_ReachableStates.jpg start in red goal in grey box arrows are one abstract action that can reach multiple goals, in dotted oval depending on which refinement we use (each arrow is a refinement) this is like belief states due to stochastic actions, get multiple results not because of stochasticity, but need to decide on refinement to use add another step from first set of possible states to a new set (second dotted-line box) check for intersection with goal states if there is an intersection then search backwards through specific refinements to find the set to use -- if we searched forward there would be a large tree to examine but backwards is a single path Video 15.9. Reachable States Question sometimes it's difficult to specify exactly which states are reached because the refinements are complicated, so use an approximate set of reachable states for each action you have a lower and upper bound on reachable states some things are common to all refinements and some are specific ex: going to airport takes time, but costs money in some cases (box is lower -- things we know we'll get to in each case dotted line is upper -- things we might get to but not sure if all combinations of them will "check out" depending on refinements) Quiz: for each of the three actions shown (on two "boards") (...and apparently JUST that action, no subsequent...) is it guaranteed that we reach the goal with the right refinement? is it never possible? or is it uncertain because the description of bounds doesn't tell enough? see image: 15class_ReachableStates_Quiz.jpg for bottom left there is no overlap with goal so nothing we do there works for top left, there is intersection in the lower bound so guaranteed for right, the intersection is in the upper bound so have to look more carefully at the refinements to find right combo... Video 15.10. Conformant Plan Question see image: 15class_PerceptPlan.jpg extend classical planning with active perception to deal with Partial Observability ex: a table and chair with two cans of paint and we can see the table (but not the chair) have a buncha actions for painting and stuff add an active perception action: LookAt(x) if x is in view add Percept() perception schemas Color(x,c) which sets a color percept for x adds a new field 'c' as the return value "color" seems to be used in Paint(x,can) to link Precond Color(can,c) with Effect Color(x,c)... Quiz: is there a conformant plan (without sensing) that can achieve the goal? yes we can paint both things with the same paint... then we know they are the same color Video 15.11. Sensory Plan Question see image: 15class_PerceptPlan2.jpg if the table and chair were already the same color you waste your time Quiz: is there a better way using perceptions, if we allow plans to have conditionals? yahshureyabetcha or we wouldn't be doing this.... a variety of possibilities... LookAt(Table), LookAt(Chair) if Colors are then same, then NoOp else remove can lids and look at them if table is same color as a can, then paint chair with that can else if char is same color as a can, then paint table with that can else paint them both with can1 note that Color(can,c) is for any possible can...