Muestra la distribución de disciplinas para esta publicación.
Publicaciones WoS (Ediciones: ISSHP, ISTP, AHCI, SSCI, SCI), Scopus, SciELO Chile.
| Indexado |
|
||
| DOI | |||
| Año | 2018 | ||
| Tipo | proceedings paper |
Citas Totales
Autores Afiliación Chile
Instituciones Chile
% Participación
Internacional
Autores
Afiliación Extranjera
Instituciones
Extranjeras
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.
| Ord. | Autor | Género | Institución - País |
|---|---|---|---|
| 1 | Sigurdson, Devon | Hombre |
Univ Alberta - Canadá
|
| 2 | Bulitko, Vadim | Hombre |
Univ Alberta - Canadá
|
| 3 | Yeoh, William | Hombre |
WASHINGTON UNIV - Estados Unidos
|
| 4 | HERNANDEZ-ULLOA, CARLOS MARCELO | Hombre |
Universidad Nacional Andrés Bello - Chile
|
| 5 | Koenig, Sven | Hombre |
Univ Southern Calif - Estados Unidos
|
| 6 | IEEE | Corporación |
| Agradecimiento |
|---|
| Devon Sigurdson and Vadim Bulitko appreciate support from NSERC and Nvidia. Carlos Hernandez 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. |