Department of Computer Science
University of Rochester
October 2009
Motivation
Imagine two teams—seven players each—playing capture the
flag and each player carrying a GPS device that logs its
position every second (see Figure 1 below).
Given that raw and noisy data, how can we automatically and reliably
detect and recognize interesting events that happen in the game?
Can we learn the rules of capture the flag by observing several
rounds? Can we generalize beyond the observations and envision a
"typical game" that would capture the underlying commonalities and
allow us to recognize anomalous events?
How can we use such mined knowledge to predict what is going to happen
next in a given game? Capitalizing on this higher-level knowledge, can we
learn better and more robust strategies that an artificial multi-agent
system can then use to compete with people? What about electronic
assistants that help human teams be more successful? How to
efficiently summarize a long game to a busy person without leaving out
important events? Can we make sensible decisions based on our inferred
results? . . .
Figure 1. A video of two teams (7 players each) playing one round
of capture the flag (CTF). One team has players color-coded in cool
colors, the other team has warm colors. In our version of CTF, the
two "flags" are stationary and are shown as circles near the top and
the bottom of the figure. The horizontal road in the middle of the
image is the territory boundary. One way to achieve victory is to
enter the opponent's circle. The data is shown sped-up and prior to
any denoising or corrections for map errors. The same video, except
in much better quality, is available here
(in Ogg Video format).
Goals
One could continue asking many more important questions in this
fashion. We are currently working on addressing the above issues
while viewing the inherent uncertainty of the world and the
imprecision of the raw data as omnipresent elements that our
methodology has to deal with. In fact, we are investigating the
possibility of coupling the data denoising process with learning and
reasoning tasks in a closed-loop principled way.
Even though the capture the flag domain doesn't capture all the
complexities of life, most of the problems that we are addressing here
clearly have direct analogs in more real-life tasks that artificial
intelligence needs to address—such as improving smart
environments, human-computer interaction, surveillance, assisted
cognition, and battlefield control. In order to immediately test our
approaches across domains, we also experiment with data collected by
people wearing various multi-modal sensory loggers over extended
periods of time (including our own
data—see Figure 2
and Figure 3—and
the Reality Mining
dataset). There, instead of reasoning about game events, typical
games, strategies, etc., we reason about people's everyday activities
and routines, goals, plans, significant locations, and the like.
We experiment with several approaches to representing our data and to
the inherently relational and multi-agent reasoning that these
domains require. More specifically, we focus on application of Markov
logic networks, probabilistic inductive logic programming,
eigenanalysis, relational conditional random fields, and reinforcement
learning to solve the above mentioned problems.
Figure 2. Examples of three trips (red, bright blue, and violet) logged by
a GPS device carried by a person living in Rochester. (Click on the map to enlarge.)
Figure 3. An originally noisy GPS trace "snapped" to a street map
(thick gray lines represent streets) and displayed in our system
that combines denoising, reasoning, and visualization.