Automatic planning is the branch of artificial intelligence that studies how to obtain an executable action plan (for example, by a robot) with a specific objective, within a formal model of functioning of the world, that is to say, of the effects and conditions of execution of the possible actions, of the goal for achieving, of the initial baseline state, etc.

Hector Geffner (ICREA), coordinator of the research group on Artificial Intelligence of the Department of Information and Communication Technologies (DTIC) at UPF, and Guillem Francès, PhD student of the same group, will be presenting at the IJCAI 2016 International Conference to be held in New York from 9 to 15 July, a study in which they highlight the importance of existential quantifiers in automatic planning. Existential quantifiers are logical elements that allow compactly indicating the existence of one or more elements that fulfil a given property.

They facilitate the modelling and a gain in computational efficiency

Francès and Geffner uphold that existential quantification is a component of modelling languages that has been inadequately supported by the current technology of automatic planning, especially bearing in mind the important role that existential quantification can have in terms of a link between automatic planning and the field of programming based on constraint satisfaction, one of the most successful branches of artificial intelligence.

The authors claim that “proper processing of the variables quantified existentially allows not just a more natural use of the technology of planning on the part of non-expert users, as they facilitate the modelling of numerous problems, but also a gain in computational efficiency”. In addition, properly processing existential variables provides more fluidity in planning problems that involve constraints.

The values of the variables must satisfy the constraints

In planning, the term constraint satisfaction is given to the process of finding a solution to a set of constraints imposed by the conditions and that must be met by the variables. Therefore, a plausible solution to a problem is the set of values acquired by the variables to satisfy all the constraints presented.  

In this work, Geffner and Francès explain how to do this and provide an original extension of the heuristics that are traditionally used in automatic planning based on constraint satisfaction techniques. In addition, this extension will allow adequately supporting existential quantification.

Reference work:

Guillem Francès, Hector Geffner (2016), “ E-STRIPS: Existential Quantification in Planning and Constraint Satisfaction”, Proceedings 25th International Joint Conference on Artificial Intelligence, 9-15 de juliol, Nova York (EUA).