COLLOQUIUM
Department of Computer Science and Engineering
University of South Carolina

Combinatorial Structures and Filter Design in Information Spaces
Jingjin Yu
Department of Electrical and Computer Engineering
University of Illinois at Urbana-Champaign

Date: April 4, 2013
Time: 1330-1430 (1:30pm-2:30pm)
Place: Swearingen 3D05 (Former Staff Lounge)

Abstract

As we know, Kalman filters, given their effectiveness in handling
probabilistic events, play an important role in the processing of
probabilistic sensor information, such as point clouds gathered from
laser scanners. However, not all data is amenable to probabilistic
analysis - some problems induce inherently combinatorial data
structures. For these problems, a combinatorial filtering approach is
necessary. In this talk, I discuss two such robotics (sensor fusion)
problems. The first problem generalizes visibility-based
pursuit-evasion games and seeks to maintain the distribution of hidden
targets that move outside the field-of-view of the pursuers while a
sensor sweep is being performed. Observing that key events happen only
when the shadow region (all points invisible to the sensors) changes
combinatorially or when targets pass in and out of the field-of-view,
we can significantly reduce the amount of sensor information that we
store, without discarding any useful information for computing the
distribution of the hidden targets. This allows us to "live" inside a
derived information space, which gives rises to efficient
algorithms. These filtering algorithms provide critical information
for tasks such as counting, herding, pursuit-evasion, and situational
awareness in general.  Next, we study the problem of using sparse,
heterogeneous sensors to verify the stories (i.e., path samples) of
agents (robots or people). Since there are two sets of data, the
combinatorial filter for this problem can be built in two ways: Using
a filter (an automaton) built from sensor data to process the story or
using a filter built from the story to process the sensor data. Both
approaches lead to dynamic programming based (optimally) efficient
algorithms.  In addition to exact path inference, our method also
applies to approximate path inference that allows errors in the
story. Besides immediate applicability toward security and forensics
problems, the idea of external verification is promising in
complementing design time model verification.

Jingjin Yu received a B.S. in materials science and engineering from
USTC, Hefei, China (1998). He holds M.S. degrees in chemistry
(University of Chicago, 2000), mathematics (University of Illinois at
Chicago, 2001), and computer science (University of Illinois at Urbana
Champain, 2010). He is currently a Ph.D. candidate with the Department
of Electrical and Computer Engineering at the University of Illinois
at Urbana-Champaign. His research interests include robotics and
control theory.