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).Abstract
Stackelberg 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.
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).Abstract
Fish 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.
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].Abstract
Going 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.
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.Abstract
This 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.
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.Abstract
Among 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.
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).Abstract
To 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.
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.Abstract
Recent 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.
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.Abstract
This 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.
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].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 game-theoretic approach to generate randomized patrol policies for controlling such diffusion.
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).Abstract
Multiagent 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.
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).Abstract
Illegal 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.
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).Abstract
Given 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.