Plan Validation

Plan validation is an important part of the use of PDDL, particularly in its role for the competition. With approximately 5000 plans to consider in the competition in 2002, it can be seen that automation is essential. The validation problem is tractable for propositional versions of PDDL because plans are finite and can be validated simply by simulation of their execution. The issue is more complicated for PDDL2.1 because the potential for concurrent activity, possibly in the face of numeric change, makes it necessary to ensure that invariant properties are protected and that concurrent activity is non-interfering.

When durative actions are used there is a question over whether a plan should be considered valid if it does not contain all of the end points of the actions initiated in the plan. When an action is exploited in a plan for the effect it has at the end of its duration it is clear that that end point will be present in the plan, but when an action was selected for its start effect this is less clear. A match-striking action is performed for its start effect, not in order to have a burned out match at the end of a brief interval. It could be argued that, having obtained the desired start effect the end of the action is irrelevant and the plan can terminate (as soon as all goals are achieved) without ensuring that all initiated actions end safely. Indeed, the plan search process in Sapa [Do KambhampatiDo Kambhampati2001] can terminate whilst there are still queued events awaiting the advancement of time. However, it is possible to conceive of situations in which the end point of an action, incorporated only for its start effect, introduces inconsistencies in the plan so that its inclusion would make the plan invalid. In these cases it seems that plan validity could be compromised by ignoring end effects.

In order to avoid having to resolve these complexities, we have taken the view that a PDDL2.1 plan is valid only if all action start and end points are explicit within the plan. Having identified that this is the case we then proceed to confirm that all happenings within the plan are mutex-free.

Plan validation is decidable for domains including discretized and, under certain constraints, continuous durative actions because all activity is encapsulated with the durative actions explicitly identified by a plan. This makes the trace induced by a plan finite and hence checkable. We therefore observe that the validation problem for PDDL2.1 is decidable even when actions contain duration inequalities. This is because the work in determining how the duration inequalities should be solved has already been completed in the finished plan so validation of the plan can proceed by simulation of its execution, as is the case for PDDL plans. The problem is tractable for domains without continuous effects, but the introduction of continuous effects can, in principle, allow expression of domains with very complex functions describing numeric change [Howey LongHowey Long2002]. Under the assumption that continuous effects are restricted to description in terms of simple linear or quadratic functions, without any interactions between concurrent continuous effects, plan validity is tractable. The cost in practice is increased however, since it may be necessary to solve polynomials in order to check invariants. Validation of plans containing more complex expressions of change is being explored.

Although plan validity checking is tractable, there is a subtlety that arises because of the need to represent plans syntactically and the difficulties involved in expressing numbers with arbitrary precision. In principle, all of the values that are required to describe valid plans are algebraic (assuming we constrain continuous effects as indicated above), and therefore finitely representable. In practice, expecting planners to handle numbers as algebraic expressions seems unnecessarily complicated and it is far more reasonable to assume that numbers will be represented as finite precision floating point values. Indeed, the syntax we have adopted for the expression of plans restricts planners to expressing times as finite precision floating point values. With this constraint, and because of limitations on the precision of floating point computations in implementations of plan validation systems, it is necessary to take a more pragmatic view of the validation process and accept that numeric conditions will have to be evaluated to a certain tolerance. Otherwise, it can occur that there is no way to report a plan to the necessary degree of accuracy for it to have a valid interpretation under the semantics we defined in Section 8. In most cases, a plan that specifies time points to, for example, four significant digits, is a reasonable abstraction of the execution time activity that will be needed to control the flow system. No plan can specify time points absolutely precisely, so abstraction is forced upon the planner by the fact that it is working with models of the world and not the physical world itself. The problem, then, is one of the relationship between the theoretical semantics and the pragmatic concerns of automated validation.

Figure 18: The pragmatic mapping between semantics of plans and their validation by automated computational processes. The shaded area contains plans that cannot be interpreted within the theoretical semantics. It can be seen that a plan in this collection is indistinguishable from a meaningful plan when mapped to the syntactic side of the picture.

In Figure 18 this relationship is depicted in terms of what kinds of plans can be automatically validated. The left side of the picture describes the theoretical semantics, with the arrow indicating the link between plans and their interpretation under the theoretical semantics. For example, it is possible to construct a domain and problem for which a plan that requires an action to happen at time $\sqrt 2$ is a meaningful semantic object, but for which a plan that specifies that the action happen at time $1.41$ is not a meaningful semantic object because $1.41$ is not equal to $\sqrt 2$. These two plans are distinct, and only one is correct (under the assumed constraints). The right side of the picture depicts the pragmatic validation of syntactic plan objects. The two control plans, though distinct in the semantics, can map to the same syntactic object if we assume that the validation is subject to a tolerance of 0.01. These plans both map to the syntactic object in which $1.41$ approximates the value $\sqrt 2$. This syntactic plan can be validated using the pragmatic validation processes necessary for automatic validation of describable syntactic plans, which will check for validity subject to the tolerance of 0.01. The pragmatic constraints on the representations of plans, the expectations about representations of numeric values in planners and validators and their consequences are all reasonable assumptions given that the models against which we check validity are, in any case, abstractions, at some non-zero tolerance, of the world. In practice, it is a problem to accept plans at specified tolerance levels only in pathological cases, while arithmetic precision in computer representations of floats has an immediate and negative impact if one tries to take the stronger line that plans should only be accepted if they are strictly valid according to the formally precise evaluation of expressions.

Finally, there is an interesting philosophical issue that arises and is discussed by Henzinger and his co-authors henzinger1,henzinger2. It is, in fact, not possible to achieve exact precision in the measurement of time or other continuous numeric quantities. Henzinger et al. have considered this problem through the development of robust automata. Robust automata only accept a trace if there exists a tube of traces within a distance $\epsilon > 0$ of the original trace, all of which are acceptable by the original acceptance criteria. These are called fuzzy tubes indicating that time is fuzzily, rather than precisely, detectable. This idea offers a path to a formal semantics that is closer to defining plans that are robust to the imprecision in an executive's ability to measure time. Unfortunately, checking fuzzy tubes is intractable. We currently compromise by adopting an $\epsilon$ value, used as the tolerance in checking that numeric values fulfil numeric constraints during plan execution, to also represent the minimum separation of conflicting end points within plans. This is consistent with the idea that if the planner assumes that an executive is willing to abstract to the indicated tolerance level in the checking of preconditions for actions then it is unreasonable to suppose that a plan can make use of finer grained measurements in determining when actions should be applied. At the moment the value of $\epsilon$ is set in the validation process, and only communicated informally to planner-engineers, but it might be better to allow a domain designer to define an $\epsilon$ appropriate for use in the particular domain. There remain several issues concerning the correct management of the buffers during validation (particularly the usual problem concerning the transitivity of ``fuzzy closeness'') which are important issues for temporal reasoning as a whole and are not restricted to the planning context. We do not yet have solutions to all of these problems.