# Combined AGADESN with DBSCAN Algorithm for Cluster Target Motion Intention Recognition

Authors: Xirui Xue; Shucai Huang; Daozhi Wei
Journal: International Journal of Aerospace Engineering
 (2022)

---

## Abstract

In this paper, we consider the problem of motion intention recognition for cluster targets with splitting behaviour and lack of motion prior information. This is a challenge to the classical Bayesian inference based intention recognition algorithms because they rely heavily on a priori knowledge. In order to solve these problems, a joint algorithm of deep echo state network optimized by adaptive genetic algorithm (AGADESN) and DBSCAN clustering algorithm is proposed in this paper. We use improved Olfati-Saber model with direction noise to generate cluster motion and use the cluster motion data to drive AGADESN algorithm to predict cluster destination, which achieves higher destination prediction accuracy than DESN algorithm. We innovatively design the motion similarity distance (MSD) and take the destination prediction output as one of the distance inputs, alleviating the lack of differentiation among different cluster targets caused by only relying on speed and position distance at the early stage of cluster motion. Based on the MSD, DBSCAN clustering algorithm is used to identify clusters in the field of view to determine whether splitting behaviour occurs. Simulation results demonstrate the effectiveness of the proposed algorithm in cluster target motion intention recognition and its superiority over DESN algorithm and DBSCAN algorithm only based on speed and position distance.


---

## Body

## 1. Introduction

In recent years, the recognition and prediction of the moving intention of cluster targets have attracted extensive attention. Cluster target intention recognition and prediction refers to the automatic evaluation and prediction of a certain goal or plan to be achieved by the cluster target in the region. It is an important function of situation analysis and belongs to the high-level processing part of the data fusion system [1]. At present, UAV cluster has been used in environmental detection, target tracking, and other aspects and has also been widely used in several recent regional conflicts. Solving the problem of cluster intention recognition would help better solve the problems of UAV cluster control [2, 3], target tracking [4], path planning [5, 6], etc. In particular, in UAV path planning, it is very important to effectively infer the intention of UAV clusters to solve the coverage path planning problem [7, 8]. However, due to the difficulty of modeling cluster trajectory, the lack of prior information about the motion and the existence of multiple motion patterns such as splitting and merging, it is difficult to recognize cluster motion intention. In addition, some clusters have strong autonomous ability, obvious heterogeneous characteristics and automatic path planning ability, which brings more difficulties to the recognition of cluster motion intention [9, 10].In order to solve these problems, it is necessary to establish a reasonable collaborative motion model of cluster targets. A pioneering study by Reynolds [11] demonstrated that cluster motion follows three basic collaborative rules: separation, speed matching, and aggregation. A similar approach is proposed by Vicsek et al. [12], who believed that the collaborative motion comes from adjusting the speed of cluster members to the average speed in their neighbourhood. Other studies have focused on the dynamic behaviour of clusters. For example, Couzin et al. [13] attempted to explain the clustering phenomenon under effective guidance and group decision-making. However, clusters described only by three basic collaborative rules are prone to fracture due to the dispersion of member positions. On the basis of the basic rules, Olfati-Saber [14] designed and added the virtual leader in order to solve the problem of cluster fracture. However, the assumption in the basic Olfati-Saber model that the virtual leader information is accurate all the time is too idealistic. Considering the difficulty of virtual leader information acquisition in the actual cluster movement process, Gaussian noise with time-varying variance is introduced to make the cluster cooperative motion model more realistic.Traditional cluster target intention recognition mainly relies on Bayesian network inference framework [15]. Bayesian reasoning has the advantages of dealing with the inherent uncertainty of sensor data and the inherent semantic fuzziness of intention recognition, supporting the relearning of reasoning network parameters [16, 17]. In order to overcome the problem of aircraft carrier group target intention reasoning in multidomain operations and multientity hierarchical, Bayesian network is used by Qiao et al. [18]. However, model-driven Bayesian reasoning inevitably needs to use the prior statistical information of the target, which is usually difficult for us to obtain. Especially in the military field, the random, sudden, and unknown maneuver of enemy UAV cluster targets further increase the difficulty of obtaining prior information.In recent decades, sensor and computer technology have promoted the rapid development of big data processing. In particular, deep learning and neural networks have made many impressive advances and have excellent performance in intention recognition [19, 20]. In order to recognize and predict the motion intention of cluster targets, the data-driven neural network method needs to use the target motion sequence information. Echo state network (ESN) is widely used in time series prediction because of its simple structure and efficient training [21]. However, the motion sequence information of cluster targets is more complex, and the prediction ability of ESN is insufficient. Accordingly, some scholars have proposed a deep echo state network (DESN) model [22, 23].In this paper, we divide cluster target intention recognition into two parts: destination prediction and cluster identification. Song et al. [24] used DESN to predict taxi destination. However, in order to achieve the lowest learning error, arbitrarily set network parameters may not guarantee the best training results of DESN. Chen and Zhang and Lu et al. [25, 26], respectively, used grey wolf algorithm and genetic algorithm (GA) to optimize DESN parameters. However, in the process of application, we find that DESN optimized by GA converges slowly, and the parameter optimization result after convergence is not ideal. Accordingly, we further develop the optimization process of GA and propose a genetic algorithm with adaptive mutation rate [27] to optimize DESN.In terms of cluster identification, Snidaro et al.[28] used the evidence reasoning algorithm in D-S evidence theory, with the help of prior knowledge and multisensor detection information, to complete the identifying and clustering of targets. Oxenham et al. [29] extracted the situation elements of Bayesian network and used data mining to achieve target clustering. However, due to the small size of the cluster target members, under the existing detection conditions, the members attribute information is difficult to obtain. Moreover, the cluster motion prior information is difficult to obtain, so traditional clustering algorithm is still one of the most effective cluster identification algorithms.Clustering algorithms mainly include data-based clustering algorithms and parameter-likelihood-based clustering algorithms [30]. Data-based clustering algorithms include hierarchical clustering [31] and partitioned clustering such as k-means estimator [32]. Density-based noise application spatial clustering (DBSCAN) is a typical data-based clustering algorithm [33, 34], which can be used to solve the clustering problem with uncertain data. However, when the distance between target members is close, the performance of DBSCAN algorithm decreases. This paper defines a new distance measure based on destination prediction, which is called motion similarity distance (MSD). At this distance, DBSCAN algorithm is applied to cluster identification, and a good clustering effect is achieved.A joint algorithm of AGADESN and DBSCAN is proposed to solve the problem of cluster target motion intention recognition under the condition of lack of motion prior information and cluster splitting. The main contributions of this paper are described as follows:(1)
The direction noise with time-varying variance is introduced to improve the virtual leader. Under the framework of Olfati-Saber model, a more practical cluster target collaborative motion model is proposed. The proposed algorithm takes into account the source of command information when the cluster is moving, describes the process of gradually reducing the noise in the moving direction as the cluster approaches the destination, and considers the compensation of the cluster speed for the noise interference(2)
The adaptive mutation rate is introduced into the genetic algorithm, and the adaptive genetic algorithm with faster iteration speed is used to optimize the parameters of the DESN. The AGADESN algorithm is proposed(3)
Based on the cluster motion model proposed in this paper, the cluster motion trajectory dataset for training and test is established, and under the sliding window structure, the cluster motion destination is predicted by using AGADESN model. Experimental results show that our algorithm improves the correct prediction ratio of basic DESN algorithm by 8.39%.(4)
A new distance measure MSD is proposed, which combines the predicted destination distance with the position distance and speed distance, and the DBSCAN algorithm is used to identify the cluster to judge the splitting behaviour on the MSD. The experimental results show that the DBSCAN algorithm using MSD can quickly identify the clusters in the sensor field of view and has stronger robustness when the number of clusters changes.The rest of this paper is organized as follows. In Section2, improved Olfati-Saber is used to describe the cluster collaborative motion. In Section 3, we introduce the joint algorithm of motion intention recognition. Section 4 analyses the generated cluster motion trajectory and gives the results and discussion of the motion intention recognition simulation experiment. Section 5 summarizes the paper.


## 2. Cluster Collaborative Motion Model

### 2.1. Fundamentals of the Olfati-Saber Model

The Olfati-Saber cluster collaborative motion model adds a virtual leader on the basis of the three cluster collaborative motion principles of separation, speed matching and aggregation. All members of the cluster can obtain the position and speed information of the virtual leader. After simplifying the cluster members into the particle model, at timet, the Olfati-Saber model describes the motion of member i as follows:
(1)q̇it=pit,ṗit=uit,whereqit and pit are the position and speed vectors of member i at time t, respectively. uit is the control input of member i at time t. According to the principle of cluster collaborative motion proposed by Olfati-Saber model, uit is designed as follows:
(2)uit=fis+fim+fil,wherefis is the separation and aggregation control input, which is used to adjust the spacing between members to avoid collisions between members. fim is the speed matching control input, which ensures the information transmission within the cluster, makes the cluster topology have weak connectivity, and realizes the gradual consistency of the members’ speed. fil is the control input of the virtual leader, which is used to plan the overall motion path of the cluster.The description offis is shown as follows:
(3)fis=−∑j∈Nit∇qiΨαqj−qiσ,where⋅σ represents the σ-norm, and its calculation method is shown as follows:
(4)zσ=1ε1+εz2−1.Here, the fixed parameter isε∈0,1.qj−qiσ denotes the σ-norm distance between member i and member j. Nit represents the set of members in the neighbourhood of member i that can interact with member i. Neighborhood can be selected according to different metrics, and widely used distance metrics include Euclidean distance and topological distance [35, 36].Ψα⋅ represents the potential energy function, which needs to meet the requirements of continuity, differentiability, and nonnegativity, and its magnitude is related to the distance between the two members. ∇Ψα⋅ represents the gradient of the potential energy function, so as to convert the potential energy into the separation and aggregation control input.The form ofΨα⋅ is defined as follows:
(5)Ψαz=∫dαzΦαsds,whered is the expected distance between members after the member speed converges. dα is the transformation form of σ-norm distance of d and dα=dσ.Φa⋅ is the potential force function between members. When the distance between member i and member j is less than the distance threshold, there is repulsive force between them to prevent collision. Otherwise, there is an attractive force to promote the cluster aggregation. The expression of Φa⋅ is as follows:
(6)Φαz=ρhz/rαΦz−dα,whererα is the finite cut-off point, and rα=rσ. r represents the maximum distance that information interaction can occur between members. ρhz is the smooth scalar function with a value range of [0, 1] [37]. The introduction of ρhz makes the potential force have limited extreme values and makes the spatial adjacency matrix smoother, which is defined as follows:
(7)ρhz=1z∈0,h,121+cosπz−h1−hz∈h,1,0otherwise,Φz is a nonuniform s-shaped function, expressed as follows:
(8)Φz=12a+bz+c1+z+c2+a−b.To ensureΦ0=0, the parameters in the Equation (8) need to meet 0<a≤b and c=a−b/4ab.The description offim is shown as follows:
(9)fim=∑j∈Nitaijqpj−pi,where(10)aijq=ρhqj−qiσrαj≠i,0j=i.Andaijq forms the spatial adjacency matrix.The description offil is shown as follows:
(11)fil=c1ql−qi+c2pl−pi,wherec1 and c2 are the coefficient of the virtual leader, and only the position matching or speed matching between the cluster members and the virtual leader can be considered in the assignment process to make c1=0 or c2=0.


### 2.2. Virtual Leader Model with Direction Noise

In this paper, during the motion of the cluster to the destination, the position of the virtual leader at each time is taken as the center of the cluster. So, the position matching parameterc1=0. Considering only the speed matching with the virtual leader, the speed magnitude plt and direction vector nlt of the virtual leader at time t are given as follows:
(12)plt=γtqlt−qdtTt−t,(13)nlt=cosθt,sinθtT,whereTt represents the total time for the cluster to move to the destination. qlt represents the position of the virtual leader at time t, that is, the position of the cluster center. qdt indicates the destination location at time t. γt is the speed compensation parameter, which meets γt≥1. θt is the motion direction of the virtual leader at time t. Because there is noise when obtaining θt; it is a random variable.Generally, as the cluster approaches the destination, the more accurately the cluster detects the position information of the destination, the smaller the noise of direction would be. Therefore, we modelθt as a Gaussian distribution that obeys time-varying variance, that is, θt∼Nθ¯t,Rθt. Where θ¯t is the accurate direction and Rθt is its time-varying variance, which is defined as follows:
(14)Rθt=δqlt−qdt2,whereδ is the noise variance control coefficient.Due to the influence of noise, the speed of the virtual leader moving to the destination is always a component ofplt, so it is necessary to add the coefficient γt to compensate. The γt is related to Rθt, and γt=fγqlt. The mean value of noise is compensated, so the following results can be obtained by solving fγqlt.
(15)fγqlt=1/cos∫θ¯tθ¯t+πθt−θ¯t2πRθte−θ−θ¯t2/2Rθtdθt=1/cos1−e−π2/2RθtRθt2π.Generally, the value ofδ is very small to guarantee qlt−qdtδ<π. When this is true, γt≥1. According to Equation (15), as the virtual leader approaches the destination, Rθt approaches 0 and γt approaches 1.


## 2.1. Fundamentals of the Olfati-Saber Model

The Olfati-Saber cluster collaborative motion model adds a virtual leader on the basis of the three cluster collaborative motion principles of separation, speed matching and aggregation. All members of the cluster can obtain the position and speed information of the virtual leader. After simplifying the cluster members into the particle model, at timet, the Olfati-Saber model describes the motion of member i as follows:
(1)q̇it=pit,ṗit=uit,whereqit and pit are the position and speed vectors of member i at time t, respectively. uit is the control input of member i at time t. According to the principle of cluster collaborative motion proposed by Olfati-Saber model, uit is designed as follows:
(2)uit=fis+fim+fil,wherefis is the separation and aggregation control input, which is used to adjust the spacing between members to avoid collisions between members. fim is the speed matching control input, which ensures the information transmission within the cluster, makes the cluster topology have weak connectivity, and realizes the gradual consistency of the members’ speed. fil is the control input of the virtual leader, which is used to plan the overall motion path of the cluster.The description offis is shown as follows:
(3)fis=−∑j∈Nit∇qiΨαqj−qiσ,where⋅σ represents the σ-norm, and its calculation method is shown as follows:
(4)zσ=1ε1+εz2−1.Here, the fixed parameter isε∈0,1.qj−qiσ denotes the σ-norm distance between member i and member j. Nit represents the set of members in the neighbourhood of member i that can interact with member i. Neighborhood can be selected according to different metrics, and widely used distance metrics include Euclidean distance and topological distance [35, 36].Ψα⋅ represents the potential energy function, which needs to meet the requirements of continuity, differentiability, and nonnegativity, and its magnitude is related to the distance between the two members. ∇Ψα⋅ represents the gradient of the potential energy function, so as to convert the potential energy into the separation and aggregation control input.The form ofΨα⋅ is defined as follows:
(5)Ψαz=∫dαzΦαsds,whered is the expected distance between members after the member speed converges. dα is the transformation form of σ-norm distance of d and dα=dσ.Φa⋅ is the potential force function between members. When the distance between member i and member j is less than the distance threshold, there is repulsive force between them to prevent collision. Otherwise, there is an attractive force to promote the cluster aggregation. The expression of Φa⋅ is as follows:
(6)Φαz=ρhz/rαΦz−dα,whererα is the finite cut-off point, and rα=rσ. r represents the maximum distance that information interaction can occur between members. ρhz is the smooth scalar function with a value range of [0, 1] [37]. The introduction of ρhz makes the potential force have limited extreme values and makes the spatial adjacency matrix smoother, which is defined as follows:
(7)ρhz=1z∈0,h,121+cosπz−h1−hz∈h,1,0otherwise,Φz is a nonuniform s-shaped function, expressed as follows:
(8)Φz=12a+bz+c1+z+c2+a−b.To ensureΦ0=0, the parameters in the Equation (8) need to meet 0<a≤b and c=a−b/4ab.The description offim is shown as follows:
(9)fim=∑j∈Nitaijqpj−pi,where(10)aijq=ρhqj−qiσrαj≠i,0j=i.Andaijq forms the spatial adjacency matrix.The description offil is shown as follows:
(11)fil=c1ql−qi+c2pl−pi,wherec1 and c2 are the coefficient of the virtual leader, and only the position matching or speed matching between the cluster members and the virtual leader can be considered in the assignment process to make c1=0 or c2=0.


## 2.2. Virtual Leader Model with Direction Noise

In this paper, during the motion of the cluster to the destination, the position of the virtual leader at each time is taken as the center of the cluster. So, the position matching parameterc1=0. Considering only the speed matching with the virtual leader, the speed magnitude plt and direction vector nlt of the virtual leader at time t are given as follows:
(12)plt=γtqlt−qdtTt−t,(13)nlt=cosθt,sinθtT,whereTt represents the total time for the cluster to move to the destination. qlt represents the position of the virtual leader at time t, that is, the position of the cluster center. qdt indicates the destination location at time t. γt is the speed compensation parameter, which meets γt≥1. θt is the motion direction of the virtual leader at time t. Because there is noise when obtaining θt; it is a random variable.Generally, as the cluster approaches the destination, the more accurately the cluster detects the position information of the destination, the smaller the noise of direction would be. Therefore, we modelθt as a Gaussian distribution that obeys time-varying variance, that is, θt∼Nθ¯t,Rθt. Where θ¯t is the accurate direction and Rθt is its time-varying variance, which is defined as follows:
(14)Rθt=δqlt−qdt2,whereδ is the noise variance control coefficient.Due to the influence of noise, the speed of the virtual leader moving to the destination is always a component ofplt, so it is necessary to add the coefficient γt to compensate. The γt is related to Rθt, and γt=fγqlt. The mean value of noise is compensated, so the following results can be obtained by solving fγqlt.
(15)fγqlt=1/cos∫θ¯tθ¯t+πθt−θ¯t2πRθte−θ−θ¯t2/2Rθtdθt=1/cos1−e−π2/2RθtRθt2π.Generally, the value ofδ is very small to guarantee qlt−qdtδ<π. When this is true, γt≥1. According to Equation (15), as the virtual leader approaches the destination, Rθt approaches 0 and γt approaches 1.


## 3. Cluster Motion Intention Recognition Method

### 3.1. Intention Recognition Process

Because splitting or merging behavior would occur in the process of cluster moving to the destination, we divide the cluster target motion intention recognition into two parts: destination prediction and cluster identification. We would use the deep echo state network optimized by adaptive genetic algorithm (AGADESN) and DBSCAN clustering algorithm to solve the above two problems. The method process is shown in Figure1.Figure 1
Intention recognition method process.As shown in Figure1, we use the improved Olfati-Saber model with direction noise to generate a cluster motion trajectory dataset, which is divided into two parts: training dataset and test dataset. The datasets are input into AGADESN. The training dataset is used for network training and parameter optimization, and the test dataset is used for destination prediction. The destination prediction output and the predicted destination distance are generated through this process. The predicted destination distance, position distance, and speed distance of the test set are fused to produce the motion similarity distance (MSD). Based on the MSD, the DBSCAN algorithm is used to cluster the targets, and the cluster identification output is generated. The specific operation steps of intention recognition method would be described in the next section.


### 3.2. Destination Prediction Based on AGADESN

#### 3.2.1. Method of Destination Prediction by DESN

Because the target trajectory is constantly updated to the destination in the process of target motion, we need to obtain multiple destination predictions at different stages of the trajectory. To this end, we design a 1-dimensional sliding window structure, as shown in Figure2. The sliding window length is lw, and each sliding length is ls. The first prediction starts when the obtained trajectory length meets the sliding window length. When the update length of track points meets the sliding length, the sliding window updates the training and test data for the second prediction. If the target trajectory update ends after the mth prediction, all destination predictions are completed on the whole trajectory.Figure 2
1-dimensional sliding window structure.The DESN structure used for each prediction is shown in Figure3. DESN combines echo state network (ESN) with deep learning idea, and adds multiple reservoir structures as hidden layers on the basis of ESN, so that DESN can map more complex time series characteristics.Figure 3
Deep echo state network structure.The working mechanism of DESN is as follows. During the mth prediction, the external data enters the input layer and enters reservoir 1 after being weighted by the input weightWin1. The state of reservoir 1 at the previous time is weighted by the weight W1 and summed with the received weighted external input. After the activation function, a new state is generated as the state x1n of reservoir 1 at the current time, and the state is used as the input of reservoir 2. After repeating the above work process, the state xLn of the last reservoir is obtained. The set of all reservoir states is recorded as xn=x1nT,x2nT,⋯xLnTT, and the output is generated by the activation function after the output layer is affected by the output weight. Among them, the maximum number of layers L is called depth, and the network requires a total of Nn=Nn,1+Nn,2+⋯+Nn,L neurons.Equations ((16)–(19)) are the mathematical model of the DESN.
(16)xinln=Winliln+Wlxln−1+bl,(17)iln=un,l=1,xl−1n,l>1,(18)xln=1−alxln−1+alflxinln,(19)yn=gWoutxn.In Equation (16), taking the reservoir l as an example, Winl and Wl represent the input weight and reservoir weight, respectively. bl represents the noise of the reservoir, and iln is the input data. xln is the updated reservoir state, and xinln is the weighted input data of the reservoir. In Equation (17), un represents the external input data. In Equation (18), al represents the leakage parameter of the reservoir l, and al∈0,1. fl⋅ represents the activation function. Generally, fl⋅ is selected as the hyperbolic tangent function. In Equation (19), yn represents the output data, and Wout is the output weight. g⋅ represents the activation function of the output layer, and gx=x is usually selected.DESN’s training and test process are as follows. The training process of the mth prediction is essentially the training of the output weight matrixWout. Firstly, the network parameters are initialized, and the random algorithm is used to generate the input weight Winl, reservoir weight Wl, and noise bl of the DESN, which remain unchanged during the training process. Secondly, if the trajectory sequence is Qm=Q1m,Q2m,⋯,QNm of N targets in the sliding window at the mth prediction, the trajectory sequence of the target i is as follows:
(20)Qim=qim−1⋅lw+1,qim−1⋅lw+2,⋯,qim⋅lw.DivideQm into training sample Qtrm and test sample Qtem. Input the training sample Q1m,Q2m,⋯,QStrm one by one, so as to obtain all reservoir state matrices X=x1,x2,⋯,xStr. Finally, calculate the training output weight Wout. If the destination prediction position output corresponding to the training sample is Y=y1,y2,⋯,yStr, the output weight of the DESN for destination prediction can be obtained according to Equation (21).
(21)Wout=YXTXXT+αE−1,whereα represents a small positive number [38], and E represents the identity matrix. Among them, the destination prediction of the target i is as follows:
(22)yi=qd,im−1⋅lw+1,qd,im−1⋅lw+2,⋯,qd,im⋅lw.qd,it represents the predicted destination position of the ith trajectory sample at time t. After the training, input the test sample Qtem to test the learning effect of the DESN, which can output the destination prediction according to Equation (19) under the trained output weight Wout.


#### 3.2.2. Optimization of DESN Parameters by Adaptive Genetic Algorithm

DESN has reliable time series prediction ability. However, like other deep learning algorithms, its prediction effect is limited by the selection of parameters. The parameters that have the greatest impact on the effect of the algorithm include the number of reservoirsNl, the number of reservoir nodes Nr, and the spectral radius ρ. ρ is one of the most important central parameters representing the reservoir weight matrix.In order to solve the problem of choosing DESN parameters, we use an adaptive genetic algorithm (AGA) with variable mutation rate to optimize the parameters. Compared with traditional genetic algorithm, it can avoid premature convergence and fall into local optimization. The mutation rate of the AGA uses pseudoderivative to consider the time that GA stays at a certain point. The longer the algorithm stays at the local optimal value, the greater the possibility of mutation.Taking the mth prediction as an example, firstly, the parameters of the DESN model are chromosome encoded to correspond to the genetic operator of the AGA. The encoded chromosome of DESN model parameters is as follows:(23)P=Nl,Nr,ρ.Secondly, the fitness function is established to guide the search process of AGA. The design of fitness function affects the convergence speed and prediction accuracy of the algorithm. Generally, the fitness function is converted from the error function of DESN model. For the DESN model, the destination prediction error is naturally regarded as the fitness function. Therefore, the corresponding fitness function of the mth prediction is as follows:(24)FP=1Str×lw∑i=1Str∑j=1lwqd,im−1⋅lw+j−q∧d,im−1⋅lw+j2,whereFP represents the average prediction error of destination position when chromosome P is the DESN model parameter.Finally, according to the chromosome and fitness function established by AGADESN model, the best chromosome is selected through adaptive genetic operation. In the model, the selection operation [39] and crossover operation [40] are consistent with the traditional GA. In the mutation operation, the adaptive mutation rate based on the derivative of fitness function to generation is as follows:
(25)rm=2×sigmoidg−0.5,whererm is the adaptive mutation rate, and sigmoid function is defined as follows:
(26)sigmoidg=11+e−g,whereg is defined as follows:
(27)g=gc−go.Here,gc represents the current generation, and go represents the oldest generation with the same optimal fitness. g, thus, is inversely related to the derivative of the fitness function with respect to generation.The implementation steps of AGADESN are shown in Figure4.Figure 4
Process for implementing AGADESN algorithm.As the figure shows, the specific steps are as follows:Step 1.
Input training data, initialize DESN model parametersNl, Nr, and ρ.Step 2.
Encode the parameters of DESN model and initialize the chromosomes in the population.Step 3.
The best chromosome is selected by genetic manipulation and fitness evaluation.Step 4.
Decode the optimal chromosome to obtain the optimal parameters of the DESN model.Step 5.
Input training data and train DESN model weightWout.Step 6.
Input test data to obtain destination prediction results.


### 3.3. Cluster Identification Based on DBSCAN

#### 3.3.1. Definition of Motion Similarity Distance

According to the cluster collaborative motion model, in the process of moving towards the destination, the members of the same cluster are close to each other and have similar speed vectors, which are the basis for us to cluster the target to identify the cluster. However, a fact that may be ignored is that the same cluster members also have similar destination position predictions, which provide additional information for us to identify clusters.In 2-dimensional case, the motion state vector of targeti at time t is St,it=qi,xt,pi,xt,qi,yt,pi,ytT, and the prediction value of destination is qd,it=qd,i,xt,qd,i,ytT. Due to the sliding window structure, there may be more than one predicted value of the track point at time t, so qd,it is the mean value of all predicted values, as shown in Equation (28).
(28)qd,it=1Z∑j=1Zqd,ijt,whereZ is the number of destination position predicted values at the track point at time t. qd,ijt represents the jth predicted value.We define a new distance measure, which is called motion similarity distance (MSD). The MSD between memberi and member j is shown in Equation (29).
(29)fSt,it,qd,it,St,jt,qd,jt=1−e−w1Rv2/2σRv2+w2Rd2/2σRd2+w3Rp2/2σRp2.Among them,Rv, Rd, and Rp are the speed distance, position distance, and predicted destination distance, respectively. The weight wi≥0i=1,2,3 represents the importance of different distances, and ∑iwi=1. σRv, σRd, and σRp are the standard deviation of the corresponding distance. The distances are calculated as follows:
(30)Rv=pi,xt−pj,xt2+pi,yt−pi,yt21/2,Rd=max0,qi,xt−qj,xt2+qi,yt−qj,yt21/2−De1,Rp=max0,qd,i,xt−qd,j,xt2+qd,i,yt−qd,j,yt21/2−De2,whereDe1 describes the expected distance of members. De2 describes the extended range of destinations.


#### 3.3.2. Principle of DBSCAN Cluster Identification

DBSCAN is an effective density-based clustering algorithm, which can describe the density of data distribution, and then identify clusters of arbitrary shape and effectively distinguish noise points. DBSCAN algorithm sets a field with a radius ofEps around each target data point. If the number of other target data points in a target field reaches the set threshold MinPts, it is considered that the target belongs to the cluster and is the core point. If there are no other target data points in the neighborhood of a target, the target is considered to be a noise point. If there are target data points in the target field, but the number of data points does not meet MinPts, it is considered that the target is a boundary point. Figure 5 shows the schematic diagram of the DBSCAN algorithm.Figure 5
Schematic diagram of the DBSCAN algorithm.As shown in Figure5, the radius of the circle is the clustering radius Eps and set MinPts=2. It can be seen from the figure that the number of data points in the neighborhood of targets (2, 3, 4, 5, and 6) is greater than MinPts,so they are core points. There are only points 2 in the neighborhood of data point 1, so point 1 is a boundary point. There are no other targets in the neighborhood of data point 7, so it is a noise point. We can obtain that (1, 2, 3, 4, 5, and 6) belong to the same cluster. The DBSCAN algorithm flow is as follows:Algorithm 1:DBSCAN algorithm flow.
Input: Uncertain data setD, Clustering radius Eps, Minimal number of neighboring points MinPtsOutput: A set of clusters, types of all the points inDMain function of the algorithm:DBSCAN(D, Eps, MinPts)ClusterNum=0for each target point P in DifP is visitedcontinue to next pointend ifmarkP as visitedEps-Neighborhood=regionQuery(P, Eps)if sizeof(Eps-Neighborhood)<MinPtsmarkP as noiseelseClusterNum=next clusterexpandCluster(P, Eps-Neighborhood, ClusterNum, Eps, MinPts)end ifend forENDregionQuery(P, Eps)returnEps-Neighborhood(P)={Q∈S|D(P,Q)≤Eps}expandCluster(P, Eps-Neighborhood, ClusterNum, Eps, MinPts)addP to cluster ClusterNumfor each point P′ in Eps-NeighborhoodifP′ is not visitedmarkP′ as visitedEps−Neighborhood′ =regionQuery(P′, Eps)if sizeof(Eps−Neighborhood′)>=MinPtsEps-Neighborhood=Eps-Neighborhood joined with Eps−Neighborhood′end ifend ififP′ is not yet member of any clusteraddP′ to cluster ClusterNumend ifend for


## 3.1. Intention Recognition Process

Because splitting or merging behavior would occur in the process of cluster moving to the destination, we divide the cluster target motion intention recognition into two parts: destination prediction and cluster identification. We would use the deep echo state network optimized by adaptive genetic algorithm (AGADESN) and DBSCAN clustering algorithm to solve the above two problems. The method process is shown in Figure1.Figure 1
Intention recognition method process.As shown in Figure1, we use the improved Olfati-Saber model with direction noise to generate a cluster motion trajectory dataset, which is divided into two parts: training dataset and test dataset. The datasets are input into AGADESN. The training dataset is used for network training and parameter optimization, and the test dataset is used for destination prediction. The destination prediction output and the predicted destination distance are generated through this process. The predicted destination distance, position distance, and speed distance of the test set are fused to produce the motion similarity distance (MSD). Based on the MSD, the DBSCAN algorithm is used to cluster the targets, and the cluster identification output is generated. The specific operation steps of intention recognition method would be described in the next section.


## 3.2. Destination Prediction Based on AGADESN

### 3.2.1. Method of Destination Prediction by DESN

Because the target trajectory is constantly updated to the destination in the process of target motion, we need to obtain multiple destination predictions at different stages of the trajectory. To this end, we design a 1-dimensional sliding window structure, as shown in Figure2. The sliding window length is lw, and each sliding length is ls. The first prediction starts when the obtained trajectory length meets the sliding window length. When the update length of track points meets the sliding length, the sliding window updates the training and test data for the second prediction. If the target trajectory update ends after the mth prediction, all destination predictions are completed on the whole trajectory.Figure 2
1-dimensional sliding window structure.The DESN structure used for each prediction is shown in Figure3. DESN combines echo state network (ESN) with deep learning idea, and adds multiple reservoir structures as hidden layers on the basis of ESN, so that DESN can map more complex time series characteristics.Figure 3
Deep echo state network structure.The working mechanism of DESN is as follows. During the mth prediction, the external data enters the input layer and enters reservoir 1 after being weighted by the input weightWin1. The state of reservoir 1 at the previous time is weighted by the weight W1 and summed with the received weighted external input. After the activation function, a new state is generated as the state x1n of reservoir 1 at the current time, and the state is used as the input of reservoir 2. After repeating the above work process, the state xLn of the last reservoir is obtained. The set of all reservoir states is recorded as xn=x1nT,x2nT,⋯xLnTT, and the output is generated by the activation function after the output layer is affected by the output weight. Among them, the maximum number of layers L is called depth, and the network requires a total of Nn=Nn,1+Nn,2+⋯+Nn,L neurons.Equations ((16)–(19)) are the mathematical model of the DESN.
(16)xinln=Winliln+Wlxln−1+bl,(17)iln=un,l=1,xl−1n,l>1,(18)xln=1−alxln−1+alflxinln,(19)yn=gWoutxn.In Equation (16), taking the reservoir l as an example, Winl and Wl represent the input weight and reservoir weight, respectively. bl represents the noise of the reservoir, and iln is the input data. xln is the updated reservoir state, and xinln is the weighted input data of the reservoir. In Equation (17), un represents the external input data. In Equation (18), al represents the leakage parameter of the reservoir l, and al∈0,1. fl⋅ represents the activation function. Generally, fl⋅ is selected as the hyperbolic tangent function. In Equation (19), yn represents the output data, and Wout is the output weight. g⋅ represents the activation function of the output layer, and gx=x is usually selected.DESN’s training and test process are as follows. The training process of the mth prediction is essentially the training of the output weight matrixWout. Firstly, the network parameters are initialized, and the random algorithm is used to generate the input weight Winl, reservoir weight Wl, and noise bl of the DESN, which remain unchanged during the training process. Secondly, if the trajectory sequence is Qm=Q1m,Q2m,⋯,QNm of N targets in the sliding window at the mth prediction, the trajectory sequence of the target i is as follows:
(20)Qim=qim−1⋅lw+1,qim−1⋅lw+2,⋯,qim⋅lw.DivideQm into training sample Qtrm and test sample Qtem. Input the training sample Q1m,Q2m,⋯,QStrm one by one, so as to obtain all reservoir state matrices X=x1,x2,⋯,xStr. Finally, calculate the training output weight Wout. If the destination prediction position output corresponding to the training sample is Y=y1,y2,⋯,yStr, the output weight of the DESN for destination prediction can be obtained according to Equation (21).
(21)Wout=YXTXXT+αE−1,whereα represents a small positive number [38], and E represents the identity matrix. Among them, the destination prediction of the target i is as follows:
(22)yi=qd,im−1⋅lw+1,qd,im−1⋅lw+2,⋯,qd,im⋅lw.qd,it represents the predicted destination position of the ith trajectory sample at time t. After the training, input the test sample Qtem to test the learning effect of the DESN, which can output the destination prediction according to Equation (19) under the trained output weight Wout.


### 3.2.2. Optimization of DESN Parameters by Adaptive Genetic Algorithm

DESN has reliable time series prediction ability. However, like other deep learning algorithms, its prediction effect is limited by the selection of parameters. The parameters that have the greatest impact on the effect of the algorithm include the number of reservoirsNl, the number of reservoir nodes Nr, and the spectral radius ρ. ρ is one of the most important central parameters representing the reservoir weight matrix.In order to solve the problem of choosing DESN parameters, we use an adaptive genetic algorithm (AGA) with variable mutation rate to optimize the parameters. Compared with traditional genetic algorithm, it can avoid premature convergence and fall into local optimization. The mutation rate of the AGA uses pseudoderivative to consider the time that GA stays at a certain point. The longer the algorithm stays at the local optimal value, the greater the possibility of mutation.Taking the mth prediction as an example, firstly, the parameters of the DESN model are chromosome encoded to correspond to the genetic operator of the AGA. The encoded chromosome of DESN model parameters is as follows:(23)P=Nl,Nr,ρ.Secondly, the fitness function is established to guide the search process of AGA. The design of fitness function affects the convergence speed and prediction accuracy of the algorithm. Generally, the fitness function is converted from the error function of DESN model. For the DESN model, the destination prediction error is naturally regarded as the fitness function. Therefore, the corresponding fitness function of the mth prediction is as follows:(24)FP=1Str×lw∑i=1Str∑j=1lwqd,im−1⋅lw+j−q∧d,im−1⋅lw+j2,whereFP represents the average prediction error of destination position when chromosome P is the DESN model parameter.Finally, according to the chromosome and fitness function established by AGADESN model, the best chromosome is selected through adaptive genetic operation. In the model, the selection operation [39] and crossover operation [40] are consistent with the traditional GA. In the mutation operation, the adaptive mutation rate based on the derivative of fitness function to generation is as follows:
(25)rm=2×sigmoidg−0.5,whererm is the adaptive mutation rate, and sigmoid function is defined as follows:
(26)sigmoidg=11+e−g,whereg is defined as follows:
(27)g=gc−go.Here,gc represents the current generation, and go represents the oldest generation with the same optimal fitness. g, thus, is inversely related to the derivative of the fitness function with respect to generation.The implementation steps of AGADESN are shown in Figure4.Figure 4
Process for implementing AGADESN algorithm.As the figure shows, the specific steps are as follows:Step 1.
Input training data, initialize DESN model parametersNl, Nr, and ρ.Step 2.
Encode the parameters of DESN model and initialize the chromosomes in the population.Step 3.
The best chromosome is selected by genetic manipulation and fitness evaluation.Step 4.
Decode the optimal chromosome to obtain the optimal parameters of the DESN model.Step 5.
Input training data and train DESN model weightWout.Step 6.
Input test data to obtain destination prediction results.


## 3.2.1. Method of Destination Prediction by DESN

Because the target trajectory is constantly updated to the destination in the process of target motion, we need to obtain multiple destination predictions at different stages of the trajectory. To this end, we design a 1-dimensional sliding window structure, as shown in Figure2. The sliding window length is lw, and each sliding length is ls. The first prediction starts when the obtained trajectory length meets the sliding window length. When the update length of track points meets the sliding length, the sliding window updates the training and test data for the second prediction. If the target trajectory update ends after the mth prediction, all destination predictions are completed on the whole trajectory.Figure 2
1-dimensional sliding window structure.The DESN structure used for each prediction is shown in Figure3. DESN combines echo state network (ESN) with deep learning idea, and adds multiple reservoir structures as hidden layers on the basis of ESN, so that DESN can map more complex time series characteristics.Figure 3
Deep echo state network structure.The working mechanism of DESN is as follows. During the mth prediction, the external data enters the input layer and enters reservoir 1 after being weighted by the input weightWin1. The state of reservoir 1 at the previous time is weighted by the weight W1 and summed with the received weighted external input. After the activation function, a new state is generated as the state x1n of reservoir 1 at the current time, and the state is used as the input of reservoir 2. After repeating the above work process, the state xLn of the last reservoir is obtained. The set of all reservoir states is recorded as xn=x1nT,x2nT,⋯xLnTT, and the output is generated by the activation function after the output layer is affected by the output weight. Among them, the maximum number of layers L is called depth, and the network requires a total of Nn=Nn,1+Nn,2+⋯+Nn,L neurons.Equations ((16)–(19)) are the mathematical model of the DESN.
(16)xinln=Winliln+Wlxln−1+bl,(17)iln=un,l=1,xl−1n,l>1,(18)xln=1−alxln−1+alflxinln,(19)yn=gWoutxn.In Equation (16), taking the reservoir l as an example, Winl and Wl represent the input weight and reservoir weight, respectively. bl represents the noise of the reservoir, and iln is the input data. xln is the updated reservoir state, and xinln is the weighted input data of the reservoir. In Equation (17), un represents the external input data. In Equation (18), al represents the leakage parameter of the reservoir l, and al∈0,1. fl⋅ represents the activation function. Generally, fl⋅ is selected as the hyperbolic tangent function. In Equation (19), yn represents the output data, and Wout is the output weight. g⋅ represents the activation function of the output layer, and gx=x is usually selected.DESN’s training and test process are as follows. The training process of the mth prediction is essentially the training of the output weight matrixWout. Firstly, the network parameters are initialized, and the random algorithm is used to generate the input weight Winl, reservoir weight Wl, and noise bl of the DESN, which remain unchanged during the training process. Secondly, if the trajectory sequence is Qm=Q1m,Q2m,⋯,QNm of N targets in the sliding window at the mth prediction, the trajectory sequence of the target i is as follows:
(20)Qim=qim−1⋅lw+1,qim−1⋅lw+2,⋯,qim⋅lw.DivideQm into training sample Qtrm and test sample Qtem. Input the training sample Q1m,Q2m,⋯,QStrm one by one, so as to obtain all reservoir state matrices X=x1,x2,⋯,xStr. Finally, calculate the training output weight Wout. If the destination prediction position output corresponding to the training sample is Y=y1,y2,⋯,yStr, the output weight of the DESN for destination prediction can be obtained according to Equation (21).
(21)Wout=YXTXXT+αE−1,whereα represents a small positive number [38], and E represents the identity matrix. Among them, the destination prediction of the target i is as follows:
(22)yi=qd,im−1⋅lw+1,qd,im−1⋅lw+2,⋯,qd,im⋅lw.qd,it represents the predicted destination position of the ith trajectory sample at time t. After the training, input the test sample Qtem to test the learning effect of the DESN, which can output the destination prediction according to Equation (19) under the trained output weight Wout.


## 3.2.2. Optimization of DESN Parameters by Adaptive Genetic Algorithm

DESN has reliable time series prediction ability. However, like other deep learning algorithms, its prediction effect is limited by the selection of parameters. The parameters that have the greatest impact on the effect of the algorithm include the number of reservoirsNl, the number of reservoir nodes Nr, and the spectral radius ρ. ρ is one of the most important central parameters representing the reservoir weight matrix.In order to solve the problem of choosing DESN parameters, we use an adaptive genetic algorithm (AGA) with variable mutation rate to optimize the parameters. Compared with traditional genetic algorithm, it can avoid premature convergence and fall into local optimization. The mutation rate of the AGA uses pseudoderivative to consider the time that GA stays at a certain point. The longer the algorithm stays at the local optimal value, the greater the possibility of mutation.Taking the mth prediction as an example, firstly, the parameters of the DESN model are chromosome encoded to correspond to the genetic operator of the AGA. The encoded chromosome of DESN model parameters is as follows:(23)P=Nl,Nr,ρ.Secondly, the fitness function is established to guide the search process of AGA. The design of fitness function affects the convergence speed and prediction accuracy of the algorithm. Generally, the fitness function is converted from the error function of DESN model. For the DESN model, the destination prediction error is naturally regarded as the fitness function. Therefore, the corresponding fitness function of the mth prediction is as follows:(24)FP=1Str×lw∑i=1Str∑j=1lwqd,im−1⋅lw+j−q∧d,im−1⋅lw+j2,whereFP represents the average prediction error of destination position when chromosome P is the DESN model parameter.Finally, according to the chromosome and fitness function established by AGADESN model, the best chromosome is selected through adaptive genetic operation. In the model, the selection operation [39] and crossover operation [40] are consistent with the traditional GA. In the mutation operation, the adaptive mutation rate based on the derivative of fitness function to generation is as follows:
(25)rm=2×sigmoidg−0.5,whererm is the adaptive mutation rate, and sigmoid function is defined as follows:
(26)sigmoidg=11+e−g,whereg is defined as follows:
(27)g=gc−go.Here,gc represents the current generation, and go represents the oldest generation with the same optimal fitness. g, thus, is inversely related to the derivative of the fitness function with respect to generation.The implementation steps of AGADESN are shown in Figure4.Figure 4
Process for implementing AGADESN algorithm.As the figure shows, the specific steps are as follows:Step 1.
Input training data, initialize DESN model parametersNl, Nr, and ρ.Step 2.
Encode the parameters of DESN model and initialize the chromosomes in the population.Step 3.
The best chromosome is selected by genetic manipulation and fitness evaluation.Step 4.
Decode the optimal chromosome to obtain the optimal parameters of the DESN model.Step 5.
Input training data and train DESN model weightWout.Step 6.
Input test data to obtain destination prediction results.


## 3.3. Cluster Identification Based on DBSCAN

### 3.3.1. Definition of Motion Similarity Distance

According to the cluster collaborative motion model, in the process of moving towards the destination, the members of the same cluster are close to each other and have similar speed vectors, which are the basis for us to cluster the target to identify the cluster. However, a fact that may be ignored is that the same cluster members also have similar destination position predictions, which provide additional information for us to identify clusters.In 2-dimensional case, the motion state vector of targeti at time t is St,it=qi,xt,pi,xt,qi,yt,pi,ytT, and the prediction value of destination is qd,it=qd,i,xt,qd,i,ytT. Due to the sliding window structure, there may be more than one predicted value of the track point at time t, so qd,it is the mean value of all predicted values, as shown in Equation (28).
(28)qd,it=1Z∑j=1Zqd,ijt,whereZ is the number of destination position predicted values at the track point at time t. qd,ijt represents the jth predicted value.We define a new distance measure, which is called motion similarity distance (MSD). The MSD between memberi and member j is shown in Equation (29).
(29)fSt,it,qd,it,St,jt,qd,jt=1−e−w1Rv2/2σRv2+w2Rd2/2σRd2+w3Rp2/2σRp2.Among them,Rv, Rd, and Rp are the speed distance, position distance, and predicted destination distance, respectively. The weight wi≥0i=1,2,3 represents the importance of different distances, and ∑iwi=1. σRv, σRd, and σRp are the standard deviation of the corresponding distance. The distances are calculated as follows:
(30)Rv=pi,xt−pj,xt2+pi,yt−pi,yt21/2,Rd=max0,qi,xt−qj,xt2+qi,yt−qj,yt21/2−De1,Rp=max0,qd,i,xt−qd,j,xt2+qd,i,yt−qd,j,yt21/2−De2,whereDe1 describes the expected distance of members. De2 describes the extended range of destinations.


### 3.3.2. Principle of DBSCAN Cluster Identification

DBSCAN is an effective density-based clustering algorithm, which can describe the density of data distribution, and then identify clusters of arbitrary shape and effectively distinguish noise points. DBSCAN algorithm sets a field with a radius ofEps around each target data point. If the number of other target data points in a target field reaches the set threshold MinPts, it is considered that the target belongs to the cluster and is the core point. If there are no other target data points in the neighborhood of a target, the target is considered to be a noise point. If there are target data points in the target field, but the number of data points does not meet MinPts, it is considered that the target is a boundary point. Figure 5 shows the schematic diagram of the DBSCAN algorithm.Figure 5
Schematic diagram of the DBSCAN algorithm.As shown in Figure5, the radius of the circle is the clustering radius Eps and set MinPts=2. It can be seen from the figure that the number of data points in the neighborhood of targets (2, 3, 4, 5, and 6) is greater than MinPts,so they are core points. There are only points 2 in the neighborhood of data point 1, so point 1 is a boundary point. There are no other targets in the neighborhood of data point 7, so it is a noise point. We can obtain that (1, 2, 3, 4, 5, and 6) belong to the same cluster. The DBSCAN algorithm flow is as follows:Algorithm 1:DBSCAN algorithm flow.
Input: Uncertain data setD, Clustering radius Eps, Minimal number of neighboring points MinPtsOutput: A set of clusters, types of all the points inDMain function of the algorithm:DBSCAN(D, Eps, MinPts)ClusterNum=0for each target point P in DifP is visitedcontinue to next pointend ifmarkP as visitedEps-Neighborhood=regionQuery(P, Eps)if sizeof(Eps-Neighborhood)<MinPtsmarkP as noiseelseClusterNum=next clusterexpandCluster(P, Eps-Neighborhood, ClusterNum, Eps, MinPts)end ifend forENDregionQuery(P, Eps)returnEps-Neighborhood(P)={Q∈S|D(P,Q)≤Eps}expandCluster(P, Eps-Neighborhood, ClusterNum, Eps, MinPts)addP to cluster ClusterNumfor each point P′ in Eps-NeighborhoodifP′ is not visitedmarkP′ as visitedEps−Neighborhood′ =regionQuery(P′, Eps)if sizeof(Eps−Neighborhood′)>=MinPtsEps-Neighborhood=Eps-Neighborhood joined with Eps−Neighborhood′end ifend ififP′ is not yet member of any clusteraddP′ to cluster ClusterNumend ifend for


## 3.3.1. Definition of Motion Similarity Distance

According to the cluster collaborative motion model, in the process of moving towards the destination, the members of the same cluster are close to each other and have similar speed vectors, which are the basis for us to cluster the target to identify the cluster. However, a fact that may be ignored is that the same cluster members also have similar destination position predictions, which provide additional information for us to identify clusters.In 2-dimensional case, the motion state vector of targeti at time t is St,it=qi,xt,pi,xt,qi,yt,pi,ytT, and the prediction value of destination is qd,it=qd,i,xt,qd,i,ytT. Due to the sliding window structure, there may be more than one predicted value of the track point at time t, so qd,it is the mean value of all predicted values, as shown in Equation (28).
(28)qd,it=1Z∑j=1Zqd,ijt,whereZ is the number of destination position predicted values at the track point at time t. qd,ijt represents the jth predicted value.We define a new distance measure, which is called motion similarity distance (MSD). The MSD between memberi and member j is shown in Equation (29).
(29)fSt,it,qd,it,St,jt,qd,jt=1−e−w1Rv2/2σRv2+w2Rd2/2σRd2+w3Rp2/2σRp2.Among them,Rv, Rd, and Rp are the speed distance, position distance, and predicted destination distance, respectively. The weight wi≥0i=1,2,3 represents the importance of different distances, and ∑iwi=1. σRv, σRd, and σRp are the standard deviation of the corresponding distance. The distances are calculated as follows:
(30)Rv=pi,xt−pj,xt2+pi,yt−pi,yt21/2,Rd=max0,qi,xt−qj,xt2+qi,yt−qj,yt21/2−De1,Rp=max0,qd,i,xt−qd,j,xt2+qd,i,yt−qd,j,yt21/2−De2,whereDe1 describes the expected distance of members. De2 describes the extended range of destinations.


## 3.3.2. Principle of DBSCAN Cluster Identification

DBSCAN is an effective density-based clustering algorithm, which can describe the density of data distribution, and then identify clusters of arbitrary shape and effectively distinguish noise points. DBSCAN algorithm sets a field with a radius ofEps around each target data point. If the number of other target data points in a target field reaches the set threshold MinPts, it is considered that the target belongs to the cluster and is the core point. If there are no other target data points in the neighborhood of a target, the target is considered to be a noise point. If there are target data points in the target field, but the number of data points does not meet MinPts, it is considered that the target is a boundary point. Figure 5 shows the schematic diagram of the DBSCAN algorithm.Figure 5
Schematic diagram of the DBSCAN algorithm.As shown in Figure5, the radius of the circle is the clustering radius Eps and set MinPts=2. It can be seen from the figure that the number of data points in the neighborhood of targets (2, 3, 4, 5, and 6) is greater than MinPts,so they are core points. There are only points 2 in the neighborhood of data point 1, so point 1 is a boundary point. There are no other targets in the neighborhood of data point 7, so it is a noise point. We can obtain that (1, 2, 3, 4, 5, and 6) belong to the same cluster. The DBSCAN algorithm flow is as follows:Algorithm 1:DBSCAN algorithm flow.
Input: Uncertain data setD, Clustering radius Eps, Minimal number of neighboring points MinPtsOutput: A set of clusters, types of all the points inDMain function of the algorithm:DBSCAN(D, Eps, MinPts)ClusterNum=0for each target point P in DifP is visitedcontinue to next pointend ifmarkP as visitedEps-Neighborhood=regionQuery(P, Eps)if sizeof(Eps-Neighborhood)<MinPtsmarkP as noiseelseClusterNum=next clusterexpandCluster(P, Eps-Neighborhood, ClusterNum, Eps, MinPts)end ifend forENDregionQuery(P, Eps)returnEps-Neighborhood(P)={Q∈S|D(P,Q)≤Eps}expandCluster(P, Eps-Neighborhood, ClusterNum, Eps, MinPts)addP to cluster ClusterNumfor each point P′ in Eps-NeighborhoodifP′ is not visitedmarkP′ as visitedEps−Neighborhood′ =regionQuery(P′, Eps)if sizeof(Eps−Neighborhood′)>=MinPtsEps-Neighborhood=Eps-Neighborhood joined with Eps−Neighborhood′end ifend ififP′ is not yet member of any clusteraddP′ to cluster ClusterNumend ifend for


## 4. Experiments and Results

### 4.1. Generate Datasets

In order to verify the effectiveness of the algorithm proposed in this paper, we generate a cluster cooperative motion simulation dataset based on the improved Olfati-Saber model. This algorithm uses the combination of AGADESN and DBSCAN algorithms to identify the motion intention of cluster targets. The total number of targets in the field of view isN=15.Targets are released in the range of 0,20×0,20m2, and the initial speed in both x and y directions is 0 m/s. The number of clusters is random, but there are at least 3 targets in a cluster, that is, the number of clusters in the field of view is Nc≤5. Total movement time Tt=100s, and sampling interval τ=0.1s. 5 destinations are set to form a destination set, and the position of each destination is shown in Table 1.Table 1
Destination position.
DestinationPosition (x, y)/mD1(1400, 2040)D2(1960, 2500)D3(2560, 3360)D4(2880, 2940)D5(3440, 2680)In the simulation, the destination of the cluster motion is randomly determined and can be changed during the cluster motion, but in order to ensure the stability of the trajectory, the destination can be changed again only after the destination is determined for the first time or changed for at least 25 s.Set the Olfati-Saber model parametersa=1 and b=5, then the corresponding c=25/5. Set parameter ε=0.85, select d=15 and r=95, then the corresponding dα=15.1 and rα=101.9. Only consider the speed collaboration with the virtual leader, and set the parameters h=0.2, c1=0, and c2=0.2. Set the noise variance control coefficient δ=5×10−4.Under the above simulation conditions, 100 cluster motion scenes are generated, and a total of 1500 tracks are obtained; 80% of which are used for training and 20% for test. The generated dataset is shown in Figure6.Figure 6
Cluster motion dataset.A cluster movement scene is taken out from the training set, as shown in Figure7, and the cluster motion speed is shown in Figure 8.Figure 7
A cluster motion scenario.Figure 8
Cluster motion speed of the above scenario.As can be seen from Figures7 and 8, the motion of each target is chaotic at the initial stage of release. With the mutual cooperation of the targets in the same cluster, the speed of the targets in the same cluster gradually tends to be the same, and three different clusters are gradually formed. Around 33 s, the cluster moving towards destination D1 splits and gradually forms cluster C2 and C3. After C2 changes the destination and moves for a period of time, it changes the destination to D1 again and arrives. C3 finally arrives at D3. At about 66 s, the clusters moving towards destination D4 splits and gradually forms cluster C4 and C5. C4 and C5 finally arrive at D4 and D5, respectively. In the late stage of target motion, the speed of each target in the same cluster tends to be consistent, and the trajectory is gradually parallel, and the cluster forms a stable structure. It can also be found from Figure 8 that due to the time-varying variance of the direction noise, the mean value of the noise at the initial time is large, and the trajectory has great instability. As the target approaches the destination, the mean value of the noise approaches 0, and the cluster speed is smoother.


### 4.2. Destination Prediction Results

In order to verify the superiority of the proposed algorithm, we use the algorithm in this paper, the DESN algorithm optimized by genetic algorithm (GADESN) and the DESN algorithm to predict the destination of cluster targets, respectively. Set the sliding window lengthlw=100, and each sliding length lw=20, then M=46 times of destination prediction is required to make the sliding window traverse the whole trajectory. The calculation method of M is as follows:
(31)M=1+Tt/τ−lwls.The root mean square error (RMSE) is used to evaluate the prediction performance of the AGADESN model, which is defined as follows:(32)RMSEt=1Z∑i=1Zqd,iit−q∧d,it2.Under the above sliding window setting,Z∈1,2,3,4,5.Set reservoir leakage parametersal=0.9. The number of reservoirs Nl, the number of neurons Nr in each reservoir, and the spectral radius ρ are given by AGA in AGADESN algorithm and by GA in GADESN algorithm. In the DESN algorithm, we set Nl=5, Nr=200, and ρ=0.8. Taking the 46th prediction as an example, the iteration trajectory of the AGA and the GA are shown in the following figure.It can be seen from Figure9 that the fitness value of the adaptive genetic algorithm has converged when iterating to generation 46, with a fitness value of 42.6, and the genetic algorithm has converged when iterating to generation 74, with a fitness value of 48.3. Adaptive genetic algorithm has faster convergence speed and better fitness value, so AGADESN model has faster iteration speed and better prediction accuracy.Figure 9
Adaptive genetic algorithm and genetic algorithm fitness value iteration trajectory.The destination position prediction RMSE of the cluster in Figure7 is shown in the following figure.It can be seen from Figure10 that as the cluster approaches the destination, although the destination position prediction RMSE of AGADESN algorithm fluctuates, on the whole, RMSE tends to decrease gradually. The RMSE of all clusters can be reduced to less than 100 m before the end of the motion. Since there is no destination change in C4, the algorithm can determine the destination very early and maintain RMSE at a low level. When the destination of C2 changes again in the late stage of motion, the algorithm can also quickly catch the new destination, and the RMSE gradually decreases.Figure 10
Destination position prediction RMSE of the cluster in Figure7.In the figure, the circle with the destination as the center and 300 m as the radius can distinguish different destinations in the destination set, which is called the destination range. Generally, if the destination set is known, we do not need to get the accurate destination prediction position of the target, but only need to specify which destination range the predicted value is in to determine the destination. If the mean value of all the destination position predicted values on a certain trajectory point is within the range of the real destination, we call the prediction on this trajectory point the correct prediction. Under the above definition, the condition for correct prediction in this experiment is that the mean absolute error (MAE) of all predicted values at a certain trajectory point is no more than 300 m. The MAE(t) is defined as follows:
(33)MAEt=1Z∑i=1Zqd,iit−q^d,it.Figure11 gives the average RMSE of destination position prediction for all cluster in the test set by the AGADESN, GADESN, and DESN algorithms.Figure 11
Average RMSE of destination position prediction for all cluster in the test set.RMSE is computed differently from MAE and according to holder inequality, there always holdsRMSEt≥MAEt. Therefore, the RMSE threshold for correct prediction is always not less than the destination range. But without knowing how optimistic the predicted value is, we take the RMSE threshold of the correct prediction to be its lower bound 300 m, as indicated by the red dotted line in the figure.Figure11 shows that in the initial stage, before the target destination changes, all 3 algorithms can predict the approximate position of the destination. Comparatively, AGADESN algorithm achieves the correct prediction at 12 s, which is 8 s earlier than GADESN algorithm. Some of the targets change their destinations around 30 s and 50 s; the RMSE of 3 algorithms increases, and after recognizing the new destinations, the RMSE returns to a lower level. After a second destination change maneuver of targets occurs, the AGADESN algorithm achieves more stably correct predictions in 55 s, whereas the GADESN and DESN algorithms need 70 s. The AGADESN algorithm has a better effect, both in terms of prediction accuracy and in the time to achieve the correct prediction.In the whole process of target motion, the correct prediction proportion of destinations of all clusters in the test set is shown in Figure12.Figure 12
Proportion of correct predictions.In Figure12, we plot the proportion of correct predictions of destinations for the test set clusters at 5 s intervals. It is known from the figure that the AGADESN algorithm can correctly predict about 40% of the cases when no destination change occurs. When the destination of the cluster motion is changed, the proportion of correct predictions decreases for 3 algorithms. However, the proportion of correct predictions improves faster for the AGADESN algorithm after 55 s. Throughout the trajectory, the proportion of correct predictions by the AGADESN algorithm proposed in this paper is generally higher than that by the other comparison algorithms, increasing by 8.39% the proportion of correct predictions by the DESN algorithm.


### 4.3. Cluster Identification Results

To demonstrate the effectiveness of DBSCAN algorithm based on the motion similarity distance proposed in this paper for cluster identification, we set the distance parametersσRv=0.7, σRd=100, σRp=600, De1=15, and De2=300 after obtaining the destination position predictions. Solving for the Rv, Rd, and Rp distances for each moment of target 1 and target 7 belonging to different clusters are shown in Figure 13. Among them, target 1 belongs to C3; initial destination is D1, and final destination is D3 after 33 s. Target 7 belongs to C4; initial destination is D5, and final destination is D4 after 32 s.Figure 13
Rv, Rd and Rp distances of the two targets at each moment.It is known from Figure13 that the initial moment, because the target release point is concentrated, the two targets are relatively close together, and the speed difference is not great, so that the Rv and Rd of the two targets are both smaller in the motion early stage. But because the predicted destinations of the two targets are quite different, the Rp distance difference is obvious in the motion early stage. In the motion late stage, after the two targets turning, the Rp distance starts to decrease due to the closer distances between the D3 and D4. But Rv and Rd distances increase. Thus, the MSD defined in this paper, which fuses the Rv, Rd, and Rp distances, can effectively compensate for the main time of action of the three distances, such that targets belonging to different clusters have large distances consistently throughout the motion.Set DBSCAN algorithm parametersEps=0.3; MinPts=2, and w1=w2=w3=0.33. Clusters are identified throughout using the DBSCAN algorithm based on the MSD, and Figure 14 shows the cluster identification results for t=2,4,6,8s in the motion early stage; t=62,64,66,68s in the splitting stage, and t=94,96,98,100s in the motion late stage.Figure 14
Cluster identification results at specific time.In the early stage of cluster motion, the release area of cluster is small, and the target belonging to the same cluster has not completed speed collaboration. Because the MSD integrates position, speed, and predicted destination distances, the result of cluster identification has crossover in the position plane. Whent=8s, different clusters begin to differentiate in the field of view of the sensor. When cluster splits, different cluster positions are far away from each other, so the algorithm in this paper can easily distinguish different clusters and effectively identify the newly born clusters. In the late stage of cluster motion, the algorithm can maintain the accuracy of cluster identification, but when clusters C1 and C2 arrive at D1 at the same time, the algorithm identifies C1 and C2 as the same cluster. This is because the speed distance when the cluster arrives at the destination plays a major role in distinguishing clusters, and the contribution of the speed distance to the MSD decreases when the predicted destination distance is introduced, which has an impact on the identification result. But on the other hand, if two clusters arrive at the same destination at the same time, whether the two clusters merge or not would not affect our further decision.Figure15 shows the comparison of cluster identification results by DBSCAN algorithm based on the proposed MSD and based on only position and speed fusion distance (PSD), where the DBSCAN algorithm based on the PSD is set to w1=w2=0.5,w3=0.Figure 15
Comparison of cluster identification results based on the MSD and the PSD.As can be seen from Figure15, at the initial stage of cluster motion, due to the small distance difference between targets, the identification results of DBSCAN algorithm are often inaccurate. When the target is splitting, the identification result lags behind the time of splitting and fluctuates. By comparison, DBSCAN algorithm based on the MSD has higher identification accuracy and stability than that only considering position and speed distance. Especially in the initial stage of cluster motion, the introduction of the predicted destination distance significantly makes up for the deficiency of only considering position and speed distance.


### 4.4. Discussion

#### 4.4.1. Selection of Eps

The selection ofEps has an impact on DBSCAN algorithm. In order to evaluate the significance of Eps influence, we increase Eps from 0.01 to 1 with the step size of 0.01, and set appropriate distance parameters for all cluster scenarios in the test set to conduct cluster identification experiments. The correct identification probability of cluster number is shown in Figure 16.Figure 16
Correct identification probability under differentEps.As can be seen from Figure16, although Eps can be set arbitrarily within [0.01, 1), the DBSCAN algorithm can obtain a good correct identification probability under any Eps. However, with the increase of Eps, the probability still shows a process of first increasing and then decreasing. When Eps is set in (0.3, 0.4), the correct identification probability is the highest. The analysis shows that Eps setting value is related to a variety of factors and is most closely related to the distance between clusters during the whole motion of clusters. When clusters are close to each other, if Eps is set too small, members in the same cluster may be considered as belonging to different clusters, resulting in a large number of identified clusters. On the contrary, if Eps is set too large, the number of identified clusters may be less. Therefore, for the whole process of cluster motion, the adaptive setting of Eps can achieve the best cluster identification effect.


#### 4.4.2. Algorithm Runtime Evaluation

To evaluate the feasibility of the algorithm on large-scale data sets, Figures17 and 18 show the running time of each intention recognition of the algorithm in the experiment.Figure 17
Training time of AGADESN algorithm.Figure 18
Average time of intention recognition under single test scenario.Figure17 shows the training time of AGADESN algorithm for each destination prediction. It can be seen from Figure 17 that the average training time for each prediction of AGADESN algorithm is 607 s, of which the iteration time for adaptive genetic algorithm is 83 s, and the time for DESN training is 524 s. It can be seen that because the adaptive genetic algorithm embeds the DESN training process, the algorithm needs to calculate the DESN training error in each iteration, so the DESN training time accounts for the main part of the AGADESN algorithm training time. This also leads to the long training time of the algorithm. The adaptive genetic algorithm proposed in the paper uses adaptive mutation rate, and its genetic operation iteration time is short. Comparing the training time of each destination prediction, it can be seen that when the target is maneuvering, the time required for algorithm training increases because the destination position is unknown after maneuvering. When the target approaches the destination, the cluster moves straight toward the destination with less noise, and the algorithm training time is reduced.Figure18 shows the average recognition time of our algorithm for the cluster intention in a single test scenario. The average time of intention recognition of the trained network in a single scene is 0.1221s, including 0.0988 s for destination prediction and 0.0233 s for cluster identification. It can be seen from Figure 18 that the algorithm has a fast intention recognition speed for 15 targets in a single test scenario, and the destination prediction time accounts for the main part of the algorithm’s running time. Because DBSCAN algorithm has no deep structure, it has higher efficiency. Its clustering identification speed is fast and can meet the real-time requirements.From the above analysis, it can be seen that the trained network can quickly identify the cluster motion intention, which makes the algorithm applicable to the prediction of large-scale cluster motion intention. However, because AGADESN algorithm directly uses the training error of DESN as the fitness evaluation function in the training process, it takes a long time for a single iteration of AGADESN, which makes the algorithm unable to meet the requirements of online real-time training, which limits the training speed of the algorithm in large-scale data sets.


#### 4.4.3. Exploration of Further Improving the Accuracy of Intention Recognition

In this paper, in order to accurately simulate more the cluster motion, we introduce the motion direction noise with time-varying variance on the basis of the basic Olfati-Saber model. However, the cluster motion trajectory noise makes the relationship between the motion characteristics and the destination more unclear, which has a negative impact on the prediction of the cluster motion destination. In order to alleviate the interference of noise and extract more motion features related to the destination, we try to decompose the cluster motion trajectory signal by using the variational mode decomposition (VMD) algorithm [41]. Due to the independence of different modality data, it is possible to further improve the accuracy of destination prediction by inputting different modality data into the circular convolution attention network to fuse different features for destination prediction [42].We define the motion similarity distance and introduce the destination prediction distance into the position speed distance to judge whether multiple targets belong to the same cluster, which achieves better cluster recognition effect. However, when the cluster splits, the effect of DBSCAN algorithm in identifying clusters fluctuates and lags, which brings challenges to the real-time performance of the algorithm. During the experiment, we realize that the improvement of the clustering identification effect is essentially due to the introduction of additional information (destination information). Therefore, in order to improve the real-time performance of the cluster recognition algorithm, further information mining of the cluster motion trajectory is needed.In terms of hardware, we can use infrared, photoelectric and other sensors to obtain the multidimensional information of the target, but we must propose better feature selection and fusion algorithms. Chen et al. [43] proposed two deep learning frameworks to explore and preserve the temporal and spatial information of EEG signals in a cascade or parallel manner and achieved good results in human intention recognition, which is enlightening to us. The basis of cluster identification is that targets with similar features should have a greater probability of being neighbours. We can use more complex convolutional neural networks to explore the local structure of clusters and integrate it into the selection of joint features [44]. Secondly, the cluster identification should be carried out in a more adaptive way, using an adaptive loss function to enhance the robustness to system noise, which may be caused by wrong destination prediction or by abnormal parameter values of DBSCAN algorithm.


## 4.1. Generate Datasets

In order to verify the effectiveness of the algorithm proposed in this paper, we generate a cluster cooperative motion simulation dataset based on the improved Olfati-Saber model. This algorithm uses the combination of AGADESN and DBSCAN algorithms to identify the motion intention of cluster targets. The total number of targets in the field of view isN=15.Targets are released in the range of 0,20×0,20m2, and the initial speed in both x and y directions is 0 m/s. The number of clusters is random, but there are at least 3 targets in a cluster, that is, the number of clusters in the field of view is Nc≤5. Total movement time Tt=100s, and sampling interval τ=0.1s. 5 destinations are set to form a destination set, and the position of each destination is shown in Table 1.Table 1
Destination position.
DestinationPosition (x, y)/mD1(1400, 2040)D2(1960, 2500)D3(2560, 3360)D4(2880, 2940)D5(3440, 2680)In the simulation, the destination of the cluster motion is randomly determined and can be changed during the cluster motion, but in order to ensure the stability of the trajectory, the destination can be changed again only after the destination is determined for the first time or changed for at least 25 s.Set the Olfati-Saber model parametersa=1 and b=5, then the corresponding c=25/5. Set parameter ε=0.85, select d=15 and r=95, then the corresponding dα=15.1 and rα=101.9. Only consider the speed collaboration with the virtual leader, and set the parameters h=0.2, c1=0, and c2=0.2. Set the noise variance control coefficient δ=5×10−4.Under the above simulation conditions, 100 cluster motion scenes are generated, and a total of 1500 tracks are obtained; 80% of which are used for training and 20% for test. The generated dataset is shown in Figure6.Figure 6
Cluster motion dataset.A cluster movement scene is taken out from the training set, as shown in Figure7, and the cluster motion speed is shown in Figure 8.Figure 7
A cluster motion scenario.Figure 8
Cluster motion speed of the above scenario.As can be seen from Figures7 and 8, the motion of each target is chaotic at the initial stage of release. With the mutual cooperation of the targets in the same cluster, the speed of the targets in the same cluster gradually tends to be the same, and three different clusters are gradually formed. Around 33 s, the cluster moving towards destination D1 splits and gradually forms cluster C2 and C3. After C2 changes the destination and moves for a period of time, it changes the destination to D1 again and arrives. C3 finally arrives at D3. At about 66 s, the clusters moving towards destination D4 splits and gradually forms cluster C4 and C5. C4 and C5 finally arrive at D4 and D5, respectively. In the late stage of target motion, the speed of each target in the same cluster tends to be consistent, and the trajectory is gradually parallel, and the cluster forms a stable structure. It can also be found from Figure 8 that due to the time-varying variance of the direction noise, the mean value of the noise at the initial time is large, and the trajectory has great instability. As the target approaches the destination, the mean value of the noise approaches 0, and the cluster speed is smoother.


## 4.2. Destination Prediction Results

In order to verify the superiority of the proposed algorithm, we use the algorithm in this paper, the DESN algorithm optimized by genetic algorithm (GADESN) and the DESN algorithm to predict the destination of cluster targets, respectively. Set the sliding window lengthlw=100, and each sliding length lw=20, then M=46 times of destination prediction is required to make the sliding window traverse the whole trajectory. The calculation method of M is as follows:
(31)M=1+Tt/τ−lwls.The root mean square error (RMSE) is used to evaluate the prediction performance of the AGADESN model, which is defined as follows:(32)RMSEt=1Z∑i=1Zqd,iit−q∧d,it2.Under the above sliding window setting,Z∈1,2,3,4,5.Set reservoir leakage parametersal=0.9. The number of reservoirs Nl, the number of neurons Nr in each reservoir, and the spectral radius ρ are given by AGA in AGADESN algorithm and by GA in GADESN algorithm. In the DESN algorithm, we set Nl=5, Nr=200, and ρ=0.8. Taking the 46th prediction as an example, the iteration trajectory of the AGA and the GA are shown in the following figure.It can be seen from Figure9 that the fitness value of the adaptive genetic algorithm has converged when iterating to generation 46, with a fitness value of 42.6, and the genetic algorithm has converged when iterating to generation 74, with a fitness value of 48.3. Adaptive genetic algorithm has faster convergence speed and better fitness value, so AGADESN model has faster iteration speed and better prediction accuracy.Figure 9
Adaptive genetic algorithm and genetic algorithm fitness value iteration trajectory.The destination position prediction RMSE of the cluster in Figure7 is shown in the following figure.It can be seen from Figure10 that as the cluster approaches the destination, although the destination position prediction RMSE of AGADESN algorithm fluctuates, on the whole, RMSE tends to decrease gradually. The RMSE of all clusters can be reduced to less than 100 m before the end of the motion. Since there is no destination change in C4, the algorithm can determine the destination very early and maintain RMSE at a low level. When the destination of C2 changes again in the late stage of motion, the algorithm can also quickly catch the new destination, and the RMSE gradually decreases.Figure 10
Destination position prediction RMSE of the cluster in Figure7.In the figure, the circle with the destination as the center and 300 m as the radius can distinguish different destinations in the destination set, which is called the destination range. Generally, if the destination set is known, we do not need to get the accurate destination prediction position of the target, but only need to specify which destination range the predicted value is in to determine the destination. If the mean value of all the destination position predicted values on a certain trajectory point is within the range of the real destination, we call the prediction on this trajectory point the correct prediction. Under the above definition, the condition for correct prediction in this experiment is that the mean absolute error (MAE) of all predicted values at a certain trajectory point is no more than 300 m. The MAE(t) is defined as follows:
(33)MAEt=1Z∑i=1Zqd,iit−q^d,it.Figure11 gives the average RMSE of destination position prediction for all cluster in the test set by the AGADESN, GADESN, and DESN algorithms.Figure 11
Average RMSE of destination position prediction for all cluster in the test set.RMSE is computed differently from MAE and according to holder inequality, there always holdsRMSEt≥MAEt. Therefore, the RMSE threshold for correct prediction is always not less than the destination range. But without knowing how optimistic the predicted value is, we take the RMSE threshold of the correct prediction to be its lower bound 300 m, as indicated by the red dotted line in the figure.Figure11 shows that in the initial stage, before the target destination changes, all 3 algorithms can predict the approximate position of the destination. Comparatively, AGADESN algorithm achieves the correct prediction at 12 s, which is 8 s earlier than GADESN algorithm. Some of the targets change their destinations around 30 s and 50 s; the RMSE of 3 algorithms increases, and after recognizing the new destinations, the RMSE returns to a lower level. After a second destination change maneuver of targets occurs, the AGADESN algorithm achieves more stably correct predictions in 55 s, whereas the GADESN and DESN algorithms need 70 s. The AGADESN algorithm has a better effect, both in terms of prediction accuracy and in the time to achieve the correct prediction.In the whole process of target motion, the correct prediction proportion of destinations of all clusters in the test set is shown in Figure12.Figure 12
Proportion of correct predictions.In Figure12, we plot the proportion of correct predictions of destinations for the test set clusters at 5 s intervals. It is known from the figure that the AGADESN algorithm can correctly predict about 40% of the cases when no destination change occurs. When the destination of the cluster motion is changed, the proportion of correct predictions decreases for 3 algorithms. However, the proportion of correct predictions improves faster for the AGADESN algorithm after 55 s. Throughout the trajectory, the proportion of correct predictions by the AGADESN algorithm proposed in this paper is generally higher than that by the other comparison algorithms, increasing by 8.39% the proportion of correct predictions by the DESN algorithm.


## 4.3. Cluster Identification Results

To demonstrate the effectiveness of DBSCAN algorithm based on the motion similarity distance proposed in this paper for cluster identification, we set the distance parametersσRv=0.7, σRd=100, σRp=600, De1=15, and De2=300 after obtaining the destination position predictions. Solving for the Rv, Rd, and Rp distances for each moment of target 1 and target 7 belonging to different clusters are shown in Figure 13. Among them, target 1 belongs to C3; initial destination is D1, and final destination is D3 after 33 s. Target 7 belongs to C4; initial destination is D5, and final destination is D4 after 32 s.Figure 13
Rv, Rd and Rp distances of the two targets at each moment.It is known from Figure13 that the initial moment, because the target release point is concentrated, the two targets are relatively close together, and the speed difference is not great, so that the Rv and Rd of the two targets are both smaller in the motion early stage. But because the predicted destinations of the two targets are quite different, the Rp distance difference is obvious in the motion early stage. In the motion late stage, after the two targets turning, the Rp distance starts to decrease due to the closer distances between the D3 and D4. But Rv and Rd distances increase. Thus, the MSD defined in this paper, which fuses the Rv, Rd, and Rp distances, can effectively compensate for the main time of action of the three distances, such that targets belonging to different clusters have large distances consistently throughout the motion.Set DBSCAN algorithm parametersEps=0.3; MinPts=2, and w1=w2=w3=0.33. Clusters are identified throughout using the DBSCAN algorithm based on the MSD, and Figure 14 shows the cluster identification results for t=2,4,6,8s in the motion early stage; t=62,64,66,68s in the splitting stage, and t=94,96,98,100s in the motion late stage.Figure 14
Cluster identification results at specific time.In the early stage of cluster motion, the release area of cluster is small, and the target belonging to the same cluster has not completed speed collaboration. Because the MSD integrates position, speed, and predicted destination distances, the result of cluster identification has crossover in the position plane. Whent=8s, different clusters begin to differentiate in the field of view of the sensor. When cluster splits, different cluster positions are far away from each other, so the algorithm in this paper can easily distinguish different clusters and effectively identify the newly born clusters. In the late stage of cluster motion, the algorithm can maintain the accuracy of cluster identification, but when clusters C1 and C2 arrive at D1 at the same time, the algorithm identifies C1 and C2 as the same cluster. This is because the speed distance when the cluster arrives at the destination plays a major role in distinguishing clusters, and the contribution of the speed distance to the MSD decreases when the predicted destination distance is introduced, which has an impact on the identification result. But on the other hand, if two clusters arrive at the same destination at the same time, whether the two clusters merge or not would not affect our further decision.Figure15 shows the comparison of cluster identification results by DBSCAN algorithm based on the proposed MSD and based on only position and speed fusion distance (PSD), where the DBSCAN algorithm based on the PSD is set to w1=w2=0.5,w3=0.Figure 15
Comparison of cluster identification results based on the MSD and the PSD.As can be seen from Figure15, at the initial stage of cluster motion, due to the small distance difference between targets, the identification results of DBSCAN algorithm are often inaccurate. When the target is splitting, the identification result lags behind the time of splitting and fluctuates. By comparison, DBSCAN algorithm based on the MSD has higher identification accuracy and stability than that only considering position and speed distance. Especially in the initial stage of cluster motion, the introduction of the predicted destination distance significantly makes up for the deficiency of only considering position and speed distance.


## 4.4. Discussion

### 4.4.1. Selection of Eps

The selection ofEps has an impact on DBSCAN algorithm. In order to evaluate the significance of Eps influence, we increase Eps from 0.01 to 1 with the step size of 0.01, and set appropriate distance parameters for all cluster scenarios in the test set to conduct cluster identification experiments. The correct identification probability of cluster number is shown in Figure 16.Figure 16
Correct identification probability under differentEps.As can be seen from Figure16, although Eps can be set arbitrarily within [0.01, 1), the DBSCAN algorithm can obtain a good correct identification probability under any Eps. However, with the increase of Eps, the probability still shows a process of first increasing and then decreasing. When Eps is set in (0.3, 0.4), the correct identification probability is the highest. The analysis shows that Eps setting value is related to a variety of factors and is most closely related to the distance between clusters during the whole motion of clusters. When clusters are close to each other, if Eps is set too small, members in the same cluster may be considered as belonging to different clusters, resulting in a large number of identified clusters. On the contrary, if Eps is set too large, the number of identified clusters may be less. Therefore, for the whole process of cluster motion, the adaptive setting of Eps can achieve the best cluster identification effect.


### 4.4.2. Algorithm Runtime Evaluation

To evaluate the feasibility of the algorithm on large-scale data sets, Figures17 and 18 show the running time of each intention recognition of the algorithm in the experiment.Figure 17
Training time of AGADESN algorithm.Figure 18
Average time of intention recognition under single test scenario.Figure17 shows the training time of AGADESN algorithm for each destination prediction. It can be seen from Figure 17 that the average training time for each prediction of AGADESN algorithm is 607 s, of which the iteration time for adaptive genetic algorithm is 83 s, and the time for DESN training is 524 s. It can be seen that because the adaptive genetic algorithm embeds the DESN training process, the algorithm needs to calculate the DESN training error in each iteration, so the DESN training time accounts for the main part of the AGADESN algorithm training time. This also leads to the long training time of the algorithm. The adaptive genetic algorithm proposed in the paper uses adaptive mutation rate, and its genetic operation iteration time is short. Comparing the training time of each destination prediction, it can be seen that when the target is maneuvering, the time required for algorithm training increases because the destination position is unknown after maneuvering. When the target approaches the destination, the cluster moves straight toward the destination with less noise, and the algorithm training time is reduced.Figure18 shows the average recognition time of our algorithm for the cluster intention in a single test scenario. The average time of intention recognition of the trained network in a single scene is 0.1221s, including 0.0988 s for destination prediction and 0.0233 s for cluster identification. It can be seen from Figure 18 that the algorithm has a fast intention recognition speed for 15 targets in a single test scenario, and the destination prediction time accounts for the main part of the algorithm’s running time. Because DBSCAN algorithm has no deep structure, it has higher efficiency. Its clustering identification speed is fast and can meet the real-time requirements.From the above analysis, it can be seen that the trained network can quickly identify the cluster motion intention, which makes the algorithm applicable to the prediction of large-scale cluster motion intention. However, because AGADESN algorithm directly uses the training error of DESN as the fitness evaluation function in the training process, it takes a long time for a single iteration of AGADESN, which makes the algorithm unable to meet the requirements of online real-time training, which limits the training speed of the algorithm in large-scale data sets.


### 4.4.3. Exploration of Further Improving the Accuracy of Intention Recognition

In this paper, in order to accurately simulate more the cluster motion, we introduce the motion direction noise with time-varying variance on the basis of the basic Olfati-Saber model. However, the cluster motion trajectory noise makes the relationship between the motion characteristics and the destination more unclear, which has a negative impact on the prediction of the cluster motion destination. In order to alleviate the interference of noise and extract more motion features related to the destination, we try to decompose the cluster motion trajectory signal by using the variational mode decomposition (VMD) algorithm [41]. Due to the independence of different modality data, it is possible to further improve the accuracy of destination prediction by inputting different modality data into the circular convolution attention network to fuse different features for destination prediction [42].We define the motion similarity distance and introduce the destination prediction distance into the position speed distance to judge whether multiple targets belong to the same cluster, which achieves better cluster recognition effect. However, when the cluster splits, the effect of DBSCAN algorithm in identifying clusters fluctuates and lags, which brings challenges to the real-time performance of the algorithm. During the experiment, we realize that the improvement of the clustering identification effect is essentially due to the introduction of additional information (destination information). Therefore, in order to improve the real-time performance of the cluster recognition algorithm, further information mining of the cluster motion trajectory is needed.In terms of hardware, we can use infrared, photoelectric and other sensors to obtain the multidimensional information of the target, but we must propose better feature selection and fusion algorithms. Chen et al. [43] proposed two deep learning frameworks to explore and preserve the temporal and spatial information of EEG signals in a cascade or parallel manner and achieved good results in human intention recognition, which is enlightening to us. The basis of cluster identification is that targets with similar features should have a greater probability of being neighbours. We can use more complex convolutional neural networks to explore the local structure of clusters and integrate it into the selection of joint features [44]. Secondly, the cluster identification should be carried out in a more adaptive way, using an adaptive loss function to enhance the robustness to system noise, which may be caused by wrong destination prediction or by abnormal parameter values of DBSCAN algorithm.


## 4.4.1. Selection of Eps

The selection ofEps has an impact on DBSCAN algorithm. In order to evaluate the significance of Eps influence, we increase Eps from 0.01 to 1 with the step size of 0.01, and set appropriate distance parameters for all cluster scenarios in the test set to conduct cluster identification experiments. The correct identification probability of cluster number is shown in Figure 16.Figure 16
Correct identification probability under differentEps.As can be seen from Figure16, although Eps can be set arbitrarily within [0.01, 1), the DBSCAN algorithm can obtain a good correct identification probability under any Eps. However, with the increase of Eps, the probability still shows a process of first increasing and then decreasing. When Eps is set in (0.3, 0.4), the correct identification probability is the highest. The analysis shows that Eps setting value is related to a variety of factors and is most closely related to the distance between clusters during the whole motion of clusters. When clusters are close to each other, if Eps is set too small, members in the same cluster may be considered as belonging to different clusters, resulting in a large number of identified clusters. On the contrary, if Eps is set too large, the number of identified clusters may be less. Therefore, for the whole process of cluster motion, the adaptive setting of Eps can achieve the best cluster identification effect.


## 4.4.2. Algorithm Runtime Evaluation

To evaluate the feasibility of the algorithm on large-scale data sets, Figures17 and 18 show the running time of each intention recognition of the algorithm in the experiment.Figure 17
Training time of AGADESN algorithm.Figure 18
Average time of intention recognition under single test scenario.Figure17 shows the training time of AGADESN algorithm for each destination prediction. It can be seen from Figure 17 that the average training time for each prediction of AGADESN algorithm is 607 s, of which the iteration time for adaptive genetic algorithm is 83 s, and the time for DESN training is 524 s. It can be seen that because the adaptive genetic algorithm embeds the DESN training process, the algorithm needs to calculate the DESN training error in each iteration, so the DESN training time accounts for the main part of the AGADESN algorithm training time. This also leads to the long training time of the algorithm. The adaptive genetic algorithm proposed in the paper uses adaptive mutation rate, and its genetic operation iteration time is short. Comparing the training time of each destination prediction, it can be seen that when the target is maneuvering, the time required for algorithm training increases because the destination position is unknown after maneuvering. When the target approaches the destination, the cluster moves straight toward the destination with less noise, and the algorithm training time is reduced.Figure18 shows the average recognition time of our algorithm for the cluster intention in a single test scenario. The average time of intention recognition of the trained network in a single scene is 0.1221s, including 0.0988 s for destination prediction and 0.0233 s for cluster identification. It can be seen from Figure 18 that the algorithm has a fast intention recognition speed for 15 targets in a single test scenario, and the destination prediction time accounts for the main part of the algorithm’s running time. Because DBSCAN algorithm has no deep structure, it has higher efficiency. Its clustering identification speed is fast and can meet the real-time requirements.From the above analysis, it can be seen that the trained network can quickly identify the cluster motion intention, which makes the algorithm applicable to the prediction of large-scale cluster motion intention. However, because AGADESN algorithm directly uses the training error of DESN as the fitness evaluation function in the training process, it takes a long time for a single iteration of AGADESN, which makes the algorithm unable to meet the requirements of online real-time training, which limits the training speed of the algorithm in large-scale data sets.


## 4.4.3. Exploration of Further Improving the Accuracy of Intention Recognition

In this paper, in order to accurately simulate more the cluster motion, we introduce the motion direction noise with time-varying variance on the basis of the basic Olfati-Saber model. However, the cluster motion trajectory noise makes the relationship between the motion characteristics and the destination more unclear, which has a negative impact on the prediction of the cluster motion destination. In order to alleviate the interference of noise and extract more motion features related to the destination, we try to decompose the cluster motion trajectory signal by using the variational mode decomposition (VMD) algorithm [41]. Due to the independence of different modality data, it is possible to further improve the accuracy of destination prediction by inputting different modality data into the circular convolution attention network to fuse different features for destination prediction [42].We define the motion similarity distance and introduce the destination prediction distance into the position speed distance to judge whether multiple targets belong to the same cluster, which achieves better cluster recognition effect. However, when the cluster splits, the effect of DBSCAN algorithm in identifying clusters fluctuates and lags, which brings challenges to the real-time performance of the algorithm. During the experiment, we realize that the improvement of the clustering identification effect is essentially due to the introduction of additional information (destination information). Therefore, in order to improve the real-time performance of the cluster recognition algorithm, further information mining of the cluster motion trajectory is needed.In terms of hardware, we can use infrared, photoelectric and other sensors to obtain the multidimensional information of the target, but we must propose better feature selection and fusion algorithms. Chen et al. [43] proposed two deep learning frameworks to explore and preserve the temporal and spatial information of EEG signals in a cascade or parallel manner and achieved good results in human intention recognition, which is enlightening to us. The basis of cluster identification is that targets with similar features should have a greater probability of being neighbours. We can use more complex convolutional neural networks to explore the local structure of clusters and integrate it into the selection of joint features [44]. Secondly, the cluster identification should be carried out in a more adaptive way, using an adaptive loss function to enhance the robustness to system noise, which may be caused by wrong destination prediction or by abnormal parameter values of DBSCAN algorithm.


## 5. Conclusions

In this paper, we propose a joint algorithm of AGADESN algorithm and DBSCAN clustering algorithm for motion intention recognition of cluster targets. It can simultaneously predict the moving destination of cluster targets and identify clusters in the field of view. The improved Olfati-Saber model is used to generate cluster motion, which takes into account the accuracy of destination information acquired by cluster targets, and introduces the motion direction noise with time-varying variance. In the intention prediction algorithm, we introduce the adaptive mutation rate to optimize genetic algorithm and use adaptive genetic algorithm to optimize DESN parameters. The optimized DESN is used for destination prediction of cluster targets, and a more accurate prediction effect is achieved. The prediction output information provides input for the innovatively designed MSD. Based on the MSD, we identify clusters within the field of view under the DBSCAN framework to judge in real-time whether target splitting behavior occurs, which is more robust than the DBSCAN algorithm considering only the position and speed distance. In future work, we may improve the clustering algorithm to reduce the required parameters, further improving the cluster identification performance.



---

*Source: 8220029-2022-10-22.xml*