1 Introduction

Cooperative unmanned aerial vehicles (UAVs) are known to provide great versatility, resource efficiency, and survivability in various civilian and military applications compared to a single UAV [1,2,3,4]. An UAV swarm has been paid considerable attention by many researchers especially in passive target tracking. This is because an UAV swarm is able to provide enhanced performance even using low-grade sensors and to avoid the observability issue as well. Accordingly, the related studies have been mainly focused on the data fusion architecture and the formation of an UAV swarm which directly affect the overall target tracking performance [5,6,7]. However, since there are difficulties in deriving the performance measure due to the nonlinear filter structure used for passive target tracking, a systematic way to determine the optimal UAV formation still remains as an unsolved problem.

The moving target tracking with a passive sensor has been recognized as one of the representative nonlinear estimation problems. This is because the available passive measurement such as TDOA(time difference of arrival) or AOA(angle of arrival) has a nonlinear relation with the target state variables that should be estimated. Since the random trajectory of a moving target is modeled as a nonstationary or cyclostationary time series, the passive target tracking can be addressed by the nonlinear Kalman filtering for Gauss-Markov random processes [8,9,10,11]. Theoretically speaking, the estimation performance of the Kalman filter is characterized by using a Fisher information matrix (FIM) equivalent to the inverse of error covariance matrix [12, 13]. However, different from the linear one, nonlinear filters often produce biased estimates which cause the performance degradation of target tracking. Therefore, the structure of a target tracking filter is substantial in defining the practical target tracking performance measure.

It is well-known that the performance of a passive target tracking filter using multi-sensor measurements is influenced by the relative geometry between the target and the sensors. This implies that the optimal sensor placement is another significant factor to secure the satisfactory target tracking performance. However, since the error covariance matrix of a nonlinear Kalman filter varies with the target motion, it is hard to derive the necessary and sufficient condition for optimal sensor placement in closed-form [14]. To tackle this issue, most existing methods rely on gradient-based numerical algorithms which require computational burden [15,16,17]. Even worse, if moving platforms equip the sensors and control their formation continuously, the optimization problem will become increasingly complicated. In this circumstance, the numerical techniques would not be adequate for on-line determination of the optimal sensor placement.

Meanwhile, the parameter optimization of the prescribed sensor formation has been attempted [18,19,20]. This scheme assumes that the multiple sensors are placed on a line or circle with equal spacing. In this setting, the target tracking performance measure has just a single unknown parameter, hence the complexity of the sensor formation problem is drastically reduced. This method was usually applied for the limited case where the target is surrounded by multiple sensors. Although the far-field target tracking was sporadically studied, the result may be restrictive in real applications by ignoring the maximum communication range between sensors. Furthermore, the previous schemes could fail to find the global optimum because they omitted the bias estimation errors caused by nonlinear filters in formulating the sensor formation problem.

To overcome the aforementioned limitations, this paper presents an analytic solution to the optimal formation of an UAV swarm providing TDOA measurements for target tracking. In contrast to the existing methods, the estimation error properties of the passive target tracking filter are taken into account. To do this, the passive target tracking problem is settled by using a linear non-conservative robust Kalman filter (NCRKF) [21]. Exploiting the linear filter structure and the strong convergence of NCRKF, the FIM of the passive target tracking filter can be easily derived in closed form. It is also shown that, by taking determinant of the FIM, the object function of the UAV formation problem is simply expressed as a function of two factors; the relative position of the companion UAV with respect to the reference UAV as well as the standard deviations of the TDOA measurement noises. To cope with the time-varying relative geometry between target and UAV swarm, the optimal UAV formation is defined as the max-min solution of the derived objective function. Thus, the proposed analytic solution is able to guarantee the passive target tracking performance even in the worst case. Moreover, our solution is practically meaningful because it is derived by considering the communication range among UAVs which is important in implementing the multi-UAV system. Through the computer simulations with typical passive target tracking scenarios, the validity of methodology is verified.

2 Linear Robust Passive Target Tracking Filter

This section outlines the TDOA-based passive target tracking problem in the setting of linear robust estimation theory. The detailed explanation is given in [21, 22].

Fig. 1
figure 1

Relative geometry of target and UAV swarm

Full size image

Consider the typical engagement geometry illustrated in Fig. 1 involving two-dimensional tracking. In Fig. 1, \((X_{I}, Y_{I})\) are axes of the inertial frame, and the origin of the inertial frame is set as the initial position of the reference UAV. The \(X_{I}\) axis coincides with the initial line-of-sight (LOS) direction from the reference UAV to the target in the horizontal plane. The positions of the target and j-th UAV are \((x_{t}, y_{t})\) and \((x_{j}, y_{j})\), respectively. Hereafter, the subscripts \(j=0\) and \(j={1 \sim N}\) are used to denote the reference UAV and its companions. If the signal propagation speed c is known, the range difference (RD) \(r_{j}\) can be easily calculated from the acquired TDOA \(t_{j}\). In such case, the RD measurement of the j-th UAV with respect to the reference UAV is simply defined as follows:

$$\begin{aligned} r_{j} \triangleq c \cdot t_{j} = d_{t,j} - d_{t,0}, ~~ j=0 \sim N \end{aligned}$$
(1)

where

$$\begin{aligned} d_{t,j} = \sqrt{(x_{t}-x_{0})^{2}+(y_{t}-y_{0})^{2}}. \end{aligned}$$

In the above equation, \(d_{t,j}\) indicates the distance from the j-th UAV to the target.

From the relationship (1), the linear uncertain measurement model can be derived after some tedious algebraic manipulations [21]. This enables the TDOA-based target tracking problem to be dealt with in the setting of linear state estimation.

$$\begin{aligned} \varvec{y}_{k} = H_{k}\varvec{x}_{k} + \varvec{v}_{k} = ({\tilde{H}}_{k} - \varDelta H_{k})\varvec{x}_{k} + \varvec{v}_{k} \end{aligned}$$
(2)

where

$$\begin{aligned} \varvec{x}&\triangleq \begin{bmatrix} x_{t}-x_{0} \\ y_{t}-y_{0} \\ d_{t,0} \\ {\dot{x}}_{t}-{\dot{x}}_{0} \\ {\dot{y}}_{t}-{\dot{y}}_{0} \\ {\dot{d}}_{t,0} \\ \ddot{x}_{t}-\ddot{x}_{0} \\ \ddot{y}_{t}-\ddot{y}_{0} \\ \ddot{d}_{t,0} \end{bmatrix}, ~~ \varvec{y} \triangleq \begin{bmatrix} \vdots \\ y_{j} \\ \vdots \end{bmatrix}, ~~ \varvec{v} \triangleq \begin{bmatrix} \vdots \\ v_{j} \\ \vdots \end{bmatrix}, \\ H&\triangleq \begin{bmatrix} & \vdots ~~~~~ \\ {h}_{j} & {0}^{1 \times 6} \\ & \vdots ~~~~~ \end{bmatrix}\!,~ {\tilde{H}} \triangleq \begin{bmatrix} & \vdots ~~~~~ \\ {\tilde{h}}_{j} & 0^{1 \times 6} \\ & \vdots ~~~~~ \end{bmatrix}\!,~ \varDelta {H} \triangleq \begin{bmatrix} & \vdots ~~~~~ \\ \varDelta {h}_{j} & 0^{1 \times 6} \\ & \vdots ~~~~~ \end{bmatrix}\!, \end{aligned}$$
$$\begin{aligned} y_{j}&\triangleq {\tilde{r}}^2_{j} - ({\tilde{x}}_{j}-{\tilde{x}}_{0})^{2} - ({\tilde{y}}_{j}-{\tilde{y}}_{0})^{2} \\&\qquad + \sigma ^2_{x_{j}} + \sigma ^2_{x_{0}} + \sigma ^2_{y_{j}} + \sigma ^2_{y_{0}} - \sigma ^2_{r_{j}}, \\ h_{j}&\triangleq -2 \begin{bmatrix} (x_{j}-x_{0})&(y_{j}-y_{0})&r_{j} \end{bmatrix}, \\ {\tilde{h}}_{j}&\triangleq -2 \begin{bmatrix} {\tilde{x}}_{j}-{\tilde{x}}_{0}&{\tilde{y}}_{j}-{\tilde{y}}_{0}&{\tilde{r}}_{j} \end{bmatrix}, \\ \varDelta {h}_{j}&\triangleq -2 \begin{bmatrix} \delta {x}_{j,0}&\delta {y}_{j,0}&\delta {r}_{j} \end{bmatrix}, \\ v_{j}&\triangleq \delta x_{j,0}^2 + \delta y_{j,0}^2 -\delta r_{j}^{2} \nonumber \\&\qquad -2({\tilde{x}}_{j,0}\delta x_{j,0} + {\tilde{y}}_{j,0}\delta y_{j,0} - {\tilde{r}}_{j} \delta r_{j}) \nonumber \\&\qquad -\sigma ^2_{r_j} +(\sigma ^2_{x_j} + \sigma ^2_{x_0}) +(\sigma ^2_{y_j} + \sigma ^2_{y_0}). \end{aligned}$$

In the above equation, \({\tilde{\epsilon }}\) and \(\delta \epsilon\) are the noise corrupted measurement of the true variable \(\epsilon\) and the measurement noise with the standard deviation \(\sigma _{\epsilon }\), respectively. The noise statistics of the j-th UAV position and the RD measurement are assumed as follows:

$$\begin{aligned} E \left\{ \begin{bmatrix} \delta x_{j} \\ \delta y_{j} \\ \delta r_{j} \end{bmatrix} \right\} = {{\varvec{0}}}^{3 \times 1}, \! var \left\{ \begin{bmatrix} \delta x_{j} \\ \delta y_{j} \\ \delta r_{j} \end{bmatrix} \right\} = diag(\sigma ^{2}_{x_{j}}, \sigma ^{2}_{y_{j}}, \sigma ^{2}_{r_{j}}) \!. \end{aligned}$$
(3)

The measurement noise \({\varvec{v}}_{k}\) and the stochastic parameter uncertainty \(\varDelta H_{k}\) satisfy the following statistics.

$$\begin{aligned}&R_{k}&\triangleq var\{\varvec{v}_{k}\} = diag([\cdots ~ R_{j} ~ \cdots ]) \end{aligned}$$
(4)
$$\begin{aligned}&W_{k}&\triangleq E\{\varDelta H_{k}^{T} R_{k}^{-1}\varDelta H_{k}\} = \begin{bmatrix} \sum \limits _{j=1}^{N}\frac{ W_{j} }{ R_{j} } & 0^{3 \times 6} \\ 0^{6 \times 3} & 0^{6 \times 6} \end{bmatrix} \end{aligned}$$
(5)
$$\begin{aligned}&V_{k}&\triangleq E\{\varDelta H_{k}^{T} R_{k}^{-1} \varvec{v}_{k}\} = \begin{bmatrix} \sum \limits ^{N}_{j=1}\frac{ V_{j} }{ R_{j} } \\ \varvec{0}^{6\times 1} \end{bmatrix} \end{aligned}$$
(6)

where

$$\begin{aligned} {R}_{j}&\triangleq var\{v_{j}\} = 2(2r_{j}^{2} + \sigma _{r_{j}}^{2})\sigma _{r_{j}}^{2} \\&\quad +2(\sigma _{x_j}^{2} + \sigma _{x_{0}}^{2})(2(x_{j}-x_{0})^{2} + \sigma _{x_j}^{2} + \sigma _{x_0}^{2}) \\&\quad +2(\sigma _{y_j}^{2} + \sigma _{y_{0}}^{2})(2(y_{j}-y_{0})^{2} + \sigma _{y_j}^{2} + \sigma _{y_0}^{2}) \\ {W}_{j}&\triangleq E\{\varDelta h_{j}^{T} \varDelta h_{j}\} = 4 \begin{bmatrix} \sigma ^2_{x_j}+\sigma ^2_{x_0} & 0 & 0 \\ 0 & \sigma ^2_{y_j}+\sigma ^2_{y_0} & 0 \\ 0 & 0 & \sigma ^2_{r_j} \end{bmatrix} \\ V_{j}&\triangleq E\{\varDelta h^{T}_{j} v_{j}\} = 4\begin{bmatrix} (x_{j}-x_{0})(\sigma ^2_{x_j} + \sigma ^2_{x_0}) \\ (y_{j}-y_{0})(\sigma ^2_{y_j} + \sigma ^2_{y_0}) \\ -r_{j} \sigma ^2_{r_{j}} \end{bmatrix} \end{aligned}$$

Without loss of generality, the target dynamics can be described using the standard constant acceleration motion model.

$$\begin{aligned} \varvec{x}_{k+1} = F_{k}\varvec{x}_{k} + \varvec{u}_{k} \end{aligned}$$
(7)

where

$$\begin{aligned} F = \begin{bmatrix} I^{3\times 3} & T\cdot I^{3\times 3} & \frac{1}{2}T^2\cdot I^{3\times 3} \\ 0^{3\times 3} & I^{3\times 3} & T\cdot I^{3\times 3} \\ 0^{3\times 3} & 0^{3\times 3} & I^{3\times 3} \end{bmatrix},~~ \varvec{u} \sim {\mathcal {N}} (0,Q). \end{aligned}$$

In the above equation, T is the sampling period and \(\varvec{u}_{k}\) is the zero-mean white process noise with its variance \(Q_{k}\).

Finally, according to [21], a linear passive target tracking filter is designed by applying the NCRKF theory to the uncertain linear state-space model (2) and (7).

(measurement update)

$$\begin{aligned} {{P}}^{-1}_{k|k}&\!=\! {{P}}^{-1}_{k|k-1} \!+\! {{\tilde{H}}}_{k}^{T}{R}^{-1}_{k}{{{{\tilde{H}}}}}_{k} \!-\! {W}_{k} \end{aligned}$$
(8)
$$\begin{aligned} \hat{\varvec{x}}_{k|k}&\!=\! ({I} \!+\!{{P}}_{k|k}{W}_{k}) \hat{\varvec{x}}_{k|k\!-\!1} \nonumber \\&\qquad +{{P}}_{k|k}{{{{\tilde{H}}}}}^{T}_{k}{R}^{\!-\!1}_{k} (\varvec{y}_{k}\!-\!{{\tilde{H}}}_{k}\hat{\varvec{x}}_{k|k\!-\!1}) \!-\! {{P}}_{k|k}{V}_{k} \end{aligned}$$
(9)

(time update)

$$\begin{aligned} {{P}}_{k+1|k}&= {F}_{k}{{P}}_{k|k}{F}^{T}_{k} +{Q}_{k} \end{aligned}$$
(10)
$$\begin{aligned} \hat{\varvec{x}}_{k+1|k}&= {F}_{k}\hat{\varvec{x}}_{k|k} \end{aligned}$$
(11)

where \(\varvec{x}\) and P are the estimate of the NCRKF and its error covariance matrix.

3 Optimal UAV Formation for TDOA-Based Target Tracking

3.1 Objective Function for Optimal UAV Formation

The ultimate goal of this paper is to determine the optimal UAV formation so that the best tracking performance can be achieved. It is a known fact that the performance of the target tracking filter is proportional to the amount of target information. Therefore, the optimal formation problem reduces the problem of determining the UAV formation, which maximizes the amount of target information. The amount of target information can be represented by FIM or the inverse of the estimation error variance when the given target tracking filter has a linear structure [23]. It implies that the target information is closely related to the filter structure for the passive target tracking problem. Therefore, we obtain the corresponding FIM of the NCRKF based passive target tracking filter and analyze its determinant to indicate tracking performance with respect to the UAV formation. Basic assumptions used for designing the optimal UAV formation are as follows:

A1.:

The passive target tracking using the UAV swarm consists of reference UAV and N companion UAVs.

A2.:

The companion UAVs are placed around the reference UAV with the consideration of the maximum possible communication range \(d_{max}\) as shown in Fig. 1. In the figure, the angular position \(\theta _{j}\) of the j-th companion UAV is defined with respect to the reference LOS which is the direction from the reference UAV to the target. \(\lambda\) is the reference UAV-to-target LOS angle. \(d_{j}\) is the distance between the reference UAV and the j-th companion UAV. It is also assumed that \(d_{max}\) and \(d_{j}\) are not changed and maintained while passive target tracking is performed.

A3.:

The measurement noises of UAV position have the same standard deviations denoted as \(\sigma _{p}\). The standard deviations of the RD measurement noises are also the same.

$$\begin{aligned} \sigma _{p}\triangleq & \sigma _{x_{0}} = \sigma _{y_{0}} = \sigma _{x_{1}} = \sigma _{y_{1}} \cdots \sigma _{x_{N}} = \sigma _{y_{N}}\\ \sigma _{r}\triangleq & \sigma _{r_{1}} = \cdots =\sigma _{r_{N}} \end{aligned}$$
A4.:

The target is sufficiently far away from the UAV swarm maintaining the certain UAV formation. In addition, the target motion is negligible within the short time period.

Based on the above basic assumptions, the target information obtained by the proposed linear passive target tracking filter in Sect. 2 is easily computed. For more detailed derivation procedure, see Appendix A.

$$\begin{aligned} {{{\mathcal {I}}}}_{r,k}({{\varvec{x}}}) \approx k(\bar{{\tilde{H}}}^{T}\bar{{R}}^{-1}\bar{{\tilde{H}}} - \bar{{W}}), \end{aligned}$$
(12)

where

$$\begin{aligned} {\bar{H}} \triangleq \begin{bmatrix} \vdots \\ h_{j} \\ \vdots \end{bmatrix} , ~ \bar{{\tilde{H}}} \triangleq \begin{bmatrix} \vdots \\ {\tilde{h}}_{j} \\ \vdots \end{bmatrix}, ~ {\bar{R}} \triangleq R. \end{aligned}$$

It can be prove that the target information of NCRKF, \({{\mathcal I}}_{r,k}({{\varvec{x}}})\), is the same with that of optimal Kalman filter (OKF), \({{{\mathcal {I}}}}_{o,k}({{\varvec{x}}})\). Extracting the position information from (47) yields

$$\begin{aligned} \begin{array}{rll} \frac{1}{k}{{{\mathcal {I}}}}_{r,k}({{\varvec{x}}}) &\xrightarrow []{a.s.}&\frac{1}{k}{{{\mathcal {I}}}}_{o,k}({\varvec{x}}) \\ &=&\!4\! \begin{bmatrix} \sum \limits ^N_{j=1}\!\frac{(x_{j}-x_{0})^{2}}{\bar{{R}}_j} & \sum \limits ^N_{j=1}\!\frac{(x_{j}-x_{0})(y_{j}-y_{0})}{\bar{{R}}_j} \\ \sum \limits ^N_{j=1}\!\frac{(x_{j}-x_{0})(y_{j}-y_{0})}{\bar{{R}}_j} & \sum \limits ^N_{j=1}\!\frac{(y_{j}-y_{0})^{2}}{\bar{{R}}_j} \end{bmatrix} \end{array} \end{aligned}$$
(13)

where \({\bar{R}}_{j}\) is obtained using (4) and assumption A3.

$$\begin{aligned} {\bar{R}}_{j} = 2\sigma ^2_r(2r^2_j+\sigma ^2_r)+8\sigma ^2_p(d^2_j+2\sigma ^2_p). \end{aligned}$$

Using the assumption A2, the target and UAV positions in Fig. 1 are rewritten as follows:

$$\begin{aligned} (x_{t}, y_{t})&= d_{t,0}( c_{\lambda } , s_{\lambda } ) \end{aligned}$$
(14)
$$\begin{aligned} (x_{j}, y_{j})&= d_{j} ( c_{\theta _{j}+\lambda }, s_{\theta _{j}+\lambda } ) \end{aligned}$$
(15)

where \(c_{\epsilon } \triangleq \cos (\epsilon )\) and \(s_{\epsilon } \triangleq \sin (\epsilon )\), respectively.

Now, let us define the amount of target position information by taking the dedterminant of (13).

$$\begin{aligned} {{\mathcal {L}}}_{p}&\triangleq \big | {{{\mathcal {I}}}}_{o,k}({{\varvec{x}}}) \big | \nonumber \\&= 4 \Bigg [ \sum \limits ^N_{j=1}\frac{(x_{j}-x_{0})^2}{\bar{{R}}_{j}} \sum \limits ^N_{j=1}\frac{(y_{j}-y_{0})^2}{\bar{{R}}_{j}} \nonumber \\&\quad - \bigg (\sum \limits ^N_{j=1} \frac{(x_{j}-x_{0})(y_{j}-y_{0})}{\bar{{R}}_{j}} \bigg )^{2} \Bigg ] \end{aligned}$$
(16)

Provided that the target is sufficiently far away from the UAV swarm and the UAV swarm is guided toward the target, the following approximations (17)\(\sim\)(19) make sense.

$$\begin{aligned}&d_{max} \ll d_{t,0} \end{aligned}$$
(17)
$$\begin{aligned}&(d_{t,0}s_{\lambda } - d_{j}s_{\theta _{j}+\lambda })^{2} \ll (d_{t,0}c_{\lambda } - d_{j}c_{\theta _{j}+\lambda })^{2} \end{aligned}$$
(18)
$$\begin{aligned}&c_{\lambda }\approx 1 , ~ s_{\lambda }\approx 0 \end{aligned}$$
(19)

Thus, the RD information is also approximated by

$$\begin{aligned} r_{j} \approx \sqrt{(d_{t,0}-d_{j}c_{\theta _{j}+\lambda })^{2}} - d_{t,0} \approx -d_{j}c_{\theta _{j}}. \end{aligned}$$
(20)

Substituting (20) and \((x_{j}-x_{0}, y_{j}-y_{0})\approx d_{j}(c_{\theta _{j}}, s_{\theta _{j}})\) into (16), the objective function for UAV formation is defined as

$$\begin{aligned} {{\mathcal {L}}}_p \approx 4 \Bigg [ \sum \limits ^N_{j=1}\frac{c_{\theta _{j}}^{2}}{\bar{{R}}_{j}} \sum \limits ^N_{j=1}\frac{s_{\theta _{j}}^{2}}{\bar{{R}}_{j}} - \bigg (\sum \limits ^{N}_{j=1} \frac{c_{\theta _{j}}s_{\theta _{j}}}{\bar{{R}}_{j}}\bigg )^2 \Bigg ], \end{aligned}$$
(21)

where \(\bar{{R}}_{j}\) is replaced by

$$\begin{aligned} \bar{{R}}_j \approx 2\sigma _{r}^{2}\bigg ( 2c_{\theta _{j}}^{2} + \bigg (\frac{\sigma _r}{d_{j}}\bigg )^{2} \bigg ) + 8\sigma _{p}^{2}\bigg ( 1 + 2\bigg (\frac{\sigma _p}{d_{j}}\bigg )^{2} \bigg ) . \end{aligned}$$

3.2 Optimal Formation of UAV Swarm

From (21), we can confirm that the amount of target information \({{\mathcal {L}}}_{p}\) depends on the relative position (\(\theta _{j}\), \(d_{j}\)) of companion UAVs with respect to the reference UAV, and the standard deviations \((\sigma _{r}, \sigma _{p})\) of measurement noises. \({{\mathcal {L}}}_{p}\) is proportional to \(d_{j}\), and inversely proportional to \((\sigma _{r}, \sigma _{p})\). It means that the enhanced target tracking performance could be achieved as the distance between UAVs becomes larger and/or the sensor measurement is more accurate. However, the intuitive result on \(\theta _{j}\) is difficult to be directly obtained from (21) because there is a somewhat complex nonlinear relationship between \(\theta _{j}\) and \({\mathcal L}_{p}\). At this point, to make the analysis problem tractable, it is noteworthy that the position of the UAV measured by the navigation system is usually very accurate \((\sigma _{p} \ll 1)\). Then, \(\bar{{R}}_{j}\) in (21) is again approximated as follows:

$$\begin{aligned} \bar{{R}}_{j} \approx 2\sigma _{r}^{2} \Bigg ( 2c_{\theta _{j}}^{2} + \bigg (\frac{\sigma _{r}}{d_{j}}\bigg )^{2} \Bigg ). \end{aligned}$$
(22)

Meanwhile, if the target moves at high speed, the target LOS angle \(\lambda\) is rapidly changed. The variation of the LOS angle has a critical effect on the UAV formation because \(\theta _{j}\) is determined with respect to the LOS direction as described in Fig. 1. Therefore, even while the UAVs are placed to maximize the amount of target information, they may not give a good tracking performance throughout the entire tracking period. To overcome the above limitation, it is desirable to find the UAV formation which maximize the amount of target information in the worst case. This leads to the following max-min problem.

$$\begin{aligned} \max \min _{\theta } {{\mathcal {L}}}_{p} \end{aligned}$$
(23)

where \({{\mathcal {L}}}_{p}\) is redefined by inserting (22) into (21).

$$\begin{aligned} {{\mathcal {L}}}_{p}&\approx 4 \Bigg [ \sum \limits _{j=1}^{N} \frac{c_{\theta _{j}}^{2}}{2\sigma _{r}^{2}\big (2c_{\theta _{j}}^{2}+(\frac{\sigma _{r}}{d_{j}})^{2}\big )} \sum \limits ^N_{j=1} \frac{s_{\theta _{j}}^{2}}{2\sigma _{r}^{2}\big (2c_{\theta _{j}}^{2}+(\frac{\sigma _{r}}{d_{j}})^{2}\big )} \nonumber \\&\quad - \bigg (\sum \limits _{j=1}^{N} \frac{c_{\theta _{j}}s_{\theta _{j}}}{2\sigma _{r}^{2}\big (2c_{\theta _{j}}^{2} + (\frac{\sigma _{r}}{d_{j}})^{2}\big )} \bigg )^{2} \Bigg ] \end{aligned}$$
(24)

A solution to this problem is given according to the following two cases. The cases are divided by the relationship between \(\theta _{j}\) and (\(\sigma _{r}\), \(d_{j}\)).

Case 1. \(|c_{\theta _{j}}| \gg {\sigma _{r}}/{d_{j}}\)

The amount of target information \({{\mathcal {L}}}_{p}\) is approximated and then rearranged as follows:

$$\begin{aligned} {{\mathcal {L}}}_{p}&\approx 4 \Bigg [ \sum ^{N}_{j=1}\frac{c_{\theta _{j}}^{2}}{4\sigma _{r}^{2}c_{\theta _{j}}^{2}} \sum ^{N}_{j=1}\frac{s_{\theta _{j}}^{2}}{4\sigma _{r}^{2}c_{\theta _{j}}^{2}} - \bigg ( \sum ^{N}_{j=1}\frac{c_{\theta _{j}}s_{\theta _{j}}}{4\sigma _{r}^{2}c_{\theta _{j}}^{2}} \bigg )^{2} \Bigg ] \nonumber \\&= \frac{ N^2 }{ 4\sigma ^{4}_{r} } \Bigg [ \frac{1}{N} \sum ^{N}_{j=1} t_{\theta _{j}}^{2} - \bigg ( \frac{1}{N}\sum ^{N}_{j=1}t_{\theta _{j}}^{2} \bigg )^{2} \Bigg ] \end{aligned}$$
(25)

where \(t_{\epsilon } \triangleq \tan (\epsilon )\).

From (25), we can conclude that \({{\mathcal {L}}}_{p}\) increases when the number of UAVs N is large, and the standard deviation of RD measurement noise \(\sigma _{r}\) is small. In addition, the term in parenthesis of (25) can be interpreted as the variance of \(t_{\theta _{j}}\), \(j=1,...,N\). Thus, this indicates that \({{\mathcal {L}}}_{p}\) also increases as the variance \(t_{\theta _{j}}\) becomes larger. In order to obtain the minimum value of \({{\mathcal {L}}}_{p}\), the stationary point of \({\mathcal L}_{p}\) and its minimization condition are given by (26) and (27), respectively.

$$\begin{aligned} \frac{\partial {{\mathcal {L}}}_{p}}{\partial t_{\theta _{N}}}&= \frac{N^{2}}{4\sigma _{r}^{4}}\! \Bigg [ \frac{2}{N}t_{\theta _{N}} - \frac{2}{N^{2}}\sum _{j=1}^{N}t_{\theta _{j}} \Bigg ] = 0 \nonumber \\&\quad \rightarrow t_{\theta _{N}} = \frac{1}{N-1}\sum ^{N-1}_{j=1}t_{\theta _{j}} \end{aligned}$$
(26)
$$\begin{aligned} \frac{\partial ^{2} {{\mathcal {L}}}_{p}}{\partial t_{\theta _{N}}^{2}} = 2 - \frac{2}{N}> 0 \rightarrow N > 1 \end{aligned}$$
(27)

As a well-known fact, since the UAV swarm-based passive target tracking problem needs at least 3 companion UAVs (\(N\ge 3\)), the minimization condition of (27) is always satisfied. Therefore, the minimizing solution of \({{\mathcal {L}}}_{p}\) is to become \(t_{\theta _{N}}=\frac{1}{N-1} \sum _{j=1}^{N-1}t_{\theta _{j}}\) defined in (26). By inserting (26) into (25), the minimum value of \({{\mathcal {L}}}_{p}\) is obtained

$$\begin{aligned} {{\mathcal {L}}}_{p}^{*} = \frac{N(N-1)}{4\sigma _{r}^{4}} \Bigg [ \frac{1}{N-1}\sum \limits ^{N-1}_{j=1}t_{\theta _{j}}^{2} - \bigg ( \frac{1}{N-1}\sum \limits ^{N-1}_{j=1}t_{\theta _{j}} \bigg )^{2} \Bigg ] \end{aligned}$$
(28)

Now, the condition for maximizing the minimum value \({\mathcal L}_{p}^{*}\) is obtained according to whether the number of UAVs N is an odd or even number.

1) N is an odd number

If the companion UAVs are placed symmetrically with respect to the target LOS direction, there exist the formation angle pairs \((\theta _{i},\theta _{j})\) with the different sign and same value where \(j=i+1\), \(\forall i,j\). In this case, because the number of UAVs N is an odd number, the second term on the right-hand side of (28) is always satisfies with \(\frac{1}{N-1}\sum _{j=1}^{N-1}t_{\theta _{j}} = 0\) irrespective of the formation angle pairs. At this time, the formation angle of the Nth companion UAV becomes \(\theta _N=0^\circ\) from (26). By the characteristics of tangent function, the first term on the right-hand side of (28) has the maximum value of the symmetry formation angle with \(|\theta _{j} |=90^\circ\). Therefore, the maximizing solution of \({{\mathcal {L}}}_{p}^{*}\) is as follows:

$$\begin{aligned} \theta _N = 0^\circ ~~&{\textit{and}}~~ \theta _i=90^\circ ~~ (i=1,3,\cdots ,N-2) \nonumber \\&{\textit{and}}~~ \theta _{j} = - \theta _{i} ~~ (i=2,4,\cdots ,N-1) \end{aligned}$$
(29)

2) N is an even number

In this case, \({{\mathcal {L}}}_{p}^{*}\) is rearranged as follows:

$$\begin{aligned} {{\mathcal {L}}}_{p}^{*} \approx \frac{N(N-1)}{4\sigma _{r}^{4}} \Bigg [ \frac{1}{N-1}\sum \limits ^{N-2}_{j=1}t_{\theta _{j}}^{2} + \frac{N}{(N-1)^2} t_{\theta _{N-1}}^{2} \Bigg ] \end{aligned}$$
(30)

Again, considering the situation of the formation angle pairs \((\theta _{i},\theta _{j})\) with the different sign and same value where \(j=i+1\), \(\forall i,j\), from the above equation, it can be deduced that \({{\mathcal {L}}}_{p}^{*}\) is maximized when \(|\theta _j|=90^\circ\) (\(j=1,\cdots ,N-1\)). This indicates \(|\theta _N |\approx 90^\circ\) by (26). Therefore, the maximizing solution of \({{\mathcal {L}}}_{p}^{*}\) can be defined by

$$\begin{aligned} \theta _{i}&= 90^\circ ~~ (i=1,3,\cdots ,N-1) \nonumber \\ {\textit{and}} ~~ \theta _{j}&= - \theta _i ~~ (j=2,4,\cdots ,N). \end{aligned}$$
(31)

Case 2. \(|c_{\theta _{j}}| \ll {\sigma _{r}}/{d_{j}}\)

In a similar way with Case 1, \({{\mathcal {L}}}_p\) can be approximated by applying the assumption \(|c_{\theta _{j}}| \ll {\sigma _{r}}/{d_{j}}\) to (24).

$$\begin{aligned} {{\mathcal {L}}}_{p} \approx \frac{1}{\sigma _{r}^{8}} \Bigg [ \sum \limits ^{N-1}_{j=1}d^{2}_{j}c_{\theta _{j}}^{2} \sum \limits ^{N-1}_{j=1}d^{2}_{j}s_{\theta _{j}}^{2} - \bigg ( \sum \limits ^{N-1}_{j=1}d_{j}^{2} s_{\theta _{j}} c_{\theta _{j}}\bigg )^{2} \Bigg ]\! \end{aligned}$$
(32)

The above equation is rearranged for convenience of the analysis.

$$\begin{aligned} {{\mathcal {L}}}_p&\approx \frac{1}{\sigma ^{8}_{r}} \Bigg [ \sum \limits ^{N-1}_{i=1}\sum \limits ^{N-1}_{j=1} d_{i}^{2}c_{\theta _{i}}^{2}\cdot d_{j}^{2}s_{\theta _{j}}^{2} \nonumber \\&~~~~~~-\sum \limits ^{N-1}_{i=1}\sum \limits ^{N-1}_{j=1} (d_{i}c_{\theta _{i}}d_{j}s_{\theta _{j}}) (d_{j}c_{\theta _{j}}d_{i}s_{\theta _{i}}) \Bigg ] \nonumber \\&= \frac{1}{\sigma _{r}^{8}} \sum \limits ^{N-1}_{i=1}\sum \limits ^{N-1}_{j=1} d_{i}c_{\theta _{i}}d_{j}s_{\theta _{j}} (d_{i}c_{\theta _i}d_{j}s_{\theta _{j}} -d_{i}s_{\theta _i}d_{j}c_{\theta _{j}}) \end{aligned}$$
(33)
Fig. 2
figure 2

Amount of target information

Full size image

In (33), letting \(p_{ij}\triangleq d_{i}c_{\theta _{i}} d_{j}s_{\theta _{j}}(d_{i}c_{\theta _{i}}d_{j}s_{\theta _{j}}-d_{i}s_{\theta _{i}}d_{j}c_{\theta _{j}})\), then \({{\mathcal {L}}}_p\) can be regarded as the sum of all matrix element \(p_{ij}\). Thus, using the fact that \(p_{ij} = 0\) where \(i=j\) and \(p_{ij} + p_{ji} = (d_{i}c_{\theta _{i}}d_{j}s_{\theta _{j}}-d_{i}s_{\theta _{i}}d_{j}c_{\theta _{j}})^{2}\), the following equation is simply obtained.

$$\begin{aligned} {{\mathcal {L}}}_{p}&\approx \frac{1}{\sigma _{r}^{8}}\sum \limits _{i=1}^{N-1}\sum \limits _{j=1}^{N-1} ( d_{i} c_{\theta _{i}} d_{j} s_{\theta _{j}} - d_{i} s_{\theta _{i}} d_{j} c_{\theta _{j}} )^{2} \nonumber \\&= \frac{1}{\sigma ^8_r} \sum \limits ^{N-1}_{i=1}\sum \limits ^{N-1}_{j=1} d^2_i d^2_j s_{\theta _{j} - \theta _{i}}^{2} \end{aligned}$$
(34)

At this point, the minimum amount of target information \({\mathcal L}_{p}^{*}\) becomes 0 in the following condition.

$$\begin{aligned} \theta _{i} = \theta _{j} ~~ \textit{or} ~~ \theta _{i} = \theta _{j} \pm 180^\circ \end{aligned}$$
(35)

From the result, we can understand that in the presence of considerable measurement noises, that is, \(|c_{\theta _{j}}| \ll \sigma _{r}/d_{j}\), the UAV formation has a negligible effect on the target tracking performance. Thus it does not mean much to the problem.

Fig. 3
figure 3

Engagement scenario

Full size image

Remark 1

The proposed scheme provides more general solution to the UAV formation problem than the existing methods because it considers practical views such as the measurement noise, the maximum communication range between UAVs, and the time-varying target motion. From (25), it is obvious that the amount of target information becomes larger as the number of UAVs increases or the measurement noise variance decreases. This conclusion accords with the previous approaches to the analysis of optimal UAV formation [15,16,17]. However, if the number of UAVs and the measurement noise properties are fixed, the amount of target information varies with the UAV formation. Unlike the previous results, (25) tells us that the optimal UAV formation maximizes the variance with respect to the formation angle \(\theta _j\). This analysis result implies that the good target tracking performance can be obtained by making the angular positions of the UAVs perpendicular to the target LOS direction and far away from it as much as possible.

Table 1 Simulation condition
Full size table

Remark 2

In the UAV swarm-based target tracking problem, UAVs are generally assumed to be distributed evenly along a uniform circle so that the formation angle of j-th companion UAV is \(2{\pi }j/N\) and with the reference UAV at the origin, according to a natural intuition in optimal UAV configuration. This is one of the most widely used formations in the existing researches [18, 24]. However, these methods are developed considering stationary target and UAVs; thus, it is not suitable for moving target scenario. As shown in Fig. 2, it is obvious that the conventional uniform formation expose their limitations in ensuring the enough amount of target information necessary to improve the target tracking performance.

4 Simulation Results

Fig. 4
figure 4

Error mean of target estimate: position

Full size image
Fig. 5
figure 5

Standard deviation of target estimate: position

Full size image

Computer simulations are carried out to validate the presented UAV formation algorithm. The performance of target tracking according to UAV formation is considered. The simulation parameters and conditions are summarized in Table 1. The target tracking is performed using TDOA information obtained from the UAV swarm, maintaining a particular UAV formation. At this time, it is assumed that the position and velocity of each UAV are individually given from its navigation sensor. It is also assumed that the target moves with constant velocity with a specific direction, where the reference and the three companion UAVs are guided towards the target. The trajectories of the target and the UAV swarm are shown in Fig. 3. For the given engagement scenario, the simulation results are obtained from 200 Monte Carlo trials.

The proposed UAV formation algorithm is compared with one of the most widely used formations, described in Remark 2. We have applied three types of tracking filters to the addressed problem by adopting optimal KF(OKF), extended Kalman filter (EKF) and presented NCRKF based tracking filter. The OKF is used to predict the performance bound but is not implementable because it uses the unavailable measurement matrix H in (2). On the other hand, the EKF is known as one of the most commonly used techniques for the non-linear passive target tracking approach.

Fig. 6
figure 6

Error mean of target estimate: velocity

Full size image
Fig. 7
figure 7

Standard deviation of target estimate: velocity

Full size image

Figures 4, 5, 6 and 7 show the error means and the corresponding standard deviations of target position and velocity estimates. From the simulation result, the proposed NCRKF shows a fast convergence property, whereas the EKF does not due to its inherent non-linearity. In addition, it can be seen that the proposed formation in Fig. 3b tends to decrease the standard deviation of estimation error faster than the previous uniform formation shown in Fig. 3a. This implies that the proposed UAV swarm formation is a better selection from the viewpoint of target tracking performance, which is consistent with the results of the optimal formation analysis performed in Sect. 3.2.

In order to clearly show the effect of the UAV formation on the tracking performance, the normalized root mean squares errors (NRMSEs) of the position and velocity estimates are shown in Figs. 8 and 9. The NRMSE is calculated as follows:

$$\begin{aligned} {{\bar{E}}}_{j} = \frac{1}{D_{j}} \sqrt{ \frac{1}{N} \sum _{k=1}^{N}{ {{\tilde{d}}}_{j}^{2}(k) } } \end{aligned}$$
(36)

where N is the number of Monte-Carlo trials, \({\tilde{d}}_{j}\) is the position or velocity estimation error. Letting \(\hat{\varvec{\xi }}\) be the estimate of the true vector \(\varvec{\xi }\), then \(\tilde{{{d}}}_{j}=(\hat{\varvec{\xi }}-\varvec{\xi })^{T}(\hat{\varvec{\xi }}-\varvec{\xi })\). \(D_{j}\) is the normalized constant which is defined as the standard deviation of the estimation error \(\hat{\varvec{\xi }}-\varvec{\xi }\). It is chosen as the maximum value of the estimation error standard deviations obtained by using two different UAV formations is used for \(D_{j}\).

From the NRMSEs of position and velocity as Figs. 8 and 9, the proposed formation provides more consistent estimation performance than the previous formation regardless of filter structrues. This result corresponds to the fact mentioned in Remark 2. Consequently, the proposed formation algorithm is expected to be used as an attractive solution for guaranteeing the excellent performance of the passive target tracking based on the UAV swarm.

5 Conclusions

A novel UAV formation algorithm has been proposed for the passive target tracking using TDOA information measured by the UAV swarm. To make the UAV formation problem tractable, the non-conservative robust Kalman filter was used for passive target tracking. Exploiting its linear filter structure and estimation error properties, the UAV formation target information was derived in closed-form. It was shown that the proposed UAV formation maximizing the worst-case target information provides more reliable passive target tracking performance than the conventional uniform formation. Moreover, the proposed approach enables practical constraints overlooked in most existing methods, such as the maximum possible communication range between UAVs to determine the UAV formation. Through the computer simulation, it has been demonstrated that the proposed UAV formation technique provides exceptional tracking performance.