Classical planning is the problem of finding a sequence of actions for
achieving a goal from an initial state assuming that actions have
deterministic effects. The most effective approach for finding such
plans is based on heuristic search guided by heuristics extracted
automatically from the problem representation. In this thesis, we
introduce alternative approaches for performing inference over the
structure of planning problems that do not appeal to heuristic
functions, nor to reductions to other formalisms such as SAT or
CSP. We show that many of the standard benchmark domains can be solved
with almost no search or a polynomially bounded amount of search, once
the structure of planning problems is taken into account. In certain
cases we can characterize this structure in terms of a novel width
parameter for classical planning. / Los problemas en planificación clásica consisten en encontrar la
secuencia de acciones que lleve a un agente a su objetivo desde un
estado inicial, asumiendo que los efectos de las acciones son
determinísticos. El enfoque más efectivo para encontrar dichos
planes es la búsqueda heurística, extrayendo de la
representación del problema de forma automática heurísticas que
guien la búsqueda. En esta tesis, introducimos enfoques
alternativos para realizar inferencias sobre la estructura del los
problemas de planificación, sin apelar a funciones heurísticas,
reducciones a SAT o CSP. Demostramos que la mayoría de
problemas estándares pueden ser resueltos casi sin búsqueda o con
una cantidad de búsqueda polinomialmente limitada, en algunos casos,
caracterizando la estructura de los problemas en término de un nuevo
parámetro de complejidad para la planificación clásica.
| Identifer | oai:union.ndltd.org:TDX_UPF/oai:www.tdx.cat:10803/101416 |
| Date | 07 December 2012 |
| Creators | Lipovetzky, Nir |
| Contributors | Geffner, Héctor, Universitat Pompeu Fabra. Departament de Tecnologies de la Informació i les Comunicacions |
| Publisher | Universitat Pompeu Fabra |
| Source Sets | Universitat Pompeu Fabra |
| Language | English |
| Detected Language | Spanish |
| Type | info:eu-repo/semantics/doctoralThesis, info:eu-repo/semantics/publishedVersion |
| Format | 152 p., application/pdf |
| Source | TDX (Tesis Doctorals en Xarxa) |
| Rights | info:eu-repo/semantics/openAccess, ADVERTIMENT. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs. |
Page generated in 0.0024 seconds