Publications by Year: 2013

2013
Jun-young Kwak. 5/2013. “The Power of Flexibility: Autonomous Agents That Conserve Energy in Commercial Buildings ”.Abstract
Agent-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 ”.Abstract
Recently, 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).Abstract
Recent 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.Abstract
Influence 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).Abstract
Influence 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.Abstract
Influence 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.Abstract
Computational 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).Abstract
We study security games with multiple defenders. To achieve maximum security, defenders must perfectly synchronize their randomized allocations of resources. However, in real-life scenarios (such as protection of the port of Boston) this is not the case. Our goal is to quantify the loss incurred by miscoordination between defenders, both theoretically and empirically. We introduce two notions that capture this loss under different assumptions: the price of miscoordination, and the price of sequential commitment. Generally speaking, our theoretical bounds indicate that the loss may be extremely high in the worst case, while our simulations establish a smaller yet significant loss in practice.
2013_20_teamcore_security_coordination.pdf
B. An, E. Shieh, R. Yang, M. Tambe, C. Baldwin, J. DiRenzo, B. Maule, and G. Meyer. 2013. “A Deployed Quantal Response Based Patrol Planning System for the US Coast Guard .” In Interfaces, 43, 5, Pp. 400-420.Abstract
In this paper we describe the model, theory developed and deployment of PROTECT, a game-theoretic system in use by the United States Coast Guard (USCG) in the Port of Boston for scheduling patrols. The USCG evaluated the deployment of PROTECT in the Port of Boston as a success and is currently evaluating the system in the Port of New York, with the potential for nationwide deployment. The PROTECT system is premised on an attacker-defender Stackelberg game model but its development and implementation required both theoretical contributions and detailed evaluations. In this paper we describe the work required in the deployment which we group into five key innovations. First, we propose a compact representation of the defender’s strategy space, by exploiting equivalence and dominance, that makes PROTECT efficient enough to solve real world sized problems. Second, this system does not assume that adversaries are perfectly rational, a regular assumption in previous game theoretic models for security. Instead, PROTECT relies on a quantal response (QR) model of the adversary’s behavior — to the best of our knowledge, this is the first real-world deployment of a QR model. Third, we develop specialized solution algorithms that are able to solve this problem for real-world instances and give theoretical guarantees. Fourth, our experimental results illustrate that PROTECT’s QR model handles real-world uncertainties more robustly than a perfect rationality model. Finally, this paper presents real-world evaluation of PROTECT by: (i) a comparison of human-generated vs PROTECT security schedules, and (ii) results from an Adversarial Perspective Team’s (human mock attackers) analysis.
2013_35_teamcore_protect_wagner_informs.pdf
Fei Fang, Albert Xin Jiang, and Milind Tambe. 2013. “Designing Optimal Patrol Strategy for Protecting Moving Targets with Multiple Mobile Resources .” In International Workshop on Optimisation in Multi-Agent Systems (OPTMAS).Abstract
Previous work on Stackelberg Security Games for scheduling security resources has mostly assumed that the targets are stationary relative to the defender and the attacker, leading to discrete game models with finite numbers of pure strategies. This paper in contrast focuses on protecting mobile targets that lead to a continuous set of strategies for the players. The problem is motivated by several real-world domains including protecting ferries with escorts and protecting refugee supply lines. Our contributions include: (i) a new game model for multiple mobile defender resources and moving targets with a discretized strategy space for the defender and a continuous strategy space for the attacker; (ii) an efficient linear-program-based solution that uses a compact representation for the defender’s mixed strategy, while accurately modeling the attacker’s continuous strategy using a novel sub-interval analysis method; (iii) a heuristic method of equilibrium refinement for improved robustness and (iv) detailed experimental analysis in the ferry protection domain.
2013_13_teamcore_optmas2013_ferry.pdf
L. S. Marcolino, D. Chen, A.X. Jiang, and M. Tambe. 2013. “Diversity Beats Strength? - A Hands-on Experience with 9x9 Go (Demonstration) .” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS) [Demonstrations Track].Abstract
Team formation is a critical step in deploying a multi-agent team. In some scenarios, agents coordinate by voting continuously. When forming such teams, should we focus on the diversity of the team or on the strength of each member? Can a team of diverse (and weak) agents outperform a uniform team of strong agents? In this demo, the user will be able to explore these questions by playing one of the most challenging board games: Go.
2013_10_teamcore_aamas2013-demo.pdf
Eric Shieh, Manish Jain, Albert Xin Jiang, and Milind Tambe. 2013. “Efficiently Solving Joint Activity Based Security Games .” In International Joint Conference on Artificial Intelligence (IJCAI).Abstract
Despite recent successful real-world deployments of Stackelberg Security Games (SSGs), scale-up remains a fundamental challenge in this field. The latest techniques do not scale-up to domains where multiple defenders must coordinate time-dependent joint activities. To address this challenge, this paper presents two branch-and-price algorithms for solving SSGs, SMARTO and SMARTH, with three novel features: (i) a column-generation approach that uses an ordered network of nodes (determined by solving the traveling salesman problem) to generate individual defender strategies; (ii) exploitation of iterative reward shaping of multiple coordinating defender units to generate coordinated strategies; (iii) generation of tighter upper-bounds for pruning by solving security games that only abide by key scheduling constraints. We provide extensive experimental results and formal analyses.
2013_15_teamcore_shieh_ijcai_2013_main.pdf
Eric Shieh, Manish Jain, Albert Xin Jiang, and Milind Tambe. 2013. “Efficiently Solving Time-Dependent Joint Activities in Security Games .” In Workshop on Optimization in Multiagent Systems (OPTMAS) at AAMAS.Abstract
Despite recent successful real-world deployments of Stackelberg Security Games (SSGs), scale-up remains a fundamental challenge in this field. The latest techniques do not scale-up to domains where multiple defenders must coordinate time-dependent joint activities. To address this challenge, this paper presents two branch-and-price algorithms for solving SSGs, SMARTO and SMARTH, with three novel features: (i) a column-generation approach that uses an ordered network of nodes (determined by solving the traveling salesman problem) to generate individual defender strategies; (ii) exploitation of iterative reward shaping of multiple coordinating defender units to generate coordinated strategies; (iii) generation of tighter upper-bounds for pruning by solving security games that only abide by key scheduling constraints. We provide extensive experimental results and formal analyses.
2013_16_teamcore_shieh_optmas2013_camera_ready.pdf
2013. “Empirical Evaluation of Computational Fear Contagion Models in Crowd Dispersions .” Journal of Autonomous Agents and Multiagent Systems, JAAMAS, 27, 2, Pp. 200-217.Abstract
t In social psychology, emotional contagion describes the widely observed phenomenon of one person’s emotions being influenced by surrounding people’s emotions. While the overall effect is agreed upon, the underlying mechanism of the spread of emotions has seen little quantification and application to computational agents despite extensive evidence of its impacts in everyday life. In this paper, we examine computational models of emotional contagion by implementing two models ((Bosse et al, 2009b) and (Durupinar, 2010)) that draw from two separate lines of contagion research: thermodynamics-based and epidemiologicalbased. We first perform sensitivity tests on each model in an evacuation simulation, ESCAPES, showing both models to be reasonably robust to parameter variations with certain exceptions. We then compare their ability to reproduce a real crowd panic scene in simulation, showing that the thermodynamics-style model (Bosse et al, 2009b) produces superior results due to the ill-suited contagion mechanism at the core of epidemiological models. We also identify that a graduated effect of fear and proximity-based contagion effects are key to producing the superior results. We then reproduce the methodology on a second video, showing that the same results hold, implying generality of the conclusions reached in the first scene.
2013_1_teamcore_iva-revisionv1.pdf
Pujol-Gonzalez, J. Cerquides, P. Meseguer, J. A. Rodriguez Aguilar, and M. Tambe. 2013. “Engineering the decentralized coordination of UAVs with limited communication range.” In Conference of the Spanish Association for Artificial Intelligence (CAEPIA), 2013.Abstract
This paper tackles the problem of allowing a team of UAVs with limited communication range to autonomously coordinate to service requests. We present two MRF-based solutions: one assumes independence between requests; and the other considers also the UAVs’ workloads. Empirical evaluation shows that the latter performs almost as well as state-of-the-art centralized techniques in realistic scenarios.
2013_28_teamcore_caepia-52.pdf
Samantha Luber, Zhengyu Yin, Francesco Delle Fave, Albert Xin Jiang, Milind Tambe, and John P. Sullivan. 2013. “Game-theoretic Patrol Strategies for Transit Systems: the TRUSTS System and its Mobile App (Demonstration) .” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS)[Demonstrations Track].Abstract
Fare evasion costs proof-of-payment transit systems significant losses in revenue. In 2007 alone, the Los Angeles Metro system, using proof-of-payment, suffered an estimated revenue loss of $5.6 million due to fare evasion [2]. In addition, resource limitations prevent officers from verifying all passengers. Thus, such officers periodically inspect a subset of the passengers based on a patrol strategy. Effective patrol strategies are then needed to deter fare evasion and maximize revenue in transit systems. In addition, since potential fare evaders can exploit knowledge about the patrol strategy to avoid inspection, an unpredictable patrol strategy is needed for effectiveness. Furthermore, due to transit system complexity, human schedulers cannot manually produce randomized patrol strategies, while taking into account all of the system’s scheduling constraints [3]. In previous work on computing game-theoretic patrol strategies, Bayesian Stackelberg games have been successfully used to model the patrolling problem. In this model, the security officer commits to a patrol strategy and the fare evaders observe this patrol strategy and select a counter strategy accordingly [4]. This approach has also been successfully deployed in real-world applications, including by the L.A. International Airport police, the U.S. Coast Guard at the Port of Boston, and the Federal Air Marshal Service [5]. However, this approach cannot be used within our setting due to the increased complexity of having more potential followers and scheduling constraints [6]. In addition, transit systems face the challenge of execution uncertainty, in which unexpected events cause patrol officers to fall off schedule and exist in unknown states in the model [1]. Addressing the increased complexity challenge, TRUSTS (Tactical Randomizations for Urban Security in Transit Systems) reduces the temporal and spatial scheduling constraints imposed by the transit system into a single transition graph, a compact representation of all possible movement throughout the transit system as flows from each station node [1]. In addition, TRUSTS remedies the execution uncertainty challenge by modeling the execution of patrol units as Markov Decision Processes (MDPs) [1]. In simulation and trial testing, the TRUSTS approach has generated effective patrol strategies for L.A. Metro System [1, 6]. In order to implement the TRUSTS approach in real-world transit systems, the METRO mobile app presented in this paper is being developed to work with TRUSTS to (i) provide officers with realtime TRUSTS-generated patrol schedules, (ii) provide recovery from schedule interruptions, and (iii) collect patrol data. An innovation in transit system patrol scheduling technology, the app works as an online agent that provides officers with the best set of patrol actions for maximizing fare evasion deterrence based on the current time and officer location. In this paper, we propose a demonstration of the TRUSTS system, composed of the TRUSTS and METRO app components, which showcases how the system works with emphasis on the mobile app for user interaction. To establish sufficient background context for the demonstration, this paper also presents a brief overview of the TRUSTS system, including the TRUSTS approach to patrol strategy generation in Section 2.1 and discussion of the METRO app’s features and user interface design in Section 2.2, and the expected benefits from deployment in the L.A. Metro System.
2013_11_teamcore_aamas_2013_camera_ready.pdf
Albert Xin Jiang, Zhengyu Yin, Chao Zhang, Milind Tambe, and Sarit Kraus. 2013. “Game-theoretic Randomization for Security Patrolling with Dynamic Execution Uncertainty.” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS).Abstract
In recent years there has been extensive research on game-theoretic models for infrastructure security. In time-critical domains where the security agency needs to execute complex patrols, execution uncertainty (interruptions) affect the patroller’s ability to carry out their planned schedules later. Indeed, experiments in this paper show that in some real-world domains, small fractions of execution uncertainty can have a dramatic impact. The contributions of this paper are threefold. First, we present a general Bayesian Stackelberg game model for security patrolling in dynamic uncertain domains, in which the uncertainty in the execution of patrols is represented using Markov Decision Processes. Second, we study the problem of computing Stackelberg equilibrium for this game. We show that when the utility functions have a certain separable structure, the defender’s strategy space can be compactly represented, and we can reduce the problem to a polynomial-sized optimization problem. Finally, we apply our approach to fare inspection in the Los Angeles Metro Rail system. Numerical experiments show that patrol schedules generated using our approach outperform schedules generated using a previous algorithm that does not consider execution uncertainty.
2013_6_teamcore_aamas13-execution.pdf
R. Yang, C. Kiekintvled, F. Ordonez, M. Tambe, and R. John. 2013. “Improving Resource Allocation Strategies Against Human Adversaries in Security Games: An Extended Study .” Artificial Intelligence Journal (AIJ), 195, Pp. 440-469.Abstract
Stackelberg games have garnered significant attention in recent years given their deployment for real world security. Most of these systems, such as ARMOR, IRIS and GUARDS have adopted the standard game-theoretical assumption that adversaries are perfectly rational, which is standard in the game theory literature. This assumption may not hold in real-world security problems due to the bounded rationality of human adversaries, which could potentially reduce the effectiveness of these systems. In this paper, we focus on relaxing the unrealistic assumption of perfectly rational adversary in Stackelberg security games. In particular, we present new mathematical models of human adversaries’ behavior, based on using two fundamental theory/method in human decision making: Prospect Theory (PT) and stochastic discrete choice model. We also provide methods for tuning the parameters of these new models. Additionally, we propose a modification of the standard quantal response based model inspired by rankdependent expected utility theory. We then develop efficient algorithms to compute the best response of the security forces when playing against the different models of adversaries. In order to evaluate the effectiveness of the new models, we conduct comprehensive experiments with human subjects using a web-based game, comparing them with models previously proposed in the literature to address the perfect rationality assumption on part of the adversary. Our experimental results show that the subjects’ responses follow the assumptions of our new models more closely than the previous perfect rationality assumption. We also show that the defender strategy produced by our new stochastic discrete choice model outperform the previous leading contender for relaxing the assumption of perfect rationality.Furthermore, in a separate set of experiments, we show the benefits of our modified stochastic model (QRRU) over the standard model (QR).
2013_5_teamcore_aij_2012_yang_final.pdf
2013. “Mitigating Multi-path Fading in a Mobile Mesh Network .” Ad-Hoc Networks Journal, 11, 4, Pp. 1510-1521.Abstract
By using robots as routers, a team of networked robots can provide a communication substrate to establish a wireless mesh network. The mobile mesh network can autonomously optimize its configuration, increasing performance. One of the main sources of radio signal fading in such a network is multi-path propagation, which can be mitigated by moving the senders or the receivers on the distance of the order of a wavelength. In this paper, we measure the performance gain when robots are allowed to make such small movements and find that it may be as much as 270%. Our main contribution is the design of a system that allows robots to cooperate and improve the real-world network throughput via a practical solution. We model the problem of which robots to move as a distributed constraint optimization problem (DCOP). Our study includes four local metrics to estimate global throughput.
2013_27_teamcore_adhoc-dcee.pdf
Chao Zhang, Albert Xin Jiang, Martin B. Short, P. Jeffrey Brantingham, and Milind Tambe. 2013. “Modeling Crime diffusion and crime suppression on transportation networks: An initial report.” In SNSC 2013: The AAAI Fall Symposium 2013 on Social Networks and Social Contagion.Abstract
In urban transportation networks, crime diffuses as criminals travel through the networks and look for illicit opportunities. It is important to first model this diffusion in order to recommend actions or patrol policies to control the diffusion of such crime. Previously, game theory has been used for such patrol policy recommendations, but these applications of game theory for security have not modeled the diffusion of crime that comes about due to criminals seeking opportunities; instead the focus has been on highly strategic adversaries that plan attacks in advance. To overcome this limitation of previous work, this paper provides the following key contributions. First, we provide a model of crime diffusion based on a quantal biased random movement (QBRM) of criminals opportunistically and repeatedly seeking targets. Within this model, criminals react to real-time information, rather than strategically planning their attack in advance. Second, we provide a gametheoretic approach to generate randomized patrol policies for controlling such diffusion.
2013_29_teamcore_crime_diffusion_model.pdf

Pages