Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 13

Communication Papers of the 2017 Federated Conference on Computer Science and Information Systems

Collision-Free Agent Migration in Spatial Simulation

, , ,

DOI: http://dx.doi.org/10.15439/2017F172

Citation: Communication Papers of the 2017 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 13, pages 6573 ()

Full text

Abstract. Parallelization of agent-based models (ABMs) is one solution for scaling up their simulation size sufficiently covering more realistic problems. In order to break through memory limitation, some ABM simulators such as RepastHPC and FLAME enabled parallel simulation over a cluster system, (i.e. distributed memory). They visualize to agents remote processors' boundary data as ghost space or facilitate message broadcast among agents, so that agents can still share a full or partial view of their simulation space. Yet, ABMs encounter a parallelization problem where multiple agents may migrate to and thus collide with each other on the same logical coordinates, which should not occur in some applications, (e.g., traffic simulation where two vehicles cannot change to the same lane). Although such collision problems have been addressed algorithmically at a user level where an agent stops before or hops over another agent, moves faster or slower, ticks over time, or cuts coordinates finer, they yet require inter-agent synchronization such as serializing agent migration over all collision-inducing sub-spaces or cells, using a single thread. To facilitate collision-free agent migration more efficiently, we considered two migration algorithms named location-ordered and direction-ordered migration, and implemented them over three ABM simulators: Multi Agent Spatial Simulation (MASS), RepastHPC, and FLAME. This paper discusses about programmability and execution performance among these three simulators in collision-free agent migration.


  1. MATSim Homepage, “http://www.matsim.org, 2012.
  2. F. Kawasaki, “Accelerating large-scale simulations of coortical neuronal network development,” Master’s thesis, Master of Science in Computing and Software Systems, University of Washington, 2012.
  3. D. L. Chao, M. E. Halloran, V. J. Obenchain, and I. M. Longini Jr, “FluTE, a Publicly Available Stochastic Influenza Epidemic Simulation Model,” PLoS Computational Biology, vol. Vol.6, no. No.1, pp. 517–527, January 2010.
  4. M. Oryani, “Applying agent-based modeling to studying emergent behaviros of the immune system cells,” Master’s thesis, KTH Electrical Engineering, Stockholm, Sweden, May 2014.
  5. R. M. D’Souza, S. Marino, and D. Kirschner, “Data-parallel algorithms for agent-based model simulations of tuberculosis on graphics processing units,” in Proc. of Agent-Directed Symposium - ADS09. San Diego, CA: SCS, March 2009.
  6. Argonne National Laboratory, “Repast for High Performance Computing, http://repast.gifhub.io/repast hpc.html.”
  7. C. Geenough and M. Holcombe, “FLAME Flexible Large-scale Agent Modeling Environment, http://www.flame.ac.uk.
  8. A. U. K. Wagoum, B. Stefen, A. Seyfried, and M. Chraibi, “Parallel real time computation of large scale pedestrian evacuations,” Advances in Engineering Software, vol. Vol.60-61, pp. 98–103, 2013.
  9. J. Barceló, J. Ferrer, D. Garcća, and R. Grau, “Microscopic traffic simulation for att systems analysis. a parallel computing version,” in 25th Anniversary of CRT, August 1998.
  10. A. Kirchner, H. Klüpfel, K. Nishinari, A. Schadschneider, and M. Schreckenberg, “Discretization effects and the influence of walking speed in cellular automata models for pedestrian dynamics,” Journal of Statistical Mechanics: Theory and Experiment, vol. Vol.2004, no. No.10, p. P10011, October 2004.
  11. S. Bandini, L. Crociani, and G. Vizzari, “Towards a more comprehensive estimation of social costs in pedestrian facilities,” in Proc. of the Workshop on The Challenge of Ageing Society: Technological Roles and Opportunities for Artificial Intelligence in conjunction with the 13th Conference of the Italian Association for Artificial Intelligence, (AI*IA 2013), Turin, Italy, December 2013, p. paper 7.
  12. C. L. Barrett et al., “TRANSSIMS(TRansportation ANalysis SIMulation System) Volume 0 - Overview,” Los Alamos National Laboratory,” LA-UR-99-1658, May 28 1999.
  13. J. Epstein and R. Axtell, Growing artificial societies: social science from the bottom up. Brookings Institution Press, October 1996, p. 224.
  14. A. K. Dewdney, “Computer recreations sharks and fish wage an ecological war on the toroidal planet wa-tor,” Scientific American, pp. 14–22, December 1984.
  15. M. Fukuda, “MASS: A Parallelizing Library for Multi-Agent Spatial Simulation, http://depts.washington.edu/dslab/MASS.