A framework for analysing state-abstraction methods

DOI10.1016/J.ARTINT.2021.103608MaRDI QIDQ2060741zbMATHOpenAlexFDO

Authors Peter Jonsson, Christer Bäckström

Publication date 13 December 2021

Published in Artificial Intelligence (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

heuristic searchrefinementcombinatorial searchaction planningstate abstractionhierarchical abstraction

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Merge-and-shrink: a compositional theory of transformations of factored transition systems
• Merge-and-Shrink Abstraction
• Graph abstraction in real-time heuristic search
• The computational complexity of avoiding spurious states in state space abstraction
• scientific article; zbMATH DE number 139761

Cites work

• scientific article; zbMATH DE number 3181472 (Why is no real title available?)
• scientific article; zbMATH DE number 139761 (Why is no real title available?)
• scientific article; zbMATH DE number 2243372 (Why is no real title available?)
• scientific article; zbMATH DE number 2243407 (Why is no real title available?)
• scientific article; zbMATH DE number 2243410 (Why is no real title available?)
• A complete parameterized complexity analysis of bounded planning
• A general theory of additive state space abstractions
• A method for computing heuristics in problem solving
• A result on the computational complexity of heuristic estimates for the \(A^*\) algorithm
• A theory of abstraction
• Abstract interpretation
• Automatically generating abstractions for planning
• Calculating criticalities
• Counterexample-guided Cartesian abstraction refinement for classical planning
• Counterexample-guided abstraction refinement for symbolic model checking
• Downward refinement and the efficiency of hierarchical problem solving
• Explaining non-acceptability in abstract argumentation
• Friends or foes? On planning as satisfiability and abstract CNF encodings
• Generalized best-first search strategies and the optimality of A*
• Heuristic search. Theory and applications
• Inconsistent heuristics in theory and practice
• Linear-time disk-based implicit graph search
• Macro-operators: A weak method for learning
• Merge-and-Shrink Abstraction
• Path Problems in Structured Graphs
• Planning in a hierarchy of abstraction spaces
• Red-black planning: a new systematic approach to partial delete relaxation
• Succinct representations of graphs
• The complexity of optimal monotonic planning: the bad, the good, and the causal graph
• The complexity of searching implicit graphs
• The computational complexity of avoiding spurious states in state space abstraction
• The computational complexity of propositional STRIPS planning
• The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
• Towards a practical theory of reformulation for reasoning about physical systems
• Weighted \(A^*\) search - unifying view and application
• ``Distance? Who cares? Tailoring merge-and-shrink heuristics to detect unsolvability

Cited in

(7)

• The computational complexity of avoiding spurious states in state space abstraction
• Deriving State-Based Implementations of Interactive Components with History Abstractions
• State trace analysis: what it can and cannot do
• Merge-and-shrink: a compositional theory of transformations of factored transition systems
• The Spotlight Principle
• Algebraic Methodology and Software Technology
• Agent abstraction via forgetting in the situation calculus

This page was built for publication: A framework for analysing state-abstraction methods

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