Shadow information spaces: Combinatorial filters for tracking targets

Jingjin Yu, Steven M. Lavalle

Research output: Contribution to journalArticlepeer-review

22 Scopus citations


This paper introduces and solves a problem of maintaining the distribution of hidden targets that move outside the field of view while a sensor sweep is being performed, resulting in a generalization of the sensing aspect of visibility-based pursuit-evasion games. Our solution first applies information space concepts to significantly reduce the general complexity so that information is processed only when the shadow region (all points invisible to the sensors) changes combinatorially or targets pass in and out of the field of view. The cases of distinguishable, partially distinguishable, and completely indistinguishable targets are handled. Depending on whether the targets move nondeterministically or probabilistically, more specific classes of problems are formulated. For each case, efficient filtering algorithms are introduced, implemented, and demonstrated that provide critical information for tasks such as counting, herding, pursuit evasion, and situational awareness.

Original languageEnglish (US)
Article number6112246
Pages (from-to)440-456
Number of pages17
JournalIEEE Transactions on Robotics
Issue number2
StatePublished - Apr 2012
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering


  • Combinatorial filters
  • integer linear programming
  • shadow information spaces
  • target tracking
  • visibility based pursuit evasion


Dive into the research topics of 'Shadow information spaces: Combinatorial filters for tracking targets'. Together they form a unique fingerprint.

Cite this