Novel approaches for generalized planning

Abstract

Classical planning is the problem of finding a sequence of actions, from a given initial state to some goal state. While, in generalized planning, a plan is a solution to a set of planning problems, which belong to the same class. In this thesis we explore novel ways of computing generalized plans, inductively from a set of examples, and deductively from a model of actions. First we present an extension of planning programs, as a representation of a generalized plan, which is induced from a set of examples. The extension, allows for modeling of classification tasks. This work also introduces a novel domain-independent algorithm for generating hierarchical task networks directly from the action model and one representative instance of the planning problem. We also present the optimizations used by the translation and show that the algorithm is competitive with the state-of-the-art algorithms.

La planificació clàssica és un problema que consisteix en trobar una seqüència d’accions, que va des d’un estat inicial fins un objectiu. Per una altra banda en planificació general, un plà és una solució a un conjunt de problemes de planificació els quals pertanyen a una mateixa classe. En aquesta tesi explorem camins nous per obtenir plans generals de forma inductiva sobre un conjunt d’exemples, i de forma deductiva sobre un model d’accions. Primer presentem una extensió per programes de planificació, com una representació d’un plà general, el qual és induït d’un conjunt d’exemples. L’extensió permet modelar una tasca de classificació. Aquest treball també introdueix un nou algorisme, que és independent de domini, que genera una xarxa de tasques jeràrquiques directament d’un model d’accions i d’una instància d’un problema de planificació. També presentem les optimitzacions utilitzades en la traducció i mostrem que aquest algorisme és competitiu amb l’estat de l’art.