# Self-Organized Fission Control for Flocking System

Authors: Mingyong Liu; Panpan Yang; Xiaokang Lei; Yang Li
Journal: Journal of Robotics
 (2015)

---

## Abstract

This paper studies the self-organized fission control problem for flocking system. Motivated by the fission behavior of biological flocks, information coupling degree (ICD) is firstly designed to represent the interaction intensity between individuals. Then, from the information transfer perspective, a “maximum-ICD” based pairwise interaction rule is proposed to realize the directional information propagation within the flock. Together with the “separation/alignment/cohesion” rules, a self-organized fission control algorithm is established that achieves the spontaneous splitting of flocking system under conflict external stimuli. Finally, numerical simulations are provided to demonstrate the effectiveness of the proposed algorithm.


---

## Body

## 1. Introduction

The fission behavior of flocking system is a widely observed phenomenon in biology, society, and engineering applications [1]. A bird flock may sometimes split into multiple clusters for food foraging or predator escaping [2]. An unmanned ground vehicle (UGV) swarm often needs to segregate into small subgroups for the multisite surveillance mission [3]. In these cases, members in the flock are often identical ones with limited sensing and computing capabilities and only rely on the local interaction with their nearest neighbors [4]. Therefore, the fission phenomenon of flocking system is virtually an emergent behavior that arises in a self-organized fashion [5]. How a cohesive flock splits and forms clusters remains a fascinating issue of both theoretical and practical interests.Currently, the research on flocking system mainly focuses on the consensus based problems such as aggregation and formation [6, 7], of which the central rules are separation, alignment, and cohesion [8]. These rules have been extensively used in the distributed sensing of mobile sensor networks, formation keeping of satellite clusters, cooperative control of unmanned ground/aerial/underwater vehicles, and so forth [9]. However, the “average consensus” property of these rules gives the flock a “collective mind” [10] and leads to a group-level ability of “consensus decision making” [11, 12], which may dispel the conflict information and encumber the process of group splitting [13].At present, literatures that address the fission control problem seem diverse. By predefining the leaders/targets to different individuals, fission behavior emerged in the multiobjective tracking process [14–16]; in [17], Kumar et al. assigned different coupling strength to heterogeneous robot swarm that leads weak coupling robots to separate and the strong coupling robots form clusters. In addition, a long range attractive, short range repulsive interaction as well as an intermediate range Gauss-shaped interaction was employed for flock aggregation and splitting in [18].In this paper, we tend to study the self-organized fission control problem for flocking system without predefining the leaders or identifying the differences between individuals. Motivated by the fact that interaction intensity plays a crucial role in the fission behavior of animal flocks [2, 11, 19], information coupling degree (ICD) is used as an index to denote the interaction intensity between individuals. Then, a “maximum-ICD” based pairwise interaction rule is proposed to achieve the effective information transfer within the flock. Together with the traditional “separation/alignment/cohesion” rules, a self-organized fission control algorithm is established, which realizes the spontaneous splitting of a cohesive flock under conflict external stimuli. Finally, numerical simulations are performed to illustrate the effectiveness of the proposed method.The remainder of this paper is organized as follows: in Section2, the fission control problem for flocking system is formulated; in Section 3, the biological principle for fission behavior is described and an information coupling degree based fission strategy is established; in Section 4, a self-organized fission control algorithm that includes a new pairwise interaction rule is proposed and the theoretical analysis is given; in Section 5, various numerical simulations and discussions are carried out to demonstrate the effectiveness of the fission control algorithm; Section 6 offers the concluding remarks.


## 2. Problem Formulation

Consider a flocking system consisting ofN identical individuals moving in the n-dimensional Euclidean space with the following dynamics:
(1)p˙i=qi,q˙i=ui,i=1,2,…,N,
where pi∈Rn is the position vector of individual i, qi∈Rn is its velocity vector, and ui∈Rn is the acceleration vector (control input) acting on it. For notational convenience, we let
(2)p=p1p2⋮pN,q=q1q2⋮qN∈RNn.The neighboring set of individualsi is defined as Ni(t)={j:pi-pj≤R, j=1,…,N, j≠i}, where · is the Euclidean norm and R is the sensing range of each individual. Also, we define the neighboring graph G=(V,E,A) [20] to be an undirected graph consisting of a set of nodes V={v1,v2,…,vN}, a set of edges E={(vi,vj)∈V×V:vi~vj}, and an adjacency matrix A=[aij] with aij>0 if (vi,vj)∈E and aij=0, otherwise. The adjacency matrix A of undirected graph G is symmetric and the corresponding Laplacian matrix is L=D-A, where D=diag⁡{d1,d2,…,dN}∈RN×N is the in-degree matrix of graph G and di=∑j=1N‍aij is the in-degree of node vi.Essentially speaking, flocking behavior is a self-organized emergent phenomenon of large numbers of individuals by interacting with their neighbors and surrounding environment [21]. Correspondingly, the control input acting on an individual member can be written as
(3)ui=uiin+giuiout,
where uiin is the internal interaction force between individual i and its neighbors and uiout is the force acting on individuals from external environment. Usually, not all the members are directly influenced by the environment; here we utilize gi to denote whether individual i can sense environment information, where gi=1 means the environment information can be directly obtained by individual i and gi=0, otherwise.Fission behavior often occurs when a cohesive flock encounters obstacles/danger on their moving path or observes multiple targets for tracking [2, 15, 22, 23]. In such occasions, only a small portion of individuals (e.g., lie on the edge of the flock) are directly influenced by the environment information and often response with fast maneuvering like abrupt accelerating or turning [2, 22]; the motion of other members is only governed by their internal interaction force uiin. Therefore, environment information can only be seen as the trigger event of fission behavior; whether the whole flock has the ability to split is essentially determined by its local interaction rules [5].Therefore, the objective of this paper is to design the distributed local interaction rules and synthesize the control inputui for a flocking system such that when conflict environment information acts on part of members in the flock, it can segregate into clustered subgroups spontaneously.To better describe the fission behavior in a quantitative way, we first give the mathematical definition of fission behavior as follows.Definition 1.
A flocking system is said to be segregated (or a fission behavior occurs) if and only if it satisfies the following conditions.(1)
The distance between individuals in the same subgroup remains bounded; that is,pi(t)-pj(t)≤δ, i,j∈Gk, where δ is a constant value and Gk denotes the subgroup k.(2)
For individuals in the same subgroup, their velocities will asymptotically converge to the same value; that is,qi(t)-qj(t)→0, i,j∈Gk.(3)
For any distanceD>R, there exists a time after which the distance between individuals in different subgroups is at least D; that is, min⁡pi(t)-pj(t)≥D, i∈Gk, j∈Gl, which means that the subgroups will ultimately lose connection with each other and hence the fission behavior emerges.Remark 2.
It is worth mentioning that the fission behavior studied in this paper is a spontaneous response to external stimuli, during which only a small portion of members directly sense the external stimuli and the whole flock governed by the fission control algorithm is able to segregate autonomously in a self-organized fashion. Therefore, it is fundamentally different from the aforementioned fission control approaches like assignment, identification, or centralized control [14–17] and is more consistent with the fission behavior of real flocking system [2, 23].


## 3. Information Coupling Degree Based Fission Rule

Fission behavior is the result of “collective decision making” in the presence of motion differences of individuals in the flock [2, 24]. Couzin et al. revealed that, for significant differences in the preferences of individuals, the decision dynamics may bifurcate away from consensus and lead to the emergence of fission behavior [11]. In addition, research from biologists also suggests that fission behavior, to a large extent, depends on the mutual interaction intensity between individuals [1, 25]. Individuals with larger interaction intensity tend to have tighter correlation and form clusters in the presence of significant differences in the preferences of individuals [2, 11].Inspired by the above results, we construct a new index named information coupling degree (ICD) to denote the mutual interaction intensity between individuals. ICD is a motion dependent variable that is relevant to many factors; for example, individuals are usually more influenced by the close neighbors (distance) [26], they tend to be more sensitive to fast moving neighbors (velocity) [19, 27], and individual with more neighbors are usually more dominated (number of neighbors) [28]. In particular, we choose the two most dominating factors, the relative position and relative velocity between individuals, to design ICD in the following form:
(4)cij=ξij·ωij,
where ξij is the position coupling term determined by the relative position between individuals. As the influence of neighbors is decreasing with the increase of their relative distance due to the sensing ability [29], we write the position coupling term as follows:
(5)ξij=rij1+pi-pj2,
where rij>0 is the coefficient of position coupling term.In addition,ωij is the velocity coupling term that is relevant to the relative velocity between individuals. Generally, individuals are very sensitive to some specific behavior of their neighbors like abrupt accelerating or turning [19]; therefore we design ωij as
(6)ωij=μijqi-qj×q¯i∑j∈Ni(t)qi-qj×q¯i,
where q¯i=(1/Ni)∑j∈Ni(t)qj is the average velocity of the neighbors of individual i, Ni is the number of its neighbors, and μij>0 is the coefficient of velocity coupling term. Here, (qi-qj)×q¯i reflects the degree of the difference between (qi-qj) and q¯i, with (qi-qj) being the relative velocity between two individuals. The bigger (qi-qj)×q¯i is, the more different motion of individual j is from the neighbors of individual i, the more attention will be paid by individual i to individual j, and the tighter correlation they will tend to have, correspondingly.From the information transfer perspective, fission behavior can be generalized as the conflict stimulus information propagation process among members within the flock [2, 23, 30]. Individuals which change their direction of travel in response to the direction taken by their nearest neighbors can quickly transfer information about the predator or food source [30]. Therefore, we propose a “maximum-ICD” based strategy to maximize the stimulus information transfer, where individuals tend to have closer relation with the neighbor that has maximum ICD with it [19, 31].Based on the above description, we formulate the “maximum-ICD” strategy as(7)fi=j∣max⁡cij,cij>c*,j∈Nit,
where c* is the threshold value of the fission behavior. When cij>c*, fission behavior occurs; otherwise, it is not disturbed by conflict environment stimuli and moves in stable formation. In this paper, we choose c* to be an appropriate value to prevent the unexpected fission behavior due to random fluctuation or other unknown factors.Utilizing the “maximum-ICD” strategy, we propose a pairwise interaction rule to realize the directional information flow among individuals. The internal interaction mechanism of individuals during the fission process is illustrated in Figure1. Assume that, at time t-Δt, individual fi (locates at pfit-Δt with velocity qfit-Δt) is propelled by external stimuli and changes its motion rapidly to a new position pfit with velocity qfit in a small time interval Δt. According to (4), individual i is more influenced by fi and tends to have a relatively tighter correlation with it. Therefore, at time t the force of neighbors acting on individual i can be written as
(8)uit=ufit-Δt+∑i=1Ni-1uit-Δt,
where ufit-Δt is the pairwise interaction force of the most correlated neighbor fi acting on individual i and ∑i=1Ni-1uit-Δt denotes the sum of the forces of other neighbors acting on it, with Ni being the number of neighbors.Figure 1
Internal interaction mechanisms of individuals based on “maximum-ICD” strategy.Remark 3.
It can be seen from (4)~(6) that information coupling degree combines both the position and velocity information between individuals and their neighbors; meanwhile they also tend to have closer relation with the fast maneuvering neighbors that are near to them, which is consistent with the property of real flocking system [19].


## 4. Self-Organized Fission Control Algorithm

Based on the above fission control principle, we take the most correlated neighbor to form a pairwise interaction with individuali. By integrating the motion information of the most correlated neighbor into the coordinated law, together with the “separation/alignment/repulsion” rules, the distributed fission control algorithm is formulated as
(9)ui=fip+fiv+fif︸uiin+gifie︸uiout,
where the environment force uiout is represented by the external stimulus term fie, it causes the rapid movement change of individuals and evokes the fission behavior, and gi denotes whether individual i can sense external stimuli. Usually, fie has diverse forms according to different environment stimuli, such as the direction to a known source or a segment of a migration route [11, 32]. Here, for the convenience of analysis, we design the external stimulus term as the following simple position feedback form:
(10)fie=-pi-pie,
where pie is the desired position driven by external stimuli and it is supposed to be a constant value at every sampling time interval.Obviously, the internal interaction forceuiin consists of three components.(1)fip is used to regulate the position between individual i and its neighbors. This term is responsible for collision avoidance and cohesion in the flock; that is, when individuals are too far away from each other, the attraction force will make them move together; when individuals are too close, the repulsion force will propel them away to avoid collision. It is derived from the field produced by a collective function which depends on the relative distance between individual i and its neighbors and is defined as
(11)fip=-∑j∈Nit‍∇piψijpij-pfijσ,
where ∇ is the gradient operator, the σ-norm ·σ of a vector is a map Rn→R+ defined by zσ=(1/ϵ)[1+ϵz2-1] with a parameter ϵ>0, and z=[z1,z2,…,zn]T∈Rn. Note that the map zσ is differentiable everywhere, but z=z12+z22+⋯+zn2 is not differentiable at z=0. This property of σ-norm is used for the construction of smooth collective potential functions for individuals. To construct a smooth pairwise potential with finite cutoff, we follow the work of [7] and integrate an action function ϕα(z) that varies for all z≥rα. Define this action function as
(12)ϕαz=ρhzrαϕz-dα,ϕz=12a+bσ1z+c+a-b,
where σ1(z)=z/1+z2 and ϕ(z) is an uneven sigmoidal function with parameters that satisfy 0<a≤b, c=|a-b|/4ab to guarantee ϕ(0)=0. The pairwise attractive/repulsive potential function ψα(z) is then defined as
(13)ψα(z)=∫dαz‍ϕα(s)ds
and is depicted in Figure 2.Figure 2
The pairwise attractive/repulsive potential function.Additionally,pij=pi-pj is the relative position vector between individuals i and j; pfij=pfi-pfj is the relative position vector between the most correlated neighbors of individuals i and j.(2)fiv is the velocity coordination term that regulates the velocity of individuals
(14)fiv=-∑j∈Nit‍aijqij-qfij,
where qij=qi-qj is the relative velocity vector between individuals i and j and qfij=qfi-qfj is the relative velocity vector between the most correlated neighbors of individuals i and j. Moreover, A(t)=[aij(t)] is the adjacency matrix which is defined as
(15)aij(t)=0,ifj=i,ρhpj-piσrσ,ifj≠i
with the bump function ρh(z), h∈(0,1), being
(16)ρh(z)=1,z∈0,h,121+cos⁡πz-h1-h,z∈h,1,0,otherwise.(3)fif is the pairwise interaction term that produces a closer relation between individual i and its most correlated neighbor fi, which is used to guide the motion preference of individual i. Specifically, we employ an attractive force and velocity feedback approach to generate fif as
(17)fif=-k1∇pfiUfi-k2qi-qfi,
where k1,k2>0 are the constant feedback gains and Ufi=(1/2)(pi-pfi)2 is the potential energy of its most correlated neighbor. This term guarantees the velocity convergence of individual i to its most correlated neighbor fi and ultimately induces the fission behavior.Remark 4.
The specifically designed pairwise attractive/repulsive artificial potentialψα and adjacent matrix aij here are to guarantee the smoothness of the potential function and Laplacian matrix, which will facilitate the theoretical analysis with the traditional Lyapunov-based stability analysis method.Remark 5.
Note that, in our fission control algorithm (9), the most correlated neighbor of individual i is chosen according to (7), and it is dynamically updating during the fission process of the flock, which realizes the implicit stimulus information transfer among members in the flock. Thus, there is an essential difference between our work and the researches of [14–16], as the latter assume the leader or target of each member is predefined and fixed during the fission process.Remark 6.
From (7) we can also see that if cij<c*, the most correlated neighbor of individual i does not exist. In this case, the fission control algorithm (9) degrades into
(18)ui=-∑j∈Ni(t)‍∇piψijpi-pjσ-∑j∈Ni(t)‍aij(qi-qj)+gifie
which is equivalent to the first flocking control law proposed in [7]. This situation occurs when the differences of motion preference between individuals are relatively small and hence the fission behavior does not occur. Therefore, algorithm (18) in [7] can be seen as a special case of ours. However, algorithm (18) is not able to achieve the spontaneous fission behavior due to its average consensus property. A detailed comparative simulation and analysis is demonstrated in part 5.Here, we define the sum of the total artificial potential energy and the total relative kinetic energy between all individuals and the external stimuli as follows:(19)Qp,q=12∑i=1N‍Uip+qi-qfiTqi-qfi,
where
(20)Uip=Vip+k1pi-pfiTpi-pfi=∑j∈Ni(t)‍ψijpij-pfijσ+k1pi-pfiTpi-pfi+gipi-pieTpi-pie.
Obviously, Q is a positive semidefinite function. We have the following result.Theorem 7.
Consider a flocking system consisting ofN individuals with dynamics (1). Supposing the initial energy Q0  (Q0=Q(p(0),q(0))) of the flock is finite and the initial graph G is connected before the fission process, when conflict external stimuli cause the rapid maneuvering of individuals that lie on the edge of the flock, under the fission control law (9), a cohesive flocking system will segregate into clustered subgroups due to the differences of information coupling degree between individuals. Then, the following statements hold.(i)
The distance between individuals in the same subgroup is not larger thanδ, where δ=(Ni-1)2Q0/k1 and Ni is the number of individuals in the subgroup.(ii)
The velocities of individuals in the same subgroup will asymptotically converge to the same value.(iii)
The distance between different subgroups is larger thanR as time goes by.Proof.
We take a cluster ofNi individuals in the neighborhood of individual i into consideration and assume that graph GNi is connected in the small sampling time interval from t to t1.
(i) Letp~ie=pi-pie be the position difference vector between individual i and the external stimuli, and let p~i=pi-pfi, q~i=qi-qfi be the position difference vector and velocity difference vector between individual i and its most correlated neighbor fi, respectively. Then the following equations hold:
(21)pij-pfij=p~i-p~j=p~ij,qij-qfij=q~i-q~j=q~ij.
The control inputui can then be rewritten as
(22)ui=-∑j∈Ni(t)‍∇p~iψijp~i-p~jσ-∑j∈Nit‍aijq~i-q~j-k1p~i-k2q~i-gip~ie.
Substituting (21) into (19) yields
(23)Q=12∑i=1Ni‍∑j∈Nit‍ψijp~ijσ+q~iTq~i∑j∈Nit‍+k1p~iTp~i+gip~ieTp~ie.
Due to the symmetry of the artificial potential functionψij and adjacency matrix A, we have
(24)∂ψijp~ijσ∂p~ij=∂ψijp~ijσ∂p~i=-∂ψijp~ijσ∂p~j.
Taking the derivative ofQ, we can obtain
(25)Q˙=12∑i=1Ni‍∑j∈Nit‍ψ˙ijp~i-p~jσ∑j∈Nit‍+2k1q~iTp~i+2q~iTui+2gip~˙ieTp~ie=12∑i=1Ni‍∑j∈Nit‍p~˙iT∇p~iψijp~i-p~jσ-∑j∈Nit‍p~˙jT∇p~jψijp~i-p~jσ+2k1q~iTp~i+2q~iT-∑j∈Ni‍∇p~iψijp~i-p~jσ-∑j∈Nit‍aijq~i-q~j-k1p~i-k2q~i-gip~ie∑j∈Nit‍+2giq~iTp~ie=∑i=1Ni‍q~iT-∑j∈Nit‍aijq~i-q~j-k2q~i=-q~TLp~+k2INi⊗Inq~,
where L(p~) is the Laplacian matrix of graph G(p~), p~=col(p~1,p~2,…,p~Ni)∈RNi×n, q~=col(q~1,q~2,…,q~Ni)∈RNi×n, and INi is the Ni dimensional identity matrix.
AsL(p~) is positive semidefinite, Q˙<0, hence Q is a nonincreasing function. As the initial energy Q0 of the subgroup is finite, for any sampling time interval t~t1, Q<Q0. Form (23), we have k1p~iTp~i≤2Q0. Accordingly, the distance between individual i and its most correlated neighbor is not greater than 2Q0/k1. Due to the connectivity of the subgroup, there exists a joint connected path from individual i to Ni in the small time internal t~t1; therefore the distance between any two individuals is less than δ=(Ni-1)2Q0/k1 in the same subgroup.
(ii) From above,Q<Q0, the set {p~,q~} is closed and bounded. Therefore, the set
(26)Ω=p~T,q~T∈R2Ni×n∣Q≤Q0
is a compact invariant set. According to LaSalle’s invariant set principle, all the trajectories of individuals that start from Ω will converge to the largest invariant set inside the region Ω={[p~T,q~T]∈R2Ni×n∣Q˙=0}. Therefore, the velocity of individual i will converge to that of its most correlated neighbor fi; that is,
(27)qi=qfi.
Without loss of generality, we assume theNith individual in the subgroup is the only one that senses the external stimulus and it responses with fast maneuvering. According to (4), Ni is the most correlated neighbor with largest information coupling degree. In the small time internal t~t1, there exists a joint connected path from individual i to Ni; the velocities of all the individuals in the subgroup will converge to that of the Nith individual asymptotically. Hence, we have
(28)q1=q2=⋯=qNi-1=qNi,
where qNi is the velocity of individual Ni that senses the external stimuli.
(iii) For individualsi and j in different subgroups, as has been illustrated in (i) and (ii), their motion is substantially determined by their most correlated neighbors. Therefore, if the most correlated neighbors of individuals i and j move in opposite directions under different external stimuli, the motion of the two individuals will diverge as time goes by. Hence, we will ultimately have
(29)lim⁡t→∞D>R,
where D=pi-pj is the relative distance between individuals i and j.
From the above proof, we can conclude that, under the fission control algorithm (9), the subgroups are gradually moving out of the sensing range of each other. Meanwhile, the subgroup itself will keep a cohesive whole and move in formation separately.


## 5. Simulation Study

To verify the effectiveness of the proposed fission control algorithm, 40 individuals are chosen to perform the simulation in two-dimensional plane.


### 5.1. Simulation Setup

Suppose the 40 individuals lie randomly within the region of20×20m2 and their initial distribution is connected. The initial velocities are set with arbitrary directions and magnitudes within the range of [010]m/s. The sensing range of each individual is constrained to R=5 m. The other simulation parameters are chosen as rij=0.5, μij=5, c*=0.3, Δt=0.005s, ϵ=0.2, and k1=k2=1.In particular, we consider the case where a flock segregates into two clustered subgroups by introducing two conflict external stimuli towards different directions. Before the fission behavior takes place, we first let individuals aggregate and move in formation with the same velocity of[50]Tm/s. Suppose that, at t=7s, two individuals (e.g., lie on the edge of the flock, we let them be individual 1 and individual 2) sense the two external stimuli separately, other members are not able to sense the external stimuli, and we have g1=g2=1, gi=0, i≠1,2. Meanwhile, the desired positions of individual 1 and individual 2 are updating according to (1) with speeds q1e=[53]Tm/s and q2e=[5-5]Tm/s, respectively.


### 5.2. Simulation Results

Steered by the fission control algorithm (9), a self-organized fission behavior will occur and the simulation results are shown in Figures 3~6.Snapshots of the trajectories of individuals during the fission process, where “∘” represents the initial position of individuals and “•” denotes the final position of each individual. Specifically, “red dot” are the two individuals that sense external stimuli with “red arrow” being their desired directions.
(a)
t
=
6 s
(b)
t
=
9 s
(c)
t
=
12 s
(d)
t
=
15 sFigure3(a) is the snapshot of the flocking system at t=6s, from which it can be seen that individuals aggregate from random distribution and form a cohesive formation; Figure 3(b) shows the response of the flock when individual 1 and individual 2 (denoted by red solid dots) sense the external stimuli; individuals in the flock tend to change their movements to different directions due to the pairwise interaction rule. In Figure 3(c), the flock segregates into subgroups and two clusters emerge. In Figure 3(d), the subgroups run out of the sensing range of each other and the segregated subgroups move in formation separately.Figures4(a) and 4(b) give the plot of the velocities of individuals during the fission process in both x- and y-axis, from which we can see that before two external stimuli appear (t<7s), individuals move in formation and their velocities asymptotically converge to [50]Tm/s; at t=7s, under the fission control algorithm, fission behavior occurs and the velocities of the two subgroups tend to that of the individuals who sense the external stimuli. Consequently, the velocities of individuals in subgroup 1 converge to [53]Tm/s while the velocities of individuals in subgroup 2 converge to [5-5]Tm/s.Velocity of individuals during the fission process.
(a)
Velocity ofx-axis
(b)
Velocity ofy-axisIn addition, we utilize the average distance of individuals to illustrate the fission behavior in a more intuitional way. The average distancedavg is represented by
(30)davg=1Ni∑i=1Ni∑j=1Nipi-pj,
where Ni is the number of individuals in the flock.Figure5 shows the average distance between individuals during the simulation, where blue line denotes the average distance of all the individuals while red dash line and black dash dot line represent the average distance of individuals in subgroup 1 and subgroup 2, respectively. We can clearly see that the three lines tend to converge to a fixed value before segregation (t<7s). When the fission behavior occurs, the average distance of all the individuals increases with time, denoting the divergence of the two subgroups. On the contrary, the average distances of the two subgroups tend to maintain a constant value (about 3m), which demonstrates that the two subgroups are moving in stable formation.Figure 5
Average distance of the whole group and two separated subgroups.Figure 6
Information coupling degree between individual 1 and its neighbors.Figure6 gives the information coupling degree between individual 1 and its neighbors during the fission process, which clearly demonstrates that before the external stimuli appear (t<7s), the ICD between individual 1 and its neighbors converge to a constant value. This is because, in the steady formation state, the relative position and velocity between individual 1 and its neighbors remain stable. With the introduction of the external stimuli, the ICD between individual 1 and its neighbors begins to vary due to their rapid movement variation, and the ICD between individual 1 and its neighbors in the same subgroup converge to a steady state, while ICD of individual 1 and other individuals in the other subgroup quickly decreases to 0 for the loss of connection between each other.From the above simulation results (Figures3~6) we can conclude that the proposed fission control algorithm is capable of realizing the self-organized fission behavior when the introduction of the external stimuli causes the motion preferences conflict in the flock. Particularly, our approach is neither negotiation nor appointment based but mimics the fission behavior of animal flocks, which is also more feasible, robust, and efficient in engineering application than the centralized approach.


### 5.3. Further Discussion

To better understand the size distribution of subgroups, we define the size ratioS as a specification to evaluate the fission behavior
(31)S=Nmin⁡Nmax⁡,
where Nmin⁡ and Nmax⁡ are the size of the smallest subgroup and biggest subgroup, respectively. Obviously, S∈[0,1]: the bigger S is, the smaller size difference between the two subgroups is. Particularly, when S=1, the numbers of individuals in the two subgroups is the same.Figure7 is the histogram of the size ratio of 40 individuals for 100 times of simulation, from which we can see that about 80% of the results show the size ratio equal to 1 and nearly 10% are close to 1, and only a very small portion of the size ratio is randomly located from 0 to 1. Therefore, it can be concluded that, from a probabilistic perspective, the algorithm proposed in this paper can realize the equal-sized fission control.Figure 7
Histogram statistics for the size ratio of the separated subgroups.Finally, we carry out a comparative simulation using the first algorithm (18) proposed in [7] based on “separation/alignment/repulsion” rules. At t=7s, we introduce two conflict external stimuli on individual 1 and individual 2, and the desired positions of individual 1 and individual 2 are also updating according to (1) with speeds q1e=[53]Tm/s and q2e=[5-5]Tm/s, respectively. Then we have the following the algorithm(32)ui=∑j∈Niψαpj-piσnij+∑j∈Niaijpqj-qi+gipi-pie,g1=g2=1.With the same simulation parameters, the moving trajectories of individuals are shown in Figure8.Figure 8
Trajectories of individuals under the external stimuli with algorithm (32).From Figure8 we can see that only two individuals that sense the external stimuli can split from the group while the rest move in a cohesive formation along its previous trajectory. It can also be seen from the amplified figure that when individual 1 and individual 2 split from the flock, the motion of other individuals tends to fluctuate, but they finally return to the cohesive formation state. The main reason for the above result lies in the “average consensus” approach adopted in (32), which counteracts the external stimuli and leads the flock move towards the average direction of the stimulus signal.Therefore, the traditional “separation/alignment/cohesion” based coordination rules decrease the flexibility and maneuverability of flocking system especially in the case of danger/obstacle avoidance or multiple objects tracking. As a matter of fact, under algorithm (32), fission behavior only occurs when all the individuals can directly sense external stimuli, which is essentially different from our work.


## 5.1. Simulation Setup

Suppose the 40 individuals lie randomly within the region of20×20m2 and their initial distribution is connected. The initial velocities are set with arbitrary directions and magnitudes within the range of [010]m/s. The sensing range of each individual is constrained to R=5 m. The other simulation parameters are chosen as rij=0.5, μij=5, c*=0.3, Δt=0.005s, ϵ=0.2, and k1=k2=1.In particular, we consider the case where a flock segregates into two clustered subgroups by introducing two conflict external stimuli towards different directions. Before the fission behavior takes place, we first let individuals aggregate and move in formation with the same velocity of[50]Tm/s. Suppose that, at t=7s, two individuals (e.g., lie on the edge of the flock, we let them be individual 1 and individual 2) sense the two external stimuli separately, other members are not able to sense the external stimuli, and we have g1=g2=1, gi=0, i≠1,2. Meanwhile, the desired positions of individual 1 and individual 2 are updating according to (1) with speeds q1e=[53]Tm/s and q2e=[5-5]Tm/s, respectively.


## 5.2. Simulation Results

Steered by the fission control algorithm (9), a self-organized fission behavior will occur and the simulation results are shown in Figures 3~6.Snapshots of the trajectories of individuals during the fission process, where “∘” represents the initial position of individuals and “•” denotes the final position of each individual. Specifically, “red dot” are the two individuals that sense external stimuli with “red arrow” being their desired directions.
(a)
t
=
6 s
(b)
t
=
9 s
(c)
t
=
12 s
(d)
t
=
15 sFigure3(a) is the snapshot of the flocking system at t=6s, from which it can be seen that individuals aggregate from random distribution and form a cohesive formation; Figure 3(b) shows the response of the flock when individual 1 and individual 2 (denoted by red solid dots) sense the external stimuli; individuals in the flock tend to change their movements to different directions due to the pairwise interaction rule. In Figure 3(c), the flock segregates into subgroups and two clusters emerge. In Figure 3(d), the subgroups run out of the sensing range of each other and the segregated subgroups move in formation separately.Figures4(a) and 4(b) give the plot of the velocities of individuals during the fission process in both x- and y-axis, from which we can see that before two external stimuli appear (t<7s), individuals move in formation and their velocities asymptotically converge to [50]Tm/s; at t=7s, under the fission control algorithm, fission behavior occurs and the velocities of the two subgroups tend to that of the individuals who sense the external stimuli. Consequently, the velocities of individuals in subgroup 1 converge to [53]Tm/s while the velocities of individuals in subgroup 2 converge to [5-5]Tm/s.Velocity of individuals during the fission process.
(a)
Velocity ofx-axis
(b)
Velocity ofy-axisIn addition, we utilize the average distance of individuals to illustrate the fission behavior in a more intuitional way. The average distancedavg is represented by
(30)davg=1Ni∑i=1Ni∑j=1Nipi-pj,
where Ni is the number of individuals in the flock.Figure5 shows the average distance between individuals during the simulation, where blue line denotes the average distance of all the individuals while red dash line and black dash dot line represent the average distance of individuals in subgroup 1 and subgroup 2, respectively. We can clearly see that the three lines tend to converge to a fixed value before segregation (t<7s). When the fission behavior occurs, the average distance of all the individuals increases with time, denoting the divergence of the two subgroups. On the contrary, the average distances of the two subgroups tend to maintain a constant value (about 3m), which demonstrates that the two subgroups are moving in stable formation.Figure 5
Average distance of the whole group and two separated subgroups.Figure 6
Information coupling degree between individual 1 and its neighbors.Figure6 gives the information coupling degree between individual 1 and its neighbors during the fission process, which clearly demonstrates that before the external stimuli appear (t<7s), the ICD between individual 1 and its neighbors converge to a constant value. This is because, in the steady formation state, the relative position and velocity between individual 1 and its neighbors remain stable. With the introduction of the external stimuli, the ICD between individual 1 and its neighbors begins to vary due to their rapid movement variation, and the ICD between individual 1 and its neighbors in the same subgroup converge to a steady state, while ICD of individual 1 and other individuals in the other subgroup quickly decreases to 0 for the loss of connection between each other.From the above simulation results (Figures3~6) we can conclude that the proposed fission control algorithm is capable of realizing the self-organized fission behavior when the introduction of the external stimuli causes the motion preferences conflict in the flock. Particularly, our approach is neither negotiation nor appointment based but mimics the fission behavior of animal flocks, which is also more feasible, robust, and efficient in engineering application than the centralized approach.


## 5.3. Further Discussion

To better understand the size distribution of subgroups, we define the size ratioS as a specification to evaluate the fission behavior
(31)S=Nmin⁡Nmax⁡,
where Nmin⁡ and Nmax⁡ are the size of the smallest subgroup and biggest subgroup, respectively. Obviously, S∈[0,1]: the bigger S is, the smaller size difference between the two subgroups is. Particularly, when S=1, the numbers of individuals in the two subgroups is the same.Figure7 is the histogram of the size ratio of 40 individuals for 100 times of simulation, from which we can see that about 80% of the results show the size ratio equal to 1 and nearly 10% are close to 1, and only a very small portion of the size ratio is randomly located from 0 to 1. Therefore, it can be concluded that, from a probabilistic perspective, the algorithm proposed in this paper can realize the equal-sized fission control.Figure 7
Histogram statistics for the size ratio of the separated subgroups.Finally, we carry out a comparative simulation using the first algorithm (18) proposed in [7] based on “separation/alignment/repulsion” rules. At t=7s, we introduce two conflict external stimuli on individual 1 and individual 2, and the desired positions of individual 1 and individual 2 are also updating according to (1) with speeds q1e=[53]Tm/s and q2e=[5-5]Tm/s, respectively. Then we have the following the algorithm(32)ui=∑j∈Niψαpj-piσnij+∑j∈Niaijpqj-qi+gipi-pie,g1=g2=1.With the same simulation parameters, the moving trajectories of individuals are shown in Figure8.Figure 8
Trajectories of individuals under the external stimuli with algorithm (32).From Figure8 we can see that only two individuals that sense the external stimuli can split from the group while the rest move in a cohesive formation along its previous trajectory. It can also be seen from the amplified figure that when individual 1 and individual 2 split from the flock, the motion of other individuals tends to fluctuate, but they finally return to the cohesive formation state. The main reason for the above result lies in the “average consensus” approach adopted in (32), which counteracts the external stimuli and leads the flock move towards the average direction of the stimulus signal.Therefore, the traditional “separation/alignment/cohesion” based coordination rules decrease the flexibility and maneuverability of flocking system especially in the case of danger/obstacle avoidance or multiple objects tracking. As a matter of fact, under algorithm (32), fission behavior only occurs when all the individuals can directly sense external stimuli, which is essentially different from our work.


## 6. Conclusion

This paper addresses the fission control problem of flocking system. To overcome the shortcomings of the “average consensus” based interaction rules that encumber the fission behavior, a new pairwise interaction rule is proposed to implement the fission behavior. Firstly, we propose an information coupling degree based approach to describe the internal interaction intensity between individuals. Then, by choosing the neighbors with largest information coupling degree as the most correlated neighbor, we integrate the motion information of the most correlated neighbor into the distributed fission control algorithm to form a strong correlated pairwise interaction, which realizes the directional information flow of external stimuli and induces the fission behavior of the flock in a self-organized fashion. Moreover, theoretical analysis proves that a flock will segregate into clustered subgroups when external stimuli cause the motion information conflict in it. Finally, simulation studies demonstrate the effectiveness of the proposed fission control algorithm.



---

*Source: 321781-2015-02-02.xml*