COMPLEXITY RESULTS FOR SAS<sup>+</sup> PLANNING
Computational IntelligencePublished 1 November 1995
Christer Bäckström, Bernhard Nebel
Citations402
SJR quartileQ2
SJR score0.58
SNIP1.20
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This article provides a complete map over the complexity of SAS+ planning under all combinations of the previously considered restrictions and proves that the SAS+‐PUS problem is the maximal tractable problem under the restrictions.
Abstract
We have previously reported a number of tractable planning problems defined in the SAS + formalism. This article complements these results by providing a complete map over the complexity of SAS + planning under all combinations of the previously considered restrictions. We analyze the complexity of both finding a minimal plan and finding any plan. In contrast to other complexity surveys of planning, we study not only the complexity of the decision problems but also the complexity of the generation problems. We prove that the SAS + ‐PUS problem is the maximal tractable problem under the restrictions we have considered if we want to generate minimal plans. If we are satisfied with any plan, then we can generalize further to the SAS + ‐US problem, which we prove to be the maximal tractable problem in this case.
Keywords
Computer Science
Artificial IntelligenceStrips: A new approach to the application of theorem proving to problem solving
4,073 Citations1971Richard Fikes, Nils J. Nilsson
A new problem solver called STRIPS is described that attempts to find a sequence of operators in a space of world models to transform a given initial world model into a model in which a given goal formula can be proven to be true.
Artificial IntelligencePlanning for conjunctive goals
1,110 Citations1987David Chapman
Theorems that suggest that efficient general purpose planning with more expressive action representations is impossible are presented, and ways to avoid this problem are suggested.
Artificial IntelligenceThe computational complexity of propositional STRIPS planning
845 Citations1994Tom Bylander
For these types of restrictions, it is shown when planning is tractable (polynomial) and intractable (NP-hard) and PSPACE-complete to determine if a given planning instance has any solutions.
Artificial IntelligencePlanning as search: A quantitative approach
364 Citations1987Richard E. Korf
It is presented that planning can be viewed as problem-solving search using subgoals, macro-operators, and abstraction as knowledge sources and an analysis of abstraction concludes that abstraction hierarchies can reduce exponential problems to linear complexity.
Artificial IntelligenceA validation-structure-based theory of plan modification and reuse
233 Citations1992Subbarao Kambhampati, James Hendler
A theory of plan modification applicable to hierarchical nonlinear planning is presented, which utilizes the validation structure of stored plans to yield a flexible and conservative plan modification framework.
Artificial IntelligenceOn the complexity of blocks-world planning
220 Citations1992N.C. Gupta, Dana Nau
It is shown that in the best-known version of the blocks world, planning is difficult, in the sense that finding an optimal plan is NP-hard, but theNP-hardness is not due to deleted-condition interactions, but instead due to a situation which the authors call a deadlock.
Artificial IntelligenceReasoning about partially ordered events
120 Citations1988Thomas Dean, Mark Boddy
This paper provides a partial decision procedure that reports useful results and runs in polynomial time as an alternative to a complete, but potentially exponential-time decision procedure.
MIT Press eBooksHandbook of Theoretical Computer Science: Algorithms and Complexity
96 Citations1990Jan Van Leeuwen, Albert R. Meyer +1 more
This handbook will provide professionals and students with a comprehensive overview of the main results and developments in this rapidly evolving field and consists of thirty-seven chapters in two volumes addressing core areas of theoretical computer science as it is practiced today.
Computational IntelligencePlanning in polynomial time: the SAS‐PUBS class
63 Citations1991Christer Bäckström, Inger Klein
This article describes a polynomial‐time, O(n3), planning algorithm for a limited class of planning problems that achieves computational tractability, but at the expense of only applying to a significantly morelimited class of problems.
Artificial IntelligenceOn the computational complexity of temporal projection, planning, and plan validation
47 Citations1994Bernhard Nebel, Christer Bäckström
It is shown that plan validation is tractable for an even larger class of plans—the unconditional plans—for which temporal projection is NP-hard, thus indicating that temporal projection may not be a necessary ingredient in planning and plan validation.
National Conference on Artificial IntelligenceA representation of action structures
47 Citations1986Erik Sandewall, Ralph Rönnquist
The formalism is developed, the example is given, and the criterion for admissible action' structures is specified formally, where postconditions of earlier actions serve as prevail— or preconditions of later actions in a coherent way, and there are no conflicting attempts to change ("update") a feature in the world.
On the complexity of domain-independent planning
45 Citations1992Kutluhan Erol, Dana Nau +1 more
This paper examines how the complexity of domain-independent planning with STRIPS-style operators depends on the nature of the planning operators and shows how the time complexity varies depending on a wide variety of conditions.
Artificial IntelligenceExpressive equivalence of planning formalisms
41 Citations1995Christer Bäckström
It is proven that neither negative goals, partial initial states nor multi-valued state variables increase the expressiveness of “standard” propositional STRIPS under ESP reduction.
Principles of Knowledge Representation and ReasoningEquivalence and Tractability Results for SAS+ Planning.
32 Citations1992Christer Bäckström
This specification discloses a copying apparatus having an original feeding mechanism for feeding originals by moving the originals on the surface of an original supporting member characterized in that discharging means acts on the original support member from that side opposite to the original supporting side of theOriginal supporting member to discharge the original Supporting surface.
Parallel non-binary planning in polynomial time
27 Citations1991Christer Bäckström, Inger Klein
A class of planning problems which allows non-binary state variables and parallel execution of actions is presented, and it is proven to be tractable and a sound and complete polynomial time algorithm for planning within this class is provided.
Elsevier eBooksComplexity Results for Extended Planning
23 Citations1992Tom Bylander
My primary result is that planning with definite Horn domain theories is PSPACE-complete even if operators are limited to zero preconditions and one postcondition, which is not encouraging for domain-independent planning.
Reasoning about interdependent actions
21 Citations1988Christer Bäckström
This thesis consists of two papers on different but related topics concerned with the use of logic as a tool to model mechanical assembly processes.
National Conference on Artificial IntelligenceComplexity results for serial decomposability
18 Citations1992Tom Bylander
The computational complexity of serial decomposability is analyzed and it is found that given a bound on the size of the input, every problem in PSPACE can be transformed to a problem that is nearly serially-decomposable.
Lecture notes in computer sciencePlanning in polynomial time
6 Citations1990Christer Bäckström, Inger Klein
This paper describes a polynomial-time, O(n3), planning algorithm for a limited class of planning problems that achieves computational tractability, but at the expense of only applying to a significantly morelimited class of problems.
Complexity results for state-variable planning under mixed syntactical and structural restrictions
5 Citations1995Peter Jönsson, Christer Bäckström
An almost exhaustive map of complexity results for state-variable planning under all combinations of syntactical and structural restrictions, considering both optimal and non-optimal plan generation.
Medical Entomology and ZoologyCurrent Trends in Ai Planning: Ewsp'93-2Nd European Workshop on Planning
3 Citations1994Christer Bäckström, Erik Sandewall