2013
Jun-young Kwak. 5/2013. “
The Power of Flexibility: Autonomous Agents That Conserve Energy in Commercial Buildings ”.
AbstractAgent-based systems for energy conservation are now a growing area of research in multiagent
systems, with applications ranging from energy management and control on the smart grid, to
energy conservation in residential buildings, to energy generation and dynamic negotiations in
distributed rural communities. Contributing to this area, my thesis presents new agent-based
models and algorithms aiming to conserve energy in commercial buildings.
More specifically, my thesis provides three sets of algorithmic contributions. First, I provide
online predictive scheduling algorithms to handle massive numbers of meeting/event scheduling
requests considering flexibility, which is a novel concept for capturing generic user constraints
while optimizing the desired objective. Second, I present a novel BM-MDP (Bounded-parameter
Multi-objective Markov Decision Problem) model and robust algorithms for multi-objective
optimization under uncertainty both at the planning and execution time. The BM-MDP model
and its robust algorithms are useful in (re)scheduling events to achieve energy efficiency in the
presence of uncertainty over user’s preferences. Third, when multiple users contribute to energy
savings, fair division of credit for such savings to incentivize users for their energy saving activities
arises as an important question. I appeal to cooperative game theory and specifically to the concept
of Shapley value for this fair division. Unfortunately, scaling up this Shapley value computation is
a major hindrance in practice. Therefore, I present novel approximation algorithms to efficiently compute the Shapley value based on sampling and partitions and to speed up the characteristic
function computation.
These new models have not only advanced the state of the art in multiagent algorithms, but
have actually been successfully integrated within agents dedicated to energy efficiency: SAVES,
TESLA and THINC. SAVES focuses on the day-to-day energy consumption of individuals and
groups in commercial buildings by reactively suggesting energy conserving alternatives. TESLA
takes a long-range planning perspective and optimizes overall energy consumption of a large
number of group events or meetings together. THINC provides an end-to-end integration within
a single agent of energy efficient scheduling, rescheduling and credit allocation. While SAVES,
TESLA and THINC thus differ in their scope and applicability, they demonstrate the utility of
agent-based systems in actually reducing energy consumption in commercial buildings.
I evaluate my algorithms and agents using extensive analysis on data from over 110,000 real
meetings/events at multiple educational buildings including the main libraries at the University
of Southern California. I also provide results on simulations and real-world experiments, clearly
demonstrating the power of agent technology to assist human users in saving energy in commercial
buildings.
2013_36_teamcore_junkwak-dissertation.pdf Zhengyu Yin. 2013. “
Addressing Uncertainty in Stackelberg Games for Security: Models and Algorithms ”.
AbstractRecently, there has been significant research interest in using game-theoretic approaches to allocate limited security resources to protect physical infrastructure including ports, airports, transit systems, and other critical national infrastructure as well as natural resources such as forests,
tigers, fish, and so on. Indeed, the leader-follower Stackelberg game model is at the heart of many
deployed applications. In these applications, the game model provides a randomized strategy for
the leader (security forces), under the assumption that the adversary will conduct surveillance
before launching an attack. Inevitably, the security forces are faced with the problem of uncertainty. For example, a security officer may be forced to execute a different patrol strategy from the
planned one due to unexpected events. Also, there may be significant uncertainty regarding the
amount of surveillance conducted by an adversary. While Bayesian Stackelberg games for modeling discrete uncertainty have been successfully used in deployed applications, they are NP-hard
problems and existing methods perform poorly in scaling up the number of types: inadequate for
complex real world problems. Furthermore, Bayesian Stackelberg games have not been applied
to model execution and observation uncertainty and finally, they require the availability of full
distributional information of the uncertainty. To overcome these difficulties, my thesis presents four major contributions. First, I provide
a novel algorithm Hunter for Bayesian Stackelberg games to scale up the number of types. Exploiting the efficiency of Hunter, I show preference, execution and observation uncertainty can
be addressed in a unified framework. Second, to address execution and observation uncertainty
(where distribution may be difficult to estimate), I provide a robust optimization formulation to
compute the optimal risk-averse leader strategy in Stackelberg games. Third, addressing the uncertainty of the adversary’s capability of conducting surveillance, I show that for a class of Stackelberg games motivated by real security applications, the leader is always best-responding with a
Stackelberg equilibrium strategy regardless of whether the adversary conducts surveillance or not.
As the final contribution, I provide TRUSTS, a novel game-theoretic formulation for scheduling
randomized patrols in public transit domains where timing is a crucial component. TRUSTS
addresses dynamic execution uncertainty in such spatiotemporal domains by integrating Markov
Decision Processes into the game-theoretic model. Simulation results as well as real-world trials
of TRUSTS in the Los Angeles Metro Rail system provide validations of my approach.
2013_14_teamcore_thesis.pdf Thanh H. Nguyen, Rong Yang, Amos Azaria, Sarit Kraus, and Milind Tambe. 2013. “
Analyzing the Effectiveness of Adversary Modeling in Security Games .” In Conference on Artificial Intelligence (AAAI).
AbstractRecent deployments of Stackelberg security games (SSG)
have led to two competing approaches to handle boundedly
rational human adversaries: (1) integrating models of human (adversary) decision-making into the game-theoretic algorithms, and (2) applying robust optimization techniques
that avoid adversary modeling. A recent algorithm (MATCH)
based on the second approach was shown to outperform the
leading modeling-based algorithm even in the presence of
significant amount of data. Is there then any value in using human behavior models in solving SSGs? Through extensive experiments with 547 human subjects playing 11102
games in total, we emphatically answer the question in the
affirmative, while providing the following key contributions:
(i) we show that our algorithm, SU-BRQR, based on a novel
integration of human behavior model with the subjective utility function, significantly outperforms both MATCH and its
improvements; (ii) we are the first to present experimental
results with security intelligence experts, and find that even
though the experts are more rational than the Amazon Turk
workers, SU-BRQR still outperforms an approach assuming
perfect rationality (and to a more limited extent MATCH);
(iii) we show the advantage of SU-BRQR in a new, large
game setting and demonstrate that sufficient data enables it
to improve its performance over MATCH.
2013_17_teamcore_aaai2013_suqr.pdf Jason Tsai, Yundi Qian, Yevgeniy Vorobeychik, Christopher Kiekintveld, and Milnd Tambe. 2013. “
Bayesian Security Games for Controlling Contagion .” In MAIN Workshop at AAMAS 2013, 2nd ed., 27: Pp. 200-217.
AbstractInfluence blocking games have been used to model adversarial domains with a social component, such as counterinsurgency. In these
games, a mitigator attempts to minimize the efforts of an influencer
to spread his agenda across a social network which is modeled as a
graph. Previous work has assumed that the influence graph structure is known with certainty by both players. However, in reality,
there is often significant information asymmetry between the mitigator and the influencer. We introduce a model of this information
asymmetry as a two-player zero-sum Bayesian game. Nearly all
past work in influence maximization and social network analysis
suggests that graph structure is fundamental in strategy generation,
leading to an expectation that solving the Bayesian game exactly
would be vastly superior to any technique that does not account
for uncertainty about the network structure. Surprisingly, we show
through extensive experimentation on synthetic and real-world social networks that many common forms of uncertainty can be addressed near-optimally by ignoring the vast majority of it and simply solving an abstracted game with a few randomly chosen types.
This suggests that optimal strategies of games that do not model
the full range of uncertainty in influence blocking games are in
many cases robust to uncertainty about the structure of the influence graph.
2013_21_teamcore_main2013_tsai-final_version.pdf J. Tsai, Y. Qian, Y. Vorobeychik, C. Kiekintveld, and M. Tambe. 2013. “
Bayesian security games for controlling contagion .” In ASE/IEEE International Conference on Social Computing(SocialCom).
AbstractInfluence blocking games have been used to model
adversarial domains with a social component, such as counterinsurgency. In these games, a mitigator attempts to minimize the
efforts of an influencer to spread his agenda across a social
network. Previous work has assumed that the influence graph
structure is known with certainty by both players. However, in
reality, there is often significant information asymmetry between
the mitigator and the influencer. We introduce a model of this
information asymmetry as a two-player zero-sum Bayesian game.
Nearly all past work in influence maximization and social network
analysis suggests that graph structure is fundamental in strategy
generation, leading to an expectation that solving the Bayesian
game exactly is crucial. Surprisingly, we show through extensive
experimentation on synthetic and real-world social networks that
many common forms of uncertainty can be addressed nearoptimally by ignoring the vast majority of it and simply solving an
abstracted game with a few randomly chosen types. This suggests
that optimal strategies of games that do not model the full range
of uncertainty in influence blocking games are typically robust
to uncertainty about the influence graph structure.
2013_30_teamcore_socialcom_cameraready.pdf J. Tsai, Y. Qian, M. Tambe, Y. Vorobeychik, and C. Kiekintveld. 2013. “
Bayesian Security Games for Controlling Contagion (Extended version) .” ASE Human Journal, 2, Pp. 168-181.
AbstractInfluence blocking games have been used to model adversarial domains with a social component, such as counterinsurgency. In these games, a mitigator attempts to minimize the efforts of an influencer to spread his agenda across a social network. Previous work has assumed that the influence graph structure is known with certainty by both players. However, in reality, there is often significant information asymmetry between the mitigator and the influencer. We introduce a model of this information asymmetry as a two-player zero-sum Bayesian game. Nearly all past work in influence maximization and social network analysis suggests that graph structure is fundamental in strategy generation, leading to an expectation that solving the Bayesian game exactly is crucial. Surprisingly, we show through extensive experimentation on synthetic and real-world social networks that many common forms of uncertainty can be addressed near-optimally by ignoring the vast majority of it and simply solving an abstracted game with a few randomly chosen types. This suggests that optimal strategies of games that do not model the full range of uncertainty in influence blocking games are typically robust to uncertainty about the influence graph structure.
2013_33_teamcore_79-386-1-pb.pdf Dehghani M., Immordino-Yang M. H., Graham J., Marsella S., Forbus K., Ginges J., Tambe M., and Maheswaran R. 2013. “
Computational Models of Moral Perception, Conflict & Elevation .” In International Association for Computing and Philosophy (IACAP) 2013.
AbstractComputational models of moral cognition will be critical to the creation of agents
and robots that operate autonomously in morally sensitive and complex domains. We
propose a framework for developing computational models of moral cognition based on
behavioral and neurobiological experimental results and field observations. Specifically,
we discuss the following critical issues in building such models: 1. Managing conflicts
between different moral concerns; 2. The role of moral perceptions in moral judgments;
3. Mechanisms and consequences of moral emotions; 4. Learning and adjusting moral
behavior. Moreover, we discuss computational architectures for building and exploring
models of moral cognition at different levels of analysis: individual, small groups and
large groups.
2013_26_teamcore_icap2013-june7-13-md-final.pdf 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).
AbstractWe 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.
AbstractIn 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).
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 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].
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? 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).
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_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.
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