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

Christer BäckströmAAAI 2015 · DOI

Introduction

Automated planning is a fundamental challenge in artificial intelligence, involving the discovery of a sequence of actions to transition from an initial state to a goal state. In its general form, planning is PSPACE-complete, making it computationally prohibitive as problem instances scale. To address this, researchers seek "tractable fragments"—restricted versions of the problem that can be solved efficiently.

This paper, presented at AAAI 2015, significantly advances the theoretical understanding of tractability by relaxing previous constraints on state variable transitions. While earlier work established that planning is tractable when Domain-Transition Graphs (DTGs) are acyclic, this research proves that Fixed-Parameter Tractability (FPT) can be maintained even in the presence of cycles, provided specific structural conditions are met.

Problem Statement: Beyond Acyclicity

In the SAS+ planning framework, state variables change values according to transitions defined in a Domain-Transition Graph (DTG). Previous tractability results relied heavily on these DTGs being acyclic. However, real-world scenarios frequently involve reversible actions or cyclic processes—such as a vehicle moving between locations or a machine cycling through operational states.

The central question addressed by this paper is whether tractability can be preserved when DTGs contain cycles. The challenge with cycles is that they potentially introduce an infinite search space of walks, making it difficult to determine if a specific dependency between variables can be satisfied.

Methodology: Parameterized Complexity and Abstraction

The author utilizes Parameterized Complexity Analysis to identify specific problem features that, when bounded, allow for efficient computation. A problem is Fixed-Parameter Tractable (FPT) if its running time is exponential only in terms of small, fixed parameters and polynomial in the overall input size ($n$).

The Gap Lemma and Cycle Abstraction

The core theoretical breakthrough is Lemma 6 (The Gap Lemma). The author demonstrates that when matching transitions between dependent variables, there is a threshold of repetition. If a dependency can be satisfied by traversing a cycle a certain number of times ($q+2$), it can be satisfied for any number of traversals beyond that.

This allows for a "Cycle Abstraction" where walks are represented by a signature. Instead of tracking every possible iteration, the algorithm uses a bound ($p_{max}$) to represent the number of traversals, with a special symbol ($*$) denoting an unbounded number of cycles. This collapses an infinite search space into a finite set of values.

Structural Simplification

The paper employs two primary structural techniques:

  1. Condensation Graphs: Complex DTGs are simplified by contracting strongly connected components (SCCs) into single nodes, creating a Directed Acyclic Graph (DAG) of cycles (Cycle-DAGs).
  2. CSP Mapping: The planning problem is transformed into a Constraint Satisfaction Problem (CSP). By leveraging the properties of the Causal Graph—which maps dependencies between variables—the author shows that if the Causal Graph is a polytree, the resulting CSP can be solved efficiently.

Key Results

The primary contribution is Theorem 15, which establishes that planning is FPT when the Causal Graph is a polytree and the DTGs are cycle-DAGs (where every SCC is a simple cycle).

The complexity is defined by four parameters:

  • $d$: Maximum domain size.
  • $k$: Number of paths in the condensation of the DTG.
  • $c$: Number of contracted cycles along a path.
  • $p_{max}$: The upper bound for cycle traversals.

The resulting algorithm operates in $O((k^2(p_{max} + 2)^{2c})^2 \cdot poly(n))$ time. While the exponential component involves several parameters, in many practical domains, these values remain small, ensuring the "heavy lifting" remains polynomial relative to the problem size.

Discussion and Limitations

While this research expands the boundaries of tractable planning, it acknowledges several limitations:

  • Plan Existence vs. Generation: The proofs focus on deciding if a plan exists. In cyclic domains, the shortest plan might still be exponentially long, making plan generation a separate challenge.
  • Simple Cycles: The current results are restricted to "simple" cycles within SCCs. Many real-world problems involve more complex, intertwined cyclic structures.
  • Causal Graph Topology: The requirement for a polytree structure is restrictive, as many problems feature more complex dependency cycles (higher treewidth).

Conclusion

By introducing cycle abstraction and the Gap Lemma, this paper provides a rigorous mathematical foundation for planning in cyclic domains. These results not only broaden the theoretical landscape of FPT planning but also offer potential for developing more sophisticated heuristics for general-purpose planners by utilizing these tractable fragments as approximations.

Summary updated

BibTeX
@inproceedings{backstrom2015some,
  author = {Christer Bäckström},
  title = {{Some Fixed Parameter Tractability Results for Planning with Non-Acyclic Domain-Transition Graphs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2015},
  doi = {10.1609/aaai.v29i1.9648},
}
Figure