The computational complexity of propositional STRIPS planning

DOI10.1016/0004-3702(94)90081-7zbMath0821.68065OpenAlexW2061146398MaRDI QIDQ1337679

Publication date: 19 September 1995

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0004-3702(94)90081-7

zbMATH Keywords

computational complexity STRIPS planning

Mathematics Subject Classification ID

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

Related Items (83)

Goal distance estimation for automated planning using neural networks and support vector machines ⋮ Decidability and complexity of action-based temporal planning over dense time ⋮ Automatic workflow verification and generation ⋮ Concise finite-domain representations for PDDL planning tasks ⋮ Strong planning under uncertainty in domains with numerous but identical elements (a generic approach) ⋮ Expressiveness of communication in answer set programming ⋮ Default reasoning by deductive planning ⋮ An algorithmic theory of learning: robust concepts and random projection ⋮ Phase transitions of PP-complete satisfiability problems ⋮ Merge-and-Shrink Abstraction ⋮ Maintenance goals of agents in a dynamic environment: formulation and policy construction ⋮ Heuristics for planning with penalties and rewards formulated in logic and computed through circuits ⋮ Applicability conditions for plans with loops: computability results and algorithms ⋮ From model checking to equilibrium checking: reactive modules for rational verification ⋮ Intractability and the use of heuristics in psychological explanations ⋮ The MADLA planner: multi-agent planning by combination of distributed and local heuristic search ⋮ State-variable planning under structural restrictions: algorithms and complexity ⋮ Verified Over-Approximation of the Diameter of Propositionally Factored Transition Systems ⋮ Planning in multi-agent environment using strips representation and non-cooperative equilibrium strategy ⋮ A probabilistic analysis of propositional STRIPS planning ⋮ Complexity of Planning in Action Formalisms Based on Description Logics ⋮ Kernel functions for case-based planning ⋮ Complexity of planning for connected agents in a partially known environment ⋮ Fast planning through planning graph analysis ⋮ Divide-and-Evolve: a Sequential Hybridization Strategy Using Evolutionary Algorithms ⋮ The influence of \(k\)-dependence on the complexity of planning ⋮ Temporal ASP: from logical foundations to practical use with \texttt{telingo} ⋮ Experimental evaluation of pheromone models in ACOPlan ⋮ Picturing Counting Reductions with the ZH-Calculus ⋮ A planner agent that tries its best in presence of nondeterminism ⋮ Intractability and approximation of optimization theories of cognition ⋮ Parameterized complexity of theory of mind reasoning in dynamic epistemic logic ⋮ Specifying and computing preferred plans ⋮ On the complexity of planning for agent teams and its implications for single agent planning ⋮ The complexity of deciding reachability properties of distributed negotiation schemes ⋮ Policy analysis for administrative role-based access control ⋮ Conformant planning via heuristic forward search: A new approach ⋮ Cost-optimal Planning, Delete Relaxation, Approximability, and Heuristics ⋮ Limitations of acyclic causal graphs for planning ⋮ On the complexity of case-based planning ⋮ Towards efficient universal planning: A randomized approach ⋮ Planning with Incomplete Information ⋮ Algorithms and conditional lower bounds for planning problems ⋮ A lightweight epistemic logic and its application to planning ⋮ Refining complexity analyses in planning by exploiting the exponential time hypothesis ⋮ State space search nogood learning: online refinement of critical-path dead-end detectors in planning ⋮ Star-topology decoupled state space search ⋮ A simple polynomial-time rescaling algorithm for solving linear programs ⋮ A survey of computational complexity results in systems and control ⋮ Discovering hidden structure in factored MDPs ⋮ Conformant plans and beyond: principles and complexity ⋮ Blocks World revisited ⋮ Set-structured and cost-sharing heuristics for classical planning ⋮ An algorithmic theory of learning: Robust concepts and random projection ⋮ Directed Unfolding of Petri Nets ⋮ The complexity of agent design problems: Determinism and history dependence ⋮ Causal graphs and structurally restricted planning ⋮ A state space analysis of propose-and-revise ⋮ Optimal admissible composition of abstraction heuristics ⋮ Landmark-based approaches for goal recognition as planning ⋮ COMPLETENESS AND REALIZABILITY: CONDITIONS FOR AUTOMATIC GENERATION OF WORKFLOWS ⋮ On-the-Fly Macros ⋮ A framework for analysing state-abstraction methods ⋮ Planning under uncertainty as G<scp>OLOG</scp>programs ⋮ Backdoors to planning ⋮ Computing programs for generalized planning using a classical planner ⋮ CPCES: a planning framework to solve conformant planning problems through a counterexample guided refinement ⋮ Computational complexity of planning and approximate planning in the presence of incompleteness ⋮ FROM PLANNING TO SEARCHING FOR THE SHORTEST PLAN: AN OPTIMAL TRANSITION ⋮ MANAGING TEMPORAL CYCLES IN PLANNING PROBLEMS REQUIRING CONCURRENCY ⋮ On transformation of conditional, conformant and parallel planning to linear programming ⋮ Red-black planning: a new systematic approach to partial delete relaxation ⋮ Towards the evaluation of action reversibility in STRIPS using domain generators ⋮ Determining Action Reversibility in STRIPS Using Answer Set and Epistemic Logic Programming ⋮ Automated planning as an early verification tool for distributed control ⋮ A complete parameterized complexity analysis of bounded planning ⋮ On the computational complexity of temporal projection, planning, and plan validation ⋮ Complexity results for standard benchmark domains in planning ⋮ The complexity of achievement and maintenance problems in agent-based systems ⋮ On the undecidability of probabilistic planning and related stochastic optimization problems ⋮ Contingent planning under uncertainty via stochastic satisfiability ⋮ \(\text{DA}^2\) merging operators ⋮ The effects of uncertainty on plan success in a simulated maintenance robot domain

Cites Work

This page was built for publication: The computational complexity of propositional STRIPS planning