Publications

2013
Albert Xin Jiang, Zhengyu Yin, Chao Zhang, Milind Tambe, and Sarit Kraus. 2013. “Game-theoretic Randomization for Security Patrolling with Dynamic Execution Uncertainty.” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS).Abstract
In recent years there has been extensive research on game-theoretic models for infrastructure security. In time-critical domains where the security agency needs to execute complex patrols, execution uncertainty (interruptions) affect the patroller’s ability to carry out their planned schedules later. Indeed, experiments in this paper show that in some real-world domains, small fractions of execution uncertainty can have a dramatic impact. The contributions of this paper are threefold. First, we present a general Bayesian Stackelberg game model for security patrolling in dynamic uncertain domains, in which the uncertainty in the execution of patrols is represented using Markov Decision Processes. Second, we study the problem of computing Stackelberg equilibrium for this game. We show that when the utility functions have a certain separable structure, the defender’s strategy space can be compactly represented, and we can reduce the problem to a polynomial-sized optimization problem. Finally, we apply our approach to fare inspection in the Los Angeles Metro Rail system. Numerical experiments show that patrol schedules generated using our approach outperform schedules generated using a previous algorithm that does not consider execution uncertainty.
2013_6_teamcore_aamas13-execution.pdf
R. Yang, C. Kiekintvled, F. Ordonez, M. Tambe, and R. John. 2013. “Improving Resource Allocation Strategies Against Human Adversaries in Security Games: An Extended Study .” Artificial Intelligence Journal (AIJ), 195, Pp. 440-469.Abstract
Stackelberg games have garnered significant attention in recent years given their deployment for real world security. Most of these systems, such as ARMOR, IRIS and GUARDS have adopted the standard game-theoretical assumption that adversaries are perfectly rational, which is standard in the game theory literature. This assumption may not hold in real-world security problems due to the bounded rationality of human adversaries, which could potentially reduce the effectiveness of these systems. In this paper, we focus on relaxing the unrealistic assumption of perfectly rational adversary in Stackelberg security games. In particular, we present new mathematical models of human adversaries’ behavior, based on using two fundamental theory/method in human decision making: Prospect Theory (PT) and stochastic discrete choice model. We also provide methods for tuning the parameters of these new models. Additionally, we propose a modification of the standard quantal response based model inspired by rankdependent expected utility theory. We then develop efficient algorithms to compute the best response of the security forces when playing against the different models of adversaries. In order to evaluate the effectiveness of the new models, we conduct comprehensive experiments with human subjects using a web-based game, comparing them with models previously proposed in the literature to address the perfect rationality assumption on part of the adversary. Our experimental results show that the subjects’ responses follow the assumptions of our new models more closely than the previous perfect rationality assumption. We also show that the defender strategy produced by our new stochastic discrete choice model outperform the previous leading contender for relaxing the assumption of perfect rationality.Furthermore, in a separate set of experiments, we show the benefits of our modified stochastic model (QRRU) over the standard model (QR).
2013_5_teamcore_aij_2012_yang_final.pdf
2013. “Mitigating Multi-path Fading in a Mobile Mesh Network .” Ad-Hoc Networks Journal, 11, 4, Pp. 1510-1521.Abstract
By using robots as routers, a team of networked robots can provide a communication substrate to establish a wireless mesh network. The mobile mesh network can autonomously optimize its configuration, increasing performance. One of the main sources of radio signal fading in such a network is multi-path propagation, which can be mitigated by moving the senders or the receivers on the distance of the order of a wavelength. In this paper, we measure the performance gain when robots are allowed to make such small movements and find that it may be as much as 270%. Our main contribution is the design of a system that allows robots to cooperate and improve the real-world network throughput via a practical solution. We model the problem of which robots to move as a distributed constraint optimization problem (DCOP). Our study includes four local metrics to estimate global throughput.
2013_27_teamcore_adhoc-dcee.pdf
Chao Zhang, Albert Xin Jiang, Martin B. Short, P. Jeffrey Brantingham, and Milind Tambe. 2013. “Modeling Crime diffusion and crime suppression on transportation networks: An initial report.” In SNSC 2013: The AAAI Fall Symposium 2013 on Social Networks and Social Contagion.Abstract
In 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 gametheoretic approach to generate randomized patrol policies for controlling such diffusion.
2013_29_teamcore_crime_diffusion_model.pdf
Thanh H. Nguyen, Amos Azaria, James Pita, Rajiv Maheswaran, Sarit Kraus, and Milind Tambe. 2013. “Modeling Human Adversary Decision Making in Security Games: An Initial Report (Extended Abstract) .” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS) [SHORT PAPER].Abstract
Motivated by recent deployments of Stackelberg security games (SSGs), two competing approaches have emerged which either integrate models of human decision making into game-theoretic algorithms or apply robust optimization techniques that avoid adversary modeling. Recently, a robust technique (MATCH) has been shown to significantly outperform the leading modeling-based algorithms (e.g., Quantal Response (QR)) even in the presence of significant amounts of subject data. As a result, the effectiveness of using human behaviors in solving SSGs remains in question. We study this question in this paper.
2013_9_teamcore_ext103-nguyen.pdf
Albert Xin Jiang, Thanh H. Nguyen, Milind Tambe, and Ariel D. Procaccia. 2013. “Monotonic Maximin: A Robust Stackelberg Solution Against Boundedly Rational Followers .” In Conference on Decision and Game Theory for Security (GameSec).Abstract
There has been recent interest in applying Stackelberg games to infrastructure security, in which a defender must protect targets from attack by an adaptive adversary. In real-world security settings the adversaries are humans and are thus boundedly rational. Most existing approaches for computing defender strategies against boundedly rational adversaries try to optimize against specific behavioral models of adversaries, and provide no quality guarantee when the estimated model is inaccurate. We propose a new solution concept, monotonic maximin, which provides guarantees against all adversary behavior models satisfying monotonicity, including all in the family of Regular Quantal Response functions. We propose a mixed-integer linear program formulation for computing monotonic maximin. We also consider top-monotonic maximin, a related solution concept that is more conservative, and propose a polynomial-time algorithm for top-monotonic maximin.
2013_31_teamcore_robustqr.pdf
Leandro Soriano Marcolino, Albert Xin Jiang, and Milind Tambe. 2013. “Multi-agent Team Formation: Diversity Beats Strength? .” In International Joint Conference on Artificial Intelligence (IJCAI).Abstract
Team formation is a critical step in deploying a multi-agent team. In some scenarios, agents coordinate by voting continuously. When forming such teams, should we focus on the diversity of the team or on the strength of each member? Can a team of diverse (and weak) agents outperform a uniform team of strong agents? We propose a new model to address these questions. Our key contributions include: (i) we show that a diverse team can overcome a uniform team and we give the necessary conditions for it to happen; (ii) we present optimal voting rules for a diverse team; (iii) we perform synthetic experiments that demonstrate that both diversity and strength contribute to the performance of a team; (iv) we show experiments that demonstrate the usefulness of our model in one of the most difficult challenges for Artificial Intelligence: Computer Go.
2013_18_teamcore_ijcai13.pdf
Fei Fang, Albert Xin Jiang, and Milind Tambe. 2013. “Optimal Patrol Strategy for Protecting Moving Targets with Multiple Mobile Resources .” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS).Abstract
Previous work on Stackelberg Security Games for scheduling security resources has mostly assumed that the targets are stationary relative to the defender and the attacker, leading to discrete game models with finite numbers of pure strategies. This paper in contrast focuses on protecting mobile targets that lead to a continuous set of strategies for the players. The problem is motivated by several real-world domains including protecting ferries with escorts and protecting refugee supply lines. Our contributions include: (i) a new game model for multiple mobile defender resources and moving targets with a discretized strategy space for the defender and a continuous strategy space for the attacker; (ii) an efficient linearprogram-based solution that uses a compact representation for the defender’s mixed strategy, while accurately modeling the attacker’s continuous strategy using a novel sub-interval analysis method; (iii) a heuristic method of equilibrium refinement for improved robustness and (iv) detailed experimental analysis in the ferry protection domain.
2013_8_teamcore_fp052-fang.pdf
Francesco Maria Delle Fave, Yundi Qian, Albert Xin Jiang, Matthew Brown, and Milind Tambe. 2013. “Planning and Learning in Security Games .” In ACM SigEcom Exchanges, 3rd ed. Vol. 11.Abstract
We present two new critical domains where security games are applied to generate randomized patrol schedules. For each setting, we present the current research that we have produced. We then propose two new challenges to build accurate schedules that can be deployed effectively in the real world. The first is a planning challenge. Current schedules cannot handle interruptions. Thus, more expressive models, that allow for reasoning over stochastic actions, are needed. The second is a learning challenge. In several security domains, data can be used to extract information about both the environment and the attacker. This information can then be used to improve the defender’s strategies.
2013_22_teamcore_sigecom2013.pdf
Nan Li, Jun-young Kwak, Burcin Becerik-Gerber, and Milind Tambe. 2013. “Predicting HVAC Energy Consumption in Commercial Buildings using Multiagent Systems .” In International Symposium on Automation and Robotics in Construction (ISARC).Abstract
Energy consumption in commercial buildings has been increasing rapidly in the past decade. The knowledge of future energy consumption can bring significant value to commercial building energy management. For example, prediction of energy consumption decomposition helps analyze the energy consumption patterns and efficiencies as well as waste, and identify the prime targets for energy conservation. Moreover, prediction of temporal energy consumption enables building managers to plan out the energy usage over time, shift energy usage to off-peak periods, and make more effective energy purchase plans. This paper proposes a novel model for predicting heating, ventilation and air conditioning (HVAC) energy consumption in commercial buildings. The model simulates energy behaviors of HVAC systems in commercial buildings, and interacts with a multiagent systems (MAS) based framework for energy consumption prediction. Prediction is done on a daily, weekly and monthly basis. Ground truth energy consumption data is collected from a test bed office building over 267 consecutive days, and is compared to predicted energy consumption for the same period. Results show that the prediction can match 92.6 to 98.2% of total HVAC energy consumption with coefficient of variation of the root mean square error (CV-RMSE) values of 7.8 to 22.2%. Ventilation energy consumption can be predicted at high accuracies (over 99%) and low variations (CV-RMSE values of 3.1 to 16.3%), while cooling energy consumption accounts for majority of inaccuracies and variations in total energy consumption prediction.
2013_23_teamcore_camera_ready_predicting_hvac_energy_consumption_in_commercial_buildings_using_multiagent_systems.pdf
Fei Fang, Albert Xin Jiang, and Milind Tambe. 2013. “Protecting Moving Targets with Multiple Mobile Resources .” Journal of Artificial Intelligence Research, 48, Pp. 583-634.Abstract
In recent years, Stackelberg Security Games have been successfully applied to solve resource allocation and scheduling problems in several security domains. However, previous work has mostly assumed that the targets are stationary relative to the defender and the attacker, leading to discrete game models with finite numbers of pure strategies. This paper in contrast focuses on protecting mobile targets that leads to a continuous set of strategies for the players. The problem is motivated by several real-world domains including protecting ferries with escort boats and protecting refugee supply lines. Our contributions include: (i) A new game model for multiple mobile defender resources and moving targets with a discretized strategy space for the defender and a continuous strategy space for the attacker. (ii) An efficient linear-programming-based solution that uses a compact representation for the defender’s mixed strategy, while accurately modeling the attacker’s continuous strategy using a novel sub-interval analysis method. (iii) Discussion and analysis of multiple heuristic methods for equilibrium refinement to improve robustness of defender’s mixed strategy. (iv) Discussion of approaches to sample actual defender schedules from the defender’s mixed strategy. (iv) Detailed experimental analysis of our algorithms in the ferry protection domain.
2013_34_teamcore_jair_ferry.pdf
Jason Tsai. 2013. “Protecting Networks Against Diffusive Attacks: Game-Theoretic Resource Allocation for Contagion Mitigation ”.Abstract
Many real-world situations involve attempts to spread influence through a social network. For example, viral marketing is when a marketer selects a few people to receive some initial advertisement in the hopes that these ‘seeds’ will spread the news. Even peacekeeping operations in one area have been shown to have a contagious effect on the neighboring vicinity. Each of these domains also features multiple parties seeking to maximize or mitigate a contagious effect by spreading its own influence among a select few seeds, naturally yielding an adversarial resource allocation problem. My work models the interconnected network of people as a graph and develops algorithms to optimize resource allocation in these networked competitive contagion scenarios. Game-theoretic resource allocation in the past has not considered domains with both a networked structure and contagion effects, rendering them unusable in critical domains such as rumor control, counterinsurgency, and crowd management. Networked domains without contagion effects already present computational challenges due to the large scale of the action space. To address this issue, my first contribution proposed efficient game-theoretic allocation algorithms for the graph-based urban road network domain. This work still provides the only polynomialtime algorithm for allocating vehicle checkpoints through a city, giving law enforcement officers an efficient tool to combat terrorists making their way to potential points of attack. Second, I have provided the first game-theoretic treatment for contagion mitigation in social networks and given practitioners the first principled techniques for such vital concerns as rumor control and counterinsurgency. Finally, I extended my work on game-theoretic contagion mitigation to address uncertainty about the network structure to find that, contrary to what evidence and intuition suggest, heuristic sampling approaches provide near-optimal solutions across a wide range of generative graph models and uncertainty models. Thus, despite extreme practical challenges in attaining accurate social network information, my techniques remain near-optimal across numerous forms of uncertainty in multiple synthetic and real-world graph structures. Beyond optimization of resource allocation, I have further studied contagion effects to understand the effectiveness of such resources. First, I created an evacuation simulation, ESCAPES, to explore the interaction of pedestrian fear contagion and authority fear mitigation during an evacuation. Second, using this simulator, I have advanced the frontier in contagion modeling by developing empirical evaluation methods for comparing and calibrating computational contagion models that are critical in crowd simulations and evacuation modeling. Finally, I have also conducted an examination of agent-human emotional contagion to inform the rising use of simulations for personnel training in emotionally-charged situations.
2013_24_teamcore_jasontsai-dissertation.pdf
Nupul Kukreja, William G. J. Halfond, and Milind Tambe. 2013. “Randomizing Regression Tests using Game Theory .” In International conference on Automated Software Engineering (ASE).Abstract
As software evolves, the number of test-cases in the regression test suites continues to increase, requiring testers to prioritize their execution. Usually only a subset of the test cases is executed due to limited testing resources. This subset is often known to the developers who may try to “game” the system by committing insufficiently tested code for parts of the software that will not be tested. In this new ideas paper, we propose a novel approach for randomizing regression test scheduling, based on Stackelberg games for deployment of scarce resources. We apply this approach to randomizing test cases in such a way as to maximize the testers’ expected payoff when executing the test cases. Our approach accounts for resource limitations (e.g., number of testers) and provides a probabilistic distribution for scheduling test cases. We provide an example application of our approach showcasing the idea of using Stackelberg games for randomized regression test scheduling.
2013_32_teamcore_ase.pdf
Rong Yang, Albert Xin Jiang, Milind Tambe, and Fernando Ordo´nez. 2013. “Scaling-up Security Games with Boundedly Rational Adversaries: A Cutting-plane Approach .” In International Joint Conference on Artificial Intelligence (IJCAI).Abstract
To improve the current real-world deployments of Stackelberg security games (SSGs), it is critical now to efficiently incorporate models of adversary bounded rationality in large-scale SSGs. Unfortunately, previously proposed branch-and-price approaches fail to scale-up given the non-convexity of such models, as we show with a realization called COCOMO. Therefore, we next present a novel cutting-plane algorithm called BLADE to scale-up SSGs with complex adversary models,with three key novelties: (i) an efficient scalable separation oracle to generate deep cuts; (ii) a heuristic that uses gradient to further improve the cuts; (iii) techniques for quality-efficiency tradeoff.
2013_19_teamcore_ijcai13_yang.pdf
Jason Tsai, Yundi Qian, Yevgeniy Vorobeychik, Christopher Kiekintveld, and Milind Tambe. 2013. “Security Games with Contagion: Handling Asymmetric Information .” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS) [SHORT PAPER].Abstract
Counterinsurgency, which is the effort to mitigate support for an opposing organization, is one such domain that has been studied recently and past work has modeled the problem as an influence blocking maximization that features an influencer and a mitigator. While past work has introduced scalable heuristic techniques for generating effective strategies using a double oracle algorithm, it has not addressed the issue of uncertainty and asymmetric information, which is the topic of this paper.
2013_3_teamcore_aamas13_camera_readyv3.pdf
Bo An, Matthew Brown, Yevgeniy Vorobeychik, and Milind Tambe. 2013. “Security Games with Surveillance Cost and Optimal Timing of Attack Execution.” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS).Abstract
Stackelberg games have been used in several deployed applications to allocate limited resources for critical infrastructure protection. These resource allocation strategies are randomized to prevent a strategic attacker from using surveillance to learn and exploit patterns in the allocation. Past work has typically assumed that the attacker has perfect knowledge of the defender’s randomized strategy or can learn the defender’s strategy after conducting a fixed period of surveillance. In consideration of surveillance cost, these assumptions are clearly simplistic since attackers may act with partial knowledge of the defender’s strategies and may dynamically decide whether to attack or conduct more surveillance. In this paper, we propose a natural model of limited surveillance in which the attacker dynamically determine a place to stop surveillance in consideration of his updated belief based on observed actions and surveillance cost. We show an upper bound on the maximum number of observations the attacker can make and show that the attacker’s optimal stopping problem can be formulated as a finite state space MDP. We give mathematical programs to compute optimal attacker and defender strategies. We compare our approaches with the best known previous solutions and experimental results show that the defender can achieve significant improvement in expected utility by taking the attacker’s optimal stopping decision into account, validating the motivation of our work.
2013_2_teamcore_sglsc.pdf
Jun-young Kwak, Pradeep Varakantham, Rajiv Maheswaran, Yu-Han Chang, Milind Tambe, Burcin Becerik-Gerber, and Wendy Wood. 2013. “TESLA: An Energy-saving Agent that Leverages Schedule Flexibility .” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS).Abstract
This innovative application paper presents TESLA, an agent-based application for optimizing the energy use in commercial buildings. TESLA’s key insight is that adding flexibility to event/meeting schedules can lead to significant energy savings. TESLA provides three key contributions: (i) three online scheduling algorithms that consider flexibility of people’s preferences for energyefficient 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; and (iii) surveys of real users that indicate that TESLA’s assumptions exist in practice. TESLA was evaluated on data of over 110,000 meetings held at nine campus buildings during eight months in 2011–2012 at USC and SMU. These results show that, compared to the current systems, TESLA can substantially reduce overall energy consumption.
2013_4_teamcore_aamas13-tesla-camera-ready-finalv2.pdf
Manish Jain. 2013. “Thwarting Adversaries with Unpredictability: Massive-scale Game-Theoretic Algorithms for Real-world Security Deployments ”.Abstract
Protecting critical infrastructure and targets such as airports, transportation networks, power generation facilities as well as critical natural resources and endangered species is an important task for police and security agencies worldwide. Securing such potential targets using limited resources against intelligent adversaries in the presence of the uncertainty and complexities of the real-world is a major challenge. My research uses a game-theoretic framework to model the strategic interaction between a defender (or security forces) and an attacker (or terrorist adversary) in security domains. Game theory provides a sound mathematical approach for deploying limited security resources to maximize their effectiveness. While game theory has always been popular in the arena of security, unfortunately, the state of the art algorithms either fail to scale or to provide a correct solution for large problems with arbitrary scheduling constraints. For example, US carriers fly over 27,000 domestic and 2,000 international flights daily, presenting a massive scheduling challenge for Federal Air Marshal Service (FAMS). My thesis contributes to a very new area that solves game-theoretic problems using insights from large-scale optimization literature towards addressing the computational challenge posed by real-world domains. I have developed new models and algorithms that compute optimal strategies for scheduling defender resources is large real-world domains. My thesis makes the following contributions. First, it presents new algorithms that can solve for trillions of actions for both the defender and the attacker. Second, it presents a hierarchical framework that provides orders of magnitude scale-up in attacker types for Bayesian Stackelberg games. Third, it provides an analysis and detection of a phase-transition that identifies properties that makes security games hard to solve. These new models have not only advanced the state of the art in computational game-theory, but have actually been successfully deployed in the real-world. My work represents a successful transition from game-theoretic advancements to real-world applications that are already in use, and it has opened exciting new avenues to greatly expand the reach of game theory. For instance, my algorithms are used in the IRIS system: IRIS has been in use by the Federal Air Marshals Service (FAMS) to schedule air marshals on board international commercial flights since October 2009.
2013_25_teamcore_manish_thesis.pdf
Jun-young Kwak, Pradeep Varakantham, Rajiv Maheswaran, Yu-Han Chang, Milind Tambe, Burcin Becerik-Gerber, and Wendy Wood. 2013. “Why TESLA Works: Innovative Agent-based Application Leveraging Schedule Flexibility for Conserving Energy .” In Workshop on Multiagent-based Societal Systems (MASS) at AAMAS.Abstract
This paper presents TESLA, an agent-based application for optimizing the energy use in commercial buildings. TESLA’s key insight is that adding flexibility to event/meeting schedules can lead to significant energy savings. TESLA provides two key contributions: (i) three online scheduling algorithms that consider flexibility of people’s preferences for energy-efficient scheduling of incrementally/dynamically arriving meetings and events; and (ii) an algorithm to effectively identify key meetings that lead to significant energy savings by adjusting their flexibility. TESLA was evaluated on data of over 110,000 meetings held at nine campus buildings during eight months in 2011–2012 at the University of Southern California (USC) and the Singapore Management University (SMU), and it indicated that TESLA’s assumptions exist in practice. This paper also provides an extensive analysis on energy savings achieved by TESLA. These results and analysis show that, compared to the current systems, TESLA can substantially reduce overall energy consumption.
2013_12_teamcore_mass-camera-ready-v2.pdf
Manish Jain, Vincent Conitzer, and Milind Tambe. 2013. “Security Scheduling for Real-world Networks .” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS).Abstract
Network based security games, where a defender strategically places security measures on the edges of a graph to protect against an adversary, who chooses a path through a graph is an important research problem with potential for real-world impact. For example, police forces face the problem of placing checkpoints on roads to inspect vehicular traffic in their day-to-day operations, a security measure the Mumbai police have performed since the terrorist attacks in 2008. Algorithms for solving such network-based security problems have been proposed in the literature, but none of them scale up to solving problems of the size of real-world networks. In this paper, we present SNARES, a novel algorithm that computes optimal solutions for both the defender and the attacker in such network security problems. Based on a double-oracle framework, SNARES makes novel use of two approaches: warm starts and greedy responses. It makes the following contributions: (1) It defines and uses mincut-fanout, a novel method for efficient warm-starting of the computation; (2) It exploits the submodularity property of the defender optimization in a greedy heuristic, which is used to generate “better-responses"; SNARES also uses a better-response computation for the attacker. Furthermore, we evaluate the performance of SNARES in real-world networks illustrating a significant advance: whereas state-of-the-art algorithms could handle just the southern tip of Mumbai, SNARES can compute optimal strategy for the entire urban road network of Mumbai.
2013_7_teamcore_fp066-jain.pdf

Pages