she prefers. What is clearly needed, therefore, is the ability to generate a set of plans, among all sets of *bounded* (small) number of plans, with the highest chance of including the user's preferred plan. An immediate challenge is formalizing what it means for a *meaningful* set of plans, in other words what the *quality measure* of plan sets should be given an incomplete preference specification.

We propose different quality measures for the two scenarios listed above. In the extreme case when the user could not provide any knowledge of her preferences, we define a spectrum of distance measures between two plans based on their syntactic features in order to define the diversity measure of plan sets. These measures can be used regardless of the user's preference, and by maximizing the diversity of a plan set we increase the chance that the set is uniformly distributed in the unknown preference space, and therefore likely contains a plan that is close to a user's desired one.

This measure can be further refined when some knowledge of the user's preferences is provided. As mentioned above, we assume that the user's preference is specified by a convex combination of plan attributes, and incomplete in the sense that the distribution of trade-off weights is given, not their exact values. The whole set of best plans (i.e. the ones with the best value function) can be pictured as the lower convex-hull of the Pareto set on the attribute space. To measure the quality of any (bounded) set of plans on the whole optimal set, we adapt the idea of *Integrated Preference Function* (IPF) (Carlyle et al., 2003), in particular its special case *Integrated Convex Preference* (ICP). This measure was developed in the Operations Research (OR)
community in the context of multi-criteria scheduling, and is able to associate a robust measure of representativeness for any set of solution schedules (Fowler et al., 2005).

Armed with these quality measures, we can then formulate the problem of planning with partial preference models as finding a bounded set of plans that has the best quality value. Our next contribution therefore is to investigate effective approaches for using quality measures to bias a planner's search to find a high quality plan set efficiently. For the first scenario when the preference specification is not provided, two representative state-of-the-art planning approaches are considered. The first, GP-CSP (Do and Kambhampati, 2001), typifies the issues involved in generating diverse plans in bounded horizon compilation approaches, while the second, LPG
(Gerevini et al., 2003), typifies the issues involved in modifying the heuristic search planners. Our investigations with GP-CSP allow us to compare the relative difficulties of enforcing diversity with each of the three different distance measures (elaborated in later section). With LPG, we find that the proposed quality measure makes it more effective in generating plan set over large problem instances. For the second case when part of the user's preferences is provided, we also present a spectrum of approaches for solving this problem efficiently. We implement these approaches on top of Metric-LPG (Gerevini et al., 2008). Our empirical evaluation compares these approaches both among themselves as well as against the methods for generating diverse plans ignoring the partial preference information, and the results demonstrate the promise of our proposed solutions.

Our work can be considered as a complement to current research in planning with preferences, as shown in Figure 1. Under the perspective of planning with preferences, most current work in planning synthesize a single solution plan, or a single best one, in situations where user has no preferences, or a complete knowledge of preferences is given to the planner. On the other hand, we address the problem of synthesizing a set of plans when knowledge of user's preferences is either completely unknown or partially specified.

The paper is organized as follows. Section 2 gives fundamental concepts in preferences, and formal notations. In Section 3, we formalize quality measures of plan set in the two scenarios.

3