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. / 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.
| Identifer | oai:union.ndltd.org:TDX_UPF/oai:www.tdx.cat:10803/7570 |
| Date | 17 December 2010 |
| Creators | Keyder, Emil Ragip |
| 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 | English |
| Type | info:eu-repo/semantics/doctoralThesis, info:eu-repo/semantics/publishedVersion |
| Format | 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.0034 seconds