Resource Temporal Networks: Definition and Complexity

1 Introduction

Historically, Artificial Intelligence Planning focuses on ab­ solute changes (for instance change of the truth value of a predicate), conditions on the state of the world and symbol­ ical precedences between operations whereas Scheduling fo­ cuses on relative changes of the world (resource consump­ tion or production) and numerical time. Recent advances in both fields have enlarged their relative ambition: time and resources are increasingly being studied by the AI Planning community whereas conditions and absolute changes are nec­ essary to express complex scheduling problems involving for example alternative recipes or complex conditions and ef­ fects on the level of resources. This paper introduces and analyzes the computational complexity of a formalism that mixes on the same fluent the ingredients of AI Planning (ab­ solute changes, conditions) and the ones of Scheduling (rela­ tive changes, numerical time). There has been some recent work on the decidability of planning with numerical state variables [Helmert, 2002] but to the best of our knowledge, no computational complexity study has been published that analyzes a complex but realistic and useful fragment of the overall framework of planning with time and numerical state variables. This paper is a step in this direction.

2 Resource Temporal Networks

2.1 Definition

Definition 1 (Resource) A resource is a numerical fluent whose value can vary over time. The value of this fluent at date t is called the resource level at date t and is denoted l(t).

In this paper, we focus on time and resource levels belong­ ing to a dense set (rational numbers): t E Q, l(t) E Q. Al­ though the framework can be extended to handle continuous changes, we only consider discrete changes.

Definition 2 (Resource Statements) We define the follow­ ing statements on a resource where t, ts and te denote vari­ able time-points and q some constant in Q:

• An absolute change is a statement denoted A(q, t) stat­ ing that because of this change at date t, the level of the resource changes from a current Ievell to q.
• A relative change is a statement denoted R( q, t) stat­ ing that because of this change at date t, the level of the resource changes from current level l to l + q. This corresponds to a production of lql units if q > 0 or a consumption oflql units if q < 0.
• A lower-than condition is a statement denoted L(q, t 8 , te) stating that the level of the resource must remain lower than or equal to q over time interval [ts, te)·
• A greater-than condition is a statement denoted G(q, t 8 , te) stating that the level of the resource must remain greater than or equal to q over time interval [ts, te)·

A,n,C,Q respectively denote the sets of absolute, rela­ tive changes, lower-than and greater-than conditions. If x E AU n is a resource change, we denote t( x) the time-point of x and q(x) the resource quantity involved in x. If x E £ U Q is a condition, we denote ts (x) the start time-point of x, te(x) its end time-point and q(x) the resource quantity involved in x. Note that the above resource statements also allow for expressing equal conditions of the form E(q, t 5 , te) stating that the level of the resource remains equal to q over the time interval [t 8 , te) as the conjunction of a lower-than condition L(q, t 8 , te) and a greater-than condition G(q, t 8 , te)· The set of equal conditions is denoted £. Resource statements are the basic ingredients for defining Resource Temporal Net­ works (RTNs). Informally, an RTN represents a set of pos­ sible evolutions of a given numerical variable (the level of the resource) over time.

Definition 3 (Resource Temporal Network) A resource temporal network (RTN} is a tuple (T, A , R , £ , Q, N) where: Tis a set of time-point variables, A, n, £and Q respectively denote a set of absolute, relative changes, lower-than and greater-than conditions ref erring to time-points in T. N is a Temporal Network using the formalism STW defined in [Gerevini and Cristani, 1997]l on the time-points ofT.

In this paper, for simplicity reasons, we focus on decision problems and reasoning involving a unique resource. Our framework can naturally be extended toward (1) parametrized resources of the form Res(y) where y is a variable parameter describing which resource a given resource statement applies and (2) handling variable quantities q in resource statements. Those extensions are out of the scope of the paper.

Definition 4 (Instantiation of an RTN) An instantiation of an RTN is a function a : T--+ Q.

It is to be noted that in this paper, we assume that all the re­ source statements are known and the only decision variables of an RTN are the time-points in T. We do not handle, at this point, the complete AI Planning problem of generating an RTN given a partial RTN and a set of operators described as RTNs.

Definition 5 (Time-consistent instantiation) An instantia­ tion a is said to be time-consistent iff a is consistent with the STW N.

Computing a time-consistent instantiation of an RTN can be done in O(n 3 ) [Gerevini and Cristani, 1997]. We now de­ fine the notion of resource-consistent instantiation. In the def­ inition below, conditions [1] and [2] ensure that in a resource­ consistent instantiation, two absolute changes assigning dif­ ferent levels cannot be simultaneous and an absolute change cannot be simultaneous with a relative change. The ratio­ nale for this semantics is that, as in [Fox and Long, 2002], we allow simultaneity only for pair of changes (x, y) that are commutative, that is such that applying x just after y leads to the same level as applying y just after x . Given a date T, point [3] defines iT( T ), the last date before T at which an absolute change occurred and ij( T) the resource level assigned by such an absolute change. Note that ij( T) can be defined without ambiguity because two absolute changes assigning different levels cannot be simultaneous. Equation [4] defines the pro­ file of the resource level over time. Conditions [5] and [6] state that this profile must satisfy the lower-than and greater­ than conditions.

Definition 6 (Resource-consistent instantiation) An in­ stantiation a is said to be resource-consistent if! the following conditions are satisfied:

• V(x, y) E A 2 ,q(x) =/:. q(y):::} aot(x) =/:. aot(y) [1}
• V(x, y) E A X n ,aot(x) =I= aot(y) [2}

1 This formalism allows for both the representation of metric con­ straints t - t' ::; r E Q and unequations t -:f. t'.

• VT E Q, let 's define iT( T) and ij( T) as follows [3}
• if3x E A,aot(x)::; T, then:
• iT(T) = m a x xEA,o-ot(x )$;T a o t(x )
• ij(T) = q(x ) with x E A, a o t(x ) = iT(T)
• otherwise, iT(T) = -oo, ij(T) = 0.

There exists a function l,. ( T) : Q ~---> Q such that :

• l,.(T) = ij(T) + L x E'R,a(T) <o-ot(x)$T q(x ) [4}
• Vx E £ , VT E [a ot 8 (x ), aote(x )), l,.(T) ::; q(x ) [5}
• Vx E Q, \IT E [aot 8 (x ), aote(x )) , l,.(T) ~ q(x) [6}

Definition 7 (Solution of a RTN) A solution to an RTN is an instantiation a that is both time- and resource-consistent.

2.2 Example

Suppose the following RTN: T = {t1, t2, t3, t4, ts}, A {A(3, ts)}, R = {R(1, ti),R(3,t2),R(-4, t3)}, £ = 0, Q = {G(3, t4, ts)}, N = {t2 - t1 E [5, 10], t3 - t2 E [O,+oo),ts -tl E [O,+oo),ts - t4 E [2,+oo)}. ThisRTNis depicted in Figure 1. The following instantiation a is clearly a solution to this RTN: a(t1 ) = 0, a(t2) = a(t4) = 5, a(t3) = 8, a(ts) = 7. It corresponds to the function l,.(t) depicted in Figure 2.

3 Expressive Power

In this section, we show that most of the classical attributes used in AI Planning as well as most of the resources used in Scheduling can be represented in the RTN framework.

3.1 Planning Attributes

STRIPS operators

Let p be a STRIPS predicate. It can be represented by a resource for which level 0 means that p is false and level 1 means that p is true. Let o be an operator at time-point t. If p is in the precondition of operator o, this can be captured by a greater-than condition G(l , t', t) with the constraint t' -< t 2 . If · p is in the precondition of operator o, this can be cap­ tured by a lower-than condition L(O, t', t). Ifp is in the delete list of operator o, this can be captured by an absolute change A(O, t ) stating that after t , p will be false. If p is in the add list of operator o, this can be captured by an absolute change A(l , t ) stating that after t , p will be true.

IxTET attributes

Let att be an IxTET attribute [Ghallab and Laruelle, 1994]. We can build a mapping f..latt that maps the possible values of attribute att to IQ. Then, a hold predicate hold(att , v, t , t') can be modeled by an equal condition E(f..lau (v), t , t'). An event event( att , v, v', t ) by the conjunction of an equal con­ dition E(f..latt ( v), t', t) , an absolute change A(f..latt ( v'), t) and a temporal constraint t' -< t .

PDDL 2.1

Let's consider a durative action ofPDDL 2.1 [Fox and Long, 2002]. This action can be represented by two time points t 8 (start) and te (end) in our formalism. A condition at start on a non-numerical proposition p can be captured by a greater­ than condition G(l, t, t 8 ) with the precedence t -< t8 , an ef­ fect at start by an absolute change A(l , t 8 ) (similar modeling for conditions and effects at end) and an invariant condition by a greater-than condition G(l , t"' te). Conditions and in­ variants of the form :::;, ~ and= on numeric variables can be captured by RTN conditions L, G and E . Numeric effects assign correspond to absolute changes, whereas increase and decrease correspond to relative changes.

3.2 Scheduling Resources

Discrete resources

A discrete resource of maximal capacity Q [Laborie, 2003] can be captured by an RTN with a greater-than condition G(O, - oo, +oo) 3 a lower-than condition L(Q, -oo, +oo) and an initial production R(Q, - oo). An activity requiring q units of resource over the time interval [t 8 , te) is represented by a pair of relative changes R( - q, t 8 ), R( +q, te)· If the discrete resource is given a varying maximal capacity pro­ file, this can be modeled as a set of lower-than conditions L(Qi, ti, ti+I)-

Reservoir

A reservoir of maximal capacity Q and initial level L [La­ borie, 2003] can be captured by an RTN with a greater­ than condition G(O, -oo, +oo ), a lower-than condition L(Q, - oo, +oo) and an absolute change A(L, -oo) . A production activity corresponds to a relative change R(q, t) where q > 0 whereas a consumption activity corresponds to a relative change R(q, t) where q < 0.

State Resources

In ILOG Scheduler [ILOG, 2002], state resources are defined as objects that at each timepoint can take only one possible state among a known set of possible states S = { Si }. Ac­ tivities requiring different states of the state resource cannot overlap. We can build a mapping f..l res that maps the possible states of the state resource to IQ. Then, the requirement of a given state s of a state resource by an activity executing on the time interval [ts, te) can be modeled as an absolute change A(f..lres(s ), t 8 ) and an equal condition E( f..lres (s), t 8 , te)·

2 t' -< t denotes the constraint t- t' E (0, +oo ).

3 We assume that -oo denotes a time-point before any other time­ point and +oo denotes a time-point after any other time-point.

Additional Expressivity

The RTN framework allows for modeling complex resources and activities in scheduling. In manufacturing for instance, maintenance activities need to be executed as soon as the level of some numerical variable (measuring the "need for mainte­ nance") has reached a certain level. The level of this variable is increased (relative change) by production activities and is reset to 0 (absolute change) by maintenance activities. An­ other example is scheduling while ensuring some condition on a numerical variable during the execution of an activity (e.g. maintaining the temperature of a furnace within a suit­ able interval). Such kind of conditions are very important in process industry and chemistry. The conjunction of ab­ solute changes, relative changes and conditions holding over variable time intervals offers a powerful formalism for rep­ resenting complex scheduling problems. Additional features such as dependence between variable resource quantities q and time-points t that do not directly fit into the RTN model can be handled by additional constraints in a constraint prop­ agation framework.

4 Complexity

In this section, we analyze the algorithmic complexity of solving and providing necessary truth criteria for general RTNs and particular fragments of the RTN formalism. By NP-Complete we mean NP-Complete in the strong sense.

4.1 Notations

Let us consider the following notations about temporal con­ straints: P A denotes the point algebra of [Vilain and Kautz, 1986] which is a restriction of STN# that only consists of the set of qualitative relations {0, -<, ~' = , >--, t, =/=, ?} be­ tween timepoints. ST N # denotes a general STN#. We write t -< t' or t ~ t' to express the fact that the corre­ sponding relation is subsumed by the temporal network. We use the following notations about resource statements: n+ denote any set of relative changes x such that q(x) > 0 (producers). nt- denote any set of pairs of resource state­ ments (R( + 1, t 8 ) , R( - l,te)) where t 8 -< te. LQ denotes the lower-than condition L(Q, - oo, +oo). At" denotes any set ofpairs (x,y) where x = A(q, t8 ) andy= E(q, t 8 ,te ) with t 8 -< te. A fragment of the complete RTN framework is denoted (XIY) where X is the set of changes and con­ ditions allowed in this fragment and Y the type of tempo­ ral constraints. n denotes the number of resource statements in the RTN, m the number of temporal constraints between time-points and maxfiow(n, m) the complexity of comput­ ing a maximum flow on a graph with n nodes and m arcs 4 .

4 State-of-the-art maximum flow algorithms do it in 0 ( nm log n) in worst case [Hochbaum, 1998].

4.2 Finding a solution

Complexity 1 The problem of finding a solution to an RTN is in NP.

Proof: The time-consistency of an instantiation a can be checked in polynomial time and, given its definition, the func­ tion lu can be build and the resource-consistency checked in polynomial time. A simple algorithm to check that an instan­ tiation is a solution runs in 0 ( m + n log n). ·

The proof of the three polynomiality results below is omit­ ted because trivial.

Complexity 2 (R+, LQJSTNI ) can be solved in O(n 3 ) .

Complexity 3 (Rt- , £ 1 JPA) can be solved in O(n 3 ) .

Complexity 4 (A, RJSTNI ) can be solved in O(n 3 ).

Complexity 5 (Rt-, £1JSTNI ) is NP-Complete.

Proof: The scheduling decision problem 1Jprec( lij) , Pi 1JCmax ::; T that consists in scheduling on a machine a set of activities of unit duration subject to minimax delays be­ tween activities and maximal makespan is a special case of (Rt-,£1ISTNI). See for instance [Finta and Liu, 1996] for a proof of its NP-completeness. ·

Complexity 6 (AEJSTNI ) is NP-Complete.

Proof: The special case where all the quantities q of the pairs (x, y) are different can be reformulated as a problem (nt-,£IISTNI) (cfabove). ·

Complexity 7 (R+, EJP A) is NP-Complete.

Proof: The Subset Sum Problem (SSP), which is known to be NP-complete [Garey and Johnson, 1979] can be re­ duced to this problem. SSP: Given a finite set R; and for each element x E R a positive integer size q(x); a positive integer Q. Is there a subset S of R such that L xES q(x ) = Q? Let the RTN composed of the re­ source relative changes R(q(x), t(x)) for x E Rand only one equal conditionE( Q, T, T 1 ) with T -< T 1 · It's clear that if there exists a solution S to the SSP then this solution can clearly be transformed into a solution to the RTN; for ex­ ample by choosing T = 0, T 1 = 1, Vx E S, t(x) = 0, Vx E R \ S, t(x) = 1. Reciprocally, for any solution a to the RTN, a solution to the corresponding SSP can be built by takingS= {x E Rfaot(x )) ::; a(T)}. Note that SSP is not NP-Complete in the strong sense. (R+ , EJP A) can be proved to be NP-Complete in the strong sense by a transformation from the 3-Partition problem [Garey and Johnson, 1979] very similar to the one used in this proof. ·

Complexity 8 (A, n+ , LQ JP A) is NP-Complete.

Proof: The Bin Packing Problem (BPP), which is known to be NP-complete [Garey and Johnson, 1979] can be reduced to this problem. BPP: Given a finite set R of m items; for each item x E R a positive integer size q(x); a positive integer Q and k ::; m. Can R be partitioned into k dis­ joint sets R1, ... , Rk such that Vi E [1, k], Lx(;'R, q(x) ::; Q? Let the RTN composed of the resource relative changes {R(q(x), t(x))}xEn, a temporal chain of k - 1 absolute changes { A(O, Ti)}i=l..k- 1 with the precedence constraint Ti -< Ti+1 and the lower-than condition L( Q, -oo, +oo ). If there exists a solution R1, ... , Rk to the BPP, it's clear that a solution a to the RTN can be built as follows: a( Ti) = 2i, Vx E ~ ' a ot(x) = 2i - 1. Reciprocally, a solution to the RTN problem can be used to build a solution to the BPP by defining the sets R1 = {x E R / a ot(x) < a(TI)} and, for 1 < i < k, Ri = {x E R / a(Ti-1) ::; a ot(x) < a(Ti)} and Rk = {x E R / a(Tk-d ::; aot(x )}. ·

Complexity 9 (Rt-, LQ JP A) is NP-Complete.

Proof: The Sequencing to Minimize Maximum Cumulative Cost Problem (SMMCCP) with tasks costs in { -1, 1 }, which is known to be NP-complete [Garey and Johnson, 1979] can be reduced to this problem. SMMCCP: Given a set of tasks T, a partial order between tasks -<, a fixed cost c( t) E { -1, 1} for each task t E T and a constant K, find a total order < on T that obeys the partial order -< and such that Vt E T, Lt'<t c(t') ::; K. Given a SMMCCP, we can build an RTN as follows. Each task t corresponds to a time­ point in the RTN. The precedence constraints correspond to the partial order -< between tasks. Two additional time-points -oo and +oo are respectively added before and after all the other time points t E T . For a task t such that c(t) = +1, we add the two relative changes R(+1,t) and R(-1,+oo) . For a task t such that c( t) = -1, we add the two relative changes R(+1,-oo) and R(-1, t). Let N be the number of tasks t such that c( t) = - 1. We then add the lower-than condition L(K + N , -oo, +oo). Let i(t) E [1 , JTIJ be an arbitrary indexing of the set of tasks T . Let a be a solution to the RTN. We build a total order between tasks as follows: t' < t if and only if a(t') < a(t) or [a(t') = a(t) and c(t') = -1 and c(t) = +1] or [a(t') = a(t) and c(t') = c(t) and i(t') < i(t)]. It's easy to see that < is a solution to the original SMMCCP. ·

4.3 Necessary Truth Criterion

The Necessary Truth Criterion (NTC) is the problem of de­ ciding whether a given RTN is such that any of its time­ consistent instantiation is also resource-consistent (and thus, is a solution). NTCs were introduced by David Chapman in a very influential paper [Chapman, 1987] where, in the con­ text of planning with resources, he mentions the existence of "clever polynomial algorithms using network flow techniques that compute the exact least value the state variable could take on ". One of these algorithms was described in [Rhys, 1970] and more recently in [Muscettola, 2002]. In this sec­ tion, we develop this idea and give some complexity results for NTCs in the context of resource temporal networks. No­ tice that, due to lack of space, proofs are mostly sketched. Note also that all the problems studied in this section are NP­ Complete (see section 4.2). Without lack of generality we as­ sume in this section that the RTNs do not contain any poten­ tially conflicting pairs of changes. A pair of absolute changes (x, x') E A 2 is said to be potentially conflicting if and only if q(x) =f. q(x') and N does not subsume t(x) =f. t(x'). A pair (x, x') E A x R is said to be potentially conflicting if and only if N does not subsume t(x) =f. t(x'). Indeed, if such conflicting pairs exist, it is easy to add the corresponding non­ simultaneity constraints t(x) =f. t(x') onN.

Lemma 1 NTC for (R, LQISTNi-) can be solved in O(maxfiow(n, m)).

Proof: First, we recap a result of [Rhys, 1970] showing that NTC for (R, LQIPA) is polynomial. The problem can be expressed as a Maximum Weight Closure Problem (MWCP) on the directed graph where the arcs -<, ::5 of the PA net­ work have been reversed and all arcs =f. are ignored. MWCP: Given a directed graph G = (V, A) and a node weight q(x) E Qfor each node in x E V. A subsetS ~ Vis called a closure if and only if it does not contain any outgo­ ing arc that is 1::/x E S, (x, y) E A => y E S . The problem is to find the maximum weight closure. The RTN satisfies the NTC if and only if the weight of the maximum weight clo­ sure is lower than or equal to Q. Indeed, if S* denotes the maximum weight closure, there exists an instantiation of the RTN such that all the changes in S* are scheduled before all the other changes and the resource level after all the changes in S* is the maximum resource level reachable in all time­ consistent instantiations. This level is exactly the weight of S* . As shown in [Ahuja et al., 1993], the MWCP is equiva­ lent to the min-cut/max-flow problem. For the more general problem (R,£QISTNi-), similar arguments as in [Muscet­ tola, 2002] (separation schedule) can be used to show that the RTN satisfies the NTC if and only if the symbolical P A temporal constraint network subsumed by the ST Ni- satis­ fies the NTC. ·

Lemma 2 NTC for (A, n +' LQ I p A) can be solved in O(maxfiow(n, m)).

Proof: We can note that for any instantiation a, the set of chronologically ordered absolute changes A = { xi};=l..n with a o t(xi) :::; a o t(xi+1 ) partitions the set of changes AU n+ inton+l subsets: So= {y E n+,aot(y) < aot(xl)}, fori= l..n-1, Si = {xi}U{y E n+,aot(xi ) < aot(y) < a ot(xi+l)}, Sn = {xn}U{y En+, aot(xn) < aot(y)}. Si is called the layer of Xi. In this context, the maximal level of the resource in instantiation a is the weight of the maximum weight layerS~ AU n+ defined as I:xES q(x). Given an instance of RTN, we build an undirected graph Gas follows. Each change x E AU n+ is associated a unique node in G whose weight is equal to q(x). Informally, there will be an edge between two changes {x , x'} if and only if they can­ not belong to the same layer in a time-consistent instantiation. More precisely, there is an edge in G between each pair of ab­ solute change. Furthermore, if X E Au n+ is a change and x' E n + is a relative change, there is an edge {X' x'} in G if and only if there exists an absolute change y E A such that x ::5 y ::5 x'. It is not difficult to show that the maximal level of the resource is equal to the weight of the maximum inde­ pendent set of G. Furthermore G is a comparability graph as the edges involving at least one relative change can nat­ urally be oriented with the direction of a path containing an absolute change between them and the remaining of the edges (between pairs of absolute changes) forms a clique. Comput­ ing the maximum weight independent set of a comparability graph is polynomial and can be solved as a min-flow problem [Golumbic, 1980]. Thus, the NTC only needs to compare the weight of the maximum weight independent set of G with the maximal resource level Q. ·

The following lemma is a generalization of Lemma 2 when all changes are allowed including consumers (q < 0).

Lemma 3 NTC for (A, R, LQIPA) can be solved in O(nmaxfiow(n, m)).

Proof: We prove that the problem can be solved by solv­ ing nA Maximum Weight Convex Set Problems (MWCSP) where nA :=:; n is the number of absolute changes. MWCSP: Given a poset G = (V, :=;) where :=:; is a partial order on V (reflexive, antisymmetric and transitive relation) and a weight function w(x) E Q. A subsetS ~ Vis said to be convex if andonlyifl::/(x,y) E S 2 ,Vz E V,x :=:; z :=:; y => z E S . The problem is to find a convex subset S ~ V of maximum total weight. As shown in [Groflin, 1985], this problem can be solved in polynomial time by a min-flow/max-cut algo­ rithm. For a given absolute change xi E A, we transform the problem of computing the maximum level of the resource in the layer of Xi (see sketch of proof of Lemma 2) as an in­ stance ofMWCSP. The poset Gi = (V;, :::;) of this MWCSP is built as follows: V; = {xi} u {x E Au n, -.(x ::5 Xi)} and x :::; y if and only if relation x ::5 y is subsumed by the PA network. w(xi) = K + q(xi) where K is big enough (K > ~xEnlq(x)i), w(x) = -oo if x E A\ {xi} and w(x) = q(x) if x E n. One can show that for any con­ vex set S of Gi containing Xi, there exists a time-consistent instantiation a and a timet such that la(t) = w(S)- K and that for any time-consistent instantiation a and a time t, the set { x E V; /a o t ( x) :=:; t} is convex. Thus, the maximum re­ source level reachable in the layer of Xi is w(Si) - K where s; is the maximum weight convex set of Gi. Note that due to the choice of K, Xi E Si. ·

We can see that Lemmas 1, 2 and 3 also hold when the unique lower-than condition does not span over the com­ plete horizon ( -oo, +oo) but on some variable time interval [t., te) where {t., te} CT. Indeed, in this case, the problem can be transformed into a problem where the lower-than con­ dition spans over the complete horizon and three additional relative changes are considered: R(-K,-oo), R(+K,t.), R( -K, te) where K is big enough.

Furthermore, Lemmas 1 and 3 also hold for a greater-than condition 9Q as, here again, the problem can easily be trans­ formed into a problem with a lower-than condition L-Q and with opposite resource changes.

Theorem 1 Let II = (T, A, R, £, Q, N) be an RTN. For y E C U Q, let IIy denote the RTN where y is the only condition in otherwordsiiy = (T,A, R ,Cn{y} ,Qn{y} ,N) . NTC(II) is true if and only if for each condition statement y E £ U 9, NTC(IIy) is true.

Proof: The theorem gives a necessary condition for NTC(II) to be true because if the condition is not met, a time-consistent instantiation can be built that is not resource­ consistent. Reciprocally, if NTC(II) is false, it means that there exists a time-consistent instantiation that is not resource-consistent. This time-consistent instantiation vio­ lates at least one condition statement y E £ U Q. ·

The following complexity results use Theorem 1 to extend Lemmas 1 and 3 to the more general case of any set of condi­ tion statements. For each of these results, one can show that problem IIy can be transformed into one of the corresponding lemma and thus, its time complexity is polynomial.

Complexity 10 NTC for (R, C, giST N'~-) can be solved in O(n maxfiow(n, m)).

Complexity 11 NTC for (A, n, C, giP A) can be solved in O(n 2 maxfiow(n, m)).

5 Conclusion and Future Work

In this paper, we introduce the notion of RTN to express a large panel of possible evolutions of a given numerical state variable over time. RTNs allow modeling on the same flu­ ent features of classical AI Planning (absolute changes, con­ ditions) and Scheduling (relative changes). We show that computing a solution to an RTN is in general NP-Complete whereas determining whether all time-consistent instantia­ tions of an RTN are solutions is polynomial. This last result indicates that efficient solving methods based on such poly­ nomial Necessary Truth Criteria can be developed. Indeed, when an RTN does not satisfy the NTC, all the algorithms we mention can exhibit a subset of changes sufficient to explain why some time-consistent instantiations are not a solution. Just like in classical planning or scheduling, these potential conflicts can be used to branch in a search tree until the NTC is true and to perform constraint propagation.

A direction for future work will consist in studying the complexity of the only problem whose complexity is still open: NTC for (A, R, C, gj ST Ni-). Based on the fairly optimistic results described in this paper, we also plan to work on the development of practical and efficient algo­ rithms for solving NTC and for finding solutions (branching schemes, heuristics, computation of resource envelopes, con­ straint propagation). We think that the numerous and well­ studied combinatorial problems we found tightly related with RTNs (one-machine scheduling problems, subset sum, bin packing, sequencing to minimize maximum cumulative costs, maximum weight closure, maximum weight independent set, maximum weight convex set) can also help to solve RTNs. For instance, state-of-the-art bin packing algorithms could be a source of inspiration for (A, n+, CQISTN'~-). Extension of the framework to integrate and mix continuous relative changes (see continuous reservoirs [ILOG, 2002]) and abso­ lute changes (see [Penberthy and Weld, 1994; Trinquart and Ghallab, 2001]) is also clearly of interest.

6 Acknowledgements

I am very grateful to Andre Kezdy for pointing me to some relevant articles about the maximum weight convex set prob­ lem as well as to many other graph theorists who got inter­ ested in this problem. Special thanks to Emmanuel Guere and Pascal Massimino for enlightening discussions on the RTN semantics and complexity issues and to Francis Sourd for carefully proofreading the paper.