Planning as Satisfiability is one of the most well-known and effective technique for classical planning: s atplan 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 approach in order to handle preferences and SATPLAN in order to solve problems with simple preferences. The resulting system, satplan(P) is competitive with sgplan, the winning system in the category "simple preferences" at the last IPC. Further, we show that Satplan(P) performances are (almost) always comparable to those of S atplan when solving the same problems without preferences: in other words, introducing simple preferences in s atplan 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 corresponding 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 comparable to those of SATPLAN in many cases, but can be significantly 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 quantitative preferences, different reductions from quantitative to qualitative ones, and most of the propositional planning domains from the IPCs and that satplan can handle.
展开▼
