Reconnection with the ideal tree : a new approach to real-time search
Loading...
Files
Date
2014
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
En esta tesis se presenta FRIT, un algoritmo simple que resuelve problemas de búsqueda determinística para un agente, en ambientes parcialmente conocidos bajo restricciones de tiempo estrictas. A diferencia de otros algoritmos de búsqueda heurística en tiempo real (BHTR), FRIT no busca el objetivo: busca un camino que conecte el estado actual con un árbol ideal T . El árbol tiene su raíz en el objetivo y se construye usando la heurística h. Si el agente observa que un arco en el árbol no existe en el ambiente real, lo saca de T y realiza una búsqueda de reconexión para encontrar un camino que lleve a cualquier estado en T . La búsqueda de reconexión se lleva a cabo por medio de otro algoritmo. Así, FRIT puede aplicarse sobre muchos algoritmos de búsqueda y si se trata de un algoritmo para BHTR, el algoritmo resultante puede serlo también. Por otro lado, mostramos que FRIT también puede usar un algoritmo de búsqueda ciega, resultando en un algoritmo que puede ser aceptable para aplicaciones con restricciones de tiempo estrictas (como videojuegos) y que incluso puede ser preferible a un algoritmo de BHTR.
Evaluamos el algoritmo en problemas estándares de búsqueda en grillas, incluyendo mapas de videojuegos y laberintos. Los resultados muestran que FRIT usado con RTAA*—un algoritmo de BHTR típico—es significativamente mejor que RTAA*, con mejoras de hasta un orden de magnitud bajo restricciones de tiempo estrictas. Además, FRIT(daRTAA*) supera a daRTAA*—el estado del arte en BHTR—y en promedio obtiene soluciones un 50% menos costosas usando el mismo tiempo total. Finalmente, FRIT usando búsqueda en amplitud obtiene soluciones de muy buena calidad y puede ser ideal para aplicaciones de videojuegos.
Description
Tesis (Master of Science in Enginnering)--Pontificia Universidad Católica de Chile, 2014