2013
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.
AbstractDespite 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.
Abstractt 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.
AbstractThis 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].
AbstractFare 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).
AbstractIn 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.
AbstractStackelberg 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.
AbstractBy 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.pdfChao 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.
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 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].
AbstractMotivated 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).
AbstractThere 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).
AbstractTeam 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).
AbstractPrevious 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.
AbstractWe 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).
AbstractEnergy 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.
AbstractIn 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 ”.
AbstractMany 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).
AbstractAs 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).
AbstractTo 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].
AbstractCounterinsurgency, 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).
AbstractStackelberg 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