Publications

2013
Albert Xin Jiang, Ariel D. Procaccia, Yundi Qian, Nisarg Shah, and Milind Tambe. 2013. “Defender (Mis)coordination in Security Games .” In International Joint Conference on Artificial Intelligence (IJCAI).Abstract
We study security games with multiple defenders. To achieve maximum security, defenders must perfectly synchronize their randomized allocations of resources. However, in real-life scenarios (such as protection of the port of Boston) this is not the case. Our goal is to quantify the loss incurred by miscoordination between defenders, both theoretically and empirically. We introduce two notions that capture this loss under different assumptions: the price of miscoordination, and the price of sequential commitment. Generally speaking, our theoretical bounds indicate that the loss may be extremely high in the worst case, while our simulations establish a smaller yet significant loss in practice.
2013_20_teamcore_security_coordination.pdf
B. An, E. Shieh, R. Yang, M. Tambe, C. Baldwin, J. DiRenzo, B. Maule, and G. Meyer. 2013. “A Deployed Quantal Response Based Patrol Planning System for the US Coast Guard .” In Interfaces, 43, 5, Pp. 400-420.Abstract
In this paper we describe the model, theory developed and deployment of PROTECT, a game-theoretic system in use by the United States Coast Guard (USCG) in the Port of Boston for scheduling patrols. The USCG evaluated the deployment of PROTECT in the Port of Boston as a success and is currently evaluating the system in the Port of New York, with the potential for nationwide deployment. The PROTECT system is premised on an attacker-defender Stackelberg game model but its development and implementation required both theoretical contributions and detailed evaluations. In this paper we describe the work required in the deployment which we group into five key innovations. First, we propose a compact representation of the defender’s strategy space, by exploiting equivalence and dominance, that makes PROTECT efficient enough to solve real world sized problems. Second, this system does not assume that adversaries are perfectly rational, a regular assumption in previous game theoretic models for security. Instead, PROTECT relies on a quantal response (QR) model of the adversary’s behavior — to the best of our knowledge, this is the first real-world deployment of a QR model. Third, we develop specialized solution algorithms that are able to solve this problem for real-world instances and give theoretical guarantees. Fourth, our experimental results illustrate that PROTECT’s QR model handles real-world uncertainties more robustly than a perfect rationality model. Finally, this paper presents real-world evaluation of PROTECT by: (i) a comparison of human-generated vs PROTECT security schedules, and (ii) results from an Adversarial Perspective Team’s (human mock attackers) analysis.
2013_35_teamcore_protect_wagner_informs.pdf
Fei Fang, Albert Xin Jiang, and Milind Tambe. 2013. “Designing Optimal Patrol Strategy for Protecting Moving Targets with Multiple Mobile Resources .” In International Workshop on Optimisation in Multi-Agent Systems (OPTMAS).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 linear-program-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_13_teamcore_optmas2013_ferry.pdf
L. S. Marcolino, D. Chen, A.X. Jiang, and M. Tambe. 2013. “Diversity Beats Strength? - A Hands-on Experience with 9x9 Go (Demonstration) .” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS) [Demonstrations Track].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? In this demo, the user will be able to explore these questions by playing one of the most challenging board games: Go.
2013_10_teamcore_aamas2013-demo.pdf
Eric Shieh, Manish Jain, Albert Xin Jiang, and Milind Tambe. 2013. “Efficiently Solving Joint Activity Based Security Games .” In International Joint Conference on Artificial Intelligence (IJCAI).Abstract
Despite recent successful real-world deployments of Stackelberg Security Games (SSGs), scale-up remains a fundamental challenge in this field. The latest techniques do not scale-up to domains where multiple defenders must coordinate time-dependent joint activities. To address this challenge, this paper presents two branch-and-price algorithms for solving SSGs, SMARTO and SMARTH, with three novel features: (i) a column-generation approach that uses an ordered network of nodes (determined by solving the traveling salesman problem) to generate individual defender strategies; (ii) exploitation of iterative reward shaping of multiple coordinating defender units to generate coordinated strategies; (iii) generation of tighter upper-bounds for pruning by solving security games that only abide by key scheduling constraints. We provide extensive experimental results and formal analyses.
2013_15_teamcore_shieh_ijcai_2013_main.pdf
Eric Shieh, Manish Jain, Albert Xin Jiang, and Milind Tambe. 2013. “Efficiently Solving Time-Dependent Joint Activities in Security Games .” In Workshop on Optimization in Multiagent Systems (OPTMAS) at AAMAS.Abstract
Despite recent successful real-world deployments of Stackelberg Security Games (SSGs), scale-up remains a fundamental challenge in this field. The latest techniques do not scale-up to domains where multiple defenders must coordinate time-dependent joint activities. To address this challenge, this paper presents two branch-and-price algorithms for solving SSGs, SMARTO and SMARTH, with three novel features: (i) a column-generation approach that uses an ordered network of nodes (determined by solving the traveling salesman problem) to generate individual defender strategies; (ii) exploitation of iterative reward shaping of multiple coordinating defender units to generate coordinated strategies; (iii) generation of tighter upper-bounds for pruning by solving security games that only abide by key scheduling constraints. We provide extensive experimental results and formal analyses.
2013_16_teamcore_shieh_optmas2013_camera_ready.pdf
2013. “Empirical Evaluation of Computational Fear Contagion Models in Crowd Dispersions .” Journal of Autonomous Agents and Multiagent Systems, JAAMAS, 27, 2, Pp. 200-217.Abstract
t In social psychology, emotional contagion describes the widely observed phenomenon of one person’s emotions being influenced by surrounding people’s emotions. While the overall effect is agreed upon, the underlying mechanism of the spread of emotions has seen little quantification and application to computational agents despite extensive evidence of its impacts in everyday life. In this paper, we examine computational models of emotional contagion by implementing two models ((Bosse et al, 2009b) and (Durupinar, 2010)) that draw from two separate lines of contagion research: thermodynamics-based and epidemiologicalbased. We first perform sensitivity tests on each model in an evacuation simulation, ESCAPES, showing both models to be reasonably robust to parameter variations with certain exceptions. We then compare their ability to reproduce a real crowd panic scene in simulation, showing that the thermodynamics-style model (Bosse et al, 2009b) produces superior results due to the ill-suited contagion mechanism at the core of epidemiological models. We also identify that a graduated effect of fear and proximity-based contagion effects are key to producing the superior results. We then reproduce the methodology on a second video, showing that the same results hold, implying generality of the conclusions reached in the first scene.
2013_1_teamcore_iva-revisionv1.pdf
Pujol-Gonzalez, J. Cerquides, P. Meseguer, J. A. Rodriguez Aguilar, and M. Tambe. 2013. “Engineering the decentralized coordination of UAVs with limited communication range.” In Conference of the Spanish Association for Artificial Intelligence (CAEPIA), 2013.Abstract
This paper tackles the problem of allowing a team of UAVs with limited communication range to autonomously coordinate to service requests. We present two MRF-based solutions: one assumes independence between requests; and the other considers also the UAVs’ workloads. Empirical evaluation shows that the latter performs almost as well as state-of-the-art centralized techniques in realistic scenarios.
2013_28_teamcore_caepia-52.pdf
Samantha Luber, Zhengyu Yin, Francesco Delle Fave, Albert Xin Jiang, Milind Tambe, and John P. Sullivan. 2013. “Game-theoretic Patrol Strategies for Transit Systems: the TRUSTS System and its Mobile App (Demonstration) .” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS)[Demonstrations Track].Abstract
Fare evasion costs proof-of-payment transit systems significant losses in revenue. In 2007 alone, the Los Angeles Metro system, using proof-of-payment, suffered an estimated revenue loss of $5.6 million due to fare evasion [2]. In addition, resource limitations prevent officers from verifying all passengers. Thus, such officers periodically inspect a subset of the passengers based on a patrol strategy. Effective patrol strategies are then needed to deter fare evasion and maximize revenue in transit systems. In addition, since potential fare evaders can exploit knowledge about the patrol strategy to avoid inspection, an unpredictable patrol strategy is needed for effectiveness. Furthermore, due to transit system complexity, human schedulers cannot manually produce randomized patrol strategies, while taking into account all of the system’s scheduling constraints [3]. In previous work on computing game-theoretic patrol strategies, Bayesian Stackelberg games have been successfully used to model the patrolling problem. In this model, the security officer commits to a patrol strategy and the fare evaders observe this patrol strategy and select a counter strategy accordingly [4]. This approach has also been successfully deployed in real-world applications, including by the L.A. International Airport police, the U.S. Coast Guard at the Port of Boston, and the Federal Air Marshal Service [5]. However, this approach cannot be used within our setting due to the increased complexity of having more potential followers and scheduling constraints [6]. In addition, transit systems face the challenge of execution uncertainty, in which unexpected events cause patrol officers to fall off schedule and exist in unknown states in the model [1]. Addressing the increased complexity challenge, TRUSTS (Tactical Randomizations for Urban Security in Transit Systems) reduces the temporal and spatial scheduling constraints imposed by the transit system into a single transition graph, a compact representation of all possible movement throughout the transit system as flows from each station node [1]. In addition, TRUSTS remedies the execution uncertainty challenge by modeling the execution of patrol units as Markov Decision Processes (MDPs) [1]. In simulation and trial testing, the TRUSTS approach has generated effective patrol strategies for L.A. Metro System [1, 6]. In order to implement the TRUSTS approach in real-world transit systems, the METRO mobile app presented in this paper is being developed to work with TRUSTS to (i) provide officers with realtime TRUSTS-generated patrol schedules, (ii) provide recovery from schedule interruptions, and (iii) collect patrol data. An innovation in transit system patrol scheduling technology, the app works as an online agent that provides officers with the best set of patrol actions for maximizing fare evasion deterrence based on the current time and officer location. In this paper, we propose a demonstration of the TRUSTS system, composed of the TRUSTS and METRO app components, which showcases how the system works with emphasis on the mobile app for user interaction. To establish sufficient background context for the demonstration, this paper also presents a brief overview of the TRUSTS system, including the TRUSTS approach to patrol strategy generation in Section 2.1 and discussion of the METRO app’s features and user interface design in Section 2.2, and the expected benefits from deployment in the L.A. Metro System.
2013_11_teamcore_aamas_2013_camera_ready.pdf
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

Pages