Translation-based approaches to Conformant Planning

Welcome to the UPF Digital Repository

Palacios Verdes, Héctor Luis. Translation-based approaches to Conformant Planning. 2009
http://hdl.handle.net/10230/11912
dc.contributor.author Palacios Verdes, Héctor Luis
dc.contributor.other Geffner, Héctor
dc.contributor.other Universitat Pompeu Fabra. Departament de Tecnologies de la Informació i les Comunicacions
dc.date.accessioned 2013-07-12T01:50:07Z
dc.date.available 2013-07-12T01:50:07Z
dc.date.issued 2009-12-03
dc.identifier.uri http://hdl.handle.net/10230/11912
dc.description.abstract Conformant planning is the problem of finding a sequence of actions for achieving a goal in the presence of uncertainty in the initial state and state transitions. While few practical problems are purely conformant, the ability to find conformant plans is needed in planning with observations where conformant situations are an special case and where relaxations into conformant planning yield useful heuristics. In this dissertation, we introduce new formulations for tackling the conformant planning problem with deterministic actions using translations. On the one hand, we propose a translation in propositional logic and two schemes for obtaning conformant plans for it, one based on boolean operations of projection and model counting, the other based on projection and satisfiability. On the other hand, we introduce translations of the conformant planning problem into classical problems that are solved by a modern and effective classical planner. We analyze the formal properties of the translations into classical planning and evaluate the performance of the resulting conformant planners.
dc.description.abstract La planificación conformante es el problema de encontrar una secuencia de acciones para lograr un objetivo en presencia de información incompleta sobre el estado inicial y en las transiciones entre estados. Aunque pocos problemas son de carácter puramente conformante, la posibilidad de encontrar planes conformantes es necesaria en planificación con observaciones, donde las situaciones conformantes son un caso particular, y donde las relajaciones a planificación conformante dan heurísticas útiles. En esta tesis atacamos el problema de la planificación conformante con acciones determinísticas mediante dos formulaciones basadas en traducciones. Por un lado, proponemos una traducción a lógica proposicional y dos esquemas para obtener planes conformantes a partir de ésta, uno basado en operaciones booleanas de projección y conteo de modelos, y otro basado en projección y satisfacción proposicional. Por otro lado, introducimos traducciones que permiten transformar un problema de planificación conformante en un problema de planificación clásica que es luego resuelto usando planificadores clásicos. También analizamos las propiedades formales de las traducciones y evaluamos el rendimiento de los planificadores obtenidos.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.publisher Universitat Pompeu Fabra
dc.rights 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.rights info:eu-repo/semantics/openAccess
dc.title Translation-based approaches to Conformant Planning
dc.date.modified 2013-07-10T11:42:20Z
dc.subject.keyword cnf
dc.subject.keyword ddnnf
dc.subject.keyword knowledge compilation
dc.subject.keyword planning
dc.subject.keyword classical planning
dc.subject.keyword planning under uncertainty
dc.subject.keyword conformant planning
dc.subject.keyword sat
dc.subject.keyword artificial
dc.subject.keyword intelligence
dc.subject.keyword computer science
dc.subject.keyword 62

See full text
http://hdl.handle.net/10803/7564

Search


Advanced Search

Browse

My Account

Statistics