TLDR: This research paper introduces a method to transform PDDL axiom programs that allow negative occurrences of derived predicates (common in stratifiable logic programs) into a form compliant with the stricter PDDL 2.2 standard. The transformation involves introducing ‘stage axioms’ that track predicate derivation order, allowing negative conditions to be rephrased positively. While theoretically sound and polynomially bounded in size, its practical impact on planning systems, particularly regarding program size blow-up, requires empirical evaluation.
The Planning Domain Definition Language (PDDL) is a widely used standard for specifying tasks in classical artificial intelligence planning. A key feature of PDDL is the use of axioms, which can be thought of as rules that define new predicates (derived predicates) based on existing ones (basic predicates). These axioms allow for more complex and expressive descriptions of world states.
Traditionally, the PDDL standard has a specific restriction: negative occurrences of predicates within axiom bodies are only allowed for basic predicates, not for derived ones. This means you can’t directly say something like ‘if X is NOT a path, then Y is true’ if ‘path’ is a derived predicate. However, in academic literature, authors often relax this limitation, permitting negative occurrences of derived predicates as long as the set of axioms is ‘stratifiable’. Stratifiability essentially means that the axioms can be organized into layers, where predicates are fully defined in earlier layers before being negatively referenced in later ones, preventing circular definitions through negation.
The good news is that both the strict PDDL standard and the more flexible stratifiable approach can express the same range of queries, indicating that it should be possible to convert one form into the other. This research paper, titled “Eliminating Negative Occurrences of Derived Predicates from PDDL Axioms,” presents a method to achieve this transformation.
The Challenge of Negative Occurrences
Consider an example: defining a ‘path’ between two points based on existing ‘edges’. This is a derived predicate. Now, imagine you want to define ‘acyclic’ (meaning there are no cycles) as ‘there is no path from X to X’. Here, ‘path’ is a derived predicate, and it appears negatively (¬path). While logically sound in a stratifiable system, this is not permitted by the strict PDDL 2.2 standard.
The paper addresses this by building on existing work in fixed-point logic, adapting it to the specific context of PDDL axiom programs. The core idea is to ‘compile away’ these problematic negative occurrences.
The Transformation Process
The proposed transformation introduces a set of auxiliary predicates, referred to as ‘stage axioms’. These new predicates are designed to explicitly track the order in which other predicates are derived during the fixed-point computation process. Essentially, they keep track of when a certain fact becomes true. For instance, relations like ‘derived strictly before’ (≺), ‘derived before or at the same time’ (⪯), and ‘derived immediately before’ (◁) are introduced. There are also complement relations like ‘not derived strictly before’ (⊀) and ‘not derived before or at the same time’ (⪯̸).
By defining these stage-ordering relations through new axioms, the system can then replace any negative occurrence of a derived predicate, say ¬P(x), with an equivalent positive expression involving these new stage predicates, such as ¬x⪯̸P,P x. This effectively rephrases the negative condition into a positive one about the derivation stages, without changing the overall meaning of the program.
The transformation is applied iteratively, stratum by stratum, until all negative occurrences of derived predicates are eliminated. The final result is a PDDL axiom program that adheres to the PDDL 2.2 standard, where all derived predicates appear positively in axiom bodies.
Also Read:
- Navigating the Pitfalls of Concept Grounding in Neuro-Symbolic AI
- AwareCompiler: A New Approach to Smarter Program Optimization
Implications and Future Directions
While the transformation is theoretically sound and ensures equivalence, it does come with a ‘blow-up’ in the size of the resulting program. This blow-up is polynomial, meaning it grows predictably with the size of the original program. However, for practical planning systems that ‘ground’ (convert abstract rules into concrete instances), this increase in size, especially due to increased predicate arity and quantifier rank, could be significant.
Despite this, the transformation could be highly beneficial for certain planning approaches, such as relaxation heuristics (like those used in the FF planning system). These heuristics often struggle with negative conditions involving derived predicates, sometimes simplifying them in ways that lose accuracy. By converting these into positive forms, the heuristics could potentially achieve better approximations.
The authors acknowledge that an empirical evaluation is the natural next step to assess the practical feasibility of this transformation in real-world planning systems. This research provides a valuable theoretical tool for enhancing the expressive power and compilability of PDDL axioms. You can read the full paper here: Eliminating Negative Occurrences of Derived Predicates from PDDL Axioms.
