Beyond Forks: Finding and Ranking Star Factorings for Decoupled Search

Daniel Gnad, Valerie Poser, Jörg HoffmannIJCAI 2017 · DOI

TL;DR

This paper introduces new, more general methods for finding "star factorings" in planning problems, significantly expanding the applicability of decoupled search. They also propose a predictive portfolio approach that intelligently selects the best factoring for a given task, leading to improved overall performance.

What Problem Does This Paper Address?

Classical AI planning involves finding a sequence of actions to reach a goal state from an initial state. This can be computationally challenging due to the exponential growth of possible states. "Decoupled search" is a technique that tackles this by partitioning the problem's state variables into "factors" and searching over these factors separately. A specific type of decoupling, "star-topology decoupled search," assumes a particular structure where one "center" factor interacts with multiple "leaf" factors, but leaves don't interact directly. While this approach can be very effective, previous methods for identifying these star factorings were limited to simple structures like "forks" and "inverted-forks." This paper aims to overcome this limitation by developing more general strategies to find a wider range of star factorings, thereby enabling decoupled search in more complex problems and domains.

Methods

The paper introduces two novel strategies for finding "strict-star factorings," which are more general than previous ones:

  • Maximum Independent Set (MIS) based Factoring: This strategy leverages the causal graph of a planning task. It identifies a maximum independent set of variables in the causal graph, which forms the initial set of leaf factors. A post-processing step then aims to maximize "leaf flexibility" (the proportion of actions that only affect a leaf factor and its center, not other leaf factors) and ensure leaves are "mobile" (not frozen by dependencies).
  • Greedy Incident Arc Factoring (IA): This is a simpler, faster approach that prioritizes variables with a high number of incident arcs in the causal graph. These highly connected variables are moved to the "center" factor, while the remaining variables are partitioned into leaf factors based on weakly connected components.

Additionally, the authors propose a Predictive Per-Instance Self-Configuration method. This approach runs short sample searches with each identified factoring strategy. Based on features extracted from these sample searches (like heuristic improvement or number of expanded states), it selects the most promising factoring for the specific planning task.

Datasets

The experiments were conducted on standard benchmark suites from international planning competitions, covering both sequential optimal and satisficing planning tracks. No new benchmarks were introduced.

Key Insights and Ideas

  • Generalizing Star Factorings: The core insight is that previous methods for finding star factorings were too restrictive. By moving beyond simple fork/inverted-fork structures to more general "strict-star factorings," decoupled search can be applied to a much wider range of problems.
  • Leaf Flexibility Matters: The concept of "leaf flexibility" is crucial. A leaf factor with low flexibility (many actions also affecting the center) doesn't offer much benefit for decoupling. The MIS-based strategy actively tries to maximize this flexibility.
  • Complementarity of Strategies: The paper highlights that different factoring strategies (MIS, IA, and even older ones like fork/inverted-fork) are often complementary. No single strategy consistently outperforms others across all tasks.
  • Predictive Portfolio Effectiveness: The predictive self-configuration approach is highly effective. By intelligently choosing among multiple factoring strategies based on sample search performance, it achieves superior overall performance compared to using any single strategy.

Key Results

  • The new MIS and IA factoring strategies significantly expand the set of problems solvable by decoupled search, particularly in domains not previously amenable to this technique.
  • The predictive self-configuration (SC) method demonstrates high accuracy in selecting the best performing factoring for a given instance, leading to improved coverage.
  • While major improvements in coverage are rare, the new strategies often outperform standard search baselines when previous methods abstained.
  • The IA strategy is generally faster than the MIS strategy in finding factorings, though MIS can sometimes lead to better results.
  • Scatter plots show that for instances where both MIS and IA succeed, they often find similar factorings, but there are cases where one outperforms the other, especially in terms of search space size and runtime.

Limitations and Future Work

  • Abstinence: Both new factoring strategies, like previous ones, can abstain on certain instances (e.g., if they cannot find at least two mobile leaf factors). This limits the applicability of decoupled search in those cases.
  • General Star Factorings: The paper focuses on "strict-star factorings" which are identifiable from the causal graph. More general star factorings, not easily captured by the causal graph, are not explored due to their complexity.
  • Future Work: The authors suggest exploring other features for factoring strategies beyond causal graph connectivity and investigating more general star factorings. They also acknowledge that the observed limitations might be inherent to the structure of the benchmarks themselves, rather than solely due to the factoring methods.

Summary updated

BibTeX
@inproceedings{gnad2017beyond,
  author = {Daniel Gnad and Valerie Poser and Jörg Hoffmann},
  title = {{Beyond Forks: Finding and Ranking Star Factorings for Decoupled Search}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/602},
}
Figure