unnecessary delays in the plan. However, in the test problems of the 3rd IPC the possibility of overlapping mutex actions is rare, and when it is possible it does not affect the temporal quality of the plans significantly. Recently, we have extended the treatment of mutex actions in LPG , distinguishing various types of interferences and competing needs. These are handled by ordering constraints between different endpoints of the involved actions, allowing overlapping mutex actions. Experimental results using the SimpleTime variant of the Satellite domain show that the new version of LPG generates plans which are about 10% better (in terms of makespan) than those computed by the competition version. Moreover, the overhead introduced by the more sophisticated management of the temporal information is on average negligible. A detailed description of how temporal information is managed in the new version of LPG is given in another recent paper (Gerevini, Saetti, & Serina, 2003).

## 3.5 Numerical State Variables

In this subsection we briefly describe how LPG deals with preconditions and effects involving nmerical quantities.  We start with a brief description of numerical preconditions and effects in PDDL21, and then we show how the plan representation, search neighborhood and heuristics that we presented in the previous sections have been extended to handle them.

In PDDL2.1 a state s for a planning domain involving numerical variables is a pair
(p(s), v(s)) where p(s) is a set of ground atoms (positive facts), and v(s) = (r1,...,rn) is a tuple of real numbers representing the values of the n numerical variables v 1 , v 2 , ..., v n , A numerical expression is an arithmetic expression over the set V of these variables and the real numbers. A numerical precondition is a triple ( exp, rel, exp'), where exp and exp' are numerical expressions, and rel E {<, <, =, >} is a relational operator. A numerical effect is a triple ⟨ v i , ass, exp ⟩ , where v i ∈ V is a variable, ass ∈ {:=, +=, −−, *=, /=} is an assignment operator (using a C-like notation), and exp is a numerical expression.

In order to handle numerical domains, we have extended the notion of TA-graph with numerical fact nodes representing values of numerical variables. For each level l in the current action graph A and each numerical variable v 1 E V, there is a numerical fact node representing the value for v i at level l . The resulting tuple of real values at level l is denoted by Num values ( l ). These values are derived by applying all actions in A at the levels preceding , starting from the initial level and following the order of the corresponding levels. 19 The values of the numerical fact nodes at the initial level, Num values (0), are the real numbers assigned to the corresponding numerical variables in the initial state of the planning problem under consideration. Similarly, we can associate with each level l a set of facts that are true ( Supported_facts ( l )), given the actions in A at levels preceding l .

In this way we can define a numerical state s 1 = ( Supported_facts ( l ), Num_values ( l )) for each level l of A.

A numerical precondition (exp,rel,exp') of an action at a level l is supported if and only if the values of exp and exp ′ evaluated in s t satisfy the relation rel .