Complexity of action path finding with small precondition sets

Suppose that we are given a finite set of Boolean attributes and a set of actions defined on them. Every action has the effect of changing some attribute values and may also depend on further attribute values which are, however, not changed. The subset of attributes affected by an action is known as precondition. The goal is to find some sequence of executable actions that transform a given initial state into a desired target state. This type of problem appears, e.g., in robot motion planning. In this paper, we study cases of the problem where the precondition of every action only depends on a conjunction of terms with at most two attributes. We classify a number of cases as polynomial-time solvable or NP-complete. They amount to extended versions of some classic graph problems, among them topological orderings and perfect matchings. This appears to be the first systematic study of preconditions, despite the rich literature on many aspects of path finding in finite state spaces. A complete dichotomy of polynomial-time and NP-complete cases remains an open question.