Weighted real-time heuristic search
Loading...
Date
2013
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Multiplicar la función heurística por un peso mayor que uno es una conocida técnica en Búsqueda Heurística. Cuando se aplica a A* con una heurística admissible ella produce considerables ahorros de tiempo, a costo de sacrificar optimilidad de la solución. Pocos trabajos han estudiado la aplicabilidad de esta técnica a Búsqueda Heurística en Tiempo Real, un enfoque de búsqueda basado búsqueda heurística. En esta tesis, presentamos dos nuevos enfoques para usar pesos en Búsqueda Heurística en Tiempo Real. El primero, weighted lookahead, es una variante del existente enfoque de Shimbo e Ishida. El incorpora pesos a la fase de lookahead del algoritmo de Búsqueda en Tiempo Real. El segundo, weighted update, incorpora los pesos en las aristas del grafo de búsqueda durante la fase de learning. Ambas técnicas son aplicables a una amplia clase de algoritmos de Búsqueda en Tiempo Real. Acá las implementamos a LSS-LRTA*, obteniendo dos nuevos algoritmos.
Description
Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2013