If a given behavior of a multi-agent system restricts the phase variable to an invariant manifold, then we define a phase transition as a change of physical characteristics such as speed, coordination, and structure. We define such a phase transition as splitting an underlying manifold into two sub-manifolds with distinct dimensionalities around the singularity where the phase transition physically exists. Here, we propose a method of detecting phase transitions and splitting the manifold into phase transitions free sub-manifolds. Therein, we firstly utilize a relationship between curvature and singular value ratio of points sampled in a curve, and then extend the assertion into higher-dimensions using the shape operator. Secondly, we attest that the same phase transition can also be approximated by singular value ratios computed locally over the data in a neighborhood on the manifold. We validate the Phase Transition Detection (PTD) method using one particle simulation and three real world examples.
Citation: |
Figure 1.
An abrupt phase change of the crowd behavior where a walking crowd suddenly starts running [2]. (a) The first phase of the motion (walking) is embedded onto the blue colored manifold, while the second phase (running) is embedded onto the red colored manifold. Two snapshots showing walking and running at time steps
Figure 2.
(a) Superimposing a neighborhood of the curve
Figure 3.
Local distribution of data around the point
Figure 4.
(a) A three dimensional sombrero-hat of 2000 points consisting two sub-manifolds (blue and green) and locus of singularities (red) is intersected with the plane
Figure 5.
Detecting phase transitions in a particle swarm simulated using the Vicsek model with alternating noise levels. (a) The distribution of
Figure 6.
Detecting a phase transition between phases of walking and running in a human crowd [3]. (a) The distribution of
Figure 7.
Detecting a transition in a bird flock between phases sitting and flying [1]. (a) The distribution of
Figure 8.
Detecting phase transitions in a fish school. (a) The distribution of
[1] | Birds flying away, shutterstock. Available from: https://www.shutterstock.com/video/clip-3003274-stock-footage-birds-flying-away.html?src=search/Yg-XYej1Po2F0VO3yykclw:1:19/gg. |
[2] | Data set of detection of unusual crowd activity available at robotics and vision laboratory, Department of Computer Science and Engineering, University of Minnesota. Available from: http://mha.cs.umn.edu/proj_events.shtml. |
[3] | Data set of pet2009 at Computational Vision Group, University of Reading, 2009. Available from: http://ftp.pets.reading.ac.uk/pub/. |
[4] | N. Abaid, E. Bollt and M. Porfiri, Topological analysis of complexity in multiagent systems, Physical Review E, 85 (2012), 041907. doi: 10.1103/PhysRevE.85.041907. |
[5] | G. Alfred, Modern Differential Geometry of Curves and Surfaces with Mathematica, CRC press, 1998. |
[6] | I. R. de Almeida and C. R. Jung, Change detection in human crowds, in Graphics, Patterns and Images (SIBGRAPI), 2013 26th SIBGRAPI-Conference on, IEEE, (2013), 63-69. doi: 10.1109/SIBGRAPI.2013.18. |
[7] | E. L. Andrade, S. Blunsden and R. B. Fisher, Hidden markov models for optical flow analysis in crowds, in Pattern Recognition, 2006. ICPR 2006. 18th International Conference on, IEEE, 1(2006), 460-463. doi: 10.1109/ICPR.2006.621. |
[8] | M. Ballerini, N. Cabibbo, R. Candelier, A. Cavagna, E. Cisbani, I. Giardina, A. Orlandi, G. Parisi, A. Procaccini and M. Viale, et al., Empirical investigation of starling flocks: A benchmark study in collective animal behavior, Animal Behaviour, 76 (2008), 201-215. doi: 10.1016/j.anbehav.2008.02.004. |
[9] | C. Becco, N. Vandewalle, J. Delcourt and P. Poncin, Experimental evidences of a structural and dynamical transition in fish school, Physica A: Statistical Mechanics and its Applications, 367 (2006), 487-493. doi: 10.1016/j.physa.2005.11.041. |
[10] | M. Beekman, D. J. T. Sumpter and F. L. W. Ratnieks, Phase transition between disordered and ordered foraging in pharaoh's ants, Proceedings of the National Academy of Sciences, 98 (2001), 9703-9706. doi: 10.1073/pnas.161285298. |
[11] | A. C. Bovik, Handbook of Image and Video Processing, Academic press, 2010. |
[12] | R. Bracewell, Fourier Analysis and Imaging, Springer Science & Business Media, 2010. doi: 10.1007/978-1-4419-8963-5. |
[13] | I. D. Couzin, Collective cognition in animal groups, Trends in cognitive sciences, 13 (2009), 36-43. doi: 10.1016/j.tics.2008.10.002. |
[14] | I. D. Couzin, J. Krause, N. R. Franks and S. A. Levin, Effective leadership and decision-making in animal groups on the move, Nature, 433 (2005), 513-516. doi: 10.1038/nature03236. |
[15] | A. Deutsch, Principles of biological pattern formation: Swarming and aggregation viewed as self organization phenomena, Journal of Biosciences, 24 (1999), 115-120. doi: 10.1007/BF02941115. |
[16] | J. H. Friedman, J. L. Bentley and R. A. Finkel, An algorithm for finding best matches in logarithmic expected time, ACM Transactions on Mathematical Software, 3 (1977), 209-226. doi: 10.1145/355744.355745. |
[17] | K. Gajamannage, S. Butailb, M. Porfirib and E. M. Bollt, Model reduction of collective motion by principal manifolds, Physica D: Nonlinear Phenomena, 291 (2015), 62-73. doi: 10.1016/j.physd.2014.09.009. |
[18] | K. Gajamannage, S. Butailb, M. Porfirib and E. M. Bollt, Identifying manifolds underlying group motion in Vicsek agents, The European Physical Journal Special Topics, 224 (2015), 3245-3256. doi: 10.1140/epjst/e2015-50088-2. |
[19] | J. J. Gerbrands, On the relationships between SVD, KLT and PCA, Pattern recognition, 14 (1981), 375-381. doi: 10.1016/0031-3203(81)90082-0. |
[20] | R. Gerlai, High-throughput behavioral screens: The first step towards finding genes involved in vertebrate brain function using zebra fish, Molecules, 15 (2010), 2609-2622. doi: 10.3390/molecules15042609. |
[21] | G. H. Golub and C. Reinsch, Singular value decomposition and least squares solutions, Numerische Mathematik, 14 (1970), 403-420. doi: 10.1007/BF02163027. |
[22] | D. Helbing, J. Keltsch and P. Molnar, Modelling the evolution of human trail systems, Nature, 388 (1997), 47-50. |
[23] | J. M. Lee, Riemannian Manifolds: An Introduction to Curvature, volume 176, Springer, 1997. doi: 10.1007/b98852. |
[24] | J. M. Lee, Introduction to Smooth Manifolds, Graduate Texts in Mathematics, 218. Springer-Verlag, New York, 2003. doi: 10.1007/978-0-387-21752-9. |
[25] | R. Mehran, A. Oyama and M. Shah, Abnormal crowd behavior detection using social force model, in Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on, IEEE, (2009), 935-942. doi: 10.1109/CVPR.2009.5206641. |
[26] | M. M. Millonas, Swarms, Phase Transitions, and Collective Intelligence, Technical report, Los Alamos National Lab., New Mexico, USA, 1992. |
[27] | S. R. Musse and D. Thalmann, A model of human crowd behavior: Group inter-relationship and collision detection analysis, in Computer Animation and Simulation, Springer, (1997), 39-51. doi: 10.1007/978-3-7091-6874-5_3. |
[28] | M. Nagy, Z. Ákos, D. Biro and T. Vicsek, Hierarchical group dynamics in pigeon flocks, Nature, 464 (2010), 890-893. doi: 10.1038/nature08891. |
[29] | B. O'neill, Elementary Differential Geometry, Academic press, New York, 1966. |
[30] | T. Papenbrock and T. H. Seligman, Invariant manifolds and collective motion in many-body systems, AIP Conf. Proc. , 597(2001), p301, arXiv: nlin/0206035. doi: 10.1063/1.1427476. |
[31] | B. L. Partridge, The structure and function of fish schools, Scientific American, 246 (1982), 114-123. doi: 10.1038/scientificamerican0682-114. |
[32] | W. Rappel, A. Nicol, A. Sarkissian, H. Levine and W. F. Loomis, Self-organized vortex state in two-dimensional dictyostelium dynamics, Physical Review Letters, 83 (1999), p1247. |
[33] | E. M. Rauch, M. M. Millonas and D. R. Chialvo, Pattern formation and functionality in swarm models, Physics Letters A, 207 (1995), 185-193. doi: 10.1016/0375-9601(95)00624-C. |
[34] | V. Y. Rovenskii, Topics in Extrinsic Geometry of Codimension-one Foliations, Springer, 2011. doi: 10.1007/978-1-4419-9908-5. |
[35] | S. T. Roweis and L. K. Saul, Nonlinear dimensionality reduction by locally linear embedding, Science, 290 (2000), 2323-2326. doi: 10.1126/science.290.5500.2323. |
[36] | R. V. Solé, S. C. Manrubia, B. Luque, J. Delgado and J. Bascompte, Phase transitions and complex systems: Simple, nonlinear models capture complex systems at the edge of chaos, Complexity, 1 (1996), 13-26. |
[37] | D. Somasundaram, Differential Geometry: A First Course, Alpha Science Int'l Ltd., 2005. |
[38] | D. Sumpter, J. Buhl, D. Biro and I. Couzin, Information transfer in moving animal groups, Theory in Biosciences, 127 (2008), 177-186. doi: 10.1007/s12064-008-0040-1. |
[39] | J. B. Tenenbaum, V. De Silva and J. C. Langford, A global geometric framework for nonlinear dimensionality reduction, Science, 290 (2000), 2319-2323. doi: 10.1126/science.290.5500.2319. |
[40] | E. Toffin, D. D. Paolo, A. Campo, C. Detrain and J. Deneubourg, Shape transition during nest digging in ants, Proceedings of the National Academy of Sciences, 106 (2009), 18616-18620. doi: 10.1073/pnas.0902685106. |
[41] | C. M. Topaz and A. L. Bertozzi, Swarming patterns in a two-dimensional kinematic model for biological groups, SIAM Journal on Applied Mathematics, 65 (2004), 152-174. doi: 10.1137/S0036139903437424. |
[42] | T. Vicsek, A. Cziró, E. Ben-Jacob, I. Cohen and O. Shochet, Novel type of phase transition in a system of self-driven particles, Physical Review Letters, 75 (1995), 1226-1229. doi: 10.1103/PhysRevLett.75.1226. |
[43] | E. Witten, Phase transitions in m-theory and f-theory, Nuclear Physics B, 471 (1996), 195-216. doi: 10.1016/0550-3213(96)00212-X. |
[44] | P. N. Yianilos, Data structures and algorithms for nearest neighbor search in general metric spaces, in Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, (1993), 311-321. |
[45] | T. Zhao and R. Nevatia, Tracking multiple humans in crowded environment, in Computer Vision and Pattern Recognition, 2004. CVPR 2004. Proceedings of the 2004 IEEE Computer Society Conference on, IEEE, (2004), Ⅱ-406. doi: 10.1109/CVPR.2004.1315192. |