The computational complexity of propositional STRIPS planning
From MaRDI portal
Recommendations
- scientific article; zbMATH DE number 67474
- Strong bounds on the approximability of two Pspace-hard problems in propositional planning
- A probabilistic analysis of propositional STRIPS planning
- Complexity, decidability and undecidability results for domain-independent planning
- Complexity results for standard benchmark domains in planning
Cites work
- scientific article; zbMATH DE number 3657150 (Why is no real title available?)
- scientific article; zbMATH DE number 67473 (Why is no real title available?)
- scientific article; zbMATH DE number 67474 (Why is no real title available?)
- scientific article; zbMATH DE number 67476 (Why is no real title available?)
- scientific article; zbMATH DE number 67483 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Complexity, decidability and undecidability results for domain-independent planning
- Impediments to universal preference-based default theories
- Macro-operators: A weak method for learning
- Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems
- Planning for conjunctive goals
- Reasoning about action. I: A possible worlds approach
- Reasoning about partially ordered events
- Relationships between nondeterministic and deterministic tape complexities
- STRIPS: A new approach to the application of theorem proving to problem solving
- The Decision Problem for a Class of First‐Order Formulas in Which all Disjunctions are Binary
Cited in
(only showing first 100 items - show all)- On the complexity of planning for agent teams and its implications for single agent planning
- Planning over chain causal graphs for variables with domains of size 5 is NP-hard
- An algorithmic theory of learning: Robust concepts and random projection
- Verified over-approximation of the diameter of propositionally factored transition systems
- Star-topology decoupled state space search
- Heuristics for planning with penalties and rewards formulated in logic and computed through circuits
- Goal distance estimation for automated planning using neural networks and support vector machines
- On the complexity of blocks-world planning
- Complexity, decidability and undecidability results for domain-independent planning
- A simple polynomial-time rescaling algorithm for solving linear programs
- The complexity of deciding reachability properties of distributed negotiation schemes
- Causal graphs and structurally restricted planning
- On the complexity of case-based planning
- \(\text{DA}^2\) merging operators
- Kernel functions for case-based planning
- Concise finite-domain representations for PDDL planning tasks
- Algorithms and conditional lower bounds for planning problems
- Functional strips: A more flexible language for planning and problem solving
- On the computational complexity of temporal projection, planning, and plan validation
- scientific article; zbMATH DE number 67474 (Why is no real title available?)
- Blocks World revisited
- The influence of \(k\)-dependence on the complexity of planning
- Experimental evaluation of pheromone models in ACOPlan
- Solving Simple Planning Problems with More Inference and No Search
- Automatic workflow verification and generation
- Conformant plans and beyond: principles and complexity
- Planning in multi-agent environment using strips representation and non-cooperative equilibrium strategy
- scientific article; zbMATH DE number 1467489 (Why is no real title available?)
- The complexity of achievement and maintenance problems in agent-based systems
- Applicability conditions for plans with loops: computability results and algorithms
- CPCES: a planning framework to solve conformant planning problems through a counterexample guided refinement
- Specifying and computing preferred plans
- Intractability and the use of heuristics in psychological explanations
- A survey of computational complexity results in systems and control
- Fast planning through planning graph analysis
- An algorithmic theory of learning: robust concepts and random projection
- Towards efficient universal planning: A randomized approach
- Red-black planning: a new systematic approach to partial delete relaxation
- On the undecidability of probabilistic planning and related stochastic optimization problems
- Directed Unfolding of Petri Nets
- scientific article; zbMATH DE number 67473 (Why is no real title available?)
- Computational complexity of planning and approximate planning in the presence of incompleteness
- Contingent planning under uncertainty via stochastic satisfiability
- Merge-and-Shrink Abstraction
- The MADLA planner: multi-agent planning by combination of distributed and local heuristic search
- Decidability and complexity of action-based temporal planning over dense time
- scientific article; zbMATH DE number 1946870 (Why is no real title available?)
- Phase transitions of PP-complete satisfiability problems
- scientific article; zbMATH DE number 1931653 (Why is no real title available?)
- State space search nogood learning: online refinement of critical-path dead-end detectors in planning
- From model checking to equilibrium checking: reactive modules for rational verification
- Limitations of acyclic causal graphs for planning
- State-variable planning under structural restrictions: algorithms and complexity
- Default reasoning by deductive planning
- Discovering hidden structure in factored MDPs
- A probabilistic analysis of propositional STRIPS planning
- Complexity of Planning in Action Formalisms Based on Description Logics
- Landmark-based approaches for goal recognition as planning
- A complete parameterized complexity analysis of bounded planning
- Refining complexity analyses in planning by exploiting the exponential time hypothesis
- Policy analysis for administrative role-based access control
- Optimal admissible composition of abstraction heuristics
- Complexity results for standard benchmark domains in planning
- Conformant planning via heuristic forward search: A new approach
- Strong planning under uncertainty in domains with numerous but identical elements (a generic approach)
- Temporal ASP: from logical foundations to practical use with \texttt{telingo}
- Automated planning as an early verification tool for distributed control
- On the expressive power of planning formalisms. Conditional effects and Boolean preconditions in the STRIPS formalisms
- A framework for analysing state-abstraction methods
- Cost-optimal planning, delete relaxation, approximability, and heuristics
- Qualitative numeric planning: reductions and complexity
- Planning with incomplete information (invited paper)
- Backdoors to planning
- Upper and lower time and space bounds for planning
- Planning in artificial intelligence
- On-the-Fly Macros
- Picturing Counting Reductions with the ZH-Calculus
- The complexity of agent design problems: Determinism and history dependence
- Planning under uncertainty as G<scp>OLOG</scp>programs
- Expressiveness of communication in answer set programming
- A state space analysis of propose-and-revise
- Managing temporal cycles in planning problems requiring concurrency
- A planner agent that tries its best in presence of nondeterminism
- COMPLETENESS AND REALIZABILITY: CONDITIONS FOR AUTOMATIC GENERATION OF WORKFLOWS
- On transformation of conditional, conformant and parallel planning to linear programming
- On transformation of STRIPS planning to linear programming
- Determining action reversibility in STRIPS using answer set and epistemic logic programming
- Maintenance of plan libraries for case-based planning: offline and online policies
- Maintenance goals of agents in a dynamic environment: formulation and policy construction
- A lightweight epistemic logic and its application to planning
- Complexity of planning for connected agents in a partially known environment
- Computing programs for generalized planning using a classical planner
- Intractability and approximation of optimization theories of cognition
- Parameterized complexity of theory of mind reasoning in dynamic epistemic logic
- Towards the evaluation of action reversibility in STRIPS using domain generators
- Set-structured and cost-sharing heuristics for classical planning
- Computational complexity of computing symmetries in finite-domain planning
- On the complexity of the storyplan problem
- The effects of uncertainty on plan success in a simulated maintenance robot domain
- Divide-and-Evolve: a Sequential Hybridization Strategy Using Evolutionary Algorithms
This page was built for publication: The computational complexity of propositional STRIPS planning
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1337679)
