PowerPoint PresentationPlanning as Nondeterministic SearchMaking it DeterministicDigression: the A* algorithm (on trees)The A* AlgorithmHill ClimbingFastForward (FF)Selection HeuristicFastForwardAIPS-2000 Planning Competition2002 International Planning Competition2004 International Planning CompetitionPlan-Space PlanningFlaw SelectionSerializing and AND/OR TreeOne SerializationAnother SerializationWhy Does This Matter?A Pretty Good HeuristicHow Much Difference Can the Refinement Strategy Make?Case Study, ContinuedResolver SelectionSlide 23Dana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/1Chapter 9 Heuristics in PlanningLecture slides forAutomated Planning: Theory and PracticeDana S. NauUniversity of Maryland02:55 PM January 14, 2019Dana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/2Planning as Nondeterministic SearchDana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/3Making it DeterministicDana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/4Digression: the A* algorithm (on trees)Suppose we’re searching a tree in which each edge (s,s') has a cost c(s,s')If p is a path, let c(p) = sum of the edge costsFor classical planning, this is the length of pFor every state s, letg(s) = cost of the path from s0 to sh*(s) = least cost of all paths from s to goal nodesf*(s) = g(s) + h*(s) = least cost of all pathsfrom s0 to goal nodes that go through sSuppose h(s) is an estimate of h*(s)Let f(s) = g(s) + h(s)»f(s) is an estimate of f*(s)h is admissible if for every state s, 0 ≤ h(s) ≤ h*(s)If h is admissible then f is a lower bound on f*g(s)h*(s)Dana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/5The A* AlgorithmA* on trees: loopchoose the leaf node s such that f(s) is smallestif s is a solution then return it and exitexpand it (generate its children)On graphs, A* is more complicatedadditional machinery to deal withmultiple paths to the same nodeIf a solution exists (and certain otherconditions are satisfied), then:If h(s) is admissible, then A* is guaranteed to find an optimal solutionThe more “informed” the heuristic is (i.e., the closer it is to h*),the smaller the number of nodes A* expandsIf h(s) is within c of being admissible, then A* isguaranteed to find a solution that’s within c of optimalg(s)h*(s)Dana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/6Hill ClimbingUse h as a node-selection heuristicSelect the node v in C for which h(v) is smallest Why not use f ?Do we care whether h is admissible?uCDana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/7FastForward (FF)Depth-first searchSelection heuristic: relaxed GraphplanLet v be a node in CLet Pv be the planning problem of getting from v to a goaluse Graphplan to find a solution for a relaxation of PvThe length of this solution is a lower bound on the length of a solution to PvuCDana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/8Selection HeuristicGiven a planning problem Pv, create a relaxed planning problem P'v and use GraphPlan to solve itConvert to set-theoretic representation»No negative literals; goal is now a set of atomsRemove the delete lists from the actionsConstruct a planning graph until a layer is found that contains all of the goal atomsThe graph will contain no mutexes because the delete lists were removedExtract a plan π' from the planning graph»No mutexes  no backtracking  polynomial time|π'| is a lower bound on the length of the best solution to PvDana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/9FastForwardFF evaluates all the nodes in the set C of u’s successorsIf none of them has a better heuristic value than u, FF does a breadth-first search for a state with a strictly better evaluation The path to the new state is added to the current plan, and the search continues from this state Works well because plateaus and local minima tend to be small in many benchmark planning problems Can’t guarantee how fast FF will find a solution,or how good a solution it will findHowever, it works pretty well on many problemsDana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/10AIPS-2000 Planning CompetitionFastForward did quite wellIn the this competition, all of the planning problems were classical problemsTwo tracks:“Fully automated” and “hand-tailored” plannersFastForward participated in the fully automated track»It got one of the two “outstanding performance” awardsLarge variance in how close its plans were to optimal»However, it found them very fast compared with the other fully-automated plannersDana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/112002 International Planning CompetitionAmong the automated planners, FastForward was roughly in the middle LPG (graphplan + local search) did much better, and got a “distinguished performance of the first order” awardIt’s interesting to see how FastForward did in problems that went beyond classical planning»Numbers, optimizationExample: Satellite domain, numeric versionA domain inspired by the Hubble