next up previous
Next: Introduction

Shadow Information Spaces:
Combinatorial Filters for Tracking Targets

Jingjin Yu   Steven M. LaValle
jyu18@uiuc.edu   lavalle@uiuc.edu
Department of Electrical and Computer Engineering   Department of Computer Science
University of Illinois   University of Illinois
Urbana, IL 61801 USA   Urbana, IL 61801 USA


Abstract:

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 substantial generalization of visibility-based pursuit-evasion games. Our solution first applies information space concepts to dramatically 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.




next up previous
Next: Introduction
Jingjin Yu 2011-01-18