ICP Est(G′) guides Metric-LPG's search toward a plan p generated from G′such that the resulting set **P ∪ {**p} has a minimum ICP value: p **= argmin**
p ICP(**P ∪ {**p}). Thus, **ICP Est**(G′)
estimates the expected total ICP value if the best plan p found by expanding G′is added to the current found plan set P. Like the original Metric-LPG, p is estimated by pR = G′ SR where R is the relaxed plan resolving inconsistencies in G′caused by inserting or removing a. The ICP Est(G′) for a given NA-graph G′is calculated as: ICP Est(G′) = ICP(P ∪pR) with the ICP measure as described in Equation 12. Notice here that while P is the set of valid plans, pR is not. It is an invalid plan represented by a NA-graph containing some unsupported preconditions. However, Equation 12 is still applicable as long as we can measure the time and cost dimensions of pR. To measure the makespan of pR, we estimate the time points at which unsupported facts in G′ would be supported in pR = G′ ∪ R and propagate them over actions in G′to its last level. We then take the earliest time point at which all facts at the last level appear to measure the makespan of pR. For the cost measure, we just sum the individual costs of all actions in pR.

At each step of Metric-LPG's local search framework, combining two measures **ICP Est**(G′)
and **SearchCost**(G′) gives us an evaluation function that fits right into the original Metric-LPG framework and prefers a NA-graph G′in the neighborhood of G that gives the best trade-off between the estimated effort to repair and the estimated decrease in quality of the next resulting plan set. 5.5. Experimental Results We have implemented several approaches based on our algorithms discussed in the previous sections: Sampling (Section 5.1), ICP-sequential (Section 5.2) and Hybrid that combines both
(Section 5.3) with both the uniform and triangular ditributions. We consider two types of distributions in which the most probable weight for plan makespan are 0.2 and 0.8, which we will call "w02" and "w08" distributions respectively (Figure 9 shows these distributions). We test all implementations against a set of 20 problems in each of several benchmark temporal planning domains used in the previous International Planning Competitions (IPC): ZenoTravel, *DriverLog*, and *Depots*. The only modification to the original benchmark set is the added action costs.

The descriptions of these domains can be found at the IPC website ( *ipc.icaps-conference.org*). The experiments were conducted Intel Core2 Duo machine with 3.16GHz CPU and 4Gb RAM.

For all approaches, we search for a maximum of k **= 10** plans within the 10-minute time limit for each problem (i.e., t **= 10** minutes), and the resulting plan set is used to compute the ICP value. In the Sampling approach, we generate ten trade-off values w between *makespan* and *plan cost* based on the distribution, and for each one we search for a plan p subject to the value function V (p, w) = w × tp **+ (1** − w) × cp. In the Hybrid approach, on the other hand, the first Sampling approach is used with k0 = 3 generated trade-off values to find an initial plan set, which is then improved by the ICP-Sequential runs. As Metric-LPG is a stochastic local search planner, we run it three times for each problem and average the results. In 77% and 70% of 60 problems in the three tested domains for Hybrid and Sampling approaches respectively, the standard deviation of ICP values of plan sets are at most 5% of the average values. This indicates that ICP values of plan set in different runs are quite stable. As the Hybrid approach is an improved version of ICP-sequential and gives better results in almost all tested problems, we omit the ICP-Sequential in discussions below. We now analyze the results in more detailed.

The utility of using the partial knowledge of user's preferences: To evaluate the utility of taking partial preferences into account, we first compare our results against the naive approaches that