Act, and the REST Will Follow: Exploiting Determinism in Planning as Satisfiability

Abstract

In this paper we focus on Planning as Satisfiability (SAT). We build from the simple consideration that the values of fluents at a certain time point derive deterministically from the initial situation and the sequence of actions performed till that point. Thus, the choice of actions to perform is the only source of nondeterminism. This is a rather trivial consideration, but which has important positive consequences if implemented in current planners via SAT. In fact, it produces a dramatic size reduction of the space of the truth assignments searched in by the SAT decider used to solve the final SAT problem. To justify this claim, we repeat many of the experiments reported in (Ernst, Millstein, & Weld 1997), and show that the CPU time requested to solve a problem can go down up to 4 orders of magnitude. Introduction Historically, planning has been dealt with as a problem of deduction in first order logic (Green 1969; McCarthy & Hayes 1969) or later through the definition of special...