Dana Nau: Lecture slides for Automated Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/ 1 Part III Heuristics and Control Strategies Dana S. Nau University of Maryland 1:32 PM February 29, 2012 Lecture slides for Automated Planning: Theory and PracticeDana Nau: Lecture slides for Automated Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/ 2 Motivation 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 Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/ 3 Abstract 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 Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/ 4 Abstract 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 Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/ 5 Abstract 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 Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/ 6 Abstract Search Procedure ● Remove some unpromising members of B ● e.g., loop detection, constraint violationDana Nau: Lecture slides for Automated Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/ 7 Plan-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 Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/ 8 State-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 Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/ 9 Planning-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 mutex for number of levels = 0, 1, 2, …Dana Nau: Lecture slides for Automated Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/ 10 Search Heuristics ● Chapter 9: Heuristics in Planning ◆ Heuristics for choosing where to search next ◆ The heuristics in this chapter are domain-independent within classical planning Chapter 9"Chapter 9"Dana Nau: Lecture slides for Automated Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/ 11 Branching 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 search Chapter 10"Chapter 11"Dana Nau: Lecture slides for Automated Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/ 12 Branching 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”