attributes and their possible values covering roles, features and measures. Our work differs from hers in two respects. First, we focus on domain-independent distance measures. Second we consider the computation of diverse plans in the context of state of the art domain independent planners.

The problem of finding multiple but similar plans has been considered in the context of replanning. A recent effort in this direction is (Fox et al., 2006). Our work focuses on the problem of finding diverse plans by a variety of distance measures when the user's preferences exist but are completely unknown.

Outside the planning literature, our closest connection is to the work by Hebrard et al. 2005, who solve the problem of finding similar/dissimilar solutions for CSPs without additional domain knowledge. It is instructive to note that unlike CSP, where the number of potential solutions is finite (albeit exponential), the number of distinct plans for a given problem can be infinite (since we can have infinitely many non-minimal versions of the same plan). Thus, effective approaches for generating diverse plans are even more critical. The challenges in finding interrelated plans also bear some tangential similarities to the work in information retrieval on finding similar or dissimilar documents (c.f. (Zhang et al., 2002)).

## 7. Conclusion And Future Work

In this paper, we consider the planning problem with partial user's preference model in two scenarios where the knowledge about preference is completely unknown or only part of it is given.

We propose a general approach to this problem where a set of plans is presented to the user from which she can select. For each situation of the incompleteness, we define different quality measure of plan sets and investigate approaches to generating plan set with respect to the quality measure. In the first scenario when the user is known to have preferences over plans, but the details are completely unknown, we define the quality of plan sets as their diversity value, specified with syntactic features of plans (its action set, sequence of states, and set of causal links).

We then consider generating diverse set of plans using two state-of-the-art planners, GP-CSP and LPG. The approaches we developed for supporting the generation of diverse plans in GP-CSP are broadly applicable to other planners based on bounded horizon compilation approaches for planning. Similarly, the techniques we developed for LPG, such as biasing the relaxed plan heuristics in terms of distance measures, could be applied to other heuristic planners. The experimental results with GP-CSP explicate the relative difficulty of enforcing the various distance measures, as well as the correlation among the individual distance measures (as assessed in terms of the sets of plans they find). The experiments with LPG demonstrate the potential of planning using heuristic local search in producing large sets of highly diverse plans.

When part of the user's preferences is given, in particular the set of features that the user is interested in and the distribution of weights representing their relative importance, we propose the usage of *Integrated Preference Function*, and its special case *Integrated Convex Preference* function, to measure the quality of plan sets, and propose various heuristic approaches based on the Metric-LPG planner (Gerevini et al., 2008) to find a good plan set with respect to this measure. We show empirically that taking partial preferences into account does improve the quality of plan set returned to the users, and that our proposed approaches are sensitive to the degree of preference incompleteness, represented by the distribution.

While a planning agent may well start with a partial preference model, in the long run, we would like the agent to be able to improve the preference model through repeated interactions with the user. In our context, at the beginning when the degree of incompleteness of preferences 36