Interpretation of Plans and Traces

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.

Definition 18   Plantrace Let $ H$ be a Hybrid Automaton, with h-event set $ \Sigma$ partitioned into two subsets, $ A$, the actions, and $ E$, the events. A plantrace of $ H$ is an element of the language $ (\mathbb{Q}_{> 0}   A^+)^*$.

A plantrace consists of sequences of one or more action control switches (denoted by $ A^+$), each following a single time interval which must be greater than 0 in length (0 length intervals are not allowed because the actions on either side of them would actually be occurring simultaneously). For example, the sequence $ \langle 3   a_0   a_1   a_2   2.7   a_3   a_4\rangle $ is a plantrace. Note that we have only allowed rational valued intervals between actions. This is to be consistent with the history of PDDL in which irrational time points have not been considered.

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:

Definition 19   Permutation equivalent plantraces Two plantraces $ \tau_{1}$ and $ \tau_{2}$, are permutation equivalent, written $ \tau_{1} \equiv \tau_{2}$ if $ \tau_1$ can be transformed into $ \tau_2$ by permuting any subsequence that contains only actions.

Definition 20   Plan projection The projection of a plan, $ P$, yields a plantrace $ proj(P)$ as follows. Assume that the plan (a sequence of pairs of times and action instance names) is given sorted by time:

\begin{displaymath}\begin{array}{ll}
proj(P) & = proj2(0,P)\\
proj2(t,\langle\r...
...\langle t_1-t,a\rangle + proj2(t_1,rest), otherwise
\end{array}\end{displaymath}

Plan projection is a functional description of the process by which plans are interpreted as plantraces. This process involves constructing the sequence of intervals between collections of actions that share the same time of execution, interleaved with the sequences of actions that occur together at each execution time. The most significant point to make is that where actions are given the same time for execution, the order in which they occur in the plantrace is determined simply by the (arbitrary) order in which they are listed in the plan. This does not affect the interpretation of the plan as we see in the following definition.

Definition 21   Interpretation of a plan The interpretation of a plan $ P$ for planning instance $ I$ is the set $ PT_P$ of all plantraces for $ H_I$ that are permutation equivalent to $ proj(P)$.

By taking all plantraces that are permutation equivalent to the projection of the plan we remove any dependency of the interpretation of a plan on the ordering of the actions with the same time stamp. Our objective is to link the validity of plans to the acceptance of traces, so we now consider trace acceptance.

Henzinger defines trace acceptance for a trace of an HA. The definition is equivalent to the following:

Definition 22   Trace Acceptance A trace, $ \tau = \langle a_{i} \rangle_{i = 1, \ldots ,n}$ where $ a_i \in \Sigma \cup \mathbb{R}_{\geq}$ is accepted by $ H$ if there is a sequence $ r = \langle q_{i} \rangle_{i = 0, \ldots ,n}$, where the $ q_{i}$ are states in the timed transition system $ S^{t}_{H}$ of $ H$, and: $ r$ is called an accepting run for $ \tau$ in $ H$ and, if $ q_{n} = (v,{\vec{x}})$, we say that it ends in state $ v$ with final values $ {\vec{x}}$.

A plan does not contain the transitions that represent events. For this reason, we make the following definition:

Definition 23   Trace abstraction A trace, $ \tau$, for a Hybrid Automaton with h-events partitioned into two sets, the actions $ A$ and the events $ E$, is abstracted to create a plantrace by removing all events in $ \tau$ and then replacing each maximal contiguous sequence of numbers with a single number equal to the sum of the sequence. Finally, if the last value in this modified trace is a number it is removed.

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.

Definition 24   Plantrace Acceptance Given a Hybrid Automaton, $ H$, with h-event set $ \Sigma$ partitioned into action $ A$ and events $ E$, a plantrace, $ \tau$, is accepted by $ H$ if there is a trace $ \tau^\prime$ that is accepted by $ H$ such that $ \tau$ is an abstraction of $ \tau^\prime$.

It is important to observe that this definition implies that checking for acceptance of a plantrace could be computationally significantly harder than checking for standard trace acceptance. This is because the test requires the discovery of events that could complete the gaps between actions in the plantrace. However, since the events are constrained so that if they are applicable then they are forced to be applied, provided we restrict attention to commuting events, the problem of determining plantrace acceptance does not involve searching through alternative event sequences. If reasonable constraints are placed on the kinds of event cascades that may interleave between actions, the problem of checking plantrace acceptance becomes straightforward.

Finally, we return to plans and consider which plans are actually valid.

Definition 25   Validity of a Plan A plan $ P$, for planning instance $ I$, is valid if all of the plantraces in $ PT_P$ are accepted by the Hybrid Automaton $ H_I$. The plan achieves the goal $ G$ of $ I$ if every accepted trace with an abstraction in $ PT_P$ ends in a state that satisfies $ G$.

The constraint that simultaneously executed actions are non-mutex is sufficient to ensure that it is only necessary to consider one representative from the set of all permutation equivalent plantraces in order to confirm validity of a plan.

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.

Definition 26   Event-deterministic Planning Instances A PDDL+ planning instance, $ I$, is event-deterministic if in every state in $ H_I$ in which two events, $ e_1$ and $ e_2$, are applicable, the transition sequences $ e_1$ followed by $ e_2$ and $ e_2$ followed by $ e_1$ are both valid and reach the same resulting state. In this case $ e_1$ and $ e_2$ are said to commute.

If every pair of events that are ever applicable in any state commute then the planning instance is event-deterministic. In general, deciding whether a planning instance is event-deterministic is an expensive operation because the entire state space must be enumerated. However, it is much easier to construct event-deterministic planning instances because it is only necessary to consider whether pairs of events will commute. In particular, non-mutex events will always commute.

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