Publication: Búsqueda heurística en planificación basada en costes
Loading...
Identifiers
Publication date
2010-06
Defense date
2010-06-01
Authors
Tutors
Journal Title
Journal ISSN
Volume Title
Publisher
Impact
Export
Abstract
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.
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.
Description
Keywords
Planificación automática, Búsqueda heurística, Planificación basada en costes