RT Dissertation/Thesis
T1 Creating planning portfolios with predictive models
A1 Cenamor Guijarro, Isabel Rosario
AB Sequential planning portfolios are very powerful in exploiting the complementarystrength of different automated planners: for each planning taskthere are one or more base planners that obtain the best solution. Therefore,the main challenge when building a planning portfolio is to ensure thata suitable planner be chosen and that it gets enough planning time. To solvethis problem we need firstly to define three elements. The first is the settingsor planning conditions: time, memory, or other constraints. The second oneis the set of base planners. And finally, a benchmark that provides us withknowledge on how the base planners will behave under the given settings,following some kind of inductive process. Ideally, if the previous elementsare correctly defined, when a new planning task arrives, an oracle will beable to tell which base planner to run and for how long. In practice, sinceno oracle exists, the challenge to choose a sub-set of base planners, is assigningthem a running time and deciding the order in which they are runto optimize a planning metric under the predefined settings. Many state-of-the-art portfolios might never achieve an optimal performance because theydo not select different planners for the different planning tasks. In addition,these static techniques typically assign a fixed running time to the selectedset of planners, independently of the task. besides, the old-fashioned dynamicportfolios present a poor characterization of the planning task anddo not have enough knowledge to predict an accurate portfolio configurationin many cases. The aforementioned drawbacks are intensified by thefact that there is an increasing number of planners available to choose from,although many of them are designed following similar approaches, so theyare expected to behave similarly.This dissertation is built on two main hypotheses. Firstly that the spaceof the base planners can be reduced just by selecting a subset of diverse orcomplementary planners; e.g. that there is a minimal set of planners thatensure that the optimal portfolio can be computed. Secondly, that planningtasks can be characterized, and that the difficulty in solving them can bemodelled as a function of these features. To evaluate the first hypothesis,we analyze different metrics that could be used to filter the initial set of baseplanners. Classical metrics such as coverage, quality or execution time havebeen chosen by different portfolios in the past. We demonstrate that theseselection methods may reduce the diversity of the portfolios, and proposean alternative method based on the Pareto dominance. We then carry outa profound analysis on previous planning task characterizations and show how we could exploit them in current planning paradigms. A group of very informative features are proposed to improve the current feature definition of the planning tasks. These features have enough knowledge to differentiateplanning tasks with similar \a priori" complexity. In this thesis wedemonstrate that the implicit knowledge can be exploited in the constructionof predictive models. These models estimate whether a base plannerwill be able to solve a given problem and, if so, how long it will take. Nevertheless,the predictive models are not perfect and sometimes provide wrong(or inaccurate) predictions. To solve this kind of problems, we propose differentportfolio strategies to combine the number of selected base plannersand their times. These strategies take into account the predefined settingsand the knowledge learned in previous phases.In conclusion, this thesis sets out a profound analysis of three differentmechanisms or steps to create planning portfolios with predictive models,including new proposals for developing: planner filtering, planning taskfeaturing, learning predictive models and portfolio construction strategies.One of the proposed portfolios was the winner of the Sequential SatisficingTrack of the International Planning Competition held in 2014
AB Los portfolios de planificadores tienen un gran potencial ya que puedenaprovecharse de los diferentes planificadores automáticos, consiguiendo mejorarel rendimiento de un único planificador. Sin embargo, la creación de unportfolio no es una tarea sencilla, ya que para poder crear uno lo suficientementebueno, hay que tratar tres problemas fundamentales. El primero deellos es encontrar qué planificadores hay que seleccionar como componentesdel mismo. La segunda es el tiempo que hay que asignar a cada planificadory, la última y no menos importante el orden en el que se tienen que ejecutar.Actualmente en el estado del arte, estas configuraciones, se realizan apartir de los resultados obtenidos por los planificadores en una fase previade entrenamiento con un conjunto de problemas y restricciones prefijado(tiempo, memoria, etc), consiguiendo una configuración específica tratandode optimizar una métrica. Idealmente, la mejor configuración posible consisteen asignar el tiempo suficiente al mejor planificador para cada tareade planificación. Sin embargo, esta configuración no siempre es posible, yhay que recurrir a otras aproximaciones como asignar un tiempo fijo a unaselección de planificadores. Ésta no es la única simplificación utilizada, existenotras técnicas más cercanas a la óptima, en las cuales se selecciona unplanificador o varios en función de la tarea a resolver. Sin embargo, estossistemas, denominados dinámicos, incluyen una escasa caracterización delas tareas de planificación.En esta tesis se parte de dos hipótesis. La primera de ellas es que existe unconjunto reducido de planificadores que maximiza la diversidad. La segundade ellas consiste en la posibilidad de crear un conjunto de descriptivos losuficientemente bueno para caracterizar la tarea de planificación. La caracterización de las tareas de planificación puede estar basada en sus distintasrepresentaciones, así como en sus paradigmas. La primera tarea es seleccionarun conjunto de planificadores; realizando un análisis basado en lasmétricas clásicas de planificación, como son problemas resueltos, calidady 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 combinandolas métricas de tiempo y calidad. Continuando con nuestras hip_otesis esnecesario crear un conjunto de características bien informado para la tareade planificación. Estas características deben ser capaces de diferenciar adecuadamentepor problema y para ello sería necesario basarse en los distintosparadigmas de la planificación automática. Este grupo de característicastienen que ser úutiles para crear modelos predictivos. Estos modelos podrándarnos además de una selección de planificadores, una aproximación deltiempo asignado a cada componente y el orden de los mismos. Adicionalmentese presentarán una serie de estrategias para explotar el conocimientoobtenido con los modelos predictivos.En conclusión, se plantea y desarrolla un sistema para configurar porfoliosde planificadores usando modelos predictivos en tres fases distintas. Unainstanciación de este sistema fue el ganador de la competición internacionalde planificación en el áarea de satisfacibilidad en el año 2014.
YR 2017
FD 2017-03
LK https://hdl.handle.net/10016/25125
UL https://hdl.handle.net/10016/25125
LA eng
NO Mención Internacional en el título de doctor
DS e-Archivo
RD 16 jun. 2024