On the complexity of case-based planning

DOI10.1080/09528130500283717MaRDI QIDQ5704532zbMATH OpenOpenAlexFDO

Authors Paolo Liberatore

Publication date 15 November 2005

Published in Journal of Experimental & Theoretical Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0407034

zbMATH Keywords

automated planningcase-based planningcomputational complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Pattern recognition, speech recognition (68T10)

Abstract: We analyze the computational complexity of problems related to case-based planning: planning when a plan for a similar instance is known, and planning from a library of plans. We prove that planning from a single case has the same complexity than generative planning (i.e., planning "from scratch"); using an extended definition of cases, complexity is reduced if the domain stored in the case is similar to the one to search plans for. Planning from a library of cases is shown to have the same complexity. In both cases, the complexity of planning remains, in the worst case, PSPACE-complete.

Recommendations

• Kernel functions for case-based planning
• The complexity of planning problems with simple causal graphs
• A survey on case-based planning
• The computational complexity of propositional STRIPS planning
• Case-based planning for problems with real-valued fluents: kernel functions for effective plan retrieval

Cites work

• scientific article; zbMATH DE number 1094634 (Why is no real title available?)
• Monotonic reductions, representative equivalence, and compilation of intractable problems
• On the computational complexity of temporal projection, planning, and plan validation
• Preprocessing of intractable problems
• STRIPS: A new approach to the application of theorem proving to problem solving
• The computational complexity of propositional STRIPS planning

Cited in

(16)

• Computational complexity of planning and approximate planning in the presence of incompleteness
• Approximate planning
• Model-lite planning: case-based vs. model-based approaches
• Planning from second principles
• scientific article; zbMATH DE number 1696842 (Why is no real title available?)
• scientific article; zbMATH DE number 2089753 (Why is no real title available?)
• Case-based planning for problems with real-valued fluents: kernel functions for effective plan retrieval
• scientific article; zbMATH DE number 2079757 (Why is no real title available?)
• scientific article; zbMATH DE number 194494 (Why is no real title available?)
• scientific article; zbMATH DE number 1929233 (Why is no real title available?)
• Case-based planning of treatment of infants with respiratory failure
• A survey on case-based planning
• On the complexity of the storyplan problem
• Kernel functions for case-based planning
• Maintenance of plan libraries for case-based planning: offline and online policies
• Complexity results for standard benchmark domains in planning

This page was built for publication: On the complexity of case-based planning

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