TL;DR
This paper introduces "fact-alternating mutex groups" (fam-groups), a novel type of state invariant for classical planning that is computationally easier to infer than traditional mutex groups. The authors demonstrate that fam-groups can be effectively used for pruning planning tasks, leading to significant improvements in problem-solving performance.
What Problem Does This Paper Address?
Classical planning systems often struggle with the combinatorial explosion of states. State invariants, properties that hold true across all reachable states, can help by reducing the search space. Mutex groups are a type of invariant where at most one fact from a set can be true in any given state. While their importance is recognized, the theoretical analysis and efficient inference of mutex groups have been challenging. This paper addresses the difficulty of inferring general mutex groups by proposing a more restricted but computationally tractable variant, the fact-alternating mutex group, and demonstrating its practical utility.
Methods
The core contributions of this paper are:
- Theoretical Analysis: The authors establish that inferring maximum mutex groups is PSPACE-complete, while inferring maximum fam-groups is NP-complete. They also prove that fam-groups are a subset of general mutex groups.
- Novel Invariant Type: They define "fact-alternating mutex groups" (fam-groups) with a specific condition related to operator preconditions and effects. This definition leads to a more efficient inference process.
- ILP-based Inference Algorithm: A novel algorithm is presented for inferring maximal fam-groups using Integer Linear Programming (ILP). This algorithm is proven to be complete.
- Pruning Algorithm: A preprocessing algorithm is introduced that utilizes inferred fam-groups to remove irrelevant facts and operators that can lead to dead-end states, significantly improving planning performance.
Datasets
The authors evaluated their algorithms on domains from the optimal deterministic track of the International Planning Competition (IPC) 2011 and 2014. They excluded the "Citycar" domain due to its conditional effects but included domains with negative preconditions.
Key Insights and Ideas
- Computational Trade-off: By introducing a more restricted invariant (fam-groups), the authors achieve a significant reduction in computational complexity for inference, moving from PSPACE-complete to NP-complete. This is a crucial step for practical applications.
- "Alternating" Nature: The key insight behind fam-groups is their "alternating" property, where facts from a group appear and disappear in a predictable manner. This property is directly exploited for detecting dead-end states.
- Pruning Effectiveness: The experimental results strongly suggest that fam-groups, particularly their ability to identify dead-end operators, are highly effective for pruning planning tasks, leading to substantial improvements in problem-solving coverage.
- Fam-groups vs. h²-mutexes: While h²-mutexes (pairs of facts that cannot co-occur) are easier to infer and can form supersets of fam-group decompositions, fam-groups offer unique properties (like dead-end detection) that h²-mutexes alone do not provide.
Key Results
- Complexity: Maximum mutex group inference is PSPACE-complete; maximum fam-group inference is NP-complete.
- Pruning Performance: The proposed pruning algorithm (using fam-groups) significantly increased the number of solved tasks across various heuristics, achieving coverage improvements of up to 7% over other methods.
- FDR Translation: Fam-groups enabled more compact state encodings in Finite Domain Representation (FDR) translations, reducing the number of variables and memory footprint.
- Comparison: The authors' fam-group inference algorithm (fa) and its optimized version (fafd) showed competitive or superior performance compared to existing methods like FD (Helmert's algorithm) and h² heuristic, especially in terms of pruning effectiveness and FDR translation.
Limitations and Future Work
- Regression Invariants: Fam-groups inferred in regression tasks were found to be "very weak" and generally useless for pruning in that context. However, combining them with other methods (like Alcázar and Torralba's) showed promise.
- ILP Solver Dependence: The ILP-based inference algorithm's performance is dependent on the ILP solver. While complete, it can be computationally intensive.
- Future Work: The authors suggest that faster but incomplete methods for fam-group inference could be used to initialize their algorithm, potentially speeding up the process while maintaining completeness. They also note that the "alternating" property of fam-groups could be further explored for other planning-related tasks.
Summary updated