2015
V. Nagarajan, L. S. Marcolino, and M. Tambe. 2015. “
Every team deserves a second chance: Identifying when things go wrong (Student Abstract Version) .” In Conference on Artificial Intelligence (AAAI 2015). Texas, USA.
AbstractWe show that without using any domain knowledge, we
can predict the final performance of a team of voting
agents, at any step towards solving a complex problem.
2015_9_teamcore_aaai_student_abstract2015.pdf V. Nagarajan, L. S. Marcolino, and M. Tambe. 2015. “
Every Team Makes Mistakes: An Initial Report on Predicting Failure in Teamwork .” In AAAI Workshop Learning for General Competency in Video Games (AAAI 2015). Texas, USA.
AbstractVoting among different agents is a powerful tool in
problem solving, and it has been widely applied to improve the performance in machine learning. However,
the potential of voting has been explored only in improving the ability of finding the correct answer to a
complex problem. In this paper we present a novel benefit in voting, that has not been observed before: we
show that we can use the voting patterns to assess the
performance of a team and predict their final outcome.
This prediction can be executed at any moment during
problem-solving and it is completely domain independent. We present a preliminary theoretical explanation
of why our prediction method works, where we show
that the accuracy is better for diverse teams composed
by different agents than for uniform teams made of
copies of the same agent. We also perform experiments
in the Computer Go domain, where we show that we
can obtain a high accuracy in predicting the final outcome of the games. We analyze the prediction accuracy
for 3 different teams, and we show that the prediction
works significantly better for a diverse team. Since our
approach is completely domain independent, it can be
easily applied to a variety of domains, such as the video
games in the Arcade Learning Environment.
2015_10_teamcore_aaai_workshop2015.pdf L. S. Marcolino, V. Nagarajan, and M. Tambe. 2015. “
Every Team Makes Mistakes, in Large Action Spaces .” In Multidisciplinary Workshop on Advances in Preference Handling (M-PREF 2015).
AbstractVoting is applied to better estimate an optimal answer to complex problems in many domains. We
recently presented a novel benefit of voting, that
has not been observed before: we can use the voting patterns to assess the performance of a team
and predict whether it will be successful or not in
problem-solving. Our prediction technique is completely domain independent, and it can be executed
at any time during problem solving. In this paper
we present a novel result about our technique: we
show that the prediction quality increases with the
size of the action space. We present a theoretical
explanation for such phenomenon, and experiments
in Computer Go with a variety of board sizes.
2015_33_teamcore_mpref15.pdf H. Xu, Z. Rabinovich, S. Dughmi, and M. Tambe. 2015. “
Exploring Information Asymmetry in Two-Stage Security Games .” In AAAI Conference on Artificial Intelligence (AAAI).
AbstractStackelberg security games have been widely deployed to
protect real-world assets. The main solution concept there
is the Strong Stackelberg Equilibrium (SSE), which optimizes the defender’s random allocation of limited security
resources. However, solely deploying the SSE mixed strategy has limitations. In the extreme case, there are security
games in which the defender is able to defend all the assets
“almost perfectly” at the SSE, but she still sustains significant
loss. In this paper, we propose an approach for improving the
defender’s utility in such scenarios. Perhaps surprisingly, our
approach is to strategically reveal to the attacker information
about the sampled pure strategy.
Specifically, we propose a two-stage security game model,
where in the first stage the defender allocates resources and
the attacker selects a target to attack, and in the second stage
the defender strategically reveals local information about that
target, potentially deterring the attacker’s attack plan. We then
study how the defender can play optimally in both stages.
We show, theoretically and experimentally, that the two-stage
security game model allows the defender to achieve strictly
better utility than SSE.
2015_3_teamcore_two_stage_game.pdf Shahrzad Gholami, Chao Zhang, Arunesh Sinha, and Milind Tambe. 2015. “
An extensive study of Dynamic Bayesian Network for patrol allocation against adaptive opportunistic criminals .” In IJCAI'15 Workshop on Behavioral, Economic and Computational Intelligence for Security (BECIS).
AbstractPolice patrols are used ubiquitously to deter crimes in
urban areas. A distinctive feature of urban crimes is
that criminals react opportunistically to patrol officers’
assignments. Different models of adversary behavior have been proposed but their exact form remains
uncertain. Recent work [Zhang et al., 2015] has explored learning the model from real-world criminal
activity data. To that end, criminal behavior and the
interaction with the patrol officers is represented as parameters of a Dynamic Bayesian Network (DBN), enabling application of standard algorithms such as EM
to learn the parameters. More specifically, the EMC2
algorithm is a sequence of modifications to the DBN
representation, that allows for a compact representation resulting in better learning accuracy and increased
speed of learning. In this paper, we perform additional
experiments showing the efficacy of the EMC2
algorithm. Furthermore, we explore different variations of
Markov model. Unlike DBNs, the Markov models do
not have hidden states, which indicate distribution of
criminals, and are therefore easier to learn using standard MLE techniques. We compare all the approaches
by learning from a real data set of criminal activity
obtained from the police department of University of
Southern California (USC) situated in Los Angeles,
USA. We demonstrate a significant better accuracy of
predicting the crime using the EMC2
algorithm compared to other approaches. This work was done in collaboration with the police department of USC.
2015_34_teamcore_keep_pace_with_criminal_workshop.pdf Amulya Yadav, Thanh Nguyen, Francesco Delle Fave, Milind Tambe, Noa Agmon, Manish Jain, Widodo Ramono, and Timbul Batubara. 2015. “
Handling Payoff Uncertainty in Green Security Domains with Adversary Bounded Rationality .” In In IJCAI-15 Workshop on Behavioral, Economic and Computational Intelligence for Security (BECIS-15).
AbstractResearch on Stackelberg Security Games (SSG)
has recently shifted to green security domains, for
example, protecting wildlife from illegal poaching.
Previous research on this topic has advocated the
use of behavioral (bounded rationality) models of
adversaries in SSG. As its first contribution, this
paper, for the first time, provides validation of these
behavioral models based on real-world data from a
wildlife park. The paper’s next contribution is the
first algorithm to handle payoff uncertainty – an important concern in green security domains – in the
presence of such adversarial behavioral models.
2015_39_teamcore_yadav_becis2015.pdf Amulya Yadav, Thanh Nguyen, Francesco Delle Fave, Milind Tambe, Noa Agmon, Manish Jain, Widodo Ramono, and Timbul Batubara. 2015. “
Handling Payoff Uncertainty with Adversary Bounded Rationality in Green Security Domains .” In In IJCAI-15 Workshop on Algorithmic Game Theory (AGT-15).
AbstractResearch on Stackelberg Security Games (SSG)
has recently shifted to green security domains, for
example, protecting wildlife from illegal poaching.
Previous research on this topic has advocated the
use of behavioral (bounded rationality) models of
adversaries in SSG. As its first contribution, this
paper, for the first time, provides validation of these
behavioral models based on real-world data from a
wildlife park. The paper’s next contribution is the
first algorithm to handle payoff uncertainty – an important concern in green security domains – in the
presence of such adversarial behavioral models.
2015_38_teamcore_yadav_agt2015.pdf Yasaman Dehghani Abbasi, Martin Short, Arunesh Sinha, Nicole Sintov, Chao Zhang, and Milind Tambe. 2015. “
Human Adversaries in Opportunistic Crime Security Games: Evaluating Competing Bounded Rationality Models .” In Conference on Advances in Cognitive Systems.
AbstractThere are a growing number of automated decision aids based on game-theoretic algorithms in daily use
by security agencies to assist in allocating or scheduling their limited security resources. These
applications of game theory, based on the “security games” paradigm, are leading to fundamental
research challenges: one major challenge is modeling human bounded rationality. More specifically, the
security agency, assisted with an automated decision aid, is assumed to act with perfect rationality against
a human adversary; it is important to investigate the bounded rationality of these human adversaries to
improve effectiveness of security resource allocation. This paper for the first time provides an empirical
investigation of adversary bounded rationality in opportunistic crime settings, where modeling bounded
rationality is particularly crucial. We conduct extensive human subject experiments, comparing ten
different bounded rationality models, and illustrate that: (a) while previous research proposed the use of
the stochastic choice “quantal response” model of human adversary, this model is significantly
outperformed by more advanced models of “subjective utility quantal response”; (b) Combinations of
the well-known prospect theory model with these advanced models lead to an even better performance
in modeling human adversary behavior; (c) while it is important to model the non-linear human weighing
of probability, as advocated by prospect theory, our findings are the exact opposite of prospect theory in
terms of how humans are seen to weigh this non-linear probability.
2015_20_teamcore_yasi_cogsy_re_submitted_version.pdf Dehghani Abbasi Y., Short M., Sinha A., Sintov N., Zhang Ch., and Tambe M. 2015. “
Human Adversaries in Opportunistic Crime Security Games: How Past success (or failure) affects future behavior .” In Workshop on Behavioral, Economic and Computational Intelligence for Security (IJCAI).
AbstractThere are a growing number of automated decision aids
based on game-theoretic algorithms in daily use by
security agencies to assist in allocating or scheduling
their limited security resources. These applications of
game theory, based on the “security games” paradigm,
are leading to fundamental research challenges: one
major challenge is modeling human bounded rationality.
More specifically, the security agency, assisted with an
automated decision aid, is assumed to act with perfect
rationality against a human adversary; it is important to
investigate the bounded rationality of these human
adversaries to improve effectiveness of security
resource allocation. In (Abbasi et al, 2015), the authors
provide an empirical investigation of adversary bounded
rationality in opportunistic crime settings. In this paper,
we propose two additional factors in the “subjective
utility quantal response” model.
2015_28_teamcore_ijcai2015_re_submitted_version.pdf Zinovi Rabinovich, Albert X. Jiang, Manish Jain, and Haifeng Xu. 2015. “
Information Disclosure as a Means to Security .” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS).
AbstractIn this paper we present a novel Stackelberg-type model of security domains: Security Assets aSsignment with Information disclosure (SASI). The model combines both the features of the Stackelberg Security Games (SSGs) model and of the Bayesian Persuasion
(BP) model. More specifically, SASI includes: a) an uncontrolled,
exogenous security state that serves as the Defender’s private information; b) multiple security assets with non-accumulating, targetlocal defence capability; c) a pro-active, verifiable and public, unidirectional information disclosure channel from the Defender to the
Attacker. We show that SASI with a non-degenerate information
disclosure can be arbitrarily more efficient, than a “silent” Stackelberg assets allocation. We also provide a linear program reformulation of SASI that can be solved in polynomial time in SASI
parameters. Furthermore, we show that it is possible to remove one
of SASI parameters and, rather than require it as an input, recover
it by computation. As a result, SASI becomes highly scalable.
2015_42_teamcore_sasi.pdf Fei Fang, Thanh Nguyen, Benjamin Ford, Nicole Sintov, and Milind Tambe. 2015. “
Introduction to Green Security Games (Extended Abstract) .” In Workshop on Cognitive Knowledge Acquisition and Applications (IJCAI 2015).
AbstractConservation agencies around the world are tasked with protecting endangered wildlife from poaching. Despite their substantial efforts, however, species are continuing to be poached
to critical status and, in some cases, extinction. In South
Africa, rhino poaching has seen a recent escalation in frequency; while only 122 rhinos were poached in 2009, a record
1215 rhinos were poached in 2014 (approximately 1 rhino every eight hours)[the Rhino International, 2015]. To combat
poaching, conservation agencies send well-trained rangers to
patrol designated protected areas. However, these agencies
have limited resources and are unable to provide 100% coverage to the entire area at all times. Thus, it is important that
agencies make the most efficient use of their patrolling resources, and we introduce Green Security Games (GSGs) as
a tool to aid agencies in designing effective patrols.
First introduced by [Von Stengel and Zamir, 2004] as a
Leadership Game, Stackelberg Games have been applied in
a variety of Security Game research (i.e., Stackelberg Security Games, or SSGs). In particular, the focus on randomization in Stackelberg Games lends itself to solving real-world
security problems where defenders have limited resources,
such as randomly allocating Federal Air Marshals to international flights [Tsai et al., 2009]. However, the SSG model
focuses on generating an optimal defender strategy against a
single defender-attacker interaction (e.g., a single terrorist attack). For domains where attacks occur frequently, such as
in wildlife conservation, another type of Security Game is
needed that effectively models the repeated interactions between the defender and the attacker.
While still following the Leader-Follower paradigm of
SSGs, GSGs have been developed as a way of applying Game
Theory to assist wildlife conservation efforts, whether its to
prevent illegal fishing [Haskell et al., 2014], illegal logging
[Johnson et al., 2012], or wildlife poaching [Yang et al.,
2014]. GSGs are similar to SSGs except that, in GSGs, the
game takes place over N rounds. In SSGs, once the attacker
makes a decision, the game is over, but in GSGs, the attacker (e.g., the poacher) and defender have multiple rounds
in which they can adapt to each other’s choices in previous
rounds. This multi-round feature of GSGs introduces some
key research challenges that are being studied: (1) how can
we incorporate the attacker’s previous choices into our model
of their behavior, in order to improve the defender’s strategy, [Yang et al., 2014; Kar et al., 2015] and (2) how do we
choose a strategy such that the long-term payoff (i.e., cumulative expected utility) is maximized [Fang et al., 2015]? In
addition to exploring these open research questions, we also
discuss field tests of the Protection Assistant for Wildlife Security (PAWS) software in Uganda and Malaysia.
2015_27_teamcore_ijcai2015_gsg.pdf Chao Zhang, Arunesh Sinha, and Milind Tambe. 2015. “
Keeping pace with criminals: Designing patrol allocation against adaptive opportunistic criminals .” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2015).
AbstractPolice patrols are used ubiquitously to deter crimes in urban areas.
A distinctive feature of urban crimes is that criminals react opportunistically to patrol officers’ assignments. Compared to strategic
attackers (such as terrorists) with a well-laid out plan, opportunistic criminals are less strategic in planning attacks and more flexible
in executing them. In this paper, our goal is to recommend optimal police patrolling strategy against such opportunistic criminals.
We first build a game-theoretic model that captures the interaction
between officers and opportunistic criminals. However, while different models of adversary behavior have been proposed, their exact form remains uncertain. Rather than simply hypothesizing a
model as done in previous work, one key contribution of this paper is to learn the model from real-world criminal activity data.
To that end, we represent the criminal behavior and the interaction
with the patrol officers as parameters of a Dynamic Bayesian Network (DBN), enabling application of standard algorithms such as
EM to learn the parameters. Our second contribution is a sequence
of modifications to the DBN representation, that allows for a compact representation of the model resulting in better learning accuracy and increased speed of learning of the EM algorithm when
used for the modified DBN. These modifications use marginalization approaches and exploit the structure of this problem. Finally,
our third contribution is an iterative learning and planning mechanism that keeps updating the adversary model periodically. We
demonstrate the efficiency of our learning algorithm by applying
it to a real data set of criminal activity obtained from the police
department of University of Southern California (USC) situated in
Los Angeles, USA. We project a significant reduction in crime rate
using our planning strategy as opposed to the actual strategy deployed by the police department. We also demonstrate the improvement in crime prevention in simulations when we use our iterative
planning and learning mechanism compared to just learning once
and planing. This work was done in collaboration with the police
department of USC.
2015_13_teamcore_keep_pace_with_criminal.pdf Chao Zhang, Manish Jain, Ripple Goyal, Arunesh Sinha, and Milind Tambe. 2015. “
Keeping pace with criminals: Learning, Predicting and Planning against Crime: Demonstration Based on Real Urban Crime Data (Demonstration) .” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2015).
AbstractCrime in urban areas plagues every
city in all countries. This demonstration will show a novel approach for
learning and predicting crime patterns
and planning against such crimes using
real urban crime data. A notable characteristic of urban crime, distinct from
organized terrorist attacks, is that most
urban crimes are opportunistic in nature, i.e., criminals do not plan their attacks in detail, rather they seek opportunities for committing crime and are
agile in their execution of the crime [6,
7, 1, 4]. Police officers conduct patrols
with the aim of preventing crime. However, criminals can adapt their strategy in response of police deployment by
seeking crime opportunity in less effectively patrolled location. The problem
of where and how much to patrol is therefore important.
There are two approaches to solve this problem. The first
approach is to schedule patrols manually by human planners,
which is followed in various police departments. However,
it has been demonstrated that manual planning of patrols
is not only time-consuming but also highly ineffective in related scenarios of protecting airport terminals [3] and ships
in ports [5]. The second approach is to use automated planners to plan patrols against urban crime. This approach
has either focused on modeling the criminal explicitly [7,6] (rational, bounded rational, etc.) in a game model or
to learn the adversary behavior using machine learning [2].
However, the proposed mathematical models of criminal behavior have not been validated with real data. Also, prior
machine learning approaches have either only focused on the
adversary actions ignoring their adaptation to the defenders’
actions [2]. Hence, in this presentation we propose
a novel approach to
learn and update the
criminal behavior from
real data [8]. We
model the interaction
between criminals and
patrol officers as a Dynamic Bayesian Network (DBN). Figure 1
shows an example of such DBN. Next, we apply a dynamic
programming algorithm to generate optimal patrol strategy
against the learned criminal model. By iteratively updating
the criminals’ model and computing patrol strategy against
them, we help patrol officers keep up with criminals’ adaptive behavior and execute effective patrols. This process is
shown as a flow chart in Figure 2.
With this context, the demonstration presented in this
paper introduces a web-based software with two contributions. First, our system collects and analyzes crime reports
and resources (security camera, emergency supplies, etc.)
data, presenting them in various forms. Second, our patrol
scheduler incorporates the algorithm in [8] in a scheduling
recommendation system. The demonstration will engage audience members by having them participate as patrol officers
and using the software to ‘patrol’ the University of Southern
California (USC) campus in USA.
2015_15_teamcore_de005_zhang_learning_demo.pdf Debarun Kar, Fei Fang, Francesco Delle Fave, Nicole Sintov, Arunesh Sinha, Aram Galstyan, Bo An, and Milind Tambe. 2015. “
Learning Bounded Rationality Models of the Adversary in Repeated Stackelberg Security Games .” In Adaptive and Learning Agents Workshop at the International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2015).
AbstractSeveral competing human behavior models have been proposed
to model and protect against boundedly rational adversaries in repeated Stackelberg security games (SSGs). However, these existing
models fail to address three main issues which are extremely detrimental to defender performance. First, while they attempt to learn
adversary behavior models from adversaries’ past actions (“attacks
on targets”), they fail to take into account adversaries’ future adaptation based on successes or failures of these past actions. Second,
they assume that sufficient data in the initial rounds will lead to
a reliable model of the adversary. However, our analysis reveals
that the issue is not the amount of data, but that there just is not
enough of the attack surface exposed to the adversary to learn a
reliable model. Third, current leading approaches have failed to include probability weighting functions, even though it is well known
that human beings’ weighting of probability is typically nonlinear.
Moreover, the performances of these models may be critically dependent on the learning algorithm used to learn the parameters of
these models. The first contribution of this paper is a new human
behavior model, SHARP, which mitigates these three limitations as
follows: (i) SHARP reasons based on success or failure of the adversary’s past actions on exposed portions of the attack surface to
model adversary adaptiveness; (ii) SHARP reasons about similarity between exposed and unexposed areas of the attack surface, and
also incorporates a discounting parameter to mitigate adversary’s
lack of exposure to enough of the attack surface; and (iii) SHARP
integrates a non-linear probability weighting function to capture the
adversary’s true weighting of probability. Our second contribution
is a comparison of two different approaches for learning the parameters of the bounded rationality models.
Our third contribution is a first “longitudinal study” – at least in
the context of SSGs – of competing models in settings involving
repeated interaction between the attacker and the defender. This
study, where each experiment lasted a period of multiple weeks
with individual sets of human subjects, illustrates the strengths and
weaknesses of different models and shows the advantages of SHARP.
2015_27_teamcore_ijcai2015_gsg.pdf D. J. Gerber, E. Pantazis, L. S. Marcolino, and A. Heydarian. 2015. “
A Multi-Agent Systems for Design Simulation Framework: Experiments with Virtual-Physical-Social Feedback for Architecture .” In Symposium on Simulation for Architecture and Urban Design (SimAUD 2015).
AbstractThis paper presents research on the development of multiagent systems (MAS) for integrated and performance driven
architectural design. It presents the development of a
simulation framework that bridges architecture and
engineering, through a series of multi-agent based
experiments. The research is motivated to combine multiple
design agencies into a system for managing and optimizing
architectural form, across multiple objectives and contexts.
The research anticipates the incorporation of feedback from
real world human behavior and user preferences with physics
based structural form finding and environmental analysis
data. The framework is a multi-agent system that provides
design teams with informed design solutions, which
simultaneously optimize and satisfy competing design
objectives. The initial results for building structures are
measured in terms of the level of lighting improvements and
qualitatively in geometric terms. Critical to the research is
the elaboration of the system and the feedback loops that are
possible when using the multi-agent systems approach.
2015_18_teamcore_simaud2015.pdf Eric Shieh. 2015. “
Not a Lone Ranger: Unleashing Defender Teamwork in Security Games ”.
AbstractGame theory has become an important research area in handling complex security resource allocation and patrolling problems. Stackelberg Security Games (SSGs) have been used in modeling these types of problems via a defender and an attacker(s). Despite recent successful real-world deployments of SSGs, scale-up to handle defender teamwork 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, my thesis presents algorithms for solving defender teamwork in SSGs in two phases. As a first step, I focus on domains without execution uncertainty, in modeling and solving SSGs that incorporate teamwork among defender resources via 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. In the second stage of my thesis, I address execution uncertainty among defender resources that arises from the real world by integrating the powerful teamwork mechanisms offered by decentralized Markov Decision Problems (Dec-MDPs) into security games. My thesis offers the following novel contributions: (i) New model of security games with defender teams that coordinate under uncertainty; (ii) New algorithm based on column generation that utilizes Decentralized Markov Decision Processes (Dec-MDPs) to generate defender strategies that incorporate uncertainty; (iii) New techniques to handle global events (when one or more agents may leave the system) during defender execution; (iv) Heuristics that help scale up in the number of targets and resources to handle real-world scenarios; (v) Exploration of the robustness of randomized pure strategies. Different mechanisms, from both solving situations with and without execution uncertainty, may be used depending on the features of the domain. This thesis opens the door to a powerful combination of previous work in multiagent systems on teamwork and security games.
2015_19_teamcore_shieh_thesis_20150324.pdf L. S. Marcolino, H. Xu, A.X. Jiang, M. Tambe, and E. Bowring. 2015. “
The Power of Teams that Disagree: Team Formation in Large Action Spaces .” In Coordination, Organizations, Institutions and Norms in Agent Systems X. Springer-Verlag Lecture Notes in AI, 2015.
AbstractRecent work has shown that diverse teams can outperform a uniform
team made of copies of the best agent. However, there are fundamental questions
that were never 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, where we prove that the performance
of a diverse team improves as the size of the action space increases. Moreover, we
show that the performance converges exponentially fast to the optimal one as we
increase the number of agents. We present synthetic experiments that give 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 a diverse team improves in performance
as the board size increases, and eventually overcomes a uniform team.1
2015_32_teamcore_coin2014book.pdf Amulya Yadav, Leandro Soriano Marcolino, Eric Rice, Robin Petering, Hailey Winetrobe, Harmony Rhoades, Milind Tambe, and Heather Carmichael. 2015. “
PSINET: Aiding HIV Prevention Amongst Homeless Youth by Planning Ahead .” AI Magazine.
AbstractHomeless youth are prone to Human Immunodeficiency
Virus (HIV) due to their engagement in high risk behavior such as unprotected sex, sex under influence of
drugs, etc. Many non-profit agencies conduct interventions to educate and train a select group of homeless
youth about HIV prevention and treatment practices and
rely on word-of-mouth spread of information through
their social network. Previous work in strategic selection of intervention participants does not handle uncertainties in the social network’s structure and evolving network state, potentially causing significant shortcomings in spread of information. Thus, we developed
PSINET, a decision support system to aid the agencies
in this task. PSINET includes the following key novelties: (i) it handles uncertainties in network structure
and evolving network state; (ii) it addresses these uncertainties by using POMDPs in influence maximization;
and (iii) it provides algorithmic advances to allow high
quality approximate solutions for such POMDPs. Simulations show that PSINET achieves ∼60% more information spread over the current state-of-the-art. PSINET
was developed in collaboration with My Friend’s Place
(a drop-in agency serving homeless youth in Los Angeles) and is currently being reviewed by their officials.
2015_25_teamcore_aimag_yadav.pdf Amulya Yadav, Leandro Marcolino, Eric Rice, Robin Petering, Hailey Winetrobe, Harmony Rhoades, Milind Tambe, and Heather Carmichael. 2015. “
PSINET - An Online POMDP Solver for HIV Prevention in Homeless Populations .” In In AAAI-15 Workshop on Planning, Search, and Optimization (PlanSOpt-15).
AbstractHomeless youth are prone to Human Immunodeficiency
Virus (HIV) due to their engagement in high risk behavior such as unprotected sex, sex under influence of
drugs, etc. Many non-profit agencies conduct interventions to educate and train a select group of homeless
youth about HIV prevention and treatment practices and
rely on word-of-mouth spread of information through
their social network. Previous work in strategic selection of intervention participants does not handle uncertainties in the social network’s structure and evolving network state, potentially causing significant shortcomings in spread of information. Thus, we developed
PSINET, a decision support system to aid the agencies
in this task. PSINET includes the following key novelties: (i) it handles uncertainties in network structure
and evolving network state; (ii) it addresses these uncertainties by using POMDPs in influence maximization;
and (iii) it provides algorithmic advances to allow high
quality approximate solutions for such POMDPs. Simulations show that PSINET achieves ∼60% more information spread over the current state-of-the-art. PSINET
was developed in collaboration with My Friend’s Place
(a drop-in agency serving homeless youth in Los Angeles) and is currently being reviewed by their officials.
2015_4_teamcore_yadav.pdf Arjun Tambe and Thanh Nguyen. 2015. “
Robust Resource Allocation in Security Games and Ensemble Modeling of Adversary Behavior .” In ACM Symposium on Applied Computing (ACM SAC 2015) Track on Intelligent Robotics and Multi-Agent Systems (IRMAS).
AbstractGame theoretic algorithms have been used to optimize the
allocation of security resources to improve the protection of critical
infrastructure against threats when limits on security resources
prevent full protection of all targets. Past approaches have assumed
adversaries will always behave to maximize their expected utility,
failing to address real-world adversaries who are not perfectly
rational. Instead, adversaries may be boundedly rational, i.e., they
generally act to increase their expected value but do not
consistently maximize it. A successful approach to addressing
bounded adversary rationality has been a robust approach that does
not explicitly model adversary behavior. However, these robust
algorithms implicitly rely on an efficiently computable weak model
of adversary behavior, which does not necessarily match adversary
behavior trends. We therefore propose a new robust algorithm that
provides a more refined model of adversary behavior that retains
the advantage of efficient computation. We also develop an
ensemble method used to tune the algorithm’s parameters, and
compare this method’s accuracy in predicting adversary behavior
to previous work. We test these contributions in security games
against human subjects to show the advantages of our approach.
2015_5_teamcore_arjun_paper.pdf