Research Projects
Andreas Krause,
Mani Chandy, Rob Clayton, Tom Heaton
et al.
Can one use cell phones to detect earthquakes?
We tackle a fundamental question in cyber-physical systems: What is the ideal structure of systems that detect critical events – such as earthquakes – by using data from large numbers of sensors held and managed by ordinary people in the community? The approach is to develop theory about widely-distributed sense and respond systems, using dynamic – and possibly unreliable – networks using sensors and responders installed and managed by ordinary citizens, and to apply the theory to problems important to society, such as responding to earthquakes.
We tackle a fundamental question in cyber-physical systems: What is the ideal structure of systems that detect critical events – such as earthquakes – by using data from large numbers of sensors held and managed by ordinary people in the community? The approach is to develop theory about widely-distributed sense and respond systems, using dynamic – and possibly unreliable – networks using sensors and responders installed and managed by ordinary citizens, and to apply the theory to problems important to society, such as responding to earthquakes.
- Project
website of the Community Seismic Network
- An IPSN 2010 paper with Matt Faulkner and Daniel Golovin on distributed online sensor selection [pdf]
- An IPSN 2008 paper with Eric Horvitz, Aman Kansal and Feng Zhao
on Community Sensing for urban traffic
prediction from GPS devices [pdf]
We are interested in practical algorithms with theoretical guarantees
for challenging active learning and experimental design problems. We
recently introduced a structural property, adaptive submodularity,
which generalizes the classical notion of submodular functions to
adaptive policies. We show that if a problem satisfies this property,
an efficient, adaptive greedy algorithm guarantees near-optimal
policies. We further show that this property arises in diverse
applications including active learning, Bayesian sequential
experimental design and adaptive viral marketing.
Which ads should we display in sponsored search in order to
maximize our revenue? How should we dynamically rank information
sources to
maximize value of information? Which sensors in a sensor network should
we
activate when in order to best monitor some unknown phenomenon over
time?
These and other problems can be
formalized as bandit problems optimization with complex, structured
decision spaces.
We are developing novel algorithms and analyze them in the no-regret
model. We evaluate our approaches on several
real-world information gathering problems.
Convex optimization has become a main workhorse
for many machine learning algorithms during the past ten years. When
minimizing a convex loss function for, e.g., training a Support Vector
Machine, we can rest assured to efficiently find an optimal solution,
even for large problems. In recent years, another fundamental problem
structure, which has similar beneficial properties, has emerged as very
useful in a variety of machine learning applications: Submodularity is
an intuitive diminishing returns property, stating that adding an
element to a smaller set helps more than adding it to a larger set.
Similarly to convexity, submodularity allows one to efficiently find
provably (near-) optimal solutions. We are studying submodularity and
its
implications for challenging sparse representation, inference and
learning problems.
- Tutorials
(with Carlos Guestrin): ICML
2008, IJCAI 2009
- Matlab/Octave Toolbox for submodular optimization and a JMLR paper about it [pdf]
- See our NIPS 2010 paper with Peter Stobbe on efficiently minimizing decomposable submodular functions [pdf]
- An ICML 2010 paper with Volkan Cevher on a connection between submodularity and sparse representations [pdf]
- An ICML 2010 paper with Ryan Gomes on large scale budgeted nonparametric learning [pdf]
- Our KDD 2010 paper with Jure Leskovec and Manuel Gomez-Rodriguez
on a structure learning problem of inferring influential news websites
and blogs [pdf]
We are interested in rich probabilistic models
for modeling interaction in navigation and activity recognition. As an
example, we study the safe navigation of a mobile robot through crowds
of
dynamic agents with uncertain trajectories. Existing algorithms suffer
from the "freezing robot" problem: once the environment surpasses a
certain level of complexity, the planner decides that all forward paths
are unsafe, and the robot freezes in place (or performs unnecessary
maneuvers) to avoid collisions. Our key insight is that dynamic agents
solve the frozen robot problem by engaging in "joint collision
avoidance": They cooperatively make room to create feasible
trajectories. We develop IGP, a nonparametric statistical model based
on Dependent Output Gaussian Processes that can estimate crowd
interaction from data. Our model naturally captures the non-Markov
nature of agent trajectories, as well as their goal-driven navigation.
- Our
project webpage with some videos
- Our IROS 2010 paper with Pete Trautman
on the IGP model [pdf]
We
identify a key
structural property of many observation selection
problems: submodularity, an
intuitive diminishing returns property. Exploiting this property allows
to obtain efficient approximation algorithms
with
provable guarantees,
as well as drastically speeding up algorithms. We use our algorithms
for applications such as sensor placement in drinking water
distribution and environmental monitoring using robotic sensors.
- A short overview paper with Carlos Guestrin on this topic that appeared as Cover Feature in IEEE Computer Magazine.
- Our JMLR paper with Carlos Guestrin, Brendan McMahan and Anupam Gupta on the Saturate algorithm for robust submodular optimization [pdf]
- Our JAIR paper with Carlos Guestrin on VOIDP for optimal value of information in chain models [pdf]
- Our IJCAI 2009 paper with Amarjeet Singh and William Kaiser on
adaptive informative path planning [pdf]