New Heuristics for Planning with Action Costs
Mostra el registre complet Registre parcial de l'ítem
- dc.contributor.author Keyder, Emil Ragip
- dc.contributor.other Geffner, Héctor
- dc.contributor.other Universitat Pompeu Fabra. Departament de Tecnologies de la Informació i les Comunicacions
- dc.date.accessioned 2024-03-16T02:34:50Z
- dc.date.available 2024-03-16T02:34:50Z
- dc.date.issued 2011-04-12T16:36:42Z
- dc.date.issued 2011-02-10
- dc.date.issued 2010-12-17
- dc.date.issued 2011-02-10
- dc.date.modified 2024-03-15T10:58:07Z
- dc.description.abstract Classical planning is the problem of nding a sequence of actions that take an agent from an initial state to a desired goal situation, assuming deter- ministic outcomes for actions and perfect information. Satis cing planning seeks to quickly nd low-cost solutions with no guarantees of optimality. The most e ective approach for satis cing planning has proved to be heuristic search using non-admissible heuristics. In this thesis, we introduce several such heuristics that are able to take into account costs on actions, and there- fore try to minimize the more general metric of cost, rather than length, of plans, and investigate their properties and performance. In addition, we show how the problem of planning with soft goals can be compiled into a classical planning problem with costs, a setting in which cost-sensitive heuristics such as those presented here are essential.
- dc.description.abstract La plani caci on cl asica es el problema que consiste en hallar una secuencia de acciones que lleven a un agente desde un estado inicial a un objetivo, asum- iendo resultados determin sticos e informaci on completa. La plani caci on \satis cing" busca encontrar una soluci on de bajo coste, sin garant as de op- timalidad. La b usqueda heur stica guiada por heur sticas no admisibles es el enfoque que ha tenido mas exito. Esta tesis presenta varias heur sticas de ese g enero que consideran costes en las acciones, y por lo tanto encuentran soluciones que minimizan el coste, en lugar de la longitud del plan. Adem as, demostramos que el problema de plani caci on con \soft goals", u objetivos opcionales, se puede reducir a un problema de plani caci on clasica con costes en las acciones, escenario en el que heur sticas sensibles a costes, tal como las aqu presentadas, son esenciales.
- dc.description.abstract Programa de doctorat en Tecnologies de la Informació i les Comunicacions
- dc.format application/pdf
- dc.format application/pdf
- dc.identifier 978-84-694-2126-0
- dc.identifier http://www.tdx.cat/TDX-0210111-150546
- dc.identifier http://hdl.handle.net/10803/7570
- dc.identifier B.7617-2011
- dc.identifier.uri http://hdl.handle.net/10230/12060
- 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.source TDX (Tesis Doctorals en Xarxa)
- dc.subject.keyword unfolded hyperpath
- dc.subject.keyword STRIPS
- dc.subject.keyword Steiner tree
- dc.subject.keyword soft goal compilation
- dc.subject.keyword set-additive heuristic
- dc.subject.keyword soft goal
- dc.subject.keyword search
- dc.subject.keyword satisficing planning
- dc.subject.keyword relaxed plan heuristic
- dc.subject.keyword relaxed plan
- dc.subject.keyword relaxation
- dc.subject.keyword recursive conditioning
- dc.subject.keyword planning domain
- dc.subject.keyword planning
- dc.subject.keyword landmark
- dc.subject.keyword optimal planning
- dc.subject.keyword oversubscription
- dc.subject.keyword independence
- dc.subject.keyword independence assumption
- dc.subject.keyword inference
- dc.subject.keyword landmark heuristic
- dc.subject.keyword hypergraph
- dc.subject.keyword heuristic
- dc.subject.keyword heuristic search
- dc.subject.keyword graph
- dc.subject.keyword dtree
- dc.subject.keyword delete relaxation
- dc.subject.keyword cost
- dc.subject.keyword constraint satisfaction
- dc.subject.keyword conjunctive landmark
- dc.subject.keyword classical planning
- dc.subject.keyword complexity
- dc.subject.keyword choice variable
- dc.subject.keyword Bayesian network
- dc.subject.keyword additive heuristic
- dc.subject.keyword algorithm
- dc.subject.keyword AND/OR graph
- dc.subject.keyword action cost
- dc.subject.keyword 62
- dc.title New Heuristics for Planning with Action Costs
- dc.type info:eu-repo/semantics/doctoralThesis
- dc.type info:eu-repo/semantics/publishedVersion