Optimal motion strategies for range-only constrained multisensor target tracking

Ke Zhou, Stergios I. Roumeliotis

Research output: Contribution to journalArticlepeer-review

80 Scopus citations


In this paper, we study the problem of optimal trajectory generation for a team of mobile sensors tracking a moving target using distance-only measurements. This problem is shown to be NP-Hard, in general, when constraints are imposed on the speed of the sensors. We propose two algorithms, modified Gauss-Seidel relaxation and linear programming (LP) relaxation, for determining the set of feasible locations that each sensor should move to in order to collect the most informative measurements; i.e., distance measurements that minimize the uncertainty about the position of the target. These algorithms are applicable regardless of the process model that is employed for describing the motion of the target, while their computational complexity is linear in the number of sensors. Extensive simulation results are presented demonstrating that the performance attained with the proposed methods is comparable to that obtained with grid-based exhaustive search, whose computational cost is exponential in the number of sensors, and significantly better than that of a random, toward the target, motion strategy.

Original languageEnglish (US)
Pages (from-to)1168-1185
Number of pages18
JournalIEEE Transactions on Robotics
Issue number5
StatePublished - 2008

Bibliographical note

Funding Information:
Manuscript received August 6, 2007; revised March 5, 2008. First published September 19, 2008; current version published October 31, 2008. This paper was recommended for publication by Associate Editor D. Sun and Editor L. Parker upon evaluation of the reviewers’ comments. This work was supported in part by the University of Minnesota (DTC) and in part by the National Science Foundation under Grant EIA-0324864, Grant IIS-0643680, and Grant IIS-0811946.


  • Active sensing
  • Linear programming (LP) relaxation (LPR)
  • Mobile sensors
  • Modified Gauss-Seidel relaxation (MGSR)
  • Target tracking


Dive into the research topics of 'Optimal motion strategies for range-only constrained multisensor target tracking'. Together they form a unique fingerprint.

Cite this