Abstract
Modern automated planning often struggles with goals involving existential quantification, typically relying on "compilation" techniques that lead to state-space explosion and heuristic blindness. This paper introduces ∃-STRIPS, a framework that handles existentially quantified variables natively. By integrating Constraint Satisfaction Problem (CSP) solvers directly into the heuristic evaluation, the proposed ∃S planner achieves significant improvements in scalability and search efficiency. Experimental results across several domains demonstrate that native existential reasoning outperforms standard compilation-based approaches in both coverage and node expansions.
Introduction
In automated planning, particularly within STRIPS or PDDL frameworks, goals often involve "choices." For instance, a goal might be to place a blue block on any red block, represented logically as $\exists z. \text{on}(\text{blue}, z) \wedge \text{red}(z)$. While standard PDDL supports this syntax, most modern planners cannot handle it directly. Instead, they employ a "compilation" trick, expanding the formula into every possible combination (e.g., "blue on red block A" OR "blue on red block B"). This approach suffers from two major drawbacks: exponential state-space explosion and "heuristic blindness," where the underlying problem structure is obscured, leading to suboptimal search decisions.
Methodology: The ∃-STRIPS Framework
The authors propose ∃-STRIPS, a native extension that preserves existential variables during the search process rather than compiling them away. The core innovation lies in the heuristic evaluation:
- Modified Relaxed Planning Graph (RPG): The standard RPG is extended to define satisfaction of an existential formula based on the existence of a valid variable substitution within a graph layer.
- CSP Integration: Determining the existence of such a substitution is treated as a Constraint Satisfaction Problem (CSP). The ∃S planner integrates the Gecode CP solver directly into its heuristic loop.
- The ∃S Planner: Built upon the Functional STRIPS planner FS0, ∃S leverages these techniques to provide more informed search guidance.
Experimental Evaluation
The approach was evaluated on four domain families designed to test existential reasoning:
- BW-PATTERN: BlocksWorld with color pattern goals rather than specific IDs.
- VERTEX-COLORING: Graph coloring encoded as action-less planning.
- GROUPING: Organizing blocks by color into unspecified locations.
- COUNTERS: Numerical constraints between variables.
Performance was compared against baselines using both compiled and manually reformulated encodings.
Key Results and Insights
Experimental data confirms that native existential reasoning is significantly more effective than compilation.
Search Efficiency and Coverage
As shown in the experimental results, the EF-FS configuration (the ∃S planner) consistently achieved the highest coverage across all tested domains. Notably, in the GROUPING and COUNT0 domains, ∃S required orders of magnitude fewer node expansions than propositional baselines (P-FF). This indicates that the native heuristic is far more "informed" about the true difficulty of the task.
Heuristic Informativeness vs. Overhead
While solving a CSP at every search node introduces computational overhead, the results suggest this is a worthwhile trade-off. The "aha moment" of the research is that solving a small, local CSP—though theoretically NP-complete—is often faster and provides better guidance than navigating a massive, flattened state space produced by compilation.
Conclusion
∃-STRIPS demonstrates that treating existential variables as "open choices" allows planners to reason about constraints directly. This bridges the gap between the Planning and Constraint Programming (CP) communities. Future work aims to reduce CSP overhead by utilizing multivalued variables and improving the "support extraction" logic for relaxed plans to further enhance plan quality.
Summary updated