Creating planning portfolios with predictive models

• Autores: Isabel Rosario Cenamor Guijarro
• Directores de la Tesis: Fernando Fernández Rebollo (dir. tes.) , Tomás Eduardo de la Rosa Turbides (codir. tes.)
• Lectura: En la Universidad Carlos III de Madrid ( España ) en 2017
• Idioma: español
• Tribunal Calificador de la Tesis: María Araceli Sanchís de Miguel (presid.) , Álvaro Torralba Arias de Reyna (secret.) , Alessandro Saetti (voc.)
• Enlaces
  • Tesis en acceso abierto en: e-Archivo
• Resumen

  • Los portfolios de planificadores tienen un gran potencial ya que pueden aprovecharse de los diferentes planificadores automáticos, consiguiendo mejorar el rendimiento de un único planificador. Sin embargo, la creación de un portfolio no es una tarea sencilla, ya que para poder crear uno lo suficientemente bueno, hay que tratar tres problemas fundamentales. El primero de ellos es encontrar qué planificadores hay que seleccionar como componentes del mismo. La segunda es el tiempo que hay que asignar a cada planificador y, la última y no menos importante el orden en el que se tienen que ejecutar. Actualmente, estas configuraciones, en el estado del arte, se realizan a partir de los resultados obtenidos por los planificadores en una fase previa de entrenamiento con un conjunto de problemas y restricciones prefijado (tiempo, memoria, etc). Consiguiendo una configuración especifica tratando de optimizar una métrica. Idealmente, la mejor configuración posible consiste en asignar el tiempo suficiente al mejor planificador para cada tarea de planificación. Sin embargo, esta configuración no siempre es posible, y hay que recurrir a otras aproximaciones como asignar un tiempo fijo a una selección de planificadores. Ésta no es la única simplificación utilizada, existen otras técnicas más cercanas a la óptima, en las cuales se selecciona un planificador o varios en función de la tarea a resolver. Sin embargo, estos sistemas, denominados dinámicos, incluyen una escasa caracterización de las tareas de planificación.

    En esta tesis se parte de dos hipótesis. La primera de ellas es que existe un conjunto reducido de planificadores que maximiza la diversidad. La segunda de ellas consiste en la posibilidad de crear un conjunto de características lo suficientemente bueno para una tarea de planificación. La caracterización de las tareas de planificación puede estar basada en sus distintas representaciones, así como en sus paradigmas. La primera tarea es realizar un análisis basado en las métricas clásicas de planificación, como son problemas resueltos, calidad y tiempo para seleccionar un subconjunto de planificadores. Adicionalmente, proponemos como alternativa a estas métricas, una técnica multiobjetivo. Este criterio está basado en la dominancia de Pareto combinando las métricas de tiempo y calidad. Continuando con nuestras hipótesis es necesario crear un conjunto de características bien informado para la tarea de planificación. Estas características deben ser capaces de diferenciar adecuadamente por problema y para ello será necesario basarse en los distintos paradigmas de la planificación automática. Este grupo de características tienen que ser útiles para crear modelos predictivos. Estos modelos podrán darnos además de una selección de planificadores, una aproximación del tiempo asignado a cada componente y el orden de los mismos. Adicionalmente se presentarán una serie de estrategias para explotar el conocimiento obtenido con los modelos predictivos.

    En conclusión, se plantea y desarrolla un sistema para configurar porfolios de planificadores usando modelos predictivos en tres fases distintas. Una instanciación de este sistema fue el ganador de la competición internacional de planificación en el área de satisfacibilidad en el año 2014.