^{1, 2}School of Electronics and Information Engineering, University of Science and Technology Liaoning,, Liaoning, Anshan, China
^{2}Corresponding author
Vibroengineering PROCEDIA, Vol. 13, 2017, p. 243-248.
https://doi.org/10.21595/vp.2017.18839
Received 7 July 2017; received in revised form 10 July 2017; accepted 11 July 2017; published 26 September 2017
JVE Conferences
Based on the basics of the flocking, the concept and relationship of individual, cluster and flocking behavior are introduced. Two research methods, which are the macroscopic Angle of Euler method and the Lagrangian method of microcosmic Angle, are elaborated in detail. Then several flocking models and their improvement applications are summarized, the model among them based on dynamic principle is widely used, so the basic mode of its behavior, the following mechanism of an individual in an orderly procession, the mechanism for avoiding obstacles, and the causes of fission behavior are discussed in this paper. Finally, some problems in current researches of flocking are presented and future development are prospected.
Keywords: flocking, mathematical modeling, flocking behavior, collective motion.
1. Introduction
The research of flocking is always the focus of complex science since Edmund Selous who observed the birds circling in 1905. Over the past more than 100 years, the flocking research has been applied in a wide range of courses, from the beginning of biological studies, then it extends to physics, computer science, cybernetics, and even the humanities.
The phenomenon of natural flocking is spectacular, such as the migration of birds and fish, the prey of the wolves, and even the ravages of locusts, these large-scale, orderly behavior reflects the efficiency of the cluster. The scientists were inspired to apply the flocking control to machine engineering in order to replace artificial tasks. It is especially important to establish the mathematical model, several common mathematical models are summarized in this paper.
2. Theoretical research on flocking control
2.1. Theoretical research on flocking control
Individuals are the building blocks of a group, and group behavior is the emergence of individual interactions which called “flocking”. Simple flocking activities are clustered, progressive, evading and so on.
The cluster is a biological or device system that is jointly performed by some type of communication. In nature, geese and bees are common natural biological clusters; In life, the electronic devices and servers are long enough for server clusters, and the content on the web is provided by the information cluster; In the national economy, various industries are woven together to support the national economy, and the cooperation of these industries constitutes an industrial cluster [1].
The flocking behavior is the key of understanding life in biology, and it also promotes the development of science and technology in the application engineering. Swarm intelligence is the demand of modern science and technology, which is a high-level behavior that is generated by decentralized self-organization, there will no leader in the cluster, depending on the interaction between the individual information and independent can judge and update their own rules, in this case, the new rules for adapting to the environment can be described as an effective strategy for the group to evolve in the process of collaboration.
The focus of flocking model interaction lies in the unified relationship between the whole and the individual, and the interaction between them provides two methods for systematic research.
2.2. Cluster system research methods
2.2.1. Euler method
Euler is a holistic approach that ignores the characteristics of the individual, and views them as “whole” to study its density. Based on the theory of the classical diffusion theory of Feck, the theory of diffusion is as follows:
where $\rho $ is the change in the concentration of the particles per moment in the unit area, which is equal to the amount of displacement of the particle on the $X$-axis, $D$ is the particle diffusivity. Skellam J. G. thought it was not scientific only considering the spread of the whole itself, and ignoring the environment or from the internal resistance effect. He proposed to increase a convection factor on the $X$ axis. There are two variables are on $X$ direction, and u is the cluster of translational convection, then the equation can be written as:
Mogilner A and collaborators worked on flow problem, a force made a careful study of the particles; For the choice of diffusivity $D$, Alt W. Degenerate and Ikeda T. found that the function of $D$ in different clusters were different.
Euler’s study of the large-scale flocking that scientists have observed has worked, it uses partial differential equations to analyze the diffusion, and the analysis process does not require environmental considerations [2]. The Euler method is able to study the general movement properties of the cluster, but it ignores the individual characteristics and cannot be modeled from the individual point of view, which is not conducive to the control of the application.
2.2.2. Lagrange method
Lagrange method is based on individual microscopic modeling analysis, which using Newton equations of motion to describe the force of the object, the equation is as follows:
where $m$ is the quality, $x$ is the position, and $F$ is the resultant force of objects.
Reder C. M firstly proposed a clustering model using the force function and applied it to the behavior of the fish group; Warburton K. and his collaborators studied the effects of net forces on biological influences; Beni G. and his collaborators analyzed the stability of the model and validated the conclusion that it was stable when the environment was disturbed; The team of Grain V. and Wang extended this force to $N$-dimensional space and studied its stability.
The Lagrange method analyzes on the individual, and its modeling is based on the individual’s intrinsic factor, the individual is affected by the external environment and Individual interaction rules. It’s a natural intuitive modeling approach, it has influenced many subsequent research ideas, which is an important way of improving overall efficiency through individual control.
2.3. Mathematical model
2.3.1. Boid model
In 1986, Reynolds used a computer to simulate the world's first cluster campaign, which was called the Boid model. This was based on mapping the actual flock of birds to the computer, by using dots on the computer screen to represent the bird, setting the coordinates, the speed direction, and so on for each point. Reynolda was obtained by the model experiment of three simple rules: attract-synchronous-rejection, which become the cornerstone of the foundation of the clustering model for subsequent model is established based on.
Wang and his partners considered on the basis of the model to increase the actual situation, environment variables, such as outside groups within the population variables and the individual character itself, which replacing the original individual consistency hypothesis in the model [3], They simulated birds, fish and insects and studied the differences in their populations.
2.3.2. Vicsek model
In 1995 the physicist T. Vicsek and his collaborators proposed particle synchronization model (Vicsek model), which range from the perspective of statistical mechanics of cluster motion, according to the individual view within the scope of the average particle velocity adjust itself, the speed and the direction of flocking synchronization in a certain space, randomly distributed $N$ particles. The position and movement direction the particle updating equations are as follows:
where $x$, $v$ and $\theta $ are the values of the position, velocity, and angle of the particle $i$ at time $t$; $\mathrm{\Delta}t$ is set to 1; the Angle at time $t+1$ is determined by the average velocity of all the particles in the area of the center of the $i$ particle; $\mathrm{\Delta}\theta $ is the noise interference that obeys the uniform distribution; In the paper [4], the study showed that when the flocking density is large and the noise is small, the individual will gradually become synchronized; Increase the noise and the particles will become confused. In Vicsek model, the state of the individual is only related to density and noise, and the noise levels interfere with the particles and make different changes. This kind of change can be compared to the three state changes of matter. The model will control the connection of science and physics, and it becomes the relevant theoretical research.
The Vicsek model is widely studied for its simple but also is a complex system. Chen and others put forward individual update rules, they thought the priority should be given to the movement of neighborhood Angle deviation of the two biggest particles, including value instead of the original model of average speed [5], and the simulation showed that this method not only reduces the calculation quantity, but also improves the convergence speed of the model. Gao and others believed that the convergence of the model is related to the number of particles in the field of vision, and introduces the degree of “degree” to describe it [6]; Li was simply adding the individual’s speed to the update rules, making the overall adjustment more accurate [7]. Tian had studied the model from a biologically-driven point of view [8].
2.3.3. Three-Circle model
In 2002 I. D. Couzin proposed the Three-Circle model [9], he incorporated the Reynolds movement three principles into the model, building the individual perception range, which consists of exclusion zones, synchronous zones. This was a model controlled by the individual of the distance parameter. Each individual had its own range of inductance, and the individual had no influence over its range; When other individuals within the scope of the induction and particles from the far, attract trend particle was governed by the rules, to be near individuals, an area known as the attract area; As the individual approaches a certain distance, it moved into the sync area of the particle, allowing the speed of the two to synchronize. If the individual was less than the distance of the particle, the particle produces an exclusion trend away from the individual, which was the exclusion zone of the particle.
The individuals around the particle will give priority to the individuals who reject the minimum distance in the area, following the following rules:
where $c$ is the position of the individual, $d$ is the direction vector, the equation shows that when there are other individuals in the exclusion zone, the particle moves in a sparse direction; If there is no other individuals in the exclusion zone, the state of the particle will be affected by the individual in the other two regions, the velocity of the particle is affected by the speed of the synchronous region, and the position is closer to the attractor. The formula is as follows:
2.3.4. Social force model
In 1995, Helbing et al proposed a social force model to simulate pedestrian flow under normal conditions [10]. The force model was based on Newton’s mechanical modeling method. The individual speed is changed by force driving:
where $m$ and $v$ are the quality and speed of the individual; ${f}_{ij}$ and ${f}_{iw}$ are individual and individual interactions with the environment.
Helbing and others worked on the basis of the model considering joining panic environment in 2000 [11], which used to study stress conditions of the reaction of the crowd, and found some behavior characteristics of the crowd in a tense; Hu and others believed that people would automatically avoid the crowded areas, and proposed an improved model of a dynamic blocking area to study the relationship between human flux and density [12].
The social force model applies to the layout of various large public places and the retreat of disasters, the model simulates the fire in the dormitory of the university [13].
2.3.5. Dynamics model
Similar to the social force model, it is the analysis of the force situation of the individual, which assumes that $N$ individuals constitute a cluster, and each individual’s dynamic equation is:
where ${r}_{i}={\left({x}_{i},{y}_{i}\right)}^{T}$ is the position vector of individual $i$, ${v}_{i}={\left({x}_{i},{y}_{i}\right)}^{T}$ is the velocity vector of the individual, ${u}_{i}={\left({x}_{i},{y}_{i}\right)}^{T}$ is the control input, which is:
where ${\alpha}_{i}$ is the speed control vector, so that the individual speed matching; ${a}_{i}$ is a distance vector control for avoidance; individual position under the model with adjacency graph $G=\left(V,e\right)$, $V=\left\{1,\dots N\right\}$, is the set of all the individual form of points, $\epsilon =v\times v$ is the communication between the individual under the condition of edge set.
The dynamic model is one of the main modeling methods of the cluster control model. The force acting on the individual is connected with the environment change, which is convenient for efficient and precise operation control.
3. Flocking behavior
3.1. Formation march
The formation movement is the most basic behavior of the flocking movement, and describes the simulation study of the input of the individual by the dynamic model.
Natural clusters were mostly guided by leaders, Yu and others emulated the leaders’ clusters, which showed that individuals follow leaders independently. Wang considered the no-leader flocking virtual navigation method mode, by selecting the individual cluster individual potential minimum as a virtual leader, and the minimum potential energy which the virtual leader always calculating was not fixed. The other individuals through the minimum potential energy within the cluster information could adjust themselves, which could accelerate the convergence speed of the internal cluster, and lack of influence to prevent the leader [14].
Follow the rules of the cluster formation which researched by biological characteristics got better results, the formation of a flock of pigeons was researched by Qiu Huaxin, and head pigeon was the leader. Others follow each of their superiors, but direct supervisor had the greatest impact. In the literature [15], The hierarchical formation of pigeon groups was illustrated by simulation modeling.
3.2. Avoid obstacles
Obstacles inevitably occur on the route of a flocking movement, but the large mobile groups in the biological community can escape the obstacles by passing information between each other individually.
Cheng worked on the potential energy field of the obstacle to repel the force of the individual which could guide the individual to avoid [16]; In the literature [17], the study of individual and the distance of the obstacle, it defined the shortest distance point of the shadow of the individual projecting to the obstacle as the virtual point. The detection of individual and virtual point distance, when the distance was smaller than the safe distance, repulsion by obstacle, individual away from the virtual point until the safe distance between them are safe. This way was called “along the wall”, which could avoid the local minimum problem caused by the individual potential field preparatory measures cannot be moved.
3.3. Clustering behavior
Clustering results in clustering behavior when individual information within a cluster varies and individual interactions result in conflict. Clustering was important for the survival of the cluster [18].
The change of individual information can be divided into two directions, one is from the individual without any outside interference, such as cell growth and differentiation. Cell differentiation by adhesion hypothesis, with that Graner proposed Cellular Potts model. Cell differentiation was a complex biological phenomenon, related to the field of biological and chemical energy. Graner studied the energy relationship between cells by using Hamilton function, and found that the difference in cell type was the main cause of cell differentiation, and this change was caused by the cell itself. The other one is that the clustering disturbed by the outside, which causes the individual information to change, and then affects the group to produce the grouping behavior.
4. Conclusions
In this paper, the mathematical model of the cluster system and its application are described in detail, in order to apply it to practical engineering, further research is necessary to solve the problems: how to select the optimal model; how to control the information interaction among individuals; controllability and robustness of cluster system and so on; At present, cluster research has been applied in transportation, military and other fields, its development still remains to be explored for further research.
References
- Huang Tianyun Conrtol for Self-Organized Collect Motions of Swarm Robotic System. Ph.D. Thesis, Dalian University of Technology, Dalian, 2015. [CrossRef]
- Chen Shiming Review of the modeling and control of swarm behaviors. Computer Engineering Science, Vol. 29, Issue 7,2007, p. 102-105. [CrossRef]
- Wang Nannan, Yu Hang, Chen Jing An improved self-organization biological swarm simulation model. Journal of Dalian Nationalities University, Vol. 14, 2012, p. 81-84. [CrossRef]
- Tamas Vicsek Novel type of phase transition in a system of self-driven particles. Physical Review Letters, Vol. 75, 1995, p. 1226-1229. [CrossRef]
- Chen Shiming, Shu Juan, Nie Shen A convergence properties of improved Vicsek model. Information and Control, Vol. 40, Issue 3, 2011, p. 318-322. [CrossRef]
- Gao Jianxi, Chen Zhuo, Cai Yunze A new method to improve the convergence efficiency of Vicsek model. Control and Decision, Vol. 24, Issue 8, 2009, p. 1270-1272. [CrossRef]
- LiFeng Simulation research of group decision making based on improved Vicsek model. Journal of Zhongshan University Graduate, Vol. 31, Issue 1, 2010, p. 79-85. [CrossRef]
- TianBaomei Research of Vicsek Model with a System of Self-Driven Agents. University of Science and Technology of China, 2009. [CrossRef]
- Couzin I. D. Collective memory and spatial sorting in animal groups Journal of Theoretical Biology, Vol. 218, 2002, p. 1-11. [CrossRef]
- Helbing D., Molnar P. Social force model for pedestrian dynamics. Physical Review E, Vol. 51, Issue 5, 1995, p. 4282-4285. [CrossRef]
- Helbing D., Farkas I., Vicsek T. Simulating dynamics features of escapepanic. Nature, Vol. 407, Issue 1, 2000, p. 487-490. [CrossRef]
- Hu Qingmei, Fang Weining, Jia Yuquan Simulation study on crowd behavior and crowd behavior. Science in China Press, Vol. 39, Issues 5, 2009, p. 1034-1038. [CrossRef]
- Long Shenjie, Zhu Bin, Tang Mingjing Simulation study on fire escape of dormitory building in University. Journal of Zunyi Normal College, Vol. 18, Issue 3, 2016 p. 102-105. [CrossRef]
- Wang Dongmei, Fang Huajing Intelligent group virtual leader cluster based on motion control. Journal of Huazhong University of Science and Technology, Vol. 36, Issue 10, 2008, p. 5-7. [CrossRef]
- Qiu Huaxin, Duan Haibin, Fan Yanming Autonomous Formation of multiple UAVs based on behavior mechanism of pigeon swarm. Control theory and Application, Vol. 32, Issue 10, 2015, p. 1298-1304. [CrossRef]
- Chen Lei, Wang Yongji, Zhu Quanmin Multi-agent based swarm formation control system for multiple mobile robots. Systems Engineering and Electronic Technology, Vol. 28, Issue 5, 2006, p. 731-735. [CrossRef]
- Cheng Lei, Zhu Quanmin, Wu Huaiyu Multi modal cluster motion control for multi mobile robots incorporating wall behavior. Control and Decision, Vol. 26, Issue 3, 2011, p. 477-480. [CrossRef]
- Yang Panpan, Liu Mingyong, Lei Xiaokang Advances in modeling and control of clustering behavior in cluster systems. Control and Decision, Vol. 31, Issue 2, 2016, p. 193-206. [CrossRef]