Decentralized Multi-Agent Active Search and Tracking
when Targets Outnumber Agents

Searching for targets, detecting objects of interest (OOIs), localizing and following them are tasks integral to several robotics applications. Hence one or more of these sub-problems have been widely studied in a number of settings. For example, in informative path planning [1] or simultaneous localization and mapping (SLAM) [2], when the OOIs are fixed, an agent (or robot) adaptively selects actions to detect and localize the targets. Here the environment (or, the target distribution) being stationary, an agent tends to explore unseen parts of its surroundings more than exploit already observed viewpoints. In contrast, when targets are dynamic, the environment is non-stationary. Therefore, agents tracking an unknown number of moving targets should trade-off between exploring the possibly unobserved parts of the environment and exploiting its own posterior estimates to localize the previously detected targets at the current timestep. Unfortunately, prior work in multi-target tracking (MTT) has often assumed that the environment is known and exploration is not of primary concern [3]. Moreover, with multiple agents, existing MTT methods simplify the explore-exploit dilemma by separating search and tracking into sequential tasks where each agent is assigned to track a target as soon as it is found [4]. Another approach is to assign sub-teams for executing these tasks separately [5]. Further, the majority of these multi-agent multi-target tracking (MAMTT) algorithms require either a central controller to coordinate joint tracking actions, facilitate target hand-offs among agents or they depend on synchronized inter-agent communication for distributed inference and decision making. Unfortunately, such conditions may not be feasible in practice: the environment may be unstructured and unknown, OOIs may need to be simultaneously detected and localized (i.e. without a separation between search and tracking phases), there may not be enough agents to continuously monitor all the targets and unreliable communication channels may hinder inter-agent synchronization at each timestep.

In this work, we aim to develop a more practical approach to the MAMTT setup. In particular, we focus on the setting where agents are outnumbered by targets, so that the multi-agent team is unable to continuously cover all targets in their fields of view. The number of targets and their initial locations are unknown. Therefore, agents need to interact with the environment to collect observations by adaptively making explore-exploit decisions. It is not feasible to continuously track all targets, but our goal is to produce an estimate of the number and positions of all targets with time. We assume that there is no central controller, and agents share their observations asynchronously with teammates, whenever possible. In other words, agents do not wait to receive observations, action selection policy or environment belief information from their teammates and can continue their online decision making when communication is unreliable or even unavailable.

Target detection and tracking are both widely studied problems, typically considered as distinct tasks in various applications like search and rescue [6], security surveillance [7], computer games [8], etc. [3] is a detailed survey of the many different approaches and taxonomy used in robotics and related fields for such scenarios. Here, we discuss some of the most relevant prior work in our context.

The single target state is commonly modeled assuming linear dynamics with additive Gaussian noise, using the Kalman filter [9] or using non-parametric particle filters [10]. In multi-target settings, alternative approaches like Multiple Hypothesis Tracker (MHT) [11], Joint Probabilistic Data Association (JPDA) [12] and Probability Hypothesis Density (PHD) filter [13] have been proposed, all of which differ in how they perform data association [14]. The PHD filter is particularly suited when unique identities for each target are not required, for example, in search and rescue tasks, where agents should detect and localize all survivors. In this work, we build on the Sequential Monte Carlo (SMC) formulation of the PHD filter presented in [15].

Prior work in MAMTT algorithms primarily considers centralized or distributed settings, the latter still necessitating synchronized communication among subgroups of agents at each time step. Coupled with a PHD filter, some of the common action selection methods previously proposed for tracking include mutual information and expected count based objectives [16], Renyi divergence maximization [4] and Lloyd’s algorithm for Voronoi-cell based control [17, 18]. [4] discusses the benefits of a simultaneous search-and-tracking algorithm but their proposed method requires that agents transition from searching to tracking upon target detection, foregoing further exploration. In similar spirit, [19] proposes solving an information gain based multi-objective optimization problem over a finite planning horizon to decide the best (greedy) joint action for a centralized search-and-tracking task. In contrast with these deterministic objectives, [20] demonstrates the superior performance of stochastic optimization methods like Particle Swarm Optimization (PSO) and Simulated Annealing (SA) for better coverage and localization in such settings. Unfortunately, none of these prior approaches are applied in the decentralized and asynchronous multi-agent setup when agents are unable to support continuous target coverage.

Recently, some learning based approaches have been proposed for tracking. [21] considers the single-agent setting, assuming a known number of (one or two) targets which only start moving after first observed by the agent. [22, 23] both propose GNN-based algorithms, trained by imitation from a centralized expert, and deployed in the distributed inference and decision making with synchronized communication setup. While [22] does not consider dynamic targets, [23] simplifies the problem to deterministic optimal control over a fixed horizon, differing from our more complex setting.

Consider a team of $J$ UAVs tasked with search and tracking of an unknown number of moving targets $\{1,\dots,k\}$ in a 2-dimensional (2D) region $\mathcal{G}$ of length $n_{l}$ and width $n_{w}$ (Fig. 1(a)). The agents can self-localize. They are equipped with noisy sensors that provide location 2D coordinates of possible targets in their current field of view (FOV). The targets can move in any direction in the search space at different speeds. We assume that agents typically move faster than targets. Each agent’s FOV includes a contiguous rectangular region of the search space, and agents may choose to observe a wider (smaller) area at a greater (lower) vertical height but with more (less) observation noise. We therefore consider a hierarchical region sensing action space for each agent. Agents can communicate asynchronously with their teammates. Over time $T$, agents observe different parts of the search space to detect and track all targets in the environment.

We now describe our algorithm $\mathrm{DecSTER}$ for multi-agent active search and tracking without continuous coverage.

The SMC-PHD filter propagation steps follow from [15].²²2We will make our code publicly available after publication. In our decentralized setup, each agent maintains its own posterior PHD $\nu_{t}^{j}$. Next, we will describe the decision making step executed by agent $j$ at time $t$.

To the best of our knowledge, prior work has not studied the problem of TS in a continuous (not discretized) search space with a PHD posterior. This is challenging because the PHD is not a distribution and does not include second order uncertainty information, whereas TS is typically applied in the Bayesian setting with the samples drawn from a posterior distribution for which both first and second order moment estimates are available [27]. Prior work in [28] has proposed particle Thompson sampling (PTS) and regenerative PTS (RPTS) algorithms for particle filters where particles are sampled proportional to their weights. Therefore, we adopt a similar principle in our first proposed TS strategy for the SMC-PHD posterior, called TS-PHD-I (Algorithm 1).

We note that this method has drawbacks. It tends to sample more particles from the regions in the PHD where the agent already estimates targets might be present. The samples drawn are thus more likely to be biased against regions of the target state space where the agent might be less certain about its observations owing to false positives or missed detections. Furthermore, this method does a poor job of modeling the uncertainty about the number of true targets.

To address the drawbacks of Algorithm 1, we now describe a second proposed approach to Thompson sampling from our SMC-PHD posterior (Algorithm 2). Recall that the expected cardinality of the target RFS $\mathcal{X}$ over a region $E\subseteq\mathcal{G}$ is given by $\hat{n}=\int_{E}\nu(\textbf{x})d\textbf{x}$. In case of the SMC-PHD representation, $\hat{n}=\sum_{i}w_{i},\forall\textbf{x}_{i}\in E$ [15] i.e. the sum of particle weights of the SMC-PHD in the region $E$ is the expected cardinality of $\mathcal{X}$ in that region. Further, [13] shows that the PHD is the best Poisson approximation of the multitarget posterior in terms of KL divergence. We therefore draw a sample $\tilde{n}$ of the cardinality of the target RFS from a Poisson distribution with mean $\hat{n}=\sum_{i}w_{i}$ (i.e. $\tilde{n}\sim\text{Poisson}(\hat{n})$). Then we sample $\tilde{n}$ locations of the possible targets by drawing from a mixture of already estimated target locations in the PHD and some locations drawn uniformly at random over the search space. These $\tilde{n}$ particles $\tilde{\mathcal{X}}=\{\tilde{\textbf{x}}_{1},\dots,\tilde{\textbf{x}}_{\tilde{n}}\}$ form our TS.

Given a true target set $\mathcal{X}=\{\textbf{x}_{1},\dots,\textbf{x}_{|\mathcal{X}|}\}$ and an estimated set $\mathcal{Y}=\{\mathbf{y}_{1},\dots,\mathbf{y}_{|\mathcal{Y}|}\}$ of possible target locations, our goal is to minimize $\text{OSPA}(\mathcal{X},\mathcal{Y})$. Since the ground truth $\mathcal{X}$ is unknown, each agent $j$ instead draws a TS $\tilde{\mathcal{X}}_{t}^{j}$ from the predicted PHD $\bar{\nu}_{t+1}^{j}$. Assuming observations are generated by $\tilde{\mathcal{X}}_{t}^{j}$ for any action $\mathbf{a}$ and $\mathcal{Y}_{t}^{j}$ is the estimated target set following the PHD filter update, agent $j$ then selects:

Algorithm 3 outlines our proposed algorithm, called $\mathrm{DecSTER}$. In our decentralized and asynchronous multi-agent setting, each agent individually runs $\mathrm{DecSTER}$ with its own sampled $\tilde{\mathcal{X}}_{t}^{j}$. Hence the stochasticity in the sampling procedure enables agents to make decentralized explore-exploit decisions for simultaneous search-and-tracking in their action space.

We now describe our experimental setup. Consider a 2D search space with dimensions $n_{l}\times n_{w}=16\times 16$. There are $k$ targets moving in this region, whose starting locations and velocities are chosen uniformly at random, such that $v_{\max}=0.1$. A team of $J$ agents are tasked with search-and-tracking of all the targets over $T=150$ steps. The agents’ action space $\mathcal{A}$ consists of hierarchical region sensing actions of width $1\times 1$, $2\times 2$, $4\times 4$ and $8\times 8$, $|\mathcal{A}|=340$. Since actions with larger FOV receive noisier observations, we vary the false positive (clutter) rate as $\lambda\in\{0.005,0.04,1,5\}$ for action widths 1, 2, 4 and 8 respectively. The survival probability in the PHD filter is set at $p_{s}=1$ and the detection probability $p_{d}=0.9$ for targets in the agent’s FOV. In our SMC-PHD implementation following [15], we initialize 100 new (birth) particles per observation and re-sample 1000 particles per estimated target, following the low variance sampling method in [29]. We choose $\tilde{\rho}=100$ (Algorithm 1).

The agents assume the target motion model $\textbf{x}_{t+1}=\mathbf{F}\textbf{x}_{t}+\bm{\epsilon}$, where $\mathbf{F}=\begin{bmatrix}1&0&\Delta T&0\\ 0&1&0&\Delta T\\ 0&0&1&0\\ 0&0&0&1\end{bmatrix}$, $\Delta T=1$ and $\bm{\epsilon}\sim\mathcal{N}(\bm{0},\mathbf{Q})$, $\mathbf{Q}=\begin{bmatrix}0.03&0&0.05&0\\ 0&0.03&0&0.05\\ 0.05&0&0.1&0\\ 0&0.05&0&0.1\end{bmatrix}$. The sensing model is $\mathbf{z}=\mathbf{H}\textbf{x}+\bm{\omega}$, where $\mathbf{H}=\begin{bmatrix}1&0&0&0\\ 0&1&0&0\end{bmatrix}$ and $\bm{\omega}\sim\mathcal{N}(\bm{0},\sigma^{2}\mathbf{I})$, $\sigma=0.1$. $\mathbf{I}$ is the identity matrix. For the OSPA metric, we set $c=2$ and $p=1$.

In the following experiments, we measure performance in terms of the average OSPA for the entire team of agents. The plots show mean across 10 random trials with the shaded regions indicating standard error. Each trial differs in the initialization of the target locations and their velocities.

We introduce $\mathrm{DecSTER}$, a novel decentralized and asynchronous algorithm for multi-agent multi-target active search-and-tracking that relaxes the restrictive assumption of requiring continuous target coverage. In simulation, $\mathrm{DecSTER}$ outperforms competitive baselines that greedily optimize for information gain or expected target detections. A key contribution is adapting TS to effectively drive exploration and exploitation using the SMC-PHD filter. Future work includes theoretical analysis of the proposed TS methods and learning improved models of environment uncertainty for non-stationary multi-target tracking. Building on recent success of TS-based multi-agent active search [26], we also aim to validate $\mathrm{DecSTER}$’s performance when deployed on teams of physical robots in the real world.