Approaching Generalized Planning using Deep Reinforcement Learning and Graph Neural Networks

Abstract

[ES] Uno de los grandes retos de la Inteligencia Artificial ha sido y sigue siendo la capacidad de inferir soluciones dadas instancias pequeñas de un problema, o incluso subproblemas, que puedan generalizar hacia otras de tamaño mayor. El objetivo de la Planificación Generalista en el campo de la Planificación Automática es, precisamente, encontrar principios generales válidos más allá de los datos que se han utilizado para encontrarlos.

En este trabajo, ofrecemos un acercamiento basado en Deep Reinforcement Learning (DRL), en el cual se ha intentado aprender una política capaz de resolver instancias de problemas complejos a partir del aprendizaje de la estructura subyacente del dominio con problemas más pequeños del mismo. Esto se ha conseguido utilizando una representación concreta de las tareas de planificación a través de un grafo, el cual codifica su estructura.

En particular, se han utilizado Graph Neural Networks (GNN), que son un tipo concreto de Red Neuronal capaz de trabajar directamente con grafos y que usa esta misma estructura para sacar la máxima información del problema. Con todo esto, se verá que la política aprendida gracias mediante las técnicas DRL y GNN generaliza bien hacia instancias de varios órdenes de magnitud superiores que con los que se había entrenado.

[EN] One of the greatest challenges of Artificial Intelligence has been and still is the ability to infer solutions from small problems or even subproblems that can generalize over larger instances. The goal of Generalized Planning in the field of Automated Planning is precisely to come up with general principles that are valid beyond the data used to infer such principles.

In this work, we offer a perspective based on Deep Reinforcement Learning (DRL), in which we try to learn a policy capable of solving complex planning problem instances by learning the underlying structure through small problems of the same domain. This is achieved by using an ideal representation of the planning tasks in the form of a graph that encodes their structure.

Particularly, we use Graph Neural Networks (GNN), which are a type of Neural Network capable of working directly on graphs and taking advantage of their structure to get the most out of the information. With all this, it will be shown that the policy learned by means of DRL and GNN generalizes well over instances of several orders of magnitude higher than those for which it has been trained.