- In generating plan sets sequentially to cope with partial preference models, Sampling approach that searches for plans separately and independently of the solution space tends to return worse quality plan sets than Hybrid approach.

- The resulting plan sets returned by Hybrid approach tend to be more sensitive to the user's preference models than those found by Sampling approach.

## 6. Related Work

Currently there are very few research efforts in the planning literature that explicitly consider incompletely specified user preferences during planning. The usual approach for handling multiple objectives is to assume that a specific way of combining the objectives is available (Refanidis and Vlahavas, 2003; Do and Kambhampati, 2003), and search for one optimal plan with respect to this function.

Brafman & Chernyavsky (2005) discuss a CSP-based approach to find a plan for the most prefered goal state given the qualitative preferences on goals. There is no action cost and makespan measurements such as in our problem setting. Other relevant work includes Bryce et al. (2007), in which the authors devise a variant of LAO* algorithm to search for a conditional plan with multiple execution options for each observation branch that are non-dominated with respect to objectives like probability and cost to reach the goal.

In the context of decision-theoretic planning, some work has been focused on scenarios where the value function is not completely defined, in particular due to the incompleteness in specifying the reward function. In those cases, one approach is to search for the most robust policy with different robustness criteria (e.g., Delage and Mannor, 2007; Regan and Boutilier, 2010; Nilim and Ghaoui, 2005). The idea of searching for sets of policies has also been considered recently in reinforcement learning. Specifically, in (Natarajan and Tadepalli, 2005) the reward function is incomplete with weight values changing over time, and a set of policies is searched and stored so that whenever the weights change a new best policy can be found by improving those in the set. On the other hand, Barrett and Narayanan (2008) provide Bellman equations for the Q-values using all vectors on convex hull to search for the whole pareto set.

Our work on planning with partial user's preferences is also related to work on preference elicitation and decision making under uncertainty of preferences. For instance, Chajewska et al (2000) consider a decision making scenario where the utility function is assumed to be drawn from a known distribution, and either a *single* best strategy or an elicitation question will be suggested based on the expected utility of the strategy and the value of information of the question.

Boutilier et al. (2010) considers preference elicitation problem in which the user's preference model is incomplete on both the set of features and the utility function. However, these scenarios are different from ours in two important issues: we focus on efficient approach to synthesizing plans with respect to the partial preferences, whereas the "outcomes" or "configurations" in their cases are considered given upfront (or could be obtained with low cost), and we aim to search for a set of plans based on a quality measure of plan sets (instead of a quality measure over individual outcome or configuration).

Our approach to generating diverse plan sets to cope with planning scenarios without knowledge of user's preferences is in the same spirit as (Tate et al., 1998) and Myers (Myers, 2006; Myers and Lee, 1999), though for different purposes. Myers, in particular, presents an approach to generate diverse plans in the context of her HTN planner by requiring the metatheory of the domain to be available and using bias on the meta-theoretic elements to control search (Myers and Lee, 1999). The metatheory of the domain is defined in terms of pre-defined 35