The computational complexity of avoiding spurious states in state space abstraction

DOI10.1016/J.ARTINT.2010.06.002MaRDI QIDQ622104zbMATH OpenOpenAlexFDO

Authors Sandra Zilles, Robert C. Holte

Publication date 31 January 2011

Published in Artificial Intelligence (Search for Journal in Brave)

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

zbMATH Keywords

abstractionheuristic searchplanning

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• A framework for analysing state-abstraction methods
• A general theory of additive state space abstractions
• scientific article; zbMATH DE number 67476
• Merge-and-Shrink Abstraction
• scientific article; zbMATH DE number 139761

Cites work

• Automatically generating abstractions for planning
• Downward refinement and the efficiency of hierarchical problem solving
• scientific article; zbMATH DE number 47025 (Why is no real title available?)
• scientific article; zbMATH DE number 67476 (Why is no real title available?)
• scientific article; zbMATH DE number 1759719 (Why is no real title available?)
• scientific article; zbMATH DE number 1395310 (Why is no real title available?)
• scientific article; zbMATH DE number 3313863 (Why is no real title available?)
• Planning as heuristic search
• Planning in a hierarchy of abstraction spaces
• Some Recent Results in Heuristic Search Theory
• STRIPS: A new approach to the application of theorem proving to problem solving
• The complexity of satisfiability problems
• The expected length of a shortest path
• Using regression-match graphs to control search in planning

Cited in

(7)

• A framework for analysing state-abstraction methods
• An approximation algorithm for box abstraction of transition systems on real state spaces
• When does abstraction help?
• Merge-and-Shrink Abstraction
• Efficient symbolic search for cost-optimal planning
• scientific article; zbMATH DE number 67476 (Why is no real title available?)
• Merge-and-shrink: a compositional theory of transformations of factored transition systems

This page was built for publication: The computational complexity of avoiding spurious states in state space abstraction

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