Abstract
The manual creation of planning domain models is a significant bottleneck in automated planning. Domain learning addresses this by inferring models from execution traces. This paper provides a formal complexity analysis of learning STRIPS domains under the assumption that observed traces are "justified"—meaning every action in the trace is necessary to reach the goal. We distinguish between "well-justified" (no single action is redundant) and "perfectly justified" (no subset of actions is redundant) traces. Our analysis reveals a complexity spectrum from P to $\Sigma^P_2$-complete, highlighting how the definition of redundancy and the inclusion of expert constraints impact the difficulty of the learning task.
Introduction
In classical planning, an agent's ability to achieve goals depends on a precise domain model. The "knowledge acquisition problem" refers to the difficulty of manually specifying these models. Domain learning seeks to automate this by extracting STRIPS rules from sequences of states and actions. However, without constraints, many trivial or incorrect models can "explain" a trace. To ensure learned models are meaningful, researchers often assume that the input traces are non-redundant or "justified." This paper formalizes these notions and establishes the theoretical bounds of the resulting learning problems.
The Justification Framework
We consider grounded STRIPS domains where actions have preconditions, add lists, and delete lists. A trace is a sequence of actions that, when executed from an initial state, reaches a goal state. We define two levels of justification:
- Well-justified: A trace is well-justified if removing any single action results in an invalid plan or a failure to reach the goal.
- Perfectly justified: A trace is perfectly justified if no subsequence (subset of actions) can be removed while maintaining plan validity and goal achievement.
To represent these traces and the effects of actions, the authors utilize a symbolic notation to track state transitions and action requirements.
As shown in the legend above, symbols indicate whether a variable is present in a state, whether it is a precondition for an action, and whether it is added or deleted by that action. This notation is used to visualize the "most restrictive domain" ($δ_{max}$), which assumes the maximum possible preconditions and deletions consistent with the traces.
Complexity of Domain Learning
The core of the paper's contribution is the complexity analysis of finding a domain model that makes a given set of traces justified. A central concept is the most restrictive domain, which acts as a representative for all possible domains. The authors prove that if a trace is justified in any consistent domain, it must be justified in $δ_{max}$. This reduction allows the learning problem to be treated as a verification problem on a single model.
The complexity results vary significantly based on the justification criteria and the presence of background "expert knowledge" (constraints on the domain expressed as logical formulas):
| Scenario | Well-Justified (Single action) | Perfectly Justified (Subset) |
|---|---|---|
| Basic Learning | P | coNP-complete |
| With Expert Knowledge | NP-complete | $\Sigma^P_2$-complete |
The jump to $\Sigma^P_2$-completeness for perfectly justified traces with expert knowledge indicates that this problem is significantly harder than standard NP-complete problems, involving nested existential and universal quantifiers.
Conclusion
This work provides the first comprehensive complexity landscape for learning planning domains from non-redundant traces. The identification of the "most restrictive domain" as a representative model is a key theoretical insight that simplifies the analysis. Future work will extend these results to more expressive formalisms, such as those with conditional effects or partial observability, where the "knowledge acquisition problem" remains a critical challenge.
Summary updated