Handling Derived Predicates

In IPC 4, PDDL was further extended with the addition of Derived Predicates [Hoffmann & Edelkamp 2005]. Derived Predicates, used in three of the competition domains, allow higher-level concepts to be recursively derived from other propositions. These derived predicates can then be present in the preconditions of actions, and allow higher-level concepts in the domain to be reasoned with. For example, in the BlocksWorld domain, the derivation rule for the `above' predicate is as follows:

(:derived (above ?x ?y)

(or (on ?x ?y) (exists (?z) (and (on ?x ?z) (above ?z ?y))))

)

Should a planner not include native support for derived predicates, it is possible to compile domains containing derived predicates into ``flattened'' domains that do not. However, it is not possible to do this without a super-polynomial increase in the size of the domain and the solution plan [Nebel et al. 2003]. At IPC 4, compiled versions of the domains that contained derived predicates were made available for competitors who could not support derived predicates. However, the sizes of the problems that could be compiled were restricted by the concomitant sizes of the PDDL files produced by the compilation process and the computational effort necessary to solve the compiled problems.

IPC 4 was the first planning competition to make use of derived predicates in its domains. As it has been shown that derived predicates cannot be reasoned about efficiently through compilation [Nebel et al. 2003] steps were taken to provide native support for them in Marvin.

It is also possible to compile derived predicates appearing in domains by adding actions to instantiate the derived predicates on an as-needed basis [Gazen & Knoblock 1997]. Using this compilation, the `above' derivation rule from the blocksworld problem described above would be compiled to the following action:

confirm_above ?x ?y


pre: (or (on ?x ?y) (exists (?z) (and (on ?x ?z) (above ?y ?z))))


add: (above ?x ?y)

If this is to be used as a domain compilation, each of the original actions in the domain must be extended to delete all of the `above' propositions, forcing the confirm_above actions to be used to re-achieve the `above' preconditions for any action that requires them. In this case, each action is given the additional effect:

(forall (?x ?y) (not (above ?x ?y)))

Although effective in STRIPS domains, it is not possible to use such a compilation for domains making use of negative preconditions as the re-derivation of derived predicates occurring as negative preconditions of actions is not enforced. For example, an action could be applied that modifies the `on' propositions, leading to a state from which a number of additional `above' properties could be derived. Deleting the `above' propositions is a necessary step, as the confirm actions should re-assert any derived predicate for any action that needs it. However, when (above ?x ?y) is deleted, (not (above ?x ?y)) is true, and can be used as an action precondition. To deal with this issue it is necessary to prevent any non-confirm actions from being applied until all possible derived predicates have been re-asserted; this prevents actions from being applied when a given `not above' is only temporarily true, i.e. whilst it has not yet been re-derived. To force the re-derivation of derived predicates, further dummy predicates and actions must be added to the domain. The necessary compilation results in a large increase in the size of the search space explored, and the additional dummy actions affect the usefulness of the relaxed-planning-graph heuristic.

The problems with using the Gazen & Knoblock compilation arise solely because, in its original form, it does not force all applicable confirm actions to be applied after each original action is applied. As such, if a planner generates the confirm actions internally and then deals with them appropriately, the compilation can still form the basis of an effective means for handling derived predicates.

To this end, when presented with a domain containing derived predicates, Marvin machine-generates the confirm actions and extends each (original) action to delete the derived predicates, as described. After each action is applied, all propositions that can be directly or recursively derived from the resulting state are instantiated by applying all applicable confirm actions. Along with avoiding an unwieldy compilation in domains with negative preconditions, handling the confirm actions internally in this manner provides performance improvements for two further reasons:

• As the confirm actions are automatically applied when appropriate, Marvin does not have to do search and perform heuristic evaluation to discover that the next action required will be a confirm action.
• Confirm actions are included alongside normal actions in the relaxed planning graph built for each state, but if used in the relaxed plan they do not contribute towards the heuristic value taken from its length, eliminating any noise they would otherwise add.