Lifted Successor Generation using Query Optimization Techniques

Corrêa, Augusto B. and Pommerening, Florian and Helmert, Malte and Francès, Guillem. (2020) Lifted Successor Generation using Query Optimization Techniques. In: Proceedings of the 30th International Conference on Automated Planning and Scheduling (ICAPS 2020), 30. pp. 80-89.

[img] PDF - Accepted Version

Official URL: https://edoc.unibas.ch/78704/

Downloads: Statistics Overview


The standard PDDL language for classical planning uses sev eral 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 simpli fies the design of other parts of the planner, in several bench- marks 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 result in 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.
Faculties and Departments:05 Faculty of Science > Departement Mathematik und Informatik > Informatik > Artificial Intelligence (Helmert)
UniBasel Contributors:Blaas Corrêa, Augusto and Pommerening, Florian and Helmert, Malte and Francès Medina, Guillem
Item Type:Conference or Workshop Item, refereed
Conference or workshop item Subtype:Conference Paper
Publisher:AAAI Press
Note:Publication type according to Uni Basel Research Database: Conference paper
Related URLs:
edoc DOI:
Last Modified:29 Sep 2020 08:15
Deposited On:29 Sep 2020 08:15

Repository Staff Only: item control page