Colección SciELO Chile

Departamento Gestión de Conocimiento, Monitoreo y Prospección
Consultas o comentarios: productividad@anid.cl
Búsqueda Publicación
Búsqueda por Tema Título, Abstract y Keywords



Multi-Agent Pathfinding with Real-Time Heuristic Search
Indexado
Scopus SCOPUS_ID:85056868019
DOI 10.1109/CIG.2018.8490436
Año 2018
Tipo

Citas Totales

Autores Afiliación Chile

Instituciones Chile

% Participación
Internacional

Autores
Afiliación Extranjera

Instituciones
Extranjeras


Abstract



Multi-agent pathfinding, namely finding collision-free paths for several agents from their given start locations to their given goal locations on a known stationary map, is an important task for non-player characters in video games. A variety of heuristic search algorithms have been developed for this task. Non-real-time algorithms, such as Flow Annotated Replanning (FAR), first find complete paths for all agents and then move the agents along these paths. However, their searches are often too expensive. Real-time algorithms have the ability to produce the next moves for all agents without finding complete paths for them and thus allow the agents to move in real time. Real-time heuristic search algorithms have so far typically been developed for single-agent pathfinding. We, on the other hand, present a real-time heuristic search algorithm for multi-agent pathfinding, called Bounded Multi-Agent A∗ (BMAA∗), that works as follows: Every agent runs an individual real-time heuristic search that updates heuristic values assigned to locations and treats the other agents as (moving) obstacles. Agents do not coordinate with each other, in particular, they neither share their paths nor heuristic values. We show how BMAA∗ can be enhanced by adding FAR-style flow annotations and allowing agents to push other agents temporarily off their goal locations, when necessary. In our experiments, BMAA∗ has higher completion rates and lower completion times than FAR.

Revista



Revista ISSN
2325-4270

Métricas Externas



PlumX Altmetric Dimensions

Muestra métricas de impacto externas asociadas a la publicación. Para mayor detalle:

Disciplinas de Investigación



WOS
Sin Disciplinas
Scopus
Sin Disciplinas
SciELO
Sin Disciplinas

Muestra la distribución de disciplinas para esta publicación.

Publicaciones WoS (Ediciones: ISSHP, ISTP, AHCI, SSCI, SCI), Scopus, SciELO Chile.

Colaboración Institucional



Muestra la distribución de colaboración, tanto nacional como extranjera, generada en esta publicación.


Autores - Afiliación



Ord. Autor Género Institución - País
1 Sigurdson, Devon Hombre University of Alberta - Canadá
2 Bulitko, Vadim Hombre University of Alberta - Canadá
3 Yeoh, William Hombre Washington University in St. Louis - Estados Unidos
4 Hernandez, Carlos Hombre Universidad Nacional Andrés Bello - Chile
5 Koenig, Sven Hombre Universidad Nacional Andrés Bello - Chile

Muestra la afiliación y género (detectado) para los co-autores de la publicación.

Financiamiento



Fuente
National Science Foundation
Natural Sciences and Engineering Research Council of Canada
Fondo Nacional de Desarrollo Científico, Tecnológico y de Innovación Tecnológica
Fondo Nacional de Desarrollo Científico, Tecnológico y de Innovación Tecnológica

Muestra la fuente de financiamiento declarada en la publicación.

Agradecimientos



Agradecimiento
ACKNOWLEDGMENTS Devon Sigurdson and Vadim Bulitko appreciate support from NSERC and Nvidia. Carlos Hernández was partially funded by Fondecyt grant number 1161526. Sven Koenig was supported by the National Science Foundation (NSF) under grant numbers 1724392, 1409987 and 1319966 as well as a gift from Amazon. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the sponsoring organizations, agencies or the U.S. government.

Muestra la fuente de financiamiento declarada en la publicación.