We complete the two-layered semantics presented in Figure 13 by showing how a plan is interpreted using Henzinger's notion of trace acceptance. This will conclude our presentation of the formal semantics of PDDL+.
Using Henzinger's syntax as a semantic model, we first map plans to traces and then rely on the interpretation of traces in terms of accepting runs. A plan is a set of time-stamped actions (Definition 3): neither events nor processes appear in the specification of a plan, even though the planned actions can initiate them. By contrast, since Henzinger does not distinguish between actions and events, a trace through a HA contains control switches which might be actions or events, together with explicit time intervals between them. Plans are finite, so we are concerned only with finite traces, but plans are normally subsets of traces, because of the missing events and the possible subdivision of intervals between actions into distinct subintervals of continuous activity.
We define a new structure, the plantrace, which contains the sequence of control switches corresponding to the actions in a plan being interpreted. We then map plantraces to sets of traces and proceed as indicated above.
In the semantics of Hybrid Automata actions that occur at the same time point are considered to be sequenced according to the ordering in which they are recorded in the trace. In reality, it is not possible to execute actions at the same time and yet ensure that they are somehow ordered to respect the possible consequences of interaction. In order to respect this constraint we introduce an additional element in the interpretation of plans: we consider the impact of ordering actions with the same time stamp in a plan in all possible permutations in order to confirm that there are no possible interactions between them. This motivates the following definition:
Henzinger defines trace acceptance for a trace of an HA. The definition is equivalent to the following:
A plan does not contain the transitions that represent events. For this reason, we make the following definition:
We can now use these definitions in the interpretation of plantraces. To avoid unnecessary multiplication of terms, we reuse the term accepted and rely on context to disambiguate which form of acceptance we intend in its use.
Finally, we return to plans and consider which plans are actually valid.
The definitions we have constructed demonstrate the relationship between plans, plantraces, traces and accepting runs. It can be observed that the definitions leave open the possibility that events will trigger in a non-deterministic way. This possibility arises when more than one event is applicable in the same state and the events do not commute. In this case, a non-deterministic choice will be made, in any accepting run, between all the applicable events. It is not possible for an action to execute before any of the events in such a state because of the time-slip process, but that process does not affect which of the events is applied. The non-deterministic choice between applicable events would allow PDDL+ to capture actions with non-deterministic outcomes. For the purposes of this paper we restrict our attention to event-deterministic planning instances.
We conclude by making some observations about the relationship between plans and accepting runs. Firstly, every valid plan corresponds to a collection of accepting runs for the labelled transition system that corresponds to the HA that is the interpretation of the planning instance. The only difference between accepting runs corresponding to a given plan is in the order in which events or actions are executed at any given single time point. In contrast, there can be accepting runs for which there is no corresponding plan. This situation arises when a domain admits accepting runs with actions occurring at irrational time points. It would be possible to extend plans to allow irrational timestamps for actions. The restriction to rationals is based on the fact that an explicit report of a plan generated by a planner can only make use of timestamps with a finite representation, so there are only countably many plans that can be expressed. The fact that there are uncountably many possible transitions based on the use of arbitrary real time values is of no use to us if a planner cannot express them all. A further point of relevance is the observation, discussed in [Gupta, Henziner, JagadeesanGupta et al.1997], that in constructing plans for execution it is of no practical interest to rely on measurement of time to arbitrary precision. Instead, it is more appropriate to look for plans that form the core of a fuzzy tube of traces all of which are accepted. In this case, the difference between rational and irrational timestamps becomes irrelevant, since any irrational value lies arbitrarily close to a rational value, so any robust plan can be represented using rational timestamps alone. We consider that this is an important direction for future exploration, where planning problems require an additional specification of a metric and a size for the fuzzy tube that the solution plan must define, with traces in the tube having a high probability of acceptance [Fox, Howey, LongFox et al.2005].
Derek Long 2006-10-09