Planning with partial preference models


Nguyen, T.; Do, M. B.; Kambhampati, S.; Srivastava, B. Planning with partial preference models. Twenty-first International Joint Conference on Artificial Intelligence (IJCAI-09); 2009 July 11-17; Pasadena, CA.


Most planners search for a plan optimizing some metric function, which commonly is a combined function of different independent objectives. In many scenarios, the exact tradeoff between those individual objective functions are not known, and the planner needs to return a set of solutions for the user to choose from. Currently, the most common one is the pareto-optimal set of non-dominating plans but finding the entire pareto set is very costly for many problems. In this paper, we consider an alternative approach of finding a representative subset of the pareto set utilizing the belief distribution of the tradeoffs between objective functions (e.g., plan makespan and execution cost). We measure the quality of this representative solution set using the Integrated Convex Preference (ICP) model and present several heuristic approaches based on the Metric-LPG planner to find a good solution set according to this measure. We show empirically that taking the ICP measure into account directly when gradually growing the solution set is better than the naive approach of sampling for the trade-off values and find good solutions individually.

Read more from SRI