Time-bounded best-first search for reversible and non-reversible search graphs
Cargando...
Archivos
Fecha
2016-08
Profesor/a Guía
Facultad/escuela
Idioma
en
Título de la revista
ISSN de la revista
Título del volumen
Editor
AI Access Foundation
Nombre de Curso
Licencia CC
Licencia CC
Resumen
Time-Bounded A* is a real-time, single-agent, deterministic search algorithm that expands
states of a graph in the same order as A* does, but that unlike A* interleaves search and action exe cution. Known to outperform state-of-the-art real-time search algorithms based on Korf’s Learning
Real-Time A* (LRTA*) in some benchmarks, it has not been studied in detail and is sometimes not
considered as a “true” real-time search algorithm since it fails in non-reversible problems even it
the goal is still reachable from the current state. In this paper we propose and study Time-Bounded
Best-First Search (TB(BFS)) a straightforward generalization of the time-bounded approach to any
best-first search algorithm. Furthermore, we propose Restarting Time-Bounded Weighted A* (TBR
(WA*)), an algorithm that deals more adequately with non-reversible search graphs, eliminating
“backtracking moves” and incorporating search restarts and heuristic learning. In non-reversible
problems we prove that TB(BFS) terminates and we deduce cost bounds for the solutions returned
by Time-Bounded Weighted A* (TB(WA*)), an instance of TB(BFS). Furthermore, we prove TBR
(WA*), under reasonable conditions, terminates. We evaluate TB(WA) in both grid pathfinding and
the 15-puzzle. In addition, we evaluate TBR (WA*) on the racetrack problem. We compare our
algorithms to LSS-LRTWA*, a variant of LRTA* that can exploit lookahead search and a weighted
heuristic. A general observation is that the performance of both TB(WA*) and TBR (WA*) im proves as the weight parameter is increased. In addition, our time-bounded algorithms almost
always outperform LSS-LRTWA* by a significant margin.
Notas
Indexación: Scopus.
Palabras clave
Search Graphs, Time-Bounded, Search Algorithm, Real-Time A
Citación
Journal of Artificial Intelligence Research. Open Access. Volume 56, Pages 547 - 57. 1 August 2016
DOI
10.1613/jair.5073