Fast subgoaling for pathfinding via real-time search

Carlos Hernández, Jorge A. Baier

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

10 Citations (Scopus)


Real-time heuristic search is a standard approach to pathfinding 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 interesting applications such as pathfinding for automnomous characters in video games, the environment is known in advance. 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 generates subgoals using a series of backward search episodes carried 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.

Original languageEnglish
Title of host publicationICAPS 2011 - Proceedings of the 21st International Conference on Automated Planning and Scheduling
Number of pages4
Publication statusPublished - 2011
Event21st International Conference on Automated Planning and Scheduling, ICAPS 2011 - Freiburg, Germany
Duration: 11 Jun 201116 Jun 2011


Other21st International Conference on Automated Planning and Scheduling, ICAPS 2011

ASJC Scopus subject areas

  • Information Systems and Management


Dive into the research topics of 'Fast subgoaling for pathfinding via real-time search'. Together they form a unique fingerprint.

Cite this