Programación genética de heurísticas para planificación

Abstract

El objetivo de esta tesis doctoral es el diseño, construcción y sobre todo, experimentación de una herramienta de aprendizaje de conocimiento de control para planificación independiente del dominio basada en programación genética (PG). Genéricamente hablando, la planificación consiste en encontrar la secuencia de pasos (el plan) que hay que dar para que, partiendo de un estado inicial dado, se cumplan determinados objetivos. En general, encontrar un plan correcto para un problema determinado es un problema "NP-completo". Una solución propuesta por la lA a este problema es añadir conocimiento adicional (de control) al planificador utilizando técnicas de aprendizaje automático. Ninguno de los sistemas propuestos hasta el momento resuelven el problema de la planificación por completo (es decir, que el planificador resuelva todos los problemas, de la manera más eficiente posible, tanto en tiempo como en espacio, y obteniendo planes que maximicen determinadas medidas de calidad). Por ello existe todavía una fuerte motivación para proponer y estudiar nuevas técnicas que acerquen más a dicho objetivo. La motivación de utilizar PG es doble. Por un lado se pretende explorar el espacio de conocimiento de control de una manera menos sesgada que otros sistemas de aprendizaje automático. Además, se pretende que la búsqueda considere al planificador de una manera global, incluyendo la teoría del dominio, la búsqueda en el espacio de planificación y todas las consideraciones de eficiencia y eficacia al mismo tiempo. En segundo lugar, se pretende utilizar la flexibilidad con la que se pueden definir los sesgos de búsqueda en PG para añadir estos sesgos a otros sistemas de aprendizaje que no dispongan de ellos. En el caso de esta tesis, se utilizará PRODIGY4.0 como planificador base y HAMLET como método de aprendizaje al que se le quieren añadir algunas características y sesgos de búsqueda que no posee. Además del objetivo principal de la tesis (el aprendizaje de conocimiento de control con PG), se quiere diseñar y experimentar con métodos para añadir conocimiento de fondo a la PG sin modificar substancialmente su modo de funcionamiento. El primer método experimentado es el sembrado de la población inicial con individuos procedentes de otros sistemas de aprendizaje (éste es realmente el sistema multi-estrategia EVOCK-HAMLET). En segundo lugar, se ha diseñado un nuevo operador genético (el operador apoyado en ejemplos) que es capaz de utilizar ejemplos como punto de partida. Para comprobar la validez de los métodos propuestos, se ha realizado una fase experimental muy extensa seguida de validación estadística y análisis.

Abstract

The aim of this thesis is to design, build and valídate experimentally a genetic programming (PG) based method for learning control knowledge for a domain independent planner. Planning is the problem of finding a sequence of steps to transform an initial State in a final state for which several conditions are satisfied. Generally, finding a correct plan is NP-hard. The solution proposed by Artificial Intelligence (AI) is to augment a domain independent planner with control knowledge, to improve its efficiency. Machine learning techniques are used for that purpose. However, although a lot has been achieved, the domain independent planning problem has not been solved completely, therefore there is still room for research. The reason for using GP is twofold. First, it is intended for exploring the control knowledge space in a less biased way than other techniques. Besides, learning search should consider the planning system, the domain theory, planning search and efficiency measures in a global manner, all at the same time. Second, PG flexibility and independence of learning biases will be used to add useful biases and characteristic to other learning methods that lack them (that is, a multi-strategy GP based system). In the present work, PRODIGY4.0 will be used as the base planner and HAMLET will be used as the learning system to which useful characteristics will be added through GP. In addition to the main goal, this thesis will design and experiment with methods to add background knowledge to a GP system, without modifying its basic algorithm. The first method seeds the initial population with individuáis obtained by other methods (in this case, by HAMLET. Actually, this is the multi-strategy system discussed in the later paragraph). The second method uses a new genetic operator (instance based crossover) that is able to use instances as a starting point. To test the validity of the methods proposed, extensive empirical and statistical validation will be carried out.