Lifted Successor Generation Using Query Optimization Techniques

Augusto B. Corrêa, Florian Pommerening, Malte Helmert, Guillem Francès

PosterID: 48
picture_as_pdf PDF
library_books Poster
menu_book BibTeX
The standard PDDL language for classical planning uses several first-order features, such as schematic actions. Yet, most classical planners ground this first-order representation into a propositional one as a preprocessing step. While this simplifies the design of other parts of the planner, in several benchmarks the grounding process causes an exponential blowup that puts otherwise solvable tasks out of reach of the planners. In this work, we take a step towards planning with lifted representations. We tackle the successor generation task, a key operation in forward-search planning, directly on the lifted representation using well-known techniques from database theory. We show how computing the variable substitutions that make an action schema applicable in a given state is essentially a query evaluation problem. Interestingly, a large number of the action schemas in the standard benchmarks are acyclic conjunctive queries, for which query evaluation is tractable. Our empirical results show that our approach is competitive with the standard (grounded) successor generation techniques in a few domains and outperforms them on benchmarks where grounding is challenging or infeasible.

Session E2: Lifted Planning / Symbolic Planning / Submodularity
Canb 10/28/2020, 18:00 – 19:00
10/30/2020, 01:00 – 02:00
Paris 10/28/2020, 08:00 – 09:00
10/29/2020, 15:00 – 16:00
NYC 10/28/2020, 03:00 – 04:00
10/29/2020, 10:00 – 11:00
LA 10/28/2020, 00:00 – 01:00
10/29/2020, 07:00 – 08:00