Planning with goal preferences and constraints
Ronen I. Brafman, Yuri Chernyavsky · 2005
In classical planning, the planner is given a concrete goal; it returns a plan for it or a failure message. In the latter case, the user can either quit or modify the goal. For many appli-cations, it is more convenient to let the user provide a more elaborate specification consisting of constraints and prefer-ences over possible goal states. Then, let the system dis-cover a plan for the most desirable among the feasible goal states. To materialize such an approach we require a formal-ism for specifying preferences and constraints over goals and an algorithm for solving the resulting constrained optimiza-tion problem. In this work we motivate the need for planning with preferences and constraints, suggest a rich, yet intuitive formalism for representing goal preferences in the context of a deterministic action model, discuss some of its properties, propose an efficient algorithm for planning with preferences and constraints based on this formalism, and provide exten-sive experimental analysis in an interesting new domain of configuration planning.