Constraint Satisfaction Techniques for Planning and Scheduling Problems (COPLAS-15)
Roman Barták, Miguel Á. Salido · 2015
RANTANPLAN is a numeric planning solver that takes advantage of recent advances in SMT. It extends reduction to SAT approaches with an easy and efficient handling of numeric fluents using background theories. In this paper we describe the design choices and features of RANTANPLAN, especially, how numeric reasoning is integrated in the system. We also provide experimental results showing that RANTANPLAN is competitive with existing exact numeric planners. Introduction The problem of planning, in its most basic form, consists in finding a sequence of actions that allow to reach a goal state from a given initial state. Although initially considered a deduction problem, it was rapidly seen that it could be addressed by looking at it as a satisfiability (model finding) problem (Kautz and Selman 1992). Many (incomplete) heuristic methods can be found in the literature to efficiently deal with this problem, most of them oriented towards finding models. Exact methods were ruled out at the beginning due to their inefficiency. However, in (Kautz, McAllester, and Selman 1996) it was shown that modern off-the-shelf SAT solvers could be effectively used to solve planning problems. In recent years, the power of SAT technology has been leveraged to planning (Rintanen 2012), making reduction into SAT competitive with heuristic search methods. Although a lot of work has been devoted to the encoding of plans in propositional logic, only a few works can be found in the literature on satisfiability based approaches to planning in domains that require numeric reasoning. This is probably due to the difficulty of efficiently handling at the same time numeric constraints and propositional formulas. Among the few works dealing with planning with resources are (Hoffmann 2003; Kautz and Walser 1999; Gerevini, Saetti, and Serina 2008; Hoffmann et al. 2007). There have also been some works using constraint and logic programming (Dovier, Formisano, and Pontelli 2010; Bartak and Toropila 2010). However, the advances in satisfiability modulo theories (SMT) (Barrett et al. 2009) in the last years make worth considering this alternative. With RANTANPLAN we demonstrate that with SMT one can elegantly handle numeric reasoning inside any PDDL domain, thanks to the integration of various background theories with a SAT solver. As the number of variables, and hence the search space, rapidly grows with the number of time steps considered, a key idea to improve the performance of SAT-based planners is to consider the possibility of executing several actions at the same time, i.e., the notion of parallel plans. Parallel plans increase the efficiency not only because they allow to reduce the time horizon, but also because it is unnecessary to consider all total orderings of the actions that are performed in parallel. Nevertheless, in SAT-based planning, parallel plans are not intended to represent true parallelism in time, and it is usually required that a sequential plan can be built from a parallel plan in polynomial time. Two main types of parallel plans are considered: ∀-step plans, and ∃step plans. In ∀-step plans, any ordering of parallel actions must result in a valid sequential plan. In ∃-step plans, there must exist a total ordering of parallel actions resulting in a valid sequential plan. We refer the reader to (Rintanen 2009; Rintanen, Heljanko, and Niemela 2006) for further details. RANTANPLAN supports ∀ and ∃-step plans, using various different encodings. To ensure that a parallel plan is sound, it is necessary that all actions proposed to be executed at the same time do not interfere. Different notions of interference have been defined, some more restrictive, some more relaxed. But, as far as we know, for efficiency reasons, potential interference between action is always determined statically, i.e., independently of any concrete state, hence in a fairly restrictive way. Moreover, very few works deal with the notion of incompatibility of actions in planning with resources, most of them with rather syntactic or limited semantic approaches (Kautz and Walser 1999; Fox and Long 2003; Gerevini, Saetti, and Serina 2008) RANTANPLAN incorporates a novel method for determining interference between actions at compile time, using an SMT solver as an oracle. Summing up, RANTANPLAN is a numeric planner based on planning as satisfiability, which translates PDDL problems into SMT formulas. It supports various types of parallelism, using a novel notion of interference. Experimental results show that it is competitive with other exact numeric planners and strictly better in non-trivial numeric domains.