MA Yan, MAO Zhaoyong, QIN Jian, MENG Xiangyao,XIAO Yujie, CHEN Jianhua, and FENG Wei

1. Key Laboratory of Unmanned Underwater Vehicle, Ministry of Industry and Information Technology, School of Marine Science and Technology, Northwestern Polytechnical University, Xi’an 710072, China; 2. Naval Research Academy, Beijing 100161, China

Abstract: Because of the low convergence efficiency of the typical Vicsek model, a Vicsek with static summoning points(VSSP) algorithm based on the Vicsek model considering static summoning points is proposed. Firstly, the mathematical model of the individual movement total cost on each summoning point is established. Then the individual classification rule is designed according to the initial state of the cluster to obtain the subclusters guided by each summoning point. Finally, the summoning factor is introduced to modify the course angle updating formula of the Vicsek model. To verify the effectiveness of the proposed algorithm and study the effect of the cluster summoning factor on the convergence rate, three groups of simulation experiments under different summoning factors are designed in this paper. To verify the superiority of the VSSP algorithm, the performance of the VSSP algorithm is compared with the classic algorithm by designing the algorithm performance comparison verification experiment. The results show that the algorithm proposed in this paper has good convergence and course angle consistency. The summoning factor is the sensitive factor of cluster convergence. This algorithm can provide a reference for efficient cluster segmentation movement.

Keywords: static summoning point, Vicsek model, summoning factor, cluster system.

1. Introduction

Cluster system is ubiquitous in nature and human life,which has important practical significance for the study of cluster movement. The application research of cluster system has been widely carried out in many fields, such as the control and evolution of aviation clusters [1], leader-missile follower-missile cluster distributed guidance[2], time-varying formation tracking control [3], unmanned aerial combat system [4-9] and so on. In recent years, with the development of underwater unmanned systems, the intelligent technology of underwater clusters has been highly valued, which is of great significance to the research on the movement model of underwater cluster systems.

The research on cluster systems is mainly realized by establishing corresponding models. Typical cluster models include the Vicsek model, the Boid model, the threecircle model, the leader-follower model, and so on.However, these classic models have their shortcomings,so many scholars have improved them to enhance the performance of models. Given the slow convergence speed and low consistency of the Vicsek model, Gao et al. [10]proposed a new method to improve the convergence efficiency of the Vicsek model by using the topological structure of a dynamic network and combining the concept of the moderate degree of complexity network.This method can improve the convergence speed and consistency of the system. Aiming at the problem that convergence efficiency of the Vicsek model is not high,Chen et al. [11] proposed a new rule that takes the median value of the movement direction of two neighboring individuals with the largest deviation of the movement direction within the set of individual neighborhoods as the motion direction of the next moment. The speed of the improved model under the control rule to achieve the direction uniformity is obviously accelerated. Jiang [12]proposed a heterogeneous speed adaptive cluster model based on the Vicsek model and studied the convergence speed and convergence probability of cluster. Tian [13]proposed a limited perspective model based on the Vicsek model and found that there is an optimal perspective for clusters, so that clusters can achieve synchronization as quickly as possible. Wang [14] added limited horizon constraints and neighborhood weights to the Vicsek model and studied the connectivity of ad-hoc communication networks. Olfati-Saber discussed how to use dynamic networks to model the behavior of multi-agent clusters[15], and extended the idea of multi-agents clustering in free space to multi-obstacle space [16]. The Olfati-Saber algorithm uses an improved potential field function to enable agents to avoid obstacles and move toward the target point, which improves the limitation of potential field traps and has become a classic multi-agents cluster control algorithm. Ye et al. [17] studied the aggregation and segmentation evolutionary behavior of the cluster system.Luo et al. [18] studied the cluster behavior of the pigeon herd. Li et al. [19] established a dynamic model of the cluster with an attention mechanism.

To solve the problem of low convergence efficiency of the Vicsek model, this paper proposes to add static summoning points based on the classic Vicsek model, so that the movements of all individuals in the group can quickly reach a consensus according to the summoning direction,and the equation of movement direction update in the Vicsek model is improved. The cluster consistency verification experiment is designed for verifying the effectiveness of the Vicsek with static summoning points(VSSP) algorithm in this paper. To verify the superiority of the VSSP algorithm, the Vicsek algorithm and the Olfati Saber algorithm are compared with the VSSP algorithm respectively, and the algorithm performance comparison verification experiment is designed. The experimental results verify the good performance of the algorithm in this paper. This algorithm can provide a reference for efficient cluster segmentation movement.

2. Classic Vicsek model

The Vicsek model [20-30] is a discrete-time cluster system composed ofNautonomous individuals. They move at the same speedvin the plane, and the course angle of each individual is updated according to the average of its neighbors ’ course angles vector. The neighbors of individualiconsist of individuals centered on the individual’s current position (xi(t),yi(t)) and having a Euclidean distance from the individual less than the normal numberr.Ni(t) is used to express the neighbors of individualiat timet, that is

Each individual is its own neighbor. Each moves at a constant positive speedvin the plane, so the position of each individual is updated as

where θi(t) is the course angle of individualiat timet,which is updated as

It is noted that the dynamic behavior of the above system is completely determined by the initial state (initial course angle and initial position), the neighborhood radiusr, and the movement speedv. The neighbors of each individual are determined by the position of other individuals, and the course angle of each individual is determined by the neighbors’ course angle. Similarly, the course angle also affects the position. Therefore, a complex non-linear relationship is formed between the positions and course angles of all individuals.

Synchronization of the multi-agent system above means that the course angles of all individuals meet the condition:

whereθmay depend on the initial stateand the system parametersv,r.

3. An improved Vicsek model with static summoning points

Because of the low convergence efficiency of the Vicsek model which describes the dynamic behavior of cluster,this paper proposes to add static summoning points based on the classic Vicsek model for making all the individual movements in the group quickly reach a consensus according to the summoning direction, and the movement direction update equation of the Vicsek model and its linearized model is replaced.

3.1 Individual classification of the initial group

All individuals in the cluster will be guided by summoning points in the process of movement. When there are multiple summoning points, it is necessary to classify all the individuals in the group first, and clarify the subcluster guided by each summoning point, because dynamic behavior of the cluster system based on the Vicsek model is completely determined by the initial state (initial course angle and initial position), the neighborhood radiusr, and the movement speedv. When the neighborhood radius and movement speed of the cluster system are given, movement of the cluster system is completely determined by the initial course angle and position of each individual. Therefore, the classification of subclusters is also based on the course angle and position of the cluster at the initial state.

Suppose there arePstatic summoning points in the system, and the position of summoning pointpis expressed as (xp,yp) (p=1,2, ···,P).Rpis used to represent the subcluster guided by the summoning pointpin the cluster. To make the cluster reach the consensus quickly at the summoning direction in the optimal state, the total movement cost of the individual to each summoning point (distance cost and summoning diversion cost) needs to be considered to ensure that each individual is assigned to the summoning point with the minimal total movement cost.

3.1.1 Total cost model of movement

(i) Distance cost The distance cost of individualiin the subcluster guided by summoning pointpat timetis recorded asdcip(t). The distance cost is the normalized value of Euclidean distance from the individual to the summoning point.

(ii) Summoning diversion angle costtis denoted as θi(t). The angle between the direct line of As shown in Fig.1, the course angle of individualiat time individualiat timetpointing to summoning pointpand the horizontal coordinate axis is defined as the summoning angle of the summoning point to the individual,which is denoted as γip(t). The summoning diversion angle ψip(t) of summoning pointpto the individualiat timetis the difference between the course angle of individualiand the summoning angle of summoning pointpto the individuali. The summoning diversion angle cost of summoning pointpto the individualiis recorded as ψcip(t), and the summoning diversion angle cost is the normalized value of the summoning diversion angle from the summoning point to the individual.

Fig. 1 Summoning diversion angle diagram

(iii) Movement total cost The movement total costMcip(t) is the weighted sum of distance cost and summoning diversion angle cost when individualiis classified into subclusters of summoning pointpat timet. Distance cost coefficientdcoefand summoning diversion angle cost coefficient ψcoefare introduced respectively, and they meet the requirement of

3.1.2 Individual classification rules in the initial cluster T

he individual classification in the cluster is completely determined by the course angle and position of the group in an initial state, and the total movement cost matrix of the cluster at the initial time is denoted asMcN×P.

Definition 1SupposeAis a matrix, and min (A, 1) returns the column position where the minimum value of each row in matrixAis located. The vectorRcis the summoning point typeset with the lowest total cost of all individuals in the cluster.

Then the subclusterRpguided by summoning pointpcan be expressed as

Thus, the types of summoning points to which all the individuals in the cluster belong have been determined,and all individuals in the subclusterRpwill quickly reach a consensus in the optimal state according to the direction of summoning pointp.

3.2 Updating equation of course angle

In this paper, static summoning points are added to increase course guidance factors in the movement process of individuals in the cluster. The updating formula of the course angle in the typical Vicsek model needs to be modified under the considering of influence from static summoning points. The updated formula of the modified course angle is

where η is the summoning factor, η∈(0,1).

4. Simulation and analysis

The improved Vicsek algorithm with static summoning points has a good cluster segmentation effect, and the convergence speed has been greatly improved. To verify the effectiveness of the algorithm proposed in this paper,a cluster segmentation consistency verification experiment is carried out. Because the summoning factor has a great influence on the convergence speed of the cluster movement, this paper has carried out comparative simulation experiments under different summoning factors. To verify the superiority of the algorithm proposed in this paper, the performance comparison experiment is designed.

Parameter settings:N=300,P=3,r=0.8,v=0.02,dcoef=0.4, ψcoef=0.6, coordinates of the summoning points set {(0,0), (3,6), (6,0)},ηis set by 0.3, 0.25, 0.15 respectively. At the initial time, the cluster is randomly distributed in the square range of ([2,4], [2,4]) with the Gaussian distribution. The simulation step is unit 1 and the number of iterations is 120.

To quantitatively evaluate the convergence consistency and convergence speed of the designed algorithm,the quantitative evaluation index of maneuver consistency parameter and convergence time defined in [31] are cited. The maneuver consistency parameterVPand convergence timeTcare expressed as

4.1 Verification of cluster segmentation consistency

In this paper, three groups of simulation experiments are carried out when the summoning factor values are 0.3,0.25 and 0.15 respectively. Fig. 2 shows the spatial distribution state of cluster individuals at typical times whenη=0.15 (the spatial dynamic distribution state of cluster individuals atη=0.3 andη=0.25 is similar to that atη=0.15, which will not be shown here). The arrow direction of each point in Fig. 2 is the direction of the individual at this moment, and the black solid box is the summoning point, the points marked in red, blue, and green are used to represent the subclusters classified into summoning points (0,0), (3,6), (6,0) respectively.

Fig. 2 Spatial distribution of individuals in a cluster at the typical time when η= 0.15

It can be seen from Fig. 2 that under the guidance of the summoning point, each subcluster quickly separates and moves to the corresponding summoning point. At the beginning of the cluster movement, each individual is constantly adjusting his course due to the great initial course difference of each individual. It makes subcluster course of the same summoning point reach the same, so there will be the phenomenon of individual wandering near the initial position. When all individuals adjust their course angles to reach the same direction as the summoning point, the subclusters will be quickly separated. It can be seen that the subclusters are completely separated and the cluster segmentation consistency is good.

4.2 Effect of summoning factor on the convergence rate

To analyze the influence of the summoning factor on the convergence rate of the cluster, three groups of simulation comparison experiments are carried out when the summoning factor values are 0.3, 0.25 and 0.15 respectively, the results are shown in Fig. 3 to Fig. 5.

Fig. 3 Simulation results when η=0.3

Fig. 4 Simulation results when η=0.25

Fig. 5 Simulation results when η=0.15

According to the simulation results: (i) With the decrease of the summoning factor, the convergence rate of a cluster is slowing down. Whenη=0.3, the course angles of all individuals in the cluster tend to be consistent after about 25 iterations, whenη=0.25, that tends to be consistent after about 32 iterations, whenη=0.15, it tends to be consistent after about 50 iterations. (ii) The trajectory of individuals in the cluster changes greatly in the early stage of the movement. This is because before course angles of subclusters reaching consistent, the course angles of subclusters are constantly adjusted under the guidance of the summoning point. (iii) The final course angles of the subclusters guided by the three summoning points converge to -135°, 90° and -45° respectively, and the cluster segmentation has a good consistency. (iv) At the beginning of the calculation, the course angle-time curve of individuals show the oscillation of the course angle. This is because the updating of the course angle is related to the course angle of other individuals in its neighborhood, where individuals belong to a subcluster of another summoning point, which has an impact on the update of the course angle.

4.3 Comparison and verification of algorithm performance

4.3.1 Comparison and verification for cluster segmentation consistency of different algorithms

To verify the superiority of the VSSP algorithm proposed in this paper, the performance of the basic Vicsek algorithm and the classic Olfati-Saber algorithm in this field are compared with the VSSP algorithm. In the simulation environment of Section 4.1, simulation experiments are carried out based on the VSSP algorithm, the Olfati-Saber algorithm, and the basic Vicsek algorithm.The summoning factor in the environment isη= 0.45.Fig. 6 shows the comparison results of the maneuver consistency parameter time history curves of the three algorithms. Table 1 shows the comparison results of the convergence time indicator of the three algorithms in the environment.

Fig. 6 Time history curve of maneuver consistency parameter VP for the three algorithms when η=0.45

Table 1 Comparison results of the convergence time indicator Tc of the three algorithms when η=0.45

From the simulation results in Fig. 6 and Table 1, the following conclusions can be drawn: (i) Whether it is comparing the maneuver consistency parameterVPor comparing the convergence time indicatorTc, not only the convergence consistency of the VSSP algorithm proposed in this paper is superior to the Olfati-Saber algorithm and the basic Vicsek algorithm, but also the convergence time is significantly shorter than the other two algorithms. (ii) The Olfati-Saber algorithm converges very quickly in the initial stage, but within a relatively high convergence consistency range, its convergence rate is slow. However, the VSSP algorithm converges at a faster convergence rate throughout the entire process,which shows a better convergence performance. Through the comparative experiments, the superiority of the algorithm proposed in this paper can be verified. (iii) The comparison results between the VSSP algorithm and the basic Vicsek algorithm show that adding static summoning points to the typical Vicsek model can greatly improve the convergence performance of the cluster movement. The comparison results between the VSSP algorithm and the Olfati-Saber algorithm show that the algorithm proposed in this paper has certain advantages.

In order to further verify the superiority of the VSSP algorithm, different simulation environments need to be set up for horizontal comparison. In Subection 4.3.2, the three algorithms are compared and verified by setting up the simulation environments for clusters of different scales. And in Subection 4.3.3, the three algorithms are compared and verified by setting the simulation environment with different numbers of summoning points.

4.3.2 Comparison and verification of algorithms under different cluster scales

In this group of comparative experiments, the parameter settings are as follows:η=0.35，P=3，r=0.8，v=0.02，dcoef=0.4， ψcoef=0.6. The summoning point set coordinate is {(0,0),(3,6),(6,0)}. The numbers of individuals areN1=100,N2=400,N3=700. At the initial time, the cluster is randomly distributed in the square range of ([2,4], [2,4]) with the Gaussian distribution.The simulation step is unit 1 and the number of iterations is 90. Fig. 7 to Fig. 9 are the simulation results when the numbers of individuals in the cluster are 100,400 and 700 respectively. Since the movement trajectories of all individuals in the cluster and the course angle-time curves of all individuals in the cluster obtained based on the three different algorithms are similar, the subgraphs (a) and (b) in Figs. 7-9 only show the simulation results based on the VSSP algorithm. Table 2 shows the comparison results of the convergence speed of different algorithms in the three environments.

Fig. 7 Simulation results when N=100

Fig. 8 Simulation results when N=400

Fig. 9 Simulation results when N=700

Fig. 10 Simulation results when the number of summoning points P=2

Fig. 11 Simulation results when the number of summoning points P=4

Fig. 12 Simulation results when the number of summoning points P=6

Fig. 13 Simulation results when the number of summoning points P=8

From the simulation results in Figs. 7-9 and Table 2,the following conclusions can be drawn: (i) As the number of individuals in the cluster increases, the convergence speed of the maneuver consistency parameterVPof the Olfati-Saber algorithm and the Vicsek algorithm becomes slower, and the convergence time indexTcbecomes larger, while the convergence speed of the VSSP algorithm is almost unchanged. This shows that the VSSP algorithm has a strong adaptability to large-scale segmenting movement. (ii) When the cluster scale is small,the convergence speed of the Olfati-Saber algorithm is significantly better than that of the Vecsek algorithm, but as the cluster scale increases, the advantage of the Olfati-Saber algorithm gradually disappears.

Table 2 Comparison results of convergence time of different algorithms in the three environments

4.3.3 Comparison and verification of algorithms under different summoning points

In this group of comparative experiments, the parameter settings are as follows:N=300，η=0.45，P=3，r=0.8，v=0.02，dcoef=0.4， ψcoef=0.6. When the number of summoning pointsP1=2, the coordinate of the summoning point set is {(0,0), (6,6)}; whenP2=4, the coordinate of the summoning point set is {(0,0), (0,6), (6,0), (6,6)};whenP3=6, the coordinate of the summoning point set is{(3,0), (0,1.5), (0,4.5), (3,6), (6,4.5), (6,1.5)}; whenP4=8,the coordinate of the summoning point set is {(1.5,0),(0,1.5), (0,4.5), (1.5,6), (4.5,6), (6,4.5), (6,1.5), (4.5,0)}.At the initial time, the cluster is randomly distributed in the square range of ([2,4], [2,4]) with the Gaussian distribution. The simulation step is unit 1 and the number of iterations is 90 times. Figs. 10-13 are the simulation results when the numbers of summoning points in the cluster are 2, 4, 6 and 8 respectively. Since the movement trajectories of all individuals in the cluster and the course angletime curves of all individuals in the cluster obtained based on the three different algorithms are similar, the subgraphs (c) and (d) in Figs. 10-13 only show the simulation results based on the VSSP algorithm. Table 3 shows the comparison results of the convergence speed of different algorithms in the four environments.

Table 3 Comparison results of convergence time of different algorithms in the four environments

From the simulation results in Figs. 10-13 and Table 3,the following conclusions can be drawn: (i) As the number of summoning points in the environment increases,the more types of clusters need to be classified, the more difficult it is to segment the clusters, and the convergence speed of the three algorithms is all slowed down.(ii) With the increase of cluster classification, the segmentation performance of the Olfati-Saber algorithm and the Vicsek algorithm deteriorates sharply, while the VSSP algorithm shows a strong adaptability.

5. Conclusions

In this paper, based on the typical Vicsek model, static summoning points are introduced to guide the individuals in the cluster to be classified into subclusters, and each subcluster gathers to its corresponding summoning points. It can be seen from the simulation experiment that adding static summoning points to the Vicsek model can greatly improve the convergence rate of the cluster movement, and at the same time make the cluster maintain good course consistency. Through the comparative experiments of different summoning factors, we can see that the summoning factor has a great influence on the convergence rate of the cluster, the larger the summoning factor is, the faster the convergence rate of the cluster is.Through comparison and verification with the typical algorithms of the Olfati-Saber algorithm and the basic Vicsek algorithm, we can see the superiority of the VSSP algorithm.

The method proposed in this paper can be well used in cluster segmentation, but in practice, the summoning points are more dynamic. Besides, the proposed method cannot be used for cluster gathering. These problems are what we need to further study later.