Resumen de Propagación acotada en búsqueda heurística en tiempo real en entornos inicialmente desconocidos

Carlos Marcelo Hernández Ulloa

• Los problemas de búsqueda en donde el agente tiene un tiempo limitado para calcular una solución en un entorno inicialmente desconocido, no pueden ser abordados por mecanismo tradicionales de búsqueda heurística, Algunos problemas de este tipo son la planificación de rutas en: robots autónomos, personajes de juegos en tiempo real para ordenador y paquetes de información en redes de sensores.

  Esta tesis esta dedicada a resolver este tipo de problemas, mediante algoritmos de búsqueda heurística en tiempo real. Presentamos varios mecanismos genéricos que aplicados a algoritmos existentes, generan nuevos algoritmos. Los nuevos algoritmos que desarrollamos mejoran el rendimiento de las aproximaciones existentes. Estos se evalúan considerando varias medidas de desempeño, las más importantes son: el coste de la solución, el tiempo total de búsqueda y el tiempo por episodio de planificación. Las principales ideas que hemos desarrollado en la tesis son:

  Propagación acotada de cambios heurísticos con iteración de valores: Presentamos un mecanismo de aprendizaje de heurísticas basado en el método de iteración de valores de programación dinámica.

  Propagación acotada de cambios heurísticos sobre un espacio local: Presentamos un mecanismo de aprendizaje de heurísticas que mejora el mecanismo basado en iteración de valores.

  Combinación entre anticipación y propagación acotada: Presentamos un mecanismo que permite combinar anticipación con propagación acotada sobre un espacio local. Esta combinación mejora el coste de la solución aumentando el tiempo de planificación por paso.

  Anticipación y movimientos del agente: Analizamos distintas estrategias de movimiento del agente. Cada estrategia tiene un rendimiento distinto, el uso de una u otra dependerá de la medida de desempeño que más importe al usuario.

  Aplicaciones: Implementamos nuestros algoritmos en mapas extraídos de juegos en tiempo real comerciales para ordenador.