To define probabilistic and decision theoretic planning problems, we need to add support for probabilistic effects. The syntax for probabilistic effects is
Figure 1 shows an encoding in PPDDL of the “Bomb and Toilet” example described by Kushmerick, Hanks, and Weld (1995). The requirements flag :probabilistic-effects signals that probabilistic effects are used in the domain definition. In this problem, there are two packages, one of which contains a bomb. The bomb can be defused by dunking the package containing the bomb in the toilet. There is a 0.05 probability of the toilet becoming clogged when a package is placed in it, thus rendering the goal state unreachable.
|
The problem definition in Figure 1 also shows that initial conditions in PPDDL can be probabilistic. In this particular example, we define two possible initial states with equal probability (0.5) of being the true initial state for any given execution. Table 1 lists the state variables for the “Bomb and Toilet” problem and their values in the two possible initial states. Intuitively, we can think of the initial conditions of a PPDDL planning problem as being the effects of an action forced to be scheduled right before time 0. Also, note that the goal of the problem involves negation, which is why the problem definition declares the :negative-preconditions requirements flag.
PPDDL allows arbitrary nesting of conditional and probabilistic effects (see example in Figure 2). This feature is in contrast to popular encodings, such as probabilistic STRIPS operators (PSOs; Kushmerik et al., 1995) and factored PSOs (Dearden & Boutilier, 1997), which do not allow conditional effects nested inside probabilistic effects. While arbitrary nesting does not add to the expressiveness of the language, it can allow for exponentially more compact representations of certain effects given the same set of state variables and actions (Rintanen, 2003). Any PPDDL action can, however, be translated into a set of PSOs with at most a polynomial increase in the size of the representation. Consequently, it follows from the results of Littman (1997) that PPDDL, after grounding (that is, full instantiation of action schemata), is representationally equivalent to dynamic Bayesian networks (Dean & Kanazawa), which is another popular representation for MDP planning problems.
Still, it is worth noting that a single PPDDL action schema can represent a large number of actions and a single predicate can represent a large number of state variables, meaning that PPDDL often can represent planning problems more succinctly than other representations. For example, the number of actions that can be represented using m objects and n action schemata with arity c is m . nc, which is not bounded by any polynomial in the size of the original representation (m + n). Grounding is by no means a prerequisite for PPDDL planning, so planners could conceivably take advantage of the more compact representation by working directly with action schemata.
Håkan L. S. Younes