Limitations of acyclic causal graphs for planning

DOI10.1016/J.ARTINT.2014.02.002MaRDI QIDQ490647zbMATH OpenOpenAlexFDO

Authors Anders Jonsson, Peter Jonsson, Tomas Lööw

Publication date 27 August 2015

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.artint.2014.02.002

zbMATH Keywords

computational complexityplanning

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Causal graphs and structurally restricted planning
• The complexity of planning problems with simple causal graphs
• The complexity of optimal monotonic planning: the bad, the good, and the causal graph
• Graph planning with expected finite horizon
• Planning over chain causal graphs for variables with domains of size 5 is NP-hard
• Causal graph justifications of logic programs

Cites work

• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 1946870 (Why is no real title available?)
• A refined view of causal graphs and component sizes: SP-closed graph classes and beyond
• Automatically generating abstractions for planning
• Downward refinement and the efficiency of hierarchical problem solving
• Planning over chain causal graphs for variables with domains of size 5 is NP-hard
• The complexity of planning problems with simple causal graphs
• The computational complexity of propositional STRIPS planning
• The role of macros in tractable planning
• Tractable plan existence does not imply tractable plan generation

Cited in

(5)

• The complexity of planning problems with simple causal graphs
• Causal graphs and structurally restricted planning
• Backdoors to planning
• A refined view of causal graphs and component sizes: SP-closed graph classes and beyond
• scientific article; zbMATH DE number 1946870 (Why is no real title available?)

This page was built for publication: Limitations of acyclic causal graphs for planning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q490647)