When is Temporal Planning Really Temporal?

1 Introduction

Although researchers have investigated a variety of architectures for temporal planning (e.g., plan-space: ZENO [Penberthy and Weld, 1994], VHPOP [Younes and Simmons, 2003]; extended planning graph: TGP [Smith and Weld, 1999], LPG [Gerevini and Serina, 2002]; reduction to linear programming: LPGP [Long and Fox, 2003]; and others), the most popular current approach is progression (or regression) search through an extended state space (e.g., SAPA [Do and Kambhampati, 2003], TP4 [Haslum and Geffner, 2001], TALPlan [Kvarnström et al., 2000], TLPlan [Bacchus and Ady, 2001], and SGPlan [Chen et al., 2006]) in which a search node is represented by a world-state augmented with the set of currently executing actions and their starting times.

Mausam and Daniel S. Weld Dept. of Comp. Sci. and Eng. University of Washington

Seattle, WA 98195

This architecture is appealing, because it is both conceptually simple and facilitates usage of powerful reachability heuristics, first developed for classical planning [Bonet et al., 1997; Hoffmann and Nebel, 2001; Nguyen et al., 2001; Helmert, 2004]. Indeed, SGPlan, which won the International Planning Competition's Temporal Planning Track in both 2004 and 2006, is such a progression planner.

There is an important technical hurdle that these temporal state-space planners need to overcome: each action could start at any of an infinite number of time points. Most of these planners avoid this infinite branching factor by a (seemingly) clever idea: restricting the possible start-time of actions to a small set of special time points, called decision epochs. Unfortunately, the popularity of this approach belies an important weakness - decision epoch planners are incomplete for many planning problems requiring concurrency [Mausam and Weld, 2006].

Seen in juxtaposition with their phenomenal success in the planning competitions, this incompleteness of decision epoch planners raises two troubling issues:

1. Are the benchmarks in the planning competition capturing the essential aspects of temporal planning?
2. Is it possible to make decision epoch planners complete while retaining their efficiency advantages?

In pursuit of the first question, we focused on characterizing what makes temporal planning really temporal - i.e. different from classical planning in a fundamental way. This leads us to the notion of required concurrency: the ability of a language to encode problems for which all solutions are concurrent. This notion naturally divides the space of temporal languages into those that can require concurrency (temporally expressive) and those that cannot (temporally simple). What is more, we show that the temporally simple languages are only barely different from classical, non-temporal, languages. This simple class, unfortunately, is the only class for which decision epoch planners are complete.

In pursuit of the second question, we show that the incompleteness of decision epoch planners is fundamental: anchoring actions to absolute times appears doomed. This leaves the temporal planning enterprise in the unenviable position of having one class of planners (decision epoch) that are fast but incomplete in fundamental ways, and another class of planners (e.g., partial order ones such as Zeno and VH- POP) that are complete but often unacceptably slow. Fortunately, we find a way to leverage the advantages of both approaches: a temporally lifted state-space planning algorithm called TEMPO. TEMPO uses the advantage of lifting (representing action start times with real-valued variables and reasoning about constraints) from partial order planners, while still maintaining the advantage of logical state information (which allows the exploitation of powerful reachability heuristics). The rest of the paper elaborates our findings.

2 Temporal Action Languages

Many different modeling languages have been proposed for planning with durative actions, and we are interested in their relative expressiveness. The TGP language [Smith and Weld, 1999], for example, requires that an action's preconditions hold all during its execution, while PDDL 2.1.3 allows more modeling flexibility. 1 We study various restrictions of PDDL 2.1.3, characterized by the times at which preconditions and effects may be 'placed' within an action. Our notation uses superscripts to describe constraints on preconditions, and subscripts to denote constraints on effects: L preconditions effects is the template. The annotations are:

• s "at-start"
• e "at-end"
• o: "over-all" (over the entire duration)

For example, Los,e is a language where every action precondition must hold over all of its execution and effects may occur at start or at end. PDDL 2.1.3 does not define, or allow, effects over an interval of time: o is only used as an annotation on preconditions.

Many other language features could be included as possible restrictions to analyze; however, most end up being less interesting than one might expect. For example, deadlines, exogenous events (timed literals), conditional effects, parameters (non-ground structures), preconditions required at intermediate points/intervals inside an action, or effects occurring at arbitrary metric points (as in ZENO) can all be compiled into Ls,o,e s,e [Smith, 2003; Fox et al., 2004]. In particular, an analysis of just Ls,o,e s,e is simultaneously an indirect analysis of these syntactically richer languages. Naturally these compilations can have dramatic performance penalties if carried out in practice; the purpose of such compilations is to ease the burden of analysis and proof. Of course, we also exclude some interesting language features (for the sake of simplicity), for example, metric resources and continuous change.

2.1 Basic Definitions

Space precludes a detailed specification of action semantics; thus, we merely paraphrase some of the relevant aspects of the PDDL 2.1.3 semantics for durative actions [Fox and Long, 2003].

Definition 1 (Actions) A model is a total function mapping fluents to values and a condition is a partial function mapping fluents to values. A transition is given by two conditions: its preconditions, and its effects.

1 PDDL 2.1.3 denotes level 3 of PDDL2.1 [Fox and Long, 2003].

An action, A, is given by a beginning transition begin(A), an ending transition end(A), an over-all condition o(A), and a positive, rational, duration δ(A).

Definition 2 (Plans) A plan, P = {s1, s2, s3, . . . , sn}, is a set of steps, where each step, s, is given by an action, action(s), and a positive, rational, starting time t(s). The makespan of P equals

A rational model of time provides arbitrary precision without Real complications.

Definition 3 (Problems) A problem, P = (A, I,G), consists of a set of actions (A), an initial model (I), and a goal condition (G).

Definition 4 (States) A (temporal) state, N, is given by a model, state(N), a time, t(N), and a plan, agenda(N), recording the actions which have not yet finished (and when they started).

A precise formulation of plan simulation is long and unnecessary for this paper; see the definition of PDDL 2.1.3 [Fox and Long, 2003]. Roughly, the steps of a plan, P = {s1, . . . , sn}, are converted into a transition sequence, i.e., a classical plan. Simulating P is then given by applying the transitions, in sequence, starting from the initial model (a classical state). Simulation fails when the transition sequence is not executable, simulation also fails if any of the over-all conditions are violated. In either case, P is not executable. P is a solution when the goal condition is true in the model that results after simulation.

Plans can be rescheduled; one plan is a rescheduling of another when the only differences are the dispatch times of steps. Let s′ = delay(s, d) be the result of delaying a step s by d units of time: t(s′ ) = t(s) + d (and action(s′ ) = action(s)). Similarly, P ′ = delay(P, d) is the result of delaying an entire plan: P ′ = {delay(s, d) : s ∈ P}. Hastening steps or plans is the result of applying negative delay. A step s has slack d in an executable plan P when P \ {s} ∪ {delay(s, -t)} is also an executable plan for every value of t between 0 and d. A step without slack is slackless, likewise, a plan is slackless when every step is slackless, that is, the plan is "left-shifted".

Definition 5 (Completeness) A planner is complete with respect to an action language L, if for all problems expressible in L, the planner is guaranteed to find a solution if one exists. A planner is optimal, with respect to language L and cost function c, if for all solvable problems expressible in L, the planner is guaranteed to find a solution minimizing c. A planner is makespan optimal if it is optimal with makespan as the cost function.

2.2 Required Concurrency

We now come to one of the key insights of this paper. In some cases it is handy to execute actions concurrently; for example, it may lead to shorter makespan. But in other cases, concurrency is essential at a very deep level.

Definition 6 (Required Concurrency) Let

P={s1, . . . , sn} be a plan. A step, s ∈ P, is concurrent 2 when there is some other step, s′ ∈ P, so that either t(s) ≤ t(s′ ) ≤ t(s) + δ(action(s)) or t(s′ ) ≤ t(s) ≤ t(s′ ) + δ(action(s′ )). A plan is concurrent when any step is concurrent, otherwise the plan is sequential. A solvable planning problem has required concurrency when all solutions are concurrent.

To make this concrete, consider the plan in Figure 1(d). The literals above the action denote its preconditions and below denote effects. Starting with G and R false, assuming A and B are the only actions, the problem of achieving G has required concurrency. That is, both of the sequential plans (A before B or vice versa) fail to be executable, let alone achieve G.

Definition 7 (Temporally Simple / Expressive) An action language, L, is temporally expressive if L can encode a problem with required concurrency; otherwise L is temporally simple.

2.3 Temporally Simple Languages

Theorem 1 Loe is temporally simple (and so is the TGP representation 3 ).

Proof: We will prove that Loe is temporally simple by showing that every concurrent solution of every problem in the language can be rescheduled into a sequential solution.

Fix a concurrent solution, P , of a problem P = (A, I, G). Without loss of generality, assume the step which ends last, say s ∈ P, is a concurrent step. 4 Since actions have effects only at end, the model that holds after simulating all of P \{s} is identical to the model that holds immediately before applying the effects of action(s) when simulating P. Since every precondition of an action holds over its entire duration, the preconditions of action(s) hold immediately prior to applying its effects, i.e., in the final model of P \ {s}. Therefore P ′ = (P \ {s}) ∪ {delay(s, δ(action(s)))} is an executable rescheduling of P. The final models in simulations of P and P ′ are identical, since both result from applying action(s) to the same model. By induction on the number of concurrent steps (note that P ′ has fewer concurrent steps), there is a rescheduling of P into a sequential solution. ✷

2 Actions execute over closed intervals in PDDL 2.1.3, so actions with overlapping endpoints are executing concurrently - at an instantaneous moment in time.

3 While the TGP representation is temporally simple, there is no perfect correspondence to any strict subset of PDDL 2.1.3, because they have slightly different semantics and hence different mutex rules. Loe is extremely close, however.

4 If not, consider the problems P ′ = (A, I, S) and P ′′ = (A, S,G) where S is the model that holds after simulating just past all the concurrent steps of P; the suffix of P is a sequential solution to the latter problem, and the argument gives a sequential rescheduling of the prefix of P solving the former problem.

Theorem 1 is interesting, because a large number of temporal planners (TGP, TP4 [Haslum and Geffner, 2001], HSP∗ [Haslum, 2006], TLPlan [Bacchus and Ady, 2001], and CPT [Vidal and Geffner, 2004]) have restricted themselves to the TGP representation, which is now shown to be so simple that essential temporal phenomena cannot be modeled! Note, for example, that the common motif of temporary resource utilization (Figure 1(d)) cannot be encoded in these representations. Yet some of these planners did extremely well in the last three International Planning Competitions. The reality: the majority of the problems in the Temporal Track do not require concurrency!

Note that the proof of Theorem 1 demonstrates a significantly stronger result than the theorem itself; not only does every problem in Loe have sequential solutions, but there is in fact a sequential rescheduling of every concurrent solution. This idea can be applied in reverse: problems in temporally simple languages can be optimally solved using classical techniques.

Theorem 2 Let P be a planning problem in a temporally simple subset of PDDL 2.1.3, and let P ′ be a corresponding STRIPS problem where durations are ignored and every action is collapsed into a single transition. 5

There is a linear-time computable bijection between the slackless solutions of P and the solutions of P ′ .

In particular, with the appropriate heuristics, optimal solutions to P can be found by solving P ′ instead. That is, STRIPS and temporally simple languages are essentially equivalent; though we do not delve into the details, one can show this correspondence in a formal manner using Nebel's framework of expressive power [Nebel, 2000]. 6

5 This transformation is performed by MIPS, LPG, and SGPlan: see those planners for details [Edelkamp, 2003; Gerevini and Serina, 2002; Chen et al., 2006].

Proof: We give a linear-time procedure for mapping solutions of the STRIPS problem to slackless solutions, which is the bijection of the theorem. However, we omit showing that the inverse is a linear-time computable total function on slackless solutions. We also omit proof for any case besides Loe ; the same basic technique (PERT scheduling) can be applied, with minor modifications, to every other case.

Consider some solution of P ′ , P ′ = A1,A2, . . . ,An. Associate with every literal, f=v, the time at which it was achieved, τ(f=v), initially 0 if v is the initial value of f, and -1 otherwise. Find the earliest dispatch time of each Ai, τ(Ai), by the following procedure 7 ; initializing τ(A1) to ϵ and i to 1:

1. For all (f=v) ∈ effects(Ai), if v ̸= argmaxv′τ(f=v′ ) set τ(f=v) = τ(Ai) + δ(Ai)
2. Set τ(Ai+1) = ϵ + max({τ(f=v) : (f=v) ∈ precond (Ai+1)} ∪ {τ (Ai) + δ(Ai) - δ(Ai+1)})
3. Increment i, loop until i > n

Then P = {si : action(si) = Ai and t(si) = τ(Ai)} is a slackless rescheduling of P ′ , preserving the order of the ends of actions, starting each action only after all of its preconditions have been achieved. In particular, P is a slackless solution. ✷

2.4 Temporally Expressive Languages

We have already seen one language, Lss,e , which can express problems with required concurrency (Figure 1(d)). Of course, the full language, PDDL 2.1.3, is also a temporally expressive language. It is no surprise that by adding at-start effects to Loe one can represent required concurrency, but it is interesting to note that merely shrinking the time that preconditions must hold to at-start (i.e. the language Lse ) also increases expressiveness. In fact, Lse is a particularly special temporally expressive language in that it exemplifies one of three fundamental kinds of dependencies that allow modeling required concurrency.

Theorem 3 Lse is temporally expressive.

The dual of Lse , Les , is an odd language - all preconditions must follow effects. Nonetheless, the language is interesting because it is also one of the three minimal temporally expressive languages.

Theorem 4 Les is temporally expressive.

It is not surprising that adding at-start effects (to a language allowing at-end effects) allows modeling required concurrency, because there is an obvious technique to exploit the facility: make a precondition of some action available only during the execution of another action. Figure 1(d) is a good example.

6 The basic idea is to compile the scheduling into the planning problem.

7 Technically, one must take ϵ to be some positive value by the requirements of PDDL 2.1.3. In a temporally simple language without a non-zero separation requirement (such as TGP) one can take ϵ as 0 instead.

What is surprising is that there is a different technique to exploit allowing effects at multiple times, one that does not even require any preconditions at all.

Theorem 5 Ls,e is temporally expressive.

Proof (of Theorems 3, 4, and 5): We prove that Lse , Les , and Ls,e are temporally expressive by demonstrating problems in each language that require concurrency. See Figure 1(a), (b), and (c), respectively. ✷

2.5 Temporal Gap

Figure 2 places the languages under discussion in the context of a lattice of the PDDL sub-languages, and shows the divide between temporally expressive and simple. We have already shown that Loe , our approximation to TGP, is temporally simple. Surprisingly, the simple syntactic criteria of temporal gap is a powerful tool for classifying languages as temporally expressive or temporally simple.

Roughly, an action has temporal gap when there is no single time point in the action's duration when all preconditions and effects hold together (which is easy to check via a simple scan of the action's definition). A language permits temporal gap if actions in the language could potentially have temporal gap, otherwise a language forbids temporal gap. We show that a language is temporally simple if and only if it forbids temporal gap. This makes intuitive sense since without a temporal gap, the duration of an action becomes a secondary attribute such as cost of the action. 8

8 This understanding of temporal expressiveness in terms of temporal gap is reminiscent of the "unique main sub-action restriction" [Yang, 1990] used in HTN schemas to make handling of task interactions easy. The resemblance is more than coincidental, given that temporal actions decompose into transitions in much the same way as HTNs specify expansions (see Section 2.1).

Definition 8 A before-condition is a precondition which is required to hold at or before at least one of the action's effects. Likewise, an after-condition is a precondition which is required to hold at or after at least one of the action's effects.

A gap between two temporal intervals, non-intersecting and not meeting each other, is the interval between them (so that the union of all three is a single interval). An action has temporal gap if there is a gap between its preconditions/effects, i.e., if there is

a gap between a before-condition and an effect, or a gap between an after-condition and an effect, or a gap between two effects.

Actions without temporal gap have a critical point: the (unique) time at which all the effects occur.

Theorem 6 A sub-language of PDDL 2.1.3 is temporally simple if and only if it forbids temporal gap.

Proof: We begin by showing that forbidding temporal gap is necessary for a language to be temporally simple.

Languages permitting a gap between a before-condition and an effect, a gap between an after-condition and an effect, or a gap between effects are super-languages of Lse , Les , or Ls,e , respectively. By Theorems 3, 4, and 5, such languages are temporally expressive. Therefore temporally simple languages require that, for every action, all before-conditions hold just before any effect is asserted, all after-conditions hold just after any effect is asserted, and that all effects are asserted at the same time. That is, a temporally simple language must forbid temporal gap.

For the reverse direction, i.e., the interesting direction, we show that any language forbidding temporal gap is temporally simple, by demonstrating that slackless solutions to any problem can be rescheduled into sequential solutions, a generalization of the proof of Theorem 1. Fix some slackless solution to some problem in a language forbidding temporal gap.

Consider the sequence of critical points in the slackless solution, along with the models that hold between them, i.e., M0, c1,M1, c2, . . . ,Mn-1, cn,Mn, where the ci are critical points and theMi are models. It is trivial to insert an arbitrary amount of delay between each critical point, lengthening the period of time over which each model holds, without altering them, by rescheduling steps. For example, multiplying each dispatch time by the maximum duration of an action achieves a sequential rescheduling preserving the sequence. For each critical point ci, all of that action's before-conditions hold in Mi-1 and all of its after-conditions hold in Mi, because the original plan is executable. Since those models are unaltered in the sequential rescheduling, the rescheduling is also executable, and thus a solution. ✷

Coming back to the space of languages, we have already noted that several popular temporal planners (e.g. TGP, TP4, HSP∗ , TLPlan, CPT) restrict their attention to temporally simple languages, which are essentially equivalent to STRIPS. The next section shows that most of the planners which claim to address temporally expressive languages, are actually incomplete in the face of required concurrency.

3 Decision Epoch Planning

The introduction showed that most temporal planners, notably those dominating the recent IPC Temporal Tracks, use the decision epoch (DE) architecture. In this section, we look in detail at this method, exposing a disconcerting weakness: incompleteness for temporally expressive action languages.

SAPA [Do and Kambhampati, 2003], TLPlan [Bacchus and Ady, 2001], TP4, and HSP∗a [Haslum and Geffner, 2001], among others, are all decision-epoch based planners. Rather than consider each in isolation, we abstract the essential elements of their search space by defining DEP. The defining attribute of DEP is search in the space of temporal states. The central attribute of a temporal state, N, is the world state, state(N). Indeed, the world state information is responsible for the success and popularity of DEP, because it enables the computation of state-based reachability heuristics developed for classical, non-temporal, planning.

We define DEP's search space by showing how temporal states are refined; there are two ways of generating children:

Fattening: Given a temporal state, N, we generate a child, NA, for every action, A ∈ A. Intuitively, NA represents an attempt to start executing A; thus, NA differs from N only by adding a new step, s, to agenda(NA) with action(s) = A and t(s) = t(N).

Advancing Time: We generate a single child, Nepoch , by simulating forward in time just past the next transition in the agenda: Nepoch=simulate(N, d+ϵ), where d=min{t : s ∈ agenda(N) and (t=t(s) or t=t(s) + δ(action(s))) and t ≥ t(N )}.

Our definition emphasizes simplicity over efficiency. We rely on simulate to check action executability; inconsistent temporal states are pruned. Obviously, a practical implementation would check these as soon as possible.

The key property of DEP is the selection of decision epochs, that is, the rule for advancing time. In order for DEP to branch over action selection at a given time point, time must have advanced to that point. Since time always advances just past the earliest transition in the agenda, DEP can only choose to start an action when some other action has just ended, or just begun. Conversely, DEP is unable to generate solutions where the beginning of an action does not coincide with some transition. Forcing this kind of behavior is surprisingly easy.

Theorem 7 DEP is incomplete for temporally expressive languages.

Proof: It suffices to show that DEP is incomplete for Lse , Les , and Ls,e to show that DEP is incomplete for all temporally expressive languages, by Theorem 6 (see Figure 2).

Figure 1(c) gives a Ls,e example which stumps DEPachieving the goal requires starting B in the middle of A, but there are no decision epochs available in that interval. DEP can solve the problems in Figure 1(a) and (b), but not minor modifications of these problems. For example, altering A to delete G2, in (a), forces B to start where there are no decision epochs. ✷

Theorem 8 DEP is complete for temporally simple sublanguages of PDDL 2.1.3, but not makespan optimal.

Proof: Figure 1(e) presents an example of makespan suboptimality; DEP would find the serial solution, but not the optimal (concurrent) plan shown. Completeness follows trivially from Theorem 2: temporally simple languages have sequential solutions, and DEP includes every sequential plan in its search space (consider advancing time whenever possible).

4 Generalized Decision Epoch Planning

As the example of Figure 1(c) shows, DEP does not consider enough decision epochs. Specifically, it makes the mistaken assumption that every action will begin immediately after some other action has begun or ended. In Figure 1(c), however, action B has to end (not begin) after A ends. Thus, it is natural to wonder if one could develop a complete DE planner by exploiting this intuition. In short, the answer is "No." but the reason why the effort fails is instructive, so we present the DEP+ algorithm below.

We generalize DEP to DEP+ by considering both beginning and ending an action at the current decision epoch. This would involve altering the past in the case of ending an action if the decision epoch were not sufficiently far in the future; to address this, we take our decision epochs as the current time plus the maximum duration of any action in the problem. Let Δ be the maximum duration, i.e., Δ = maxA∈A δ(A).

This raises a second issue: normally one would start the search at time 0, however, this would leave out the possibility of starting actions between 0 and Δ. We take the expedient of starting the search at time -Δ, and continue to rely on simulate to prune inconsistent temporal states, e.g., trying to start an action before time 0. In particular, the first decision epoch is at time 0, and attempting to end an action at the current decision epoch is not successful until the action would begin at or after time 0. 9

Fattening: For every action A, we create two children of N. N sA is analogous to NA in DEP- we commit to starting action A by adding a step s to agenda(N sA) with action(s)=A and t(s)=t(N sA) + Δ.

The latter, N eA, the essential difference from DEP, differs from N only in that agenda(N eA) contains a new step, s, with action(s)=A and t(s)=t(N eA) + Δ - δ(A).

Advancing Time: Nepoch is obtained from N by simulating to just after the first time where t(Nepoch) + Δ is the start or end of a step in agenda(Nepoch). Specifically, Nepoch=simulate(N, d + ϵ) where d=min{t|s∈agenda(N) and (t=t(s) or t=t(s) + δ(action(s))) and t ≥ t(N) + Δ}.

Theorem 9 DEP+ is incomplete for temporally expressive sub-languages of PDDL 2.1.3.

Proof: DEP+ cannot generate the plan in Figure 3, because there are no decision epochs in the interval where C must execute; the beginning of B is not a decision epoch, because B is only included after the current decision epoch moves to just after the end of A, that is, past the interval that C must execute within. Similar examples demonstrate that DEP+ is incomplete for all other expressive languages. ✷

9 This discussion has ignored the non-zero-separation requirement of PDDL 2.1.3, i.e., ϵ.

Furthermore, arbitrarily complex examples of chaining may be constructed; for example, split each action in Figure 3 into a million pieces. That is, trying to fix DEP+ by considering a denser set of decision epochs, or using some kind of lookahead, is a losing proposition.

DEP+ does improve on DEP, but, in just one way:

Theorem 10 DEP+ is makespan optimal for temporally simple sub-languages of PDDL 2.1.3.

Proof (Sketch): In a temporally simple language, by Theorem 6, every action has a critical point where all effects occur. Restrict child-generation so that the critical point of the action being added is always further in the future than the current decision epoch. Then every critical point eventually becomes a decision epoch. One can show that taking every critical point as a decision epoch is sufficient to allow the generation of every slackless solution. ✷

5 Temporally Lifted Progression Planning

The key observation about decision-epoch planning is that decisions about when to execute actions are made very eagerly - before all the decisions about what to execute are made. DEP attempts to create tight plans by starting actions only at those times where events are already happening. Unfortunately, for temporally expressive languages, this translates into the following two erroneous assumptions:

• *1 Every action will start immediately after some other action has started or ended.
• *2 The only conflicts preventing an earlier dispatch of an action, however indirect, involve actions which start earlier.

In developing DEP+, we noted the first flaw, and attempted to address it by allowing synchronization on the beginnings of actions as well as their ends. However, there does not appear to be any (practical) way of addressing the second flaw within the decision-epoch approach. One must either define every time point to be a decision epoch (branching over dense time!) or pick decision-epochs forwards and backwards, arbitrarily far, through time (as in LPGP [Long and Fox, 2003]).

Instead, we develop a complete state-space approach, by exploiting the idea of lifting over time: delaying the decisions about when to execute until all of the decisions about what to execute have been made. Note that VHPOP [Younes and Simmons, 2003] also lifts over time - we take a different approach that allows us to preserve state information at each search node.

Definition 9 A lifted temporal state, N, is given by the current temporal variable, τ(N), a model, state(N), a lifted plan, agenda(N), and a set of temporal constraints, constraints (N ).

We retain the terminology used in DEP, and DEP+, to highlight the similarity of the approaches, despite the differences in details which arise from lifting time. For example, the agenda in a lifted temporal state is different from that in a (ground) temporal state - we replace exact dispatch times (t()) with temporal variables (τbegin()), and impose constraints through constraints(N). In fact, we associate every step, s, with two temporal variables: τbegin(s) and τend(s). All the duration constraints τend(s) - τbegin(s) = δ(action(s)) and mutual exclusion constraints τx(s)̸=τy(t), for mutually exclusive transitions x(action(s)) and y(action(t)) (x and y are each one of begin or end), are always, implicitly, part of constraints().

The aspect of lifted and ground temporal states that remains identical is the current world state, state(N). In both cases this maps every fluent to the value it has at the current time. In particular, this is exactly the information needed to leverage the state-based reachability heuristics developed for classical planning. With respect to lifted temporal states, TEMPO is a complete and optimal state-space temporal planning algorithm, given by the following child-generator function:

Fattening: Given a lifted state, N, we generate a child, NA, for every action, A ∈ A. As before NA represents starting A; we add a step s to agenda(N ′ ) with action(s) = A. In addition, we add "τbegin(s) ≥ τ(N)" to constraints(N ′ ). Unlike before, we immediately simulate: NA=simulate(N ′ , τbegin(s)). In particular, everything in agenda(NA) has already started.

Advancing Time: For every s∈agenda(N), we generate a child, N A epoch , where A=action(s). Note that A has already started; this is a decision to end A. Specifically, we add "τend(s) ≥ τ(N)" to constraints(N ′ ) and then simulate: N A epoch =simulate(N ′ , τend (s))

In essence, TEMPO is searching the entire space of sequences of transitions (beginnings and endings of actions), in prefix order. That is, every search state corresponds to the unique sequence of transitions that, if (assigned dispatch times and) executed, result in the given (lifted) temporal state. Of course, just before terminating, TEMPO must actually pick some particular assignment of times satisfying constraints(N) (for a state, N, satisfying the goal) in order to return a ground plan. Since constraints(N) will, among other things, induce a total ordering, this will not be very difficult. So it should not be very surprising that TEMPO is guaranteed to find solutions - if there is a solution, it has a sequence of transitions, and TEMPO will eventually visit that sequence, and find an assignment of times.

Theorem 11 TEMPO is complete for any temporally expressive (or simple) sub-language of PDDL 2.1.3, moreover, makespan optimal.

Proof: Every potential permutation of beginnings and endings of actions can be generated by appropriate decisions at fattening and advance-time choice-points (if not pruned by simulate()). The transition sequence of any concurrent plan is one such permutation, in particular a makespan optimal solution defines one such permutation. Pruning occurs if simulate() fails at a search node, i.e., a precondition is violated. No descendant of this search node can ever change the state where the precondition is evaluated: every descendant would likewise fail to be executable. Solutions are, of course, executable, so TEMPO does not prune any solutions. It follows that TEMPO is complete; makespan optimality follows from the fact that the appropriate transition sequence is in the search space, and the optimal dispatch is easy to find. ✷

6 Discussion and RelatedWork

It should be noted that our analysis of temporal expressiveness was done at the language level, and most of our conditions for expressiveness were necessary rather than sufficient. In particular, it is obviously possible to write a domain in a temporally expressive language that does not require concurrency (or write a problem for a temporally expressive domain that does not require concurrency). For example, the (temporal) Rovers domain, contains actions with temporal gap. Nonetheless, Rovers is a temporally simple domain. This is not a contradiction of Theorem 6 - any language permitting the Rovers encoding also contains other domains and problems that require concurrency. It would be interesting to catalog domain/problem level necessary/sufficient conditions for required concurrency.

Several planners have considered using classical techniques augmented with simple scheduling to do temporal planning, for example, SGPLAN, MIPS, LPG-td, and CRIKEY [Chen et al., 2006; Edelkamp, 2003; Gerevini and Serina, 2002; Halsey et al., 2004]. That is, the planners only consider sequential solutions, but reschedule these using the temporal information. Actually, CRIKEY does not quite fit this classification; CRIKEY attempts to do classical planning as much as possible, and switches to a TEMPO like search to handle actions that could easily lead to required concurrency (envelope actions). Modulo unimportant details, an equivalent perspective on CRIKEY is as an implementation of TEMPO that strives to cut down the number of transition sequences actually considered by identifying actions where it is safe to immediately apply the ending transition after the beginning transition (non-envelope actions). Unfortunately, our preliminary investigation reveals that the pruning that results is not completeness-preserving; the conditions used to classify actions as safe are too generous.

7 Conclusion

Motivated by the observation that the most successful temporal planners are incomplete [Mausam and Weld, 2006], this paper presents a detailed examination of temporal planning algorithms and action languages. We make the following contributions:

• We introduce the notion of required concurrency which divides temporal languages into temporally simple (where concurrency is never required in order to solve a problem) and temporally expressive (where it may be) classes. Using the notion of temporal gap, we then decompose subsets of PDDL 2.1.3 into a lattice which distinguishes the expressive and simple sub-languages.
• We show that temporally simple languages are essentially equivalent to STRIPS in expressiveness. Specifically, we show a linear-time computable mapping into STRIPS, with no increase in the number of actions. Thus, any classical planner may be used to generate solutions to temporally simple planning problems!
• We prove that a large class of popular temporal planners, those that branch on a restricted set of decision epochs (e.g., all state-space planners like SAPA, SGPlan), are complete only for the temporally simple languages. In fact, there exist problems even in simple languages for which these planners are not optimal. Since these decision-epoch planners won the temporal track of the last three planning competitions, we question the choice of problems used in the competitions. 10
• On a constructive note, we sketch the design of a complete state-space temporal planning algorithm, TEMPO, which we hope will be able to achieve high performance by leveraging the heuristics that power decision epoch planners.

Acknowledgments

We thank J. Benton, Minh B. Do, Maria Fox, David Smith, Sumit Sanghai, and Menkes van den Briel for helpful discussions and feedback. We also appreciate the useful comments of the anonymous reviewers on the prior draft. This work was supported by NSF grants IIS-0307906 and IIS-308139, ONR grants N00014-021-0932, N00014-06-1-0147, and N00014-06-1-0058, the Lockheed Martin subcontract TT0687680 to ASU as part of the DARPA Integrated Learning program, and the WRF/TJ Cable Professorship.