Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Búsqueda heurística en planificación basada en costes

De
272 pages

En los últimos años se han producido avances importantes en el mundo de la Planificación Automática. La Planificación Automática es una rama de la Inteligencia Artificial que se centra principalmente en el estudio de técnicas computacionales genericas para resolver tareas de planificación. Las tareas de planificación típicamente consisten en obtener un conjunto ordenado de acciones, cuya ejecución permite alcanzar unos objetivos determinados. La dificultad más importante que presentan este tipo de tareas es que su resolución tiene un coste computacional muy elevado. Por este motivo, muchos planificadores utilizan heurísticas para guiar su proceso de planificación. Actualmente, una de las técnicas con más éxito es la Búsqueda Heurística. Gran parte de la investigación en Planificación Automática se ha centrado en las técnicas desde un punto de vista teórico, utilizando dominios simplificados. Estas técnicas se han ido dotando de mecanismos que las hacen cada vez más capaces de trabajar con caracteristicas más cercanas al mundo real. Entre otras, una de estas características es que las acciones suelen tener un coste asociado. La incorporación de los costes de las acciones en la tarea de planificación da lugar a la Planificación Basada en Costes. El interés por la planificación basada en costes es relativamente reciente. Así, el estudio de distintas heurísticas y las relaciones entre ellas, y de su comportamiento, bien de forma aislada o combinada, con distintos algoritmos de búsqueda es bastante limitado. Esta tesis estudia técnicas de búsqueda heurística aplicadas a planificación basada en costes. Cuenta con una parte más teórica, en la que se ha generado una heurística numérica, se han adaptado a planificación basada en costes otras heurísticas, y se ha establecido un marco teórico general que permite comparar y definir heurísticas numéricas que pertenecen a una misma clase. Asimismo, se han propuesto una serie de algoritmos de búsqueda heurítica y algunas variantes de los mismos. En la parte más experimental se ha valorado el comportamiento de los algoritmos combinados con distintas heurísticas. Como resultado, se ha obtenido una combinación heurísticas-algoritmo con un comportamiento muy adecuado en planificación basada en costes.--------------------------------------------------------------------------------------------------------
Automated Planning has achieved significant progress in the last years. Automated Planning is the area of Artificial Intelligence that studies the computational techniques for solving planning tasks in a generic way. Planning tasks are tasks whose objective is to obtain an ordered set of actions such that, if applied, some objectives are reached. The most important difficulty for solving planning tasks is that their computational cost is very high. For this reason, most planners are endowed with heuristics to guide their search process. Currently, one of the most successful techniques for solving planning tasks is Heuristic Search. A great part of the research in Automated Planning have focussed on the techniques from a theoretical point of view, using simplified domains. Then, the techniques have been provided with mechanisms to be able of managing more real-world features. One such features is that, usually, actions in real-world have costs. When the action costs are incorporated in the planning task, the task is called Cost-Based Planning. The increment of the interest in Cost-Based Planning is relatively recent. Thus, the study of different heuristics, their relationships, and the behavior of such heuristics in combination with search algorithms is rather limited. This thesis studies different heuristic search techniques applied to Cost-Based Planning. From the theoretical point of view, it includes the development of a new heuristic, the adaptation of other heuristics from planning without costs, and a general theoretical framework for defining and comparing heuristics of the same class. In addition, several search algorithms and variants have been proposed for planning with action costs. From the empirical point of view, it has been performed several experiments in order to determine which combination of heuristics and algorithms are more adequate. As a result, we have obtained a heuristics-algorithm combination with very good performance.
Voir plus Voir moins

Universidad Carlos III de Madrid
TESIS DOCTORAL
Busqueda Heur stica en Planificaci on Basada en
Costes
aAutor: D . Raquel Fuentetaja Piz an
Directores: Dr. D. Daniel Borrajo Mill an y Dr. D. Carlos Linares L opez
Departamento de Informatica
Leganes, Junio 2010TESIS DOCTORAL
Busqueda Heur stica en Plani caci on Basada en Costes
aAutor: D . Raquel Fuentetaja Piz an
Directores: Dr. D. Daniel Borrajo Mill an y Dr. D. Carlos Linares L opez
Firma del Tribunal Cali cador:
Firma
Presidente:
Vocal:
Vocal:
Vocal:
Secretario:
Cali caci on:
Leganes, ................................... de 2010A mi madre
A mis chicos: Carlos y HectorAgradecimientos
Me gustar a dejar constancia de mi agradecimiento a todas las personas que me han
apoyado y ayudado en el desarrollo de esta tesis. En primer lugar a mis directores, Daniel
Borrajo y Carlos Linares, por todo lo que me han ensenado.~ Por el tiempo dedicado a
revisiones y reuniones. Por darme la oportunidad en empezar este trabajo y por ayudarme
a terminarlo. Por los esfuerzos en infundirme con anza en lo que hago, algo de lo que suelo
carecer.
A todos los que son y han sido miembros del grupo PLG. En especial, a Susana por su
amistad y apoyo. A Sergio por ser como es. Por nuestras charlas de planning camino a la
piscina. A Tom as. Yo tambien quiero ser como tu. Al nal, en ocasiones, hemos conseguido
no hablar de nodos. A Fernando, por sus consejos y su envidiable actitud. A Rocio, por
escucharme siempre. A Angel, por su enfoque positivo, y por usar mi plani cador.
A la gente del grupo de plani caci on en Barcelona, por su acogida y sus comentarios.
Especialmente a Emil Keyder, por prestarme sus dominios.
A los dem as companeros~ de la universidad que me faltan por mencionar. En especial a
Javier Carb o y a Agapito. Llevamos ya muchos cafes, que hacen que cada d a sea mejor.
Gracias por vuestros animos y por las conversaciones de pap as.
Tengo la suerte de contar con muy buenos amigos. Gracias a todos vosotros por vuestro
apoyo y por los ratos de evasi on que me regal ais. A M onica y a Gema. A las chicas de
Segovia y a los de Madrid. A Edu y Esther; y a mis companeros~ ponti cios.
Por supuesto, gracias a mi familia. A mi madre, por su fortaleza. Por ensenarme~ a mirar
hacia delante. A mi padre, por con ar en mi. A mi segunda madre, mi abuela Petra. El
mejor ejemplo que se puede tener. Por su entrega. Ojala estuvierais aqu . A mi hermano y
a Sonia. Gracias por vuestra cercan a y por todo lo que me dais.
Fin almente y siempre, a Hector y a mi hijo Carlos. No se que habr a hecho sin vosotros.Resumen
En los ultimos anos~ se han producido avances importantes en el mundo de la Plani -
caci on Autom atica. La Plani caci on Autom atica es una rama de la Inteligencia Arti cial
que se centra principalmente en el estudio de tecnicas computacionales genericas para re-
solver tareas de plani caci on. Las tareas de plani caci on t picamente consisten en obtener
un conjunto ordenado de acciones, cuya ejecuci on permite alcanzar unos objetivos determi-
nados. La di cultad m as importante que presentan este tipo de tareas es que su resoluci on
tiene un coste computacional muy elevado. Por este motivo, muchos plani cadores utilizan
heur sticas para guiar su proceso de plani caci on. Actualmente, una de las tecnicas con
m as exito es la Busque da Heur stica .
Gran parte de la investigaci on en Plani caci on Autom atica se ha centrado en las tecnicas
desde un punto de vista te orico, utilizando dominios simpli cados. Estas tecnicas se han ido
dotando de mecanismos que las hacen cada vez m as capaces de trabajar con caracter sticas
m as cercanas al mundo real. Entre otras, una de estas caracter sticas es que las acciones
suelen tener un coste asociado. La incorporaci on de los costes de las acciones en la tarea de
plani caci on da lugar a la Plani caci on Basada en Costes . El interes por la plani caci on
basada en costes es relativamente reciente. As , el estudio de distintas heur sticas y las
relaciones entre ellas, y de su comportamiento, bien de forma aislada o combinada, con
distintos algoritmos de busqueda es bastante limitado.
Esta tesis estudia tecnicas de busqueda heur stica aplicadas a plani caci on basada en
costes. Cuenta con una parte m as te orica, en la que se ha generado una heur stica numerica,
se han adaptado a plani caci on basada en costes otras heur sticas, y se ha establecido un
marco te orico general que permite comparar y denir heur sticas numericas que pertene-
cen a una misma clase. Asimismo, se han propuesto una serie de algoritmos de busqueda
heur stica y algunas variantes de los mismos. En la parte m as experimental se ha valorado el
comportamiento de los algoritmos combinados con distintas heur sticas. Como resultado, se
ha obtenido una combinaconi heur sticas-algoritmo con un comportamiento muy adecuado
en plani caci on basada en costes.

Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin