Select a calendar:
Filter April Events by Event Type:
SUNMONTUEWEDTHUFRISAT
Events for April 08, 2016
-
PhD Defense - Thanh Nguyen
Fri, Apr 08, 2016 @ 10:00 AM - 12:00 PM
Thomas Lord Department of Computer Science
University Calendar
Title: Combating Adversaries under Uncertainties in Real-world Security Problems: Advanced Game-theoretic Behavioral Models and Robust Algorithms
Location: EEB 248
Date: April 8th
Time: 10am-12pm
Phd Candidate: Thanh Nguyen
Committee members:
Prof. Milind Tambe (Chair)
Prof. David Kempe
Prof. Jonathan Gratch
Prof. William Halfond
Prof. Richard John
Prof. Ariel Procaccia
Abstract:
Security is a global concern. Real-world security problems range from domains such as the protection of ports and airports from terrorists to protecting forests and wildlife from smugglers and poachers. A key challenge in solving these security problems is that security resources are limited; not all targets can be protected all the time. Therefore, security resources must be deployed intelligently, taking into account responses of attackers and potential uncertainties over their types, preference, and knowledge. Stackelberg Security Games (SSG) have drawn a significant amount of interest from security agencies. SSG-based decision aids are in widespread use for the protection of assets such as major ports in the US and airport terminals.
My research focuses on addressing uncertainties in SSGs --- one recognized area of weakness in SSGs. For example, adversary payoff values can be extremely difficult to assess and are generally characterized by significant uncertainty. My thesis provides innovative techniques and significant advances in addressing these uncertainties in SSGs. First, in many security problems, human adversaries are known to be boundedly rational, and often choose targets with non-highest expected value to attack. I introduce novel behavioral models of adversaries which significantly advance the state-of-the-art models in capturing the adversaries' decision making. More specifically, my new model for predicting poachers'behavior in wildlife protection is the first game-theoretic model which takes into account key domain challenges including the imperfect poaching data and complex temporal dependencies in the poachers' behavior. The superiority of my new models over the existing ones is demonstrated via extensive experiments based on the biggest real-world poaching dataset collected in a national park in Uganda over 12 years. Second, my research also focuses on developing new robust algorithms which address uncertainties in real-world security problems. I present the first unified maximin-based robust algorithm - a single algorithm -to handle all different types of uncertainties explored in SSGs. Furthermore, I propose a less conservative decision criterion; minimax regret for generating new, candidate defensive strategies that handle uncertainties in SSGs. In fact, this is the first time minimax regret has ever been used for addressing uncertainties in SSGs. I then present novel robust algorithms to compute minimax regret for addressing payoff uncertainty.
A contribution of particular significance is that my work is deployed in the real-world; I have deployed my robust algorithms and behavioral models for the PAWS system, which is currently being used by NGOs (Panthera and Rimba) in a conservation area in Malaysia.
Location: 248
Audiences: Everyone Is Invited
Contact: Lizsl De Leon
-
PhD Defense - Fei Fang
Fri, Apr 08, 2016 @ 01:00 PM - 03:00 PM
Thomas Lord Department of Computer Science
University Calendar
Title: Towards Addressing Spatio-Temporal Aspects in Security Games
PhD Candidate: Fei Fang
Committee members: Milind Tambe (advisor), Leana Golubchik, Jelena Mirkovic, Suvrajeet Sen, Shaddin Dughmi
Location: RTH 526
Time: April 8, 1pm-3pm
Abstract:
Game theory has been successfully used to handle complex resource allocation and patrolling problems in security and sustainability domains. More specifically, real-world applications have been deployed for different domains based on the framework of ``security games'', where the defender (e.g., security agency) has a limited number of resources to protect a set of targets from an adversary (e.g., criminal, terrorist). Whereas the first generation of security games research provided algorithms for optimizing security resources in mostly static settings, my thesis advances the state-of-the-art to a new generation of security games, handling massive games with complex spatio-temporal settings and leading to real-world applications that have fundamentally altered current practices of security resource allocation. My thesis provides the first algorithms and models for advancing key aspects of spatio-temporal challenges in security games, including (i) continuous time; (ii) continuous space; (iii) frequent and repeated attacks; (iv) complex spatial constraints.
First, focusing on games where actions are taken over continuous time (for example games with moving targets such as ferries and refugee supply lines), I propose a new game model that accurately models the continuous strategy space for the attacker and provide an efficient solution that uses compact representation for both the defender and the attacker's strategy space. Second, for games where actions are taken over continuous space (for example games with forest land as a target), I provide an algorithm computing the optimal distribution of patrol effort. Third, my work addresses challenges with one key dimension of complexity -- frequent and repeated attacks. Motivated by the repeated interaction of players in domains such as preventing poaching and illegal fishing, I introduce a novel game model that deals with frequent and repeated attacks and provide algorithms to plan effective sequential defender strategies. Furthermore, I handle complex spatial constraints that arise from the problem of designing optimal patrol strategy given complex topographical information.
My thesis work has led to two applications which have been deployed in the real world and have fundamentally altered previously used tactics, including one used by the US Coast Guard for protecting the Staten Island Ferry in New York City in past few years and another deployed in a protected area in Southeast Asia to combat illegal poaching.
Location: Ronald Tutor Hall of Engineering (RTH) - 526
Audiences: Everyone Is Invited
Contact: Lizsl De Leon
