# Planning With Partial Preference Models

Tuan Nguyen∗,∗∗,a, Minh Dob, Alfonso Gerevinic, Ivan Serinad, Biplav Srivastavae, Subbarao Kambhampatia a *Department of Computer Science and Engineering, Arizona State University Brickyard Suite 501, 699 South Mill* Avenue, Tempe, AZ 85281, USA
b *Embedded Reasoning Area, Palo Alto Research Center 3333 Coyote Hill Road, Palo Alto, CA 94304, USA*
cDipartimento di Elettronica per l'Automazione, Universit degli Studi di Brescia, Via Branze 38, I-25123 Brescia, Italy d*Free University of Bozen-Bolzano, Viale Ratisbona, 16, I-39042 Bressanone, Italy* e*IBM India Research Laboratory, New Delhi and Bangalore, India*

## Abstract

Current work in planning with preferences assume that the user's preference models are completely specified and aim to search for a single solution plan. In many real-world planning scenarios, however, the user probably cannot provide any information about her desired plans, or in some cases can only express partial preferences. In such situations, the planner has to present not only one but a set of plans to the user, with the hope that some of them are similar to the plan she prefers. We first propose the usage of different measures to capture quality of plan sets that are suitable for such scenarios: domain-independent distance measures defined based on plan elements (actions, states, causal links) if no knowledge of the user's preferences is given, and the *Integrated Convex Preference* measure in case the user's partial preference is provided. We then investigate various heuristic approaches to find set of plans according to these measures, and present empirical results demonstrating the promise of our approach.1 Key words: Planning, Preferences, Heuristics, Search

## 1. Introduction

Most work in automated planning takes as input a complete specification of domain models and/or user preferences and the planner searches for a single solution satisfying the goals, probably optimizing some objective function. In many real world planning scenarios, however, the user's preferences on desired plans are either unknown or at best partially specified (c.f. Kambhampati (2007)). In such cases, the planner's job changes from finding a single optimal plan to finding a set of representative solutions ("options") and presenting them to the user with the hope that she can find one of them desirable. As an example, in adaptive web services composition, the causal dependencies among some web services might change at the execution time, arXiv:1101.2279v1 [cs.AI] 12 Jan 2011