Structure and Complexity in Planning with Unary Operators
Preprint
Abstract
Unary operator domains -- i.e., domains in which operators have a single effect -- arise naturally in many control problems. In its most general form, the problem of STRIPS planning in unary operator domains is known to be as hard as the general STRIPS planning problem -- both are PSPACE-complete. However, unary operator domains induce a natural structure, called the domain's causal graph. This graph relates between the preconditions and effect of each domain operator. Causal graphs were exploited by Williams and Nayak in order to analyze plan generation for one of the controllers in NASA's Deep-Space One spacecraft. There, they utilized the fact that when this graph is acyclic, a serialization ordering over any subgoal can be obtained quickly. In this paper we conduct a comprehensive study of the relationship between the structure of a domain's causal graph and the complexity of planning in this domain. On the positive side, we show that a non-trivial polynomial time plan generation algorithm exists for domains whose causal graph induces a polytree with a constant bound on its node indegree. On the negative side, we show that even plan existence is hard when the graph is a directed-path singly connected DAG. More generally, we show that the number of paths in the causal graph is closely related to the complexity of planning in the associated domain. Finally we relate our results to the question of complexity of planning with serializable subgoals.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- On Reasonable and Forced Goal Orderings and their Use in an Agenda-Driven Planning AlgorithmJournal of Artificial Intelligence Research, 2000
- Tractable plan existence does not imply tractable plan generationAnnals of Mathematics and Artificial Intelligence, 1998
- State-variable planning under structural restrictions: algorithms and complexityArtificial Intelligence, 1998
- Complexity, decidability and undecidability results for domain-independent planningArtificial Intelligence, 1995
- The computational complexity of propositional STRIPS planningArtificial Intelligence, 1994
- Acquiring search-control knowledge via static analysisArtificial Intelligence, 1993
- Planning in polynomial time: the SAS‐PUBS classComputational Intelligence, 1991
- Planning as search: A quantitative approachArtificial Intelligence, 1987
- Planning for conjunctive goalsArtificial Intelligence, 1987
- Macro-operators: A weak method for learningArtificial Intelligence, 1985