On the complexity of blocks-world planning

DOI10.1016/0004-3702(92)90028-VMaRDI QIDQ1199914zbMATH OpenOpenAlexWikidataFDO

Authors S. Singh

Publication date 17 January 1993

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0004-3702(92)90028-v

zbMATH Keywords

\(NP\)-hardnessblocks-world planningdeadlocks

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

• The computational complexity of propositional STRIPS planning
• The complexity of optimal monotonic planning: the bad, the good, and the causal graph
• Blocks World revisited
• scientific article; zbMATH DE number 67474
• A probabilistic analysis of propositional STRIPS planning

Cites work

• Complexity, decidability and undecidability results for domain-independent planning
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 3978432 (Why is no real title available?)
• scientific article; zbMATH DE number 3657150 (Why is no real title available?)
• scientific article; zbMATH DE number 67474 (Why is no real title available?)
• scientific article; zbMATH DE number 194009 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3436590 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)

Cited in

(24)

• On the computational complexity of temporal projection, planning, and plan validation
• An exact algorithm for the unrestricted block relocation problem
• Solving real-world sized container pre-marshalling problems with an iterative deepening branch-and-bound algorithm
• On SAT instance classes and a method for reliable performance experiments with SAT solvers
• Complexity, decidability and undecidability results for domain-independent planning
• Using temporal logics to express search control knowledge for planning
• On distinguishing sets of structures by first-order sentences of minimal quantifier rank
• A complete parameterized complexity analysis of bounded planning
• A new mixed integer program and extended look-ahead heuristic algorithm for the block relocation problem
• A multi-heuristic approach for solving the pre-marshalling problem
• Model-lite planning: case-based vs. model-based approaches
• On the nature and role of modal truth criteria in planning
• Loading, unloading and premarshalling of stacks in storage areas: survey and classification
• Multi-agent cooperation via reasoning about the behavior of others
• Container relocation problem with time windows for container departure
• History-dependent scheduling: models and algorithms for scheduling with general precedence and sequence dependence
• On the abstraction method for the container relocation problem
• A biased random-key genetic algorithm for the container pre-marshalling problem
• A mathematical formulation and complexity considerations for the blocks relocation problem
• Blocks World revisited
• Ofelimos: combinatorial optimization via proof-of-useful-work. A provably secure blockchain protocol
• Hybrid planning for challenging construction problems: an answer set programming approach
• On the complexity of the storyplan problem
• Complexity results for standard benchmark domains in planning

This page was built for publication: On the complexity of blocks-world planning

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