Time-bounded best-first search for reversible and non-reversible search graphs
| dc.contributor.author | Hernández, Carlos | |
| dc.contributor.author | Baier, Jorge A. | |
| dc.contributor.author | Asín, Roberto | |
| dc.date.accessioned | 2023-09-28T22:33:13Z | |
| dc.date.available | 2023-09-28T22:33:13Z | |
| dc.date.issued | 2016-08 | |
| dc.description | Indexación: Scopus. | es |
| dc.description.abstract | 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. | es |
| dc.description.uri | https://jair.org/index.php/jair/article/view/11017 | |
| dc.identifier.citation | Journal of Artificial Intelligence Research. Open Access. Volume 56, Pages 547 - 57. 1 August 2016 | es |
| dc.identifier.doi | 10.1613/jair.5073 | |
| dc.identifier.issn | 1076-9757 | |
| dc.identifier.uri | https://repositorio.unab.cl/xmlui/handle/ria/53378 | |
| dc.language.iso | en | es |
| dc.publisher | AI Access Foundation | es |
| dc.subject | Search Graphs | es |
| dc.subject | Time-Bounded | |
| dc.subject | Search Algorithm | |
| dc.subject | Real-Time A | |
| dc.title | Time-bounded best-first search for reversible and non-reversible search graphs | es |
| dc.type | Artículo | es |
Archivos
Bloque original
1 - 1 de 1
Cargando...
- Nombre:
- Hernandez_Time-Bounded_Best-First_Search_for Reversible.pdf
- Tamaño:
- 720.22 KB
- Formato:
- Adobe Portable Document Format
- Descripción:
- TEXTO COMPLETO EN INGLÉS
Bloque de licencias
1 - 1 de 1
No hay miniatura disponible
- Nombre:
- license.txt
- Tamaño:
- 1.71 KB
- Formato:
- Item-specific license agreed upon to submission
- Descripción: