Multi-target visual tracking with aerial robots

Pratap Tokekar, Volkan Isler, Antonio Franchi

TL;DR

This paper tackles the challenge of multiple aerial robots tracking multiple ground targets, where a trade-off exists between covering more targets and maintaining high-quality tracking. They prove that perfectly tracking all targets with guaranteed quality is impossible and propose a greedy algorithm that achieves a 1/2 approximation for maximizing either the number of targets tracked or the overall tracking quality.

What Problem Does This Paper Address?

Imagine a swarm of drones tasked with keeping an eye on several moving objects on the ground. Each drone has a camera, and the higher it flies, the wider its view and the more targets it could see. However, flying higher also means the targets appear smaller and less distinct, reducing the quality of the tracking. This creates a fundamental conflict: do you prioritize seeing many targets with potentially fuzzy data, or fewer targets with sharp, reliable data? The paper addresses this by aiming to find optimal robot trajectories that balance these competing objectives. They also highlight the inherent difficulty: even with perfect knowledge of target motion, it's impossible to guarantee tracking all targets with a consistent level of quality.

Methods

The core of the paper lies in formulating the problem as a combinatorial optimization task. Specifically, they frame it as a variation of the Maximum Group Coverage (MGC) problem.

  • Sensing Model: They first establish a model for how a robot's camera perceives targets on the ground, accounting for factors like pixel noise, camera orientation uncertainty, and the backprojection of pixels into a "pyramid" of possible locations. This model quantifies the "quality of tracking" for a given robot-target pair.
  • Problem Formulation: They define two primary objectives:
  • Maximizing the number of targets tracked: This is akin to the unweighted MGC problem.
  • Maximizing the overall quality of tracking: This is framed as the weighted MGC problem, where the "weight" of a robot's coverage is the sum of the tracking qualities for all targets it sees.
  • Greedy Algorithm: For both objectives, they propose a greedy algorithm. In each round, the algorithm selects the robot trajectory that provides the "best" immediate gain (either covering a new target or maximizing the sum of tracking qualities), considering the constraints of assigning only one trajectory per robot. This algorithm is proven to provide a 1/2 approximation guarantee.

Datasets

Not discussed in the paper. The evaluation relies on simulations and preliminary experiments with a custom setup.

Key Insights and Ideas

  • The Inherent Trade-off: The paper mathematically proves that there's a fundamental conflict between tracking all targets and maintaining a guaranteed level of tracking quality, even if target movements are perfectly predictable. This means we must accept tracking a subset of targets or accepting variable quality.
  • MGC as a Unifying Framework: Framing the problem as Maximum Group Coverage elegantly captures the constraints of multiple robots and the need to select distinct trajectories for each.
  • Greedy is Good Enough (for now): The simple greedy approach, while not necessarily optimal, offers a provable performance guarantee (1/2 approximation), making it a practical solution for real-world deployment.

Key Results

  • Theoretical Infeasibility: The paper formally demonstrates that tracking all targets with a constant factor approximation of optimal quality is impossible for k ≥ 3 robots and n > k targets, even with known target motion.
  • 1/2 Approximation Guarantee: The proposed greedy algorithm achieves a 1/2 approximation for both maximizing the number of targets tracked and maximizing the total tracking quality.
  • Simulation Performance: Simulations showed that increasing the number of robots generally increases the number of targets tracked and the overall tracking quality. Higher target speeds, however, tend to reduce the number of trackable targets due to increased spread.
  • Experimental Validation: Preliminary experiments with four quadrotors validated the sensing model and demonstrated the feasibility of the greedy algorithm in a real-world scenario, showing robots adjusting trajectories to maintain target tracking.

Limitations and Future Work

  • Sensing Uncertainty: While the paper models sensing uncertainty, the simulations did not incorporate it. The experimental validation addressed this partially.
  • Candidate Trajectories: The algorithm relies on a set of pre-defined candidate trajectories. The generation and selection of these trajectories could be further optimized.
  • Inter-robot Communication: The paper mentions inter-robot communication constraints as a future research direction.
  • Large-Scale Experiments: The current experiments are preliminary; larger-scale validation is planned.
  • Dynamic Target Prediction: The current prediction model uses a moving average filter. More sophisticated prediction methods could improve performance.

Summary updated

Abstract

We study the problem of tracking mobile targets using a team of aerial robots. Each robot carries a camera to detect targets moving on the ground. The overall goal is to plan for the trajectories of the robots in order to track the most number of targets, and accurately estimate the target locations using the images. The two objectives can conflict since a robot may fly to a higher altitude and potentially cover a larger number of targets at the expense of accuracy. We start by showing that k ≥ 3 robots may not be able to track all n targets while maintaining a constant factor approximation of the optimal quality of tracking at all times. Next, we study the problem of choosing robot trajectories to maximize either the number of targets tracked or the quality of tracking. We formulate this problem as the weighted version of a combinatorial optimization problem known as the Maximum Group Coverage (MGC) problem. A greedy algorithm yields a 1/2 approximation for the weighted MGC problem. Finally, we evaluate the algorithm and the sensing model through simulations and preliminary experiments.
BibTeX
@inproceedings{tokekar2014multi,
  author = {Pratap Tokekar and Volkan Isler and Antonio Franchi},
  title = {{Multi-target visual tracking with aerial robots}},
  booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
  year = {2014},
  url = {https://openreview.net/forum?id=UxHCYeSFC9},
}
Figure