Abstract
This paper revisits a distributed, collective spatial clustering algorithm motivated by ants and points out its fundamental similarity to one of the most cited and earliest agent-based models. Based on this observation, a novel variant of the algorithm is proposed and its behavior and performance is studied.
The author acknowledges the support of the “Application Domain Specific Highly Reliable IT Solutions” project, which has been implemented with the support provided from the National Research, Development and Innovation Fund of Hungary, financed under the Thematic Excellence Programme TKP2020-NKA-06 (National Challenges Subprogramme) funding scheme. This research was also supported by the European Union within the framework of the Artificial Intelligence National Laboratory Program (grant id: RRF-2.3.1-21-2022-00004).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The algorithm is inspired by Thomas C. Schelling’s residential segregation model that studies residential segregation on an abstract 2D grid [5]. The model shows that moving decisions by residents, based on the similarity of nearest neighbors, will lead to highly segregated (i.e., spatially clustered) residential configurations, even when decision makers are highly tolerant.
- 2.
- 3.
For reference, the typical time-to-convergence on a \(15 \times 15\) grid with 10 agents was 1s on a Dell Latitude 5300 laptop with Intel(R) Core(TM) i7-8665U CPU @1.90GHz and 16GB RAM running 64 bit Windows.
References
Chakraborty, A., Kar, A.: Swarm Intelligence: A Review of Algorithms (2017). https://doi.org/10.1007/978-3-319-50920-4_19
Lones, M.A.: Mitigating Metaphors: A Comprehensible Guide to Recent Nature-Inspired Algorithms. SN COMPUT. SCI. 1, 49 (2020). https://doi.org/10.1007/s42979-019-0050-8
Beckers, Ralph, Goss, S., Deneubourg, J.-L., Pasteels, J.: Colony size, communication and ant foraging strategy. Psyche 96 (1989). https://doi.org/10.1155/1989/94279.
Dorigo, M., Birattari, M., Stutzle, T.: Ant colony optimization. IEEE Comput. Intell. Mag. 1(4), 28–39 (2006)
Schelling, T.C.: Micromotives and macrobehavior. Norton, New York (1978)
The powers and perils of using digital data to understand human behaviour (Editorial). Nature 595, 149–150 (2021). https://doi.org/10.1038/d41586-021-01736-y
Sendova-Franks, A.B., Scholes, S.R., Franks, N.R., Melhuish, C.: Brood sorting by ants: two phases and differential diffusion. Anim. Behav. 68(5), 1095–1106 (2004)
Bonabeau, E., Theraulaz, G., Fourcassié, V., Deneubourg, J.-L.: The Phase-Ordering Kinetics of Cemetery Organization in Ants. Santa Fe Institute, Working Papers. 57 (1998). https://doi.org/10.1103/PhysRevE.57.4568
Parunak, H.V.: “Go to the ant": engineering principles from natural multi-agent systems. Ann. Oper. Res. 75, 69–101 (1997)
Wilensky, U.: NetLogo (1999). https://ccl.northwestern.edu/netlogo/ Center for Connected Learning and Computer-Based Modeling, Northwestern University, Evanston, IL
Batty, M.: Spatial Entropy. Geograph. Anal. 6, 1–31 (1974). https://doi.org/10.1111/j.1538-4632.1974.tb01014.x
Wang, C., Zhao, H.: Spatial heterogeneity analysis: introducing a new form of spatial entropy. Entropy 20(6), 398 (2018). https://doi.org/10.3390/e20060398
Guo, Y., Jiang, C., Wu, T.-Y., Wang, A.: Mobile agent-based service migration in mobile edge computing. Int. J. Commun Syst. 34, e4699 (2021)
Sittón-Candanedo, I., Alonso, R.S., Corchado, J.M., Rodríguez-González, S., Casado-Vara, R.; A review of edge computing reference architectures and a new global edge proposal, Future Generation Computer Systems, vol. 99, 2019, pp. 278–294. https://doi.org/10.1016/j.future.2019.04.016
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Gulyás, L. (2022). Spatial Clustering by Schelling’s Ants. In: Bădică, C., Treur, J., Benslimane, D., Hnatkowska, B., Krótkiewicz, M. (eds) Advances in Computational Collective Intelligence. ICCCI 2022. Communications in Computer and Information Science, vol 1653. Springer, Cham. https://doi.org/10.1007/978-3-031-16210-7_47
Download citation
DOI: https://doi.org/10.1007/978-3-031-16210-7_47
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-16209-1
Online ISBN: 978-3-031-16210-7
eBook Packages: Computer ScienceComputer Science (R0)