which can lead to different solutions. It is then interesting to compare LPG-d and a method in which we simply run the standard LPG until k d-diverse plans are generated. An experimental comparison of the two approaches show that in many cases LPG-d performs better. In particular, the new evaluation function E is especially useful for planning problems that are easy to solve for the standard LPG, and that admit many solutions. In these cases, the original E function produces many valid plans with not enough diversification. This problem is significantly alleviated by the new term in E. An example of domain where we observed this behavior is logistics.

12

## 5. Generating Plan Sets With Partial Preference Knowledge

In this section, we consider the problem of generating plan sets when the user's preferences are only partially expressed. In particular, we focus on metric temporal planning where the preference model is assumed to be represented by an incomplete value function specified by a convex combination of two features: *plan makespan* and *execution cost*, with the exact trade-off value w drawn from a given distribution. The quality value of plan sets is measured by the ICP
value, as formalized in Equation 12. Our objective is to find a set of plans **P ⊆ S** where **|P| ≤** k and ICP(P) is the lowest.

Notice that we restrict the size of the solution set returned, not only for the comprehension issue discussed earlier, but also for an important property of the ICP measure: it is a monotonically non-increasing function of the solution set (specifically, given two solution sets P1 and P2 such that the latter is a superset of the former, it is easy to see that ICP(P2) ≤ ICP(P1)).

## 5.1. Sampling Weight Values

Given that the distribution of trade-off value w is known, the straightforward way to find a set of representative solutions is to first sample a set of k values for w: {w1, w2**, ..., w**k} based on the distribution h(w). For each value wi, we can find an (optimal) plan pi minimizing the value of the overall value function V (p, wi) = wi × tp **+ (1** − wi) × cp. The final set of solutions P = {p1, p2**, ....p**k} is then filtered to remove duplicates and dominated solutions, thus selecting the plans making up the lower-convex hull. The final set can then be returned to the user. While intuitive and easy to implement, this sampling-based approach has several potential flaws that can limit the quality of its resulting plan set.

First, given that k solution plans are searched sequentially and independently of each other, even if the plan pi found for each wiis optimal, the final solution set P = {p1, p2**...p**k} may not even be the optimal set of k solutions with regard to the ICP measure. More specifically, for a given set of solutions P, some tradeoff value w, and two non-dominated plans p, q such that V (p, w) < V (**q, w**), it is possible that ICP(P ∪ {p}) > ICP(**P ∪ {**q}). In our running example (Figure 5), let P = {p2, p5} and w = 0.8 then V (p1, w) = 0.8 × 4 + 0.2 × **25 = 8**.2 < V (p7, w) = 0.8 × 12 + 0.2 × **5 = 10**.6. Thus, the planner will select p1 to add to P because it looks locally better given the weight w = 0.8. However, ICP({p1, p2, p5}) ≈ 10.05 > ICP({p2, p5, p7}) ≈ 7.71 so indeed by taking previous set into consideration then p7 is a much better choice than p1.