Improving cost and probability estimates using interaction

Resumen

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.