Classical AI planning often faces a significant hurdle known as the "grounding bottleneck," where the exponential explosion of action instances overwhelms planners. This paper, presented at AAAI-2024, introduces the Enhanced Action Splitter (EAS), an automated technique to decompose complex action schemas into smaller, manageable micro-actions. By leveraging problem invariants and a novel lexicographic objective function, EAS significantly improves the performance of state-of-the-art planners, enabling them to solve previously intractable "hard-to-ground" problems and outperform specialized non-grounding planners.
The Grounding Bottleneck
Most modern AI planners rely on grounding—the process of instantiating schematic actions (e.g., move(?truck, ?from, ?to)) with all possible object combinations. In complex domains, this leads to a combinatorial explosion. For example, a single schema with multiple parameters can explode into millions of ground actions, causing planners to stall before the search even begins. While "action schema splitting" has been proposed to mitigate this by breaking large actions into chains of smaller ones, previous automated methods were often brittle, requiring manual hyperparameter tuning and sometimes degrading performance on simpler domains.
The Enhanced Action Splitter (EAS)
The authors propose EAS to address these limitations through three key innovations:
- Invariant-Aware Dependency Graphs: EAS utilizes "monotonicity invariants" (rules about what can be true in a state, such as a truck only being in one place at a time) to build more accurate dependency graphs. This ensures that micro-action chains are logically sound and avoid superfluous constraints.
- Lexicographic Objective Function: Instead of a single balancing parameter, EAS employs a priority-based objective function. It first ensures the number of ground actions remains below a manageable threshold (typically $10^6$) and then focuses on minimizing the branching factor of the resulting micro-actions to keep the search space small.
- Monte Carlo Search: To navigate the NP-complete space of possible action splits, EAS uses a Monte Carlo random walk with pruning, finding more efficient decompositions than standard greedy approaches.
Experimental Evaluation
The EAS framework was evaluated across a massive suite of benchmarks, including notoriously hard-to-ground domains (like Pipesworld-Tankage and Organic Synthesis) and 742 standard International Planning Competition (IPC) instances.
As shown in Figure 1, EAS provides a substantial coverage boost in hard-to-ground domains. For the Maidu planner (the IPC'23 winner), EAS increased the total solved instances from 224 to 240 out of 262 in these challenging sets. The results demonstrate that the invariant-aware approach allows planners to handle complexity that previously caused them to fail.
On the broader IPC benchmark set (Figure 2), EAS demonstrated remarkable robustness and universal applicability. It allowed standard grounding planners to outperform Powerlifted, a state-of-the-art planner designed specifically to avoid grounding altogether. For instance, Maidu with EAS solved 640 instances, significantly more than Powerlifted's 482. Crucially, EAS is minimalistic; it does not intervene unless it detects that the number of ground actions will be overwhelmingly high, preventing performance degradation on "easy" domains.
Conclusion and Future Work
EAS represents a significant step forward in making classical planners more robust to complex domain definitions. By automating the optimization of action schemas through invariant analysis and intelligent search, it removes a major barrier to applying planning technology to large-scale problems. Future work will focus on supporting actions with universally quantified effects and dynamically adjusting grounding thresholds based on hardware constraints.
Summary updated