∃-STRIPS: existential quantification in planning and constraint satisfaction

Francès, Guillem; Geffner, Héctor

∃-STRIPS: existential quantification in planning and constraint satisfaction

Citation

Francès G, Geffner H. ∃-STRIPS: existential quantification in planning and constraint satisfaction. In: Kambhampati S, editor. Twenty-Fifth International Joint Conference on Artificial Intelligence; 2016 Jul 9-15; New York, NY. Palo Alto (CA): AAAI Press / IJCAI; 2016. p. 3082-8.

Abstract

Existentially quantified variables in goals and action preconditions are part of the standard PDDL planning language, yet few planners support them, while those that do compile them away at an exponential cost. In this work, we argue that existential variables are an essential feature for representing and reasoning with constraints in planning, and that it is harmful to compile them away or avoid them altogether, since this hides part of the problem structure that can be exploited computationally. We show how to do this by formulating an extension of the standard delete-relaxation heuristics that handles existential variables. While this extension is simple, the consequences for both modeling and computation are important. Furthermore, by allowing existential variables in STRIPS and treating them properly, CSPs can be represented and solved in a direct manner as action-less,fluent-less STRIPS planning problems, something important for problems involving restrictions. In addition, functional fluents in Functional STRIPS can be compiled away with no effect on the structure and informativeness of the resulting heuristic. Experiments are reported comparing our native ∃-STRIPS planner with state-of-the-art STRIPS planners over compiled and propositional encodings, and with a Functional STRIPS planner.

Description

Comunicació presentada a la Twenty-Fifth International Joint Conference on Artificial Intelligence, celebrada els dies 9 a 15 de juliol de 2016 a Nova York.