# Structure And Complexity In Planning With Unary Operators

Ronen I. Brafman **brafman@cs.bgu.ac.il** Carmel Domshlak **dcarmel@cs.bgu.ac.il**
Department of Computer Science Ben-Gurion University P.O. Box 653, 84105 Beer-Sheva, Israel

## 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.

## 1. Introduction

One of the first well formulated problems addressed by AI researchers was the planning problem. Simply stated, it involves the generation of a sequence of system transformations, taken out of a given set of system transformations (called actions or plan operators**), whose** combined effect is to move the system from some given initial state into one of a set of desired goal states. The planning problem is known to be intractable in general (Chapman, 1987), and tractable algorithms exist for very restrictive **classes of problems only. This** discouraging fact has not deterred planning researchers. Indeed, many researchers believe that real-world problems have some properties, or structure**, that could be exploited, either**
implicitly or explicitly. In this paper we attempt to understand the relationship between structure and complexity in planning problems in which each **action changes the value of a**
single variable.

To study the relation between the structure and the complexity in a class of problems we must identify a set of parameters that characterize it. In **the case of planning, a number** of such problem properties have been studied in the past (which we review in more detail in Section 6). These properties have been mostly syntactical, i.e., they involve restriction on operators, e.g., the type and number of preconditions or effects that operators have. For