Time-Bounded Best-First Search for Reversible and Non-reversible Search Graphs

Simple item page
dc.contributor.authorHernandez, Carlos
dc.contributor.authorBaier, Jorge A.
dc.contributor.authorAsin, Roberto
dc.date.accessioned2025-01-23T21:27:19Z
dc.date.available2025-01-23T21:27:19Z
dc.date.issued2016
dc.description.abstractTime-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 execution. 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-BoundedWeighted A* (TB R (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-BoundedWeighted A* (TB(WA*)), an instance of TB(BFS). Furthermore, we prove TB R (WA*), under reasonable conditions, terminates. We evaluate TB(WA) in both grid pathfinding and the 15-puzzle. In addition, we evaluate TB R (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 TB R (WA*) improves as the weight parameter is increased. In addition, our time-bounded algorithms almost always outperform LSS-LRTWA* by a significant margin.
dc.description.funderFondecyt
dc.fuente.origenWOS
dc.identifier.eissn1943-5037
dc.identifier.issn1076-9757
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/101378
dc.identifier.wosidWOS:000396194500001
dc.language.isoen
dc.pagina.final571
dc.pagina.inicio547
dc.revistaJournal of artificial intelligence research
dc.rightsacceso restringido
dc.subject.ods11 Sustainable Cities and Communities
dc.subject.odspa11 Ciudades y comunidades sostenibles
dc.titleTime-Bounded Best-First Search for Reversible and Non-reversible Search Graphs
dc.typeartículo
dc.volumen56
sipa.indexWOS
sipa.trazabilidadWOS;2025-01-12
Files
Collections
Artículos de revistas