Fast subgoaling for pathfinding via real-time search

Carlos Hernández, Jorge A. Baier

Resultado de la investigación: Contribución a los tipos de informe/libroContribución a la conferenciarevisión exhaustiva

12 Citas (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.

Idioma originalInglés
Título de la publicación alojadaICAPS 2011 - Proceedings of the 21st International Conference on Automated Planning and Scheduling
Número de páginas4
EstadoPublicada - 2011
Evento21st International Conference on Automated Planning and Scheduling, ICAPS 2011 - Freiburg, Alemania
Duración: 11 jun. 201116 jun. 2011


Otros21st International Conference on Automated Planning and Scheduling, ICAPS 2011

Áreas temáticas de ASJC Scopus

  • Gestión y sistemas de información


Profundice en los temas de investigación de 'Fast subgoaling for pathfinding via real-time search'. En conjunto forman una huella única.

Citar esto