Structural Patterns of Tractable Sequentially-Optimal Planning

Keywords

Heuristics, Computer science, Constructive, Curse of dimensionality, Constraint (computer-aided design)

References

• Symbolic Pattern Databases in Heuristic Search PlanningStefan Edelkamp — 2002
• Solving planning domains with polytree causal graphs is NP-completeOmer Giménez — 2006
• A Reactive Planner for a Model-based ExecutiveBrian C. Williams, P. Pandurang Nayak — 1997
• The FF Planning System: Fast Plan Generation Through Heuristic SearchJ. Hoffmann, Bernhard Nebel — 2011
• Factored Planning: How, When, and When NotRonen I. Brafman, Carmel Domshlak — 2006
• The Role of Macros in Tractable Planning over Causal GraphsAnders Jönsson — 2007
• State-Variable Planning Under Structural Restrictions: Algorithms and ComplexityPeter Jönsson, Christer Bäckström — 1998
• Planning in polynomial time: the SAS‐PUBS classChrister Bäckström, Inger Klein — 1991
• Downward Refinement and the Efficiency of Hierarchical Problem SolvingFahiem Bacchus, Qiang Yang — 1994
• COMPLEXITY RESULTS FOR SAS+ PLANNINGChrister Bäckström, Bernhard Nebel — 1995
• Automatically Generating Abstractions for PlanningCraig A. Knoblock — 1994
• The Computational Complexity of Propositional STRIPS PlanningTom Bylander — 1994
• Efficient planning for a miniature assembly lineInger Klein, Peter Jönsson, Christer Bäckström — 1999
• The GRT Planning System: Backward Heuristic Construction in Forward State-Space PlanningIoannis Refanidis, Ioannis Vlahavas — 2001
• Strucutre and Complexity in Planning with Unary OperatorsRonen I. Brafman, Carmel Domshlak — 2002
• Maximizing over multiple pattern databases speeds up heuristic searchRobert C. Holte, Ariel Felner, Jack Newton — 2006
• Planning as heuristic searchBlai Bonet, Héctor Geffner — 2001
• Additive Pattern Database HeuristicsAriel Felner, Richard E. Korf, S. Hanan — 2004
• The Fast Downward Planning SystemM. Helmert — 2006
• Planning for Conjunctive GoalsDavid Chapman — 1987

Cited by

• Structural Patterns Heuristics via Fork DecompositionMichael Katz, Carmel Domshlak — 2008
• In Search of the Tractability Boundary of Planning ProblemsOmer Giménez, Anders Jönsson — 2008
• Tractable Cost-Optimal Planning over Restricted Polytree Causal GraphsMeysam Aghighi, Peter Jönsson, Simon Ståhlberg — 2015
• Optimal Additive Composition of Abstraction-based Admissible HeuristicsMichael Katz, Carmel Domshlak — 2008
• Implicit abstraction heuristics for cost-optimal planningMichael Katz — 2011
• Causal graphs and structurally restricted planningHubie Chen, Omer Giménez — 2008
• Implicit Abstraction HeuristicsMichael Katz, Carmel Domshlak — 2010
• A Refined View of Causal Graphs and Component Sizes: SP-Closed Graph Classes and BeyondC. Bäckström, P. Jonsson — 2013
• State-Dependent Cost Partitionings for Cartesian Abstractions in Classical PlanningThomas Keller, Florian Pommerening, Jendrik Seipp — 2016
• Narrowing the Gap Between Saturated and Optimal Cost Partitioning for Classical PlanningJendrik Seipp, Thomas Keller, Malte Helmert — 2017
• Computational Complexity of some Optimization Problems in PlanningMeysam Aghighi — 2017
• New perspectives on cost partitioning for optimal classical planningFlorian Pommerening — 2017
• Merge-and-shrink abstractions for classical planning : theory, strategies, and implementationSilvan Sievers — 2017
• Counterexample-Guided Cartesian Abstraction RefinementJendrik Seipp, Malte Helmert — 2013
• On planning with state-dependent action costsFlorian Geißer — 2018
• Saturated Cost Partitioning for Optimal Classical PlanningJendrik Seipp, Thomas Keller, Malte Helmert — 2020
• Structural Patterns Heuristics: Basic Idea and Concrete InstanceMichael Katz — 2007
• Generating Data In Planning: SAS + Planning Tasks of a Given Causal StructureMichael Katz, Shirin Sohrabi — 2020
• Generating SAS + Planning Tasks of Specified Causal StructureMichael Katz, Junkyu Lee, Shirin Sohrabi — 2023

Related papers

• COMPLEXITY RESULTS FOR SAS+ PLANNINGChrister Bäckström, Bernhard Nebel — 1995
• A Planning Heuristic Based on Causal Graph AnalysisMalte Helmert — 2004
• The Computational Complexity of Propositional STRIPS PlanningTom Bylander — 1994
• The Role of Macros in Tractable Planning over Causal GraphsAnders Jönsson — 2007
• Domain-Independent Construction of Pattern Database Heuristics for Cost-Optimal PlanningPatrik Haslum, Adi Botea, Malte Helmert — 2007
• New Islands of Tractability of Cost-Optimal PlanningMichael Katz, Carmel Domshlak — 2008
• The complexity of planning problems with simple causal graphsOmer Giménez, Anders Jonsson — 2008
• Additive Pattern Database HeuristicsAriel Felner, Richard E. Korf, S. Hanan — 2004
• Strucutre and Complexity in Planning with Unary OperatorsRonen I. Brafman, Carmel Domshlak — 2002