Generating SAS+ Planning Tasks of Specified Causal Structure

Michael Katz, Junkyu Lee, Shirin SohrabiSOCS 2023 · OpenReview

Abstract

Recent advances in data-driven approaches in AI planning demand increasing volumes of planning tasks, yet the supply remains limited by the manual effort required to create International Planning Competition (IPC) benchmarks. This work introduces a novel method for generating synthetic SAS+ planning tasks with any user-specified causal graph structure. By bridging the gap between theoretical complexity analysis and empirical benchmarking, we provide a scalable algorithm for constructing random tasks that mimic real-world domains or target specific theoretical structures. Evaluation with state-of-the-art optimal planners demonstrates that these generated benchmarks are non-trivial and reveal performance profiles distinct from standard IPC sets, highlighting their utility for robust planner evaluation.

1. Introduction

AI planning research relies heavily on benchmarks from the International Planning Competitions (IPCs). However, these are mostly hand-crafted by experts, leading to a limited supply of diverse tasks. As data-driven approaches—such as using machine learning for planner selection—gain traction, the need for massive, varied datasets grows.

Crucially, a planner's performance is often tied to the causal structure of a task: a directed graph showing how variables depend on one another. For example, in a logistics task, a package's location depends on the truck's location. Existing random generators produce limited structures, making it difficult to study specific theoretical "islands of tractability" or to generate tasks that mimic the complexity of real-world domains.

2. Methodology: Layer-Based Task Generation

The core contribution is a layer-based construction algorithm designed to generate SAS+ planning tasks from a target causal graph $G$. Instead of randomizing every element, the algorithm uses $G$ as a structural blueprint to ensure the resulting task adheres to specific dependency constraints.

  1. Variable Initialization: The algorithm assigns domain sizes to variables and sets an initial state.
  2. Layered Action Construction: It builds actions in layers, effectively constructing a "relaxed planning graph" in reverse. For each action, it ensures that any dependencies created (edges in the causal graph) are already present in the target graph $G$.
  3. Goal Selection: The goal is chosen from the final layer of facts to ensure the task is "delete-relaxed solvable"—meaning a plan is guaranteed to exist if negative side effects of actions are ignored.
A transportation planning task and its corresponding causal graph and relaxed planning graph layers.

The algorithm can also "mimic" existing IPC domains. By extracting the causal graph and parameters (like domain sizes) from a real task, it can generate an arbitrary number of new, structurally similar instances.

3. Benchmark Datasets

We released two major benchmark sets generated by this tool:

  • Structured Benchmark Set: 26 collections (30 instances each) based on well-studied graph families like chains, trees, stars, and directed acyclic graphs (DAGs).
  • IPC-based Benchmark Set: 42 collections (totaling 1204 instances) that mimic the structure of classic IPC domains like Blocksworld, Elevators, and Logistics.
A sample complex causal graph structure (f) used to generate the structured benchmark set.

4. Key Results and Planner Sensitivity

Testing with state-of-the-art optimal planners (such as Scorpion and SYMBA) showed that the generated tasks are far from trivial. Out of 780 "structured" tasks, 232 remained unsolved by any planner within a 30-minute limit.

Furthermore, the experiments revealed significant planner sensitivity to causal structure. A planner that excels on "star" graphs might fail on "chains," and relative performance rankings shifted significantly between the IPC-mimicking set and the original IPC benchmarks. For example, the Scorpion planner ranked first on the generated sets but fourth on the actual Autoscale IPC set. This proves that synthetic tasks can reveal different performance profiles and prevent planners from "overfitting" to standard benchmarks.

5. Conclusion and Future Work

By treating causal structure as a "control knob," researchers can now target specific complexity classes or create challenging instances by increasing edge density. While the current method ensures delete-relaxed solvability, future work aims to generate tasks with guaranteed full SAS+ solvability and to extend the method to "lifted" PDDL representations. The benchmark sets and the task generator code are publicly available at https://github.com/IBM/fdr-generator.

Summary updated

Abstract

Recent advances in data-driven approaches in AI planning demand more and more planning tasks. The supply, however, is somewhat limited. Past International Planning Competitions (IPCs) have introduced the de-facto standard benchmarks with the domains written by domain experts. The few existing methods for sampling random planning tasks severely limit the resulting problem structure. In this work we show a method for generating planning tasks of any requested causal graph structure, alleviating the shortage in existing planning benchmarks. We present an algorithm for constructing random SAS+ planning tasks given an arbitrary causal graph and offer random task generators for the well-explored causal graph structures in the planning literature. We further allow to generate a planning task equivalent in causal structure to an input SAS+ planning task. We generate two benchmark sets: 26 collections for select well-explored causal graph structures and 42 collections for existing IPC domains. We evaluate both benchmark sets with the state-of-the-art optimal planners, showing the adequacy for adopting them as benchmarks in cost-optimal classical planning. The benchmark sets and the task generator code are publicly available at https://github.com/IBM/fdr-generator.
BibTeX
@inproceedings{katz2023generating,
  author = {Michael Katz and Junkyu Lee and Shirin Sohrabi},
  title = {{Generating SAS+ Planning Tasks of Specified Causal Structure}},
  booktitle = {SOCS},
  year = {2023},
  url = {https://openreview.net/forum?id=zrxwHkpjd3},
}
Figure