Multi-Agent Cooperative Target Search

1. Introduction

With the fast development of high resolution imaging devices and processing technologies, unmanned aerial vehicles (UAVs) with air-borne cameras are increasingly employed in civil and military applications such as environmental monitoring, battlefield surveillance and map building, where ground-target search is one of the major applications [1,2]. Target tracking and search have been one of the most popular utilizations of UAVs [3,4]. The conventional method for target search by UAVs in a closed region divides the whole surveillance region into cells, and associates each cell with a probability or confidence of target existence in the cell which constitutes a probability map for the whole region [5,6].

In [7], an online planning and control method is proposed for cooperative search by a group of UAVs, where each agent keeps an individual probability map for the whole region updated according to the Dempster-Shafer theory. A path planning algorithm is designed by using the obtained measurement information, which requires each agent to directly communicate with all other agents. In [8], target detection is considered as part of an integrated mission including coverage control and data collection as parallel tasks for multi-agent networks. The coverage control method aims to maximize the joint detection probability of random events and the probability of target existence is updated by measurements based on the Bayesian rule. However, only the measurement information of direct neighbors is exchanged, which makes it difficult to obtain the target information of the whole surveillance region. In [9], a decentralized gradient-based control strategy is proposed for multiple autonomous mobile sensor agents searching for targets of interest by minimizing the joint team probability of no detection within action horizon based on range detection sensing model. However, each agent is required to collect detection information from all other agents. In [10], a decentralized search algorithm is developed which includes a two-step updating procedure for the probability maps. Each agent first obtains observations over the cells within its sensing region and updates its individual probability map by the Bayesian rule. Then, each agent transmits its individual probability map to its neighbors for map fusion. This algorithm is distributed and full network connectivity is not required. However, the lack of information correlation makes the map fusion difficult and only a heuristic fusion method is given in [10], the performance of which has not been analyzed. In our recent work [11], a distributed iterative map updating model is proposed to fuse the information from measurements and the maps of neighbors based on a logarithmic transformation of the Bayesian rule. Through this, the nonlinear Bayesian update is replaced by a linear one which simplifies the computation. The convergence speed of individual probability map of an agent is also analyzed under fixed detection and false alarm probabilities for the search of static targets.

The cooperative control is an important task for efficient target search by a group of UAVs. Compared with the centralized control algorithms, distributed control algorithms are more robust to accidental failures of UAVs and breaks of communication links [12]. In [13], a distributed multi-agent coverage control method is proposed based on a given sensing performance function related to the distance to robots and gradient descent algorithms are designed for a class of utility functions to optimize the coverage and sensing performance. In [14], a distributed, adaptive control law is developed to achieve an optimal sensing configuration for a network of mobile robots which obtain sensory information of a static environment and exchange their estimates of the environment with neighbors. In [15], a three dimensional distributed control strategy is proposed to deploy hovering robots with downward facing cameras to collectively monitor an environment. A new optimization criterion is defined as the information obtained by each pixel of a camera. In [16], a dynamic awareness model is proposed to control a multi-vehicle sensor network with intermittent communications. The state of awareness of each individual vehicle is updated by its own sensing model and sharing information with its neighbors. However, none of the coverage control schemes mentioned above has considered the detection results of target existence which may affect UAVs' movement decisions in target search. Moreover, there are very few works addressing the issue of distributed vision-based cooperative search for multiple mobile targets with probabilistic detections.

In this paper, we investigate the vision-based cooperative search for multiple ground mobile targets by a group of UAVs with limited sensing and communication capabilities. The main contribution of this paper is that a distributed strategy of information fusion and cooperative control is proposed for searching multiple mobile targets using multi-agent networks based on probabilistic detections. In addition, the time-varying detection and false alarm probabilities are considered which are due to the varying altitudes of the agents with 3-dimensional dynamics. Each agent under our search strategy shares local target information and controls its own behavior in a distributed manner. Based on the probability map updating model proposed in [11], we generalize the model by considering the information decay and transmission between cells due to environmental changes such as the target movement. The influence of the time-varying detection probability on the update of probability maps due to the three-dimensional UAV dynamics is also analyzed. Then, a coverage optimization problem is formulated to balance the coverage area and detection performance. The proposed map updating model and cooperative control scheme are distributed, i.e., each agent only communicates with the agents within its communication range.

This paper is organized as follows: Section 2 describes the basic notations and assumptions used in this paper. Section 3 presents the probability map updates by measurements and information sharing with time-varying detection probabilities. In Section 4, a three-dimensional coverage control method is presented for target search. Simulation results are shown in Section 5, and the conclusions are drawn in Section 6.

2. Basic Definitions and Assumptions

The surveillance region ∈ ℝ² is assumed to be on a plane ground and has been uniformly divided into a set of cells of the same size. We assume that all UAVs (or agents) use the same global Cartesian coordinate system and the position of each agent is denoted as ${\mu }_{i,k}={[c_{i,k}^{\mathrm{T}},h_{i,k}]}^{\mathrm{T}}$ ∈ ℝ³ for agent i (i = 1, 2, ⋯, N) at time k (as shown in Figure 1a), where c _i,k ∈ ℝ² is the planar coordinate of its projection on , h_i,k ∈ ℝ is the altitude of the agent above , N is the total number of agents and “T” denotes the transpose operation. Each agent is assumed to have access to its own position at any time. Each cell in the surveillance region is associated with a probability or confidence of target existence within the cell which is modeled using the Bernoulli distribution, i.e., θ_g,_k = 1 (a target is present) with probability P_i (θ_g,k = 1) and θ_g,k = 0 (no target is present) with probability 1 − P_i (θ_g = 1) for agent i and cell g at time k, where g ∈ ℝ² is the location of the cell center in . If more than one target are present within a cell, they are treated as one single target.

In this paper, we mainly discuss about the vision-based detections where each agent carries an airborne camera facing downward to surveillance region (as shown in Figure 1a). Each agent independently takes measurements Z_i,g,k over the cells within its sensing region ℂ_i,k at time k, where

The topology of the network of all agents at time k is modeled by an undirected graph _k = (ε_k, ). = {1,2,…,N} is the vertex set and ε_k ={{i,j} : i,j ∈ ; ‖μ_i,k− μ_j,k‖ ⩽ R_c} is the edge set, where each edge {i, j} is an unordered pair of distinct agents and R_c is the communication range of each agent. The graph or the network is connected if for any two vertices i and j there exists a sequence of edges (a path) {i, ν₁}, {ν₁, ν₂},…, {ν_n−1, ν_n}, {ν_n,j} in ε_k. Let _i,k = {j ∈ | {i,j} ∈ ε_k} U {i} denote the set of neighbors of agent i at time k where an agent is assumed to be a neighbor of itself. The degree (number of neighbors) of agent i at time k is denoted as d_i,k = | _i,k|.

3. Probability Map Update

3.1. Bayesian Update and Consensus-Based Map Fusion

In [11], we proposed a cooperative control scheme for target search in multi-agent systems. In a group of UAVs, each agent i keeps an individual probability map _i,_g,k of the whole region, where _i,g,k ≜ P_i (θ_g,k = 1) and is updated by the Bayesain rule:

$$\begin{array}{ll}{\mathcal{P}}_{i,g,k}\hfill & =\frac{P(Z_{i,g,k}|{\theta }_{g,k}=1){\mathcal{P}}_{i,g,k-1}}{P(Z_{i,g,k}|{\theta }_{g,k}=1){\mathcal{P}}_{i,g,k-1}+P(Z_{i,g,k}|{\theta }_{g,k}=0)(1-{\mathcal{P}}_{i,g,k-1})}\hfill \\ \hfill & =\{\begin{array}{ll}\frac{p_{i,k}{\mathcal{P}}_{i,g,k-1}}{p_{i,k}{\mathcal{P}}_{i,g,k-1}+q_{i,k}(1-{\mathcal{P}}_{i,g,k-1})}\hfill & \text{if}{Z}_{i,g,k}=1\hfill \\ \frac{(1-p_{i,k}){\mathcal{P}}_{i,g,k-1}}{(1-p_{i,k}){\mathcal{P}}_{i,g,k-1}+(1-q_{i,k})(1-{\mathcal{P}}_{i,g,k-1})}\hfill & \text{if}{Z}_{i,g,k}=0\hfill \\ {\mathcal{P}}_{i,g,k-1}\hfill & \text{ohterwise}\hfill \end{array}\hfill \end{array}$$

(1)

where 0 < _i,g,₀ < 1 and 1 > p_i,k,q_i,k > 0. For the cases with p_i,k = 0 or 1 or q_i,k = 0 or 1, simplified conclusions can be obtained as shown in [11] and will not be considered in this paper. By letting

$$Q_{i,g,k}=ln\left(\frac{1}{{\mathcal{P}}_{i,g,k}}-1\right)$$

(2)

we get the following transformation of Equation (1):

$$Q_{i,g,k}=Q_{i,g,k-1}+{\upsilon }_{i,g,k}$$

(3)

where

$${\upsilon }_{i,g,k}\triangleq \{\begin{array}{ll}ln\frac{q_{i,k}}{p_{i,k}}\hfill & \text{if}{Z}_{i,g,k}=1\hfill \\ ln\frac{1-q_{i,k}}{1-p_{i,k}}\hfill & \text{if}{Z}_{i,g,k}=0\hfill \\ 0\hfill & \text{otherwise}\hfill \end{array}$$

(4)

Keeping Q_i,g,k as the updated term instead of _i,g,k simplifies the nonlinear update in Equation (1) into the linear one in Equation (3). For a group of UAVs, we let each agent i at time k first take measurements and transmit the measurements to its neighbors. After receiving the measurements from all its neighbors, Q_i,g,k is updated as follows:

$$H_{i,g,k}=Q_{i,g,k-1}+\text{∑}_{j\in {\mathcal{N}}_{i,k}}{\upsilon }_{j,g,k}$$

(5)

Then, each agent i transmits the updated Q_i,g,k of the whole region to its neighbors for map fusion, which is given by:

$$Q_{i,g,k}=\text{∑}_{j\in {\mathcal{N}}_{i,k}}{w}_{i,j,k}{H}_{j,g,k}$$

(6)

where $w_{i,i,k}=1-\frac{d_{i,k}-1}{N}$, $w_{i,j,k}=\frac{1}{N}$ for j ∈ _i,k (j ≠ i) and w_i,j,k= 0 for j ∉ _i,k. Then, a matrix composed of w_i,j,k can be defined as:

$$W_k\triangleq {[w_{i,j,k}]}_{N\times N}(i,j=1,\dots ,N)$$

(7)

which is a doubly stochastic matrix [17]. The communications of neighboring agents are assumed to be synchronized within a short time interval. Time synchronization in distributed networks is not the focus of this paper and has been addressed by many works [18–21].

4. Cooperative Coverage Control

In the previous section, a distributed map updating scheme was proposed for fusion of the knowledge of multiple agents. In this section, we will design a cooperative control strategy that optimizes the trajectories of agents for target search based on their real-time updated knowledge about the target information. Within each time interval, an agent first updates its probability map by the the map updating scheme designed in Section 3.3 and then makes a control decision on which place it should move to for the next observation by collective optimization which will be addressed in this section. The two steps make the whole network form a closed-loop sensing and feedback control system.

Here we consider the waypoint motion model for each agent:

Following Equation (13), we can get

Notice that Equation (16) is not an approximation of Equation (15), but a new cost function we intend to optimize which is an upper bound of Equation (16). Such way of defining the cost function is very common in statistics and estimation theory such as the Cramér–Rao lower bound, which is often selected as the cost function if the true variance of estimation error is time-varying and unknown.

Following Equation (16), we should try to maximize $\text{E}\left[{\upsilon }_{j,g,k}^2\right]$ and the collective sensing area of all agents. From Equation (4), we get for g ∈ ℂ_j,k:

It is straightforward to find that $\text{E}\left[{\upsilon }_{j,g,k}^2\right]$ is monotonically increasing with respect to p_j,k and monotonically decreasing with respect to q_j,k no matter θ_g,k = 1 or not. Thus, Equation (16) is further replaced with the following optimization problem:

5. Simulation

6. Conclusions

In this paper, we studied the three-dimensional vision-based cooperative control and information fusion in target search by a group of UAVs with limited sensing and communication capabilities. First, heuristic detection probability and false alarm probability models were built which are related to the target discriminability of a camera and varies as a function of altitude. Then, we formulated the target search problem as a coverage optimization problem by balancing the coverage area and the detection performance. A generalized probability map updating model was proposed, by considering the information decay and transmission due to environmental changes such as the target movement. The simulation results showed that the proposed algorithms can make the individual probability maps of all agents converge to the same one which reflects the true environment when the targets are stationary. The influence of target mobility and the number of deployed UAVs on the convergence of probability maps has also been illustrated by simulation. Following this work, there is still a big potential area for future development and generalization of the proposed method. For example, the extension for detection by heterogenous sensors is an interesting topic since more types of information can be combined to improve the detection performance. More realistic environmental and system conditions that can affect the search results need to be considered such as the light intensity, block on the line of sight, camera with adjustable focus, asynchronous communication, etc.