The domain of my Phd work lies in the application game theoretic techniques to security domains.
ARMOR and IRIS are two such deployed applications. These
softwares are security assistants that generate randomized schedules for patrolling. We cast these situations
as Stackelberg Games and solve them in realistic time frames.
My other work has focused on real-world deployment of distributed constraint optimization problems.
In DCOPs, my work has primarily focused on
the theoretical aspects of domains where there are unknown reward
constraints.
Current Projects:
Computing Optimal Randomized Resource Allocations for Massive
Security Games: I have been actively involved in the
ARMOR project.
The motivation behind the project is that
predictable allocations of security resources such as police officers,
canine units, or checkpoints can be exploited by potential attackers.
The work applied game-theoretic methods to determine optimal
randomized security policies, including a
fielded application
at the Los Angeles International Airport (LAX). Specifically,
we constructed the game matrix between the defender(s) and the attacker(s)
and find the Stackelberg Equilibrium.
However, the existing
methods do not scale well for problems where a defender
must coordinate schedules for many distinct resources, which may
be subject to complex scheduling constraints. For example, the
scheduling of Federal Air Marshals (FAMs) on commercial flights, which has
complex scheduling constraints.
In our work, we study a class of games that models these and other security
domains where allocating multiple resources is a key issue. We
describe a compact representation of the strategies and payoffs for
this class of games, and introduce a new exact solution algorithm
using this representation. We use Branch and Price and Column Generation,
techniques from Operations Research, to find the probability distribution
directly over the joint schedules for the defender.
This method provides exponential improvements
in both representation size and solution time over the
best known solution algorithms for the more general class of Stackelberg
games. We introduce two additional algorithms that offer
even more dramatic performance improvements for a more specific
class of games with realistic restrictions on the players’ payoff
functions. Finally, we extend the original algorithm to incorporate
different types of resources with additional scheduling constraints,
while still offering comparable performance improvements
over previous algorithms.
We performed comprehensive testing with data from examples and real application
domains, and found that our methods provided compelling performance
advantages.
Current work on this project is focusing on generalizing these concepts
to more types of games (i.e. not just security games). Also, we want to look
at issues of bounded rationality and limited observability and develop robust
algorithms accounting for these factors.
DCOPs in real world: Buoyed by the recent successes in the area of distributed constraint
optimization problems (DCOPs),
this work addresses challenges
faced when applying DCOPs to real-world problems. The expedition
revealed that three fundamental challenges must be addressed
for a large class of real-world domains, requiring design of novel
DCOP algorithms. First, in many domains, agents do not know
the initial payoff matrix and must explore the environment to determine
rewards associated with different variable settings. Second,
the agents have a goal to maximize the total accumulated reward
rather than the instantaneous reward at the end of the run. Third,
limited task-time horizons disallow agents the luxury of full exploration
of their environment and payoff matrices.
In my work, we propose and implement a
set of novel algorithms and provide positive experimental
results. At their core, these new algorithms interweave
decision-theoretic approaches to explore the environment within
the limited time horizon with the DCOP-mandated coordination.
In addition to simulation results, we implement these algorithms on
robots, deploying DCOPs on a distributed mobile sensor network illustrating
the benefits of DCOPs in the real world.
As part of on-going work, we are trying to exhaustively examine
the search space over the various parameters to establish any trends
of dominance of any particular algorithm over others. This will help us
fine tune the agent strategy so as to be able to trade off between
exploration and exploitation of known information.
Also, we are working on deriving mathematical properties of the different
algorithms so that expectation bounds on the performance can be found.
A paper on the work has been accepted at
IJCAI'09.
Images of iRobot Create Robots
on which the algorithms were tested:
