Return to search

New Heuristics for Planning with Action Costs

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.

Identiferoai:union.ndltd.org:TDX_UPF/oai:www.tdx.cat:10803/7570
Date17 December 2010
CreatorsKeyder, Emil Ragip
ContributorsGeffner, Héctor, Universitat Pompeu Fabra. Departament de Tecnologies de la Informació i les Comunicacions
PublisherUniversitat Pompeu Fabra
Source SetsUniversitat Pompeu Fabra
LanguageEnglish
Detected LanguageEnglish
Typeinfo:eu-repo/semantics/doctoralThesis, info:eu-repo/semantics/publishedVersion
Formatapplication/pdf
SourceTDX (Tesis Doctorals en Xarxa)
Rightsinfo: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.0027 seconds