Planning with different representations

Classical planning tasks are represented using a logical language. It is common to use a first-order representation, as this makes the description of the tasks more compact. Planners have long relied on translating these first-order representations into propositional ones in a process called grounding. Earlier work showed that grounding can improve the performance of classical planners. But this can also lead to exponentially larger encodings, and tasks with short plans become intractable simply because of the size of their representation.
In this thesis, we focus on lifted planning, which operates directly on the first-order representation. This bypasses the need for grounding, avoiding its computational overhead. We show how to build a lifted planner, called Powerlifted, that uses different techniques from database theory and logic programming to achieve state-of-the-art performance.
First, we show how to perform a state-space search over the lifted representation. We address the lifted successor generation problem and show that this is equivalent to solving conjunctive queries. By exploiting the acyclicity of conjunctive queries, Powerlifted can generate successors efficiently in many domains. Second, we show how to use Datalog to compute delete-relaxation heuristics, such as the additive and the FF heuristics, directly over the lifted representation. Finally, we show how to translate other state-of-the-art techniques, such as preferred operators and width search, from the ground to the lifted setting.
We then show that some ideas from our work on lifted planning can be carried over to the ground setting. Using techniques implemented in Powerlifted, we show how to improve the grounding algorithms commonly used by classical planners. This is significant, as grounding is a crucial phase of most classical planners developed over the last two decades. Our new algorithm uses the grounding via solving paradigm from answer set programming, in which the grounding of a problem is decoupled into several logic programs, which must be solved individually to produce the propositional representation. In our experiments, our method outperforms other commonly used grounders from the literature.
Finally, we propose an extension to the classical planning formalism allowing for object creation within action effects. In practice, we show that Powerlifted can support this fragment almost effortlessly and that lifted planners, in general, seem to be a good fit for planning with object creation. Our experimental results show that object creation does not add overhead to Powerlifted while allowing for more expressive planning formalisms.