Reconnection with the ideal tree: A new approach to real-time search

Nicolás Rivera, León Illanes, Jorge A. Baier, Carlos Hernández

Resultado de la investigación: Article

3 Citas (Scopus)

Resumen

Many 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 Τ. When the agent observes that an arc in the tree cannot be traversed in the actual environment, it removes such an arc from Τand then carries out a reconnection search whose objective is to find a path between the current state and any node in Τ. 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 path finding 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 path finding-specific navigation algorithm, outperforms FRIT(BFS) when planning time is extremely limited, but when given more time, the situation reverses.

Idioma originalEnglish
Páginas (desde-hasta)235-264
Número de páginas30
PublicaciónJournal of Artificial Intelligence Research
Volumen50
EstadoPublished - 1 ene 2014

Huella dactilar

Subroutines
Navigation
Robotics
Planning

ASJC Scopus subject areas

  • Artificial Intelligence

Citar esto

Rivera, Nicolás ; Illanes, León ; Baier, Jorge A. ; Hernández, Carlos. / Reconnection with the ideal tree : A new approach to real-time search. En: Journal of Artificial Intelligence Research. 2014 ; Vol. 50. pp. 235-264.
@article{b16d175683bb4d468fdb3793470e09d0,
title = "Reconnection with the ideal tree: A new approach to real-time search",
abstract = "Many 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 Τ. When the agent observes that an arc in the tree cannot be traversed in the actual environment, it removes such an arc from Τand then carries out a reconnection search whose objective is to find a path between the current state and any node in Τ. 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 path finding 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 path finding-specific navigation algorithm, outperforms FRIT(BFS) when planning time is extremely limited, but when given more time, the situation reverses.",
author = "Nicol{\'a}s Rivera and Le{\'o}n Illanes and Baier, {Jorge A.} and Carlos Hern{\'a}ndez",
year = "2014",
month = "1",
day = "1",
language = "English",
volume = "50",
pages = "235--264",
journal = "Journal of Artificial Intelligence Research",
issn = "1076-9757",
publisher = "Morgan Kaufmann Publishers, Inc.",

}

Reconnection with the ideal tree : A new approach to real-time search. / Rivera, Nicolás; Illanes, León; Baier, Jorge A.; Hernández, Carlos.

En: Journal of Artificial Intelligence Research, Vol. 50, 01.01.2014, p. 235-264.

Resultado de la investigación: Article

TY - JOUR

T1 - Reconnection with the ideal tree

T2 - A new approach to real-time search

AU - Rivera, Nicolás

AU - Illanes, León

AU - Baier, Jorge A.

AU - Hernández, Carlos

PY - 2014/1/1

Y1 - 2014/1/1

N2 - Many 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 Τ. When the agent observes that an arc in the tree cannot be traversed in the actual environment, it removes such an arc from Τand then carries out a reconnection search whose objective is to find a path between the current state and any node in Τ. 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 path finding 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 path finding-specific navigation algorithm, outperforms FRIT(BFS) when planning time is extremely limited, but when given more time, the situation reverses.

AB - Many 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 Τ. When the agent observes that an arc in the tree cannot be traversed in the actual environment, it removes such an arc from Τand then carries out a reconnection search whose objective is to find a path between the current state and any node in Τ. 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 path finding 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 path finding-specific navigation algorithm, outperforms FRIT(BFS) when planning time is extremely limited, but when given more time, the situation reverses.

UR - http://www.scopus.com/inward/record.url?scp=84902785962&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:84902785962

VL - 50

SP - 235

EP - 264

JO - Journal of Artificial Intelligence Research

JF - Journal of Artificial Intelligence Research

SN - 1076-9757

ER -