Dublin Core
Title
Reconnection with the ideal tree : a new approach to real-time search
Subject
620
Ingeniería
Programación heurística.
Procesamiento de datos en tiempo real.
Algoritmos computacionales.
Description
Tesis (Master of Science in Enginnering)--Pontificia Universidad Católica de Chile, 2014
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.
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.
Creator
Illanes Fontaine, León
Date
2014-05-19T03:27:51Z
2014-05-19T03:27:51Z
2014
Contributor
Baier Aranda, Jorge Andrés
Pontificia Universidad Católica de Chile. Escuela de Ingeniería
Rights
acceso abierto
Format
xii, 55 hojas
application/pdf
Language
en
Type
tesis de maestría
Identifier
10.7764/tesisUC/ING/2968
https://doi.org/10.7764/tesisUC/ING/2968
https://repositorio.uc.cl/handle/11534/2968