Reconnection with the Ideal Tree: A New Approach to Real-Time Search

Simple item page
dc.contributor.authorRivera, Nicolas
dc.contributor.authorIllanes, Leon
dc.contributor.authorBaier, Jorge A.
dc.contributor.authorHernandez, Carlos
dc.date.accessioned2025-01-23T21:43:35Z
dc.date.available2025-01-23T21:43:35Z
dc.date.issued2014
dc.description.abstractMany applications, ranging from video games to dynamic robotics, require solving single-agent, deterministic search problems in partially known environments under very tight time constraints. Real-Time Heuristic Search (RTHS) algorithms are specifically designed for those applications. As a subroutine, most of them invoke a standard, but bounded, search algorithm that searches for the goal. In this paper we present FRIT, a simple approach for single-agent deterministic search problems under tight constraints and partially known environments that unlike traditional RTHS does not search for the goal but rather searches for a path that connects the current state with a so-called ideal tree T. When the agent observes that an arc in the tree cannot be traversed in the actual environment, it removes such an arc from T and then carries out a reconnection search whose objective is to find a path between the current state and any node in T. The reconnection search is done using an algorithm that is passed as a parameter to FRIT. If such a parameter is an RTHS algorithm, then the resulting algorithm can be an RTHS algorithm. We show, in addition, that FRIT may be fed with a (bounded) complete blind-search algorithm. We evaluate our approach over grid pathfinding benchmarks including game maps and mazes. Our results show that FRIT, used with RTAA*, a standard RTHS algorithm, outperforms RTAA* significantly; by one order of magnitude under tight time constraints. In addition, FRIT(daRTAA*) substantially outperforms daRTAA*, a state-of-the-art RTHS algorithm, usually obtaining solutions 50% cheaper on average when performing the same search effort. Finally, FRIT(BFS), i.e., FRIT using breadth-first-search, obtains best-quality solutions when time is limited compared to Adaptive A* and Repeated A*. Finally we show that Bug2, a pathfinding-specific navigation algorithm, outperforms FRIT(BFS) when planning time is extremely limited, but when given more time, the situation reverses.
dc.description.funderFondecyt Project
dc.fuente.origenWOS
dc.identifier.eissn1943-5037
dc.identifier.issn1076-9757
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/101679
dc.identifier.wosidWOS:000339310900001
dc.language.isoen
dc.pagina.final264
dc.pagina.inicio235
dc.revistaJournal of artificial intelligence research
dc.rightsacceso restringido
dc.subject.ods11 Sustainable Cities and Communities
dc.subject.odspa11 Ciudades y comunidades sostenibles
dc.titleReconnection with the Ideal Tree: A New Approach to Real-Time Search
dc.typeartículo
dc.volumen50
sipa.indexWOS
sipa.trazabilidadWOS;2025-01-12
Files
Collections
Artículos de revistas