Part III Heuristics and Control StrategiesMotivation for Part 3 of the BookAbstract Search ProcedureSlide 4Slide 5Slide 6Plan-Space PlanningState-Space PlanningPlanning-Graph PlanningSearch HeuristicsBranching and Pruning TechniquesBranching Versus PruningDana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/1Part IIIHeuristics and Control StrategiesDana S. NauUniversity of Maryland06:43 AM January 14, 2019Lecture slides forAutomated Planning: Theory and PracticeDana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/2Motivation for Part 3 of the BookDomain-independent planners suffer from combinatorial complexityPlanning is in the worst case intractableNeed ways to control the searchDana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/3Abstract Search ProcedureHere is a general framework for describing classical and neoclassical plannersThe planning algorithms we’ve discussed all fit into the framework, if we vary the detailse.g., the steps don’t have to be in this orderDana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/4Abstract Search ProcedureCompute information that may affect how we do some of the other stepse.g., select a flaw to work on next, or compute a planning graphDana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/5Abstract Search ProcedureDivide current set of solutions into several sets to be explored in parallele.g., B' ← {π.a | a is applicable to γ(s0,π)}Dana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/6Abstract Search ProcedureRemove some unpromising members of Be.g., loop detection, constraint violationDana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/7Plan-Space PlanningRefinement: select which flaw to work on nextBranching: {the flaw’s resolvers}Pruning: loop detectionrecall this is weak for plan-space planningDana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/8State-Space PlanningRefinement: noneBranching: {applicable or relevant actions}Pruning: loop detectionOther branching & pruning techniques in Chapters 10 & 11Dana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/9Planning-Graph PlanningWrap iterative deepening around Abstract-searchRefinement: generate the planning graph, compute mutex infoBranching: {sets of actions in action-level i that achieve goals at state-level i}Pruning: prune sets of actions that are mutexfor number of levels = 0, 1, 2, …Dana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/10Search HeuristicsChapter 9: Heuristics in PlanningHeuristics for choosing where to search nextThe heuristics in this chapter are domain-independent within classical planningChapter 9Chapter 9Dana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/11Branching and Pruning TechniquesChapter 10: pruning via search-control rulesChapter 11: branching via hierarchical task decompositionThese chapters discuss domain-configurable state-space plannersDomain-independent planning engineDomain-specific information to control the searchChapter 10Chapter 11Dana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/12Branching Versus PruningTwo equivalent approaches:Generate all possible branches, then prune some of themJust don’t bother generating the ones that would be prunedExample: Domain-configurable implementations of the block-stacking algorithm from Chapter 4Separate branching and pruning (Chapter 10)»Branch: generate all applicable actions»Prune: prune actions that build up “bad” stacks or tear down “good” onesCombined branching and pruning (Chapter 11)»Only generate actions that don’t build up “bad” stacks and don’t tear down “good”