Reconnecting with the Ideal Tree: An Alternative to Heuristic Learning in 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 search algorithm that searches for the goal that is not run to completion, due to time constraints. %After% such a search, a decision is made using the information that was% gathered during search. In this paper we present FRIT, a simple approach for %solving 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 emph{ideal tree} $C{T}$. %Such a% tree is rooted in the goal state and is built initially using the % heuristic $h$. When the agent observes that an arc in the tree cannot be traversed in the actual environment, it removes such an arc from $C{T}$ and then carries out a reconnection search whose objective is to find a path between the current state and any node in $C{T}$. The reconnection search is done using an algorithm that is passed as a parameter to FRIT. %As such, FRIT is a general framework that can be% applied to many search algorithms. 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 complete blind-search algorithm, which in some applications with tight time constraints (including video games) may be acceptable and, perhaps, preferred to a pure RTHS algorithm. We evaluate our approach over standard 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 and is perhaps the algorithm that should be preferred in video game applications.