Finite time coverage tracking algorithm of maneuvering target by multiple mobile agents

Abstract

In this paper, a problem regarding how multiple mobile agents track a high-speed maneuvering target is considered. Due to the uncertainties of the target caused by the background noises, we use a dynamic non-uniform region to describe the location of target. Therefore, the cooperative tracking problem is transformed into a problem to cover a known dynamic non-uniform region. In order to capture the high-speed maneuvering target, the mobile agents with global sensing areas and limited actuation region are designed to track and cover the dynamic region. Also, the probability that the target appear in the circle is denoted by a probability density function and a performance index function is given to describe the effectiveness of covering a moving target. With observer-based estimation and dynamic formation control, a coverage tracking algorithm is proposed so that the group of agents catch the target by a coverage tracking policy in finite time.

Keywords

Coverage tracking control finite time maneuvering target multiple mobile agents

Introduction

Recently, more and more researchers devote themselves to the coverage problem of multi-agent systems. Coverage problem is an important topic of sensor network (Cardei and Wu, 2006) or multi-robot network (Choset, 2001). The problem requires a group of individuals with perceptual, communication, computing, and mobile capabilities to perform specific tasks in a certain area, such as rescue (Miah et al., 2015), hunt (Leonard and Olshevsky, 2013), environmental monitoring (Zuo et al., 2014), deep sea detection (Wang and Hussein, 2007), and so on. Coverage problems can be classified as region coverage (Gusrialdi et al., 2009; Liu et al., 2006; Savkin et al., 2015), boundary coverage (Gupta et al., 2015; Luo, 2012; Nasimov and Matveev, 2015) and target coverage (Bikramaditya et al., 2016; Sun, 2015).

The region coverage problem have drawn much attention to the researchers in recent years. In Cortes et al. (2002), the authors introduced the location cost function as an index to optimise sensor locations, in which a low value of it corresponds to good coverage and a high value of it corresponds to poor coverage. Furthermore, the index has well defined minima corresponding to optimal coverage configurations that are centroid of Voronoi cells in the partition (Arslan and Koditschek, 2016; Du et al.,1999). In Hussein and Stipanovic (2007), the authors developed closed-loop control strategies such that each point of a given compact region in a plane can be sampled by some agents in the network by an amount of effective coverage equal to a given value. The boundary coverage is different from the area coverage, and it only requires cover all or part of the boundary of the region of interested. In Wang and Wu (2012), the authors considered the problem of optimal coverage of unknown environmental boundary using sensor networks. The algorithm was constructed with the help of homogeneity with dilation from finite-time stability as that in Wang and Hong (2008).

However, in some specific application, people are only interested in covering or enclosing where the target appears. Its core idea is to cover the region where dynamic target may appear. Also, the region is not given in advance, but changes with the target movement and uncertain information of the target. The region coverage problem needs to ensure that the uncertainty target region can be adequately covered and fully monitored. The implication is that the agents must not only track the target area at all times, but also effectively cover the target area. In Wang et al. (2009) and Wang and Wu (2012), a control law is designed for each agent to guarantee that the actuation region, in which the probability of real target appear is uniform, is covered after a period of time. However, in application, the probability of real target appear in the actuation region is non-uniform. The higher probability means that the higher probability of real target appear in one point of the actuation region.

In this paper, we consider the problem of tracking a moving target. Since the target uncertainties of the target caused by the background noises and the measurement disturbances, only the region where dynamic target may appear can be obtained. Thus, the target tracking problem can be viewed as a moving region coverage problem. Also, the possibility of the target appearing somewhere of the moving region is described by a probability density function. Finite time formation algorithms is given to perform this coverage mission. The idea of using the finite time formation algorithms to solve a coverage problem with time-varying probability density function is novel.

This article is organized as follows. In Section 2, the preliminaries and the formulation of the finite-time coverage problem is presented. The main results on the target estimation is shown in Section 3. Also, moving region coverage problem is transformed as a dynamic formation problem and the finite dynamic formation control law is obtained in Section 4. The finite control law is developed in Section 5. The numerical example illustrating the effectiveness of the proposed algorithm appears in Section 6.

Preliminaries and problem formulation

In this section, first, the graph theory is given to describe the communication topology in multi-agent networks. Then the finite time coverage tracking problem is formulated.

Preliminaries

To describe the communication topology in multi-agent networks, graph theory is useful. An undirected graph $G = {V, E}$ consists of a finite vertex set $V = {1, 2, \dots, n}$ and an edge set $E$ . An edge $(i, j) \in E$ denotes that vertex $i, j$ can obtain each other’s information, and this means $i$ and $j$ are neighbors. A path of length $r$ from a vertex $i_{1}$ to a vertex $i_{r + 1}$ is a sequence of $r + 1$ distinct vertices $i_{1}, \dots, i_{r} + 1$ such that $(i_{q}, i_{q + 1}) \in E$ for $q = 1, \dots, r$ . If there is a path between any two vertices of an undirected graph $G$ , then the graph is connected.

The weighted adjacency matrix of $G$ is denoted by $A = [a_{ij}] \in R^{n \times n}$ , where $a_{ii} = 0, a_{ij} > 0$ if $(j, i) \in E$ and $a_{ij} = 0$ otherwise. The degree matrix of $G$ is $D = diag {d_{1}, \dots, d_{n}} \in R^{n \times n}$ , where $d_{i} = \sum_{j = 1}^{n} a_{ij}$ for, and the Laplacian of $G$ is defined as

L = A - D

The following result is well-known in algebraic graph theory by denoting the eigenvalues of Laplacian $L$ associated with $G$ with $n$ agents by $λ_{1} (L), \dots, λ_{n} (L)$ satisfying

λ_{1} (L) \leq, \dots, \leq λ_{n} (L)

Lemma 1: (Wang, 2009) $λ_{1} (L) = 0$ and $1_{n} = [1, 1, \dots, 1]^{T} \in R^{n}$ is its eigenvector, and $λ_{2} (L) > 0$ if and only if the graph G is connected.

Problem formulation

In this section, we formulate our coverage tracking problem. In our problem, we consider N agents with sensors to track down a maneuvering target. The maneuvering target is expressed as follows

{\begin{matrix} \overset{\cdot}{x} = v \\ \overset{\cdot}{v} = E x + D v + F ϰ \end{matrix}

(1)

with initial conditions $x (0) = x_{0}$ , $v_{t} (0) = v_{0}$ , where $x (t) \in R^{2}$ denotes the position, $v_{t} (t) \in R^{2}$ denotes the velocity, $E, D, F$ are known matrices and the disturbance $ϰ$ is an uncertain bounded function. The dynamics of agent $i (i = 1, . . ., N)$ is described by

{\begin{matrix} {\overset{\cdot}{p}}_{i} = v_{i} \\ {\overset{\cdot}{v}}_{i} = u_{i} \end{matrix}

(2)

where $p_{i} \in R^{2}$ is the position of $i -$ th agent, $v_{i}$ is the velocity of the $i -$ th agent, and $u_{i} \in R^{2}$ is the control input.

For simplicity, we assume that each agent is equipped with one sensor and the sensing range of each agent is infinity, and therefore, the agents have a global view. Only if objective function, which describes the sensing performance of the moving target, gets its optimal value, then we say the target is tracked down (or caught) by the agent. The objective function is developed in ‘Coverage problem transform’.

In this paper, we consider a coverage tracking problem of multi-agent systems; The finite-time coverage tracking is completed if the coverage tracking can be achieved as $t \geq T_{f}$ with a finite settling time $T_{f} > 0$ . To do the job, the agents first collaborate to estimate the states of the target by a cooperative observer because some variables of the target may not be measured and each sensor may only get partially-observable measurements. Then, based on the online estimation, the agents track the target by coverage.

Cooperative observer design

In this section, we estimate a moving target by a group of the sensor measurements of the networked mobile agents since one sensor may not work

Set

A = (\begin{matrix} 0 & I_{n} \\ E & D \end{matrix}), B = (\begin{matrix} 0 \\ F \end{matrix}), q (t) = (\begin{matrix} x (t) \\ v_{t} (t) \end{matrix})

Then the target dynamics (1) can be expressed as

\overset{\cdot}{q} = A_{q} + B_{ϰ}

(3)

The measurement of the target by agent $i (i = 1, . . ., N)$ is

y_{i} = (C_{i 1}, C_{i 2}) (\begin{matrix} x (t) \\ v_{t} (t) \end{matrix}) + ω_{i} = C_{i} q + ω_{i}

(4)

where disturbance $ω_{i} \in R^{2}$ is a measurable bounded and differentiable function with ${\overset{\cdot}{ω}}_{i}$ , also bounded. Note that a single agent can only get at most partial information of the target states, so all agents have to collaborate to get enough measured information for the target estimation. Therefore, the whole system can be expressed as

{\begin{matrix} \overset{\cdot}{p} = v \\ \overset{\cdot}{v} = u \end{matrix}

(5)

{\begin{matrix} \overset{\cdot}{q} = A q + B ϰ \\ y = C q + ω \end{matrix}

(6)

where

\begin{matrix} p = (p_{1}, \dots, p_{N}), v = (v_{1}, \dots, v_{N}), y = (y_{1}, \dots, y_{N}), \\ u = (u_{1}, \dots, u_{N}), \end{matrix}

\begin{matrix} ω = (ω_{1}, \dots, ω_{N}), C_{1} = (C_{11}, \dots, C_{N 1}), \\ C_{2} = (C_{12}, \dots, C_{N 2}), C = (C_{1}, C_{2}), \end{matrix}

Assuming that the boundary of $ϰ, ω$ are measurable, i.e. $∥ (ϰ, ω)^{T} ∥ \leq \bar{δ}$ .

Remark 1: In real applications, $ϰ, ω$ cannot be measurable directly. However, $ϰ, ω$ are bounded function. Then, we can assume that $∥ (ϰ, ω)^{T} ∥ \leq \bar{δ}$ . It supports the proof of Lemma 2.

If $(A, C)$ is observable, then there exists a matrix $H = (\begin{matrix} H_{x} \\ H_{y} \end{matrix})$ such that

A - H C = (\begin{matrix} 0 & I_{n} \\ E & D \end{matrix}) - (\begin{matrix} H_{x} \\ H_{y} \end{matrix}) (C_{1}, C_{2})

(7)

is Hurwitz.

Here, a linear observer is built in order to estimate the target based on the measurement given by all the agents. Denote $\hat{x}$ as the position estimation of the moving target, $\hat{v}$ as its velocity estimation, and $\hat{q} = (\hat{x}, {\hat{v}}_{t})^{T}$ . The estimation laws of $\hat{x}$ and ${\hat{v}}_{t}$ are proposed as

\overset{\cdot}{\hat{q}} = A \hat{q} + H C (q - \hat{q}) + H ω

(8)

Note that the observer is based on one agent, but the $N$ agents, which can be called a cooperative observer.

Setting $e_{x} = x - \hat{x}, e_{v} = v_{t} - {\hat{v}}_{t}, e = (e_{x}, e_{v})^{T}$ , the error dynamics is rewritten as

\overset{\cdot}{e} = (A - H C) e + B ϰ - H ω

(9)

The following result is the convergence analysis about the error dynamics (9).

Lemma 2: (Wang, 2009) If $(A, C)$ is observable, then the error system (9) is input-to-state stable with $(ω, ϰ)$ as its input, where gain matrix $H$ satisfies (7) is Hurwitz.

Lemma 3: (Wang, 2009) By the ISS inequality, we can have

e (t) \leq L

where

L = ε + \sqrt{\frac{λ_{max} (P)}{λ_{min}}} \frac{2 ∥ (- P H, P B) ∥}{λ_{min} (Q) θ}

(10)

$P, Q$ are positive definite and

(A - H C)^{T} P + P (A - H C) + Q = 0 .

(11)

Algorithm design of tracking coverage

In this section, the tracking coverage problem is transformed as a dynamic formation problem, and a dynamic formation control law is designed and the proofs of the stability are given by Lyapunov function.

Coverage problem transform

Based on the cooperative observer given in the last section, the agents get the estimation $\hat{x} (t)$ of $x (t)$ . Denote $C (t)$ as the estimation circle of $x (t) \in R^{n}$ (as the circle center) with radius $L$ due to (10).

Define $φ (x), x \in C (t)$ a probability density function describing a possibility that the real target appear in $C (t)$ . The probability density function $φ (x)$ is nonnegative everywhere, and its integral over the entire space is equal to one, that is, $φ (x)$ satisfies $φ (x) \geq 0, \forall x \in C (t)$ and $\int_{C (t)} φ (x) dx = 1$ .

Remark 2: The density function $φ (x), x \in C (t)$ is used to describe the probability, and the higher probability means that the higher probability of real target appear in one point of $C (t)$ . The cooperative observer in Section 3 only can obtain the estimated region of the target appear, which does not describe the probability of the real target appear in $C (t)$ .

To capture the target $x (t)$ , we design the control strategy for the agents to cover the estimation region $C (t)$ and make the objective function optimal.

The map $P_{C} : p \to C (t)$ is called the projection onto $C (t)$ . Also, $P_{C}$ satisfies the follow properties

∥ P_{C} (p_{i}) - P_{C} (p_{j}) ∥ = ∥ p_{i} - p_{j} ∥, i, j = 1, 2, \dots, N,

(12)

∥ P_{C} (p_{i}) - p_{i} ∥ = ∥ P_{C} (p_{j}) - p_{j} ∥, i, j = 1, 2, \dots, N,

(13)

P_{C} (p_{i}) \in C (t), i, j = 1, 2, \dots, N,

(14)

(13) means that the distance between the position of each agent and its projection of its position for any two agents is equal. (14) means that the rejection of position of each agent is in $C (t)$ . Let $P_{C} (p) = {P_{C} (p_{1}), \dots, P_{C} (p_{N})}$ be the decentralise the virtual structure of $p = {p_{1}, \dots, p_{N}}$ , shown as Figure 1. Because of noise and loss of resolution, the sensing performance at point $x \in C (t)$ taken from $i -$ th sensor at the position $P_{C} (p_{i})$ degrades with the distance $∥ x - P_{C} (p_{i}) ∥$ between $x$ and $P_{C} (p_{i})$ ; we describe this degradation with a non-decreasing differentiable function $f : R_{+} \to R_{+}$ . Accordingly, $f (∥ x - P_{C} (p_{i}) ∥)$ provides a quantitative assessment of how poor the sensing performance is.

Figure 1.

The virtual structure of $i$ th agent.

It is assumed that the sensing cost function of each agent is given as follows

f (∥ x - P_{C} (p_{i}) ∥) = ∥ x - P_{C} (p_{i}) ∥^{2}

(15)

which is to develop a proper deployment algorithm such that the following coverage performance function is minimized

H (P_{C} (p)) = \int_{C} min_{i \in {1, 2, \dots, N}} ∥ x - P_{C} (p_{i}) ∥^{2} φ (x) dx

(16)

Qualitatively, a low value of $H$ corresponds to a good configuration for coverage of the environment. Let $C (t) = {C_{1} (t), \dots, C_{N} (t)}$ be the Voronoi partition of $C (t)$ for all ${{\tilde{p}}_{1}, \dots, {\tilde{p}}_{N}}$ shown as follows

C_{i} (t) = {x \in C | ∥ x - P_{C} (p_{i}) ∥ \leq ∥ x - P_{C} (p_{j}) ∥, \forall i \neq j}

Using these partitions, the cost function can be rewritten as

H (P_{C} (p)) = \sum_{i = 1}^{N} \int_{C_{i}} ∥ x - P_{C} (p_{i}) ∥^{2} φ (x) dx

(17)

The mass, and centroid of a Voronoi region $C_{i}$ are defined as [2]

M_{C_{i}} = \int_{C_{i}} φ (x) dx, C_{C_{i}} = \frac{1}{M_{C_{i}}} \int_{C_{i}} x φ (x) dx

(18)

A agent network is said to be in an optimal coverage configuration if each agent is positioned at the centroid of its Voronoi region, that is, if the control law $u_{i}$ can drive the agent $p_{i}$ to the centroid $C_{C_{i}}$ , the objective $H$ will have the minimum value. Next, we will give the design of control $u_{i}$ .

Let ${C_{C_{1}}, \dots, C_{C_{N}}}$ denote the desired position. The position of $i$ th agent can be represented as shown in Figure 2. In Figure 2, $r_{i}$ denotes the position vector of agent $i$ on coordinate system $OXY$ , It is easy to find that $r_{i} = (x_{i}, y_{i})^{T} = p_{i}$ denotes the position vector of agent $i$ on coordinate system $OXY$ , and then we can known that $r_{i}$ and $v_{i}$ can be measured directly. $r_{i}^{*}$ denotes the position vector of the centroid of Voronoi region $C_{i}$ , and ${\hat{r}}_{i}$ denotes a vector from the $i -$ th agent to the center of Voronoi region $C_{i}$ .

Figure 2.

The position of $i$ th agent.

In fact, our idea is to transform the tracking coverage problem to a dynamic formation problem, which is also a path planning problem (Liu, Yang and Zhang (2018); Liu et al., 2018). Our aim is to design control law $u_{i}, i = 1, \dots, N$ to drive agent $p_{i}$ to $C_{C_{i}}$ and make $v_{i}$ fit in with the velocity $v_{i}^{*}$ of $C_{C_{i}}$ , as $t \to T_{f}$ , that is

{\hat{r}}_{i} = r_{i}^{*} - r_{i} \to 0, i = 1, 2, \dots, N, t \to T_{f}

(19)

and

{\hat{v}}_{i} = v_{i}^{*} - v_{p_{i}} \to 0, i = 1, 2, \dots, N, t \to T_{f}

(20)

where $0 < T_{f} < \infty$ .

Control law design of dynamic formation

In this section, a control law is given, which makes the desire dynamic formation achieve. Let

\begin{matrix} r = [r_{1}, r_{2}, \dots, r_{N}], v = [v_{1}, v_{2}, \dots, v_{N}] \\ r^{*} = [r_{1}^{*}, r_{2}^{*}, \dots, r_{N}^{*}], v^{*} = [v_{1}^{*}, r_{2}^{*}, \dots, v_{N}^{*}] \\ \hat{r} = [{\hat{r}}_{1}, {\hat{r}}_{2}, \dots, {\hat{r}}_{N}], \hat{v} = [{\hat{v}}_{1}, {\hat{r}}_{2}, \dots, {\hat{v}}_{N}] \end{matrix}

Also, the control law is given as follows

\begin{array}{l} u_{i} = {\overset{\cdot\cdot}{r}}_{i}^{*} - β {(r_{i} - r_{i}^{*})}^{α} - γ β {(v_{i} - {\dot{r}}_{i}^{*})}^{α} \\ - \sum_{j = 1}^{N} g_{i j} a_{i j} {{[(r_{i} - r_{i}^{*}) - (r_{j} - r_{j}^{*})]}^{α} - {[(v_{i} - {\dot{r}}_{i}^{*}) - (v_{j} - {\dot{r}}_{j}^{*})]}^{α}} \end{array}

(21)

where $0 < α < 1$ .

In order to facilitate the finite-time stability analysis, the following lemma is given.

Lemma 4: $\overset{\cdot}{x} = f (x, u)$ is finite-time stable if and only if there is a continuous Lyapunov function $V$ and constants $k \geq 0$ , $0 < α < 1$ such that

\overset{\cdot}{V} \leq - k V^{α}

(22)

Then, we obtain the following theorem.

Theorem 1: Based on the control law (21), each agent can reaches its desired position and the objective $H$ obtains the minimum value in a finite time.

Proof: Based on the control law (21) and $\overset{\cdot}{\hat{r}} = \hat{v}$ , we can obtain

(\begin{matrix} \overset{\cdot}{\hat{r}} \\ \overset{\cdot}{\hat{v}} \end{matrix}) = (\begin{matrix} 0_{N \times N} & I_{N} \\ - (β I_{N} + L) & - γ (β I_{N} + L) \end{matrix}) {(\begin{matrix} \hat{r} \\ \hat{v} \end{matrix})}^{α}

(23)

Let $y = (\hat{r}, \hat{v})^{T}$ , then (23) can be rewritten as $\overset{\cdot}{y} = Ξ y^{α}$ , where

Ξ = (\begin{matrix} 0_{N \times N} & I_{N} \\ - (β I_{N} + L) & - γ (β I_{N} + L) \end{matrix})

Let $V = \frac{1}{2} y^{T} y$ be the Lyapunov function. Then, we have

\overset{\cdot}{V} = - y^{T} (\begin{matrix} 0_{N \times N} & I_{N} \\ β I_{N} + L & γ (β I_{N} + L) \end{matrix}) y^{α}

(24)

Let $\hat{Ξ} = (\begin{matrix} 0_{N \times N} & I_{N} \\ β I_{N} + L & γ (β I_{N} + L) \end{matrix})$ , we have $\overset{\cdot}{V} = - y^{T} \hat{Ξ} y^{α}$ . Note that

\begin{array}{l} \det (λ I_{2 n} - \hat{Ξ}) = \det (λ^{2} I_{n} - γ λ (β I_{n} + L) - β I_{n} - L) \\ = \det ((λ^{2} - γ λ β - β) I_{n} + (- 1 - γ λ) L) \end{array}

(25)

and

det (λ I_{n} + L) = Π_{i = 1}^{N} (λ - μ_{i})

(26)

where $μ_{i}$ is the $i$ th eigenvalue of $- L$ . By comparing (25) and (26), the roots of (25) can be obtained by solving

λ^{2} - γ λ β - β = μ_{i} (- 1 - γ λ)

and then the eigenvalues of $\hat{Ξ}$ are obtained as follows

λ_{i} = \frac{γ (β - μ_{i}) \pm \sqrt{γ^{2} {(β - μ_{i})}^{2} - 4 (β - μ_{i})}}{2}

(27)

If the information exchange topology has a (directed) spanning tree, we know that $L$ has a simple zero eigenvalue and all the other eigenvalues have negative real parts. Without loss of generality, we let $μ_{1} = 0$ and $Re (μ_{i}) < 0, i = 2, \dots, n$ . Then, we can obtain $β - μ_{i} > 0$ and $min_{i = 1, 2, \dots, N} (β - μ_{i}) = β > 0$ . Then, we have

min_{i = 1, 2, \dots, N} λ_{i} = \frac{γ β - \sqrt{γ^{2} β^{2} - 4 β}}{2}

(28)

It is easy to find that $(γ β)^{2} - (\sqrt{γ^{2} β^{2} - 4 β})^{2} = 4 β > 0$ , that is, $min_{i = 1, 2, \dots, N} λ_{i} = \frac{γ β - \sqrt{γ^{2} β^{2} - 4 β}}{2} > 0$ Then, we have

\begin{matrix} \overset{\cdot}{V} \leq - λ_{min} (\hat{Ξ}) y^{T} y \leq - \frac{γ β - \sqrt{γ^{2} β^{2} - 4 β}}{2} \\ y^{T} y^{α} \leq - \frac{γ β - \sqrt{γ^{2} β^{2} - 4 β}}{4} V^{\frac{1 + α}{2}} \end{matrix}

(29)

According to Lemma 4, we have $V \to 0$ in finite time, that is

\begin{matrix} {\hat{r}}_{i} = r_{i}^{*} - r_{i} \to 0, i = 1, 2, \dots, N, t \to T_{f} . \\ {\hat{v}}_{i} = v_{i}^{*} - v_{i} \to 0, i = 1, 2, \dots, N, t \to T_{f} \end{matrix}

Remark 3: In fact, ${\overset{\cdot}{r}}_{i}^{*} = {\overset{\cdot}{C}}_{C_{i}}, {\overset{\cdot}{r}}_{j}^{*} = {\overset{\cdot}{C}}_{C_{j}},$ and ${\overset{\cdot\cdot}{r}}_{i}^{*} = {\overset{\cdot\cdot}{C}}_{C_{i}} .$ Therefore, we take the following formation control

\begin{matrix} u_{i} = {\overset{\cdot\cdot}{C}}_{C_{i}} - β (r_{i} - r_{i}^{*})^{α} - γ β (v_{i} - {\overset{\cdot}{C}}_{C_{i}})^{α} \\ - \sum_{j = 1}^{N} g_{ij} a_{ij} {[(r_{i} - r_{i}^{*}) - (r_{j} - r_{j}^{*})]^{α} \\ - [(v_{i} - {\overset{\cdot}{C}}_{C_{i}}) - (v_{j} - {\overset{\cdot}{C}}_{C_{j}})]^{α}} \end{matrix}

(30)

Computation of boundary terms

There remains a significant practical difficulty in computing the boundary terms $C_{C_{i}}$ . We now define a number of quantities relating to Voronoi cells. Let $\partial C_{i}$ and $\partial C (t)$ be the boundary of $C_{i}$ and $C (t)$ , respectively. By $x_{\partial C_{i}} (P)$ we mean a point $x \in \partial C_{i}$ , and $n_{\partial C_{i}}$ is the outward facing unit normal of $\partial C_{i}$ . Given an agent i, we define $N_{i}$ as the index set of robots that share Voronoi boundaries with $\partial C_{i}$ , $N_{i} = {j | \partial C_{i} ⋂_{} \partial C_{j} \neq 0}$ . We denote the set of points on the Voronoi boundary shared by agents $i$ and $j$ as $l_{ij} = C_{i} ⋂_{} C_{j}$ , as shown in Figure 3. Then, $x l_{ij} (P_{C} (p_{i}), P_{C} (p_{j}))$ is a point on that shared boundary, and $n l_{ij}$ is the unit normal of $l_{ij}$ from $P_{C} (p_{i})$ to $P_{C} (p_{i})$ . By the definition of the Voronoi cell (3), we know the following facts

\partial C_{i} = (\cup_{j \in N_{i}} l_{ij}) \cup (\partial C_{i} \cap \partial C (t)), l_{ij} = l_{ji}, n l_{ij} = - n l_{ji} .

(31)

\begin{array}{l} \frac{d \int_{C_{i}} x φ (x) d x}{d t} = \frac{\partial \int_{C_{i}} x φ (x) d x}{\partial {\hat{p}}_{i}} {\dot{P}}_{C} (p_{i}) + \frac{\partial \int_{C_{i}} x φ (x) d x}{\partial x} \dot{x} \\ = {\dot{P}}_{C} (p_{i}) \int_{\partial C_{i} \cap \partial C (t)} x φ (x) d x \frac{x_{\partial C_{i}} (P)}{\partial P_{C} (p_{i})} n_{\partial C_{i}} d x \\ + {\dot{P}}_{C} (p_{i}) \sum_{j \in N_{i}} \int_{l_{i j}} x φ (x) d x \frac{x_{\partial l_{i j}}}{\partial P_{C} (p_{i})} n_{l_{i j}} d x \\ + \dot{x} \int_{\partial C_{i} \cap \partial C (t)} x φ (x) d x \frac{x_{\partial C_{i}} (P)}{\partial P_{C} (p_{i})} n_{\partial C_{i}} d x \\ + \dot{x} \sum_{j \in N_{i}} \int_{l_{i j}} x φ (x) d x \frac{x_{\partial l_{i j}}}{\partial P_{C} (p_{i})} n_{l_{i j}} d x \end{array}

(32)

where $\frac{x_{\partial C_{i}} (P)}{\partial P_{C} (p_{i})}$ and $\frac{x_{\partial l_{ij}}}{\partial P_{C} (p_{i})}$ are $N \times N$ matrices. Since points on the boundary of the environment do not change position as a function of $p_{i}$ , we have $\frac{x_{\partial C_{i}} (P)}{\partial P_{C} (p_{i})} = 0, \forall x \in \partial C_{i} \cap \partial C (t)$ . Then, we have

\begin{array}{l} \begin{array}{l} \frac{d \int_{C_{i}} x φ (x) d x}{d t} = {\dot{P}}_{C} (p_{i}) \sum_{j \in N_{i}} \\ \int_{l_{i j}} x φ (x) d x \frac{x_{\partial l_{i j}}}{\partial P_{C} (p_{i})} n_{l_{i j}} d x + \dot{x} \sum_{j \in N_{i}} \int_{l_{i j}} x φ (x) d x \frac{x_{\partial l_{i j}}}{\partial P_{C} (p_{i})} n_{l_{i j}} d x \end{array} \end{array}

(33)

Figure 3.

Quantities and constraints associated with the Voronoi boundary shared between neighboring agents.

We will exploit the geometry of the Voronoi cell to derive a parametric formula for the computation of $\frac{x_{\partial l_{ij}}}{\partial P_{C} (p_{i})} n_{l_{ij}}$ . Define $l_{ij}$ by

l_{ij} = {x | x = v_{i j_{1}} + (1 - α) v_{i j_{2}}, α \in [0, 1]}

(34)

where $v_{i j_{1}}$ , $v_{i j_{2}}$ are the end points of the line segment $l_{ij}$ . Now we can write $x (α)$ for $x \in l_{ij}$ . By the definition of the Voronoi cell, any point $x (α)$ must satisfy

n_{l_{ij}}^{T} (x (α) - \frac{P_{C} (p_{i}) + P_{C} (p_{j})}{2}) = 0, \forall x \in l_{ij} .

(35)

and

n_{l_{ij}} = \frac{P_{C} (p_{j}) - P_{C} (p_{i})}{∥ P_{C} (p_{j}) - P_{C} (p_{i}) ∥}

(36)

Differentiate (36) implicitly with respect to $P_{C} (p_{i})$ to find the relation

\frac{\partial n_{l_{ij}}^{T}}{\partial P_{C} (p_{i})} (x (α) - \frac{P_{C} (p_{i}) + P_{C} (p_{j})}{2}) + \frac{\partial x l_{ij}}{\partial P_{C} (p_{i})} n_{l_{ij}} = \frac{n_{l_{ij}}}{2},

(37)

and

\frac{\partial n l_{ij}}{\partial P_{C} (p_{i})} = \frac{n l_{ij} n l_{ij}^{T} - I_{2}}{∥ P_{C} (p_{j}) - P_{C} (p_{i}) ∥} .

(38)

Simplify and substitute using $x = v_{i j_{1}} + (1 - α) v_{i j_{2}}, α \in [0, 1]$ to find the desired formula

\begin{matrix} \frac{\partial x l_{ij}}{\partial P_{C} (p_{i})} n_{l_{ij}} = \frac{n_{l_{ij}}}{2} - \frac{n l_{ij} n l_{ij}^{T} - I_{2}}{∥ P_{C} (p_{j}) - P_{C} (p_{i}) ∥} ((v_{i j_{1}} - v_{i j_{2}}) α + v_{i j_{2}} - P_{C} (p_{i})) \\ |' A \end{matrix}

(39)

where $I_{2}$ is the $2 \times 2$ identity matrix. Notice (39) is linear in $Á$ and can be computed readily given the known quantities $p_{i}, p_{j}, v_{i j_{1}}$ , and $v_{i j_{2}}$ . Then, we can have

\begin{array}{l} \frac{d \int_{C_{i}} x φ (x) d x}{d t} = ({\dot{P}}_{C} (p_{i}) + \dot{x}) \times \sum_{j \in N_{i}} (\frac{n_{l_{i j}}}{2} - \frac{n l_{i j} n l_{i j}^{T} - I_{2}}{∥ P_{C} (p_{j}) - P_{C} (p_{i}) ∥} \\ f (v_{i j_{1}}, v_{i j_{2}}, α, P_{C} (p_{i})) \times \int_{l_{i j}} x φ (x) d x, \end{array}

(40)

where

f (v_{i j_{1}}, v_{i j_{2}}, α, P_{C} (p_{i})) = (v_{i j_{1}} - v_{i j_{2}}) α + v_{i j_{2}} - P_{C} (p_{i}),

and

\begin{array}{l} \frac{d M_{C_{i}}}{d t} = ({\dot{P}}_{C} (p_{i}) + \dot{x}) \times \sum_{j \in N_{i}} (\frac{n_{l_{i j}}}{2} - \frac{n l_{i j} n l_{i j}^{T} - I_{2}}{∥ P_{C} (p_{j}) - P_{C} (p_{i}) ∥} \\ f (v_{i j_{1}}, v_{i j_{2}}, α, p_{i})) \times \int_{l_{i j}} φ (x) d x \end{array}

(41)

Based on (39) and (41), we have

\begin{matrix} {\overset{\cdot}{C}}_{C_{i}} = \frac{1}{M_{C_{i}}^{2}} ({\overset{\cdot}{P}}_{C} (p_{i}) + \overset{\cdot}{x}) \sum_{j \in N_{i}} (\frac{n_{l_{ij}}}{2} - \frac{n l_{ij} n l_{ij}^{T} - I_{2}}{∥ P_{C} (p_{j}) - P_{C} (p_{i}) ∥} \\ \times f (v_{i j_{1}}, v_{i j_{2}}, α, p_{i})) (M_{C_{i}} \int_{l_{ij}} x φ (x) dx - \int_{l_{ij}} φ (x) dx \int_{C_{i}} x φ (x) dx) \end{matrix}

(42)

Remark 4: Similarly, we can obtain the value of ${\overset{\cdot\cdot}{C}}_{C_{i}}$ . It is easy to find that value of ${\overset{\cdot\cdot}{C}}_{C_{i}}$ contains $\overset{\cdot\cdot}{x}$ . However, $\overset{\cdot\cdot}{x}$ can not be exactly obtained in practice. Therefore, we need to consider the error between $\overset{\cdot}{\hat{v}}$ and $\overset{\cdot\cdot}{x}$ . Let $ξ = \overset{\cdot}{\hat{v}} - \overset{\cdot\cdot}{x}$ , then, we have

(\begin{matrix} \overset{\cdot}{\hat{r}} \\ \overset{\cdot}{\hat{v}} \end{matrix}) = (\begin{matrix} 0_{N \times N} & I_{N} \\ - (β I_{N} + L) & - γ (β I_{N} + L) \end{matrix}) {(\begin{matrix} \hat{r} \\ \hat{v} \end{matrix})}^{α} + (\begin{matrix} 0 \\ ξ \end{matrix})

(43)

Let $y = (\hat{r}, \hat{v})^{T}$ , $Γ = (\begin{matrix} 0 \\ ξ \end{matrix})$ then (43) can be rewritten as $\overset{\cdot}{y} = Ξ y^{α} + Γ$ , where

Ξ = (\begin{matrix} 0_{N \times N} & I_{N} \\ - (β I_{N} + L) & - γ (β I_{N} + L) \end{matrix})

Then, we have

\overset{\cdot}{V} = - y^{T} (\begin{matrix} 0_{N \times N} & I_{N} \\ β I_{N} + L & γ (β I_{N} + L) \end{matrix}) y^{α} + y^{T} Γ

(44)

First, a lemma is introduced as follows.

Lemma 5: Consider the system $\overset{\cdot}{x} = f (x, u)$ . Suppose that there exist continuous function $V (x)$ , scalars $λ > 0$ , $0 < σ < 1$ and $0 < β < \infty$ such that

\overset{\cdot}{V} (x) \leq - λ V (x)^{σ} + β

(45)

Then, the trajectory of system $\overset{\cdot}{x} = f (x, u)$ is PFS (Practical Finite-time Stable), and the trajectories of the closed-loop system is bounded in finite time as

li m_{t \to T} x \in {x | V^{σ} (x) \leq \frac{β}{(1 - θ) λ}}

(46)

where $0 < θ < 1$ . And the time is bounded as $T \leq \frac{V^{1 - σ} (x (0))}{(1 - σ) θ λ}$

Because of $∥ Γ ∥ < ζ$ , then

\begin{matrix} \overset{\cdot}{V} \leq - y^{T} (\begin{matrix} 0_{N \times N} & I_{N} \\ β I_{N} + L γ (β I_{N} + L) \end{matrix}) y^{α} + ∥ y^{T} ∥ ∥ Γ ∥ \\ \leq - y^{T} (\begin{matrix} 0_{N \times N} & I_{N} \\ β I_{N} + L & γ (β I_{N} + L) \end{matrix}) y^{α} + ∥ y^{T} ∥ ζ \\ \leq - \frac{γ β - \sqrt{γ^{2} β^{2} - 4 β}}{4} V^{\frac{1 + α}{2}} + β \end{matrix}

(47)

where $0 < β = ∥ y^{T} ∥ ζ < \infty$ , then in terms of Lemma 5, $V$ converges a bounded set

li m_{t \to T_{f}} y \in {y | V^{α} (y) \leq \frac{β}{(1 - θ) λ}}

(48)

in a finite time. And the finite time is $T_{f} \leq \frac{V^{1 - a} (y (0))}{(1 - a) θ k},$ where $k = \frac{γ β - \sqrt{γ^{2} β^{2} - 4 β}}{4} .$

Coverage tracking algorithm

In this section, the coverage tracking algorithmic is given. First, we need to execute Algorithm 1 to obtain the estimation circle $C (t)$ . Then, the agents execute Algorithm 2 to construct of cell $C_{i}$ . Last, the agents begin to execute Algorithm 3 to obtain $u_{i}$ and make finite time dynamic formation implementation.

Algorithm 1: $Obtain the estimation circle$ $C (t)$
Input: $P, H, B, Q, θ, ε$ Output: $C (t)$ ₁ for each $j \neq i, j = 1, 2, \dots, N$ do ₂ if $(A, C)$ $is observable$ and $satisfies properties (11)$ then ₃ $L = ε + \sqrt{\frac{λ_{max} (P)}{λ_{min}}} \frac{2 ∥ (- P H, P B) ∥}{λ_{min} (Q) θ}$ ₄ end ₅ end

Algorithm 2: Partitioning – Construction of cell $C_{i}$
Input: $p_{i}, p_{j}, i, j = 1, 2, \dots, N$ Output: $C_{i}$ ₁ $P_{C} (p_{i})$ is obtained; ₂ for each $j \neq i, j = 1, 2, \dots, N$ do ₃ if $P_{C} satisfies properties (12), (1213) and (121314)$ then ₄ $C_{i} (t) = {x \in C \| ∥ x - P_{C} (p_{i}) ∥ \leq ∥ x - P_{C} (p_{j}) ∥, \forall i \neq j$ }; ₅ end ₆ end

Algorithm 3: Control – Calculation of control laws $u_{i}$
Input: $p_{i}, p_{j}, i, j = 1, 2, \dots, N$ Output: $u_{i}$ ₁ while transmit $p_{i}$ and receive transmissions from other agents do ₂ $u_{i} \leftarrow 0$ , execute Partitioning algorithm; ₃ for each $P_{C (q_{i})} \in C (t)$ do ₄ if $C_{C_{i}}$ , $M_{C_{i}}$ , ${\overset{\cdot}{C}}_{C_{i}}$ , ${\overset{\cdot}{M}}_{C_{i}}$ , ${\overset{\cdot\cdot}{C}}_{C_{i}}$ and ${\overset{\cdot\cdot}{M}}_{C_{i}}$ are obtained then ₅ if $\exists j = 1, 2, \dots, N, j \neq i$ then ₆ compute ${\overset{\cdot}{C}}_{C_{j}}$ and ${\overset{\cdot}{M}}_{C_{j}}$ , ${\overset{\cdot\cdot}{C}}_{C_{j}}$ and ${\overset{\cdot\cdot}{M}}_{C_{j}}$ ₇ if $\overset{\cdot\cdot}{x} \leftarrow \overset{\cdot}{\hat{v}}$ then ₈ the control law is given as (21) ₉ end ₁₀ end ₁₁ end ₁₂ end ₁₃end

Algorithm 3: Control – Calculation of control laws

u_{i}

Input:

p_{i}, p_{j}, i, j = 1, 2, \dots, N

Output:

u_{i}

₁ while transmit $p_{i}$ and receive transmissions from other agents do
₂ $u_{i} \leftarrow 0$ , execute Partitioning algorithm;
₃ for each

P_{C (q_{i})} \in C (t)

do
₄ if

C_{C_{i}}

M_{C_{i}}

{\overset{\cdot}{C}}_{C_{i}}

{\overset{\cdot}{M}}_{C_{i}}

{\overset{\cdot\cdot}{C}}_{C_{i}}

and ${\overset{\cdot\cdot}{M}}_{C_{i}}$ are obtained then
₅ if

\exists j = 1, 2, \dots, N, j \neq i

then
₆ compute

{\overset{\cdot}{C}}_{C_{j}}

and

{\overset{\cdot}{M}}_{C_{j}}

{\overset{\cdot\cdot}{C}}_{C_{j}}

and

{\overset{\cdot\cdot}{M}}_{C_{j}}

₇ if

\overset{\cdot\cdot}{x} \leftarrow \overset{\cdot}{\hat{v}}

then
₈ the control law is given as (21)
₉ end
₁₀ end
₁₁ end
₁₂ end
₁₃end

In order to implement in an algorithmic manner the partitioning scheme and control law, the sensing regions $Ω_{i}$ and cells $C_{i}$ need to be approximated by polygons. In order to calculate the value of the control law, several line integrals have to be calculated numerically as well as one double integral. The line integrals are calculated as sums, each term of which is evaluated on an edge $l_{ij}$ of polygon $C_{i}$ . The double integral is just the area of the corresponding cell $C_{i}$ and can thus be calculated simply as the area of the polygonal approximation $Ω_{i}$ of that cell. Since cells may consist of multiple disjoint regions or have holes, their polygonal approximations may have multiple contours, internal or external.

Numerical simulations

In order to illustrate the theoretical results, some numerical simulations are presented to validate our coverage algorithms.

The initial position of four agents are $p_{1} (t_{0}) = (0.4, 0.5)^{T}$ , $p_{2} (t_{0}) = (1.6, 1.6)^{T}, p_{3} (t_{0}) = (0.55, 0.50)^{T}, p_{4} (t_{0}) = (1.0, 1.1)^{T} .$ The actuation range of the agent is $r = 0.9$ and the system matrices of the moving target are

E = (\begin{matrix} 0 & 0 \\ 0 & 0 \end{matrix}), D = (\begin{matrix} - 1 & 0 \\ 0 & - 1 \end{matrix}), F = (\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}) .

The disturbances are given as follows, $ϰ (t) = (\cos t, \sin t)^{T}$ , $ω_{1} (t) = \cos t, ω_{i} (t) = \sin t, i = 2, 3, 4$ . In this example, let

\begin{matrix} A = (\begin{matrix} 0 & I_{2} \\ E & D \end{matrix}), B = (\begin{matrix} 0 \\ F \end{matrix}), \\ C = (\begin{matrix} C_{1} & C_{2} \end{matrix}) = (\begin{matrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{matrix}) \end{matrix}

Case 1: The probability density function of the real target appear is the normal distribution probability function.

In order to make the regional integrals easy, we select the circumscribing square of the target region as the new target region. The projection of the initial position and final position of the four agents are shown in Figure 4 (left). It is easy to find that projection of the initial position in the region are grouped, and the projection of the final position in the region are scattered. The projections of the trajectories of the agents on the region of interest can be seen in Figure 4 (left), and the final positions of the agents are marked by asterisks. The change curve of coverage performance index function is shown in Figure 4 (right) and the index function converges to a constant value over time.

Figure 4.

The trajectories of four agents on $Ω$ and Value of $H$ .

Case 2: The probability density function of the real target appear is uniform.

The projection of the initial position and final position of the four agents are shown in Figure 5 (left). It is easy to find that projection of the initial position in the region are grouped, and the projection of the final position in the region are scattered, which is different from the Case 1. The projections of the trajectories of the agents on the region can be seen in Figure 5 (left), and the final positions of the agents are marked by asterisks. The change curve of coverage performance index function is shown in Figure 5 (right) and the index function converges to a constant value over time. It is easy to find that the convergence rata in Case 1 is greater than the Case 2, which means that the non-uniform probability distribution is beneficial to the coverage of the moving region.

Figure 5.

The trajectories of four agents on $Ω$ and value of $H$ .

Conclusions and future work

In this paper, we considered a multi-agent tracking problem to cover a moving target in finite time. Since the sensors could not get the exact position and velocity of the moving target, we reconstructed the variables with help of observer design first. Also, based on the observer, we have a circle to denote the region where the target may appear and the probability that the target appear in the circle is denoted by a probability density function. Then a performance index function is given to describe the effectiveness of covering a moving target. Last, a formation-based tracking method was proposed to cover the estimation region of the target in finite time so as to catch it by networked agents.

In the recent work, a general approach that $N$ agents are used to cover a moving and fixed size region to guarantee the moving target is covered. However, in the practical problem, the estimation region of the target is time varying. Thus, how to cover the moving and time varying region is a new problem to solve. The future research will focus on this issue.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work is partially supported by the National Key Research and Development Project (Grant No. 2018YFE0208700) and Special Research Project of Chinese Civil Aircraft (No. MJ-2020-S-03).

ORCID iD

Longbiao Ma

References

Arslan

Koditschek

(2016) Voronoi-based coverage control of heterogeneous disk-shaped robots. In: 2016 IEEE International Conference on Robotics and Automation, Stockholm, Sweden, 16–21 May 2016, pp. 1–8. Stockholm: Institute of Electrical and Electronic Engineers.

Bikramaditya

Bidyadhar

Bibhuti

(2016) Co-operative control coordination of a team of underwater vehicles with communication constraints. Transactions of the Institute of Measurement and Control 38(4): 463–481.

Cardei

(2006) Energy-efficient coverage problems in wireless ad-hoc sensor networks. Computer Communications 29(4): 413–420.

Choset

(2001) Coverage for robotics: A survey of recent results. Annals of Mathematics and Artificial Intelligence 31(1–4): 113–126.

Cortes

Martinez

Karatas

(2002) Coverage control for mobile sensing networks. IEEE Transactions on Robotics & Automation 20(2): 243–255.

Faber

Gunzburger

(1999) Centroidal Voronoi tessellations: Applications and algorithms. Siam Review 41(4): 637–676.

Gupta

Rao

Tamarapalli

(2015) Analysis of stochastic k-coverage and connectivity in sensor networks with boundary deployment. IEEE Transactions on Intelligent Transportation Systems 16(4): 1–11.

Gusrialdi

Hirche

Asikin

(2009) Voronoi-based coverage control with anisotropic sensors and experimental case study. Intelligent Service Robotics 2(4): 195–204.

Hussein

Stipanovic

(2007) Effective coverage control for mobile sensor networks with guaranteed collision avoidance. IEEE Transactions on Control Systems Technology 15(4): 642–657.

10.

Leonard

Olshevsky

(2013) Nonuniform coverage control on the line. IEEE Transactions on Automatic Control 58(11): 2743–2755.

11.

Liu

Xiao

(2006) Random coverage with guaranteed connectivity: Joint scheduling for wireless sensor networks. IEEE Transactions on Parallel & Distributed Systems 17(6): 562–575.

12.

Liu

Yang

Zhang

(2018) Path planning for UAV based on improved chaotic ant colony algorithm (CACA). Command Information System and Technology 9(6): 41–48.

13.

Luo

(2012) Barrier coverage control based on data fusion for wireless sensor network. Journal of Electronics & Information Technology 34(4): 825–831.

14.

Luo

Shao

(2018) Design of intelligent path planning for tactical enviroment. Command Information System and Technology 9(6): 49–54.

15.

Miah

Bao

Bourque

(2015) Nonuniform coverage control with stochastic intermittent communication. IEEE Transactions on Automatic Control 60(7): 1981–1986.

16.

Nasimov

Matveev

(2015) Suboptimal decentralized blanket coverage control of mobile autonomous sensor networks. In: 2014 6th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), St. Petersburg, Russia, 6–8 October 2014, pp. 366-371. St. Petersburg: Institute of Electrical and Electronic Engineers.

17.

Savkin

Cheng

(2015) Decentralized Coverage Control Problems for Mobile Robotic Sensor and Actuator Networks. John Wiley & Sons.

18.

Sun

Wang

(2015) A novel energy efficient multi-target coverage control protocol with event driven mechanism of wireless sensor network. In: 2015 International Conference on Identification, Information, and Knowledge in the Internet of Things, Beijing, China, 22–23 October 2015, pp. 201-205. Beijing: Institute of Electrical and Electronic Engineers.

19.

Wang

Hong

(2008) Finite-time consensus for multi-agent networks with second-order agent dynamics. IFAC Proceedings Volumes 41(2): 15185–15190.

20.

Wang

(2012) Coverage tracking control for multiple cooperative agents. International Journal of Control 85(6): 660–670.

21.

Wang

Hong

Jiang

(2009) Coverage tracking of a moving target by a group of mobile agents. In: 2009 7th Asian Control Conference, Hong Kong, China, 27–29 August 2009, pp. 332–337. Hong Kong: Institute of Electrical and Electronic Engineers.

22.

Wang

Hussein

(2007) Cooperative vision-based multi-vehicle dynamic coverage control for underwater applications. In: 2007 IEEE International Conference on Control Applications, Singapore, Singapore, 1–3 October 2007, pp. 82–87. Singapore: Institute of Electrical and Electronic Engineers.

23.

Zuo

Chen

Cui

(2014) Coverage control of multiple autonomous underwater vehicle with disturbance by ocean currents considered. Journal of Northwestern Polytechnical University 32(5): 769–774.