Get me to my GATE on time: Efficiently solving general-sum Bayesian threat screening games

Aaron Schlenker, Matthew Brown, Arunesh Sinha, Milind Tambe, Ruta Mehta

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Threat Screening Games (TSGs) are used in domains where there is a set of individuals or objects to screen with a limited amount of screening resources available to screen them. TSGs are broadly applicable to domains like airport passenger screening, stadium screening, cargo container screening, etc. Previous work on TSGs focused only on the Bayesian zero-sum case and provided the MGA algorithm to solve these games. In this paper, we solve Bayesian general-sum TSGs which we prove are NP-hard even when exploiting a compact marginal representation. We also present an algorithm based upon a adversary type hierarchical tree decomposition and an efficient branch-and-bound search to solve Bayesian generalsum TSGs. With this we provide four contributions: (1) GATE, the first algorithm for solving Bayesian general-sum TSGs, which uses hierarchical type trees and a novel branch-and-bound search, (2) the Branch-and-Guide approach which combines branch-and-bound search with the MGA algorithm for the first time, (3) heuristics based on properties of TSGs for accelerated computation of GATE, and (4) experimental results showing the scalability of GATE needed for real-world domains.

Original languageEnglish (US)
Title of host publicationFrontiers in Artificial Intelligence and Applications
EditorsGal A. Kaminka, Frank Dignum, Eyke Hullermeier, Paolo Bouquet, Virginia Dignum, Maria Fox, Frank van Harmelen
PublisherIOS Press
Pages1476-1484
Number of pages9
ISBN (Electronic)9781614996712
DOIs
StatePublished - Jan 1 2016
Event22nd European Conference on Artificial Intelligence, ECAI 2016 - The Hague, Netherlands
Duration: Aug 29 2016Sep 2 2016

Publication series

NameFrontiers in Artificial Intelligence and Applications
Volume285
ISSN (Print)0922-6389

Other

Other22nd European Conference on Artificial Intelligence, ECAI 2016
Country/TerritoryNetherlands
CityThe Hague
Period8/29/169/2/16

ASJC Scopus subject areas

  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Get me to my GATE on time: Efficiently solving general-sum Bayesian threat screening games'. Together they form a unique fingerprint.

Cite this