Structure and inference in classical planning

dc.contributor
Universitat Pompeu Fabra. Departament de Tecnologies de la Informació i les Comunicacions
dc.contributor.author
Lipovetzky, Nir
dc.date.accessioned
2013-02-04T13:17:58Z
dc.date.available
2013-02-04T13:17:58Z
dc.date.issued
2012-12-07
dc.identifier.uri
http://hdl.handle.net/10803/101416
dc.description.abstract
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.
eng
dc.description.abstract
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.
spa
dc.format.extent
152 p.
cat
dc.format.mimetype
application/pdf
dc.language.iso
eng
cat
dc.publisher
Universitat Pompeu Fabra
dc.rights.license
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.
dc.source
TDX (Tesis Doctorals en Xarxa)
dc.subject
Automated Planning
cat
dc.subject
Classical Planning
cat
dc.subject
Heuristic Search
cat
dc.subject
Artificial Intelligence
cat
dc.title
Structure and inference in classical planning
cat
dc.type
info:eu-repo/semantics/doctoralThesis
dc.type
info:eu-repo/semantics/publishedVersion
dc.subject.udc
62
cat
dc.contributor.authoremail
nir.lipovetzky@upf.edu
cat
dc.contributor.director
Geffner, Héctor
dc.embargo.terms
cap
cat
dc.rights.accessLevel
info:eu-repo/semantics/openAccess
dc.identifier.dl
B. 4561-2013
cat
dc.description.degree
Programa de doctorat en Tecnologies de la Informació i les Comunicacions


Documentos

tnl.pdf

1020.Kb PDF

Este ítem aparece en la(s) siguiente(s) colección(ones)