# An Improved KF-RBF Based Estimation Algorithm for Coverage Control with Unknown Density Function

Authors: Lei Zuo; Maode Yan; Yaoren Guo; Wenrui Ma
Journal: Complexity
 (2019)

---

## Abstract

This paper investigates the coverage control for a group of agents, where the density function over the given region is unknown and time-varying. A cost function, depending on the density function and a certain metric, is provided to evaluate the performance of coverage network. Then, while considering the sampling noise, a novel estimation algorithm is developed to approximate the density function based on the Kalman filter (KF) and the Radial Basis Function (RBF) neural network. Compared with the other estimation algorithms, a novel sampling regulation mechanism is designed to improve the estimation performance and reduce the computational load. On this basis, a coverage control scheme with estimated density function is proposed to drive the agents to the optimal deployment. Moreover, the stability and performance of proposed coverage control system are strictly analyzed. Finally, numerical simulation is provided to illustrate the effectiveness of proposed approaches.


---

## Body

## 1. Introduction

Recently, the coverage control has received substantially increasing interest, which has emerged in many applications [1–7]. The objective of coverage control is to deploy the agents in a given region, such that the regions with higher interest can get more attentions from the agents. The distribution of this interested information is defined asdensity function. To achieve this goal, a cost function, containing a certain metric and the density function, is provided to evaluate the performance of coverage network. Then, a distributed controller is proposed to minimize this cost function such that the agents can reach the optimal deployment from arbitrary initial positions. It can be seen that the density function plays an important role in coverage control.Due to the fact that the density function is usually unknown to the agents, the coverage control with unknown density function has been further investigated. Generally, a spatial estimation algorithm is usually developed to approximate the density function. For example, a decentralized adaptive spatial estimation algorithm is developed to approximate the density function for the coverage control in [8]. To verify the effectiveness of this spatial estimation algorithm, an experiment with a group of mobile sensors is presented in [9]. In our previous work, an efficient coverage algorithm for mobile sensor networks with unknown density function is proposed, where the consensus mechanism is applied to improve the estimation efficiency [10]. More related literature can be found in [11–14].While considering the sampling noise, the filter algorithms are usually employed to estimate the density function. For instance, the density function over a spatially decoupled scalar field is estimated by using a discrete Kalman filter (KF) based estimation algorithm in [15]. A distributed spatial estimation algorithm based on the Kriging interpolation technique is developed for a group of agents in [16]. The experiment for this KF-based estimation algorithm in coverage control is provided in [17]. To further proceed with the coverage control with unknown density function, a novel estimation algorithm is developed for the coverage network by using the neural network in [18].When the density function is time-varying, there are also some results to drive the agents to the optimal deployment. In [19], a switching control algorithm with two controllers is proposed, where the first controller is used to compensate for the variation of density function and the second one is to drive the agents to their optimal positions. The coverage control with time-varying density function is also investigated in [20], in which the density function over this field is continuously growing and cannot be measured by the onboard sensors. Moreover, for the coverage control with unknown and time-varying density function, the Bayesian prediction techniques are employed to estimate the density function in [21].Although the coverage control with unknown density function has been well studied, there are still many problems in practice. For instance, in [8–10], the density function is estimated based on the noise-free measurements, which limits their applications. For the coverage control with noisy measurements ([15–17]), the state transition matrices in these KF-based estimation algorithms are usually assumed to be knowna priori. Moreover, in [18, 21], the computational load of the estimation algorithms is heavy. In addition, for most existing coverage control with time-varying density function, the agents are assumed to know the density functiona priori ([19, 20]). Hence, it is necessary to further investigate the coverage control with both time-varying and unknown density function.Motivated by this fact, a novel estimation algorithm for density function is developed based on the Kalman filter (KF) and Radial Basis Function (RBF) neural networks. The coverage control scheme with this estimated density function is further proposed in this paper. The main contributions are twofold:(i)
An improved KF-RBF based estimation algorithm is proposed for the unknown and time-varying density function in coverage control. In this estimation algorithm, the RBF neural network is used to estimate the density function and the related Kalman filter is employed to deal with the noisy measurements. Moreover, a sampling regulation mechanism is designed to improve the estimation efficiency and reduce the computational load. Compared with the existing results in [15–17], the proposed KF-RBF based estimation algorithm can deal with the sampling noise and approximate the time-varying density function without any assumption about the state transition matrices. Moreover, since a sampling regulation mechanism is applied into this estimation algorithm, its computational load is less than the spatial estimation algorithms in [18, 21].(ii)
Based on the estimated density function, a coverage control strategy is proposed to drive the agents to the optimal deployment. Since the density function is time-varying, the proposed coverage network can effectively adjust the deployment of agents, such that the regions with higher interest could always get more attention from the agents. Moreover, the stability and performance of this proposed coverage control system are strictly analyzed.The remainder of this paper is organized as follows: The preliminaries and problem formulation are presented in Section2. An improved KF-RBF based estimation algorithm is developed in Section 3, and the related coverage control scheme is proposed in Section 4. In Section 5, numerical simulations are provided to verify the proposed approaches. Finally, Section 6 concludes this paper.


## 2. Preliminaries and Problem Formulation

Considern agents in a given region Q. The density function over this region is denoted as ϕ(q,t):R2→R+,q∈Q. Then, we define the following cost function(1)HP,t=∑i=1n∫Wifpi,qϕq,tdqwhere P=[p1,…,pn]T is the position vector of all agents; Wi is the assigned region to the ith agent, and f(pi,q) is the metric describing the coverage cost from pi to q.To quantitatively assess the coverage cost, letf(pi,q)=pi-q2. Then, according to Lloyd algorithm, the Voronoi partition is the optimal strategy for a group of agents in a convex region [22]. That is, the Voronoi region is the optimal assigned region to each agent. The detailed definition of Voronoi region is shown as(2)Vi=q∈Q∣q-pi2≤q-pj2,∀i,j∈n,i≠jwhere q∈Q is an arbitrary point in Q and Vi is the Voronoi region to the ith agent.Then, the cost function with quantitative assessmentpi-q2 and Voronoi region Vi is presented as(3)HP,t=∑i=1n∫Viq-pi2ϕq,tdqThe objective of coverage control is to minimize the cost functionH(P,t) in (3). As H(P,t) is a function in terms of pi and t, we take the partial derivative of H(P,t) along the trajectory of each agent:(4)∂HP,t∂pi=2MVipi-CViwhere(5)MVi=∫Viϕq,tdqCVi=∫Viqϕq,tdq∫Viϕq,tdq.Then, the cost function will reach the minimum when∂H(P,t)/∂pi=0. It leads us to (6)pi∗=CVi=∫Viqϕq,tdq∫Viϕq,tdqwhere pi∗ denotes the optimal position of the ith agent.On this basis, the optimal deployment for a group of agents is thatpi=CVi,∀i=1,…,n. Note that the density function ϕ(q,t) is necessary to obtain CVi. However, it is usually time-varying and unknown to the agents. To this end, an improved KF-RBF based estimation algorithm is designed to approximate the density function, and the coverage control with estimated density function will be proposed in this paper.Remark 1.
In general, the density functionϕ(q,t) denotes the distribution of interested information in a given region. In practical cases, the density function has a lot of physical meanings. For instance, the density function can denote the occurrence probability of events in the given region. Then, based on the objective of coverage control, we can effectively drive the agents to the optimal deployment, such that the regions with higher probabilities can get more attention from the agents. One can refer to [23, 24] for more details about the coverage control with detailed density function.


## 3. The Improved KF-RBF Estimation Algorithm

### 3.1. Spatial Model

Suppose the agents can measure the density function at its location. Then, the measurements of coverage network are shown as follows.(7)YP,t=yp1,t,…,ypn,tT∈RnAs the density functionϕ(q,t) is time-varying and the measurements are noise corrupted, a KF-RBF based estimation algorithm will be developed to approximate the ϕ(q,t). In the RBF framework, let Ψ(q)=[ψ1(q),…,ψm(q)]T∈Rm be the basis function. Then, there exists an ideal vector w∈Rm satisfying [25](8)YP,t=ΨTPwwhere w is the ideal coefficient in RBF framework and Ψ(P) is shown by the following. (9)ΨP=ψ1p1,⋯,ψ1pn,⋮,⋱,⋮,ψmp1,⋯,ψmpn,∈Rm×nDenoteϕ^(q,t) as the estimated density function. The estimation error ϕ~(q,t) is shown as(10)ϕ~q,t=ϕ^q,t-ϕq,t=ψTqw^-ψTqw=ψTqw~where w^ is the estimated coefficient in RBF and w~=w^-w.Particularly, the Voronoi centroid with estimated density function is shown as follows.(11)C^Vi=∫Viqϕ^q,tdq∫Viϕ^q,tdqRegarding the estimated Voronoi centroidC^Vi, we have the following definition.Definition 2.
Given a group of agents in the mission region, the coverage network is said to be in anear-optimal deployment when all the agents satisfy limt→∞pi=C^Vi,∀i=1,…,n.


### 3.2. Sampling Regulation Mechanism

LetYk≜Y(P,tk). Then, the Pearson Correlation Coefficient between Yk and Yk-1 is shown as(12)es=∑j=1nYkj-Y¯kYk-1j-Y¯k-1∑j=1nYkj-Y¯k2∑j=1nYk-1j-Y¯k-12where es is the Pearson Correlation Coefficient; Yk(j) and Y¯k denote the jth element and the average of Yk at time tk, respectively.LetΔt1(k) be the sampling period at tk. The initial value of Δt1 is c0 and it satisfies c_≤Δt1(k)≤c¯. Then, according to (12), Δt1(k) is adjusted by the following rules:(13)Δt1k+1=min⁡Δt1k+δ,c¯if0.9≤es≤1max⁡Δt1k-δ,c_if0.8≤es<0.9c_,if0≤es<0.8where δ is a single step in coverage.From (12), we find that es∈[0,1] and the current measurement Yk is more similar to its previous ones when es is larger. For instance, when 0.9≤es≤1, we can increase the sampling period by Δt1(k+1)=Δt1(k)+δ because the current measurements Yk are quite similar to the previous ones Yk-1. When 0.8≤es<0.9, this shows that the current measurements have a certain variation with their previous ones. Hence, it is necessary to reduce the sampling period by a single step δ. The case 0≤es<0.8 means that the measurements have presented great changes. Then, we directly set the sampling period to its minimum c_ to collect more measurements.Moreover, to improve the estimation efficiency, we also take the cost function into consideration. Based on the agents’ current positions and its estimated Voronoi centroids, we have the following cost functions(14)H^aP,tk=∑i=1n∫Vipi-q2ϕ^q,tkdqH^eC^V,tk=∑i=1n∫ViC^Vi-q2ϕ^q,tkdqwhere H^a(P,tk) is the cost function with current positions and H^e(C^V,tk) is the expected cost function with estimated Voronoi centroids; C^V=C^V1,…,C^Vn.From (14), it is shown that the H^e is the expected cost function for the coverage network at tk. Then, define the variation between H^a and H^e as follows.(15)eh=H^a-H^eH^e2=H^aH^e-12>0As theH^e is the cost function with the optimal positions, we have that H^a≥H^e. From (15), it is found that the eh describes the variation between H^a and H^e. The smaller eh, the closer H^a and H^e. Particularly, when H^a=H^e, the coverage network reaches the optimal deployment. In this case, the sampling period can be further extended. Based on these analyses, we develop the following regulation rules(16)Δt2k+1,γk+1=Δt1k+1,γk+αδ,if0≤eh<0.1Δt1k+1,γk+δ,if0.1≤eh<0.3max⁡Δt1k+1-δ,c_,γk,if0.3≤eh<0.5max⁡Δt1k+1-αδ,c_,max⁡γk-δ,0,if0.5≤eh<1max⁡Δt1k+1-2αδ,c_,max⁡γk-αδ,0,if1≤eh<2c_,0,if2≤ehwhere Δt2 is the improved sampling period from Δt1; γ denotes the smoothness of cost function; and α is a positive constant.Compared with (13), Δt2 is provided to adjust the sampling period based on the cost function variation eh. In conjunction with (15) and (16), we separate eh into six parts. For instance, when 0≤eh<0.1, the current cost function H^a is close enough to the expected cost function H^e. Hence, we do not need to change the sampling period Δt1. When 1≤eh<2, it means the H^a has a certain gap with its desired value. Then, we should decrease the sampling period to have more measurements. On this basis, we can effectively obtain an improved sampling regulation rule to estimate the density function.In addition, the smoothness of cost function is also taken into consideration. We useγ to quantitatively assess the smoothness of cost function. When γ is large enough, the cost function will converge to a stable value. It shows that the coverage procedure is stable with its current measurements. In this case, the sampling period can be further increased. On this basis, we have the following auxiliary sampling rules(17)Δt3k+1=Δt2k+1+αδ,ifγk+1≥ηwhere Δt3 is the sampling period regarding both eh and γ; η is a positive constant.Note that there are three levels to regulate the sampling period. We usually takeΔt3 as the final one, because it is calculated by fully considering the coverage procedure and can provide the required measurements properly. To formally illustrate the developed sampling regulation mechanism, we provide Algorithm 1.Algorithm 1:The sampling regulation mechanism in coverage control.
Require: The positions P; The estimated density function ϕ^(q); The Voronoi partition V={V1,…,Vn}; The measurementsYk; The constant η. Ensure: The sampling period Δt3; (1) Initialization: The coverage step δ; The boundaries of sampling period c- and c_. (2) Calculate the sampling variation es based on (12); (3) Choose Δt1 from (13); (5) Obtain H^a and H^e based on the agents’ current position pi and its Voronoi centroids C^Vi. (5) Calculate eh based on (15); (6) According to the bound value of eh in (16), choose the second level sampling period Δt2; (7) Based on the smoothness metric γ and its critic η, calculate the final level sampling period Δt3 through (17).Remark 3.
Note that the measurementy(pi,t) and the density function ϕ(pi,t) are the same. Essentially, they both denote the true value of the density function at pi. y(pi,t) is the sampling measurement from the ith agent at its current position pi. ϕ(pi,t) is from the estimation algorithm, which denotes the ideal approximated value of density function at pi. It can be presented as ϕ(pi,t)=ψT(pi)w, in which the w is the ideal coefficient vector and unknown to the agents.Remark 4.
In the proposed sampling regulation mechanism, the bound values ofes and eh are determined by practical requirements. In detail, we should firstly find the boundaries of es and eh based on their definitions. Then, we separate the ranges of es and eh into some subregions by the bound values. These bound values are determined by practical requirements. For instance, {Δt2(k+1),γ(k+1)}={Δt1(k+1),γ(k)+αδ} if 0≤eh<0.1. The range 0≤eh<0.1 is given based on practical requirements. When the higher precision is required, one can also set this bound value as 0≤eh<0.05, which is essentially more fastidious to the measurements.Remark 5.
It is also worth noting that both the efficiency and accuracy of proposed estimation algorithm are affected by the sampling regulation mechanism. Generally, the smaller of the sampling period, the more accurate of the estimation algorithm. However, it would increase the dimension of measurements, which greatly limits the efficiency of the proposed estimation algorithm. Therefore, the trade-off between the estimation accuracy and efficiency should be taken into consideration while designing the sampling regulation mechanism.Remark 6.
Actually, there are three levels in the proposed sampling regulation mechanism. The first level is based on the variation of measurements, denoted byes. Based on the proposed rules in (13), the sampling period will be reduced when the current measurements have a certain variation with its previous ones. Otherwise, it will be extended. The second level is based on the differences between the current cost function H^a and the expected cost function H^e. When H^a has a certain gap from H^e, this means that the estimated errors for density function may be too large for the coverage system. Then, we need to collect more measurements to improve the estimation accuracy, which is usually realized by reducing the sampling period. In the third level, we take the smoothness of cost function into consideration. We use γ to illustrate the smoothness of cost function, and the cost function will converge to a stable value if γ is large enough. In this case, the coverage procedure is stable and accurate with its current measurements, which indicates that the sampling period can be further increased. Based on the above three levels in sampling regulation mechanism, we can greatly reduce the computational load and improve the efficiency of proposed coverage system.


### 3.3. Improved KF-RBF Based Estimation Algorithm

Regarding the proposed sampling regulation mechanism, an improved KF-RBF based estimation algorithm for density function is developed in this subsection.Depending on the RBF framework, we estimate the density function by(18)ϕ^q,t=ψTqw^-cTq,Pc-1P,PΨTPw^-YP,twhere c(·,·) denotes the spatial and temporal correlation function between any two points in the given region. For instance, c(q,P) shows the correlation between any point q and the sampling positions P. The detailed formulations of c(q,P) and c(P,P) are presented as(19)ci=σrexp⁡-q-pi2σs2exp⁡-t-ti2σt2cij=σrexp⁡-pi-pj2σs2exp⁡-ti-tj2σt2+δijwhere ci is the ith element in c(q,P) and cij is the ijth element in c(P,P); σr is a constant gain parameter; σs and σt are spatial and temporal sensitivity parameters, respectively. δij is the Kronecker Delta function, which equals 1 if i=j and zeros otherwise.The objective of this estimation algorithm is to update the coefficientw^ such that the estimation errors ϕ~(q,t) would converge to zeros. The updated law is shown as follows(20)w^˙=-KptkΨTPw^i-YP,tk+Ψ-1P1-∫Vipi-q2ψqdqw^i-Ψ-1PYP,tkΔYP,tk-∫ViΨPc-1P,Pcq,Pq-C^Vi+ψqq-C^ViTdqKC^Vi-piwhere ΔY(P,tk)=Y(P,tk)-Y(P,tk-1)/tk-tk-1; K is a positive definite matrix; Kp(tk) is the gain matrix from Kalman filter, shown as follows(21)Kptk=Pktk-1ΨTPΨPPktk-1ΨTP+R-1where R is the noise covariance matrix; Pk(tk-1) is the covariance matrix for estimation errors shown by the following. (22)Pktk=Pktk-1-KptkΨPPktk-1In this way, the density function at any pointq can be approximated by (18), (20), and (21). The Kp in (21) is derived from the Kalman filter, which is used to deal with sampling noise. To fully illustrate the improved KF-RBF based estimation algorithm, we provide Algorithm 2.Algorithm 2:The improved KF-RBF based estimation algorithm.
Require: The sampling measurements Y(P,t) and the agent positions P. Ensure: The estimated density function ϕ^(q,t) (1) Initialization: The related parameters w^0, σr, σs, σt, R, Pk(t0); The basis function ψ(q) and the estimation errors criticξ; (2) whileQ≠⌀do (3) q=q∗ and w^=w^0; (4) Compute Ψ(P), c(q,P) and C(P,P) in (18); (5) Obtain C^Vi through the previous estimated density function; (6) Calculate the estimation errors ΨT(P)w^-Y(P,t); (7)whileΨT(P)w^-Y(P,t)>ξdo (8)  Calculate Kp(tk) based on (21); (9)  Update the covariance matrix Pk(tk); (10)  Substitute Kp(tk) into (20) and obtain the coefficient parameters w^(tk+1); (11)  Obtain the estimated density function ϕ^(q,tk+1) through (18); (12)end while (13) Remove q from Q and choose another point q∗ for estimation; (14) Update the related variables: k=k+1; w^0=w^tk+1; (15) end whileIn Algorithm2, the parameters σr, σs, and σt are chosen based on the boundary of density function and the given region. To accurately obtain these parameters, one can use the Monte Carlo and Markov Chain (MCMC) to calculate them iteratively [26]. In addition, while applying Algorithm 2, we have to rasterize the given region to obtain the spatial distribution of density function. In this way, we can calculate the density function point by point and finally get the distribution of density function over the given region.Remark 7.
In addition, the adaptive updated law ofw^˙ in (20) consists of three parts. The first term is used to decrease the estimation errors of density function; the second one can eliminate the influence of time-varying density function in proposed coverage control system; and the last one is to compensate for the distance between the estimated centroid C^Vi and the real centroid CVi. In conjunction with these terms, the estimation errors of proposed algorithm will converge to zeros while ensuring the system stability.


## 3.1. Spatial Model

Suppose the agents can measure the density function at its location. Then, the measurements of coverage network are shown as follows.(7)YP,t=yp1,t,…,ypn,tT∈RnAs the density functionϕ(q,t) is time-varying and the measurements are noise corrupted, a KF-RBF based estimation algorithm will be developed to approximate the ϕ(q,t). In the RBF framework, let Ψ(q)=[ψ1(q),…,ψm(q)]T∈Rm be the basis function. Then, there exists an ideal vector w∈Rm satisfying [25](8)YP,t=ΨTPwwhere w is the ideal coefficient in RBF framework and Ψ(P) is shown by the following. (9)ΨP=ψ1p1,⋯,ψ1pn,⋮,⋱,⋮,ψmp1,⋯,ψmpn,∈Rm×nDenoteϕ^(q,t) as the estimated density function. The estimation error ϕ~(q,t) is shown as(10)ϕ~q,t=ϕ^q,t-ϕq,t=ψTqw^-ψTqw=ψTqw~where w^ is the estimated coefficient in RBF and w~=w^-w.Particularly, the Voronoi centroid with estimated density function is shown as follows.(11)C^Vi=∫Viqϕ^q,tdq∫Viϕ^q,tdqRegarding the estimated Voronoi centroidC^Vi, we have the following definition.Definition 2.
Given a group of agents in the mission region, the coverage network is said to be in anear-optimal deployment when all the agents satisfy limt→∞pi=C^Vi,∀i=1,…,n.


## 3.2. Sampling Regulation Mechanism

LetYk≜Y(P,tk). Then, the Pearson Correlation Coefficient between Yk and Yk-1 is shown as(12)es=∑j=1nYkj-Y¯kYk-1j-Y¯k-1∑j=1nYkj-Y¯k2∑j=1nYk-1j-Y¯k-12where es is the Pearson Correlation Coefficient; Yk(j) and Y¯k denote the jth element and the average of Yk at time tk, respectively.LetΔt1(k) be the sampling period at tk. The initial value of Δt1 is c0 and it satisfies c_≤Δt1(k)≤c¯. Then, according to (12), Δt1(k) is adjusted by the following rules:(13)Δt1k+1=min⁡Δt1k+δ,c¯if0.9≤es≤1max⁡Δt1k-δ,c_if0.8≤es<0.9c_,if0≤es<0.8where δ is a single step in coverage.From (12), we find that es∈[0,1] and the current measurement Yk is more similar to its previous ones when es is larger. For instance, when 0.9≤es≤1, we can increase the sampling period by Δt1(k+1)=Δt1(k)+δ because the current measurements Yk are quite similar to the previous ones Yk-1. When 0.8≤es<0.9, this shows that the current measurements have a certain variation with their previous ones. Hence, it is necessary to reduce the sampling period by a single step δ. The case 0≤es<0.8 means that the measurements have presented great changes. Then, we directly set the sampling period to its minimum c_ to collect more measurements.Moreover, to improve the estimation efficiency, we also take the cost function into consideration. Based on the agents’ current positions and its estimated Voronoi centroids, we have the following cost functions(14)H^aP,tk=∑i=1n∫Vipi-q2ϕ^q,tkdqH^eC^V,tk=∑i=1n∫ViC^Vi-q2ϕ^q,tkdqwhere H^a(P,tk) is the cost function with current positions and H^e(C^V,tk) is the expected cost function with estimated Voronoi centroids; C^V=C^V1,…,C^Vn.From (14), it is shown that the H^e is the expected cost function for the coverage network at tk. Then, define the variation between H^a and H^e as follows.(15)eh=H^a-H^eH^e2=H^aH^e-12>0As theH^e is the cost function with the optimal positions, we have that H^a≥H^e. From (15), it is found that the eh describes the variation between H^a and H^e. The smaller eh, the closer H^a and H^e. Particularly, when H^a=H^e, the coverage network reaches the optimal deployment. In this case, the sampling period can be further extended. Based on these analyses, we develop the following regulation rules(16)Δt2k+1,γk+1=Δt1k+1,γk+αδ,if0≤eh<0.1Δt1k+1,γk+δ,if0.1≤eh<0.3max⁡Δt1k+1-δ,c_,γk,if0.3≤eh<0.5max⁡Δt1k+1-αδ,c_,max⁡γk-δ,0,if0.5≤eh<1max⁡Δt1k+1-2αδ,c_,max⁡γk-αδ,0,if1≤eh<2c_,0,if2≤ehwhere Δt2 is the improved sampling period from Δt1; γ denotes the smoothness of cost function; and α is a positive constant.Compared with (13), Δt2 is provided to adjust the sampling period based on the cost function variation eh. In conjunction with (15) and (16), we separate eh into six parts. For instance, when 0≤eh<0.1, the current cost function H^a is close enough to the expected cost function H^e. Hence, we do not need to change the sampling period Δt1. When 1≤eh<2, it means the H^a has a certain gap with its desired value. Then, we should decrease the sampling period to have more measurements. On this basis, we can effectively obtain an improved sampling regulation rule to estimate the density function.In addition, the smoothness of cost function is also taken into consideration. We useγ to quantitatively assess the smoothness of cost function. When γ is large enough, the cost function will converge to a stable value. It shows that the coverage procedure is stable with its current measurements. In this case, the sampling period can be further increased. On this basis, we have the following auxiliary sampling rules(17)Δt3k+1=Δt2k+1+αδ,ifγk+1≥ηwhere Δt3 is the sampling period regarding both eh and γ; η is a positive constant.Note that there are three levels to regulate the sampling period. We usually takeΔt3 as the final one, because it is calculated by fully considering the coverage procedure and can provide the required measurements properly. To formally illustrate the developed sampling regulation mechanism, we provide Algorithm 1.Algorithm 1:The sampling regulation mechanism in coverage control.
Require: The positions P; The estimated density function ϕ^(q); The Voronoi partition V={V1,…,Vn}; The measurementsYk; The constant η. Ensure: The sampling period Δt3; (1) Initialization: The coverage step δ; The boundaries of sampling period c- and c_. (2) Calculate the sampling variation es based on (12); (3) Choose Δt1 from (13); (5) Obtain H^a and H^e based on the agents’ current position pi and its Voronoi centroids C^Vi. (5) Calculate eh based on (15); (6) According to the bound value of eh in (16), choose the second level sampling period Δt2; (7) Based on the smoothness metric γ and its critic η, calculate the final level sampling period Δt3 through (17).Remark 3.
Note that the measurementy(pi,t) and the density function ϕ(pi,t) are the same. Essentially, they both denote the true value of the density function at pi. y(pi,t) is the sampling measurement from the ith agent at its current position pi. ϕ(pi,t) is from the estimation algorithm, which denotes the ideal approximated value of density function at pi. It can be presented as ϕ(pi,t)=ψT(pi)w, in which the w is the ideal coefficient vector and unknown to the agents.Remark 4.
In the proposed sampling regulation mechanism, the bound values ofes and eh are determined by practical requirements. In detail, we should firstly find the boundaries of es and eh based on their definitions. Then, we separate the ranges of es and eh into some subregions by the bound values. These bound values are determined by practical requirements. For instance, {Δt2(k+1),γ(k+1)}={Δt1(k+1),γ(k)+αδ} if 0≤eh<0.1. The range 0≤eh<0.1 is given based on practical requirements. When the higher precision is required, one can also set this bound value as 0≤eh<0.05, which is essentially more fastidious to the measurements.Remark 5.
It is also worth noting that both the efficiency and accuracy of proposed estimation algorithm are affected by the sampling regulation mechanism. Generally, the smaller of the sampling period, the more accurate of the estimation algorithm. However, it would increase the dimension of measurements, which greatly limits the efficiency of the proposed estimation algorithm. Therefore, the trade-off between the estimation accuracy and efficiency should be taken into consideration while designing the sampling regulation mechanism.Remark 6.
Actually, there are three levels in the proposed sampling regulation mechanism. The first level is based on the variation of measurements, denoted byes. Based on the proposed rules in (13), the sampling period will be reduced when the current measurements have a certain variation with its previous ones. Otherwise, it will be extended. The second level is based on the differences between the current cost function H^a and the expected cost function H^e. When H^a has a certain gap from H^e, this means that the estimated errors for density function may be too large for the coverage system. Then, we need to collect more measurements to improve the estimation accuracy, which is usually realized by reducing the sampling period. In the third level, we take the smoothness of cost function into consideration. We use γ to illustrate the smoothness of cost function, and the cost function will converge to a stable value if γ is large enough. In this case, the coverage procedure is stable and accurate with its current measurements, which indicates that the sampling period can be further increased. Based on the above three levels in sampling regulation mechanism, we can greatly reduce the computational load and improve the efficiency of proposed coverage system.


## 3.3. Improved KF-RBF Based Estimation Algorithm

Regarding the proposed sampling regulation mechanism, an improved KF-RBF based estimation algorithm for density function is developed in this subsection.Depending on the RBF framework, we estimate the density function by(18)ϕ^q,t=ψTqw^-cTq,Pc-1P,PΨTPw^-YP,twhere c(·,·) denotes the spatial and temporal correlation function between any two points in the given region. For instance, c(q,P) shows the correlation between any point q and the sampling positions P. The detailed formulations of c(q,P) and c(P,P) are presented as(19)ci=σrexp⁡-q-pi2σs2exp⁡-t-ti2σt2cij=σrexp⁡-pi-pj2σs2exp⁡-ti-tj2σt2+δijwhere ci is the ith element in c(q,P) and cij is the ijth element in c(P,P); σr is a constant gain parameter; σs and σt are spatial and temporal sensitivity parameters, respectively. δij is the Kronecker Delta function, which equals 1 if i=j and zeros otherwise.The objective of this estimation algorithm is to update the coefficientw^ such that the estimation errors ϕ~(q,t) would converge to zeros. The updated law is shown as follows(20)w^˙=-KptkΨTPw^i-YP,tk+Ψ-1P1-∫Vipi-q2ψqdqw^i-Ψ-1PYP,tkΔYP,tk-∫ViΨPc-1P,Pcq,Pq-C^Vi+ψqq-C^ViTdqKC^Vi-piwhere ΔY(P,tk)=Y(P,tk)-Y(P,tk-1)/tk-tk-1; K is a positive definite matrix; Kp(tk) is the gain matrix from Kalman filter, shown as follows(21)Kptk=Pktk-1ΨTPΨPPktk-1ΨTP+R-1where R is the noise covariance matrix; Pk(tk-1) is the covariance matrix for estimation errors shown by the following. (22)Pktk=Pktk-1-KptkΨPPktk-1In this way, the density function at any pointq can be approximated by (18), (20), and (21). The Kp in (21) is derived from the Kalman filter, which is used to deal with sampling noise. To fully illustrate the improved KF-RBF based estimation algorithm, we provide Algorithm 2.Algorithm 2:The improved KF-RBF based estimation algorithm.
Require: The sampling measurements Y(P,t) and the agent positions P. Ensure: The estimated density function ϕ^(q,t) (1) Initialization: The related parameters w^0, σr, σs, σt, R, Pk(t0); The basis function ψ(q) and the estimation errors criticξ; (2) whileQ≠⌀do (3) q=q∗ and w^=w^0; (4) Compute Ψ(P), c(q,P) and C(P,P) in (18); (5) Obtain C^Vi through the previous estimated density function; (6) Calculate the estimation errors ΨT(P)w^-Y(P,t); (7)whileΨT(P)w^-Y(P,t)>ξdo (8)  Calculate Kp(tk) based on (21); (9)  Update the covariance matrix Pk(tk); (10)  Substitute Kp(tk) into (20) and obtain the coefficient parameters w^(tk+1); (11)  Obtain the estimated density function ϕ^(q,tk+1) through (18); (12)end while (13) Remove q from Q and choose another point q∗ for estimation; (14) Update the related variables: k=k+1; w^0=w^tk+1; (15) end whileIn Algorithm2, the parameters σr, σs, and σt are chosen based on the boundary of density function and the given region. To accurately obtain these parameters, one can use the Monte Carlo and Markov Chain (MCMC) to calculate them iteratively [26]. In addition, while applying Algorithm 2, we have to rasterize the given region to obtain the spatial distribution of density function. In this way, we can calculate the density function point by point and finally get the distribution of density function over the given region.Remark 7.
In addition, the adaptive updated law ofw^˙ in (20) consists of three parts. The first term is used to decrease the estimation errors of density function; the second one can eliminate the influence of time-varying density function in proposed coverage control system; and the last one is to compensate for the distance between the estimated centroid C^Vi and the real centroid CVi. In conjunction with these terms, the estimation errors of proposed algorithm will converge to zeros while ensuring the system stability.


## 4. Coverage Control with Estimated Density Function

In this section, the coverage control scheme with estimated density function is developed. The performance and stability of this proposed coverage control system are further analyzed.Consider the dynamics of agents as follows(23)p˙i=ui,i=1,⋯,nwhere ui is the inputs of each agent.Regarding the estimated density functionϕ^(q,t), the cost function with estimated density function is presented as follows. (24)H^P,t=∑i=1n∫Viq-pi2ϕ^q,tdqThen, a distributed coverage control law is proposed as follows:(25)ui=Kc∫Viϕ^q,tdq∫Viqϕ^q,tdq-pi=KcC^Vi-pi,i=1,⋯,nwhere Kc∈R2×2 is the positive definite matrix.To further analyze the stability of proposed coverage system, a formalized theorem is presented as follows.Theorem 8.
Consider a group of agents in a given regionQ, which is described by (23). The sampling regulation mechanism of these agents is presented in (13), (16), and (17). The time-varying density function over given region is approximated through (18). Then, by using the proposed coverage control law in (25), the coverage network will converge to the near-optimal deployment from arbitrary initial positions.Proof.
According to (18), the estimation errors are shown as follows. (26)ϕ~q,t=ϕ^q,t-ϕq,t=ψTqw~-cTq,Pc-1P,PΨTPw~
Based on the updated law in (20), w^˙i is presented as(27)w^˙i=-KptkΨTPw^i-YP,tk+Ψ-1P1-∫Vipi-q2ψqdqw^i-Ψ-1PYP,tkΔYP,tk-∫ViΨPc-1P,Pcq,Pq-C^Vi+ψqq-C^ViTdqKC^Vi-pi(28)=-KpΨTPw~i+1-∫Vipi-q2ψqdqw~iw˙-A=-KpΨTPw~i+w˙-∫Vipi-q2ψqdqw˙w~i-Awhere (29)A=∫ViΨPc-1P,Pcq,Pq-C^Vi+ψqq-C^ViTdqKC^Vi-pi.
Then, consider the following Lyapunov function candidate.(30)V=H+12∑i=1nw~iTw~i>0
Taking the derivative ofV gives the following.(31)V˙=∑i=1nddt∫Vipi-q2ϕq,tdq+w~iTw~˙i
DenoteV˙i≜d/dt∫Vipi-q2ϕ(q,t)dq+w~iTw~˙i and we have the following.(32)V˙i=ddt∫Vipi-q2ϕq,tdq+w~iTw~˙i=∂∂pi∫Vipi-q2ϕq,tdqp˙i+∫Vipi-q2ϕ˙q,tdq+w~iTw~˙i=MVipi-LVip˙i+∫Vipi-q2ψqdqw˙+w~iTw~˙i
Regarding the estimated density functionϕ^(q,t), LVi satisfies the following.(33)LVi=L^Vi-L~Vi=M^ViC^Vi-M~ViC~Vi=MViC^Vi+M~ViC^Vi-C~Vi
Substituting (25) and (33) into (32), we have the following.(34)V˙i=MVipi-MViC^Vi+M~ViC^Vi-C~ViKcC^Vi-pi+∫Vipi-q2ψqdqw˙+w~iTw~˙i=-MViC^Vi-pi-M~ViC^Vi+L~ViKcC^Vi-pi+∫Vipi-q2ψqdqw˙+w~iTw~˙i
Particularly for the termM~ViC^Vi+L~Vi, we have the following.(35)M~ViC^Vi+L~Vi=∫Viq-C^VicTq,Pc-1P,PΨTPw~i+q-C^ViψqTw~idq
Asw~˙i=w^˙i-w˙, w~iTw~˙i becomes as follows.(36)w~iTw~˙i=w~iT-KpΨTPw~i+w˙-∫Vipi-q2ψqdqw˙w~i-A-w˙=w~iT-KpΨTPw~i-∫Vipi-q2ψqdqw˙w~-A=-w~iTKpΨTPw~i-∫Vipi-q2ψqdqw˙i-w~iTA
Then, in conjunction with (35) and (36), V˙ can be written as follows.(37)V˙=∑i=1n-MViC^Vi-piTKcC^Vi-pi-w~iTKpϕ~q,t
For the termw~iTKpϕ~(q,t) in (37), we have the following.(38)w~iTKpϕ~q,t=w~iTΨPΨ-1PKpΨTPw~i
From the Kalman filter, we notice that theKp is used to measure the influence of sampling noise covariance matrix R and estimation error covariance matrix Pk. Hence, when R and Pk are approaching zeros, Kp satisfies the following.(39)limR→0Kp=limR→0PkΨTPΨPPkΨTP+R=Ψ-1PlimPk→0Kp=limPk→0PkΨTPΨPPkΨTP+R=0
AsΨ-1(P) is positive definite, Ψ-1(P)Kp satisfies the following.(40)Ψ-1PKp∈0,Ψ-1P2
Then, we have the following.(41)w~iTΨPΨ-1PKpΨTPw~i≥0
On this basis,V˙ satisfies the following.(42)V˙=∑i=1n-MViC^Vi-piTKcC^Vi-pi-w~iTKpϕ~q,t≤0
On this basis, we obtain thatV>0 and V˙≤0 in the given region. Based on the Barbalat’s lemma, the proposed coverage system with estimated density function is stable and the agents will asymptotically converge to the near-optimal deployment from arbitrary initial positions. Moreover, as the coverage system converges to the set V˙=0, the coefficient wi satisfies limt→∞w~iTw~i=0. That is, the proposed estimation algorithm for density function will effectively converge to the real density function.Note that the convergence of estimation algorithm and the stability of proposed coverage control system are both demonstrated in this proof. In (30), the w~i is used to show the convergence of proposed estimation algorithm. As shown in this proof, the V will converge to the set V˙=0 under the proposed control law. From (42), it indicates that limt→∞w~iTw~i=0. That is, the estimation errors of proposed estimated algorithm will converge to zeros. Actually, we can individually prove the convergence of proposed estimation algorithm. However, while applying this estimation algorithm into the coverage system, we must show the convergence of proposed coverage control system with estimated density function.Based on the proposed coverage control scheme in (25), the agents will converge to the estimated Voronoi centroids C^Vi,i=1,…,n. From Definition 2, it is shown that the coverage network can only reach the near-optimal deployment when the density function is unknown to the agents. Actually, while converging the estimated density function to the real one, the near-optimal deployment is almost the same with the real optimal deployment. Hence, it is feasible to put the near-optimal deployment into practice.


## 5. Simulation

Consider 9 agents in a given regionQ (1km×1km). The dynamics of each agent are described by (23), and the density function over this given region is unknown to the agents. Suppose the real density function over Q is described by(43)ϕq,t=1+1000exp⁡-52qx-2Cx2-52qy-2Cy2where q=qx,qyT and Cx, Cy are shown as follows.(44)Cx=Cy=0.1t,0≤t<1.50.15+0.01t,1.5≤t<70.22+0.028t,7≤t<100.5,10≤tFrom (43), we find that the real density function over the mission region is time-varying and the peak of this density function moves along the diagonal from (0,0) to (1,1) with different speeds.The initial sampling period isΔt1(0)=5s and the measurement noise is ξ~N(0,1). The initial covariance matrices in Kalman filter are R(0)=I and Pk(0)=I. In the spatial and temporal correlation function c(·,·), the related parameters are chosen as σr=1, σs=2, and σt=5. The initial value of coefficient w^(0) is random from 1 to 10. On this basis, the numerical results of proposed coverage control system are shown as follows.Figure1 illustrates the coverage behaviors of agents with unknown time-varying density function. The star points and triangle points are the agent positions and the Voronoi centroids, respectively. The dashed lines denote the Voronoi partition, and the estimated density function over this given region is presented by the colorful background in Figure 1. The yellow region denotes the peak area of density function, and the detailed values of every kind of colors are presented by the color bar. As shown in Figure 1(a), the initial deployment of agents is randomly located in the given region, and the estimated density function is far away from the real one. Then, in Figure 1(b), the estimation errors for density function converge to zeros and the agents are almost clustered around the peak region of density function. While proceeding the coverage control, all the agents follow the peak of density function and converge to the optimal deployment in Figure 1(c). Regarding Figures 1(a), 1(b), and 1(c), it is shown that the proposed coverage control law can always drive the agents to follow the optimal deployment with time-varying density function. In addition, from background of Figure 1, we can clearly say that the estimated density function strictly follows the moving of real density function, which verifies the effectiveness of proposed estimation algorithm. More detailed analyses are presented in Figures 2, 3, and 4.Figure 1
The deployment with time-varying density function.
(a)
The initial deployment of agents (b)
The deployment of agents att=2min (c)
The final deployment of agentsFigure 2
The coverage trajectories of agents.Figure 3
The distances from the agents to their centroids.Figure 4
The evolution of the cost function.
(a)
The cost function with regulable sampling mechanism (b)
The cost function with fixed sampling mechanismThe coverage trajectories of all agents are presented in Figure2, where the circle points are the initial positions, the star points denote the agents’ current positions, and the triangle points are the Voronoi centroids. The dashed lines denote the Voronoi partition with the agents’ final positions, and the solid lines are the moving trajectories. In Figure 2, we notice that all the agents move to the lower left corner of the region at the beginning, which is exactly the initial location of the peak of density function. Then, since the peak of density function moves to the center part, the agents are driven to follow the peak such that the regions with higher density can always get more attention from the agents. This result shows that the proposed control strategy can always drive the agents to follow the optimal deployment with time-varying density function.Figure3 describes the evolution of the distances from the agents to their centroids. From this figure, we can find that all the agents converge to their centroids, which indicates that the coverage network reaches the optimal deployment. Note that these distances are sometimes increasing during the coverage procedure. It is because the density function is time-varying and the centroids are closely related to the density function. Hence, the distances between agents and their centroids may be larger when the density function changes its distribution. From another point, this result verifies the advantages of proposed coverage system with time-varying density function.The evolution of cost function is provided in Figure4, where Figure 4(a) shows the cost function with proposed sampling regulation mechanism and Figure 4(b) is the cost function with fixed sampling period. In Figure 4, the blue line is the cost function with estimated density function (He), and the red line denotes the cost function with real density function (Hr). From Figures 4(a) and 4(b), we can find that the cost function with estimated density function strictly follows the cost function with real density function, which also verifies the accuracy and efficiency of our proposed coverage scheme and estimation algorithm. Then, comparing Figure 4(a) with Figure 4(b), we find that the convergence rate of cost function with sampling regulation mechanism is obviously larger than the cost function with fixed sampling period. Moreover, the cost function with fixed sampling period shows some chattering during the coverage procedure in Figure 4(b), because the developed sampling mechanism can adjust the sampling period depending on the trend of time-varying density function. For instance, from (43), the peak of real density function changes slowly in 2min to 7min. Then, we extend the sampling period based on the proposed sampling regulation mechanism during this time. However, the fixed sampling mechanism still takes measurement at 5s each time, which also increases the influences of sampling noise. For the evolution of cost function after 7min, Figure 4(a) shows a faster convergence than the cost function in Figure 4(b), because the coverage network with sampling regulation mechanism is more sensitive to the variation of density function. Therefore, the developed sampling regulation mechanism in coverage control reduces the system’s computational load and improves the efficiency of proposed coverage system.


## 6. Conclusion

In this paper, we study the coverage control problems for a group of agents with unknown and time-varying density function. According to the objective of coverage control, a cost function with a certain metric and density function is provided to describe the performance of coverage network. Then, based on the KF and RBF neural network, a novel estimation algorithm is designed to approximate the time-varying density function with noise corrupted measurements. Moreover, a novel sampling regulation mechanism is developed to improve the estimation performance. Regarding the estimated density function, a coverage control scheme is proposed such that the agents can converge to the optimal deployment from arbitrary initial positions. The stability of proposed coverage control system is strictly demonstrated. Finally, numerical simulations are provided to verify the effectiveness of the proposed approaches.



---

*Source: 6268127-2019-07-03.xml*