Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

9-2016

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.

Discipline

Databases and Information Systems

Research Areas

Data Science and Engineering

Publication

Proceedings of 22nd European Conference on Artificial Intelligence (ECAI)

Volume

285

ISBN

978-1-61499-671-2

Identifier

10.3233/978-1-61499-672-9-1476

City or Country

The Hague, the Netherlands

Additional URL

http://doi.org/10.3233/978-1-61499-672-9-1476

Download

Share

COinS