Christer Bäckström

AIJ Journal 2022 Journal Article

A framework for analysing state-abstraction methods

• Christer Bäckström
• Peter Jonsson

Abstraction has been used in combinatorial search and action planning from the very beginning of AI. Many different methods and formalisms for state abstraction have been proposed in the literature, but they have been designed from various points of view and with varying purposes. Hence, these methods have been notoriously difficult to analyse and compare in a structured way. In order to improve upon this situation, we present a coherent and flexible framework for modelling abstraction (and abstraction-like) methods based on graph transformations. The usefulness of the framework is demonstrated by applying it to problems in both search and planning. We model six different abstraction methods from the planning literature and analyse their intrinsic properties. We show how to capture many search abstraction concepts (such as avoiding backtracking between levels) and how to put them into a broader context. We also use the framework to identify and investigate connections between refinement and heuristics—two concepts that have usually been considered as unrelated in the literature. This provides new insights into various topics, e. g. Valtorta's theorem and spurious states. We finally extend the framework with composition of transformations to accommodate for abstraction hierarchies, and other multi-level concepts. We demonstrate the latter by modelling and analysing the merge-and-shrink abstraction method.

JAIR Journal 2021 Journal Article

Cost-optimal Planning, Delete Relaxation, Approximability, and Heuristics

• Christer Bäckström
• Peter Jonsson
• Sebastian Ordyniak

Cost-optimal planning is a very well-studied topic within planning, and it has proven to be computationally hard both in theory and in practice. Since cost-optimal planning is an optimisation problem, it is natural to analyse it through the lens of approximation. An important reason for studying cost-optimal planning is heuristic search; heuristic functions that guide the search in planning can often be viewed as algorithms solving or approximating certain optimisation problems. Many heuristic functions (such as the ubiquitious h+ heuristic) are based on delete relaxation, which ignores negative effects of actions. Planning for instances where the actions have no negative effects is often referred to as monotone planning. The aim of this article is to analyse the approximability of cost-optimal monotone planning, and thus the performance of relevant heuristic functions. Our findings imply that it may be beneficial to study these kind of problems within the framework of parameterised complexity and we initiate work in this direction.

IJCAI Conference 2019 Conference Paper

A Refined Understanding of Cost-optimal Planning with Polytree Causal Graphs

• Christer Bäckström
• Peter Jonsson
• Sebastian Ordyniak

Complexity analysis based on the causal graphs of planning instances is a highly important research area. In particular, tractability results have led to new methods for constructing domain-independent heuristics. Important early examples of such results were presented by, for instance, Brafman & Domshlak and Katz & Keyder. More general results based on polytrees and bounding certain parameters were subsequently derived by Aghighi et al. and Ståhlberg. We continue this line of research by analyzing cost-optimal planning for instances with a polytree causal graph, bounded domain size and bounded depth. We show that no further restrictions are necessary for tractability, thus generalizing the previous results. Our approach is based on a novel method of closely analysing optimal plans: we recursively decompose the causal graph in a way that allows for bounding the number of variable changes as a function of the depth, using a reording argument and a comparison with prefix trees of known size. We then transform the planning instances into tree-structured constraint satisfaction instances.

SoCS Conference 2018 Conference Paper

A Refined Understanding of Cost-Optimal Planning with Polytree Causal Graphs

• Christer Bäckström
• Peter Jonsson
• Sebastian Ordyniak

Complexity analysis based on the causal graphs of planning instances has emerged as a highly important area of research. In particular, tractability results have led to new methods for the identification of domain-independent heuristics. Important early examples of such tractability results have been presented by, for instance, Brafman & Domshlak and Katz & Keyder. More general results based on polytrees and bounding certain parameters were subsequently derived by Aghighi et al. and Ståhlberg. We continue this line of research by analyzing cost-optimal planning restricted to instances with a polytree causal graph, bounded domain size and bounded depth (i. e. the length of the longest directed path in the causal graph). We show that no further restrictions are necessary for tractability, thus generalizing the previous results. Our approach is based on a novel method of closely analysing optimal plans: we recursively decompose the causal graph in a way that allows for bounding the number of variable changes as a function of the depth, using a reording argument and a comparison with prefix trees of known size. We can then transform the planning instances into constraint satisfaction instances; an idea that has previously been exploited by, for example, Brafman & Domshlak and Bäckström. This allows us to utilise efficient algorithms for constraint optimisation over tree-structured instances.

IJCAI Conference 2018 Conference Paper

Novel Structural Parameters for Acyclic Planning Using Tree Embeddings

• Christer Bäckström
• Peter Jonsson
• Sebastian Ordyniak

We introduce two novel structural parameters for acyclic planning (planning restricted to instances with acyclic causal graphs): up-depth and down-depth. We show that cost-optimal acyclic planning restricted to instances with bounded domain size and bounded up- or down-depth can be solved in polynomial time. For example, many of the tractable subclasses based on polytrees are covered by our result. We analyze the parameterized complexity of planning with bounded up- and down-depth: in a certain sense, down-depth has better computational properties than up-depth. Finally, we show that computing up- and down-depth are fixed-parameter tractable problems, just as many other structural parameters that are used in computer science. We view our results as a natural step towards understanding the complexity of acyclic planning with bounded treewidth and other parameters.

JAIR Journal 2017 Journal Article

Time and Space Bounds for Planning

• Christer Bäckström
• Peter Jonsson

There is an extensive literature on the complexity of planning, but explicit bounds on time and space complexity are very rare. On the other hand, problems like the constraint satisfaction problem (CSP) have been thoroughly analysed in this respect. We provide a number of upper- and lower-bound results (the latter based on various complexity-theoretic assumptions such as the Exponential Time Hypothesis) for both satisficing and optimal planning. We show that many classes of planning instances exhibit a dichotomy: either they can be solved in polynomial time or they cannot be solved in subexponential time. In many cases, we can even prove closely matching upper and lower bounds. Our results also indicate, analogously to CSPs, the existence of sharp phase transitions. We finally study and discuss the trade-off between time and space. In particular, we show that depth-first search may sometimes be a viable option for planning under severe space constraints.

ICAPS Conference 2016 Conference Paper

A Multi-Parameter Complexity Analysis of Cost-Optimal and Net-Benefit Planning

• Meysam Aghighi
• Christer Bäckström

Aghighi and Bäckström have previously studied cost-optimal planning (COP) and net-benefit planning (NBP) for three action cost domains: the positive integers (Z_+), the non-negative integers (Z_0) and the positive rationals (Q_+). These were indistinguishable under standard complexity analysis for both problems, but separated for COP using parameterised complexity analysis. With the plan cost, k, as parameter, COP was W[2]-complete for Z_+, but para-NP-hard for both Z_0 and Q_+, i. e. presumably much harder. NBP was para-NP-hard for all three domains, thus remaining unseparable. We continue by considering combinations with several additional parameters and also the non-negative rationals (Q_0). Examples of new parameters are the plan length, l, and the largest denominator of the action costs, d. Our findings include: (1) COP remains W[2]-hard for all domains, even if combining all parameters; (2) COP for Z_0 is in W[2] for the combined parameter {k, l}; (3) COP for Q_+ is in W[2] for {k, d} and (4) COP for Q_0 is in W[2] for {k, d, l}. For NBP we consider further additional parameters, where the most crucial one for reducing complexity is the sum of variable utilities. Our results help to understand the previous results, eg. the separation between Z_+ and Q_+ for COP, and to refine the previous connections with empirical findings.

ECAI Conference 2016 Conference Paper

Analysing Approximability and Heuristics in Planning Using the Exponential-Time Hypothesis

• Meysam Aghighi
• Christer Bäckström
• Peter Jonsson
• Simon Ståhlberg

Cost-optimal planning has become a very well-studied topic within planning. Needless to say, cost-optimal planning has proven to be computationally hard both theoretically and in practice. Since cost-optimal planning is an optimisation problem, it is natural to analyse it from an approximation point of view. Even though such studies may be valuable in themselves, additional motivation is provided by the fact that there is a very close link between approximability and the performance of heuristics used in heuristic search. The aim of this paper is to analyse approximability (and indirectly the performance of heuristics) with respect to lower time bounds. That is, we are not content by merely classifying problems into complexity classes - we also study their time complexity. This is achieved by replacing standard complexity-theoretic assumptions (such as P ≠ NP) with the exponential time hypothesis (ETH). This enables us to analyse, for instance, the performance of the h+heuristic and obtain general trade-off results that correlate approximability bounds with bounds on time complexity.

ECAI Conference 2016 Conference Paper

Upper and Lower Time and Space Bounds for Planning

• Christer Bäckström
• Peter Jonsson

There is an extensive literature on the complexity of planning, but explicit bounds on time and space complexity are very rare. On the other hand, problems like the constraint satisfaction problem have been thoroughly analysed in this respect. We provide a number of upper and lower bound results for both plan satisfiability (PSAT) and length-optimal planning (LOP), with an emphasis on monotone planning (where actions have only positive effects) which is used in, for instance, h+and similar heuristics. Let v and a be the number of variables and actions, respectively. We consider both restrictions on the number and polarity of preconditions and effects of actions and the PUBS restrictions in SAS+. For all such classes, we show that PSAT and LOP is either tractable or cannot be solved in subexponential time 2o( v) or time 2o( a) , unless the so-called Exponential Time Hypothesis (ETH) is false. There is also a sharp transition: monotone LOP can be solved in time 2o( v) ifbut not if a∈ Ω ( v) . We also study upper bounds and discuss the trade-off between time and space, providing a polynomial-space algorithm for monotone LOP that beats depth-first search in most cases. This raises the important question how lower bounds are affected by polynomial space restrictions.

AAAI Conference 2015 Conference Paper

Some Fixed Parameter Tractability Results for Planning with Non-Acyclic Domain-Transition Graphs

• Christer Bäckström

Bäckström studied the parameterised complexity of planning when the domain-transition graphs (DTGs) are acyclic. He used the parameters d (domain size), k (number of paths in the DTGs) and w (treewidth of the causal graph), and showed that planning is fixed-parameter tractable (fpt) in these parameters, and fpt in only parameter k if the causal graph is a polytree. We continue this work by considering some additional cases of non-acyclic DTGs. In particular, we consider the case where each strongly connected component (SCC) in a DTG must be a simple cycle, and we show that planning is fpt for this case if the causal graph is a polytree. This is done by first preprocessing the instance to construct an equivalent abstraction and then apply Bäckströms technique to this abstraction. We use the parameters d and k, reinterpreting this as the number of paths in the condensation of a DTG, and the two new parameters c (the number of contracted cycles along a path) and pmax (an upper bound for walking around cycles, when not unbounded).

ECAI Conference 2014 Conference Paper

Parameterising the Complexity of Planning by the Number of Paths in the Domain-transition Graphs

• Christer Bäckström

We apply the theory of parameterised complexity to planning, using the concept of fixed-parameter tractability (fpt) which is more relaxed than the usual tractability concept. The parameter we focus on is the maximal number of paths in the domain-transition graphs, and we show that for this parameter, optimal planning is fpt for planning instances with polytree causal graphs and acyclic domain-transition graphs. If this parameter is combined with the additional parameters of domain size for the variables and the treewidth of the causal graph, then planning is fpt also for instances with arbitrary causal graphs. Furthermore, all these parameters are fpt to test in advance. These results also imply that delete-relaxed planning is fpt, even in its recent generalisation to non-binary variables.

IJCAI Conference 2013 Conference Paper

Bridging the Gap Between Refinement and Heuristics in Abstraction

• Christer Bäckström
• Peter Jonsson

There are two major uses of abstraction in planning and search: refinement (where abstract solutions are extended into concrete solutions) and heuristics (where abstract solutions are used to compute heuristics for the original search space). These two approaches are usually viewed as unrelated in the literature. It is reasonable to believe, though, that they are related, since they are both intrinsically based on the structure of abstract search spaces. We take the first steps towards formally investigating their relationships, employing our recently introduced framework for analysing and comparing abstraction methods. By adding some mechanisms for expressing metric properties, we can capture concepts like admissibility and consistency of heuristics. We present an extensive study of how such metric properties relate to the properties in the original framework, revealing a number of connections between the refinement and heuristic approaches. This also provides new insights into, for example, Valtorta’s theorem and spurious states.

SoCS Conference 2013 Conference Paper

Fast Detection of Unsolvable Planning Instances Using Local Consistency

• Christer Bäckström
• Peter Jonsson
• Simon Ståhlberg

There has been a tremendous advance in domain-independent planning over the past decades, and planners have become increasingly efficient at finding plans. However, this has not been paired by any corresponding improvement in detecting unsolvable instances. Such instances are obviously important but largely neglected in planning. In other areas, such as constraint solving and model checking, much effort has been spent on devising methods for detecting unsolvability. We introduce a method for detecting unsolvable planning instances that is loosely based on consistency checking in constraint programming. Our method balances completeness against efficiency through a parameter k: the algorithm identifies more unsolvable instances but takes more time for increasing values of k. We present empirical data for our algorithm and some standard planners on a number of unsolvable instances, demonstrating that our method can be very efficient where the planners fail to detect unsolvability within reasonable resource bounds. We observe that planners based on the h^m heuristic or pattern databases are better than other planners for detecting unsolvability. This is not a coincidence since there are similarities (but also significant differences) between our algorithm and these two heuristic methods.

SoCS Conference 2012 Conference Paper

Abstracting Abstraction in Search II: Complexity Analysis

• Christer Bäckström
• Peter Jonsson

Modelling abstraction as a function from the original state space to an abstract state space is a common approach in combinatorial search. Sometimes this is too restricted, though, and we have previously proposed a framework using a more flexible concept of transformations between labelled graphs. We also proposed a number of properties to describe and classify such transformations. This framework enabled the modelling of a number of different abstraction methods in a way that facilitated comparative analyses. It is of particular interest that these properties can be used to capture the concept of refinement without backtracking between levels; how to do this has been an open question for at least twenty years. In this paper, we continue our previous research by analysing the complexity of testing the various transformation properties for both explicit and implicit graph~representations.

KR Conference 2012 Conference Paper

Abstracting Abstraction in Search with Applications to Planning

• Christer Bäckström
• Peter Jonsson

we restrict ourselves in this way; its use dates back to A B STRIPS (Sacerdoti 1974) and even to the first version of GPS (Newell, Shaw, and Simon 1959). In order for abstraction to be useful, the abstract instance should be easier to solve and the total time spent should be less than without using abstraction. This is a reasonable requirement, yet it has turned out very difficult to achieve in practice. It has been demonstrated in many ways that abstraction can be very effective at decreasing overall solution time but few, if any, methods give any guarantees. For instance, Knoblock (1994) proposed a way to automatically create abstractions and demonstrated that it could give exponential speed-up in certain cases while Bäckström and Jonsson (1995) showed that the method can also backfire by creating solutions that are exponentially longer than the optimal solutions. Abstraction is thus a method that can strike both ways and it requires a careful analysis of the application domain to know if abstraction is useful or not. Abstraction has been used in search and planning from the very beginning of AI. Many different methods and formalisms for abstraction have been proposed in the literature but they have been designed from various points of view and with varying purposes. Hence, these methods have been notoriously difficult to analyse and compare in a structured way. In order to improve upon this situation, we present a coherent and flexible framework for modelling abstraction (and abstraction-like) methods based on transformations on labelled graphs. Transformations can have certain method properties that are inherent in the abstraction methods and describe their fundamental modelling characteristics, and they can have certain instance properties that describe algorithmic and computational characteristics of problem instances. The usefulness of the framework is demonstrated by applying it to problems in both search and planning. First, we show that we can capture many search abstraction concepts (such as avoidance of backtracking between levels) and that we can put them into a broader context. We further model five different abstraction concepts from the planning literature. Analysing what method properties they have highlights their fundamental differences and similarities. Finally, we prove that method properties sometimes imply instance properties. Taking also those instance properties into account reveals important information about computational aspects of the five methods. 1 1. 1 A large number of different abstraction and abstractionlike methods appear in the literature. Unfortunately, many of these methods are tied to particular formalisms which make them difficult to analyse and compare in a meaningful way. We present a framework for comparing and analysing abstraction and abstraction-like methods based on transformations between labelled graphs. The idea of using functions (typically homomorphisms) on graphs (or other structures) for describing abstractions is very natural and has appeared in the literature earlier, cf. Holte et al. (1996) or Helmert, Haslum, and Hoffmann (2007). We extend this idea by viewing transformations as tuples hf, Ri where, loosely speaking, the function f describes the “structure” of the abstracted graph and R gives an “interpretation” of the abstracted labels. This gives us a plethora of possibilities to model and study different kinds of abstraction-like methods. We stress that we do not set out to create a grand theory of abstraction. There are attempts in the literature to define and study abstraction on a very general level which allow for an in-depth treatment of ontological aspects, cf. Giunchiglia and Walsh (1992) or Pandurang Nayak and Levy (1995). Our approach is much more pragmatic, and it is first and foremost intended for studying computational aspects of abstraction in search. This does not exclude that it may be useful in other contexts but we view this as an added bonus and not a primary goal. We also want to point out that our pur-

ECAI Conference 2012 Conference Paper

From Macro Plans to Automata Plans

• Christer Bäckström
• Anders Jonsson 0001
• Peter Jonsson

Macros have a long-standing role in planning as a tool for representing repeating subsequences of operators. Macros are useful both for guiding search towards a solution and for representing plans compactly. In this paper we introduce automata plans which consist of hierarchies of finite state automata. Automata plans can be viewed as an extension of macros that enables parametrization and branching. We provide several examples of the utility of automata plans, and prove that automata plans are strictly more expressive than macro plans. We also prove that automata plans admit polynomialtime sequential access of the operators in the underlying "flat" plan, and identify a subset of automata plans that admit polynomial-time random access. Finally, we compare automata plans with other representations allowing polynomial-time sequential access.

ECAI Conference 2012 Conference Paper

Macros, Reactive Plans and Compact Representations

• Christer Bäckström
• Anders Jonsson 0001
• Peter Jonsson

The use and study of compact representations of objects is widespread in computer science. AI planning can be viewed as the problem of finding a path in a graph that is implicitly described by a compact representation in a planning language. However, compact representations of the path itself (the plan) have not received much attention in the literature. Although both macro plans and reactive plans can be considered as such compact representations, little emphasis has been placed on this aspect in earlier work. There are also compact plan representations that are defined by their access properties, for instance, that they have efficient random access or efficient sequential access. We formally compare two such concepts with macro plans and reactive plans, viewed as compact representations, and provide a complete map of the relationships between them.

AAAI Conference 2012 Conference Paper

The Complexity of Planning Revisited — A Parameterized Analysis

• Christer Bäckström
• Yue Chen
• Peter Jonsson
• Sebastian Ordyniak
• Stefan Szeider

The early classifications of the computational complexity of planning under various restrictions in STRIPS (Bylander) and SAS+ (Bäckström and Nebel) have influenced following research in planning in many ways. We go back and reanalyse their subclasses, but this time using the more modern tool of parameterized complexity analysis. This provides new results that together with the old results give a more detailed picture of the complexity landscape. We demonstrate separation results not possible with standard complexity theory, which contributes to explaining why certain cases of planning have seemed simpler in practice than theory has predicted. In particular, we show that certain restrictions of practical interest are tractable in the parameterized sense of the term, and that a simple heuristic is sufficient to make a well-known partialorder planner exploit this fact.

SoCS Conference 2011 Conference Paper

All PSPACE-Complete Planning Problems Are Equal but Some Are More Equal than Others

• Christer Bäckström
• Peter Jonsson

Complexity analysis of planning is problematic. Even very simple planning languages are PSPACE-complete, yet cannot model many simple problems naturally. Many languages with much more powerful features are also PSPACE-complete. It is thus difficult to separate planning languages in a useful way and to get complexity figures that better reflect reality. This paper introduces new methods for complexity analysis of planning and similar combinatorial search problems, in order to achieve more precision and complexity separations than standard methods allow. Padding instances with the solution size yields a complexity measure that is immune to this factor and reveals other causes of hardness, that are otherwise hidden. Further combining this method with limited non-determinism improves the precision, making even finer separations possible. We demonstrate with examples how these methods can narrow the gap between theory and practice.

ICAPS Conference 2011 Conference Paper

Limits for Compact Representation of Plans

• Christer Bäckström
• Peter Jonsson

Most planning formalisms allow instances with shortest plans of exponential length. While such instances are problematic, they are usually unavoidable and can occur in practice. There are several known cases of restricted planning problems where plans can be exponential but always have a compact (ie. polynomial) representation, often using recursive macros. Such compact representations are important since exponential plans are difficult both to use and to understand. We show that these results do not extend to the general case, by proving a number of bounds for compact representations of plans under various criteria, like efficient sequential or random access of actions. Further, we show that it is unlikely to get around this by reformulating planning into some other problem. The results are discussed in the context of abstraction, macros and plan explanation.

AIJ Journal 2000 Journal Article

Towards efficient universal planning: A randomized approach

• Peter Jonsson
• Patrik Haslum
• Christer Bäckström

One of the most widespread approaches to reactive planning is Schoppers' universal plans. We propose a stricter definition of universal plans which guarantees a weak notion of soundness, not present in the original definition, and isolate three different types of completeness that capture different behaviors exhibited by universal plans. We show that universal plans which run in polynomial time and are of polynomial size cannot satisfy even the weakest type of completeness unless the polynomial hierarchy collapses. By relaxing either the polynomial time or the polynomial space requirement, the construction of universal plans satisfying the strongest type of completeness becomes trivial. As an alternative approach, we study randomized universal planning. By considering a randomized version of completeness and a restricted (but nontrivial) class of problems, we show that there exists randomized universal plans running in polynomial time and using polynomial space which are sound and complete for the restricted class of problems. We also report experimental results on this approach to planning, showing that the performance of a randomized planner is not easily compared to that of a deterministic planner.

AIJ Journal 1999 Journal Article

Computational complexity of relating time points with intervals

• Peter Jonsson
• Thomas Drakengren
• Christer Bäckström

Several algebras have been proposed for reasoning about qualitative constraints over the time line. One of these algebras is Vilain's point–interval algebra, which can relate time points with time intervals. Apart from being a stand-alone qualitative algebra, it is also used as a subalgebra in Meiri's approach to temporal reasoning, which combines reasoning about metric and qualitative temporal constraints over both time points and time intervals. While the satisfiability problem for the full point–interval algebra is known to be NP-complete, not much is known about its 4294967296 subclasses. This article completely determines the computational complexity of these subclasses and it identifies all of the maximal tractable subalgebras—five in total.

AIJ Journal 1998 Journal Article

A unifying approach to temporal constraint reasoning

• Peter Jonsson
• Christer Bäckström

We present a formalism, Disjunctive Linear Relations (DLRs), for reasoning about temporal constraints. DLRs subsume most of the formalisms for temporal constraint reasoning proposed in the literature and is therefore computationally expensive. We also present a restricted type of DLRs, Horn DLRs, which have a polynomial-time satisfiability problem. We prove that most approaches to tractable temporal constraint reasoning can be encoded as Horn DLRs, including the ORD-Horn algebra by Nebel and Bürckert and the simple temporal constraints by Dechter et al. Thus, DLRs is a suitable unifying formalism for reasoning about temporal constraints.

AIJ Journal 1998 Journal Article

State-variable planning under structural restrictions: algorithms and complexity

• Peter Jonsson
• Christer Bäckström

Computationally tractable planning problems reported in the literature so far have almost exclusively been defined by syntactical restrictions. To better exploit the inherent structure in problems, it is probably necessary to study also structural restrictions on the underlying state-transition graph. The exponential size of this graph, though, makes such restrictions costly to test. Hence, we propose an intermediate approach, using a state-variable model for planning and defining restrictions on the separate state-transition graphs for each state variable. We identify such restrictions which can tractably be tested and we present a planning algorithm which is correct and runs in polynomial time under these restrictions. The algorithm has been implemented and it outperforms Graphplan on a number of test instances. In addition, we present an exhaustive map of the complexity results for planning under all combinations of four previously studied syntactical restrictions and our five new structural restrictions. This complexity map considers both the optimal and non-optimal plan generation problem.

AIJ Journal 1995 Journal Article

Expressive equivalence of planning formalisms

• Christer Bäckström

A concept of expressive equivalence for planning formalisms based on polynomial transformations is defined. It is argued that this definition is reasonable and useful both from a theoretical and from a practical perspective; if two languages are equivalent, then theoretical results carry over and, more practically, we can model an application problem in one language and then easily use a planner for the other language. In order to cope with the problem of exponentially sized solutions for planning problems an even stronger concept of expressive equivalence is introduced, using the novel ESP reduction. Four different formalisms for propositional planning are then analyzed, namely two variants of STRIPS, ground TWEAK and the SAS+ formalism. Although these may seem to exhibit different degrees of expressive power, it is proven that they are, in fact, expressively equivalent under ESP reduction. This means that neither negative goals, partial initial states nor multi-valued state variables increase the expressiveness of “standard” propositional STRIPS.

ECAI Conference 1994 Conference Paper

Executing Parallel Plans Faster by Adding Actions

• Christer Bäckström

AIJ Journal 1994 Journal Article

On the computational complexity of temporal projection, planning, and plan validation

• Bernhard Nebel
• Christer Bäckström

One kind of temporal reasoning is temporal projection—the computation of the consequences of a set of events. This problem is related to a number of other temporal reasoning tasks such as plan validation and planning. We show that one particular, simple case of temporal projection on partially ordered events turns out to be harder than previously conjectured, while planning is easy under the same restrictions. Additionally, we show 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. Analyzing the partial decision procedure for the temporal projection problem that has been proposed by other authors, we notice that it fails to be complete for unconditional plans, a case where we have shown plan validation tractable.

ECAI Conference 1992 Conference Paper

On the Computational Complexity of Planning and Story Understanding

• Christer Bäckström
• Bernhard Nebel