Target tracking with distributed sensors: The focus of attention problem

Volkan Isler, Sanjeev Khanna, John Spletzer, Camillo J. Taylor

Research output: Contribution to journalArticlepeer-review

40 Scopus citations

Abstract

In this paper, we consider the problem of assigning sensors to track targets so as to minimize the expected error in the resulting estimation for target locations. Specifically, we are interested in how disjoint pairs of bearing or range sensors can be best assigned to targets to minimize the expected error in the estimates. We refer to this as the focus of attention (FOA) problem. In its general form, FOA is NP-hard and not well approximable. However, for specific geometries we obtain significant approximation results: a 2-approximation algorithm for stereo cameras on a line, a (1 + ∈)-approximation algorithm for any constant ∈ when the cameras are equidistant, and a 1.42-approximation algorithm for equally spaced range sensors on a circle. In addition to constrained geometries, we further investigate the problem for general sensor placement. By reposing as a maximization problem-where the goal is to maximize the number of tracks with bounded error-we are able to leverage results from maximum set-packing to render the problem approximable. We demonstrate the utility of these algorithms in simulation for a target tracking task, and for localizing a team of mobile agents in a sensor network. These results provide insights into sensor/target assignment strategies, as well as sensor placement in a distributed network.

Original languageEnglish (US)
Pages (from-to)225-247
Number of pages23
JournalComputer Vision and Image Understanding
Volume100
Issue number1-2 SPEC. ISS.
DOIs
StatePublished - Oct 2005

Keywords

  • Approximation algorithms
  • Focus of attention
  • Sensor assignment

Fingerprint Dive into the research topics of 'Target tracking with distributed sensors: The focus of attention problem'. Together they form a unique fingerprint.

Cite this