Online bridged pruning for real-time search with arbitrary lookaheads

Carlos Hernández Ulloa, Adi Botea, Jorge A. Baier, Vadim Bulitko

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

3 Citas (Scopus)

Resumen

Real-time search algorithms are relevant to timesensitive decision-making domains such as video games and robotics. In such settings, the agent is required to decide on each action under a constant time bound, regardless of the search space size. Despite recent progress, poor-quality solutions can be produced mainly due to state re-visitation. Different techniques have been developed to reduce such a re-visitation, with state pruning showing promise. In this paper, we propose a novel pruning approach applicable to the wide class of real-time search algorithms. Given a local search space of arbitrary size, our technique aggressively prunes away all states in its interior, possibly adding new edges to maintain the connectivity of the search space frontier. An experimental evaluation shows that our pruning often improves the performance of a base real-time search algorithm by over an order of magnitude. This allows our implemented system to outperform state-of-the-art real-time search algorithms used in the evaluation.

Idioma originalInglés
Título de la publicación alojada26th International Joint Conference on Artificial Intelligence, IJCAI 2017
EditorialInternational Joint Conferences on Artificial Intelligence
Páginas510-516
Número de páginas7
ISBN (versión digital)9780999241103
EstadoPublicada - 1 ene 2017
Evento26th International Joint Conference on Artificial Intelligence, IJCAI 2017 - Melbourne, Australia
Duración: 19 ago 201725 ago 2017

Conferencia

Conferencia26th International Joint Conference on Artificial Intelligence, IJCAI 2017
PaísAustralia
CiudadMelbourne
Período19/08/1725/08/17

Áreas temáticas de ASJC Scopus

  • Inteligencia artificial

Huella Profundice en los temas de investigación de 'Online bridged pruning for real-time search with arbitrary lookaheads'. En conjunto forman una huella única.

  • Citar esto

    Ulloa, C. H., Botea, A., Baier, J. A., & Bulitko, V. (2017). Online bridged pruning for real-time search with arbitrary lookaheads. En 26th International Joint Conference on Artificial Intelligence, IJCAI 2017 (pp. 510-516). International Joint Conferences on Artificial Intelligence.