2014
Thanh H. Nguyen, Amulya Yadav, Bo An, Milind Tambe, and Craig Boutilier. 2014. “
Regret-based Optimization and Preference Elicitation for Stackelberg Security Games with Uncertainty .” In National Conference on Artificial Intelligence (AAAI).
AbstractStackelberg security games (SSGs) have been deployed in a
number of real-world domains. One key challenge in these
applications is the assessment of attacker payoffs which may
not be perfectly known. Previous work has studied SSGs
with uncertain payoffs modeled by interval uncertainty and
provided maximin-based robust solutions. In contrast, in this
work we propose the use of the less conservative minimax
regret decision criterion for such payoff-uncertain SSGs and
present the first algorithms for computing minimax regret for
SSGs. We also address the challenge of preference elicitation,
using minimax regret to develop the first elicitation strategies
for SSGs. Experimental results validate the effectiveness of
our approaches.
2014_18_teamcore_aaai2014_mirage.pdf William B. Haskell, Debarun Kar, Fei Fang, Milind Tambe, Sam Cheung, and Elizabeth Denicola. 2014. “
Robust protection of fisheries with COmPASS .” In Innovative applications of Artificial Intelligence (IAAI).
AbstractFish stocks around the world are in danger from illegal fishing. In collaboration with the U.S. Coast Guard
(USCG), we work to defend fisheries from illegal fisherman (henceforth called Lanchas) in the U.S. Gulf of
Mexico. We have developed the COmPASS (Conservative Online Patrol ASSistant) system to design USCG
patrols against the Lanchas. In this application, we face
a population of Lanchas with heterogeneous behavior
who fish frequently. We have some data about these
Lanchas, but not enough to fit a statistical model. Previous security patrol assistants have focused on counterterrorism in one-shot games where adversaries are assumed to be perfectly rational, and much less data about
their behavior is available. COmPASS is novel because:
(i) it emphasizes environmental crime; (ii) it is based on
a repeated Stackelberg game; (iii) it allows for bounded
rationality of the Lanchas and it offers a robust approach
against the heterogeneity of the Lancha population; and
(iv) it can learn from sparse Lancha data. We report the
effectiveness of COmPASS in the Gulf in our numerical experiments based on real fish data. The COmPASS
system is to be tested by USCG.
2014_17_teamcore_iaai_2014.pdf F. M. Delle Fave, M. Brown, C. Zhang, E. Shieh, A.X. Jiang, H. Rosoff, M. Tambe, and J.P. Sullivan. 2014. “
Security Games in the Field: an Initial Study on a Transit System (Extended Abstract) .” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS) [Short paper].
AbstractGoing beyond previous deployments of Stackeleberg security games
(SSGs), this paper presents actual results from the field using a
novel deployed system referred to as the Multi-Operation Patrol
Scheduling System (MOPSS). MOPSS generates patrols for a transit system considering three different threats: fare evasion (FE),
terrorism (CT) and crime (CR). In so doing, this paper present four
contributions: (i) we propose the first multi-operation patrolling
system; (ii) MOPSS is the first system to use Markov decision processes (MDPs) to handle uncertain interruptions in the execution of
patrol schedules; (iii) we are the first to deploy a new Opportunistic Security Game model, where the adversary, a criminal, makes
opportunistic decisions on when and where to commit crimes and,
most importantly (iv) we evaluate MOPSS via real-world deployments, providing some of the first real-world data from security
games in the field.
2014_10_teamcore_dellefave_aamas_2014_camera_ready.pdf F. M. Delle Fave, M. Brown, C. Zhang, E. Shieh, A.X. Jiang, H. Rosoff, M. Tambe, and J.P. Sullivan. 2014. “
Security Games in the Field: Deployments on a Transit System .” In: Lecture Notes in Artificial Intelligence. Springer. In Press.
AbstractThis paper proposes the Multi-Operation Patrol Scheduling
System (MOPSS), a new system to generate patrols for transit system.
MOPSS is based on five contributions. First, MOPSS is the first system
to use three fundamentally different adversary models for the threats of
fare evasion, terrorism and crime, generating three significantly different types of patrol schedule. Second, to handle uncertain interruptions
in the execution of patrol schedules, MOPSS uses Markov decision processes (MDPs) in its scheduling. Third, MOPSS is the first system to
account for joint activities between multiple resources, by employing the
well known SMART security game model that tackles coordination between defender’s resources. Fourth, we are also the first to deploy a new
Opportunistic Security Game model, where the adversary, a criminal,
makes opportunistic decisions on when and where to commit crimes.
Our fifth, and most important, contribution is the evaluation of MOPSS
via real-world deployments, providing data from security games in the
field.
2014_29_teamcore_delle_fave14c.pdf Haifeng Xu, Fei Fang, Albert Xin Jiang, Vincent Conitzer, Shaddin Dughmi, and Milind Tambe. 2014. “
Solving Zero-Sum Security Games in Discretized Spatio-Temporal Domains .” In 28th Conference on Artificial Intelligence (AAAI 2014). Québec, Canada.
AbstractAmong the many deployment areas of Stackelberg Security games, a major area involves games played out in
space and time, which includes applications in multiple
mobile defender resources protecting multiple mobile
targets. Previous algorithms for such spatio-temporal
security games fail to scale-up and little is known of
the computational complexity properties of these problems. This paper provides a novel oracle-based algorithmic framework for a systematic study of different problem variants of computing optimal (minimax) strategies
in spatio-temporal security games. Our framework enables efficient computation of a minimax strategy when
the problem admits a polynomial-time oracle. Furthermore, for the cases in which efficient oracles are difficult to find, we propose approximations or prove hardness results.
2014_21_teamcore_ferry_algorithm.pdf Matthew Brown, Sandhya Saisubramanian, Pradeep Varakantham, and Milind Tambe. 2014. “
STREETS: Game-Theoretic Traffic Patrolling with Exploration and Exploitation .” In Innovative applications of Artificial Intelligence (IAAI).
AbstractTo dissuade reckless driving and mitigate accidents,
cities deploy resources to patrol roads. In this paper, we
present STREETS, an application developed for the city
of Singapore, which models the problem of computing randomized traffic patrol strategies as a defenderattacker Stackelberg game. Previous work on Stackelberg security games has focused extensively on counterterrorism settings. STREETS moves beyond counterterrorism and represents the first use of Stackelberg
games for traffic patrolling, in the process providing a
novel algorithm for solving such games that addresses
three major challenges in modeling and scale-up. First,
there exists a high degree of unpredictability in travel
times through road networks, which we capture using
a Markov Decision Process for planning the patrols of
the defender (the police) in the game. Second, modeling all possible police patrols and their interactions
with a large number of adversaries (drivers) introduces
a significant scalability challenge. To address this challenge we apply a compact game representation in a
novel fashion combined with adversary and state sampling. Third, patrol strategies must balance exploitation
(minimizing violations) with exploration (maximizing
omnipresence), a tradeoff we model by solving a biobjective optimization problem. We present experimental results using real-world traffic data from Singapore.
This work is done in collaboration with the Singapore
Ministry of Home Affairs and is currently being evaluated by the Singapore Police Force.
2014_22_teamcore_iaai2014traffic_camera.pdf L. S. Marcolino, H. Xu, A.X. Jiang, M. Tambe, and E. Bowring. 2014. “
Team Formation in Large Action Spaces .” In In 17th International Workshop on Coordination, Organizations, Institutions and Norms (COIN 2014). Paris, France.
AbstractRecent work has shown that diverse teams can outperform
a uniform team made of copies of the best agent. However, there are
fundamental questions that were not asked before. When should we use
diverse or uniform teams? How does the performance change as the action
space or the teams get larger? Hence, we present a new model of diversity
for teams, that is more general than previous models. We prove that
the performance of a diverse team improves as the size of the action
space gets larger. Concerning the size of the diverse team, we show that
the performance converges exponentially fast to the optimal one as we
increase the number of agents. We present synthetic experiments that
allow us to gain further insights: even though a diverse team outperforms
a uniform team when the size of the action space increases, the uniform
team will eventually again play better than the diverse team for a large
enough action space. We verify our predictions in a system of Go playing
agents, where we show a diverse team that improves in performance as
the board size increases, and eventually overcomes a uniform team.
2014_20_teamcore_coin2014.pdf Jun-young Kwak, Pradeep Varakantham, Rajiv Maheswaran, Yu-Han Chang, Milind Tambe, Burcin Becerik-Gerber, and Wendy Wood. 2014. “
TESLA: An Extended Study of an Energy-saving Agent that Leverages Schedule Flexibility .” Journal of Autonomous Agents and Multiagent Systems, JAAMAS, 28, 4, Pp. 605-636.
AbstractThis paper presents TESLA, an agent for optimizing energy usage in commercial buildings. TESLA’s key insight is that adding flexibility to event/meeting
schedules can lead to significant energy savings. This paper provides four key contributions: (i) online scheduling algorithms, which are at the heart of TESLA, to solve
a stochastic mixed integer linear program (SMILP) for energy-efficient scheduling of
incrementally/dynamically arriving meetings and events; (ii) an algorithm to effectively identify key meetings that lead to significant energy savings by adjusting their
flexibility; (iii) an extensive analysis on energy savings achieved by TESLA; and (iv)
surveys of real users which indicate that TESLA’s assumptions of user flexibility hold
in practice. TESLA was evaluated on data gathered from over 110,000 meetings held
at nine campus buildings during an eight month period in 2011–2012 at the University of Southern California (USC) and the Singapore Management University (SMU).
These results and analysis show that, compared to the current systems, TESLA can
substantially reduce overall energy consumption.
2014_2_teamcore_tesla_jaamas_r1_1.pdf Chao Zhang, Albert Xin Jiang, Martin B. Short, Jeffrey P. Brantingham, and Milind Tambe. 2014. “
Towards a game theoretic approach for defending against crime diffusion .” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS) [SHORT PAPER].
AbstractIn urban transportation networks, crime diffuses as criminals travel
through the networks and look for illicit opportunities. It is important to first model this diffusion in order to recommend actions
or patrol policies to control the diffusion of such crime. Previously,
game theory has been used for such patrol policy recommendations,
but these applications of game theory for security have not modeled
the diffusion of crime that comes about due to criminals seeking
opportunities; instead the focus has been on highly strategic adversaries that plan attacks in advance. To overcome this limitation of
previous work, this paper provides the following key contributions.
First, we provide a model of crime diffusion based on a quantal
biased random movement (QBRM) of criminals opportunistically
and repeatedly seeking targets. Within this model, criminals react
to real-time information, rather than strategically planning their attack in advance. Second, we provide a game-theoretic approach to
generate randomized patrol policies for controlling such diffusion.
2014_11_teamcore_chao_2014_extend.pdf Eric Shieh, Albert Xin Jiang, Amulya Yadav, Pradeep Varakantham, and Milind Tambe. 2014. “
Unleashing Dec-MDPs in Security Games: Enabling Effective Defender Teamwork .” In European Conference on Artificial Intelligence (ECAI).
AbstractMultiagent teamwork and defender-attacker security games are
two areas that are currently receiving significant attention within
multiagent systems research. Unfortunately, despite the need for effective teamwork among multiple defenders, little has been done to
harness the teamwork research in security games. This paper is the
first to remedy this situation by integrating the powerful teamwork
mechanisms offered by Dec-MDPs into security games. We offer the
following novel contributions in this paper: (i) New models of security games where a defender team’s pure strategy is defined as a DecMDP policy for addressing coordination under uncertainty; (ii) New
algorithms based on column generation that enable efficient generation of mixed strategies given this new model; (iii) Handling global
events during defender execution for effective teamwork; (iv) Exploration of the robustness of randomized pure strategies. The paper
opens the door to a potentially new area combining computational
game theory and multiagent teamwork.
2014_25_teamcore_ecai_main_decmdp_security_final.pdf Rong Yang, Benjamin Ford, Milind Tambe, and Andrew Lemieux. 2014. “
Adaptive Resource Allocation for Wildlife Protection against Illegal Poachers.” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS).
AbstractIllegal poaching is an international problem that leads to the extinction of species and the destruction of ecosystems. As evidenced by dangerously dwindling populations of endangered species, existing anti-poaching mechanisms are insufficient. This paper introduces the Protection Assistant for Wildlife Security (PAWS) application - a joint deployment effort done with researchers at Uganda’s Queen Elizabeth National Park (QENP) with the goal of improving wildlife ranger patrols. While previous works have deployed applications with a game-theoretic approach (specifically Stackelberg Games) for counter-terrorism, wildlife crime is an important domain that promotes a wide range of new deployments. Additionally, this domain presents new research challenges and opportunities related to learning behavioral models from collected poaching data. In addressing these challenges, our first contribution is a behavioral model extension that captures the heterogeneity of poachers’ decision making processes. Second, we provide a novel framework, PAWS-Learn, that incrementally improves the behavioral model of the poacher population with more data. Third, we develop a new algorithm, PAWS-Adapt, that adaptively improves the resource allocation strategy against the learned model of poachers. Fourth, we demonstrate PAWS’s potential effectiveness when applied to patrols in QENP, where PAWS will be deployed.
2014_7_teamcore_aamas2014_yang.pdf Thanh Nguyen, Albert Jiang, and Milind Tambe. 2014. “
Stop the Compartmentalization: Unified Robust Algorithms for Handling Uncertainties in Security Games.” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS).
AbstractGiven the real-world applications of Stackelberg security games (SSGs), addressing uncertainties in these games is a major challenge. Unfortunately, we lack any unified computational framework for handling uncertainties in SSGs. Current state-of-the-art has provided only compartmentalized robust algorithms that handle uncertainty exclusively either in the defender’s strategy or in adversary’s payoff or in the adversary’s rationality, leading to potential failures in real-world scenarios where a defender often faces multiple types of uncertainties. Furthermore, insights for improving performance are not leveraged across the compartments, leading to significant losses in quality or efficiency. In this paper, we provide the following main contributions: 1) we present the first unified framework for handling the uncertainties explored in SSGs; 2) based on this unified framework, we propose the first set of “unified” robust algorithms to address combinations of these uncertainties; 3) we introduce approximate scalable robust algorithms for handling these uncertainties that leverage insights across compartments; 4) we present experiments demonstrating solution quality and runtime advantages of our algorithms.
2014_6_teamcore_mm_extended.pdf