Introduction
Automated planning involves finding a sequence of actions to reach a goal state from an initial state. A fundamental challenge in this field is the state space explosion problem, where the number of possible states grows exponentially with the number of variables. While techniques like Partial Order Reduction (POR) and Factored Planning can mitigate this by exploiting operator independence, they often require the problem to be formulated in a "loosely coupled" manner. Many existing planning domains are "tightly coupled," where a single variable might encapsulate multiple independent logical components. This paper proposes an automated method to reformulate such problems by factorizing complex state variables into smaller, independent factors using Cartesian graph factorization.
Methodology: Automated Reformulation via Graph Factorization
The authors' approach centers on the Atomic Transition System (ATS) of a state variable. An ATS is a directed graph where nodes represent the possible values of a variable and edges represent the operators that cause transitions between these values.
The core innovation is the application of Cartesian graph factorization to these ATS graphs. In discrete mathematics, a graph can often be decomposed into a Cartesian product of smaller "prime" graphs. By identifying these factors, a single large-domain variable can be "unzipped" into multiple smaller-domain variables. For instance, a variable representing a position in a 2D grid can be factorized into two variables representing the x and y coordinates.
Once a variable is factorized, the original operators are mapped to new "factorized operators" that act on the new sub-variables. To ensure the validity of this transformation, the authors employ a "try-and-check" algorithm. This process verifies that the preconditions and effects of all operators in the planning problem remain consistent with the new factorized structure.
Key Insights: Isomorphism and Search Pruning
A critical theoretical result of this work is that the state space of the factorized problem is isomorphic to the original. This ensures that the underlying logic and reachability of the problem are preserved. However, the factorized representation explicitly exposes the independence of actions that was previously hidden.
This explicit independence is what allows search pruning techniques, such as sleep sets and strong stubborn sets, to be highly effective. These methods can now recognize that certain sequences of actions are permutations of each other and avoid redundant exploration. The paper proves that this can lead to exponential reductions in the number of nodes explored during the search process.
Empirical Results
The proposed method was evaluated on several domains, including a modified version of the IPC Visitall domain. In this domain, the task is to visit all cells in a grid. By factorizing the position variable, the independence of horizontal and vertical movement is exposed.
As shown in the results table, the factorized formulation leads to significant performance gains. For a grid of size 9, the number of nodes generated during an IDA* search with sleep sets dropped from approximately 2.5 million to just over 93,000. Correspondingly, the runtime was reduced from 14.4 seconds to a mere 0.6 seconds. These results empirically validate the theoretical promise of exponential speedups through automated factorization.
Conclusion and Future Work
While the results are promising, the current "try-and-check" approach is mathematically strict, requiring perfect consistency across all operators. This limitation prevents the technique from being applied to many standard IPC domains that exhibit "mostly independent" structures.
Future research could explore "relaxed factorizations" that only require isomorphism over the reachable portion of the state space rather than the entire product graph. Additionally, incorporating edge labels (action names) into the factorization algorithms could make the process more robust and widely applicable. The ultimate goal remains a fully automated, general-purpose implementation capable of optimizing a wide range of classical planning problems.
Summary updated