J.A.: Fast subgoaling for pathfinding via real-time search

Real-time heuristic search is a standard approach to pathfind-ing when agents are required to make decisions in a bounded, very short period of time. An assumption usually made in the development and evaluation of real-time algorithms is that the environment is unknown. Nevertheless, in many in-teresting applications such as pathfinding for automnomous characters in video games, the environment is known in ad-vance. Recent real-time search algorithms such as D LRTA* and kNN LRTA * exploit knowledge about the environment while pathfinding under real-time constraints. Key to those algorithms is the computation of subgoals in a preprocessing step. Subgoals are subsequently used in the online planning phase to obtain high-quality solutions. Preprocessing in those algorithms, however, requires significant computation. In this paper we propose a novel preprocessing algorithm that gener-ates subgoals using a series of backward search episodes car-ried out from potential goals. The result of a single backward search episode is a tree of subgoals that we then use while planning online. We show the advantages of our approach over state-of-the-art algorithms by carrying out experiments on standard real-time search benchmarks