Events Calendar

PhD Defense - Eric Shieh

Dissertation Title
Not a Lone Ranger: Unleashing Defender Teamwork in Security Games

PhD Candidate
Eric Shieh

Committee
Milind Tambe (chair), Morteza Dehghani, Cyrus Shahabi, Andrea Armani, Rahul Jain

Time and Place
Monday, 2 Feb, 1:30pm
EEB 248 Conference Room

Abstract
Given the global concerns about security, intelligent allocation of limited security resources has become a major challenge. Game theory offers a promising solution; in particular, Stackelberg Security Games (SSGs) have been used in modeling these types of problems via a defender and an attacker(s), and applications based on SSGs have been widely deployed in the United States and tested in countries around the world. 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; the number of pure strategies becomes too large for the game to be even represented in memory. 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 using incremental strategy generation, where defender pure strategies are generated one at a time. To efficiently generate strategies incrementally, I provide several novel techniques including: (i) an 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.

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 models of security games where a defender team's pure strategy is defined as a Dec-MDP policy for addressing coordination under uncertainty; (ii) New algorithms and heuristics that solve this new model and help scale up in the number of targets and agents to handle real-world scenarios; (iii) 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.

Location: Hughes Aircraft Electrical Engineering Center (EEB) - 248

Audiences: Everyone Is Invited

Contact: Lizsl De Leon