%0 Journal Article 
%A Escudero Martín, Yolanda
%T Improving cost and probability estimates using interaction
%D 2016
%U http://hdl.handle.net/10017/25858
%X La planificación automática consiste en producir una colección de acciones o plan que lleven a un agente desde un estado inicial a un objetivo. Esta colección puede ser una secuencia simple o una secuencia más compleja parcialmente ordenada de acciones. Se denomina planificación clásica cuando se cuenta con información completa del problema y las acciones son deterministas. Durante los últimos años se han conseguido significativos avances en la planificación automática, siendo capaz de resolver problemas de considerable tamaño y complejidad. Sin embargo, este enfoque no es efectivo a la hora de resolver problemas reales ya que en este tipo de problemas pueden suceder eventos inesperados, la respuesta tras realizar una acción no se puede predecir y como consecuencia el estado actual del mundo no se conoce con certeza. Por lo tanto, la ejecución de un plan generado por un planificador clásico ante un problema de la vida real podría fallar al no tener en cuenta dichas contingencias. Cuando se cuenta con información incompleta del problema y/o las acciones no son deterministas se denomina planificación bajo incertidumbre. Tradicionalmente, estos enfoques hacen uso de Procesos de Markov para generar planes robustos, pero de alta sobrecarga computacional. Otros enfoques de planificación bajo incertidumbre hacen uso de planificación de contingencias, traducción del problema con incertidumbre a un problema determinista o determinization y replanificación para resolver problemas. En los últimos años, la planificación automática se ha sumado al área de estudio del reconocimiento de metas, el cual se puede interpretar como la operación inversa a la planificación ya que tiene como objetivo inferir la(s) meta(s) de un agente tras observar parcial o completamente las acciones llevadas a cabo por el mismo. Recientemente, se han aplicado técnicas de planificación para resolver problemas de reconocimiento de metas, pero este enfoque está todavía en sus comienzos. Problemas de planificación clásica, de planificación bajo incertidumbre y de reconocimiento de metas se pueden resolver mediante búsqueda heurística, una de las técnicas que más éxito ha tenido resolviendo estos problemas. Las funciones heurísticas más comunes en planificación automática calculan estimaciones de distancia en forma de coste o probabilidad de alcanzar el estado meta desde un estado actual particular. Se denominan heurísticas admisibles a aquellas que guían la búsqueda hacia soluciones óptimas. Es decir, que minimizan el coste o maximizan la probabilidad. Estas heurísticas, a pesar de producir una solución óptima, pueden no ser suficientemente informativas o ser de alto coste computacional. Por otro lado, se denominan heurísticas no admisibles a aquellas que generan soluciones subóptimas. Estas heurísticas pueden o no producir la solución óptima, pero son más informativas que las heurísticas admisibles y han demostrado tener un buen rendimiento en cuanto a tiempo y calidad de la solución. En esta tesis, se investiga sobre aquellas heurísticas en el estado del arte que consideran acciones con coste o acciones probabilísticas para calcular estimaciones de coste y estimaciones de probabilidad más precisas.   Para mejorar la precisión de las estimaciones de coste, se desarrolla una función heurística que lleva a cabo propagación de costes en un grafo de planificación. Estas estimaciones son más exactas gracias al uso de Interaction, término que permite calcular la relación de independencia, de sinergia o de exclusión mutua entre pares de elementos. Estas estimaciones de coste se utilizan para (1) guiar a un planificador clásico hacia soluciones que minimizan el coste, (2) guiar a un planificador probabilístico hacia soluciones que maximizan la probabilidad y (3) resolver eficientemente problemas de reconocimiento de metas. Para mejorar la precisión de las estimaciones de probabilidad, se desarrolla un novedoso enfoque que lleva a cabo propagación de probabilidades en un grafo de planificación. Esta propagación de probabilidades es más avanzada que la previa ya que considera (1) la probabilidad global de cada proposición entre los posibles efectos de cada acción probabilística y (2) la dependencia de pares de proposiciones entre los posibles efectos de una acción probabilística. La unión de ambas técnicas permite calcular estimaciones de probabilidad más exactas y así generar soluciones de alta probabilidad de éxito. Como resultado de este estudio se obtiene una familia de heurísticas que calculan aproximaciones de coste y aproximaciones de probabilidad más exactas y constantes que otras heurísticas del estado del arte.
%K Planificación automática
%K Algoritmos heurísticos
%K Planificación automática
%K Informática
%K Computer science
%~ Biblioteca Universidad de Alcala