action preconditions ( G ), and ending when G ⊆ I . The subroutine incrementally constructs a set of actions ( ACTS ) achieving the facts in G and the preconditions of the actions already selected (using Action ). At each iteration the set G is revised by adding the preconditions of the last action selected, and removing the facts belonging to I or to the effects of actions already selected (step 7). Termination of RequiredActions is guaranteed because every element of G is reachable from I .

Time-fact ( f , 1) is computed in a way similar to Num acts ( f , 1). Step 3 of ComputeReachabilityInformation initializes it to 0, for any fact f in the initial state. Then, at every application of an action a in the forward process described above, we estimate the earliest possible time t for applying a as the maximum value over the times currently assigned to its preconditions (step 11). For any effect f of a that has not been considered yet (i.e., that is not in F ), or that has a temporal value higher than t plus the duration of a, steps 13-14 set Time_fact ( f , 1) to this lower value (because we have found a shorter relaxed plan to achieve f from I ).

The complexity of ComputeReachabilityInformation is polynomial in the number of facts and actions in the problem/domain under consideration. Step 10, the most expensive step of the algorithm, is executed O ( | O | ) times, where O is the set of all actions, and | O | is the size of this set. It is easy to see that the worst-case time complexity of RequiredActions is O ( | O |). It follows that the time complexity of ComputeReachabilityInformation is 0( 0 | 2 ). However, we have experimentally observed that very often RequiredActions terminates returning numbers much smaller than [0] (i.e, that the number of iterations that the algorithm performs is well below [0]). Finally, we observe that the order in which actions are examined for their application in the forward process can affect the output results. In our current implementation we use a random order.

Figure 7 illustrates the algorithm with an example. Suppose that the facts in the initial state I are f 1 ...s, and that the actions in O are a 1 ... 7 , where the subscript of the actions correspond to the order in which they are applied by the algorithm. The first actions that are applied are a 1 , a 2 and a 3 , because their preconditions are in F which is initially set to I .

The Num acts value of these preconditions is set to zero, because RequiredActions applied to them returns zero. In the internal for-loop of the algorithm we update the reachability information for each effect of these actions. In particular, consider the effects f 1 and f 3 of a 1 . Since f 1 is not a new fact (it belongs to I ) and its Num acts and Time_fact values are set to the minimum (initial) values, steps 14 and 16 do not revise them. Since f 9 is a new fact, step 14 sets Time_fact ( f 0 ) to 10 (i.e., the duration of a 1 ), and step 16 sets Num acts ( f 9 ) to 1 ( r a is zero). Moreover, Action ( f 9 , 1) is set to a 1 by step 17. The effects of a2 and a3 are handled similarly.

At this point, since there is no other action that is applicable in F , the internal whileloop terminates, F is set to F ∪ { fo, fio, fil, fil }, and F new is set to ∅. The set A ′ of the actions in A that are applicable is {a 4 , a 5 , a 6 }. Consider the application of a 4 . We have that r a at step 10 is set to 2, because RequiredActions(I, Pre(a,)) sets ACTS to {a,,a2} (note that f 1 E I, Action(f 9, 1) = a 1, Action(f 10, 1) = a 2, and all preconditions of these actions are in I ). Thus, Time_fact (f 13 ) is set to 80 (i.e., the maximum temporal value assigned to a precondition of a 4 , 30, plus the duration of a 4 ), and Num act s( f 13 ) to 3. The effects of the actions a 5 and a 6 are handled in a similar way. However, it is worth noting that Num acts ( f 15 ) is first set to 3, when we examine a5, and then revised to 2, when we