Planning as Satisfiability with Preferences

Abstract

Planning as Satisfiability is one of the most well-known and effective technique for classical planning: SATPLAN has been the winning system in the deterministic track for optimal planners in the 4th International Planning Competition (IPC) and a co-winner in the 5th IPC. In this paper we extend the Planning as Satisfiability ap-proach in order to handle preferences and SATPLAN in or-der to solve problems with simple preferences. The resulting system, SATPLAN(P) is competitive with SGPLAN, the win-ning system in the category “simple preferences ” at the last IPC. Further, we show that SATPLAN(P) performances are (al-most) always comparable to those of SATPLAN when solving the same problems without preferences: in other words, in-troducing simple preferences in SATPLAN does not affect its performances. This latter result is due both to the particular mechanism we use in order to incorporate preferences in SAT-PLAN and to the relative low number of soft goals (each corre-sponding to a simple preference) usually present in planning problems. Indeed, if we consider the issue of determining minimal plans (corresponding to problems with thousands of preferences) the performances of SATPLAN(P) are compara-ble to those of SATPLAN in many cases, but can be signif-icantly worse when the number of preferences is very high compared to the total number of variables in the problem. Our analysis is conducted considering both qualitative and quan-titative preferences, different reductions from quantitative to qualitative ones, and most of the propositional planning do-mains from the IPCs and that SATPLAN can handle.