Paper:
Statistical Exploration of Distributed Pattern Formation Based on Minimalistic Approach
Yuichiro Sueoka, Takamasa Tahara, Masato Ishikawa, and Koichi Osuka
Osaka University
2-1 Yamada-oka, Suita, Osaka 565-0871, Japan
In this paper, we discuss the pattern formation of objects that can be stacked and transported by distributed autonomous agents. Inspired by the social behavior of termite colonies, which often build elaborate three-dimensional structures (nest towers), this paper explores the mechanism of termite-like agents through a computational and minimalistic approach. We introduce a cellular automata model (i.e., spatially discretized) for the agents and the objects they can transport, where each agent follows a “rule” determined by the assignment of fundamental actions (move/ load/ unload) based on the state of its neighboring cells. To evaluate the resulting patterns from the viewpoint of structural complexity and agent effort, we classify the patterns using the Kolmogorov dimension and higher-order local autocorrelation, two well-known statistical techniques in image processing. We find that the Kolmogorov dimension provides a good metric for the structural complexity of a pattern, whereas the higher-order local autocorrelation is an effective means of identifying particular local patterns.
- [1] M. Duarte et al., “Evolution of Collective Behaviors for a Real Swarm of Aquatic Surface Robots,” PLoS ONE, Vol.11, No.3, e0151834, 2016.
- [2] L. Bayındır, “A Review of Swarm Robotics Tasks,” Neurocomputing, Vol.172, pp. 292-321, 2016.
- [3] E. Şahin, “Swarm Robotics: From Sources of Inspiration to Domains of Application,” E. Şahin and W. M. Spears (Eds.), “Swarm Robotics: Lecture Notes in Computer Science,” Vol.3342, pp. 10-20, Springer, 2005.
- [4] M. Brambilla, E. Ferrante, M. Birattari, and M. Dorigo, “Swarm Robotics: A Review from the Swarm Engineering Perspective,” Swarm Intelligence, Vol.7, No.1, pp. 1-41, 2013.
- [5] J. Werfel, K. Petersen, and R. Nagpal, “Designing Collective Behavior in a Termite-Inspired Robot Construction Team,” Science, Vol.343, No.6172, pp. 754-758, 2014.
- [6] K. Nakayama, Y. Sueoka, M. Ishikawa, Y. Sugimoto, and K, Osuka, “Control of transportation trails by distributed autonomous agents inspired by the foraging behavior of ants,” J. of Nonlinear Theory and Its Applications, Vol.5, No.4, pp. 487-498, 2014.
- [7] D. M. Gordon, “Ants at Work: How an Insect Society Is Organized,” Simon and Schuster, 1999.
- [8] M. Hansell, “Built by Animals: The Natural History of Animal Architecture,” Oxford University Press, 2009.
- [9] N. Mizumoto, K. Kobayashi, and K. Matsuura, “Emergence of intercolonial variation in termite shelter tube patterns and prediction of its underlying mechanism,” R. Soc. Open Sci., Vol.2, No.11, 150360, 2015.
- [10] S. Garnier et al., “Aggregation Behaviour as a Source of Collective Decision in a Group of Cockroach-like-robots,” Proc. of European Conf. on Artificial Life, pp. 169-178, 2005.
- [11] S. Nolfi and D. Floreano, “Evolutionary Robotics: The Biology, Intelligence, and Technology of Self-Organizing Machines,” MIT Press, 2000.
- [12] S. Murata, E. Yoshida, A. Kamimura, H. Kurokawa, K. Tomita, and S. Kokaji, “M-TRAN: Self-reconfigurable modular robotic system,” IEEE/ASME Trans. on Mechatronics, Vol.7, No.4, pp. 431-441, 2002.
- [13] H. Kurokawa, K. Tomita, A. Kamimura, E. Yoshida, S. Kokaji, and S. Murata, “Distributed self-reconfiguration control of modular robot M-TRAN,” 2005 IEEE Int. Conf. Mechatronics and Automation, Vol.1, pp. 254-259, 2005.
- [14] H. Kurokawa, K. Tomita, A. Kamimura, S. Kokaji, T. Hasuo, and S. Murata, “Distributed self-reconfiguration of M-TRAN III modular robotic system,” The Int. J. of Robotics Research, Vol.27, Nos.3-4, pp. 373-386, 2008.
- [15] K. Petersen, R. Nagpal, and J. Werfel, “TERMES: An autonomous robotic system for three-dimensional collective construction,” H. Durrant-Whyte, N. Roy, and P. Abbeel (Eds.), “Robotics: Science and Systems VII,” p. 384, MIT Press, 2011.
- [16] J. Werfel, K. Petersen, and R. Nagpal, “Distributed multi-robot algorithms for the TERMES 3d collective construction system,” Proc. of Robotics: Science and Systems VII, 2011.
- [17] M. Rubenstein et al., “Programmable self-assembly in a thousand-robot swarm,” Science, Vol.345, No.6198, pp. 795-799, 2014.
- [18] T. Yasuda and K. Ohkura, “Sharing Experience for Behavior Generation of Real Swarm Robot Systems Using Deep Reinforcement Learning,” J. Robot. Mechatron., Vol.31, No.4, pp. 520-525, 2019.
- [19] M. Hiraga and K. Ohkura, “Effects of Congestion on Swarm Performance and Autonomous Specialization in Robotic Swarms,” J. Robot. Mechatron., Vol.31, No.4, pp. 526-534, 2019.
- [20] S. Wolfram, “Cellular Automata and Complexity: Collected Papers,” Westview Press, 1994.
- [21] J. L. Schiff, “Cellular Automata: A Discrete View of the World,” John Wiley & Sons, 2008.
- [22] C. G. Langton, “Studying artificial life with cellular automata,” Physica D: Nonlinear Phenomena, Vol.22, Issues 1-3, pp. 120-149, 1986.
- [23] T. Kurita, N. Otsu, and T. Sato, “A face recognition method using higher order local autocorrelation and multivariate analysis,” Proc. of 11th IAPR Int. Conf., pp. 213-216, 1992.
- [24] N. Otsu and T. Kurita, “A new scheme for practical flexible and intelligent vision systems,” Proc. of IAPR Workshop on Computer Vision, pp. 431-435, 1988.
- [25] G. J. Chaitin, “Algorithmic information theory,” IBM J. of Research and Development, Vol.21, No.4, pp. 350-359, 1977.
- [26] A. N. Kolmogorov, “On tables of random numbers,” Sankhyā: The Indian J. of Statistics, Series A, Vol.25, No.4, pp. 369-376, 1963.
- [27] A. N. Kolmogorov, “Three approaches to the quantitative definition of information,” Problems of Information Transmission, Vol.1, No.1, pp. 1-7, 1965.
- [28] A. N. Kolmogorov, “On tables of random numbers,” A. N. Shiryaev (Ed.), “Selected Works of A. N. Kolmogorov,” Springer, 1993.
This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.