The Universal PDDL Domain

Patrik Haslum, Augusto B. CorrêaarXiv 2024 · OpenReview

TL;DR

This paper demonstrates that it's surprisingly easy to create a "universal" PDDL domain that can represent any propositional planning problem. This finding has significant implications, suggesting that for many problems, domain-specific planning strategies offer no inherent advantage over a general-purpose planner.

What Problem Does This Paper Address?

In Artificial Intelligence (AI) planning, a fundamental distinction exists between a "domain" and a "problem instance." A domain defines the general rules, actions, and predicates of a planning world (e.g., how blocks can be stacked), while a problem instance specifies the concrete objects, initial state, and goal for a particular scenario (e.g., stack block A on block B, starting with blocks C and D on the table). This distinction is crucial for techniques like generalized planning, which aims to find a single plan that works for all instances within a domain.

The authors tackle a question about the expressive power of PDDL (Planning Domain Definition Language), the standard language for specifying these domains and problems. Specifically, they investigate whether it's possible to define a PDDL domain that is so general it can encompass any propositional planning problem, regardless of its original domain. This relates to the idea of a "universal" domain.

Methods

The core of the paper is the construction of a "universal" PDDL domain. The simplest formulation involves two types: action and proposition. It features a single action schema, apply, which takes an action as a parameter. The preconditions and effects of this apply action are designed to dynamically mirror the preconditions and effects of the original action from the problem instance being represented.

To represent a specific planning problem instance (let's call it $\Pi$) within this universal domain, the authors propose a method:

  1. Objects: All ground actions and propositions from $\Pi$ are treated as objects in the universal domain.
  2. Predicates: For each ground action a and proposition p in $\Pi$, specific predicates like (pre a p), (add a p), and (del a p) are created.
  3. Initial State: Predicates (true p) are asserted for all propositions p that are true in $\Pi$'s initial state.
  4. Goal: The goal is expressed as a conjunction of (true p) for all goal propositions p in $\Pi$.

The paper also explores a STRIPS formulation of this universal domain, which uses a more complex set of actions to sequentially check preconditions and apply effects, mimicking the original action's behavior.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and does not evaluate on specific benchmark datasets.

Key Insights and Ideas

  • The "Universal" Domain is Trivial to Construct: The most striking insight is how straightforward it is to define a PDDL domain that can represent any propositional planning problem. This challenges the intuition that domains should capture specific problem structures.
  • Implications for Generalized Planning: The existence of such a universal domain suggests that for many problems, domain-specific planning strategies might not offer any significant advantage over a general-purpose planner. If any problem can be mapped to a universal domain, then a planner designed for that universal domain could, in principle, solve any problem.
  • The Trade-off: Grounding: While the universal domain is easy to define, instantiating it for a specific problem requires "grounding" all actions and propositions. This grounding process can lead to an exponential increase in the size of the problem representation, negating potential efficiency gains.
  • Limits of PDDL Expressiveness: The paper highlights that PDDL's fixed maximum predicate arity imposes a bound on the shortest plan length for any instance of a given domain. This implies that a truly universal PDDL domain that can represent any problem instance polynomially in size is impossible.

Key Results

  • The paper provides a concrete PDDL definition for a universal domain that can represent any propositional planning problem.
  • It demonstrates that this universal domain can be constructed with a single action schema and a limited number of predicates.
  • It shows that while a universal domain can be constructed, representing arbitrary problems within it can lead to an exponential blow-up in problem size due to grounding.
  • The authors prove that a lifted universal PDDL domain (where predicate arity is fixed) cannot represent all planning problems with a polynomial size increase, implying that some problems will always require exponentially larger representations in such a domain.

Limitations and Future Work

  • Polynomial Size Representation: A key limitation acknowledged is that while a universal domain can represent any problem, it cannot do so polynomially in size for all problems within the standard PDDL framework. This is due to the fixed predicate arity.
  • Expressive Formalisms: The authors suggest that more expressive formalisms, such as those allowing recursive terms (function symbols), might overcome the polynomial size limitation and potentially allow for polynomial-size universal domains.
  • Complexity of Restricted Domains: The paper opens up avenues for future research into characterizing classes of domains that do admit efficient generalized planning, perhaps by exploring descriptive complexity theory.
  • Practical Implications: While theoretically significant, the practical implications of the universal domain construction (especially the grounding cost) for real-world planning systems remain an area for further exploration.

Summary updated

Abstract

In AI planning, it is common to distinguish between planning domains and problem instances, where a "domain" is generally understood as a set of related problem instances. This distinction is important, for example, in generalised planning, which aims to find a single, general plan or policy that solves all instances of a given domain. In PDDL, domains and problem instances are clearly separated: the domain defines the types, predicate symbols, and action schemata, while the problem instance specifies the concrete set of (typed) objects, the initial state, and the goal condition. In this paper, we show that it is quite easy to define a PDDL domain such that any propositional planning problem instance, from any domain, becomes an instance of this (lifted) "universal" domain. We construct different formulations of the universal domain, and discuss their implications for the complexity of lifted domain-dependent or generalised planning.
BibTeX
@misc{haslum2024universal,
  author = {Patrik Haslum and Augusto B. Corrêa},
  title = {{The Universal PDDL Domain}},
  year = {2024},
  eprint = {2411.08040},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2411.08040},
}
Figure